From e528aec6d2d277338d7ddfdceba38d62eff08657 Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Tue, 29 Sep 2015 10:03:30 -0400 Subject: More data structure work. Yet more imports from previous version. --- .../java/bjc/utils/data/bst/BinarySearchTree.java | 128 ++++++++++ .../bjc/utils/data/bst/DirectedWalkFunction.java | 43 ++++ .../main/java/bjc/utils/data/bst/ITreePart.java | 81 ++++++ .../src/main/java/bjc/utils/data/bst/TreeLeaf.java | 101 ++++++++ .../src/main/java/bjc/utils/data/bst/TreeNode.java | 173 +++++++++++++ .../java/bjc/utils/funcdata/FunctionalList.java | 282 +++++++++++++++++++++ .../utils/funcdata/FunctionalStringTokenizer.java | 55 ++++ 7 files changed, 863 insertions(+) create mode 100644 BJC-Utils2/src/main/java/bjc/utils/data/bst/BinarySearchTree.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/data/bst/DirectedWalkFunction.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/data/bst/ITreePart.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeLeaf.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeNode.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalStringTokenizer.java diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/bst/BinarySearchTree.java b/BJC-Utils2/src/main/java/bjc/utils/data/bst/BinarySearchTree.java new file mode 100644 index 0000000..509cfcd --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/data/bst/BinarySearchTree.java @@ -0,0 +1,128 @@ +package bjc.utils.data.bst; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.List; +import java.util.function.Predicate; + +import bjc.utils.data.bst.ITreePart.TreeLinearizationMethod; + +/** + * A binary search tree, with some mild support for functional traversal. + * + * @author ben + * + * @param The data type stored in the node. + */ +public class BinarySearchTree { + private Comparator comp; + private int nCount; + private ITreePart root; + + /** + * Create a new tree using the specified way to compare elements. + * @param cmp + */ + public BinarySearchTree(Comparator cmp) { + nCount = 0; + comp = cmp; + } + + /** + * Add a node to the binary search tree. + * @param dat The data to add to the binary search tree. + */ + public void addNode(T dat) { + nCount++; + if (root == null) { + root = new TreeNode(dat, null, null); + } else { + root.add(dat, comp); + } + } + + /** + * Balance the tree, and remove soft-deleted nodes for free. + * Takes O(N) time, but also O(N) space. + */ + public void balance() { + ArrayList elms = new ArrayList<>(nCount); + + root.forEach(TreeLinearizationMethod.INORDER, e -> elms.add(e)); + + root = null; + + int piv = elms.size() / 2; + int adj = 0; + + while((piv - adj) >= 0 && (piv + adj) < elms.size()) { + if(root == null) { + root = new TreeNode(elms.get(piv), null, null); + } else { + root.add(elms.get(piv + adj), comp); + root.add(elms.get(piv - adj), comp); + } + + adj++; + } + + if((piv - adj) >= 0) { + root.add(elms.get(piv - adj), comp); + } else if((piv + adj) < elms.size()) { + root.add(elms.get(piv + adj), comp); + } + } + + /** + * Get the root of the tree. + * @return The root of the tree. + */ + public ITreePart getRoot() { + return root; + } + + /** + * Soft-delete a node from the tree. + * Soft-deleted nodes stay in the tree until trim()/balance() is invoked, + * and are not included in traversals/finds. + * @param dat + */ + public void deleteNode(T dat) { + nCount--; + root.delete(dat, comp); + } + + /** + * Check if a node is in the tree + * @param dat The node to check the presence of for the tree. + * @return Whether or not the node is in the tree. + */ + public boolean isInTree(T dat) { + return root.contains(dat, comp); + } + + /** + * Traverse the tree in a specified way until the function fails + * @param tlm The way to linearize the tree for traversal + * @param p The function to use until it fails + */ + public void traverse(TreeLinearizationMethod tlm, Predicate p) { + root.forEach(tlm, p); + } + + /** + * Remove all soft-deleted nodes from the tree. + */ + public void trim() { + List nds = new ArrayList<>(nCount); + + traverse(TreeLinearizationMethod.PREORDER, d -> { + nds.add(d); + return true; + }); + + root = null; + + nds.forEach(d -> addNode(d)); + } +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/bst/DirectedWalkFunction.java b/BJC-Utils2/src/main/java/bjc/utils/data/bst/DirectedWalkFunction.java new file mode 100644 index 0000000..232f3d4 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/data/bst/DirectedWalkFunction.java @@ -0,0 +1,43 @@ +package bjc.utils.data.bst; + +/** + * Represents a function for doing a directed walk of a binary tree. + * @author ben + * + * @param + */ +@FunctionalInterface +public interface DirectedWalkFunction { + /** + * Represents the results used to direct a walk in a binary tree. + * + * @author ben + * + */ + public enum DirectedWalkResult { + /** + * Specifies that the function has succesfully completed + * + */ + SUCCESS, + /** + * Specifies that the function has failed. + */ + FAILURE, + /** + * Specifies that the function wants to move left in the tree next. + */ + LEFT, + /** + * Specifies that the function wants to move right in the tree next. + */ + RIGHT + } + + /** + * Perform a directed walk on a node of a tree. + * @param data The data stored in the node currently being visited + * @return The way the function wants the walk to go next. + */ + public DirectedWalkResult walk(T data); +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/bst/ITreePart.java b/BJC-Utils2/src/main/java/bjc/utils/data/bst/ITreePart.java new file mode 100644 index 0000000..5667ce1 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/data/bst/ITreePart.java @@ -0,0 +1,81 @@ +package bjc.utils.data.bst; + +import java.util.Comparator; +import java.util.function.BiFunction; +import java.util.function.Function; +import java.util.function.Predicate; + +/** + * A interface for the fundamental things that want to be part of a tree. + * @author ben + * + * @param The data contained in this part of the tree. + */ +public interface ITreePart { + /** + * Represents the ways to linearize a tree for traversal. + * @author ben + * + */ + public enum TreeLinearizationMethod { + /** + * Visit the left side of this tree part, the tree part itself, and then the right part. + */ + INORDER, + /** + * Visit the left side of this tree part, the right side, and then the tree part itself. + */ + POSTORDER, + /** + * Visit the tree part itself, then the left side of tthis tree part and then the right part. + */ + PREORDER + } + + /** + * Add a element below this tree part somewhere. + * @param dat The element to add below this tree part + * @param comp The thing to use for comparing values to find where to insert the tree part. + */ + void add(T dat, Comparator comp); + /** + * Collapses this tree part into a single value. + * Does not change the underlying tree. + * @param f The function to use to transform data into mapped form. + * @param bf The function to use to collapse data in mapped form into a single value. + * @return A single value from collapsing the tree. + */ + E collapse(Function f, BiFunction bf); + /** + * Check if this tre part or below it contains the specified data item + * @param data The data item to look for. + * @param cmp The comparator to use to search for the data item + * @return Whether or not the given item is contained in this tree part or its children. + */ + boolean contains(T data, Comparator cmp); + /** + * Get the data associated with this tree part. + * @return The data associated with this tree part. + */ + T data(); + /** + * Remove the given node from this tree part and any of its children. + * @param dat The data item to remove. + * @param cmp The comparator to use to search for the data item. + */ + void delete(T dat, Comparator cmp); + /** + * Execute a directed walk through the tree. + * @param ds The function to use to direct the walk through the tree. + * @return Whether the directed walk finished successfully. + */ + boolean directedWalk(DirectedWalkFunction ds); + /** + * Execute a provided function for each element of tree it succesfully completes for + * @param tlm The way to linearize the tree for executing + * @param c The function to apply to each element, where it returning false + * terminates traversal early + * @return Whether the traversal finished succesfully + */ + boolean forEach(TreeLinearizationMethod tlm, Predicate c); +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeLeaf.java b/BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeLeaf.java new file mode 100644 index 0000000..173afc1 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeLeaf.java @@ -0,0 +1,101 @@ +package bjc.utils.data.bst; + +import java.util.Comparator; +import java.util.function.BiFunction; +import java.util.function.Function; +import java.util.function.Predicate; + +/** + * A leaf in a tree. + * @author ben + * + * @param The data stored in the tree. + */ +public class TreeLeaf implements ITreePart { + protected T data; + protected boolean deleted; + + /** + * Create a new leaf holding the specified data. + * @param dat The data for the leaf to hold. + */ + public TreeLeaf(T dat) { + data = dat; + } + + /* + * Can't add things to a leaf. + * (non-Javadoc) + * @see bjc.utils.data.bst.ITreePart#add(java.lang.Object, java.util.Comparator) + */ + @Override + public void add(T dat, Comparator comp) { + throw new IllegalArgumentException("Can't add to a leaf."); + } + + /* + * Just transform our data. + * (non-Javadoc) + * @see bjc.utils.data.bst.ITreePart#collapse(java.util.function.Function, java.util.function.BiFunction) + */ + @Override + public E collapse(Function f, BiFunction bf) { + return f.apply(data); + } + + /* + * Only check our data. + * (non-Javadoc) + * @see bjc.utils.data.bst.ITreePart#contains(java.lang.Object, java.util.Comparator) + */ + @Override + public boolean contains(T data, Comparator cmp) { + return this.data.equals(data); + } + + /* + * Just get the data + * (non-Javadoc) + * @see bjc.utils.data.bst.ITreePart#data() + */ + @Override + public T data() { + return data; + } + + /* + * Just mark ourselves as "not here" + * (non-Javadoc) + * @see bjc.utils.data.bst.ITreePart#delete(java.lang.Object, java.util.Comparator) + */ + @Override + public void delete(T dat, Comparator cmp) { + if(data.equals(dat)) { + deleted = true; + } + } + + /* + * Just walk our data and only succede if the walk does, because there's nowhere left to go. + * (non-Javadoc) + * @see bjc.utils.data.bst.ITreePart#directedWalk(bjc.utils.data.bst.DirectedWalkFunction) + */ + @Override + public boolean directedWalk(DirectedWalkFunction ds) { + switch(ds.walk(data)) { + case SUCCESS: + return true; + default: + return false; + } + } + + /* + * Just check our data. + * (non-Javadoc) + * @see bjc.utils.data.bst.ITreePart#forEach(bjc.utils.data.bst.ITreePart.TreeLinearizationMethod, java.util.function.Predicate) + */ + public boolean forEach(TreeLinearizationMethod tlm, Predicate c) { + return c.test(data); + } +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeNode.java b/BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeNode.java new file mode 100644 index 0000000..660fd03 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeNode.java @@ -0,0 +1,173 @@ +package bjc.utils.data.bst; + +import static bjc.utils.data.bst.DirectedWalkFunction.DirectedWalkResult.*; + +import java.util.Comparator; +import java.util.function.BiFunction; +import java.util.function.Function; +import java.util.function.Predicate; + +/** + * A binary node in a tree. + * @author ben + * + * @param The data type stored in the tree. + */ +public class TreeNode extends TreeLeaf { + private ITreePart left; + private ITreePart right; + + /** + * Create a new node with the specified data and children. + * @param data The data to store in this node. + * @param left The left child of this node. + * @param right The right child of this node. + */ + public TreeNode(T data, ITreePart left, ITreePart right) { + super(data); + this.left = left; + this.right = right; + } + + /* + * Either adds it to the left/right, or undeletes itself. + * (non-Javadoc) + * @see bjc.utils.data.bst.TreeLeaf#add(java.lang.Object, java.util.Comparator) + */ + @Override + public void add(T dat, Comparator comp) { + switch (comp.compare(data, dat)) { + case -1: + if (left == null) { + left = new TreeNode(dat, null, null); + } else { + left.add(dat, comp); + } + case 0: + if (deleted) { + deleted = false; + } else { + throw new IllegalArgumentException( + "Can't add duplicate values"); + } + case 1: + if (right == null) { + right = new TreeNode(dat, null, null); + } else { + right.add(dat, comp); + } + } + } + + @Override + public E collapse(Function f, BiFunction bf) { + E tm = f.apply(data); + + if (left != null) { + if (right != null) { + return bf.apply(tm, bf.apply(left.collapse(f, bf), + right.collapse(f, bf))); + } else { + return bf.apply(tm, left.collapse(f, bf)); + } + } else { + if(right != null) { + return bf.apply(tm, right.collapse(f, bf)); + } else { + return tm; + } + } + } + + @Override + public boolean contains(T data, Comparator cmp) { + return directedWalk(ds -> { + switch (cmp.compare(data, ds)) { + case -1: + return LEFT; + case 0: + return deleted ? FAILURE : SUCCESS; + case 1: + return RIGHT; + default: + return FAILURE; + } + }); + } + + @Override + public void delete(T dat, Comparator cmp) { + directedWalk(new DirectedWalkFunction() { + @Override + public DirectedWalkResult walk(T ds) { + switch (cmp.compare(data, dat)) { + case -1: + return left == null ? FAILURE : LEFT; + case 0: + deleted = true; + return FAILURE; + case 1: + return right == null ? FAILURE : RIGHT; + default: + return DirectedWalkResult.FAILURE; + } + } + }); + } + + @Override + public boolean directedWalk(DirectedWalkFunction ds) { + switch (ds.walk(data)) { + case SUCCESS: + return true; + case LEFT: + return left.directedWalk(ds); + case RIGHT: + return right.directedWalk(ds); + case FAILURE: + return false; + default: + return false; + } + } + + @Override + public boolean forEach(TreeLinearizationMethod tlm, Predicate c) { + switch (tlm) { + case PREORDER: + return preorderTraverse(tlm, c); + case INORDER: + return inorderTraverse(tlm, c); + case POSTORDER: + return postorderTraverse(tlm, c); + default: + throw new IllegalArgumentException( + "Passed an incorrect TreeLinearizationMethod."); + } + } + + private boolean inorderTraverse(TreeLinearizationMethod tlm, + Predicate c) { + + return ((left == null ? true : left.forEach(tlm, c)) + && (deleted ? true : c.test(data)) + && (right == null ? true : right.forEach(tlm, c))); + } + + private boolean postorderTraverse(TreeLinearizationMethod tlm, + Predicate c) { + + return ((left == null ? true : left.forEach(tlm, c)) + && (right == null ? true : right.forEach(tlm, c)) + && (deleted ? true : c.test(data))); + + } + + private boolean preorderTraverse(TreeLinearizationMethod tlm, + Predicate c) { + + return ((deleted ? true : c.test(data)) + && (left == null ? true : left.forEach(tlm, c)) + && (right == null ? true : right.forEach(tlm, c))); + } +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java new file mode 100644 index 0000000..dc57fb5 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java @@ -0,0 +1,282 @@ +package bjc.utils.funcdata; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.Iterator; +import java.util.List; +import java.util.Random; +import java.util.function.BiConsumer; +import java.util.function.BiFunction; +import java.util.function.Consumer; +import java.util.function.Function; +import java.util.function.Predicate; + +import bjc.utils.data.GenHolder; + +/** + * A wrapper over another list that provides eager functional operations over it. + * Differs from a stream in every way except for the fact that they both provide functional + * operations. + * @author ben + * + * @param The type in this list + */ +public class FunctionalList { + private List wrap; + + /** + * Create a new empty functional list. + */ + public FunctionalList() { + wrap = new ArrayList<>(); + } + + /** + * Create a new functional list containing the specified items. + * @param items The items to put into this functional list. + */ + @SafeVarargs + public FunctionalList(E... items) { + wrap = new ArrayList<>(items.length); + + for (E item : items) { + wrap.add(item); + } + } + + /** + * Create a functional list using the same backing list as the provided list. + * + * @param fl The source for a backing list + */ + public FunctionalList(FunctionalList fl) { + // TODO Find out if this should make a copy of fl.wrap instead. + wrap = fl.wrap; + } + + /** + * Create a new functional list with the specified size. + * @param sz The size of the backing list . + */ + private FunctionalList(int sz) { + wrap = new ArrayList<>(sz); + } + + /** + * Create a new functional list as a wrapper of a existing list. + * @param l The list to use as a backing list. + */ + public FunctionalList(List l) { + wrap = l; + } + + /** + * Add an item to this list + * @param item The item to add to this list. + * @return Whether the item was added to the list succesfully. + */ + public boolean add(E item) { + return wrap.add(item); + } + + /** + * Check if all of the elements of this list match the specified predicate. + * @param p The predicate to use for checking. + * @return Whether all of the elements of the list match the specified predicate. + */ + public boolean allMatch(Predicate p) { + for (E item : wrap) { + if (!p.test(item)) { + return false; + } + } + return true; + } + + /** + * Check if any of the elements in this list match the specified list. + * @param p The predicate to use for checking. + * @return Whether any element in the list matches the provided predicate. + */ + public boolean anyMatches(Predicate p) { + for (E item : wrap) { + if (p.test(item)) { + return true; + } + } + return false; + } + + /** + * Combine this list with another one into a new list and merge the results. + * Works sort of like a combined zip/map over resulting pairs. + * Does not change the underlying list. + * + * NOTE: The returned list will have the length of the shorter of this list and the combined one. + * @param l The list to combine with + * @param bf The function to use for combining element pairs. + * @return A new list containing the merged pairs of lists. + */ + public FunctionalList combineWith(FunctionalList l, BiFunction bf) { + FunctionalList r = new FunctionalList<>(); + + Iterator i2 = l.wrap.iterator(); + + for (Iterator i1 = wrap.iterator(); i1.hasNext() && i2.hasNext();) { + r.add(bf.apply(i1.next(), i2.next())); + } + + return r; + } + + /** + * Get the first element in the list + * @return The first element in this list. + */ + public E first() { + return wrap.get(0); + } + + /** + * Apply a function to each member of the list, then flatten the results. + * Does not change the underlying list. + * @param f The function to apply to each member of the list. + * @return A new list containing the flattened results of applying the provided function. + */ + public FunctionalList flatMap(Function> f) { + FunctionalList fl = new FunctionalList<>(this.wrap.size()); + + forEach(e -> { + f.apply(e).forEach(e2 -> { + fl.add(e2); + }); + }); + + return fl; + } + + /** + * Apply a given action for each member of the list + * @param c The action to apply to each member of the list. + */ + public void forEach(Consumer c) { + wrap.forEach(c); + } + + /** + * Apply a given function to each element in the list and its index. + * @param c The function to apply to each element in the list and its index. + */ + public void forEachIndexed(BiConsumer c) { + int i = 0; + + for (E e : wrap) { + c.accept(i++, e); + } + } + + /** + * Retrieve a value in the list by its index. + * @param i The index to retrieve a value from. + * @return The value at the specified index in the list. + */ + public E getByIndex(int i) { + return wrap.get(i); + } + + /** + * Get the internal backing list. + * @return The backing list this list is based off of. + */ + public List getInternal() { + return wrap; + } + + /** + * Check if this list is empty. + * @return Whether or not this list is empty. + */ + public boolean isEmpty() { + return wrap.isEmpty(); + } + + /** + * Create a new list by applying the given function to each element in the list. + * Does not change the underlying list. + * @param f The function to apply to each element in the list + * @return A new list containing the mapped elements of this list. + */ + public FunctionalList map(Function f) { + FunctionalList fl = new FunctionalList<>(this.wrap.size()); + + forEach(e -> fl.add(f.apply(e))); + + return fl; + } + + /** + * Select a random item from this list, using the provided random number generator. + * @param rnd The random number generator to use. + * @return A random element from this list. + */ + public E randItem(Random rnd) { + return wrap.get(rnd.nextInt(wrap.size())); + } + + /** + * Reduce this list to a single value, using a accumulative approach. + * @param val The initial value of the accumulative state. + * @param bf The function to use to combine a list element with the accumulative state. + * @param finl The function to use to convert the accumulative state into a final result. + * @return A single value condensed from this list and transformed into its final state. + */ + public F reduceAux(T val, BiFunction bf, Function finl) { + GenHolder acum = new GenHolder<>(val); + + wrap.forEach(e -> { + acum.held = bf.apply(e, acum.held); + }); + + return finl.apply(acum.held); + } + + /** + * Perform a binary search for the specified key using the provided means of + * comparing elements. + * Since this IS a binary search, the list must have been sorted before hand. + * @param key The key to search for. + * @param cmp The way to compare elements for searching + * @return The element if it is in this list, or null if it is not. + */ + public E search(E key, Comparator cmp) { + int res = Collections.binarySearch(wrap, key, cmp); + + return (res >= 0) ? wrap.get(res) : null; + } + + /** + * Sort the elements of this list using the provided way of comparing elements. + * Does change the underlying list. + * @param cmp The way to compare elements for sorting. + */ + public void sort(Comparator cmp) { + Collections.sort(wrap, cmp); + } + + /* + * Reduce this item to a form useful for looking at in the debugger. + * (non-Javadoc) + * @see java.lang.Object#toString() + */ + public String toString() { + StringBuilder sb = new StringBuilder("("); + + forEach(s -> sb.append(s + ", ")); + + sb.deleteCharAt(sb.length()); + sb.append(")"); + + return sb.toString(); + } +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalStringTokenizer.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalStringTokenizer.java new file mode 100644 index 0000000..1732043 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalStringTokenizer.java @@ -0,0 +1,55 @@ +package bjc.utils.funcdata; + +import java.util.StringTokenizer; +import java.util.function.Consumer; +import java.util.function.Function; + +/** + * A string tokenizer that exposes a functional interface + * @author ben + * + */ +public class FunctionalStringTokenizer { + private StringTokenizer inp; + + /** + * Create a functional string tokenizer from a non-functional one + * @param inp The non-functional string tokenizer to wrap + */ + public FunctionalStringTokenizer(StringTokenizer inp) { + this.inp = inp; + } + + /** + * Execute a provided action for each of the remaining tokens + * @param f The action to execute for each token + */ + public void forEachToken(Consumer f) { + while(inp.hasMoreTokens()) { + f.accept(inp.nextToken()); + } + } + + /** + * Return the next token from the tokenizer + * Returns null if no more tokens are available + * @return The next token from the tokenizer + */ + public String nextToken() { + return inp.hasMoreTokens() ? inp.nextToken() : null; + } + + /** + * Convert the contents of this tokenizer into a list. + * Consumes all of the input from this tokenizer. + * @param f The function to use to convert tokens. + * @return A list containing all of the converted tokens. + */ + public FunctionalList toList(Function f) { + FunctionalList r = new FunctionalList<>(); + + forEachToken(tk -> r.add(f.apply(tk))); + + return r; + } +} -- cgit v1.2.3