From 0a8f34c27c6ef93c5c94d17728af62c7607e225f Mon Sep 17 00:00:00 2001 From: Ben Culkin Date: Thu, 3 Dec 2020 19:21:38 -0500 Subject: Rename types to match Java style This renames several interfaces that had names like IWhatever, since that isn't a style that Java uses --- src/main/java/bjc/data/Context.java | 62 +++ src/main/java/bjc/data/Contexts.java | 18 +- src/main/java/bjc/data/Either.java | 22 +- src/main/java/bjc/data/Holder.java | 177 ++++++ src/main/java/bjc/data/IContext.java | 62 --- src/main/java/bjc/data/IHolder.java | 177 ------ src/main/java/bjc/data/IPair.java | 250 --------- src/main/java/bjc/data/ITree.java | 286 ---------- src/main/java/bjc/data/Identity.java | 12 +- src/main/java/bjc/data/Lazy.java | 22 +- src/main/java/bjc/data/LazyPair.java | 22 +- src/main/java/bjc/data/ListHolder.java | 22 +- src/main/java/bjc/data/Option.java | 12 +- src/main/java/bjc/data/Pair.java | 306 +++++++---- src/main/java/bjc/data/SimplePair.java | 154 ++++++ src/main/java/bjc/data/SimpleTree.java | 446 +++++++++++++++ .../java/bjc/data/TopDownTransformIterator.java | 48 +- src/main/java/bjc/data/Tree.java | 606 ++++++++------------- src/main/java/bjc/data/internals/BoundLazy.java | 38 +- .../java/bjc/data/internals/BoundLazyPair.java | 40 +- .../java/bjc/data/internals/BoundListHolder.java | 24 +- .../java/bjc/data/internals/HalfBoundLazyPair.java | 40 +- src/main/java/bjc/data/internals/WrappedLazy.java | 24 +- .../java/bjc/data/internals/WrappedOption.java | 24 +- src/main/java/bjc/esodata/PushdownMap.java | 8 +- src/main/java/bjc/esodata/SimpleDirectory.java | 6 +- src/main/java/bjc/esodata/UnifiedDirectory.java | 6 +- src/main/java/bjc/funcdata/ExtendedMap.java | 14 +- src/main/java/bjc/funcdata/Freezable.java | 73 +++ src/main/java/bjc/funcdata/FunctionalList.java | 50 +- src/main/java/bjc/funcdata/FunctionalMap.java | 10 +- .../bjc/funcdata/FunctionalStringTokenizer.java | 6 +- src/main/java/bjc/funcdata/IFreezable.java | 73 --- src/main/java/bjc/funcdata/IList.java | 455 ---------------- src/main/java/bjc/funcdata/IMap.java | 216 -------- src/main/java/bjc/funcdata/ListEx.java | 455 ++++++++++++++++ src/main/java/bjc/funcdata/MapEx.java | 216 ++++++++ src/main/java/bjc/funcdata/ObjectFrozen.java | 2 +- .../java/bjc/funcdata/TransformedValueMap.java | 8 +- .../java/bjc/funcdata/bst/BinarySearchTree.java | 10 +- .../bjc/funcdata/bst/BinarySearchTreeLeaf.java | 2 +- .../bjc/funcdata/bst/BinarySearchTreeNode.java | 8 +- src/main/java/bjc/funcdata/bst/ITreePart.java | 107 ---- src/main/java/bjc/funcdata/bst/TreePart.java | 107 ++++ src/main/java/bjc/functypes/Combinators.java | 4 +- src/main/java/bjc/functypes/Fixpoints.java | 4 +- src/main/java/bjc/functypes/ListFlattener.java | 4 +- src/test/java/bjc/funcdata/TestMapCreation.java | 8 +- src/test/java/bjc/funcdata/TestMapOperations.java | 4 +- 49 files changed, 2375 insertions(+), 2375 deletions(-) create mode 100644 src/main/java/bjc/data/Context.java create mode 100644 src/main/java/bjc/data/Holder.java delete mode 100644 src/main/java/bjc/data/IContext.java delete mode 100644 src/main/java/bjc/data/IHolder.java delete mode 100644 src/main/java/bjc/data/IPair.java delete mode 100644 src/main/java/bjc/data/ITree.java create mode 100644 src/main/java/bjc/data/SimplePair.java create mode 100644 src/main/java/bjc/data/SimpleTree.java create mode 100644 src/main/java/bjc/funcdata/Freezable.java delete mode 100644 src/main/java/bjc/funcdata/IFreezable.java delete mode 100644 src/main/java/bjc/funcdata/IList.java delete mode 100644 src/main/java/bjc/funcdata/IMap.java create mode 100644 src/main/java/bjc/funcdata/ListEx.java create mode 100644 src/main/java/bjc/funcdata/MapEx.java delete mode 100644 src/main/java/bjc/funcdata/bst/ITreePart.java create mode 100644 src/main/java/bjc/funcdata/bst/TreePart.java diff --git a/src/main/java/bjc/data/Context.java b/src/main/java/bjc/data/Context.java new file mode 100644 index 0000000..7efdc4d --- /dev/null +++ b/src/main/java/bjc/data/Context.java @@ -0,0 +1,62 @@ +package bjc.data; + +/** + * Represents a 'context' which is a hierarchical set of objects. + * @author Ben Culkin + * + */ +public interface Context { + /** + * Register an object with this context. + * + * @param name The name of the object. + * @param o The object to register. + */ + void register(String name, Object o); + + /** + * Get the parent of this context. + * + * @return The parent of this context. + */ + Context getParent(); + + /** + * Get an object from this context. + * + * @param name The name of the object. + * + * @return The object bound to that name. + */ + Object get(String name); + + /** + * Get an object which is an instance of the provided class or a subclass + * thereof. + * + * @param The type of the object. + * + * @param contract The class of the object. + * + * @return An instance of the provided class. + */ + T get(Class contract); + + /** + * Get a named object which is an instance of the provided class or a subclass + * thereof. + * + * @param The type of the object. + * + * @param name The name of the object + * @param contract The class of the object. + * + * @return An instance of the provided class, with the given name.. + */ + default T get(String name, Class contract) { + Object obj = get(name); + return obj == null + ? getParent().get(name, contract) + : contract.cast(obj); + }; +} diff --git a/src/main/java/bjc/data/Contexts.java b/src/main/java/bjc/data/Contexts.java index 75c8480..b028ad1 100644 --- a/src/main/java/bjc/data/Contexts.java +++ b/src/main/java/bjc/data/Contexts.java @@ -12,7 +12,7 @@ public class Contexts { /** * The null context, which always throws an exception. */ - public static final IContext NULL = new NullContextImpl(); + public static final Context NULL = new NullContextImpl(); private Contexts() { throw new UnsupportedOperationException(); @@ -23,7 +23,7 @@ public class Contexts { * * @return A context with no parent. */ - public static IContext create() { + public static Context create() { return new ContextImpl(NULL); } @@ -34,13 +34,13 @@ public class Contexts { * * @return A context with the given context as its parent. */ - public static IContext create(IContext parent) { + public static Context create(Context parent) { return new ContextImpl(parent); } - private static class NullContextImpl implements IContext { + private static class NullContextImpl implements Context { @Override - public IContext getParent() { + public Context getParent() { return this; } @@ -60,13 +60,13 @@ public class Contexts { } } - private static class ContextImpl implements IContext { + private static class ContextImpl implements Context { - private final IContext parent; + private final Context parent; private final Map objects; - public ContextImpl(IContext parent) { + public ContextImpl(Context parent) { this.parent = parent; this.objects = new HashMap<>(); } @@ -96,7 +96,7 @@ public class Contexts { } @Override - public IContext getParent() { + public Context getParent() { return parent; } } diff --git a/src/main/java/bjc/data/Either.java b/src/main/java/bjc/data/Either.java index 0ac3181..e4bc63d 100644 --- a/src/main/java/bjc/data/Either.java +++ b/src/main/java/bjc/data/Either.java @@ -15,7 +15,7 @@ import java.util.function.Function; * The type that could be on the right. * */ -public class Either implements IPair { +public class Either implements Pair { /** * Create a new either with the left value occupied. * @@ -73,16 +73,16 @@ public class Either implements IPair { } @Override - public IPair bind( - final BiFunction> binder) { + public Pair bind( + final BiFunction> binder) { if (binder == null) throw new NullPointerException("Binder must not be null"); return binder.apply(leftVal, rightVal); } @Override - public IPair - bindLeft(final Function> leftBinder) { + public Pair + bindLeft(final Function> leftBinder) { if (leftBinder == null) throw new NullPointerException("Left binder must not be null"); if (isLeft) return leftBinder.apply(leftVal); @@ -90,8 +90,8 @@ public class Either implements IPair { } @Override - public IPair bindRight( - final Function> rightBinder) { + public Pair bindRight( + final Function> rightBinder) { if (rightBinder == null) throw new NullPointerException("Right binder must not be null"); if (isLeft) return new Either<>(leftVal, null); @@ -100,8 +100,8 @@ public class Either implements IPair { @Override public - IPair - combine(final IPair otherPair, + Pair + combine(final Pair otherPair, final BiFunction leftCombiner, final BiFunction rightCombiner) { @@ -129,7 +129,7 @@ public class Either implements IPair { } @Override - public IPair + public Pair mapLeft(final Function mapper) { if (mapper == null) throw new NullPointerException("Mapper must not be null"); @@ -138,7 +138,7 @@ public class Either implements IPair { } @Override - public IPair + public Pair mapRight(final Function mapper) { if (mapper == null) throw new NullPointerException("Mapper must not be null"); diff --git a/src/main/java/bjc/data/Holder.java b/src/main/java/bjc/data/Holder.java new file mode 100644 index 0000000..f01812e --- /dev/null +++ b/src/main/java/bjc/data/Holder.java @@ -0,0 +1,177 @@ +package bjc.data; + +import java.util.function.Consumer; +import java.util.function.Function; +import java.util.function.UnaryOperator; + +import bjc.data.internals.BoundListHolder; +import bjc.data.internals.WrappedLazy; +import bjc.data.internals.WrappedOption; +import bjc.funcdata.FunctionalList; +import bjc.funcdata.theory.Functor; + +/** + * A holder of a single value. + * + * @author ben + * + * @param + * The type of value held. + */ +public interface Holder extends Functor { + /** + * Bind a function across the value in this container. + * + * @param + * The type of value in this container. + * + * @param binder + * The function to bind to the value. + * + * @return A holder from binding the value. + */ + public Holder + bind(Function> binder); + + /** + * Apply an action to the value. + * + * @param action + * The action to apply to the value. + */ + public default void doWith(final Consumer action) { + transform(value -> { + action.accept(value); + + return value; + }); + } + + @Override + default Function, Functor> + fmap(final Function func) { + return argumentFunctor -> { + if (!(argumentFunctor instanceof Holder)) { + final String msg + = "This functor only supports mapping over instances of IHolder"; + + throw new IllegalArgumentException(msg); + } + + final Holder holder = (Holder) argumentFunctor; + + return holder.map(func); + }; + } + + @Override + public default ContainedType getValue() { + return unwrap(value -> value); + } + + /** + * Lifts a function to bind over this holder. + * + * @param + * The type of the functions return. + * + * @param func + * The function to lift over the holder. + * + * @return The function lifted over the holder. + */ + public Function> + lift(Function func); + + /** + * Make this holder lazy. + * + * @return A lazy version of this holder. + */ + public default Holder makeLazy() { + return new WrappedLazy<>(this); + } + + /** + * Make this holder a list. + * + * @return A list version of this holder. + */ + public default Holder makeList() { + return new BoundListHolder<>(new FunctionalList<>(this)); + } + + /** + * Make this holder optional. + * + * @return An optional version of this holder. + */ + public default Holder makeOptional() { + return new WrappedOption<>(this); + } + + /** + * Create a new holder with a mapped version of the value in this holder. + * + * Does not change the internal state of this holder. + * + * @param + * The type of the mapped value. + * + * @param mapper + * The function to do mapping with. + * + * @return A holder with the mapped value + */ + public Holder + map(Function mapper); + + /** + * Replace the held value with a new one. + * + * @param newValue + * The value to hold instead. + * + * @return The holder itself. + */ + public default Holder replace(final ContainedType newValue) { + return transform(oldValue -> newValue); + } + + /** + * Transform the value held in this holder. + * + * @param transformer + * The function to transform the value with. + * + * @return The holder itself, for easy chaining. + */ + public Holder transform(UnaryOperator transformer); + + /** + * Unwrap the value contained in this holder so that it is no longer held. + * + * @param + * The type of the unwrapped value. + * + * @param unwrapper + * The function to use to unwrap the value. + * + * @return The unwrapped held value. + */ + public UnwrappedType + unwrap(Function unwrapper); + + /** + * Create an instace of IHolder containing a single value. + * + * @param The type of the value contained. + * + * @param contained The value to contain. + * + * @return An instance of IHolder containing that value. + */ + static Holder of(ElementType contained) { + return new Identity<>(contained); + } +} diff --git a/src/main/java/bjc/data/IContext.java b/src/main/java/bjc/data/IContext.java deleted file mode 100644 index e519501..0000000 --- a/src/main/java/bjc/data/IContext.java +++ /dev/null @@ -1,62 +0,0 @@ -package bjc.data; - -/** - * Represents a 'context' which is a hierarchical set of objects. - * @author Ben Culkin - * - */ -public interface IContext { - /** - * Register an object with this context. - * - * @param name The name of the object. - * @param o The object to register. - */ - void register(String name, Object o); - - /** - * Get the parent of this context. - * - * @return The parent of this context. - */ - IContext getParent(); - - /** - * Get an object from this context. - * - * @param name The name of the object. - * - * @return The object bound to that name. - */ - Object get(String name); - - /** - * Get an object which is an instance of the provided class or a subclass - * thereof. - * - * @param The type of the object. - * - * @param contract The class of the object. - * - * @return An instance of the provided class. - */ - T get(Class contract); - - /** - * Get a named object which is an instance of the provided class or a subclass - * thereof. - * - * @param The type of the object. - * - * @param name The name of the object - * @param contract The class of the object. - * - * @return An instance of the provided class, with the given name.. - */ - default T get(String name, Class contract) { - Object obj = get(name); - return obj == null - ? getParent().get(name, contract) - : contract.cast(obj); - }; -} diff --git a/src/main/java/bjc/data/IHolder.java b/src/main/java/bjc/data/IHolder.java deleted file mode 100644 index e0d39aa..0000000 --- a/src/main/java/bjc/data/IHolder.java +++ /dev/null @@ -1,177 +0,0 @@ -package bjc.data; - -import java.util.function.Consumer; -import java.util.function.Function; -import java.util.function.UnaryOperator; - -import bjc.data.internals.BoundListHolder; -import bjc.data.internals.WrappedLazy; -import bjc.data.internals.WrappedOption; -import bjc.funcdata.FunctionalList; -import bjc.funcdata.theory.Functor; - -/** - * A holder of a single value. - * - * @author ben - * - * @param - * The type of value held. - */ -public interface IHolder extends Functor { - /** - * Bind a function across the value in this container. - * - * @param - * The type of value in this container. - * - * @param binder - * The function to bind to the value. - * - * @return A holder from binding the value. - */ - public IHolder - bind(Function> binder); - - /** - * Apply an action to the value. - * - * @param action - * The action to apply to the value. - */ - public default void doWith(final Consumer action) { - transform(value -> { - action.accept(value); - - return value; - }); - } - - @Override - default Function, Functor> - fmap(final Function func) { - return argumentFunctor -> { - if (!(argumentFunctor instanceof IHolder)) { - final String msg - = "This functor only supports mapping over instances of IHolder"; - - throw new IllegalArgumentException(msg); - } - - final IHolder holder = (IHolder) argumentFunctor; - - return holder.map(func); - }; - } - - @Override - public default ContainedType getValue() { - return unwrap(value -> value); - } - - /** - * Lifts a function to bind over this holder. - * - * @param - * The type of the functions return. - * - * @param func - * The function to lift over the holder. - * - * @return The function lifted over the holder. - */ - public Function> - lift(Function func); - - /** - * Make this holder lazy. - * - * @return A lazy version of this holder. - */ - public default IHolder makeLazy() { - return new WrappedLazy<>(this); - } - - /** - * Make this holder a list. - * - * @return A list version of this holder. - */ - public default IHolder makeList() { - return new BoundListHolder<>(new FunctionalList<>(this)); - } - - /** - * Make this holder optional. - * - * @return An optional version of this holder. - */ - public default IHolder makeOptional() { - return new WrappedOption<>(this); - } - - /** - * Create a new holder with a mapped version of the value in this holder. - * - * Does not change the internal state of this holder. - * - * @param - * The type of the mapped value. - * - * @param mapper - * The function to do mapping with. - * - * @return A holder with the mapped value - */ - public IHolder - map(Function mapper); - - /** - * Replace the held value with a new one. - * - * @param newValue - * The value to hold instead. - * - * @return The holder itself. - */ - public default IHolder replace(final ContainedType newValue) { - return transform(oldValue -> newValue); - } - - /** - * Transform the value held in this holder. - * - * @param transformer - * The function to transform the value with. - * - * @return The holder itself, for easy chaining. - */ - public IHolder transform(UnaryOperator transformer); - - /** - * Unwrap the value contained in this holder so that it is no longer held. - * - * @param - * The type of the unwrapped value. - * - * @param unwrapper - * The function to use to unwrap the value. - * - * @return The unwrapped held value. - */ - public UnwrappedType - unwrap(Function unwrapper); - - /** - * Create an instace of IHolder containing a single value. - * - * @param The type of the value contained. - * - * @param contained The value to contain. - * - * @return An instance of IHolder containing that value. - */ - static IHolder of(ElementType contained) { - return new Identity<>(contained); - } -} diff --git a/src/main/java/bjc/data/IPair.java b/src/main/java/bjc/data/IPair.java deleted file mode 100644 index f7d7956..0000000 --- a/src/main/java/bjc/data/IPair.java +++ /dev/null @@ -1,250 +0,0 @@ -package bjc.data; - -import java.util.function.BiConsumer; -import java.util.function.BiFunction; -import java.util.function.Function; - -import bjc.funcdata.theory.Bifunctor; - -/** - * Represents a pair of values. - * - * @author ben - * - * @param - * The type of the left side of the pair. - * - * @param - * The type of the right side of the pair. - * - */ -public interface IPair extends Bifunctor { - /** - * Bind a function across the values in this pair. - * - * @param - * The type of the bound left. - * - * @param - * The type of the bound right. - * - * @param binder - * The function to bind with. - * - * @return The bound pair. - */ - public IPair - bind(BiFunction> binder); - - /** - * Bind a function to the left value in this pair. - * - * @param - * The type of the bound value. - * - * @param leftBinder - * The function to use to bind. - * - * @return A pair with the left type bound. - */ - public IPair - bindLeft(Function> leftBinder); - - /** - * Bind a function to the right value in this pair. - * - * @param - * The type of the bound value. - * - * @param rightBinder - * The function to use to bind. - * - * @return A pair with the right type bound. - */ - public IPair - bindRight(Function> rightBinder); - - /** - * Pairwise combine two pairs together. - * - * @param - * The left type of the other pair. - * - * @param - * The right type of the other pair. - * - * @param otherPair - * The pair to combine with. - * - * @return The pairs, pairwise combined together. - */ - public default - IPair, IPair> - combine(final IPair otherPair) { - return combine(otherPair, - Pair::new, - Pair::new); - } - - /** - * Combine the contents of two pairs together. - * - * @param - * The type of the left value of the other pair. - * - * @param - * The type of the right value of the other pair. - * - * @param - * The type of the left value of the combined pair. - * - * @param - * The type of the right value of the combined pair. - * - * @param otherPair - * The other pair to combine with. - * - * @param leftCombiner - * The function to combine the left values with. - * - * @param rightCombiner - * The function to combine the right values with. - * - * @return A pair with its values combined. - */ - public - IPair - combine(IPair otherPair, - BiFunction leftCombiner, - BiFunction rightCombiner); - - /** - * Immediately perfom the specified action with the contents of this pair. - * - * @param consumer - * The action to perform on the pair. - */ - public default void doWith(final BiConsumer consumer) { - merge((leftValue, rightValue) -> { - consumer.accept(leftValue, rightValue); - - return null; - }); - } - - @Override - default LeftBifunctorMap - fmapLeft(final Function func) { - return argumentPair -> { - if (!(argumentPair instanceof IPair)) { - final String msg - = "This function can only be applied to instances of IPair"; - - throw new IllegalArgumentException(msg); - } - - final IPair argPair - = (IPair) argumentPair; - - return argPair.mapLeft(func); - }; - } - - @Override - default RightBifunctorMap - fmapRight(final Function func) { - return argumentPair -> { - if (!(argumentPair instanceof IPair)) { - final String msg - = "This function can only be applied to instances of IPair"; - - throw new IllegalArgumentException(msg); - } - - final IPair argPair - = (IPair) argumentPair; - - return argPair.mapRight(func); - }; - } - - /** - * Get the value on the left side of the pair. - * - * @return The value on the left side of the pair. - */ - @Override - public default LeftType getLeft() { - return merge((leftValue, rightValue) -> leftValue); - } - - /** - * Get the value on the right side of the pair. - * - * @return The value on the right side of the pair. - */ - @Override - public default RightType getRight() { - return merge((leftValue, rightValue) -> rightValue); - } - - /** - * Transform the value on the left side of the pair. - * - * Doesn't modify the pair. - * - * @param - * The new type of the left part of the pair. - * - * @param mapper - * The function to use to transform the left part of the pair. - * - * @return The pair, with its left part transformed. - */ - public IPair - mapLeft(Function mapper); - - /** - * Transform the value on the right side of the pair. - * - * Doesn't modify the pair. - * - * @param - * The new type of the right part of the pair. - * - * @param mapper - * The function to use to transform the right part of the - * pair. - * - * @return The pair, with its right part transformed. - */ - public IPair - mapRight(Function mapper); - - /** - * Merge the two values in this pair into a single value. - * - * @param - * The type of the single value. - * - * @param merger - * The function to use for merging. - * - * @return The pair, merged into a single value. - */ - public MergedType - merge(BiFunction merger); - - /** - * Static pair constructor. - * - * @param left - * The left side of the pair. - * @param right - * The right side of the pair. - * @return A pair, with the specified left/right side. - */ - public static IPair pair(T1 left, T2 right) { - return new Pair<>(left, right); - } -} diff --git a/src/main/java/bjc/data/ITree.java b/src/main/java/bjc/data/ITree.java deleted file mode 100644 index 7f9c67e..0000000 --- a/src/main/java/bjc/data/ITree.java +++ /dev/null @@ -1,286 +0,0 @@ -package bjc.data; - -import java.util.function.BiFunction; -import java.util.function.Consumer; -import java.util.function.Function; -import java.util.function.Predicate; -import java.util.function.UnaryOperator; - -import bjc.funcdata.IList; -import bjc.funcdata.bst.TreeLinearizationMethod; - -/** - * A node in a homogeneous tree with a unlimited amount of children. - * - * @author ben - * - * @param - * The type of data contained in the tree nodes. - * - */ -public interface ITree { - /** - * Append a child to this node. - * - * @param child - * The child to append to this node. - */ - void addChild(ITree child); - - /** - * Append a child to this node. - * - * @param child - * The child to append to this node. - */ - void addChild(ContainedType child); - - /** - * Prepend a child to this node. - * - * @param child - * The child to prepend to this node. - */ - void prependChild(ITree child); - - /** - * Collapse a tree into a single version. - * - * @param - * The intermediate type being folded. - * - * @param - * The type that is the end result. - * - * @param leafTransform - * The function to use to convert leaf values. - * - * @param nodeCollapser - * The function to use to convert internal nodes and - * their children. - * - * @param resultTransformer - * The function to use to convert a state to the - * returned version. - * - * @return The final transformed state. - */ - ReturnedType collapse( - Function leafTransform, - BiFunction, NewType> nodeCollapser, - Function resultTransformer); - - /** - * Execute a given action for each of this tree's children. - * - * @param action - * The action to execute for each child. - */ - void doForChildren(Consumer> action); - - /** - * Expand the nodes of a tree into trees, and then merge the contents of those - * trees into a single tree. - * - * @param mapper - * The function to use to map values into trees. - * - * @return A tree, with some nodes expanded into trees. - */ - default ITree - flatMapTree(final Function> mapper) { - return topDownTransform(dat -> TopDownTransformResult.PUSHDOWN, node -> { - if (node.getChildrenCount() > 0) { - final ITree parent = node.transformHead(mapper); - - node.doForChildren(parent::addChild); - - return parent; - } - - return node.transformHead(mapper); - }); - } - - /** - * Get the specified child of this tree. - * - * @param childNo - * The number of the child to get. - * - * @return The specified child of this tree. - */ - default ITree getChild(final int childNo) { - return transformChild(childNo, child -> child); - } - - /** - * Get a count of the number of direct children this node has. - * - * @return The number of direct children this node has. - */ - int getChildrenCount(); - - /** - * Get a count of the number of direct children this node has. - * - * @return The number of direct children this node has. - */ - default int size() { - return getChildrenCount(); - } - - /** - * Get the data stored in this node. - * - * @return The data stored in this node. - */ - default ContainedType getHead() { - return transformHead(head -> head); - } - - /** - * Rebuild the tree with the same structure, but different nodes. - * - * @param - * The type of the new tree. - * - * @param leafTransformer - * The function to use to transform leaf tokens. - * - * @param internalTransformer - * The function to use to transform internal tokens. - * - * @return The tree, with the nodes changed. - */ - ITree rebuildTree( - Function leafTransformer, - Function internalTransformer); - - /** - * Transform some of the nodes in this tree. - * - * @param nodePicker - * The predicate to use to pick nodes to transform. - * - * @param transformer - * The function to use to transform picked nodes. - */ - void selectiveTransform(Predicate nodePicker, - UnaryOperator transformer); - - /** - * Do a top-down transform of the tree. - * - * @param transformPicker - * The function to use to pick how to progress. - * - * @param transformer - * The function used to transform picked subtrees. - * - * @return The tree with the transform applied to picked subtrees. - */ - ITree topDownTransform( - Function transformPicker, - UnaryOperator> transformer); - - /** - * Transform one of this nodes children. - * - * @param - * The type of the transformed value. - * - * @param childNo - * The number of the child to transform. - * - * @param transformer - * The function to use to transform the value. - * - * @return The transformed value. - * - * @throws IllegalArgumentException - * if the childNo is out of bounds (0 <= - * childNo <= childCount()). - */ - TransformedType transformChild(int childNo, - Function, TransformedType> transformer); - - /** - * Transform the value that is the head of this node. - * - * @param - * The type of the transformed value. - * - * @param transformer - * The function to use to transform the value. - * - * @return The transformed value. - */ - TransformedType - transformHead(Function transformer); - - /** - * Transform the tree into a tree with a different type of token. - * - * @param - * The type of the new tree. - * - * @param transformer - * The function to use to transform tokens. - * - * @return A tree with the token types transformed. - */ - default ITree - transformTree(final Function transformer) { - return rebuildTree(transformer, transformer); - } - - /** - * Perform an action on each part of the tree. - * - * @param linearizationMethod - * The way to traverse the tree. - * - * @param action - * The action to perform on each tree node. - */ - void traverse(TreeLinearizationMethod linearizationMethod, - Consumer action); - - /** - * Find the farthest to right child that satisfies the given predicate. - * - * @param childPred - * The predicate to satisfy. - * - * @return The index of the right-most child that satisfies the predicate, or -1 - * if one doesn't exist. - */ - int revFind(Predicate> childPred); - - /** - * Check if this tree contains any nodes that satisfy the predicate. - * - * @param pred - * The predicate to look for. - * - * @return Whether or not any items satisfied the predicate. - */ - default boolean containsMatching(Predicate pred) { - Toggle tog = new OneWayToggle<>(false, true); - - traverse(TreeLinearizationMethod.POSTORDER, val -> { - if (pred.test(val)) tog.get(); - }); - - return tog.get(); - } - - /** - * Set the head of the tree. - * - * @param dat - * The value to set as the head of the tree. - */ - void setHead(ContainedType dat); -} diff --git a/src/main/java/bjc/data/Identity.java b/src/main/java/bjc/data/Identity.java index 75b4ecd..e488072 100644 --- a/src/main/java/bjc/data/Identity.java +++ b/src/main/java/bjc/data/Identity.java @@ -11,7 +11,7 @@ import java.util.function.UnaryOperator; * @param * The type contained in the holder. */ -public class Identity implements IHolder { +public class Identity implements Holder { /* The held value. */ private ContainedType heldValue; @@ -31,8 +31,8 @@ public class Identity implements IHolder { } @Override - public IHolder - bind(final Function> binder) { + public Holder + bind(final Function> binder) { return binder.apply(heldValue); } @@ -64,7 +64,7 @@ public class Identity implements IHolder { } @Override - public Function> + public Function> lift(final Function func) { return val -> { return new Identity<>(func.apply(val)); @@ -72,7 +72,7 @@ public class Identity implements IHolder { } @Override - public IHolder + public Holder map(final Function mapper) { return new Identity<>(mapper.apply(heldValue)); } @@ -83,7 +83,7 @@ public class Identity implements IHolder { } @Override - public IHolder + public Holder transform(final UnaryOperator transformer) { heldValue = transformer.apply(heldValue); diff --git a/src/main/java/bjc/data/Lazy.java b/src/main/java/bjc/data/Lazy.java index 8573325..5fcd2ae 100644 --- a/src/main/java/bjc/data/Lazy.java +++ b/src/main/java/bjc/data/Lazy.java @@ -6,7 +6,7 @@ import java.util.function.UnaryOperator; import bjc.data.internals.BoundLazy; import bjc.funcdata.FunctionalList; -import bjc.funcdata.IList; +import bjc.funcdata.ListEx; /** * A holder that holds a means to create a value, but doesn't actually compute @@ -17,7 +17,7 @@ import bjc.funcdata.IList; * @param * The type of the value being held. */ -public class Lazy implements IHolder { +public class Lazy implements Holder { /* The supplier of the type. */ private Supplier valueSupplier; /* The actual type value. */ @@ -26,7 +26,7 @@ public class Lazy implements IHolder { private boolean valueMaterialized; /* The list of pending actions on the value. */ - private IList> actions = new FunctionalList<>(); + private ListEx> actions = new FunctionalList<>(); /** * Create a new lazy value from the specified seed value. @@ -54,16 +54,16 @@ public class Lazy implements IHolder { /* Create a new value from a supplier and a list of actions. */ private Lazy(final Supplier supp, - final IList> pendingActions) { + final ListEx> pendingActions) { valueSupplier = supp; actions = pendingActions; } @Override - public IHolder - bind(final Function> binder) { - final IList> pendingActions = new FunctionalList<>(); + public Holder + bind(final Function> binder) { + final ListEx> pendingActions = new FunctionalList<>(); for (UnaryOperator action : actions) { pendingActions.add(action); @@ -79,15 +79,15 @@ public class Lazy implements IHolder { } @Override - public Function> + public Function> lift(final Function func) { return val -> new Lazy<>(func.apply(val)); } @Override - public IHolder + public Holder map(final Function mapper) { - final IList> pendingActions = new FunctionalList<>(); + final ListEx> pendingActions = new FunctionalList<>(); for (UnaryOperator action : actions) { pendingActions.add(action); @@ -126,7 +126,7 @@ public class Lazy implements IHolder { } @Override - public IHolder + public Holder transform(final UnaryOperator transformer) { actions.add(transformer); diff --git a/src/main/java/bjc/data/LazyPair.java b/src/main/java/bjc/data/LazyPair.java index 2481cd7..048254a 100644 --- a/src/main/java/bjc/data/LazyPair.java +++ b/src/main/java/bjc/data/LazyPair.java @@ -18,7 +18,7 @@ import bjc.data.internals.HalfBoundLazyPair; * @param * The type on the right side of the pair. */ -public class LazyPair implements IPair { +public class LazyPair implements Pair { /* The supplier for the left value. */ private Supplier leftSupplier; /* The left value. */ @@ -70,14 +70,14 @@ public class LazyPair implements IPair } @Override - public IPair bind( - final BiFunction> binder) { + public Pair bind( + final BiFunction> binder) { return new BoundLazyPair<>(leftSupplier, rightSupplier, binder); } @Override - public IPair - bindLeft(final Function> leftBinder) { + public Pair + bindLeft(final Function> leftBinder) { final Supplier leftSupp = () -> { if (leftMaterialized) return leftValue; @@ -88,8 +88,8 @@ public class LazyPair implements IPair } @Override - public IPair bindRight( - final Function> rightBinder) { + public Pair bindRight( + final Function> rightBinder) { final Supplier rightSupp = () -> { if (rightMaterialized) return rightValue; @@ -101,8 +101,8 @@ public class LazyPair implements IPair @Override public - IPair - combine(final IPair otherPair, + Pair + combine(final Pair otherPair, final BiFunction leftCombiner, final BiFunction rightCombiner) { @@ -139,7 +139,7 @@ public class LazyPair implements IPair } @Override - public IPair + public Pair mapLeft(final Function mapper) { final Supplier leftSupp = () -> { if (leftMaterialized) return mapper.apply(leftValue); @@ -157,7 +157,7 @@ public class LazyPair implements IPair } @Override - public IPair + public Pair mapRight(final Function mapper) { final Supplier leftSupp = () -> { if (leftMaterialized) return leftValue; diff --git a/src/main/java/bjc/data/ListHolder.java b/src/main/java/bjc/data/ListHolder.java index 79c900d..c8a75ff 100644 --- a/src/main/java/bjc/data/ListHolder.java +++ b/src/main/java/bjc/data/ListHolder.java @@ -5,7 +5,7 @@ import java.util.function.UnaryOperator; import bjc.data.internals.BoundListHolder; import bjc.funcdata.FunctionalList; -import bjc.funcdata.IList; +import bjc.funcdata.ListEx; /** * A holder that represents a set of non-deterministic computations. @@ -15,8 +15,8 @@ import bjc.funcdata.IList; * @param * The type of contained value. */ -public class ListHolder implements IHolder { - private IList heldValues; +public class ListHolder implements Holder { + private ListEx heldValues; /** * Create a new list holder. @@ -36,34 +36,34 @@ public class ListHolder implements IHolder { } /* Create a new holder with values. */ - private ListHolder(final IList toHold) { + private ListHolder(final ListEx toHold) { heldValues = toHold; } @Override - public IHolder - bind(final Function> binder) { - final IList> boundValues = heldValues.map(binder); + public Holder + bind(final Function> binder) { + final ListEx> boundValues = heldValues.map(binder); return new BoundListHolder<>(boundValues); } @Override - public Function> + public Function> lift(final Function func) { return val -> new ListHolder<>(new FunctionalList<>(func.apply(val))); } @Override - public IHolder + public Holder map(final Function mapper) { - final IList mappedValues = heldValues.map(mapper); + final ListEx mappedValues = heldValues.map(mapper); return new ListHolder<>(mappedValues); } @Override - public IHolder + public Holder transform(final UnaryOperator transformer) { heldValues = heldValues.map(transformer); diff --git a/src/main/java/bjc/data/Option.java b/src/main/java/bjc/data/Option.java index 84e71a2..6c76d59 100644 --- a/src/main/java/bjc/data/Option.java +++ b/src/main/java/bjc/data/Option.java @@ -11,7 +11,7 @@ import java.util.function.UnaryOperator; * @param * The type of the value that may or may not be held. */ -public class Option implements IHolder { +public class Option implements Holder { private ContainedType held; /** @@ -25,21 +25,21 @@ public class Option implements IHolder { } @Override - public IHolder - bind(final Function> binder) { + public Holder + bind(final Function> binder) { if (held == null) return new Option<>(null); return binder.apply(held); } @Override - public Function> + public Function> lift(final Function func) { return val -> new Option<>(func.apply(val)); } @Override - public IHolder + public Holder map(final Function mapper) { if (held == null) return new Option<>(null); @@ -47,7 +47,7 @@ public class Option implements IHolder { } @Override - public IHolder + public Holder transform(final UnaryOperator transformer) { if (held != null) held = transformer.apply(held); diff --git a/src/main/java/bjc/data/Pair.java b/src/main/java/bjc/data/Pair.java index ea2f82f..42a28f8 100644 --- a/src/main/java/bjc/data/Pair.java +++ b/src/main/java/bjc/data/Pair.java @@ -1,154 +1,250 @@ package bjc.data; +import java.util.function.BiConsumer; import java.util.function.BiFunction; import java.util.function.Function; +import bjc.funcdata.theory.Bifunctor; + /** - * A pair of values, with nothing special about them. + * Represents a pair of values. * * @author ben * * @param - * The type of the left value. + * The type of the left side of the pair. * * @param - * The type of the right value. + * The type of the right side of the pair. + * */ -public class Pair implements IPair { - /* The left value. */ - private LeftType leftValue; - /* The right value. */ - private RightType rightValue; - - /** Create a new pair with both sides set to null. */ - public Pair() { - // Do nothing :) - } - +public interface Pair extends Bifunctor { /** - * Create a new pair with both sides set to the specified values. + * Bind a function across the values in this pair. * - * @param left - * The value of the left side. + * @param + * The type of the bound left. * - * @param right - * The value of the right side. + * @param + * The type of the bound right. + * + * @param binder + * The function to bind with. + * + * @return The bound pair. */ - public Pair(final LeftType left, final RightType right) { - leftValue = left; - rightValue = right; - } - - @Override - public IPair bind( - final BiFunction> binder) { - if (binder == null) throw new NullPointerException("Binder must not be null."); + public Pair + bind(BiFunction> binder); - return binder.apply(leftValue, rightValue); - } + /** + * Bind a function to the left value in this pair. + * + * @param + * The type of the bound value. + * + * @param leftBinder + * The function to use to bind. + * + * @return A pair with the left type bound. + */ + public Pair + bindLeft(Function> leftBinder); - @Override - public IPair - bindLeft(final Function> leftBinder) { - if (leftBinder == null) throw new NullPointerException("Binder must not be null"); + /** + * Bind a function to the right value in this pair. + * + * @param + * The type of the bound value. + * + * @param rightBinder + * The function to use to bind. + * + * @return A pair with the right type bound. + */ + public Pair + bindRight(Function> rightBinder); - return leftBinder.apply(leftValue); + /** + * Pairwise combine two pairs together. + * + * @param + * The left type of the other pair. + * + * @param + * The right type of the other pair. + * + * @param otherPair + * The pair to combine with. + * + * @return The pairs, pairwise combined together. + */ + public default + Pair, Pair> + combine(final Pair otherPair) { + return combine(otherPair, + SimplePair::new, + SimplePair::new); } - @Override - public IPair bindRight( - final Function> rightBinder) { - if (rightBinder == null) throw new NullPointerException("Binder must not be null"); + /** + * Combine the contents of two pairs together. + * + * @param + * The type of the left value of the other pair. + * + * @param + * The type of the right value of the other pair. + * + * @param + * The type of the left value of the combined pair. + * + * @param + * The type of the right value of the combined pair. + * + * @param otherPair + * The other pair to combine with. + * + * @param leftCombiner + * The function to combine the left values with. + * + * @param rightCombiner + * The function to combine the right values with. + * + * @return A pair with its values combined. + */ + public + Pair + combine(Pair otherPair, + BiFunction leftCombiner, + BiFunction rightCombiner); - return rightBinder.apply(rightValue); - } + /** + * Immediately perfom the specified action with the contents of this pair. + * + * @param consumer + * The action to perform on the pair. + */ + public default void doWith(final BiConsumer consumer) { + merge((leftValue, rightValue) -> { + consumer.accept(leftValue, rightValue); - @Override - public - IPair - combine(final IPair otherPair, - final BiFunction leftCombiner, - final BiFunction rightCombiner) { - return otherPair.bind((otherLeft, otherRight) -> { - final CombinedLeft left = leftCombiner.apply(leftValue, otherLeft); - final CombinedRight right = rightCombiner.apply(rightValue, otherRight); - - return new Pair<>(left, right); + return null; }); } @Override - public IPair - mapLeft(final Function mapper) { - if (mapper == null) throw new NullPointerException("Mapper must not be null"); + default LeftBifunctorMap + fmapLeft(final Function func) { + return argumentPair -> { + if (!(argumentPair instanceof Pair)) { + final String msg + = "This function can only be applied to instances of IPair"; - return new Pair<>(mapper.apply(leftValue), rightValue); - } + throw new IllegalArgumentException(msg); + } - @Override - public IPair - mapRight(final Function mapper) { - if (mapper == null) throw new NullPointerException("Mapper must not be null"); + final Pair argPair + = (Pair) argumentPair; - return new Pair<>(leftValue, mapper.apply(rightValue)); + return argPair.mapLeft(func); + }; } @Override - public MergedType - merge(final BiFunction merger) { - if (merger == null) throw new NullPointerException("Merger must not be null"); + default RightBifunctorMap + fmapRight(final Function func) { + return argumentPair -> { + if (!(argumentPair instanceof Pair)) { + final String msg + = "This function can only be applied to instances of IPair"; - return merger.apply(leftValue, rightValue); - } + throw new IllegalArgumentException(msg); + } - @Override - public String toString() { - return String.format("Pair [leftValue='%s', rightValue='%s']", leftValue, - rightValue); + final Pair argPair + = (Pair) argumentPair; + + return argPair.mapRight(func); + }; } + /** + * Get the value on the left side of the pair. + * + * @return The value on the left side of the pair. + */ @Override - public LeftType getLeft() { - return leftValue; + public default LeftType getLeft() { + return merge((leftValue, rightValue) -> leftValue); } + /** + * Get the value on the right side of the pair. + * + * @return The value on the right side of the pair. + */ @Override - public RightType getRight() { - return rightValue; + public default RightType getRight() { + return merge((leftValue, rightValue) -> rightValue); } - @Override - public int hashCode() { - final int prime = 31; - int result = 1; + /** + * Transform the value on the left side of the pair. + * + * Doesn't modify the pair. + * + * @param + * The new type of the left part of the pair. + * + * @param mapper + * The function to use to transform the left part of the pair. + * + * @return The pair, with its left part transformed. + */ + public Pair + mapLeft(Function mapper); - result = prime * result + (leftValue == null ? 0 : leftValue.hashCode()); - result = prime * result + (rightValue == null ? 0 : rightValue.hashCode()); + /** + * Transform the value on the right side of the pair. + * + * Doesn't modify the pair. + * + * @param + * The new type of the right part of the pair. + * + * @param mapper + * The function to use to transform the right part of the + * pair. + * + * @return The pair, with its right part transformed. + */ + public Pair + mapRight(Function mapper); - return result; - } + /** + * Merge the two values in this pair into a single value. + * + * @param + * The type of the single value. + * + * @param merger + * The function to use for merging. + * + * @return The pair, merged into a single value. + */ + public MergedType + merge(BiFunction merger); - @Override - public boolean equals(final Object obj) { - if (this == obj) return true; - if (obj == null) return false; - if (!(obj instanceof Pair)) return false; - - final Pair other = (Pair) obj; - - if (leftValue == null) { - if (other.leftValue != null) return false; - } else if (!leftValue.equals(other.leftValue)) { - return false; - } - - if (rightValue == null) { - if (other.rightValue != null) return false; - } else if (!rightValue.equals(other.rightValue)) { - return false; - } - - return true; + /** + * Static pair constructor. + * + * @param left + * The left side of the pair. + * @param right + * The right side of the pair. + * @return A pair, with the specified left/right side. + */ + public static Pair pair(T1 left, T2 right) { + return new SimplePair<>(left, right); } } diff --git a/src/main/java/bjc/data/SimplePair.java b/src/main/java/bjc/data/SimplePair.java new file mode 100644 index 0000000..48f5ca3 --- /dev/null +++ b/src/main/java/bjc/data/SimplePair.java @@ -0,0 +1,154 @@ +package bjc.data; + +import java.util.function.BiFunction; +import java.util.function.Function; + +/** + * A pair of values, with nothing special about them. + * + * @author ben + * + * @param + * The type of the left value. + * + * @param + * The type of the right value. + */ +public class SimplePair implements Pair { + /* The left value. */ + private LeftType leftValue; + /* The right value. */ + private RightType rightValue; + + /** Create a new pair with both sides set to null. */ + public SimplePair() { + // Do nothing :) + } + + /** + * Create a new pair with both sides set to the specified values. + * + * @param left + * The value of the left side. + * + * @param right + * The value of the right side. + */ + public SimplePair(final LeftType left, final RightType right) { + leftValue = left; + rightValue = right; + } + + @Override + public Pair bind( + final BiFunction> binder) { + if (binder == null) throw new NullPointerException("Binder must not be null."); + + return binder.apply(leftValue, rightValue); + } + + @Override + public Pair + bindLeft(final Function> leftBinder) { + if (leftBinder == null) throw new NullPointerException("Binder must not be null"); + + return leftBinder.apply(leftValue); + } + + @Override + public Pair bindRight( + final Function> rightBinder) { + if (rightBinder == null) throw new NullPointerException("Binder must not be null"); + + return rightBinder.apply(rightValue); + } + + @Override + public + Pair + combine(final Pair otherPair, + final BiFunction leftCombiner, + final BiFunction rightCombiner) { + return otherPair.bind((otherLeft, otherRight) -> { + final CombinedLeft left = leftCombiner.apply(leftValue, otherLeft); + final CombinedRight right = rightCombiner.apply(rightValue, otherRight); + + return new SimplePair<>(left, right); + }); + } + + @Override + public Pair + mapLeft(final Function mapper) { + if (mapper == null) throw new NullPointerException("Mapper must not be null"); + + return new SimplePair<>(mapper.apply(leftValue), rightValue); + } + + @Override + public Pair + mapRight(final Function mapper) { + if (mapper == null) throw new NullPointerException("Mapper must not be null"); + + return new SimplePair<>(leftValue, mapper.apply(rightValue)); + } + + @Override + public MergedType + merge(final BiFunction merger) { + if (merger == null) throw new NullPointerException("Merger must not be null"); + + return merger.apply(leftValue, rightValue); + } + + @Override + public String toString() { + return String.format("Pair [leftValue='%s', rightValue='%s']", leftValue, + rightValue); + } + + @Override + public LeftType getLeft() { + return leftValue; + } + + @Override + public RightType getRight() { + return rightValue; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + + result = prime * result + (leftValue == null ? 0 : leftValue.hashCode()); + result = prime * result + (rightValue == null ? 0 : rightValue.hashCode()); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if (this == obj) return true; + if (obj == null) return false; + if (!(obj instanceof SimplePair)) return false; + + final SimplePair other = (SimplePair) obj; + + if (leftValue == null) { + if (other.leftValue != null) return false; + } else if (!leftValue.equals(other.leftValue)) { + return false; + } + + if (rightValue == null) { + if (other.rightValue != null) return false; + } else if (!rightValue.equals(other.rightValue)) { + return false; + } + + return true; + } +} diff --git a/src/main/java/bjc/data/SimpleTree.java b/src/main/java/bjc/data/SimpleTree.java new file mode 100644 index 0000000..7d9fb6d --- /dev/null +++ b/src/main/java/bjc/data/SimpleTree.java @@ -0,0 +1,446 @@ +package bjc.data; + +import java.util.function.BiFunction; +import java.util.function.Consumer; +import java.util.function.Function; +import java.util.function.Predicate; +import java.util.function.UnaryOperator; + +import bjc.funcdata.FunctionalList; +import bjc.funcdata.ListEx; +import bjc.funcdata.bst.TreeLinearizationMethod; + +/** + * A node in a homogeneous tree. + * + * @author ben + * + * @param + * The type contained in the tree. + */ +public class SimpleTree implements Tree { + /* The data/label for this node. */ + private ContainedType data; + + /* The children of this node. */ + private ListEx> children; + + /* Whether this node has children. */ + /* + * @NOTE Why have both this boolean and childCount? Why not just do a childCount + * == 0 whenever you'd check hasChildren? + * + * - Because hasChildren is set once and not reset, and really what it + * indicates is that children has been allocated. + */ + private boolean hasChildren; + /* The number of children this node has. */ + private int childCount = 0; + + /* The ID of this node. */ + private int ID; + /* The next ID to assign to a node. */ + private static int nextID = 0; + + /** + * Create a new leaf node in a tree. + */ + public SimpleTree() { + this(null); + } + + /** + * Create a new leaf node in a tree. + * + * @param leaf + * The data to store as a leaf node. + */ + public SimpleTree(final ContainedType leaf) { + data = leaf; + + hasChildren = false; + + ID = nextID++; + } + + /** + * Create a new tree node with the specified children. + * + * @param leaf + * The data to hold in this node. + * + * @param childrn + * A list of children for this node. + */ + public SimpleTree(final ContainedType leaf, final ListEx> childrn) { + this(leaf); + + hasChildren = true; + + childCount = childrn.getSize(); + + children = childrn; + } + + /** + * Create a new tree node with the specified children. + * + * @param leaf + * The data to hold in this node. + * + * @param childrn + * A list of children for this node. + */ + @SafeVarargs + public SimpleTree(final ContainedType leaf, final Tree... childrn) { + this(leaf); + + hasChildren = true; + + childCount = 0; + + children = new FunctionalList<>(); + + for (final Tree child : childrn) { + children.add(child); + + childCount++; + } + } + + @Override + public void addChild(final ContainedType child) { + addChild(new SimpleTree<>(child)); + } + + @Override + public void addChild(final Tree child) { + if (hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.add(child); + } + + @Override + public void prependChild(final Tree child) { + if (hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.prepend(child); + } + + @Override + public void doForChildren(final Consumer> action) { + if (childCount > 0) children.forEach(action); + } + + @Override + public int getChildrenCount() { + return childCount; + } + + @Override + public int revFind(final Predicate> childPred) { + if (childCount == 0) return -1; + + for (int i = childCount - 1; i >= 0; i--) { + if (childPred.test(getChild(i))) return i; + } + + return -1; + } + + @Override + public void traverse(final TreeLinearizationMethod linearizationMethod, + final Consumer action) { + if (hasChildren) { + switch (linearizationMethod) { + case INORDER: + if (childCount != 2) { + final String msg = "Can only do in-order traversal for binary trees."; + + throw new IllegalArgumentException(msg); + } + + children.getByIndex(0).traverse(linearizationMethod, action); + + action.accept(data); + + children.getByIndex(1).traverse(linearizationMethod, action); + break; + case POSTORDER: + children.forEach(child -> child.traverse(linearizationMethod, action)); + + action.accept(data); + break; + case PREORDER: + action.accept(data); + + children.forEach(child -> child.traverse(linearizationMethod, action)); + break; + default: + break; + + } + } else { + action.accept(data); + } + } + + @Override + public ReturnedType collapse( + final Function leafTransform, + final BiFunction, NewType> nodeCollapser, + final Function resultTransformer) { + return resultTransformer.apply(internalCollapse(leafTransform, nodeCollapser)); + } + + @Override + public Tree + flatMapTree(final Function> mapper) { + if (hasChildren) { + final Tree flatMappedData = mapper.apply(data); + + final ListEx> mappedChildren + = children.map(child -> child.flatMapTree(mapper)); + + mappedChildren.forEach(flatMappedData::addChild); + + return flatMappedData; + } + + return mapper.apply(data); + } + + /* + * Do a collapse of this tree. + */ + + private NewType internalCollapse( + final Function leafTransform, + final BiFunction, NewType> nodeCollapser) { + if (hasChildren) { + final ListEx collapsedChildren = children.map(child -> { + final NewType collapsed = child.collapse(leafTransform, nodeCollapser, + subTreeVal -> subTreeVal); + + return collapsed; + }); + + return nodeCollapser.apply(data, collapsedChildren); + } + + return leafTransform.apply(data); + } + + private void internalToString(final StringBuilder builder, final int indentLevel, + final boolean initial) { + if (!initial) { + for (int i = 0; i < indentLevel; i++) builder.append(">\t"); + } + + builder.append("Node #"); + builder.append(ID); + builder.append(": "); + builder.append(data == null ? "(null)" : data.toString()); + builder.append("\n"); + + if (hasChildren) { + children.forEach(child -> { + if (child instanceof SimpleTree) { + final SimpleTree kid = (SimpleTree) child; + + kid.internalToString(builder, indentLevel + 1, false); + } else { + for (int i = 0; i < indentLevel + 1; i++) { + builder.append(">\t"); + } + + builder.append("Unknown node of type "); + builder.append(child.getClass().getName()); + builder.append("\n"); + } + }); + } + } + + @Override + public Tree rebuildTree( + final Function leafTransformer, + final Function operatorTransformer) { + if (hasChildren) { + final ListEx> mappedChildren = + children.map(child -> + child.rebuildTree(leafTransformer, operatorTransformer)); + + final MappedType mapData = operatorTransformer.apply(data); + return new SimpleTree<>(mapData, mappedChildren); + } + + return new SimpleTree<>(leafTransformer.apply(data)); + } + + @Override + public void selectiveTransform(final Predicate nodePicker, + final UnaryOperator transformer) { + if (hasChildren) { + children.forEach(child -> child.selectiveTransform(nodePicker, transformer)); + } else { + data = transformer.apply(data); + } + } + + @Override + public Tree topDownTransform( + final Function transformPicker, + final UnaryOperator> transformer) { + final TopDownTransformResult transformResult = transformPicker.apply(data); + + switch (transformResult) { + case PASSTHROUGH: + Tree result = new SimpleTree<>(data); + + if (hasChildren) { + children.forEach(child -> { + final Tree kid + = child.topDownTransform(transformPicker, transformer); + + result.addChild(kid); + }); + } + + return result; + case SKIP: + return this; + case TRANSFORM: + return transformer.apply(this); + case RTRANSFORM: + return transformer.apply(this).topDownTransform(transformPicker, transformer); + case PUSHDOWN: + result = new SimpleTree<>(data); + + if (hasChildren) { + children.forEach(child -> { + final Tree kid + = child.topDownTransform(transformPicker, transformer); + + result.addChild(kid); + }); + } + + return transformer.apply(result); + case PULLUP: + final Tree intermediateResult = transformer.apply(this); + + result = new SimpleTree<>(intermediateResult.getHead()); + + intermediateResult.doForChildren(child -> { + final Tree kid + = child.topDownTransform(transformPicker, transformer); + + result.addChild(kid); + }); + + return result; + default: + final String msg = String.format("Recieved unknown transform result type %s", + transformResult); + + throw new IllegalArgumentException(msg); + } + } + + @Override + public TransformedType transformChild(final int childNo, + final Function, TransformedType> transformer) { + if (childNo < 0 || childNo > childCount - 1) { + final String msg = String.format("Child index #%d is invalid", childNo); + + throw new IllegalArgumentException(msg); + } + + final Tree selectedKid = children.getByIndex(childNo); + + return transformer.apply(selectedKid); + } + + @Override + public Tree getChild(final int childNo) { + if (childNo < 0 || childNo > childCount - 1) { + final String msg = String.format("Child index #%d is invalid", childNo); + + throw new IllegalArgumentException(msg); + } + return children.getByIndex(childNo); + } + + @Override + public TransformedType + transformHead(final Function transformer) { + return transformer.apply(data); + } + + @Override + public void setHead(ContainedType dat) { + this.data = dat; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + + result = prime * result + childCount; + result = prime * result + (children == null ? 0 : children.hashCode()); + result = prime * result + (data == null ? 0 : data.hashCode()); + + return result; + } + + @Override + public String toString() { + final StringBuilder builder = new StringBuilder(); + + internalToString(builder, 1, true); + + /* Delete a trailing nl. */ + builder.deleteCharAt(builder.length() - 1); + + return builder.toString(); + } + + @Override + public boolean equals(final Object obj) { + if (this == obj) return true; + if (obj == null) return false; + if (!(obj instanceof SimpleTree)) return false; + + final SimpleTree other = (SimpleTree) obj; + + if (data == null) { + if (other.data != null) return false; + } else if (!data.equals(other.data)) { + return false; + } + + if (childCount != other.childCount) return false; + + if (children == null) { + if (other.children != null) return false; + } else if (!children.equals(other.children)) { + return false; + } + + return true; + } +} diff --git a/src/main/java/bjc/data/TopDownTransformIterator.java b/src/main/java/bjc/data/TopDownTransformIterator.java index cf211d3..28df590 100644 --- a/src/main/java/bjc/data/TopDownTransformIterator.java +++ b/src/main/java/bjc/data/TopDownTransformIterator.java @@ -26,7 +26,7 @@ import java.util.function.Function; * The type of the nodes in the tree. */ public class TopDownTransformIterator - implements Iterator> { + implements Iterator> { /** * Alias type for a tree transformation. * @@ -35,8 +35,8 @@ public class TopDownTransformIterator * @param * The type contained in the tree. */ - public interface TreeTransform extends BiFunction, - Consumer>>, ITree> { + public interface TreeTransform extends BiFunction, + Consumer>>, Tree> { // Alias type; no body is needed } @@ -49,19 +49,19 @@ public class TopDownTransformIterator */ private final TreeTransform transform; - private ITree preParent; - private ITree postParent; + private Tree preParent; + private Tree postParent; - private final Deque> preChildren; - private final Deque> postChildren; + private final Deque> preChildren; + private final Deque> postChildren; private TopDownTransformIterator curChild; private boolean done; private boolean initial; - private final Deque>> toYield; - private Iterator> currYield; + private final Deque>> toYield; + private Iterator> currYield; /** * Create a new tree iterator. @@ -76,7 +76,7 @@ public class TopDownTransformIterator public TopDownTransformIterator( final Function pickr, final TreeTransform transfrm, - final ITree tree) { + final Tree tree) { preParent = tree; preChildren = new LinkedList<>(); @@ -96,7 +96,7 @@ public class TopDownTransformIterator * @param src * The nodes to yield. */ - public void addYield(final Iterator> src) { + public void addYield(final Iterator> src) { if (currYield != null) toYield.push(currYield); currYield = src; @@ -115,7 +115,7 @@ public class TopDownTransformIterator * * @return The next yielded value. */ - public ITree flushYields(final ITree val) { + public Tree flushYields(final Tree val) { if (currYield != null) { /* * We have non-sentinel values to yield. @@ -144,14 +144,14 @@ public class TopDownTransformIterator } @Override - public ITree next() { + public Tree next() { if (done) throw new NoSuchElementException(); /* * Flush any values that need to be yielded. */ if (currYield != null) { - ITree yeld = flushYields(null); + Tree yeld = flushYields(null); if (yeld != null) return yeld; } @@ -164,7 +164,7 @@ public class TopDownTransformIterator switch (res) { case PASSTHROUGH: - postParent = new Tree<>(preParent.getHead()); + postParent = new SimpleTree<>(preParent.getHead()); if (preParent.getChildrenCount() != 0) { for (int i = 0; i < preParent.getChildrenCount(); i++) { @@ -198,12 +198,12 @@ public class TopDownTransformIterator done = true; return flushYields( - transform.apply(new Tree<>(preParent.getHead()), this::addYield)); + transform.apply(new SimpleTree<>(preParent.getHead()), this::addYield)); case PULLUP: - final ITree intRes + final Tree intRes = transform.apply(preParent, this::addYield); - postParent = new Tree<>(intRes.getHead()); + postParent = new SimpleTree<>(intRes.getHead()); if (intRes.getChildrenCount() != 0) { for (int i = 0; i < intRes.getChildrenCount(); i++) { @@ -228,22 +228,22 @@ public class TopDownTransformIterator curChild = new TopDownTransformIterator<>(picker, transform, preChildren.pop()); - final ITree res = curChild.next(); + final Tree res = curChild.next(); // System.out.println("\t\tTRACE: adding node " + res + " to children"); postChildren.add(res); return flushYields(res); } - ITree res = null; + Tree res = null; if (postParent == null) { - res = new Tree<>(preParent.getHead()); + res = new SimpleTree<>(preParent.getHead()); // System.out.println("\t\tTRACE: adding nodes " + postChildren + " to " + // res); - for (final ITree child : postChildren) { + for (final Tree child : postChildren) { res.addChild(child); } @@ -254,7 +254,7 @@ public class TopDownTransformIterator // System.out.println("\t\tTRACE: adding nodes " + postChildren + " to " + // res); - for (final ITree child : postChildren) { + for (final Tree child : postChildren) { res.addChild(child); } } @@ -263,7 +263,7 @@ public class TopDownTransformIterator return flushYields(res); } - final ITree res = curChild.next(); + final Tree res = curChild.next(); // System.out.println("\t\tTRACE: adding node " + res + " to children"); postChildren.add(res); diff --git a/src/main/java/bjc/data/Tree.java b/src/main/java/bjc/data/Tree.java index d0cfe3d..3e16e02 100644 --- a/src/main/java/bjc/data/Tree.java +++ b/src/main/java/bjc/data/Tree.java @@ -6,441 +6,281 @@ import java.util.function.Function; import java.util.function.Predicate; import java.util.function.UnaryOperator; -import bjc.funcdata.FunctionalList; -import bjc.funcdata.IList; +import bjc.funcdata.ListEx; import bjc.funcdata.bst.TreeLinearizationMethod; /** - * A node in a homogeneous tree. + * A node in a homogeneous tree with a unlimited amount of children. * * @author ben * * @param - * The type contained in the tree. + * The type of data contained in the tree nodes. + * */ -public class Tree implements ITree { - /* The data/label for this node. */ - private ContainedType data; - - /* The children of this node. */ - private IList> children; - - /* Whether this node has children. */ - /* - * @NOTE Why have both this boolean and childCount? Why not just do a childCount - * == 0 whenever you'd check hasChildren? - * - * - Because hasChildren is set once and not reset, and really what it - * indicates is that children has been allocated. +public interface Tree { + /** + * Append a child to this node. + * + * @param child + * The child to append to this node. */ - private boolean hasChildren; - /* The number of children this node has. */ - private int childCount = 0; - - /* The ID of this node. */ - private int ID; - /* The next ID to assign to a node. */ - private static int nextID = 0; + void addChild(Tree child); /** - * Create a new leaf node in a tree. + * Append a child to this node. + * + * @param child + * The child to append to this node. */ - public Tree() { - this(null); - } + void addChild(ContainedType child); /** - * Create a new leaf node in a tree. + * Prepend a child to this node. * - * @param leaf - * The data to store as a leaf node. + * @param child + * The child to prepend to this node. */ - public Tree(final ContainedType leaf) { - data = leaf; - - hasChildren = false; - - ID = nextID++; - } + void prependChild(Tree child); /** - * Create a new tree node with the specified children. + * Collapse a tree into a single version. + * + * @param + * The intermediate type being folded. + * + * @param + * The type that is the end result. + * + * @param leafTransform + * The function to use to convert leaf values. + * + * @param nodeCollapser + * The function to use to convert internal nodes and + * their children. * - * @param leaf - * The data to hold in this node. + * @param resultTransformer + * The function to use to convert a state to the + * returned version. * - * @param childrn - * A list of children for this node. + * @return The final transformed state. */ - public Tree(final ContainedType leaf, final IList> childrn) { - this(leaf); + ReturnedType collapse( + Function leafTransform, + BiFunction, NewType> nodeCollapser, + Function resultTransformer); - hasChildren = true; - - childCount = childrn.getSize(); - - children = childrn; - } + /** + * Execute a given action for each of this tree's children. + * + * @param action + * The action to execute for each child. + */ + void doForChildren(Consumer> action); /** - * Create a new tree node with the specified children. + * Expand the nodes of a tree into trees, and then merge the contents of those + * trees into a single tree. * - * @param leaf - * The data to hold in this node. + * @param mapper + * The function to use to map values into trees. * - * @param childrn - * A list of children for this node. + * @return A tree, with some nodes expanded into trees. */ - @SafeVarargs - public Tree(final ContainedType leaf, final ITree... childrn) { - this(leaf); - - hasChildren = true; - - childCount = 0; - - children = new FunctionalList<>(); - - for (final ITree child : childrn) { - children.add(child); - - childCount++; - } - } - - @Override - public void addChild(final ContainedType child) { - addChild(new Tree<>(child)); - } - - @Override - public void addChild(final ITree child) { - if (hasChildren == false) { - hasChildren = true; - - children = new FunctionalList<>(); - } - - childCount++; - - children.add(child); - } - - @Override - public void prependChild(final ITree child) { - if (hasChildren == false) { - hasChildren = true; - - children = new FunctionalList<>(); - } - - childCount++; - - children.prepend(child); - } - - @Override - public void doForChildren(final Consumer> action) { - if (childCount > 0) children.forEach(action); - } - - @Override - public int getChildrenCount() { - return childCount; - } - - @Override - public int revFind(final Predicate> childPred) { - if (childCount == 0) return -1; - - for (int i = childCount - 1; i >= 0; i--) { - if (childPred.test(getChild(i))) return i; - } - - return -1; - } - - @Override - public void traverse(final TreeLinearizationMethod linearizationMethod, - final Consumer action) { - if (hasChildren) { - switch (linearizationMethod) { - case INORDER: - if (childCount != 2) { - final String msg = "Can only do in-order traversal for binary trees."; - - throw new IllegalArgumentException(msg); - } - - children.getByIndex(0).traverse(linearizationMethod, action); + default Tree + flatMapTree(final Function> mapper) { + return topDownTransform(dat -> TopDownTransformResult.PUSHDOWN, node -> { + if (node.getChildrenCount() > 0) { + final Tree parent = node.transformHead(mapper); - action.accept(data); - - children.getByIndex(1).traverse(linearizationMethod, action); - break; - case POSTORDER: - children.forEach(child -> child.traverse(linearizationMethod, action)); - - action.accept(data); - break; - case PREORDER: - action.accept(data); - - children.forEach(child -> child.traverse(linearizationMethod, action)); - break; - default: - break; + node.doForChildren(parent::addChild); + return parent; } - } else { - action.accept(data); - } - } - - @Override - public ReturnedType collapse( - final Function leafTransform, - final BiFunction, NewType> nodeCollapser, - final Function resultTransformer) { - return resultTransformer.apply(internalCollapse(leafTransform, nodeCollapser)); - } - - @Override - public ITree - flatMapTree(final Function> mapper) { - if (hasChildren) { - final ITree flatMappedData = mapper.apply(data); - - final IList> mappedChildren - = children.map(child -> child.flatMapTree(mapper)); - - mappedChildren.forEach(flatMappedData::addChild); - - return flatMappedData; - } - return mapper.apply(data); + return node.transformHead(mapper); + }); } - /* - * Do a collapse of this tree. + /** + * Get the specified child of this tree. + * + * @param childNo + * The number of the child to get. + * + * @return The specified child of this tree. */ - - private NewType internalCollapse( - final Function leafTransform, - final BiFunction, NewType> nodeCollapser) { - if (hasChildren) { - final IList collapsedChildren = children.map(child -> { - final NewType collapsed = child.collapse(leafTransform, nodeCollapser, - subTreeVal -> subTreeVal); - - return collapsed; - }); - - return nodeCollapser.apply(data, collapsedChildren); - } - - return leafTransform.apply(data); - } - - private void internalToString(final StringBuilder builder, final int indentLevel, - final boolean initial) { - if (!initial) { - for (int i = 0; i < indentLevel; i++) builder.append(">\t"); - } - - builder.append("Node #"); - builder.append(ID); - builder.append(": "); - builder.append(data == null ? "(null)" : data.toString()); - builder.append("\n"); - - if (hasChildren) { - children.forEach(child -> { - if (child instanceof Tree) { - final Tree kid = (Tree) child; - - kid.internalToString(builder, indentLevel + 1, false); - } else { - for (int i = 0; i < indentLevel + 1; i++) { - builder.append(">\t"); - } - - builder.append("Unknown node of type "); - builder.append(child.getClass().getName()); - builder.append("\n"); - } - }); - } + default Tree getChild(final int childNo) { + return transformChild(childNo, child -> child); } - @Override - public ITree rebuildTree( - final Function leafTransformer, - final Function operatorTransformer) { - if (hasChildren) { - final IList> mappedChildren = - children.map(child -> - child.rebuildTree(leafTransformer, operatorTransformer)); - - final MappedType mapData = operatorTransformer.apply(data); - return new Tree<>(mapData, mappedChildren); - } - - return new Tree<>(leafTransformer.apply(data)); - } + /** + * Get a count of the number of direct children this node has. + * + * @return The number of direct children this node has. + */ + int getChildrenCount(); - @Override - public void selectiveTransform(final Predicate nodePicker, - final UnaryOperator transformer) { - if (hasChildren) { - children.forEach(child -> child.selectiveTransform(nodePicker, transformer)); - } else { - data = transformer.apply(data); - } + /** + * Get a count of the number of direct children this node has. + * + * @return The number of direct children this node has. + */ + default int size() { + return getChildrenCount(); } - @Override - public ITree topDownTransform( - final Function transformPicker, - final UnaryOperator> transformer) { - final TopDownTransformResult transformResult = transformPicker.apply(data); - - switch (transformResult) { - case PASSTHROUGH: - ITree result = new Tree<>(data); - - if (hasChildren) { - children.forEach(child -> { - final ITree kid - = child.topDownTransform(transformPicker, transformer); - - result.addChild(kid); - }); - } - - return result; - case SKIP: - return this; - case TRANSFORM: - return transformer.apply(this); - case RTRANSFORM: - return transformer.apply(this).topDownTransform(transformPicker, transformer); - case PUSHDOWN: - result = new Tree<>(data); - - if (hasChildren) { - children.forEach(child -> { - final ITree kid - = child.topDownTransform(transformPicker, transformer); - - result.addChild(kid); - }); - } - - return transformer.apply(result); - case PULLUP: - final ITree intermediateResult = transformer.apply(this); - - result = new Tree<>(intermediateResult.getHead()); - - intermediateResult.doForChildren(child -> { - final ITree kid - = child.topDownTransform(transformPicker, transformer); - - result.addChild(kid); - }); - - return result; - default: - final String msg = String.format("Recieved unknown transform result type %s", - transformResult); - - throw new IllegalArgumentException(msg); - } + /** + * Get the data stored in this node. + * + * @return The data stored in this node. + */ + default ContainedType getHead() { + return transformHead(head -> head); } - @Override - public TransformedType transformChild(final int childNo, - final Function, TransformedType> transformer) { - if (childNo < 0 || childNo > childCount - 1) { - final String msg = String.format("Child index #%d is invalid", childNo); - - throw new IllegalArgumentException(msg); - } - - final ITree selectedKid = children.getByIndex(childNo); + /** + * Rebuild the tree with the same structure, but different nodes. + * + * @param + * The type of the new tree. + * + * @param leafTransformer + * The function to use to transform leaf tokens. + * + * @param internalTransformer + * The function to use to transform internal tokens. + * + * @return The tree, with the nodes changed. + */ + Tree rebuildTree( + Function leafTransformer, + Function internalTransformer); - return transformer.apply(selectedKid); - } + /** + * Transform some of the nodes in this tree. + * + * @param nodePicker + * The predicate to use to pick nodes to transform. + * + * @param transformer + * The function to use to transform picked nodes. + */ + void selectiveTransform(Predicate nodePicker, + UnaryOperator transformer); - @Override - public ITree getChild(final int childNo) { - if (childNo < 0 || childNo > childCount - 1) { - final String msg = String.format("Child index #%d is invalid", childNo); + /** + * Do a top-down transform of the tree. + * + * @param transformPicker + * The function to use to pick how to progress. + * + * @param transformer + * The function used to transform picked subtrees. + * + * @return The tree with the transform applied to picked subtrees. + */ + Tree topDownTransform( + Function transformPicker, + UnaryOperator> transformer); - throw new IllegalArgumentException(msg); - } - return children.getByIndex(childNo); - } + /** + * Transform one of this nodes children. + * + * @param + * The type of the transformed value. + * + * @param childNo + * The number of the child to transform. + * + * @param transformer + * The function to use to transform the value. + * + * @return The transformed value. + * + * @throws IllegalArgumentException + * if the childNo is out of bounds (0 <= + * childNo <= childCount()). + */ + TransformedType transformChild(int childNo, + Function, TransformedType> transformer); - @Override - public TransformedType - transformHead(final Function transformer) { - return transformer.apply(data); - } + /** + * Transform the value that is the head of this node. + * + * @param + * The type of the transformed value. + * + * @param transformer + * The function to use to transform the value. + * + * @return The transformed value. + */ + TransformedType + transformHead(Function transformer); - @Override - public void setHead(ContainedType dat) { - this.data = dat; + /** + * Transform the tree into a tree with a different type of token. + * + * @param + * The type of the new tree. + * + * @param transformer + * The function to use to transform tokens. + * + * @return A tree with the token types transformed. + */ + default Tree + transformTree(final Function transformer) { + return rebuildTree(transformer, transformer); } - @Override - public int hashCode() { - final int prime = 31; - int result = 1; - - result = prime * result + childCount; - result = prime * result + (children == null ? 0 : children.hashCode()); - result = prime * result + (data == null ? 0 : data.hashCode()); - - return result; - } + /** + * Perform an action on each part of the tree. + * + * @param linearizationMethod + * The way to traverse the tree. + * + * @param action + * The action to perform on each tree node. + */ + void traverse(TreeLinearizationMethod linearizationMethod, + Consumer action); - @Override - public String toString() { - final StringBuilder builder = new StringBuilder(); + /** + * Find the farthest to right child that satisfies the given predicate. + * + * @param childPred + * The predicate to satisfy. + * + * @return The index of the right-most child that satisfies the predicate, or -1 + * if one doesn't exist. + */ + int revFind(Predicate> childPred); - internalToString(builder, 1, true); + /** + * Check if this tree contains any nodes that satisfy the predicate. + * + * @param pred + * The predicate to look for. + * + * @return Whether or not any items satisfied the predicate. + */ + default boolean containsMatching(Predicate pred) { + Toggle tog = new OneWayToggle<>(false, true); - /* Delete a trailing nl. */ - builder.deleteCharAt(builder.length() - 1); + traverse(TreeLinearizationMethod.POSTORDER, val -> { + if (pred.test(val)) tog.get(); + }); - return builder.toString(); + return tog.get(); } - @Override - public boolean equals(final Object obj) { - if (this == obj) return true; - if (obj == null) return false; - if (!(obj instanceof Tree)) return false; - - final Tree other = (Tree) obj; - - if (data == null) { - if (other.data != null) return false; - } else if (!data.equals(other.data)) { - return false; - } - - if (childCount != other.childCount) return false; - - if (children == null) { - if (other.children != null) return false; - } else if (!children.equals(other.children)) { - return false; - } - - return true; - } + /** + * Set the head of the tree. + * + * @param dat + * The value to set as the head of the tree. + */ + void setHead(ContainedType dat); } diff --git a/src/main/java/bjc/data/internals/BoundLazy.java b/src/main/java/bjc/data/internals/BoundLazy.java index a350a2b..0e0e95c 100644 --- a/src/main/java/bjc/data/internals/BoundLazy.java +++ b/src/main/java/bjc/data/internals/BoundLazy.java @@ -4,10 +4,10 @@ import java.util.function.Function; import java.util.function.Supplier; import java.util.function.UnaryOperator; -import bjc.data.IHolder; +import bjc.data.Holder; import bjc.data.Lazy; import bjc.funcdata.FunctionalList; -import bjc.funcdata.IList; +import bjc.funcdata.ListEx; /** * Implements a lazy holder that has been bound. @@ -19,21 +19,21 @@ import bjc.funcdata.IList; * The type of the new bound value. */ public class BoundLazy - implements IHolder { + implements Holder { /* The old value. */ - private final Supplier> oldSupplier; + private final Supplier> oldSupplier; /* The function to use to transform the old value into a new value. */ - private final Function> binder; + private final Function> binder; /* The bound value being held. */ - private IHolder boundHolder; + private Holder boundHolder; /* Whether the bound value has been actualized or not. */ private boolean holderBound; /* Transformations currently pending on the bound value. */ - private final IList> actions + private final ListEx> actions = new FunctionalList<>(); /** @@ -45,20 +45,20 @@ public class BoundLazy * @param binder * The function to use to bind the old value to the new one. */ - public BoundLazy(final Supplier> supp, - final Function> binder) { + public BoundLazy(final Supplier> supp, + final Function> binder) { oldSupplier = supp; this.binder = binder; } @Override - public IHolder - bind(final Function> bindr) { + public Holder + bind(final Function> bindr) { if (bindr == null) throw new NullPointerException("Binder must not be null"); /* Prepare a list of pending actions. */ - final IList> pendingActions + final ListEx> pendingActions = new FunctionalList<>(); for (UnaryOperator pendAct : actions) { @@ -66,8 +66,8 @@ public class BoundLazy } /* Create the new supplier of a value. */ - final Supplier> typeSupplier = () -> { - IHolder oldHolder = boundHolder; + final Supplier> typeSupplier = () -> { + Holder oldHolder = boundHolder; /* Bind the value if it hasn't been bound before. */ if (!holderBound) { @@ -83,7 +83,7 @@ public class BoundLazy } @Override - public Function> + public Function> lift(final Function func) { if (func == null) throw new NullPointerException("Function to lift must not be null"); @@ -94,13 +94,13 @@ public class BoundLazy } @Override - public IHolder + public Holder map(final Function mapper) { if (mapper == null) throw new NullPointerException("Mapper must not be null"); /* Prepare a list of pending actions. */ - final IList> pendingActions + final ListEx> pendingActions = new FunctionalList<>(); for (UnaryOperator pendAct : actions) { @@ -109,7 +109,7 @@ public class BoundLazy /* Prepare the new supplier. */ final Supplier typeSupplier = () -> { - IHolder oldHolder = boundHolder; + Holder oldHolder = boundHolder; /* Bound the value if it hasn't been bound. */ if (!holderBound) { @@ -133,7 +133,7 @@ public class BoundLazy } @Override - public IHolder + public Holder transform(final UnaryOperator transformer) { if (transformer == null) throw new NullPointerException("Transformer must not be null"); diff --git a/src/main/java/bjc/data/internals/BoundLazyPair.java b/src/main/java/bjc/data/internals/BoundLazyPair.java index e081c04..91981de 100644 --- a/src/main/java/bjc/data/internals/BoundLazyPair.java +++ b/src/main/java/bjc/data/internals/BoundLazyPair.java @@ -4,8 +4,8 @@ import java.util.function.BiFunction; import java.util.function.Function; import java.util.function.Supplier; -import bjc.data.IHolder; -import bjc.data.IPair; +import bjc.data.Holder; +import bjc.data.Pair; import bjc.data.Identity; import bjc.data.LazyPair; @@ -16,17 +16,17 @@ import bjc.data.LazyPair; */ @SuppressWarnings("javadoc") public class BoundLazyPair - implements IPair { + implements Pair { /* The supplier of the left value. */ private final Supplier leftSupplier; /* The supplier of the right value. */ private final Supplier rightSupplier; /* The binder to transform values. */ - private final BiFunction> binder; + private final BiFunction> binder; /* The bound pair. */ - private IPair boundPair; + private Pair boundPair; /* Whether the pair has been bound yet. */ private boolean pairBound; @@ -46,20 +46,20 @@ public class BoundLazyPair */ public BoundLazyPair(final Supplier leftSupp, final Supplier rightSupp, - final BiFunction> bindr) { + final BiFunction> bindr) { leftSupplier = leftSupp; rightSupplier = rightSupp; binder = bindr; } @Override - public IPair bind( - final BiFunction> bindr) { + public Pair bind( + final BiFunction> bindr) { if (bindr == null) throw new NullPointerException("Binder must not be null"); - final IHolder> newPair = new Identity<>(boundPair); - final IHolder newPairMade = new Identity<>(pairBound); + final Holder> newPair = new Identity<>(boundPair); + final Holder newPairMade = new Identity<>(pairBound); final Supplier leftSupp = () -> { if (!newPairMade.getValue()) { @@ -91,13 +91,13 @@ public class BoundLazyPair } @Override - public IPair - bindLeft(final Function> leftBinder) { + public Pair + bindLeft(final Function> leftBinder) { if (leftBinder == null) throw new NullPointerException("Left binder must not be null"); final Supplier leftSupp = () -> { - IPair newPair = boundPair; + Pair newPair = boundPair; if (!pairBound) { /* @@ -113,13 +113,13 @@ public class BoundLazyPair } @Override - public IPair - bindRight(final Function> rightBinder) { + public Pair + bindRight(final Function> rightBinder) { if (rightBinder == null) throw new NullPointerException("Right binder must not be null"); final Supplier rightSupp = () -> { - IPair newPair = boundPair; + Pair newPair = boundPair; if (!pairBound) { /* @@ -136,8 +136,8 @@ public class BoundLazyPair @Override public - IPair - combine(final IPair otherPair, + Pair + combine(final Pair otherPair, final BiFunction leftCombiner, final BiFunction rightCombiner) { if (otherPair == null) { @@ -157,7 +157,7 @@ public class BoundLazyPair } @Override - public IPair + public Pair mapLeft(final Function mapper) { if (mapper == null) throw new NullPointerException("Mapper must not be null"); @@ -184,7 +184,7 @@ public class BoundLazyPair } @Override - public IPair + public Pair mapRight(final Function mapper) { if (mapper == null) throw new NullPointerException("Mapper must not be null"); diff --git a/src/main/java/bjc/data/internals/BoundListHolder.java b/src/main/java/bjc/data/internals/BoundListHolder.java index 1193c8d..c944252 100644 --- a/src/main/java/bjc/data/internals/BoundListHolder.java +++ b/src/main/java/bjc/data/internals/BoundListHolder.java @@ -3,9 +3,9 @@ package bjc.data.internals; import java.util.function.Function; import java.util.function.UnaryOperator; -import bjc.data.IHolder; +import bjc.data.Holder; import bjc.data.ListHolder; -import bjc.funcdata.IList; +import bjc.funcdata.ListEx; /** * Holds a list, converted into a holder. @@ -13,9 +13,9 @@ import bjc.funcdata.IList; * @author Ben Culkin */ @SuppressWarnings("javadoc") -public class BoundListHolder implements IHolder { +public class BoundListHolder implements Holder { /* The list of contained holders. */ - private final IList> heldHolders; + private final ListEx> heldHolders; /** * Create a new list of holders. @@ -23,17 +23,17 @@ public class BoundListHolder implements IHolder { * @param toHold * The list of holders to, well, hold. */ - public BoundListHolder(final IList> toHold) { + public BoundListHolder(final ListEx> toHold) { heldHolders = toHold; } @Override - public IHolder - bind(final Function> binder) { + public Holder + bind(final Function> binder) { if (binder == null) throw new NullPointerException("Binder must not be null"); - final IList> boundHolders + final ListEx> boundHolders = heldHolders.map(containedHolder -> { return containedHolder.bind(binder); }); @@ -42,7 +42,7 @@ public class BoundListHolder implements IHolder { } @Override - public Function> + public Function> lift(final Function func) { if (func == null) throw new NullPointerException("Function to lift must not be null"); @@ -53,12 +53,12 @@ public class BoundListHolder implements IHolder { } @Override - public IHolder + public Holder map(final Function mapper) { if (mapper == null) throw new NullPointerException("Mapper must not be null"); - final IList> mappedHolders + final ListEx> mappedHolders = heldHolders.map(containedHolder -> { return containedHolder.map(mapper); }); @@ -67,7 +67,7 @@ public class BoundListHolder implements IHolder { } @Override - public IHolder + public Holder transform(final UnaryOperator transformer) { if (transformer == null) throw new NullPointerException("Transformer must not be null"); diff --git a/src/main/java/bjc/data/internals/HalfBoundLazyPair.java b/src/main/java/bjc/data/internals/HalfBoundLazyPair.java index 6bcb6ae..849b973 100644 --- a/src/main/java/bjc/data/internals/HalfBoundLazyPair.java +++ b/src/main/java/bjc/data/internals/HalfBoundLazyPair.java @@ -4,8 +4,8 @@ import java.util.function.BiFunction; import java.util.function.Function; import java.util.function.Supplier; -import bjc.data.IHolder; -import bjc.data.IPair; +import bjc.data.Holder; +import bjc.data.Pair; import bjc.data.Identity; import bjc.data.LazyPair; @@ -24,15 +24,15 @@ import bjc.data.LazyPair; */ @SuppressWarnings("javadoc") public class HalfBoundLazyPair - implements IPair { + implements Pair { /* The supplier of the old value. */ private final Supplier oldSupplier; /* The function to transform the old value into a new pair. */ - private final Function> binder; + private final Function> binder; /* The new bound pair. */ - private IPair boundPair; + private Pair boundPair; /* Has the pair been bound yet or not? */ private boolean pairBound; @@ -46,16 +46,16 @@ public class HalfBoundLazyPair * The function to use to create the pair from the old value. */ public HalfBoundLazyPair(final Supplier oldSupp, - final Function> bindr) { + final Function> bindr) { oldSupplier = oldSupp; binder = bindr; } @Override - public IPair bind( - final BiFunction> bindr) { - final IHolder> newPair = new Identity<>(boundPair); - final IHolder newPairMade = new Identity<>(pairBound); + public Pair bind( + final BiFunction> bindr) { + final Holder> newPair = new Identity<>(boundPair); + final Holder newPairMade = new Identity<>(pairBound); final Supplier leftSupp = () -> { if (!newPairMade.getValue()) { @@ -81,10 +81,10 @@ public class HalfBoundLazyPair } @Override - public IPair - bindLeft(final Function> leftBinder) { + public Pair + bindLeft(final Function> leftBinder) { final Supplier leftSupp = () -> { - IPair newPair = boundPair; + Pair newPair = boundPair; if (!pairBound) { newPair = binder.apply(oldSupplier.get()); @@ -97,10 +97,10 @@ public class HalfBoundLazyPair } @Override - public IPair - bindRight(final Function> rightBinder) { + public Pair + bindRight(final Function> rightBinder) { final Supplier rightSupp = () -> { - IPair newPair = boundPair; + Pair newPair = boundPair; if (!pairBound) { newPair = binder.apply(oldSupplier.get()); @@ -114,8 +114,8 @@ public class HalfBoundLazyPair @Override public - IPair - combine(final IPair otherPair, + Pair + combine(final Pair otherPair, final BiFunction leftCombiner, final BiFunction rightCombiner) { return otherPair.bind((otherLeft, otherRight) -> bind((leftVal, rightVal) -> { @@ -127,7 +127,7 @@ public class HalfBoundLazyPair } @Override - public IPair + public Pair mapLeft(final Function mapper) { final Supplier leftSupp = () -> { if (pairBound) @@ -149,7 +149,7 @@ public class HalfBoundLazyPair } @Override - public IPair + public Pair mapRight(final Function mapper) { final Supplier leftSupp = () -> { if (pairBound) diff --git a/src/main/java/bjc/data/internals/WrappedLazy.java b/src/main/java/bjc/data/internals/WrappedLazy.java index cda86fd..624fb1b 100644 --- a/src/main/java/bjc/data/internals/WrappedLazy.java +++ b/src/main/java/bjc/data/internals/WrappedLazy.java @@ -3,7 +3,7 @@ package bjc.data.internals; import java.util.function.Function; import java.util.function.UnaryOperator; -import bjc.data.IHolder; +import bjc.data.Holder; import bjc.data.Lazy; /** @@ -13,9 +13,9 @@ import bjc.data.Lazy; * @param * The type of the wrapped value. */ -public class WrappedLazy implements IHolder { +public class WrappedLazy implements Holder { /* Held value. */ - private final IHolder> held; + private final Holder> held; /** * Create a new wrapped lazy value. @@ -23,7 +23,7 @@ public class WrappedLazy implements IHolder { * @param wrappedHolder * The holder to make lazy. */ - public WrappedLazy(final IHolder wrappedHolder) { + public WrappedLazy(final Holder wrappedHolder) { held = new Lazy<>(wrappedHolder); } @@ -34,15 +34,15 @@ public class WrappedLazy implements IHolder { * This is a case where reified generics would be useful, because then the * compiler could know which one we meant without the dummy parameter. */ - private WrappedLazy(final IHolder> wrappedHolder, + private WrappedLazy(final Holder> wrappedHolder, @SuppressWarnings("unused") final boolean dummy) { held = wrappedHolder; } @Override - public IHolder - bind(final Function> binder) { - final IHolder> newHolder = held.map(containedHolder -> { + public Holder + bind(final Function> binder) { + final Holder> newHolder = held.map(containedHolder -> { return containedHolder.bind(binder); }); @@ -50,7 +50,7 @@ public class WrappedLazy implements IHolder { } @Override - public Function> + public Function> lift(final Function func) { return val -> { return new Lazy<>(func.apply(val)); @@ -58,9 +58,9 @@ public class WrappedLazy implements IHolder { } @Override - public IHolder + public Holder map(final Function mapper) { - final IHolder> newHolder = held.map(containedHolder -> { + final Holder> newHolder = held.map(containedHolder -> { return containedHolder.map(mapper); }); @@ -68,7 +68,7 @@ public class WrappedLazy implements IHolder { } @Override - public IHolder + public Holder transform(final UnaryOperator transformer) { held.transform(containedHolder -> { return containedHolder.transform(transformer); diff --git a/src/main/java/bjc/data/internals/WrappedOption.java b/src/main/java/bjc/data/internals/WrappedOption.java index 6becc16..f46d501 100644 --- a/src/main/java/bjc/data/internals/WrappedOption.java +++ b/src/main/java/bjc/data/internals/WrappedOption.java @@ -3,7 +3,7 @@ package bjc.data.internals; import java.util.function.Function; import java.util.function.UnaryOperator; -import bjc.data.IHolder; +import bjc.data.Holder; import bjc.data.Option; /** @@ -13,9 +13,9 @@ import bjc.data.Option; * @param * The wrapped type. */ -public class WrappedOption implements IHolder { +public class WrappedOption implements Holder { /* The held value. */ - private final IHolder> held; + private final Holder> held; /** * Create a new wrapped option. @@ -23,7 +23,7 @@ public class WrappedOption implements IHolder { * @param seedValue * The value to wrap. */ - public WrappedOption(final IHolder seedValue) { + public WrappedOption(final Holder seedValue) { held = new Option<>(seedValue); } @@ -31,15 +31,15 @@ public class WrappedOption implements IHolder { * The dummy parameter is to ensure the compiler can pick the right method, * because without this method erases to the same type as the public one. */ - private WrappedOption(final IHolder> toHold, + private WrappedOption(final Holder> toHold, @SuppressWarnings("unused") final boolean dummy) { held = toHold; } @Override - public IHolder - bind(final Function> binder) { - final IHolder> newHolder = held.map(containedHolder -> { + public Holder + bind(final Function> binder) { + final Holder> newHolder = held.map(containedHolder -> { return containedHolder.bind((containedValue) -> { if (containedValue == null) return new Option<>(null); @@ -52,7 +52,7 @@ public class WrappedOption implements IHolder { } @Override - public Function> + public Function> lift(final Function func) { return val -> { return new Option<>(func.apply(val)); @@ -60,9 +60,9 @@ public class WrappedOption implements IHolder { } @Override - public IHolder + public Holder map(final Function mapper) { - final IHolder> newHolder = held.map(containedHolder -> { + final Holder> newHolder = held.map(containedHolder -> { return containedHolder.map((containedValue) -> { if (containedValue == null) return null; @@ -75,7 +75,7 @@ public class WrappedOption implements IHolder { } @Override - public IHolder + public Holder transform(final UnaryOperator transformer) { held.transform(containedHolder -> { return containedHolder.transform((containedValue) -> { diff --git a/src/main/java/bjc/esodata/PushdownMap.java b/src/main/java/bjc/esodata/PushdownMap.java index 410eb53..76dd2db 100644 --- a/src/main/java/bjc/esodata/PushdownMap.java +++ b/src/main/java/bjc/esodata/PushdownMap.java @@ -20,9 +20,9 @@ import bjc.funcdata.*; * @param * The values in the map. */ -public class PushdownMap implements IMap { +public class PushdownMap implements MapEx { /* Our backing storage. */ - private final IMap> backing; + private final MapEx> backing; private boolean isFrozen = false; private boolean thawEnabled = true; @@ -60,7 +60,7 @@ public class PushdownMap implements IMap } @Override - public IList keyList() { + public ListEx keyList() { return backing.keyList(); } @@ -89,7 +89,7 @@ public class PushdownMap implements IMap public ValueType remove(final KeyType key) { if (isFrozen) throw new ObjectFrozen("Can't remove key " + key + " from frozen map"); - IHolder result = IHolder.of(null); + Holder result = Holder.of(null); backing.get(key).ifPresent((stk) -> { if (stk.size() > 1) { diff --git a/src/main/java/bjc/esodata/SimpleDirectory.java b/src/main/java/bjc/esodata/SimpleDirectory.java index ddc65b4..13a9f3e 100644 --- a/src/main/java/bjc/esodata/SimpleDirectory.java +++ b/src/main/java/bjc/esodata/SimpleDirectory.java @@ -1,7 +1,7 @@ package bjc.esodata; import bjc.funcdata.FunctionalMap; -import bjc.funcdata.IMap; +import bjc.funcdata.MapEx; /** * Simple implementation of {@link Directory}. @@ -18,9 +18,9 @@ import bjc.funcdata.IMap; */ public class SimpleDirectory implements Directory { /* Our sub-directories. */ - private final IMap> children; + private final MapEx> children; /* Our data. */ - private final IMap data; + private final MapEx data; /** Create a new directory. */ public SimpleDirectory() { diff --git a/src/main/java/bjc/esodata/UnifiedDirectory.java b/src/main/java/bjc/esodata/UnifiedDirectory.java index abf9a4c..1b630eb 100644 --- a/src/main/java/bjc/esodata/UnifiedDirectory.java +++ b/src/main/java/bjc/esodata/UnifiedDirectory.java @@ -1,7 +1,7 @@ package bjc.esodata; import bjc.funcdata.FunctionalMap; -import bjc.funcdata.IMap; +import bjc.funcdata.MapEx; /** * Simple implementation of {@link Directory}. @@ -18,9 +18,9 @@ import bjc.funcdata.IMap; */ public class UnifiedDirectory implements Directory { /* Our directory children. */ - private final IMap> children; + private final MapEx> children; /* Our data children. */ - private final IMap data; + private final MapEx data; /** Create a new directory. */ public UnifiedDirectory() { diff --git a/src/main/java/bjc/funcdata/ExtendedMap.java b/src/main/java/bjc/funcdata/ExtendedMap.java index 9638cdc..379ff65 100644 --- a/src/main/java/bjc/funcdata/ExtendedMap.java +++ b/src/main/java/bjc/funcdata/ExtendedMap.java @@ -15,11 +15,11 @@ import java.util.function.*; * @param * The type of the values of the map. */ -class ExtendedMap implements IMap { +class ExtendedMap implements MapEx { /* The map we delegate lookups to. */ - private final IMap delegate; + private final MapEx delegate; /* The map we store things in. */ - private final IMap store; + private final MapEx store; private boolean isFrozen = false; private boolean thawEnabled = true; @@ -33,8 +33,8 @@ class ExtendedMap implements IMap { * @param store * The map to store things in. */ - public ExtendedMap(final IMap delegate, - final IMap store) { + public ExtendedMap(final MapEx delegate, + final MapEx store) { this.delegate = delegate; this.store = store; } @@ -71,8 +71,8 @@ class ExtendedMap implements IMap { } @Override - public IList keyList() { - IList ilst = new FunctionalList<>(); + public ListEx keyList() { + ListEx ilst = new FunctionalList<>(); ilst.addAll(store.keyList()); ilst.addAll(delegate.keyList()); diff --git a/src/main/java/bjc/funcdata/Freezable.java b/src/main/java/bjc/funcdata/Freezable.java new file mode 100644 index 0000000..e83accb --- /dev/null +++ b/src/main/java/bjc/funcdata/Freezable.java @@ -0,0 +1,73 @@ +package bjc.funcdata; + +/** + * Indicates that an object can switch between immutable and mutable modes. + * + * Note that this only implements 'shallow' immutability. Namely, any sub-objects + * are not made immutable, and if the type is a collection, the elements are still + * as mutable as they were before. + * + * Implementations of this interface may choose to throw {@link ObjectFrozen} if + * you attempt to modify a frozen object, but they may also choose not to. + * + * @author Ben Culkin + */ +public interface Freezable { + /** + * Freezes the internal state of this object, making it immutable. + * + * @return True if the object is frozen, false if it couldn't be frozen. + */ + public boolean freeze(); + /** + * Thaws the internal state of this object, making it mutable. + * + * @return True if the object is thawed, false if it couldn't be thawed. + */ + public boolean thaw(); + + /** + * 'Deep-freeze' this object, making it immutable and disabling the ability to + * thaw it. + * + * @return True if the object was deep-frozen, false if that couldn't happen. + */ + default boolean deepFreeze() { + return false; + } + + /** + * Check if this object can be frozen. + * + * @return Whether or not the object can be frozen. + */ + default boolean canFreeze() { + return false; + } + + /** + * Checks if this object can be thawed. + * + * @return Whether or not the object can be thawed. + */ + default boolean canThaw() { + return false; + } + + /** + * Determines if this object is frozen. + * + * @return True if the object is frozen, false if the object is thawed. + */ + public boolean isFrozen(); + + + /** + * Determines if this object is thawed. + * + * @return True if the object is thawed, false if the object is thawed. + */ + default boolean isThawed() { + return !isFrozen(); + } +} diff --git a/src/main/java/bjc/funcdata/FunctionalList.java b/src/main/java/bjc/funcdata/FunctionalList.java index 2cdfa27..f9c06a3 100644 --- a/src/main/java/bjc/funcdata/FunctionalList.java +++ b/src/main/java/bjc/funcdata/FunctionalList.java @@ -12,10 +12,10 @@ import java.util.function.Consumer; import java.util.function.Function; import java.util.function.Predicate; -import bjc.data.IHolder; -import bjc.data.IPair; -import bjc.data.Identity; +import bjc.data.Holder; import bjc.data.Pair; +import bjc.data.Identity; +import bjc.data.SimplePair; /** * A wrapper over another list that provides eager functional operations over @@ -29,7 +29,7 @@ import bjc.data.Pair; * @param * The type in this list */ -public class FunctionalList implements Cloneable, IList { +public class FunctionalList implements Cloneable, ListEx { /* The list used as a backing store */ private final List wrapped; @@ -65,7 +65,7 @@ public class FunctionalList implements Cloneable, IList { * @return The returned list. */ @SafeVarargs - public static IList listOf(final T... items) { + public static ListEx listOf(final T... items) { return new FunctionalList<>(items); } @@ -137,8 +137,8 @@ public class FunctionalList implements Cloneable, IList { * @return A copy of the list. */ @Override - public IList clone() { - final IList cloned = new FunctionalList<>(); + public ListEx clone() { + final ListEx cloned = new FunctionalList<>(); for (final E element : wrapped) { cloned.add(element); @@ -148,7 +148,7 @@ public class FunctionalList implements Cloneable, IList { } @Override - public IList combineWith(final IList rightList, + public ListEx combineWith(final ListEx rightList, final BiFunction itemCombiner) { if (rightList == null) { throw new NullPointerException("Target combine list must not be null"); @@ -156,7 +156,7 @@ public class FunctionalList implements Cloneable, IList { throw new NullPointerException("Combiner must not be null"); } - final IList returned = new FunctionalList<>(); + final ListEx returned = new FunctionalList<>(); /* Get the iterator for the other list. */ final Iterator rightIterator = rightList.toIterable().iterator(); @@ -222,14 +222,14 @@ public class FunctionalList implements Cloneable, IList { } @Override - public IList flatMap(final Function> expander) { + public ListEx flatMap(final Function> expander) { if (expander == null) throw new NullPointerException("Expander must not be null"); - final IList returned = new FunctionalList<>(this.wrapped.size()); + final ListEx returned = new FunctionalList<>(this.wrapped.size()); forEach(element -> { - final IList expandedElement = expander.apply(element); + final ListEx expandedElement = expander.apply(element); if (expandedElement == null) throw new NullPointerException("Expander returned null list"); @@ -257,7 +257,7 @@ public class FunctionalList implements Cloneable, IList { /* * This is held b/c ref'd variables must be final/effectively final. */ - final IHolder currentIndex = new Identity<>(0); + final Holder currentIndex = new Identity<>(0); wrapped.forEach(element -> { /* Call the action with the index and the value. */ @@ -283,11 +283,11 @@ public class FunctionalList implements Cloneable, IList { } @Override - public IList getMatching(final Predicate predicate) { + public ListEx getMatching(final Predicate predicate) { if (predicate == null) throw new NullPointerException("Predicate must not be null"); - final IList returned = new FunctionalList<>(); + final ListEx returned = new FunctionalList<>(); wrapped.forEach(element -> { if (predicate.test(element)) { @@ -313,17 +313,17 @@ public class FunctionalList implements Cloneable, IList { /* Check if a partition has room for another item. */ private Boolean isPartitionFull(final int numberPerPartition, - final IHolder> currentPartition) { + final Holder> currentPartition) { return currentPartition .unwrap(partition -> partition.getSize() >= numberPerPartition); } @Override - public IList map(final Function elementTransformer) { + public ListEx map(final Function elementTransformer) { if (elementTransformer == null) throw new NullPointerException("Transformer must be not null"); - final IList returned = new FunctionalList<>(this.wrapped.size()); + final ListEx returned = new FunctionalList<>(this.wrapped.size()); forEach(element -> { // Add the transformed item to the result @@ -334,12 +334,12 @@ public class FunctionalList implements Cloneable, IList { } @Override - public IList> pairWith(final IList rightList) { - return combineWith(rightList, Pair::new); + public ListEx> pairWith(final ListEx rightList) { + return combineWith(rightList, SimplePair::new); } @Override - public IList> partition(final int numberPerPartition) { + public ListEx> partition(final int numberPerPartition) { if (numberPerPartition < 1 || numberPerPartition > wrapped.size()) { final String fmt = "%s is an invalid partition size. Must be between 1 and %d"; @@ -348,10 +348,10 @@ public class FunctionalList implements Cloneable, IList { throw new IllegalArgumentException(msg); } - final IList> returned = new FunctionalList<>(); + final ListEx> returned = new FunctionalList<>(); /* The current partition being filled. */ - final IHolder> currentPartition = new Identity<>(new FunctionalList<>()); + final Holder> currentPartition = new Identity<>(new FunctionalList<>()); this.forEach(element -> { if (isPartitionFull(numberPerPartition, currentPartition)) { @@ -395,7 +395,7 @@ public class FunctionalList implements Cloneable, IList { } /* The current collapsed list. */ - final IHolder currentState = new Identity<>(initialValue); + final Holder currentState = new Identity<>(initialValue); wrapped.forEach(element -> { /* Accumulate a new value into the state. */ @@ -444,7 +444,7 @@ public class FunctionalList implements Cloneable, IList { } @Override - public IList tail() { + public ListEx tail() { return new FunctionalList<>(wrapped.subList(1, getSize())); } diff --git a/src/main/java/bjc/funcdata/FunctionalMap.java b/src/main/java/bjc/funcdata/FunctionalMap.java index 3ab2598..3427a91 100644 --- a/src/main/java/bjc/funcdata/FunctionalMap.java +++ b/src/main/java/bjc/funcdata/FunctionalMap.java @@ -6,7 +6,7 @@ import java.util.function.*; import bjc.data.*; /** - * Basic implementation of {@link IMap} + * Basic implementation of {@link MapEx} * * @author ben * @@ -16,7 +16,7 @@ import bjc.data.*; * @param * The type of the map's values. */ -public class FunctionalMap implements IMap { +public class FunctionalMap implements MapEx { /* Our backing store. */ private Map wrappedMap; @@ -35,10 +35,10 @@ public class FunctionalMap implements IMap... entries) { + public FunctionalMap(final Pair... entries) { this(); - for (final IPair entry : entries) { + for (final Pair entry : entries) { entry.doWith(wrappedMap::put); } } @@ -89,7 +89,7 @@ public class FunctionalMap implements IMap keyList() { + public ListEx keyList() { final FunctionalList keys = new FunctionalList<>(); wrappedMap.keySet().forEach(keys::add); diff --git a/src/main/java/bjc/funcdata/FunctionalStringTokenizer.java b/src/main/java/bjc/funcdata/FunctionalStringTokenizer.java index 856c153..3344e05 100644 --- a/src/main/java/bjc/funcdata/FunctionalStringTokenizer.java +++ b/src/main/java/bjc/funcdata/FunctionalStringTokenizer.java @@ -128,7 +128,7 @@ public class FunctionalStringTokenizer { * * @return This tokenizer, converted into a list of strings. */ - public IList toList() { + public ListEx toList() { return toList((final String element) -> element); } @@ -144,11 +144,11 @@ public class FunctionalStringTokenizer { * * @return A list containing all of the converted tokens. */ - public IList toList(final Function transformer) { + public ListEx toList(final Function transformer) { if (transformer == null) throw new NullPointerException("Transformer must not be null"); - final IList returned = new FunctionalList<>(); + final ListEx returned = new FunctionalList<>(); /* Add each token to the list after transforming it. */ forEachToken(token -> { diff --git a/src/main/java/bjc/funcdata/IFreezable.java b/src/main/java/bjc/funcdata/IFreezable.java deleted file mode 100644 index abc7d6f..0000000 --- a/src/main/java/bjc/funcdata/IFreezable.java +++ /dev/null @@ -1,73 +0,0 @@ -package bjc.funcdata; - -/** - * Indicates that an object can switch between immutable and mutable modes. - * - * Note that this only implements 'shallow' immutability. Namely, any sub-objects - * are not made immutable, and if the type is a collection, the elements are still - * as mutable as they were before. - * - * Implementations of this interface may choose to throw {@link ObjectFrozen} if - * you attempt to modify a frozen object, but they may also choose not to. - * - * @author Ben Culkin - */ -public interface IFreezable { - /** - * Freezes the internal state of this object, making it immutable. - * - * @return True if the object is frozen, false if it couldn't be frozen. - */ - public boolean freeze(); - /** - * Thaws the internal state of this object, making it mutable. - * - * @return True if the object is thawed, false if it couldn't be thawed. - */ - public boolean thaw(); - - /** - * 'Deep-freeze' this object, making it immutable and disabling the ability to - * thaw it. - * - * @return True if the object was deep-frozen, false if that couldn't happen. - */ - default boolean deepFreeze() { - return false; - } - - /** - * Check if this object can be frozen. - * - * @return Whether or not the object can be frozen. - */ - default boolean canFreeze() { - return false; - } - - /** - * Checks if this object can be thawed. - * - * @return Whether or not the object can be thawed. - */ - default boolean canThaw() { - return false; - } - - /** - * Determines if this object is frozen. - * - * @return True if the object is frozen, false if the object is thawed. - */ - public boolean isFrozen(); - - - /** - * Determines if this object is thawed. - * - * @return True if the object is thawed, false if the object is thawed. - */ - default boolean isThawed() { - return !isFrozen(); - } -} diff --git a/src/main/java/bjc/funcdata/IList.java b/src/main/java/bjc/funcdata/IList.java deleted file mode 100644 index 0ff8e30..0000000 --- a/src/main/java/bjc/funcdata/IList.java +++ /dev/null @@ -1,455 +0,0 @@ -package bjc.funcdata; - -import java.util.Comparator; -import java.util.Iterator; -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 java.util.stream.Collector; - -import bjc.data.IPair; -import bjc.functypes.ID; - -/** - * A wrapper over another list that provides functional operations over it. - * - * @author ben - * - * @param - * The type in this list - */ -public interface IList extends Iterable { - /** - * Add an item to this list. - * - * @param item - * The item to add to this list. - * - * @return Whether the item was added to the list successfully.. - */ - boolean add(ContainedType item); - - /** - * Add all of the elements in the provided list to this list. - * - * @param items - * The list of items to add. - * - * @return True if every item was successfully added to the list, false - * otherwise. - */ - default boolean addAll(final IList items) { - return items.map(this::add).anyMatch(bl -> bl == false); - } - - /** - * Add all of the elements in the provided array to this list. - * - * @param items - * The array of items to add. - * - * @return True if every item was successfully added to the list, false - * otherwise. - */ - @SuppressWarnings("unchecked") - default boolean addAll(final ContainedType... items) { - boolean succ = true; - - for (final ContainedType item : items) { - final boolean addSucc = add(item); - - succ = succ ? addSucc : false; - } - - return succ; - } - - /** - * Check if all of the elements of this list match the specified predicate. - * - * @param matcher - * The predicate to use for checking. - * - * @return Whether all of the elements of the list match the specified - * predicate. - */ - boolean allMatch(Predicate matcher); - - /** - * Check if any of the elements in this list match the specified list. - * - * @param matcher - * The predicate to use for checking. - * - * @return Whether any element in the list matches the provided predicate. - */ - boolean anyMatch(Predicate matcher); - - /** - * Reduce the contents of this list using a collector. - * - * @param - * The intermediate accumulation type. - * - * @param - * The final, reduced type. - * - * @param collector - * The collector to use for reduction. - * - * @return The reduced list. - */ - default ReducedType - collect(final Collector collector) { - final BiConsumer accumulator = collector.accumulator(); - - final StateType initial = collector.supplier().get(); - return reduceAux(initial, (value, state) -> { - accumulator.accept(state, value); - - return state; - }, collector.finisher()); - } - - /** - * 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 - * The type of the second list. - * - * @param - * The type of the combined list. - * - * @param list - * The list to combine with. - * - * @param combiner - * The function to use for combining element pairs. - * - * @return A new list containing the merged pairs of lists. - */ - IList combineWith(IList list, - BiFunction combiner); - - /** - * Check if the list contains the specified item. - * - * @param item - * The item to see if it is contained. - * - * @return Whether or not the specified item is in the list. - */ - boolean contains(ContainedType item); - - /** - * Get the first element in the list. - * - * @return The first element in this list. - */ - ContainedType first(); - - /** - * Get the last element in the list. - * - * @return The last element in this list. - */ - ContainedType last(); - - /** - * Remove and return the first element from the list. - * - * @return The first element from the list. - */ - ContainedType popFirst(); - - /** - * Remove and return the last element from the list. - * - * @return The last element from the list. - */ - ContainedType popLast(); - - /** - * Apply a function to each member of the list, then flatten the results. - * - * Does not change the underlying list. - * - * @param - * The type of the flattened list. - * - * @param expander - * The function to apply to each member of the list. - * - * @return A new list containing the flattened results of applying the provided - * function. - */ - IList - flatMap(Function> expander); - - /** - * Apply a given action for each member of the list. - * - * @param action - * The action to apply to each member of the list. - */ - @Override - void forEach(Consumer action); - - /** - * Apply a given function to each element in the list and its index. - * - * @param action - * The function to apply to each element in the list and its - * index. - */ - void forEachIndexed(BiConsumer action); - - /** - * Retrieve a value in the list by its index. - * - * @param index - * The index to retrieve a value from. - * - * @return The value at the specified index in the list. - */ - ContainedType getByIndex(int index); - - /** - * Retrieve a list containing all elements matching a predicate. - * - * @param predicate - * The predicate to match by. - * - * @return A list containing all elements that match the predicate. - */ - IList getMatching(Predicate predicate); - - /** - * Retrieve the size of the wrapped list. - * - * @return The size of the wrapped list. - */ - int getSize(); - - /** - * Check if this list is empty. - * - * @return Whether or not this list is empty. - */ - boolean isEmpty(); - - /** - * Create a new list by applying the given function to each element in the list. - * - * Does not change the underlying list. - * - * @param - * The type of the transformed list. - * - * @param transformer - * The function to apply to each element in the list. - * - * @return A new list containing the mapped elements of this list. - */ - IList map(Function transformer); - - /** - * Zip two lists into a list of pairs. - * - * @param - * The type of the second list. - * - * @param list - * The list to use as the left side of the pair. - * - * @return A list containing pairs of this element and the specified list. - */ - IList> pairWith(IList list); - - /** - * Partition this list into a list of sublists. - * - * @param partitionSize - * The size of elements to put into each one of the - * sublists. - * - * @return A list partitioned into partitions of size partitionSize. The last - * partition may not be completely full if the size of the list is not a - * multiple of partitionSize. - */ - IList> partition(int partitionSize); - - /** - * Prepend an item to the list. - * - * @param item - * The item to prepend to the list. - */ - void prepend(ContainedType item); - - /** - * Prepend an array of items to the list. - * - * @param items - * The items to prepend to the list. - */ - @SuppressWarnings("unchecked") - default void prependAll(final ContainedType... items) { - for (final ContainedType item : items) { - prepend(item); - } - } - - /** - * Select a random item from the list, using a default random number generator. - * - * @return A random item from the list - */ - default ContainedType randItem() { - return randItem(num -> (int) (Math.random() * num)); - } - - /** - * 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. - */ - ContainedType randItem(Function rnd); - - /** - * Reduce this list to a single value, using a accumulative approach. - * - * @param - * The in-between type of the values - * - * @param - * The final value type - * - * @param initial - * The initial value of the accumulative state. - * - * @param accumulator - * The function to use to combine a list element with the - * accumulative state. - * - * @param transformer - * 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. - */ - ReducedType reduceAux(StateType initial, - BiFunction accumulator, - Function transformer); - - /** - * Reduce this list to a single value, using a accumulative approach. - * - * @param - * The in-between type of the values. - * - * @param initial - * The initial value of the accumulative state. - * - * @param accumulator - * The function to use to combine a list element with the - * accumulative state. - * - * @return A single value condensed from this list. - */ - default StateType reduceAux(StateType initial, - BiFunction accumulator) { - return reduceAux(initial, accumulator, ID.id()); - } - - /** - * Remove all elements that match a given predicate. - * - * @param predicate - * The predicate to use to determine elements to delete. - * - * @return Whether there was anything that satisfied the predicate. - */ - boolean removeIf(Predicate predicate); - - /** - * Remove all parameters that match a given parameter. - * - * @param element - * The object to remove all matching copies of. - */ - void removeMatching(ContainedType element); - - /** Reverse the contents of this list in place. */ - void reverse(); - - /** - * 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 comparator - * The way to compare elements for searching. Pass null to use - * the natural ordering for E. - * - * @return The element if it is in this list, or null if it is not. - */ - ContainedType search(ContainedType key, Comparator comparator); - - /** - * Sort the elements of this list using the provided way of comparing elements. - * - * Does change the underlying list. - * - * @param comparator - * The way to compare elements for sorting. Pass null to use - * E's natural ordering - */ - void sort(Comparator comparator); - - /** - * Get the tail of this list (the list without the first element). - * - * @return The list without the first element. - */ - IList tail(); - - /** - * Convert this list into an array. - * - * @param type - * The type of array to return. - * - * @return The list, as an array. - */ - ContainedType[] toArray(ContainedType[] type); - - /** - * Convert the list into a Iterable. - * - * @return An iterable view onto the list. - */ - Iterable toIterable(); - - @Override - default Iterator iterator() { - return toIterable().iterator(); - } -} diff --git a/src/main/java/bjc/funcdata/IMap.java b/src/main/java/bjc/funcdata/IMap.java deleted file mode 100644 index ca9ef11..0000000 --- a/src/main/java/bjc/funcdata/IMap.java +++ /dev/null @@ -1,216 +0,0 @@ -package bjc.funcdata; - -import java.util.*; -import java.util.function.*; - -/** - * Functional wrapper over map providing some useful things. - * - * @author ben - * - * @param - * The type of this map's keys. - * - * @param - * The type of this map's values. - */ -public interface IMap extends IFreezable { - /** - * Execute an action for each entry in the map. - * - * @param action - * The action to execute for each entry in the map. - */ - void forEach(BiConsumer action); - - /** - * Perform an action for each key in the map. - * - * @param action - * The action to perform on each key in the map. - */ - default void forEachKey(final Consumer action) { - forEach((key, val) -> action.accept(key)); - } - - /** - * Perform an action for each value in the map. - * - * @param action - * The action to perform on each value in the map. - */ - default void forEachValue(final Consumer action) { - forEach((key, val) -> action.accept(val)); - } - - /** - * Check if this map contains the specified key. - * - * @param key - * The key to check. - * - * @return Whether or not the map contains the key. - */ - boolean containsKey(KeyType key); - - /** - * Get the value assigned to the given key. - * - * @param key - * The key to look for a value under. - * - * @return The value of the key. - */ - Optional get(KeyType key); - - /** - * Add an entry to the map. - * - * @param key - * The key to put the value under. - * - * @param val - * The value to add. - * - * @return The previous value of the key in the map, or null if the key wasn't - * in the map. However, note that it may also return null if the key was - * set to null. - * - * @throws UnsupportedOperationException - * If the map implementation doesn't - * support modifying the map. - */ - ValueType put(KeyType key, ValueType val); - - /** Delete all the values in the map. */ - default void clear() { - if (isFrozen()) throw new ObjectFrozen("Can't clear a frozen map"); - - keyList().forEach(IMap.this::remove); - } - - /** - * Get the number of entries in this map. - * - * @return The number of entries in this map. - */ - default int size() { - return keyList().getSize(); - } - - /** - * Remove the value bound to the key. - * - * @param key - * The key to remove from the map. - * - * @return The previous value for the key in the map, or null if the key wasn't - * in the class. NOTE: Just because you received null, doesn't mean the - * map wasn't changed. It may mean that someone put a null value for - * that key into the map. - */ - ValueType remove(KeyType key); - - /** - * Get a list of all the keys in this map. - * - * @return A list of all the keys in this map. - */ - IList keyList(); - - /** - * Get a list of the values in this map. - * - * @return A list of values in this map. - */ - default IList valueList() { - final IList returns = new FunctionalList<>(); - - for (final KeyType key : keyList()) { - returns.add(get(key).orElse(null)); - } - - return returns; - } - - /* - * @NOTE Do we want this to be the semantics for transform, or do we want to go - * to semantics using something like Isomorphism, or doing a one-time bulk - * conversion of the values? - */ - - /** - * Transform the values returned by this map. - * - * NOTE: This transform is applied once for each lookup of a value, so the - * transform passed should be a proper function, or things will likely not work - * as expected. - * - * @param - * The new type of returned values. - * - * @param transformer - * The function to use to transform values. - * - * @return The map where each value will be transformed after lookup. - */ - default IMap transform(final Function transformer) { - return new TransformedValueMap<>(this, transformer); - } - - /** - * Extends this map, creating a new map that will delegate queries to the map, - * but store any added values itself. - * - * @return An extended map. - */ - default IMap extend() { - return extend(new FunctionalMap<>()); - }; - - - /** - * Extend this map, creating a new map that will delegate queries to - * the current map but store any added values in the provided map. - * - * @param backer The map to store values in. - * - * @return An extended map, with the specified backing map. - */ - default IMap extend(IMap backer) { - return new ExtendedMap<>(this, backer); - }; - - /** - * Static method to create a basic instance of IMap. - * - * @param The key type of the map. - * @param The value type of the map. - * - * @param args A series of key-value pairs. You will get an error if you don't - * provide the correct number of arguments (a number divisible by 2); - * however, if you pass arguments of the wrong type, you will not - * get a compile error, and usually won't get a runtime error in - * construction. However, you will get a ClassCastException as soon - * as you do something that attempts to iterate over the keys or values - * of the map. - * - * @return A map, constructed from the provided values. - * - * @throws IllegalArgumentException If you provide an incomplete pair of arguments. - */ - @SuppressWarnings("unchecked") - static IMap of(Object... args) { - if (args.length % 2 != 0) throw new IllegalArgumentException("Args must be in the form of key-value pairs"); - - IMap map = new FunctionalMap<>(); - for (int index = 0; index < args.length; index += 2) { - KeyType2 key = (KeyType2) args[index]; - ValueType2 value = (ValueType2) args[index + 1]; - - map.put(key, value); - } - - return map; - } -} diff --git a/src/main/java/bjc/funcdata/ListEx.java b/src/main/java/bjc/funcdata/ListEx.java new file mode 100644 index 0000000..164a71d --- /dev/null +++ b/src/main/java/bjc/funcdata/ListEx.java @@ -0,0 +1,455 @@ +package bjc.funcdata; + +import java.util.Comparator; +import java.util.Iterator; +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 java.util.stream.Collector; + +import bjc.data.Pair; +import bjc.functypes.ID; + +/** + * A wrapper over another list that provides functional operations over it. + * + * @author ben + * + * @param + * The type in this list + */ +public interface ListEx extends Iterable { + /** + * Add an item to this list. + * + * @param item + * The item to add to this list. + * + * @return Whether the item was added to the list successfully.. + */ + boolean add(ContainedType item); + + /** + * Add all of the elements in the provided list to this list. + * + * @param items + * The list of items to add. + * + * @return True if every item was successfully added to the list, false + * otherwise. + */ + default boolean addAll(final ListEx items) { + return items.map(this::add).anyMatch(bl -> bl == false); + } + + /** + * Add all of the elements in the provided array to this list. + * + * @param items + * The array of items to add. + * + * @return True if every item was successfully added to the list, false + * otherwise. + */ + @SuppressWarnings("unchecked") + default boolean addAll(final ContainedType... items) { + boolean succ = true; + + for (final ContainedType item : items) { + final boolean addSucc = add(item); + + succ = succ ? addSucc : false; + } + + return succ; + } + + /** + * Check if all of the elements of this list match the specified predicate. + * + * @param matcher + * The predicate to use for checking. + * + * @return Whether all of the elements of the list match the specified + * predicate. + */ + boolean allMatch(Predicate matcher); + + /** + * Check if any of the elements in this list match the specified list. + * + * @param matcher + * The predicate to use for checking. + * + * @return Whether any element in the list matches the provided predicate. + */ + boolean anyMatch(Predicate matcher); + + /** + * Reduce the contents of this list using a collector. + * + * @param + * The intermediate accumulation type. + * + * @param + * The final, reduced type. + * + * @param collector + * The collector to use for reduction. + * + * @return The reduced list. + */ + default ReducedType + collect(final Collector collector) { + final BiConsumer accumulator = collector.accumulator(); + + final StateType initial = collector.supplier().get(); + return reduceAux(initial, (value, state) -> { + accumulator.accept(state, value); + + return state; + }, collector.finisher()); + } + + /** + * 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 + * The type of the second list. + * + * @param + * The type of the combined list. + * + * @param list + * The list to combine with. + * + * @param combiner + * The function to use for combining element pairs. + * + * @return A new list containing the merged pairs of lists. + */ + ListEx combineWith(ListEx list, + BiFunction combiner); + + /** + * Check if the list contains the specified item. + * + * @param item + * The item to see if it is contained. + * + * @return Whether or not the specified item is in the list. + */ + boolean contains(ContainedType item); + + /** + * Get the first element in the list. + * + * @return The first element in this list. + */ + ContainedType first(); + + /** + * Get the last element in the list. + * + * @return The last element in this list. + */ + ContainedType last(); + + /** + * Remove and return the first element from the list. + * + * @return The first element from the list. + */ + ContainedType popFirst(); + + /** + * Remove and return the last element from the list. + * + * @return The last element from the list. + */ + ContainedType popLast(); + + /** + * Apply a function to each member of the list, then flatten the results. + * + * Does not change the underlying list. + * + * @param + * The type of the flattened list. + * + * @param expander + * The function to apply to each member of the list. + * + * @return A new list containing the flattened results of applying the provided + * function. + */ + ListEx + flatMap(Function> expander); + + /** + * Apply a given action for each member of the list. + * + * @param action + * The action to apply to each member of the list. + */ + @Override + void forEach(Consumer action); + + /** + * Apply a given function to each element in the list and its index. + * + * @param action + * The function to apply to each element in the list and its + * index. + */ + void forEachIndexed(BiConsumer action); + + /** + * Retrieve a value in the list by its index. + * + * @param index + * The index to retrieve a value from. + * + * @return The value at the specified index in the list. + */ + ContainedType getByIndex(int index); + + /** + * Retrieve a list containing all elements matching a predicate. + * + * @param predicate + * The predicate to match by. + * + * @return A list containing all elements that match the predicate. + */ + ListEx getMatching(Predicate predicate); + + /** + * Retrieve the size of the wrapped list. + * + * @return The size of the wrapped list. + */ + int getSize(); + + /** + * Check if this list is empty. + * + * @return Whether or not this list is empty. + */ + boolean isEmpty(); + + /** + * Create a new list by applying the given function to each element in the list. + * + * Does not change the underlying list. + * + * @param + * The type of the transformed list. + * + * @param transformer + * The function to apply to each element in the list. + * + * @return A new list containing the mapped elements of this list. + */ + ListEx map(Function transformer); + + /** + * Zip two lists into a list of pairs. + * + * @param + * The type of the second list. + * + * @param list + * The list to use as the left side of the pair. + * + * @return A list containing pairs of this element and the specified list. + */ + ListEx> pairWith(ListEx list); + + /** + * Partition this list into a list of sublists. + * + * @param partitionSize + * The size of elements to put into each one of the + * sublists. + * + * @return A list partitioned into partitions of size partitionSize. The last + * partition may not be completely full if the size of the list is not a + * multiple of partitionSize. + */ + ListEx> partition(int partitionSize); + + /** + * Prepend an item to the list. + * + * @param item + * The item to prepend to the list. + */ + void prepend(ContainedType item); + + /** + * Prepend an array of items to the list. + * + * @param items + * The items to prepend to the list. + */ + @SuppressWarnings("unchecked") + default void prependAll(final ContainedType... items) { + for (final ContainedType item : items) { + prepend(item); + } + } + + /** + * Select a random item from the list, using a default random number generator. + * + * @return A random item from the list + */ + default ContainedType randItem() { + return randItem(num -> (int) (Math.random() * num)); + } + + /** + * 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. + */ + ContainedType randItem(Function rnd); + + /** + * Reduce this list to a single value, using a accumulative approach. + * + * @param + * The in-between type of the values + * + * @param + * The final value type + * + * @param initial + * The initial value of the accumulative state. + * + * @param accumulator + * The function to use to combine a list element with the + * accumulative state. + * + * @param transformer + * 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. + */ + ReducedType reduceAux(StateType initial, + BiFunction accumulator, + Function transformer); + + /** + * Reduce this list to a single value, using a accumulative approach. + * + * @param + * The in-between type of the values. + * + * @param initial + * The initial value of the accumulative state. + * + * @param accumulator + * The function to use to combine a list element with the + * accumulative state. + * + * @return A single value condensed from this list. + */ + default StateType reduceAux(StateType initial, + BiFunction accumulator) { + return reduceAux(initial, accumulator, ID.id()); + } + + /** + * Remove all elements that match a given predicate. + * + * @param predicate + * The predicate to use to determine elements to delete. + * + * @return Whether there was anything that satisfied the predicate. + */ + boolean removeIf(Predicate predicate); + + /** + * Remove all parameters that match a given parameter. + * + * @param element + * The object to remove all matching copies of. + */ + void removeMatching(ContainedType element); + + /** Reverse the contents of this list in place. */ + void reverse(); + + /** + * 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 comparator + * The way to compare elements for searching. Pass null to use + * the natural ordering for E. + * + * @return The element if it is in this list, or null if it is not. + */ + ContainedType search(ContainedType key, Comparator comparator); + + /** + * Sort the elements of this list using the provided way of comparing elements. + * + * Does change the underlying list. + * + * @param comparator + * The way to compare elements for sorting. Pass null to use + * E's natural ordering + */ + void sort(Comparator comparator); + + /** + * Get the tail of this list (the list without the first element). + * + * @return The list without the first element. + */ + ListEx tail(); + + /** + * Convert this list into an array. + * + * @param type + * The type of array to return. + * + * @return The list, as an array. + */ + ContainedType[] toArray(ContainedType[] type); + + /** + * Convert the list into a Iterable. + * + * @return An iterable view onto the list. + */ + Iterable toIterable(); + + @Override + default Iterator iterator() { + return toIterable().iterator(); + } +} diff --git a/src/main/java/bjc/funcdata/MapEx.java b/src/main/java/bjc/funcdata/MapEx.java new file mode 100644 index 0000000..a7af4c5 --- /dev/null +++ b/src/main/java/bjc/funcdata/MapEx.java @@ -0,0 +1,216 @@ +package bjc.funcdata; + +import java.util.*; +import java.util.function.*; + +/** + * Functional wrapper over map providing some useful things. + * + * @author ben + * + * @param + * The type of this map's keys. + * + * @param + * The type of this map's values. + */ +public interface MapEx extends Freezable { + /** + * Execute an action for each entry in the map. + * + * @param action + * The action to execute for each entry in the map. + */ + void forEach(BiConsumer action); + + /** + * Perform an action for each key in the map. + * + * @param action + * The action to perform on each key in the map. + */ + default void forEachKey(final Consumer action) { + forEach((key, val) -> action.accept(key)); + } + + /** + * Perform an action for each value in the map. + * + * @param action + * The action to perform on each value in the map. + */ + default void forEachValue(final Consumer action) { + forEach((key, val) -> action.accept(val)); + } + + /** + * Check if this map contains the specified key. + * + * @param key + * The key to check. + * + * @return Whether or not the map contains the key. + */ + boolean containsKey(KeyType key); + + /** + * Get the value assigned to the given key. + * + * @param key + * The key to look for a value under. + * + * @return The value of the key. + */ + Optional get(KeyType key); + + /** + * Add an entry to the map. + * + * @param key + * The key to put the value under. + * + * @param val + * The value to add. + * + * @return The previous value of the key in the map, or null if the key wasn't + * in the map. However, note that it may also return null if the key was + * set to null. + * + * @throws UnsupportedOperationException + * If the map implementation doesn't + * support modifying the map. + */ + ValueType put(KeyType key, ValueType val); + + /** Delete all the values in the map. */ + default void clear() { + if (isFrozen()) throw new ObjectFrozen("Can't clear a frozen map"); + + keyList().forEach(MapEx.this::remove); + } + + /** + * Get the number of entries in this map. + * + * @return The number of entries in this map. + */ + default int size() { + return keyList().getSize(); + } + + /** + * Remove the value bound to the key. + * + * @param key + * The key to remove from the map. + * + * @return The previous value for the key in the map, or null if the key wasn't + * in the class. NOTE: Just because you received null, doesn't mean the + * map wasn't changed. It may mean that someone put a null value for + * that key into the map. + */ + ValueType remove(KeyType key); + + /** + * Get a list of all the keys in this map. + * + * @return A list of all the keys in this map. + */ + ListEx keyList(); + + /** + * Get a list of the values in this map. + * + * @return A list of values in this map. + */ + default ListEx valueList() { + final ListEx returns = new FunctionalList<>(); + + for (final KeyType key : keyList()) { + returns.add(get(key).orElse(null)); + } + + return returns; + } + + /* + * @NOTE Do we want this to be the semantics for transform, or do we want to go + * to semantics using something like Isomorphism, or doing a one-time bulk + * conversion of the values? + */ + + /** + * Transform the values returned by this map. + * + * NOTE: This transform is applied once for each lookup of a value, so the + * transform passed should be a proper function, or things will likely not work + * as expected. + * + * @param + * The new type of returned values. + * + * @param transformer + * The function to use to transform values. + * + * @return The map where each value will be transformed after lookup. + */ + default MapEx transform(final Function transformer) { + return new TransformedValueMap<>(this, transformer); + } + + /** + * Extends this map, creating a new map that will delegate queries to the map, + * but store any added values itself. + * + * @return An extended map. + */ + default MapEx extend() { + return extend(new FunctionalMap<>()); + }; + + + /** + * Extend this map, creating a new map that will delegate queries to + * the current map but store any added values in the provided map. + * + * @param backer The map to store values in. + * + * @return An extended map, with the specified backing map. + */ + default MapEx extend(MapEx backer) { + return new ExtendedMap<>(this, backer); + }; + + /** + * Static method to create a basic instance of IMap. + * + * @param The key type of the map. + * @param The value type of the map. + * + * @param args A series of key-value pairs. You will get an error if you don't + * provide the correct number of arguments (a number divisible by 2); + * however, if you pass arguments of the wrong type, you will not + * get a compile error, and usually won't get a runtime error in + * construction. However, you will get a ClassCastException as soon + * as you do something that attempts to iterate over the keys or values + * of the map. + * + * @return A map, constructed from the provided values. + * + * @throws IllegalArgumentException If you provide an incomplete pair of arguments. + */ + @SuppressWarnings("unchecked") + static MapEx of(Object... args) { + if (args.length % 2 != 0) throw new IllegalArgumentException("Args must be in the form of key-value pairs"); + + MapEx map = new FunctionalMap<>(); + for (int index = 0; index < args.length; index += 2) { + KeyType2 key = (KeyType2) args[index]; + ValueType2 value = (ValueType2) args[index + 1]; + + map.put(key, value); + } + + return map; + } +} diff --git a/src/main/java/bjc/funcdata/ObjectFrozen.java b/src/main/java/bjc/funcdata/ObjectFrozen.java index 2260a0e..a9f58b8 100644 --- a/src/main/java/bjc/funcdata/ObjectFrozen.java +++ b/src/main/java/bjc/funcdata/ObjectFrozen.java @@ -1,7 +1,7 @@ package bjc.funcdata; /** - * Exception that implementations of {@link IFreezable} can throw if you attempt + * Exception that implementations of {@link Freezable} can throw if you attempt * to modify a frozen object. * * @author Ben Culkin diff --git a/src/main/java/bjc/funcdata/TransformedValueMap.java b/src/main/java/bjc/funcdata/TransformedValueMap.java index 1e0ef51..643f610 100644 --- a/src/main/java/bjc/funcdata/TransformedValueMap.java +++ b/src/main/java/bjc/funcdata/TransformedValueMap.java @@ -19,9 +19,9 @@ import java.util.function.*; * */ final class TransformedValueMap - implements IMap { + implements MapEx { /* Our backing map. */ - private final IMap backing; + private final MapEx backing; /* Our transforming function. */ private final Function transformer; @@ -37,7 +37,7 @@ final class TransformedValueMap * @param transform * The function to use for the transform. */ - public TransformedValueMap(final IMap backingMap, + public TransformedValueMap(final MapEx backingMap, final Function transform) { backing = backingMap; transformer = transform; @@ -73,7 +73,7 @@ final class TransformedValueMap } @Override - public IList keyList() { + public ListEx keyList() { return backing.keyList(); } diff --git a/src/main/java/bjc/funcdata/bst/BinarySearchTree.java b/src/main/java/bjc/funcdata/bst/BinarySearchTree.java index 2c5b4d8..99b67cd 100644 --- a/src/main/java/bjc/funcdata/bst/BinarySearchTree.java +++ b/src/main/java/bjc/funcdata/bst/BinarySearchTree.java @@ -6,7 +6,7 @@ import java.util.List; import java.util.function.Predicate; import bjc.funcdata.FunctionalList; -import bjc.funcdata.IList; +import bjc.funcdata.ListEx; /** * A binary search tree, with some mild support for functional traversal. @@ -24,7 +24,7 @@ public class BinarySearchTree { private int elementCount; /* The root element of the tree */ - private ITreePart root; + private TreePart root; /** * Create a new tree using the specified way to compare elements. @@ -66,7 +66,7 @@ public class BinarySearchTree { * * @return Whether the adjusted pivot is with the list. */ - private boolean adjustedPivotInBounds(final IList elements, final int pivot, + private boolean adjustedPivotInBounds(final ListEx elements, final int pivot, final int pivotAdjustment) { return ((pivot - pivotAdjustment) >= 0) && ((pivot + pivotAdjustment) < elements.getSize()); @@ -78,7 +78,7 @@ public class BinarySearchTree { * Takes O(N) time, but also O(N) space. */ public void balance() { - final IList elements = new FunctionalList<>(); + final ListEx elements = new FunctionalList<>(); /* Add each element to the list in sorted order. */ root.forEach(TreeLinearizationMethod.INORDER, element -> elements.add(element)); @@ -135,7 +135,7 @@ public class BinarySearchTree { * * @return The root of the tree. */ - public ITreePart getRoot() { + public TreePart getRoot() { return root; } diff --git a/src/main/java/bjc/funcdata/bst/BinarySearchTreeLeaf.java b/src/main/java/bjc/funcdata/bst/BinarySearchTreeLeaf.java index 0b99cad..9532555 100644 --- a/src/main/java/bjc/funcdata/bst/BinarySearchTreeLeaf.java +++ b/src/main/java/bjc/funcdata/bst/BinarySearchTreeLeaf.java @@ -13,7 +13,7 @@ import java.util.function.Predicate; * @param * The data stored in the tree. */ -public class BinarySearchTreeLeaf implements ITreePart { +public class BinarySearchTreeLeaf implements TreePart { /** The data held in this tree leaf */ protected T data; diff --git a/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java b/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java index a73f81a..0eef92a 100644 --- a/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java +++ b/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java @@ -20,10 +20,10 @@ import java.util.function.Predicate; */ public class BinarySearchTreeNode extends BinarySearchTreeLeaf { /* The left child of this node */ - private ITreePart left; + private TreePart left; /* The right child of this node */ - private ITreePart right; + private TreePart right; /** * Create a new node with the specified data and children. @@ -37,8 +37,8 @@ public class BinarySearchTreeNode extends BinarySearchTreeLeaf { * @param rght * The right child of this node. */ - public BinarySearchTreeNode(final T element, final ITreePart lft, - final ITreePart rght) { + public BinarySearchTreeNode(final T element, final TreePart lft, + final TreePart rght) { super(element); this.left = lft; this.right = rght; diff --git a/src/main/java/bjc/funcdata/bst/ITreePart.java b/src/main/java/bjc/funcdata/bst/ITreePart.java deleted file mode 100644 index bac640d..0000000 --- a/src/main/java/bjc/funcdata/bst/ITreePart.java +++ /dev/null @@ -1,107 +0,0 @@ -package bjc.funcdata.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 { - /** - * Add a element below this tree part somewhere. - * - * @param element - * The element to add below this tree part - * - * @param comparator - * The thing to use for comparing values to find where to - * insert the tree part. - */ - public void add(T element, Comparator comparator); - - /** - * Collapses this tree part into a single value. - * - * Does not change the underlying tree. - * - * @param - * The type of the final collapsed value - * - * @param nodeCollapser - * The function to use to transform data into mapped - * form. - * - * @param branchCollapser - * The function to use to collapse data in mapped form - * into a single value. - * - * @return A single value from collapsing the tree. - */ - public E collapse(Function nodeCollapser, - BiFunction branchCollapser); - - /** - * Check if this tre part or below it contains the specified data item. - * - * @param element - * The data item to look for. - * - * @param comparator - * 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. - */ - public boolean contains(T element, Comparator comparator); - - /** - * Get the data associated with this tree part. - * - * @return The data associated with this tree part. - */ - public T data(); - - /** - * Remove the given node from this tree part and any of its children. - * - * @param element - * The data item to remove. - * - * @param comparator - * The comparator to use to search for the data item. - */ - public void delete(T element, Comparator comparator); - - /** - * Execute a directed walk through the tree. - * - * @param walker - * The function to use to direct the walk through the tree. - * - * @return Whether the directed walk finished successfully. - */ - public boolean directedWalk(DirectedWalkFunction walker); - - /** - * Execute a provided function for each element of tree it succesfully completes - * for. - * - * @param linearizationMethod - * The way to linearize the tree for executing. - * - * @param predicate - * The predicate to apply to each element, where it - * returning false terminates traversal early. - * - * @return Whether the traversal finished succesfully. - */ - public boolean forEach(TreeLinearizationMethod linearizationMethod, - Predicate predicate); -} diff --git a/src/main/java/bjc/funcdata/bst/TreePart.java b/src/main/java/bjc/funcdata/bst/TreePart.java new file mode 100644 index 0000000..b451463 --- /dev/null +++ b/src/main/java/bjc/funcdata/bst/TreePart.java @@ -0,0 +1,107 @@ +package bjc.funcdata.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 TreePart { + /** + * Add a element below this tree part somewhere. + * + * @param element + * The element to add below this tree part + * + * @param comparator + * The thing to use for comparing values to find where to + * insert the tree part. + */ + public void add(T element, Comparator comparator); + + /** + * Collapses this tree part into a single value. + * + * Does not change the underlying tree. + * + * @param + * The type of the final collapsed value + * + * @param nodeCollapser + * The function to use to transform data into mapped + * form. + * + * @param branchCollapser + * The function to use to collapse data in mapped form + * into a single value. + * + * @return A single value from collapsing the tree. + */ + public E collapse(Function nodeCollapser, + BiFunction branchCollapser); + + /** + * Check if this tre part or below it contains the specified data item. + * + * @param element + * The data item to look for. + * + * @param comparator + * 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. + */ + public boolean contains(T element, Comparator comparator); + + /** + * Get the data associated with this tree part. + * + * @return The data associated with this tree part. + */ + public T data(); + + /** + * Remove the given node from this tree part and any of its children. + * + * @param element + * The data item to remove. + * + * @param comparator + * The comparator to use to search for the data item. + */ + public void delete(T element, Comparator comparator); + + /** + * Execute a directed walk through the tree. + * + * @param walker + * The function to use to direct the walk through the tree. + * + * @return Whether the directed walk finished successfully. + */ + public boolean directedWalk(DirectedWalkFunction walker); + + /** + * Execute a provided function for each element of tree it succesfully completes + * for. + * + * @param linearizationMethod + * The way to linearize the tree for executing. + * + * @param predicate + * The predicate to apply to each element, where it + * returning false terminates traversal early. + * + * @return Whether the traversal finished succesfully. + */ + public boolean forEach(TreeLinearizationMethod linearizationMethod, + Predicate predicate); +} diff --git a/src/main/java/bjc/functypes/Combinators.java b/src/main/java/bjc/functypes/Combinators.java index 5632b70..bf63e47 100644 --- a/src/main/java/bjc/functypes/Combinators.java +++ b/src/main/java/bjc/functypes/Combinators.java @@ -193,10 +193,10 @@ public class Combinators { * functions. */ public static - Function> + Function> concat(Function funcA, Function funcB) { - return (arg) -> IPair.pair(funcA.apply(arg), funcB.apply(arg)); + return (arg) -> Pair.pair(funcA.apply(arg), funcB.apply(arg)); } /** diff --git a/src/main/java/bjc/functypes/Fixpoints.java b/src/main/java/bjc/functypes/Fixpoints.java index f62969c..6d5a250 100644 --- a/src/main/java/bjc/functypes/Fixpoints.java +++ b/src/main/java/bjc/functypes/Fixpoints.java @@ -24,7 +24,7 @@ public interface Fixpoints { */ static Function fix( BiFunction, ReturnType> func) { - IHolder> inner = IHolder.of(null); + Holder> inner = Holder.of(null); inner.replace((arg) -> { return func.apply(arg, inner.getValue()); }); @@ -45,7 +45,7 @@ public interface Fixpoints { BiFunction, ReturnType> func) { Map memoMap = new HashMap<>(); - IHolder> inner = IHolder.of(null); + Holder> inner = Holder.of(null); inner.replace((arg) -> memoMap.computeIfAbsent( arg, diff --git a/src/main/java/bjc/functypes/ListFlattener.java b/src/main/java/bjc/functypes/ListFlattener.java index 3768b84..91abe9d 100644 --- a/src/main/java/bjc/functypes/ListFlattener.java +++ b/src/main/java/bjc/functypes/ListFlattener.java @@ -2,7 +2,7 @@ package bjc.functypes; import java.util.function.Function; -import bjc.funcdata.IList; +import bjc.funcdata.ListEx; /** * A function that flattens a list. @@ -12,7 +12,7 @@ import bjc.funcdata.IList; * @param * The type of value in the list. */ -public interface ListFlattener extends Function, S> { +public interface ListFlattener extends Function, S> { /* * Alias */ diff --git a/src/test/java/bjc/funcdata/TestMapCreation.java b/src/test/java/bjc/funcdata/TestMapCreation.java index 6986afb..20dbe35 100644 --- a/src/test/java/bjc/funcdata/TestMapCreation.java +++ b/src/test/java/bjc/funcdata/TestMapCreation.java @@ -8,7 +8,7 @@ import org.junit.*; public class TestMapCreation { @Test public void mapOfNothingCreatesEmptyMap() { - IMap map = IMap.of(); + MapEx map = MapEx.of(); assertEquals("Map is empty", 0, map.size()); } @@ -16,12 +16,12 @@ public class TestMapCreation { @Test(expected = IllegalArgumentException.class) public void mapOfMismatchedCountErrors() { @SuppressWarnings("unused") - IMap map = IMap.of("thing1"); + MapEx map = MapEx.of("thing1"); } @Test(expected = ClassCastException.class) public void mapOfMismatchedTypeErrors() { - IMap map = IMap.of(1, 1.0); + MapEx map = MapEx.of(1, 1.0); map.forEach((key, val) -> { // An exception will be thrown here @@ -30,7 +30,7 @@ public class TestMapCreation { @Test public void mapOfCreatesWithGivenContents() { - IMap map = IMap.of("a", "A", "b", "B"); + MapEx map = MapEx.of("a", "A", "b", "B"); assertTrue("Constructed map contains key 'a'", map.containsKey("a")); assertEquals("Constructed map has key 'a' mapped to value 'A'", "A", map.get("a")); diff --git a/src/test/java/bjc/funcdata/TestMapOperations.java b/src/test/java/bjc/funcdata/TestMapOperations.java index 2db31cb..d982b5e 100644 --- a/src/test/java/bjc/funcdata/TestMapOperations.java +++ b/src/test/java/bjc/funcdata/TestMapOperations.java @@ -8,11 +8,11 @@ import org.junit.*; @SuppressWarnings("javadoc") public class TestMapOperations { - private IMap map; + private MapEx map; @Before public void setUp() throws Exception { - map = IMap.of("a", "A", "b", "B"); + map = MapEx.of("a", "A", "b", "B"); } @Test -- cgit v1.2.3