ScopedList.java
/*
** Module : ScopedList.java
** Abstract : Implementation of a scoped list, biased toward high performance iteration
**
** Copyright (c) 2016-2023, Golden Code Development Corporation.
**
** -#- -I- --Date-- ------------------------------------------Description-------------------------------------
** 001 ECF 20160320 Created initial version to replace ScopedDictionary for use cases where fast
** iteration of elements is needed and lookup by key is not.
** 002 ECF 20190319 Added command line test harness.
** CA 20190319 Fixed the tail element adjustment for the ScopedList instance, when adding an
** element as last for a scope depth other than 0.
** 003 CA 20190911 Fixed tail/head adjustment when removing an element.
** 004 CA 20221006 In NodeList.remove, instead of looking through the entire linked list, use a map to
** identify the element's Node instance; if it exists, then remove can be completed.
** This is required because for dynamic buffers, the removed element is random. Refs #6821
** 005 GBB 20230512 Logging methods replaced by CentralLogger/ConversionStatus.
** 006 CA 20231129 Small changes to avoid 'invokeinterface' in the compiled bytecode.
*/
/*
** This program is free software: you can redistribute it and/or modify
** it under the terms of the GNU Affero General Public License as
** published by the Free Software Foundation, either version 3 of the
** License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU Affero General Public License for more details.
**
** You may find a copy of the GNU Affero GPL version 3 at the following
** location: https://www.gnu.org/licenses/agpl-3.0.en.html
**
** Additional terms under GNU Affero GPL version 3 section 7:
**
** Under Section 7 of the GNU Affero GPL version 3, the following additional
** terms apply to the works covered under the License. These additional terms
** are non-permissive additional terms allowed under Section 7 of the GNU
** Affero GPL version 3 and may not be removed by you.
**
** 0. Attribution Requirement.
**
** You must preserve all legal notices or author attributions in the covered
** work or Appropriate Legal Notices displayed by works containing the covered
** work. You may not remove from the covered work any author or developer
** credit already included within the covered work.
**
** 1. No License To Use Trademarks.
**
** This license does not grant any license or rights to use the trademarks
** Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
** of Golden Code Development Corporation. You are not authorized to use the
** name Golden Code, FWD, or the names of any author or contributor, for
** publicity purposes without written authorization.
**
** 2. No Misrepresentation of Affiliation.
**
** You may not represent yourself as Golden Code Development Corporation or FWD.
**
** You may not represent yourself for publicity purposes as associated with
** Golden Code Development Corporation, FWD, or any author or contributor to
** the covered work, without written authorization.
**
** 3. No Misrepresentation of Source or Origin.
**
** You may not represent the covered work as solely your work. All modified
** versions of the covered work must be marked in a reasonable way to make it
** clear that the modified work is not originating from Golden Code Development
** Corporation or FWD. All modified versions must contain the notices of
** attribution required in this license.
*/
package com.goldencode.p2j.util;
import com.goldencode.p2j.util.logging.*;
import java.io.*;
import java.util.*;
/**
* A linked list implementation which is organized into scopes, each representing a sub-list of
* elements. Scopes are pushed onto and popped from a logical stack. An element can only be added
* if at least one scope is present. The first scope is designated the global scope. The top
* scope is the current (most recently added) scope.
* <p>
* Elements can be added to any scope, using the {@link #addAt(int, Object)} method. Convenience
* methods exist to easily add an element to the global scope or to the current scope, and to
* add multiple elements at once. Elements can be removed from any scope, using the {@link
* #removeFrom(int, Object)} method. Convenience methods exist to remove multiple elements at
* once.
* <p>
* When a scope is popped, all elements associated with the current scope are removed.
* <p>
* A read-only sublist containing all the nodes in a particular scope is available via the {@link
* #sublistAtScope(int)} method. The number of scopes can be queried with {@link #scopes()}.
* <p>
* This class is meant to provide a high-performance implementation of a scoped list which is
* iterated often, in full, from head to tail.
*
* @author ecf
*
* @param <E>
* Element type.
*/
public class ScopedList<E>
implements Iterable<E>
{
/** Logger */
private static final CentralLogger LOG = CentralLogger.get(ScopedList.class);
/** List of scopes, each of which contain zero or more nodes */
private final ArrayList<NodeList> scopes = new ArrayList<>();
/** Head of the list */
private Node<E> head = null;
/** Tail of the list */
private Node<E> tail = null;
/** Number of nodes in the list */
private int size = 0;
/**
* Default constructor.
*/
public ScopedList()
{
}
/**
* Return the number of scopes currently open.
*
* @return Number of scopes.
*/
public int scopes()
{
return scopes.size();
}
/**
* Push a new, empty scope.
*/
public void pushScope()
{
NodeList scope = new NodeList();
scopes.add(scope);
}
/**
* Pop a scope, discarding all the nodes it contains.
*/
public void popScope()
{
int scopeCount = scopes();
NodeList scope = scopes.remove(scopeCount - 1);
size -= scope.size;
if (size == 0)
{
head = null;
}
// temporarily set tail to null, until we can fix it up below
tail = null;
if (scopeCount > 1)
{
// walk backward through the scopes until we find one with a non-null tail; this
// becomes our new tail
for (int i = scopeCount - 2; tail == null && i >= 0; i--)
{
NodeList prevScope = scopes.get(i);
if (prevScope.tail != null)
{
tail = prevScope.tail;
prevScope.tail.next = null;
}
}
}
}
/**
* Move all nodes from the current scope into the immediately enclosing scope. The current
* scope is left behind and must still be removed with a call to {@link #popScope()}, but it
* will be empty. If there are no elements or there is no enclosing scope, this method is a
* no-op.
*/
public void rollUp()
{
NodeList sublist = null;
if (scopes.size() <= 1 || (sublist = getScopeAtDepth(0)).isEmpty())
{
return;
}
// TODO: implement a more efficient algorithm than individual remove/add;
// entire sublist should be moved by just fixing up heads and tails, but there are a lot
// of edge cases to get right
for (E elem : sublist)
{
removeFrom(0, elem);
addAt(1, elem);
}
}
/**
* Add the given element to the tail of the current scope (also the tail of the list), or to
* the tail of the global (first) scope.
*
* @param global
* {@code true} to add the element to the tail of the global scope;
* {@code false} to add the element to the tail of the full list.
* @param element
* Element to be added.
*
* @throws NoSuchElementException
* if there is no scope in the list.
*/
public void add(boolean global, E element)
{
int depth = (global ? scopes() - 1 : 0);
addAt(depth, element);
}
/**
* Add the given element to the tail of the scope at the given scope depth, where zero depth
* represents the current scope, and a positive depth indicate older scopes. A depth of
* {@code scopes() - 1} indicates the global scope.
*
* @param depth
* Depth of the scope to which to add the element, as described above.
* @param element
* Element to be added.
*
* @throws NoSuchElementException
* if there is no scope in the list.
* @throws IndexOutOfBoundsException
* if {@code depth < 0 || depth >= scopes()}.
*/
public void addAt(int depth, E element)
{
NodeList scope = getScopeAtDepth(depth);
Node<E> n = new Node<>(element);
if (size == 0)
{
head = n;
tail = n;
}
else if (depth == 0)
{
// link to previous tail and set new tail to new node
n.previous = tail;
if (tail != null)
{
tail.next = n;
}
tail = n;
}
else
{
int scopeCount = scopes();
// walk back through scopes from the specified depth until we find a tail with which we
// can cross-link
for (int i = scopeCount - depth - 1; n.previous == null && i >= 0; i--)
{
NodeList s = scopes.get(i);
Node<E> scopeTail = s.tail;
if (scopeTail != null)
{
n.previous = scopeTail;
n.next = scopeTail.next;
if (n.next != null)
{
n.next.previous = n;
}
scopeTail.next = n;
}
}
// if we found no scope tail, the new node is the new head of the scoped list
if (n.previous == null)
{
n.next = head;
if (head != null)
{
head.previous = n;
}
head = n;
}
// check if this is the new tail element for the entire scoped list
if (n.next == null)
{
n.previous = tail;
if (tail != null)
{
tail.next = n;
}
tail = n;
}
}
size++;
scope.addNode(n);
}
/**
* Add all of the given elements, in their current order, to the tail of the current scope
* (also the tail of the list), or to the tail of the global (first) scope.
*
* @param global
* {@code true} to add the elements to the tail of the global scope;
* {@code false} to add the elements to the tail of the full list.
* @param elements
* Elements to be added.
*
* @throws NoSuchElementException
* if there is no scope in the list.
*/
public void addAll(boolean global, List<E> elements)
{
int depth = (global ? scopes() - 1 : 0);
for (E e : elements)
{
addAt(depth, e);
}
}
/**
* Remove the given element from the scope at the given depth, where zero depth represents
* the current scope, and a positive depth indicate older scopes. A depth of {@code scopes()
* - 1} indicates the global scope.
*
* @param depth
* Depth of the scope from which to remove the element, as described above.
* @param element
* Element to be removed.
*
* @return {@code true} if the element was removed;
* {@code false} if the element was not found.
*/
public boolean removeFrom(int depth, E element)
{
NodeList scope = getScopeAtDepth(depth);
if (scope.removeElement(element))
{
size--;
return true;
}
return false;
}
/**
* Remove all of the given elements from the current scope, or from the global (first) scope.
*
* @param global
* {@code true} to remove the elements from the global scope;
* {@code false} to remove the elements from the full list.
* @param elements
* Elements to be removed.
*
* @return The number of elements removed.
*/
public int removeAllFrom(boolean global, List<E> elements)
{
int scopeCount = scopes();
NodeList scope = (global ? scopes.get(0) : scopes.get(scopeCount - 1));
int removeCount = scope.removeAllElements(elements);
size -= removeCount;
if (size == 0)
{
head = null;
tail = null;
}
return removeCount;
}
/**
* Get an unmodifiable list view of the scope at the given depth, where zero depth represents
* the current scope, and a positive depth indicate older scopes. A depth of {@code scopes()
* - 1} indicates the global scope.
*
* @param depth
* Scope depth as described above.
*
* @return A list view of the scope. It can be inspected and iterated, but not modified.
* Any methods which would alter the list will throw {@code
* UnsupportedOperationException}.
*
* @throws NoSuchElementException
* if there is no scope in the list.
* @throws IndexOutOfBoundsException
* if {@code depth < 0 || depth >= scopes()}.
*/
public List<E> sublistAtScope(int depth)
{
return getScopeAtDepth(depth);
}
/**
* Obtain a read-only iterator on the full list of elements, which iterates from head to tail.
*
* @return A read-only iterator.
*/
public Iterator<E> iterator()
{
return new Iterator<E>()
{
private Node<E> current = head;
@Override
public boolean hasNext()
{
return (current != null);
}
@Override
public E next()
{
if (current == null)
{
throw new NoSuchElementException();
}
E value = current.value;
current = current.next;
return value;
}
};
}
/**
* Get a string representation of the contents of the list, primarily for debugging purposes.
* Note that only the elements are represented (the scopes are not demarcated) in this
* implementation.
*
* @return String representation of the list.
*/
@Override
public String toString()
{
StringBuilder buf = new StringBuilder("[");
int i = 0;
for (E e : this)
{
if (i++ > 0)
{
buf.append(", ");
}
buf.append(e);
}
buf.append(']');
return buf.toString();
}
/**
* Get the node list representing the scope at the given depth, where zero depth represents
* the current scope, and a positive depth indicate older scopes. A depth of {@code scopes()
* - 1} indicates the global scope.
*
* @param depth
* Scope depth as described above.
*
* @return The node list at the given depth.
*
* @throws NoSuchElementException
* if there is no scope in the list.
* @throws IndexOutOfBoundsException
* if {@code depth < 0 || depth >= scopes()}.
*/
private NodeList getScopeAtDepth(int depth)
{
if (scopes.isEmpty())
{
throw new NoSuchElementException();
}
return scopes.get(scopes.size() - 1 - depth);
}
/**
* A node in the list. Contains an element and points to its predecessor and successor nodes
* in the list (if any).
*
* @param <E>
* Element type.
*/
private static class Node<E>
{
/** Contained element */
final E value;
/** Previous node */
Node<E> previous = null;
/** Next node */
Node<E> next = null;
/**
* Constructor.
*
* @param value
* Contained element.
*/
Node(E value)
{
this.value = value;
}
/**
* Get a string representation of the node, primarily for debugging purposes. Describes the
* node's contained element, as well as the elements contained by the node's surrounding
* nodes.
*
* @return String representation of the node.
*/
@Override
public String toString()
{
StringBuilder buf = new StringBuilder();
buf.append(previous != null ? previous.value : null);
buf.append(" <- ");
buf.append(value);
buf.append(" -> ");
buf.append(next != null ? next.value : null);
return buf.toString();
}
}
/**
* A linked list of nodes representing a single scope in the containing, scoped list. This
* class implements the {@code List} interface to provide a read-only view of this scope's
* elements.
* <p>
* A private API is provided to allow add and removal operations by the enclosing class.
*/
private class NodeList
extends AbstractSequentialList<E>
{
/** Head of the list */
private Node<E> head = null;
/** Tail of the list */
private Node<E> tail = null;
/** Size of the list */
private int size = 0;
/**
* Keep all nodes' values in an identity map - this allows resolution of the {@link Node} the value is
* kept.
*/
private IdentityHashMap<E, Node<E>> valueToNodes = new IdentityHashMap<>();
/**
* Default constructor.
*/
NodeList()
{
}
/**
* Obtain a read-only list iterator on this scope's elements. Methods which modify the list
* throw {@code UnsupportedOperationException}.
*
* @param cursor
* Zero-based cursor position at which to begin the iteration.
*
* @return Read-only list iterator.
*
* @throws IndexOutOfBoundsException
* if {@code cursor < 0 || cursor > size()}
*/
@Override
public ListIterator<E> listIterator(int cursor)
{
return new Iter(cursor);
}
/**
* Get the number of elements in this list.
*
* @return Size of the list.
*/
@Override
public int size()
{
return size;
}
/**
* Add the given node to the tail of the list. This operation only affects the state of
* this node list (head, tail, and size), but does not change the state of the node
* itself. The node is cross-linked to surrounding nodes by the enclosing class.
*
* @param node
* Node to be added.
*/
private void addNode(Node<E> node)
{
// if new node is first node, set it as head of the list
if (head == null)
{
head = node;
}
// set new node as new tail; caller will cross-link nodes
tail = node;
valueToNodes.put(node.value, node);
size++;
}
/**
* Remove the node which contains the given element, if any.
* <p>
* This operation affects both the state of this node list (head, tail, size), the state of
* the enclosing list (head and tail, but not size), the state of the given node, and the
* state of surrounding nodes. If the element is found, its node's links to other nodes are
* broken, and those nodes' links are fixed up to reference one another.
*
* @param element
* Element whose containing node is to be removed from the list.
*
* @return {@code true} if the element was removed;
* {@code false} if the element was not found.
*/
private boolean removeElement(E element)
{
return (removeElement(head, tail, element) != null);
}
/**
* Remove all nodes which match the elements in the given list, using an algorithm that is
* biased toward an assumption that the given {@code elements} are in the same order as the
* nodes in the node list.
* <p>
* For each node removed, this operation affects both the state of this node list (head,
* tail, size), the state of the enclosing list (head and tail, but not size), the state of
* the given node, and the state of surrounding nodes. If an element is found, its node's
* links to other nodes are broken, and those nodes' links are fixed up to reference one
* another.
*
* @param elements
* Elements to be removed from the list.
*
* @return The number of elements removed from this node list.
*/
private int removeAllElements(List<E> elements)
{
int count = 0;
Node<E> removed = null;
for (E e : elements)
{
if (removed == null)
{
// single pass from head to tail
removed = removeElement(head, tail, e);
if (removed != null)
{
count++;
}
}
else
{
Node<E> start = removed.next;
Node<E> end = removed.previous;
if (start != null)
{
// scan from the node after the last removed node to the tail
removed = removeElement(start, tail, e);
if (removed != null)
{
count++;
}
}
if (end != null && removed == null)
{
// scan from the head to the node before the last removed node
removed = removeElement(head, end, e);
if (removed != null)
{
count++;
}
}
}
if (head == null)
{
// can't remove any more; node list is empty
break;
}
}
return count;
}
/**
* Remove the node which contains the given element, if any. The search for {@code element}
* is conducted by scanning forward from the given {@code start} node to the given {@code
* end} node.
* <p>
* This operation affects both the state of this node list (head, tail, size), the state of
* the enclosing list (head and tail, but not size), the state of the given node, and the
* state of surrounding nodes. If the element is found, its node's links to other nodes are
* broken, and those nodes' links are fixed up to reference one another.
*
* @param begin
* Node at which to start scanning for the given element.
* @param end
* Node at which to stop scanning for the given element.
* @param element
* Element whose containing node is to be removed from the list.
*
* @return {@code true} if the element was removed;
* {@code false} if the element was not found.
*/
private Node<E> removeElement(Node<E> begin, Node<E> end, E element)
{
Node<E> current = valueToNodes.get(element);
if (current == null)
{
return null;
}
Node<E> previous = current.previous;
Node<E> next = current.next;
// fix up enclosing ScopeList's head and tail, if necessary
if (current == ScopedList.this.head)
{
ScopedList.this.head = next;
}
if (current == ScopedList.this.tail)
{
ScopedList.this.tail = previous;
}
// fix up this scope's head and tail, if necessary
Node<E> newHead = this.head;
Node<E> newTail = this.tail;
if (current == this.head)
{
newHead = (current != this.tail ? next : null);
}
if (current == this.tail)
{
newTail = (current != this.head ? previous : null);
}
this.head = newHead;
this.tail = newTail;
// remove this node and cross-link the previous and next nodes to each other
if (previous != null)
{
previous.next = next;
}
if (next != null)
{
next.previous = previous;
}
size--;
valueToNodes.remove(current.value);
return current;
}
/**
* Implementation of a read-only list iterator for a node list. Reads only within the scope
* represented by the node list; nodes attached to the head and tail nodes, which are
* outside this scope, are ignored.
*/
private class Iter
implements ListIterator<E>
{
/** Node currently being iterated */
private Node<E> current = head;
/** Iteration cursor position */
private int index;
/**
* Constructor which accepts an initial cursor position.
*
* @param index
* Zero-based cursor position. The logical cursor is positioned before the
* element at this index.
*
* @throws IndexOutOfBoundsException
* if {@code index < 0 || index > size()}
*/
Iter(int index)
{
if (index < 0 || index > size)
{
throw new IndexOutOfBoundsException("index = " + index + "; size = " + size);
}
for (int i = 0; i < index; i++)
{
current = current.next;
}
this.index = index;
}
/**
* Indicate whether there is a next element to visit.
*
* @return {@code true} if there is a next element, else {@code false}.
*/
@Override
public boolean hasNext()
{
return (current != null);
}
/**
* Return the element immediately after the current cursor position and move the cursor
* forward one element.
*
* @throws NoSuchElementException
* if there is no available element to return.
*/
@Override
public E next()
{
if (current == null)
{
throw new NoSuchElementException();
}
E value = current.value;
current = (current != tail ? current.next : null);
index++;
return value;
}
/**
* Indicate whether there is a previous element to visit.
*
* @return {@code true} if there is a previous element, else {@code false}.
*/
@Override
public boolean hasPrevious()
{
return (current != null);
}
/**
* Return the element immediately before the current cursor position and move the cursor
* backward one element.
*
* @throws NoSuchElementException
* if there is no available element to return.
*/
@Override
public E previous()
{
if (current == null)
{
throw new NoSuchElementException();
}
E value = current.value;
current = (current != head ? current.previous : null);
index--;
return value;
}
/**
* Report the index of the element immediately after the cursor's current position.
* Note that this may report an invalid index beyond the last element.
*
* @return Next element's index.
*/
@Override
public int nextIndex()
{
return index;
}
/**
* Report the index of the element immediately before the cursor's current position.
* Note that this may report an invalid index beyond the first element.
*
* @return Next element's index.
*/
@Override
public int previousIndex()
{
return index - 1;
}
/**
* Remove the current element -- unsupported in this read-only implementation.
*
* @throws UnsupportedOperationException
* always.
*/
@Override
public void remove()
{
throw new UnsupportedOperationException();
}
/**
* Replace the current element -- unsupported in this read-only implementation.
*
* @throws UnsupportedOperationException
* always.
*/
@Override
public void set(E e)
{
throw new UnsupportedOperationException();
}
/**
* Add a new element after the current element -- unsupported in this read-only
* implementation.
*
* @throws UnsupportedOperationException
* always.
*/
@Override
public void add(E e)
{
throw new UnsupportedOperationException();
}
}
}
/**
* Simple, command line, test harness.
* <p>
* Commands:
* <ul>
* <li>"v" to push a scope</li>
* <li>"^" to pop a scope</li>
* <li>"a" to add an element</li>
* <li>"r" to remove an element</li>
* <li>"q" to quit</li>
* </ul>
*
* @param args
* None.
*/
public static void main(String[] args)
{
ScopedList<Integer> list = new ScopedList<>();
try (InputStreamReader reader = new InputStreamReader(System.in))
{
int next = 0;
outer:
while (true)
{
System.out.print("Command (v, ^, a, r, q): ");
switch (read(reader))
{
case "v":
list.pushScope();
System.out.println("Pushed scope");
break;
case "^":
if (list.scopes() == 0)
{
System.out.println("No scope to be popped");
continue;
}
list.popScope();
System.out.println("Popped scope");
break;
case "a":
if (list.scopes() == 0)
{
System.out.println("Must add a scope before an element; try again");
continue;
}
System.out.print("Add: global? (y, n): ");
boolean global = false;
switch (read(reader))
{
case "y":
global = true;
break;
}
list.add(global, ++next);
System.out.println("Added element");
break;
case "r":
if (list.scopes() == 0)
{
System.out.println("Must add a scope/element before removing; try again");
continue;
}
int depth, element;
while (true)
{
System.out.print("Remove: depth? (0-" + (list.scopes() - 1) + ") ");
try
{
depth = Integer.parseInt(read(reader));
}
catch (NumberFormatException exc)
{
System.out.println("Expected a number; try again");
continue;
}
if (depth < 0 || depth > list.scopes() - 1)
{
System.out.println("Try again");
continue;
}
List<Integer> sub = list.sublistAtScope(depth);
if (sub.isEmpty())
{
System.out.println("Nothing to remove at that depth; try again");
continue outer;
}
System.out.print("Remove: element? " + sub + " ");
try
{
element = Integer.parseInt(read(reader));
}
catch (NumberFormatException exc)
{
System.out.println("Expected a number; try again");
continue;
}
if (!sub.contains(element))
{
System.out.println("Try again");
continue;
}
break;
}
if (list.removeFrom(depth, element))
{
System.out.println("Removed element");
}
else
{
System.out.println("Not found");
}
break;
case "q":
return;
default:
System.out.println("Try again");
continue;
}
int scopes = list.scopes();
System.out.println("List: " + scopes + " " + list);
for (int i = 0; i < scopes; i++)
{
System.out.println("Depth " + i + ": " + list.sublistAtScope(i));
}
}
}
catch (Exception exc)
{
LOG.severe("", exc);
}
}
/**
* Read a string from the given stream reader.
*
* @param reader
* A stream reader.
*
* @return The string from the reader.
*
* @throws IOException
* if there is an error reading.
*/
private static String read(InputStreamReader reader)
throws IOException
{
char[] buf = new char[16];
int len = reader.read(buf);
return new String(buf, 0, len).trim();
}
}