summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/main/java/bjc/esodata/FlatNestIterator.java103
-rw-r--r--src/main/java/bjc/esodata/NestList.java388
-rw-r--r--src/test/java/bjc/esodata/NestListTest.java119
3 files changed, 610 insertions, 0 deletions
diff --git a/src/main/java/bjc/esodata/FlatNestIterator.java b/src/main/java/bjc/esodata/FlatNestIterator.java
new file mode 100644
index 0000000..42981f5
--- /dev/null
+++ b/src/main/java/bjc/esodata/FlatNestIterator.java
@@ -0,0 +1,103 @@
+package bjc.esodata;
+
+import java.util.*;
+
+import bjc.data.*;
+
+final class FlatNestIterator<Element> implements ListIterator<Element>
+{
+ private Deque<ListIterator<Either<Element, NestList<Element>>>> iterators;
+
+ public FlatNestIterator(ListIterator<Either<Element, NestList<Element>>> iterator)
+ {
+ this.iterators = new ArrayDeque<>();
+ this.iterators.add(iterator);
+ }
+
+ @Override
+ public boolean hasNext() {
+ boolean result = false;
+ do {
+ result = iterators.peek().hasNext();
+
+ if (result == false) iterators.pop();
+ } while (result == false && iterators.isEmpty() == false);
+
+ return result;
+ }
+
+ @Override
+ public Element next() {
+ Holder<Element> element = Holder.of(null);
+ do {
+ element = iterators.peek().next().extract((ele) -> {
+ return Holder.of(ele);
+ }, (lst) -> {
+ // Ignore empty sublists.
+ if (lst.size() != 0) iterators.push(lst.listIterator());
+
+ return null;
+ });
+ } while (element == null && hasNext());
+
+ if (element == null) throw new NoSuchElementException();
+
+ return element.getValue();
+ }
+
+ @Override
+ public boolean hasPrevious() {
+ boolean result = false;
+ do {
+ result = iterators.peek().hasPrevious();
+
+ if (result == false) iterators.pop();
+ } while (result == false && iterators.isEmpty() == false);
+
+ return result;
+ }
+
+ @Override
+ public Element previous() {
+ Holder<Element> element = Holder.of(null);
+ do {
+ element = iterators.peek().previous().extract((ele) -> {
+ return Holder.of(ele);
+ }, (lst) -> {
+ // Ignore empty sublists.
+ if (lst.size() != 0) iterators.push(lst.listIterator());
+
+ return null;
+ });
+ } while (element == null && hasPrevious());
+
+ if (element == null) throw new NoSuchElementException();
+
+ return element.getValue();
+ }
+
+ @Override
+ public int nextIndex() {
+ return iterators.peek().nextIndex();
+ }
+
+ @Override
+ public int previousIndex() {
+ return iterators.peek().previousIndex();
+ }
+
+ @Override
+ public void remove() {
+ iterators.peek().remove();
+ }
+
+ @Override
+ public void set(Element e) {
+ iterators.peek().set(Either.left(e));
+ }
+
+ @Override
+ public void add(Element e) {
+ iterators.peek().add(Either.left(e));
+ }
+} \ No newline at end of file
diff --git a/src/main/java/bjc/esodata/NestList.java b/src/main/java/bjc/esodata/NestList.java
new file mode 100644
index 0000000..9d9149c
--- /dev/null
+++ b/src/main/java/bjc/esodata/NestList.java
@@ -0,0 +1,388 @@
+package bjc.esodata;
+
+import static bjc.functypes.Combinators.*;
+
+import java.util.*;
+import java.util.function.*;
+
+import bjc.data.*;
+
+/**
+ * A list which can contain sublists of itself.
+ *
+ * N.B: Be careful if you form a recursive list, as there is no form of detection
+ * in place for that. Some operations may work, but those that do a deep traversal
+ * of the list will not.
+ *
+ * @author Ben Culkin
+ *
+ * @param <Element> The type contained in the list.
+ */
+public class NestList<Element> extends AbstractList<Either<Element, NestList<Element>>>
+{
+ private final List<Either<Element, NestList<Element>>> backing;
+
+ /**
+ * Create a new empty nesting list.
+ */
+ public NestList() {
+ backing = new ArrayList<>();
+ }
+
+ /**
+ * Create a new empty nesting list with the given capacity.
+ *
+ * @param cap The capacity for the nesting list.
+ */
+ public NestList(int cap) {
+ backing = new ArrayList<>(cap);
+ }
+
+ /**
+ * Add an element to this list.
+ *
+ * @param element The element to add to the list.
+ *
+ * @return Whether we could add the element.
+ */
+ public boolean addItem(Element element) {
+ return backing.add(Either.left(element));
+ }
+
+ /**
+ * Add a sublist to this list.
+ *
+ * @param element The sublist to add to this list.
+ *
+ * @return Whether we could add the sublist.
+ */
+ public boolean addItem(NestList<Element> element) {
+ return backing.add(Either.right(element));
+ }
+ /**
+ * Add elements to this list.
+ *
+ * @param elements The elements to add to the list.
+ *
+ * @return Whether we could add each element.
+ */
+ public boolean[] addItems(@SuppressWarnings("unchecked") Element... elements) {
+ boolean[] vals = new boolean[elements.length];
+
+ for (int i = 0; i < vals.length; i++)
+ {
+ vals[i] = addItem(elements[i]);
+ }
+
+ return vals;
+ }
+
+ /**
+ * Add sublists to this list.
+ *
+ * @param elements The sublists to add to this list.
+ *
+ * @return Whether we could add each sublist.
+ */
+ public boolean[] addItems(@SuppressWarnings("unchecked") NestList<Element>... elements) {
+ boolean[] vals = new boolean[elements.length];
+
+ for (int i = 0; i < vals.length; i++)
+ {
+ vals[i] = addItem(elements[i]);
+ }
+
+ return vals;
+ }
+
+ /**
+ * Add a sublist with the given elements to this list.
+ *
+ * @param elements The elements of the sublist.
+ *
+ * @return Whether or not we could add the sublist.
+ */
+ public boolean addSublist(@SuppressWarnings("unchecked") Element... elements) {
+ NestList<Element> container = new NestList<>(elements.length);
+
+ for (Element ele : elements) {
+ container.addItem(ele);
+ }
+
+ return addItem(container);
+ }
+
+ /**
+ * Return an iterator over a flattened version of this list.
+ *
+ * N.B: In certain cases involving empty sublists, the hasNext() operation\
+ * may not be 100% accurate. Be warned.
+ *
+ * @return An iterator over a flattened variant of this list.
+ */
+ public ListIterator<Element> flatIterator() {
+ return new FlatNestIterator<>(listIterator());
+ }
+
+ /**
+ * Flatten one level of nesting from this list.
+ *
+ * @return The list with one level of nesting flattened.
+ */
+ public NestList<Element> flatten() {
+ NestList<Element> flatterList = new NestList<>(size());
+
+ backing.forEach((element) ->
+ element.pick(flatterList::addItem, flatterList::addAll)
+ );
+
+ return flatterList;
+ }
+
+ /**
+ * Flatten this list recursively.
+ *
+ * @return A flattened form of this list.
+ */
+ public List<Element> deepFlatten() {
+ List<Element> flatList = new ArrayList<>();
+
+ flatIterator().forEachRemaining(flatList::add);
+
+ return flatList;
+ }
+
+ /**
+ * Get the total number of elements contained in this list and all sublists.
+ *
+ * @return The total number of elements contained in this list.
+ */
+ public int deepSize() {
+ int size = 0;
+
+ for (Either<Element, NestList<Element>> element : backing)
+ {
+ size += element.extract((ele) -> 1, (lst) -> lst.deepSize());
+ }
+
+ return size;
+ }
+
+ /**
+ * Replace all of the elements in this list in-place with transformed versions.
+ *
+ * @param elementOperator The operator to apply to elements.
+ * @param listOperator The operator to apply to sublists.
+ */
+ public void replace(
+ UnaryOperator<Element> elementOperator,
+ UnaryOperator<NestList<Element>> listOperator) {
+ backing.replaceAll((ele) -> ele.map(elementOperator, listOperator));
+ }
+
+ /**
+ * Perform a shallow mapping over this list.
+ *
+ * @param <NewElement> The new element type.
+ *
+ * @param elementMapper The function to map elements.
+ * @param listMapper The function to map lists.
+ *
+ * @return A new list containing the mapped elements.
+ */
+ public <NewElement> NestList<NewElement> map(
+ Function<Element, NewElement> elementMapper,
+ Function<NestList<Element>, NestList<NewElement>> listMapper)
+ {
+ NestList<NewElement> nest = new NestList<>(backing.size());
+
+ for (Either<Element, NestList<Element>> element : backing)
+ {
+ nest.add(element.map(elementMapper, listMapper));
+ }
+
+ return nest;
+ }
+
+ /**
+ * Perform a recursive mapping over this list.
+ *
+ * @param <NewElement> The new element type.
+ *
+ * @param mapper The element mapper.
+ *
+ * @return A new list with the same structure, but transformed elements.
+ */
+ public <NewElement> NestList<NewElement> deepMap(
+ Function<Element, NewElement> mapper)
+ {
+ return map(mapper, (lst) -> lst.deepMap(mapper));
+ }
+
+ /**
+ * Perform a mapping on the list with controllable recursion.
+ *
+ * Inspired by the function of the same name from Raku.
+ *
+ * @param <NewElement> The new element type.
+ *
+ * @param recurPredicate Determines whether to recur into a list or not.
+ * @param elementMapper The mapper on elements.
+ * @param listMapper The mapper on lists we aren't recursing into.
+ *
+ * @return A new list with its elements mapped.
+ */
+ public <NewElement> NestList<NewElement> duckMap(
+ Predicate<NestList<Element>> recurPredicate,
+ Function<Element, NewElement> elementMapper,
+ Function<NestList<Element>, NestList<NewElement>> listMapper)
+ {
+ return map(
+ elementMapper,
+ iftt(recurPredicate,
+ (list) -> list.duckMap(
+ recurPredicate, elementMapper, listMapper),
+ listMapper
+ )
+ );
+ }
+
+ /**
+ * Perform a reduction over this list.
+ *
+ * @param <Output> The type of the output value.
+ *
+ * @param initial The initial state of the output value.
+ * @param elementFolder The function to fold elements with.
+ * @param listFolder The function to fold lists with.
+ *
+ * @return The result of reducing the list.
+ */
+ public <Output> Output reduce(
+ Output initial,
+ BiFunction<Output, Element, Output> elementFolder,
+ BiFunction<Output, NestList<Element>, Output> listFolder)
+ {
+ Holder<Output> out = Holder.of(initial);
+ for (Either<Element, NestList<Element>> item : backing)
+ {
+ out.transform((state) -> item.extract(
+ (ele) -> elementFolder.apply(state, ele),
+ (lst) -> listFolder.apply(state, lst))
+ );
+ }
+
+ return out.getValue();
+ }
+
+ /**
+ * Perform a recursive reduction over this list.
+ *
+ * @param <Output> The type of the output value.
+ *
+ * @param initial The initial state of the output value.
+ * @param elementFolder The function to fold elements with.
+ *
+ * @return The result of recursively reducing the list.
+ */
+ public <Output> Output deepReduce(
+ Output initial,
+ BiFunction<Output, Element, Output> elementFolder)
+ {
+ return reduce(
+ initial,
+ elementFolder,
+ (state, lst) -> lst.deepReduce(state, elementFolder));
+ }
+
+ /**
+ * Conditionally expand elements of this list into the provided list.
+ *
+ * @param nest The list to expand elements into.
+ * @param expandPicker Picks whether or not to expand a list.
+ * @param recur Whether or not to recursively expand lists.
+ *
+ * @return The provided list.
+ */
+ public NestList<Element> expandInto(
+ NestList<Element> nest,
+ Predicate<NestList<Element>> expandPicker,
+ boolean recur)
+ {
+ return reduce(nest,
+ (state, item) -> with(state, (stat) -> stat.addItem(item)),
+ (state, list) -> {
+ if (expandPicker.test(list)) {
+ return list.reduce(nest,
+ (substate, subitem)
+ -> with(substate,
+ (subst) -> subst.addItem(subitem)),
+ (substate, sublist)
+ -> with(substate, (subst) -> {
+ if (recur) {
+ sublist.expandInto(
+ subst,
+ expandPicker,
+ recur);
+ } else {
+ subst.addItem(sublist);
+ }
+ }));
+ } else {
+ state.addItem(list);
+ return state;
+ }
+ });
+ }
+ // List methods and other things.
+
+ @Override
+ public boolean add(Either<Element, NestList<Element>> e) {
+ return backing.add(e);
+ }
+
+ @Override
+ public void add(int index, Either<Element, NestList<Element>> element) {
+ backing.add(index, element);
+ }
+
+ @Override
+ public Either<Element, NestList<Element>> get(int index) {
+ return backing.get(index);
+ }
+
+ @Override
+ public boolean remove(Object o) {
+ return backing.remove(o);
+ }
+
+
+ @Override
+ public Either<Element, NestList<Element>> remove(int index) {
+ return backing.remove(index);
+ }
+
+ @Override
+ public int size() {
+ return backing.size();
+ }
+
+ @Override
+ public int hashCode() {
+ final int prime = 31;
+ int result = super.hashCode();
+ result = prime * result + Objects.hash(backing);
+ return result;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) return true;
+ if (!super.equals(obj)) return false;
+ if (getClass() != obj.getClass()) return false;
+
+ NestList<?> other = (NestList<?>) obj;
+
+ return Objects.equals(backing, other.backing);
+ }
+}
diff --git a/src/test/java/bjc/esodata/NestListTest.java b/src/test/java/bjc/esodata/NestListTest.java
new file mode 100644
index 0000000..ff3723e
--- /dev/null
+++ b/src/test/java/bjc/esodata/NestListTest.java
@@ -0,0 +1,119 @@
+package bjc.esodata;
+
+import static org.junit.Assert.*;
+
+import java.util.*;
+
+import org.junit.*;
+
+import bjc.*;
+
+@SuppressWarnings("javadoc")
+public class NestListTest
+{
+
+ @Test
+ public void testAddItemElement() {
+ NestList<String> nl = new NestList<>();
+
+ assertEquals("NestLists are created empty", 0, nl.size());
+
+ nl.addItems("hello", "there");
+
+ assertEquals("Adding two items to an empty NestList makes it size 2",
+ 2, nl.size());
+ }
+
+ @Test
+ public void testAddItemNestListOfElement() {
+ NestList<String> nl = new NestList<>();
+
+ NestList<String> nl2 = new NestList<>();
+
+ nl2.addItem("friend");
+
+ nl.addItems("hello", "there");
+ nl.addItem(nl2);
+
+ assertEquals("Adding a sublist increases the size of NestList by 1",
+ 3, nl.size());
+ }
+
+ @Test
+ public void testAddSublist() {
+ NestList<String> nl = new NestList<>();
+
+ nl.addSublist("here", "is", "a");
+ nl.addItem("thing");
+
+ assertEquals("addSublist increases size of NestList by 1", 2, nl.size());
+ }
+
+ @Test
+ public void testFlatIterator() {
+ NestList<String> nl1 = new NestList<>();
+ NestList<String> nl2 = new NestList<>();
+ NestList<String> nl3 = new NestList<>();
+
+ nl1.addItems("of", "means");
+
+ nl2.addItem(nl1);
+
+ nl3.addItem("Hello");
+ nl3.addSublist("my", "unfortunate");
+ nl3.addItem("friend");
+ nl3.addItem(nl2);
+
+ TestUtils.assertIteratorEquals(nl3.flatIterator(),
+ "Hello", "my", "unfortunate", "friend", "of", "means");
+ }
+
+ @Test
+ public void testFlatten() {
+ NestList<String> nl1A = new NestList<>();
+ NestList<String> nl2A = new NestList<>();
+ NestList<String> nl3A = new NestList<>();
+
+ nl1A.addItems("of", "means");
+
+ nl2A.addItem(nl1A);
+
+ nl3A.addItem("Hello");
+ nl3A.addSublist("my", "unfortunate");
+ nl3A.addItem("friend");
+ nl3A.addItem(nl2A);
+
+ NestList<String> nl1B = new NestList<>();
+ NestList<String> nl2B = new NestList<>();
+
+ nl1B.addItems("of", "means");
+
+ nl2B.addItems("Hello", "my", "unfortunate", "friend");
+ nl2B.addItem(nl1B);
+
+ assertEquals("Flatten removes one level of nesting",
+ nl2B, nl3A.flatten());
+ }
+
+ @Test
+ public void testDeepFlatten() {
+ NestList<String> nl1 = new NestList<>();
+ NestList<String> nl2 = new NestList<>();
+ NestList<String> nl3 = new NestList<>();
+
+ nl1.addItems("of", "means");
+
+ nl2.addItem(nl1);
+
+ nl3.addItem("Hello");
+ nl3.addSublist("my", "unfortunate");
+ nl3.addItem("friend");
+ nl3.addItem(nl2);
+
+ List<String> testList = Arrays.asList(
+ "Hello", "my", "unfortunate", "friend", "of", "means");
+
+ assertEquals("deepFlatten flattens out all sublists",
+ testList, nl3.deepFlatten());
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-10 14:56:44 +0000