Add some interesting new things

Adds a number of things based off of some of the notes I've made over
time, plus a few papers I've read.

More details to come later, whenever I decide to actually get serious
about documentation and examples and the like

8 files changed, 698 insertions, 107 deletions

diff --git a/base/src/main/java/bjc/utils/graph/ASGraph.java b/base/src/main/java/bjc/utils/graph/ASGraph.java
new file mode 100644
index 0000000..777598f
--- /dev/null
+++ b/base/src/main/java/bjc/utils/graph/ASGraph.java
@@ -0,0 +1,179 @@
+package bjc.utils.graph;
+
+import java.util.*;
+import java.util.function.Function;
+
+import bjc.data.Pair;
+import bjc.esodata.*;
+import bjc.funcdata.Freezable;
+import bjc.funcdata.ObjectFrozen;
+import bjc.functypes.Unit;
+
+public class ASGraph<Node, Value, Label> implements Freezable<ASGraph<Node, Value, Label>> {
+	private Set<Node> nodes;
+	private Function<Node, Value> nodeValuer;
+	private PairMap<Node, Node, Label> arcMap;
+
+	// Used for implementation efficiency
+	private Multimap<Node, Value> nodeToValue;
+	private Multimap<Value, Node> valueToNode;
+
+	private boolean frozen;
+	private boolean deepFrozen;
+
+	public ASGraph(Function<Node, Value> valuer) {
+		this.nodes = new HashSet<>();
+		this.nodeValuer = valuer;
+		this.arcMap = new PairMap<>();
+
+		this.nodeToValue = new TSetMultimap<>();
+		this.valueToNode = new TSetMultimap<>();
+	}
+
+	/**
+	 * Retrieve a read-only view of the nodes
+	 * 
+	 * @return A read-only set of the nodes.
+	 */
+	public Set<Node> getNodes() {
+		return Collections.unmodifiableSet(nodes);
+	}
+
+	/**
+	 * Get the value for a node in the graph.
+	 * 
+	 * @param nd The node to check.
+	 * 
+	 * @return The value for that node.
+	 */
+	public Value getValue(Node nd) {
+		return nodeValuer.apply(nd);
+	}
+
+	/**
+	 * Add a node to the graph.
+	 * 
+	 * @param nd The node to add.
+	 */
+	public void addNode(Node nd) {
+		if (deepFrozen)
+			throw new ObjectFrozen();
+
+		this.nodes.add(nd);
+
+		Value v = nodeValuer.apply(nd);
+		this.nodeToValue.add(nd, v);
+		this.valueToNode.add(v, nd);
+	}
+
+	/**
+	 * Remove a node from the graph.
+	 * 
+	 * @param nd The node to remove
+	 */
+	public void removeNode(Node nd) {
+		if (deepFrozen)
+			throw new ObjectFrozen();
+		this.nodes.remove(nd);
+
+		Value v = nodeValuer.apply(nd);
+		this.nodeToValue.remove(nd);
+		this.valueToNode.remove(v, nd);
+	}
+
+	/**
+	 * Add an arc to the graph.
+	 * 
+	 * Note that badness can happen if you add a arc that refers to nodes not in the
+	 * graph.
+	 * 
+	 * @param nd1 The source node for the arc.
+	 * @param nd2 The destination node for the arc.
+	 * @param lab The label for the arc.
+	 */
+	public void addArc(Node nd1, Node nd2, Label lab) {
+		if (deepFrozen)
+			throw new ObjectFrozen();
+		arcMap.put(Pair.pair(nd1, nd2), lab);
+	}
+
+	/**
+	 * Remove an arc from the graph.
+	 * 
+	 * @param nd1 The source node for the arc.
+	 * @param nd2 The destination node for the arc.
+	 * @param lab The label for the arc.
+	 */
+	public void removeArc(Node nd1, Node nd2, Label lab) {
+		if (deepFrozen)
+			throw new ObjectFrozen();
+		arcMap.remove(Pair.pair(nd1, nd2), lab);
+	}
+
+	/**
+	 * Check if this graph is partitioned by the given graphs.
+	 * 
+	 * <ol>
+	 * <li>Every node in nodes is contained in exactly one partition</li>
+	 * <li>For every node in nodes, the value the partition assigns it is equal to
+	 * the value from nodeValuer</li>
+	 * <li>Every arc in a partition is also in arcMap</li>
+	 * </ol>
+	 * 
+	 * @param partitions The graphs to check partitioning for.
+	 * 
+	 * @return Whether this graph is partitioned by the given nodes.
+	 */
+	public boolean partitionedBy(@SuppressWarnings("unchecked") ASGraph<Node, Value, Label>... partitions) {
+		// TODO: Implement me
+		return false;
+	}
+
+	/**
+	 * Create a graph representing a given string
+	 * 
+	 * Note that because of the way the value function is implemented, modifying the
+	 * graph will not work well.
+	 * 
+	 * @param strang The string to represent.
+	 * 
+	 * @return The graph representing the string.
+	 */
+	public static ASGraph<Integer, Character, Unit> fromString(String strang) {
+		ASGraph<Integer, Character, Unit> ret = new ASGraph<>(strang::charAt);
+
+		for (int i = 0; i < strang.length(); i++) {
+			ret.addNode(i);
+			if (i != 0)
+				ret.addArc(i - 1, i, Unit.UNIT);
+		}
+
+		return ret;
+	}
+
+	@Override
+	public boolean freeze() {
+		frozen = true;
+		return true;
+	}
+
+	@Override
+	public boolean thaw() {
+		if (deepFrozen)
+			return false;
+
+		return false;
+	}
+
+	@Override
+	public boolean deepFreeze() {
+		deepFrozen = true;
+		frozen = true;
+		return true;
+	}
+
+	@Override
+	public boolean isFrozen() {
+		return frozen;
+	}
+}
diff --git a/base/src/main/java/bjc/utils/graph/ASGraphGrammar.java b/base/src/main/java/bjc/utils/graph/ASGraphGrammar.java
new file mode 100644
index 0000000..847107d
--- /dev/null
+++ b/base/src/main/java/bjc/utils/graph/ASGraphGrammar.java
@@ -0,0 +1,30 @@
+package bjc.utils.graph;
+
+import java.util.Set;
+
+import bjc.data.Either;
+
+// See https://web.archive.org/web/20190414072011/https://core.ac.uk/download/pdf/82129679.pdf
+public class ASGraphGrammar<NonTerminal, Terminal, Label> {
+	public class Rule<Node> {
+		private ASGraph<Node, NonTerminal, ?> starting;
+		
+		// Must contain at least one node
+		private ASGraph<Node, Either<NonTerminal, Terminal>, Label> production;
+		
+		// Start node and end node must be in production
+		private Either<NonTerminal, Terminal> startNode;
+		private Either<NonTerminal, Terminal> endNode;
+		
+		public void derive(ASGraph<Node, Either<NonTerminal, Terminal>, Label> graph) {
+			// The derivation of H from G according to the rule A -> K(I/O) consists simply of replacing
+			// a node N' in G whose value is A by the graph K. Arcs leading into N' are replaced by
+			// arcs leading to I, arcs exiting from B' are replaced by arcs exiting from O, and any
+			// loop arcs on N' are replaced by arcs from O to I. 
+
+		}
+	}
+
+	// int is perhaps not the best node type, but it works
+	private Set<Rule<Integer>> rules;
+}
diff --git a/base/src/main/java/bjc/utils/graph/AlgGraph.java b/base/src/main/java/bjc/utils/graph/AlgGraph.java
new file mode 100644
index 0000000..7c9d38d
--- /dev/null
+++ b/base/src/main/java/bjc/utils/graph/AlgGraph.java
@@ -0,0 +1,88 @@
+package bjc.utils.graph;
+
+import bjc.functypes.Container;
+
+/**
+ * A directed algebraic graph
+ * 
+ * (ref. Algebraic Graphs with Class, Andrey Mokhov}
+ * 
+ * @author bjcul
+ *
+ * @param <Vertex> The type of the vertexes
+ * @param <PGraph> Containing type parameter
+ */
+public interface AlgGraph<Vertex, PGraph extends AlgGraph<?, PGraph>> extends Container<Vertex, AlgGraph<?, PGraph>> {
+	/**
+	 * Create a empty algebraic graph.
+	 * 
+	 * @param <B> The type of the vertices
+	 * 
+	 * @return A new empty graph.
+	 */
+	<B> AlgGraph<B, PGraph> empty();
+	
+	/**
+	 * Create a algebraic graph with a single vertex
+	 * 
+	 * @param val The value for the vertex
+	 * 
+	 * @return A new graph with the given vertex
+	 */
+	<B> AlgGraph<B, PGraph> vertex(B val);
+	
+	/**
+	 * Overlay a graph onto this one, adding its vertices and edges.
+	 * 
+	 * @param other The graph to overlay
+	 */
+	void overlay(AlgGraph<Vertex, PGraph> other);
+
+	/**
+	 * Connect a graph to this one, adding its vertices and edges; as well as
+	 * establishing an edge from each node in this graph, to each node in the other
+	 * graph.
+	 * 
+	 * @param other The graph to connect
+	 */
+	void connect(AlgGraph<Vertex, PGraph> other);
+	
+	/**
+	 * Overlay two graphs into a new graph.
+	 * 
+	 * @param <Vertex> The type of the vertices.
+	 * 
+	 * @param left     The graph to overlay onto
+	 * @param right    The graph being overlaid
+	 * 
+	 * @return The overlaid graph.
+	 */
+	public static <Vertex, G extends AlgGraph<Vertex, G>> G overlay(G left, G right) {
+		@SuppressWarnings("unchecked")
+		// We know this cast is good, java just can't tell
+		G result = (G) left.empty();
+		result.overlay(left);
+		result.overlay(right);
+
+		return result;
+	}
+
+	/**
+	 * Connect two graphs into a new graph.
+	 * 
+	 * @param <Vertex> The type of the vertices.
+	 * 
+	 * @param left     The graph to connect to
+	 * @param right    The graph being connected
+	 * 
+	 * @return The connected graph.
+	 */
+	public static <Vertex, G extends AlgGraph<Vertex, G>> G connect(G left, G right) {
+		@SuppressWarnings("unchecked")
+		// We know this cast is good, java just can't tell
+		G result = (G) left.empty();
+		result.overlay(left);
+		result.connect(right);
+		return result;
+	}
+}
\ No newline at end of file
diff --git a/base/src/main/java/bjc/utils/graph/SimpleAlgGraph.java b/base/src/main/java/bjc/utils/graph/SimpleAlgGraph.java
new file mode 100644
index 0000000..2c7ba08
--- /dev/null
+++ b/base/src/main/java/bjc/utils/graph/SimpleAlgGraph.java
@@ -0,0 +1,83 @@
+package bjc.utils.graph;
+
+import java.util.*;
+
+/**
+ * A basic implementation of a directed algebraic graph.
+ * 
+ * @author bjcul
+ *
+ * @param <Vertex> The type of the vertices
+ */
+public class SimpleAlgGraph<Vertex> implements AlgGraph<Vertex, SimpleAlgGraph<?>> {
+	// TODO: consider if some function for labeling edges would make sense
+	private Set<Vertex> vertices;
+	private Map<Vertex, Vertex> edges;
+
+	/**
+	 * Create a new empty graph.
+	 */
+	public SimpleAlgGraph() {
+		vertices = new HashSet<>();
+		edges = new HashMap<>();
+	}
+
+	/**
+	 * Create a new graph with the given vertices, but no edges.
+	 * 
+	 * @param vertexes The vertices for the graph.
+	 */
+	@SafeVarargs
+	public SimpleAlgGraph(Vertex... vertexes) {
+		this();
+
+		for (Vertex vertex : vertexes)
+			vertices.add(vertex);
+	}
+
+	@Override
+	public <B> SimpleAlgGraph<B> empty() {
+		return new SimpleAlgGraph<>();
+	}
+	
+	@Override
+	public <B> SimpleAlgGraph<B> vertex(B val) {
+		return new SimpleAlgGraph<>();
+	}
+	
+	/**
+	 * Overlay a graph onto this one, adding its vertices and edges.
+	 * 
+	 * @param other The graph to overlay
+	 */
+	@Override
+	public void overlay(AlgGraph<Vertex, SimpleAlgGraph<?>> other) {
+		SimpleAlgGraph<Vertex> graph = (SimpleAlgGraph<Vertex>) other;
+		
+		vertices.addAll(graph.vertices);
+		edges.putAll(graph.edges);
+	}
+
+	/**
+	 * Connect a graph to this one, adding its vertices and edges; as well as
+	 * establishing an edge from each node in this graph, to each node in the other
+	 * graph.
+	 * 
+	 * @param other The graph to connect
+	 */
+	@Override
+	public void connect(AlgGraph<Vertex, SimpleAlgGraph<?>> other) {
+		SimpleAlgGraph<Vertex> graph = (SimpleAlgGraph<Vertex>) other;
+	
+		// note: this could be inefficent for large graphs
+		for (Vertex left : vertices) {
+			for (Vertex right : graph.vertices) {
+				edges.put(left, right);
+			}
+		}
+
+		overlay(other);
+	}
+
+
+}
\ No newline at end of file
diff --git a/base/src/main/java/bjc/utils/patterns/ComplexPattern.java b/base/src/main/java/bjc/utils/patterns/ComplexPattern.java
index 2d9fc71..69ee67c 100644
--- a/base/src/main/java/bjc/utils/patterns/ComplexPattern.java
+++ b/base/src/main/java/bjc/utils/patterns/ComplexPattern.java
@@ -1,18 +1,21 @@
 package bjc.utils.patterns;
 
+import java.util.Optional;
 import java.util.function.*;
 import java.util.regex.*;
 
 import bjc.data.*;
+import bjc.functypes.ID;
+import bjc.functypes.Unit;
 
 /**
  * A pattern that can be matched against.
  * 
  * @author Ben Culkin
  *
- * @param <InputType> The type of object being matched against.
+ * @param <InputType>  The type of object being matched against.
  * @param <ReturnType> The type returned by the pattern.
- * @param <PredType> The state type returned by the predicate.
+ * @param <PredType>   The state type returned by the predicate.
  */
 public interface ComplexPattern<ReturnType, PredType, InputType> {
 	/**
@@ -20,11 +23,11 @@ public interface ComplexPattern<ReturnType, PredType, InputType> {
 	 * 
 	 * @param input The object to check against this pattern.
 	 * 
-	 * @return Whether or not this pattern is matched, as well as a state value
-	 *         that will get passed to the pattern if it did match.
+	 * @return Whether or not this pattern is matched, as well as a state value that
+	 *         will get passed to the pattern if it did match.
 	 */
 	Pair<Boolean, PredType> matches(InputType input);
-	
+
 	/**
 	 * Apply this pattern, once it has matched.
 	 * 
@@ -34,9 +37,9 @@ public interface ComplexPattern<ReturnType, PredType, InputType> {
 	 * @return The result of applying this pattern.
 	 */
 	ReturnType apply(InputType input, PredType state);
-	
+
 	/* Pattern producing functions */
-	
+
 	/**
 	 * Create a pattern composed from a predicate &amp; a function.
 	 * 
@@ -44,153 +47,125 @@ public interface ComplexPattern<ReturnType, PredType, InputType> {
 	 * @param <PreType> The type used as intermediate state.
 	 * @param <InpType> The type initially matched against.
 	 * 
-	 * @param matcher The predicate that says what this pattern matches.
-	 * @param accepter The action that happens when this pattern matches.
+	 * @param matcher   The predicate that says what this pattern matches.
+	 * @param accepter  The action that happens when this pattern matches.
 	 * 
 	 * @return A pattern composed from the passed in functions.
 	 */
 	static <RetType, PreType, InpType> ComplexPattern<RetType, PreType, InpType> from(
-			Function<InpType, Pair<Boolean, PreType>> matcher,
-			BiFunction<InpType, PreType, RetType> accepter)
-	{
+			Function<InpType, Pair<Boolean, PreType>> matcher, BiFunction<InpType, PreType, RetType> accepter) {
 		return new FunctionalPattern<>(matcher, accepter);
 	}
-	
+
 	/**
-	 * Create a pattern which checks if an object is of a given type (or a subtype of it).
+	 * Create a pattern which checks if an object is of a given type (or a subtype
+	 * of it).
 	 * 
 	 * @param <ClassType> The type to check if the object is an instance of.
-	 * @param <RetType> The type returned by the action.
-	 * @param <InpType> The type of the thing to match.
+	 * @param <RetType>   The type returned by the action.
+	 * @param <InpType>   The type of the thing to match.
 	 * 
-	 * @param clasz The Class instance for the type you want to check.
-	 * @param action The action to execute if the pattern does match.
+	 * @param clasz       The Class instance for the type you want to check.
+	 * @param action      The action to execute if the pattern does match.
 	 * 
 	 * @return A pattern which follows the specified condition.
 	 */
 	@SuppressWarnings("unchecked")
-	static <ClassType, RetType, InpType> ComplexPattern<RetType, ?, InpType> ofClass(
-			Class<ClassType> clasz,
-			Function<ClassType, RetType> action) 
-	{
-		return from(
-				(input)          -> Pair.pair(clasz.isInstance(input), null),
-				(input, ignored) -> action.apply((ClassType)input)
-		);
-	}
-	
+	static <ClassType, RetType, InpType> ComplexPattern<RetType, Unit, InpType> ofClass(Class<ClassType> clasz,
+			Function<ClassType, RetType> action) {
+		return from((input) -> Pair.pair(clasz.isInstance(input), null),
+				(input, ignored) -> action.apply((ClassType) input));
+	}
+
 	/**
 	 * Creates a pattern which matches a given object.
 	 * 
 	 * @param <RetType> The type returned when the pattern matches.
 	 * @param <InpType> The type of the thing to match.
 	 * 
-	 * @param obj The object being tested for equality.
-	 * @param action The action to execute when the object matches.
+	 * @param obj       The object being tested for equality.
+	 * @param action    The action to execute when the object matches.
 	 * 
 	 * @return A pattern which tests against the equality of an object.
 	 */
-	static <RetType, InpType> ComplexPattern<RetType, ?, InpType> matchesObject(
-			InpType obj,
-			Function<InpType, RetType> action
-			) 
-	{
-		return from(
-				(input)          -> Pair.pair(obj.equals(input), null),
-				(input, ignored) -> action.apply(input)
-		);
-	}
-	
+	static <RetType, InpType> ComplexPattern<RetType, Unit, InpType> matchesObject(InpType obj,
+			Function<InpType, RetType> action) {
+		return from((input) -> Pair.pair(obj.equals(input), null), (input, ignored) -> action.apply(input));
+	}
+
 	/**
 	 * Tests if the toString rendition of an object matches a given condition.
 	 * 
 	 * @param <RetType> The type returned by the pattern.
 	 * @param <InpType> The type of the thing to match.
 	 * 
-	 * @param pattern The string to check against.
-	 * @param action The action to check when the toString of the object matches
-	 *               the provided string. This is passed both the object, and its
-	 *               string form (in the event that you don't want to call toString
-	 *               multiple times, for whatever reason)
-	 *               
-	 * @return A pattern which tests against the toString representation of an object.
+	 * @param pattern   The string to check against.
+	 * @param action    The action to check when the toString of the object matches
+	 *                  the provided string. This is passed both the object, and its
+	 *                  string form (in the event that you don't want to call
+	 *                  toString multiple times, for whatever reason)
+	 * 
+	 * @return A pattern which tests against the toString representation of an
+	 *         object.
 	 */
-	static <RetType, InpType> ComplexPattern<RetType, ?, InpType> equalsString(
-			String pattern,
-			BiFunction<InpType, String, RetType> action
-			) 
-	{
+	static <RetType, InpType> ComplexPattern<RetType, String, InpType> equalsString(String pattern,
+			BiFunction<InpType, String, RetType> action) {
 		Function<InpType, Pair<Boolean, String>> matcher = (input) -> {
 			String objString = input.toString();
-			
+
 			return Pair.pair(pattern.equals(objString), objString);
 		};
-		
-		return from(
-				matcher,
-				(input, objString) -> action.apply(input, objString)
-		);
+
+		return from(matcher, (input, objString) -> action.apply(input, objString));
 	}
-	
+
 	/**
 	 * Check if the toString of a given object matches a regex.
 	 * 
 	 * @param <RetType> The type returned by the pattern.
-	 * @param <InpType> The type of object to match against. 
+	 * @param <InpType> The type of object to match against.
 	 * 
-	 * @param regex The regex to match against.
-	 * @param cond The predicate to use to determine if the regex matched.
-	 * @param action The action to call when the regex matched.
+	 * @param regex     The regex to match against.
+	 * @param cond      The predicate to use to determine if the regex matched.
+	 * @param action    The action to call when the regex matched.
 	 * 
 	 * @return A pattern which does the regex matching.
 	 */
-	static <RetType, InpType> ComplexPattern<RetType, Matcher, InpType> matchesRegex(
-		String regex,
-		Predicate<Matcher> cond,
-		BiFunction<InpType, Matcher, RetType> action
-	)
-	{
+	static <RetType, InpType> ComplexPattern<RetType, Matcher, InpType> matchesRegex(String regex,
+			Predicate<Matcher> cond, BiFunction<InpType, Matcher, RetType> action) {
 		java.util.regex.Pattern regexPat = java.util.regex.Pattern.compile(regex);
 
 		Function<InpType, Pair<Boolean, Matcher>> matcher = (input) -> {
 			String inpString = input.toString();
-		
+
 			Matcher mat = regexPat.matcher(inpString);
-			
-			if (cond.test(mat)) return Pair.pair(true, mat);
-			else                return Pair.pair(false, null);
+
+			if (cond.test(mat))
+				return Pair.pair(true, mat);
+			return Pair.pair(false, null);
 		};
-		
-		return from(
-				matcher,
-				(input, res) -> action.apply(input, res)
-		);
+
+		return from(matcher, (input, res) -> action.apply(input, res));
 	}
-	
+
 	// @TODO Nov 21, 2020 Ben Culkin :MorePatterns
 	// Try and write something to iterate over Iterator in a type-safe manner
 	// Also, something for doing a sub-pattern match
-	
+
 	/**
 	 * Create a pattern which will always execute.
 	 * 
 	 * @param <RetType> The type returned.
 	 * @param <InpType> The type being matched against.
 	 * 
-	 * @param action The action to execute.
+	 * @param action    The action to execute.
 	 * 
 	 * @return A pattern which will be executed.
 	 */
-	static <RetType, InpType> ComplexPattern<RetType, ?, InpType> otherwise(
-			Function<InpType, RetType> action
-			) 
-	{
-		return from(
-				(input)          -> Pair.pair(true, null),
-				(input, ignored) -> action.apply(input)
-		);
-	}
-	
+	static <RetType, InpType> ComplexPattern<RetType, Unit, InpType> otherwise(Function<InpType, RetType> action) {
+		return from((input) -> Pair.pair(true, null), (input, ignored) -> action.apply(input));
+	}
+
 	/**
 	 * Create a pattern which checks if the string form of a given object starts
 	 * with a specific string.
@@ -198,26 +173,184 @@ public interface ComplexPattern<ReturnType, PredType, InputType> {
 	 * @param <RetType> The type returned by the matcher.
 	 * @param <InpType> The type being matched against.
 	 * 
-	 * @param pattern The string to check against.
-	 * @param action The action to execute.
+	 * @param pattern   The string to check against.
+	 * @param action    The action to execute.
 	 * 
 	 * @return A pattern which functions as described.
 	 */
-	static <RetType, InpType> ComplexPattern<RetType, String, InpType> startsWith(
-			String pattern,
-			Function<String, RetType> action)
-	{
+	static <RetType, InpType> ComplexPattern<RetType, String, InpType> startsWith(String pattern,
+			Function<String, RetType> action) {
 		return from((input) -> {
 			String objString = input.toString();
-			
-			if (objString.startsWith(pattern)) {
-				return Pair.pair(
-						true,
-						objString.substring(
-							pattern.length()));
-			} else {
+
+			if (objString.startsWith(pattern))
+				return Pair.pair(true, objString.substring(pattern.length()));
+			return Pair.pair(false, null);
+		}, (input, state) -> action.apply(state));
+	}
+
+	// TODO: See about generalizing these to be able to take different return types
+	/**
+	 * Create a pattern which matches if any of its two components match.
+	 * 
+	 * @param <RetType>    The type each pattern returns
+	 * @param <InpType>    The input for each pattern.
+	 * @param <LeftState>  The first state type.
+	 * @param <RightState> The second state type.
+	 * 
+	 * @param left         The first pattern.
+	 * @param right        The second pattern.
+	 * 
+	 * @return A pattern which matches if either of its components do.
+	 */
+	static <RetType, InpType, LeftState, RightState> ComplexPattern<RetType, Either<LeftState, RightState>, InpType> or(
+			ComplexPattern<RetType, LeftState, InpType> left, ComplexPattern<RetType, RightState, InpType> right) {
+		// It would be convenient if we could just omit the two state types.
+		// However, java isn't smart enough to infer the right types without the help
+		Function<InpType, Pair<Boolean, Either<LeftState, RightState>>> matcher = (inp) -> {
+			Pair<Boolean, LeftState> leftRes = left.matches(inp);
+			if (leftRes.getLeft()) {
+				return Pair.pair(true, Either.left(leftRes.getRight()));
+			}
+
+			Pair<Boolean, RightState> rightRes = right.matches(inp);
+			if (rightRes.getLeft()) {
+				return Pair.pair(true, Either.right(rightRes.getRight()));
+			}
+			return Pair.pair(false, null);
+		};
+		return from(matcher, (input, state) -> state.isLeft() ? left.apply(input, state.forceLeft())
+				: right.apply(input, state.forceRight()));
+	}
+
+	/**
+	 * Create a pattern which matches if both component patterns do.
+	 * 
+	 * @param <RetType>    The type returned by the patterns
+	 * @param <InpType>    The input for the patterns
+	 * @param <LeftState>  The state for the right pattern
+	 * @param <RightState> The state for the left pattern
+	 * 
+	 * @param left         The left pattern
+	 * @param right        The right pattern
+	 * 
+	 * @return A pattern which matches if both of the given patterns do.
+	 */
+	static <RetType, InpType, LeftState,
+			RightState> ComplexPattern<Pair<RetType, RetType>, Pair<LeftState, RightState>, InpType> and(
+					ComplexPattern<RetType, LeftState, InpType> left,
+					ComplexPattern<RetType, RightState, InpType> right) {
+		Function<InpType, Pair<Boolean, Pair<LeftState, RightState>>> matcher = (inp) -> {
+			Pair<Boolean, LeftState> leftRes = left.matches(inp);
+			if (!leftRes.getLeft())
+				return Pair.pair(false, null);
+			Pair<Boolean, RightState> rightRes = right.matches(inp);
+			if (!rightRes.getLeft())
+				return Pair.pair(false, null);
+			return Pair.pair(true, Pair.pair(leftRes.getRight(), rightRes.getRight()));
+		};
+
+		return from(matcher, (input, state) -> {
+			return Pair.pair(left.apply(input, state.getLeft()), right.apply(input, state.getRight()));
+		});
+	}
+
+	static <RetType, InpType, Shared, State1,
+			State2> ComplexPattern<Either<Shared, RetType>, Either<Shared, Pair<Shared, State2>>, InpType> then(
+					ComplexPattern<Shared, State1, InpType> first, ComplexPattern<RetType, State2, Shared> second) {
+		Function<InpType, Pair<Boolean, Either<Shared, Pair<Shared, State2>>>> matcher = (inp) -> {
+			Pair<Boolean, State1> firstRes = first.matches(inp);
+			if (!firstRes.getLeft())
+				return Pair.pair(false, null);
+			Shared shared = first.apply(inp, firstRes.getRight());
+			Pair<Boolean, State2> secondRes = second.matches(shared);
+			if (!secondRes.getLeft())
+				return Pair.pair(true, Either.left(shared));
+			return Pair.pair(true, Either.right(Pair.pair(shared, secondRes.getRight())));
+		};
+
+		return from(matcher, (input, state) -> {
+			if (state.isLeft())
+				return state.newRight();
+			Pair<Shared, State2> right = state.forceRight();
+			return Either.right(second.apply(right.getLeft(), right.getRight()));
+		});
+	}
+
+	static <RetType, InpType, Shared, Other, State1,
+			State2> ComplexPattern<Either<Either<Shared, RetType>, Other>,
+					Either<Either<Shared, Pair<Shared, State2>>, Other>, InpType> maybeThen(
+							ComplexPattern<Either<Shared, Other>, State1, InpType> first,
+							ComplexPattern<RetType, State2, Shared> second) {
+		Function<InpType, Pair<Boolean, Either<Either<Shared, Pair<Shared, State2>>, Other>>> matcher = (inp) -> {
+			Pair<Boolean, State1> firstRes = first.matches(inp);
+			if (!firstRes.getLeft())
 				return Pair.pair(false, null);
+			Either<Shared, Other> maybeShared = first.apply(inp, firstRes.getRight());
+			if (!maybeShared.isLeft())
+				return Pair.pair(true, maybeShared.newLeft());
+			Shared shared = maybeShared.forceLeft();
+			Pair<Boolean, State2> secondRes = second.matches(shared);
+			if (!secondRes.getLeft())
+				return Pair.pair(true, Either.left(Either.left(shared)));
+			return Pair.pair(true, Either.left(Either.right(Pair.pair(shared, secondRes.getRight()))));
+		};
+
+		// Can't inline matcher, that breaks type-inference
+		return from(matcher, (input, state) -> {
+			if (!state.isLeft()) {
+				return state.newLeft();
+			}
+			Either<Shared, Pair<Shared, State2>> left = state.forceLeft();
+			if (left.isLeft()) {
+				return Either.left(left.newRight());
 			}
-		}, (ignored, input) -> action.apply(input));
+			Pair<Shared, State2> right = left.forceRight();
+			return Either.left(Either.right(second.apply(right.getLeft(), right.getRight())));
+		});
+	}
+
+	static <RetType, Shared1, Shared2, State, Input> ComplexPattern<RetType, State, Input> collapse(
+			ComplexPattern<Either<Shared1, Shared2>, State, Input> patt, Function<Shared1, RetType> f,
+			Function<Shared2, RetType> g) {
+		return patt.mapOutput(eth -> eth.extract(f, g));
+	}
+
+	static <Shared, State, Input> ComplexPattern<Shared, State, Input> collapse(
+			ComplexPattern<Either<Shared, Shared>, State, Input> patt) {
+		return patt.mapOutput(Either::collapse);
+	}
+
+	static <RetType, State,
+			Input> ComplexPattern<Optional<RetType>, ?, Input> maybe(ComplexPattern<RetType, State, Input> pat) {
+		return from((inp) -> {
+			Pair<Boolean, State> res = pat.matches(inp);
+			if (res.getLeft())
+				return Pair.pair(true, Either.left(res.getRight()));
+			return Pair.pair(true, Either.right(null));
+		}, (Input inp, Either<State, State> state) -> {
+			// Need to specify the type; inference isn't smart enough to guess the right
+			// thing
+			if (state.isLeft())
+				return Optional.of(pat.apply(inp, state.forceLeft()));
+			return Optional.empty();
+		});
+	}
+
+	default <NewInput> ComplexPattern<ReturnType, Pair<PredType, InputType>, NewInput> mapInput(
+			Function<NewInput, InputType> func) {
+		return from((inp) -> {
+			InputType procInput = func.apply(inp);
+			Pair<Boolean, PredType> res = matches(procInput);
+			return Pair.pair(res.getLeft(), Pair.pair(res.getRight(), procInput));
+		}, (input, state) -> apply(state.getRight(), state.getLeft()));
+	}
+
+	default <NewOutput> ComplexPattern<NewOutput, PredType, InputType> mapOutput(Function<ReturnType, NewOutput> func) {
+		return from(ComplexPattern.this::matches, (inp, state) -> func.apply(apply(inp, state)));
+	}
+
+	default ComplexPattern<Pair<ReturnType, PredType>, PredType, InputType> withState() {
+		return from(ComplexPattern.this::matches, (inp, state) -> Pair.pair(apply(inp, state), state));
 	}
-}
+}
\ No newline at end of file
diff --git a/base/src/main/java/bjc/utils/services/Bordello.java b/base/src/main/java/bjc/utils/services/Bordello.java
new file mode 100644
index 0000000..104c4ab
--- /dev/null
+++ b/base/src/main/java/bjc/utils/services/Bordello.java
@@ -0,0 +1,53 @@
+package bjc.utils.services;
+
+import java.util.Map;
+import java.util.concurrent.ConcurrentHashMap;
+
+/**
+ * A place to retrieve services from
+ * 
+ * @author bjcul
+ *
+ */
+public class Bordello {
+	private static final Map<Class<?>, Object> services = new ConcurrentHashMap<>();
+	
+	/**
+	 * Retrieve the implementation of a given service.
+	 * 
+	 * @param <T> The type of the service.
+	 * 
+	 * @param interfaceClass The class of the service.
+	 * 
+	 * @return The default implementation of the service.
+	 */
+	public static <T> T get(Class<T> interfaceClass) {
+		synchronized (interfaceClass) {
+			Object service = services.get(interfaceClass);
+			if (service == null) {
+				try {
+					Class<?> implementor = interfaceClass.getAnnotation(Implementor.class).value();
+					service = implementor.getDeclaredConstructor().newInstance();
+					services.put(interfaceClass, implementor);
+				} catch (Exception ex) {
+					throw new RuntimeException(ex);
+				}
+			}
+			return interfaceClass.cast(service);
+		}
+	}
+	
+	/**
+	 * Set an implementation for a given service to be something other than the default.
+	 * 
+	 * @param <T> The type of the service
+	 * 
+	 * @param interfaceClass The class of the service
+	 * @param implementor The alternate implementation for the service.
+	 */
+	public static <T> void set(Class<T> interfaceClass, T implementor) {
+		synchronized (interfaceClass) {
+			services.put(interfaceClass, implementor);
+		}
+	}
+}
diff --git a/base/src/main/java/bjc/utils/services/Implementor.java b/base/src/main/java/bjc/utils/services/Implementor.java
new file mode 100644
index 0000000..3dac860
--- /dev/null
+++ b/base/src/main/java/bjc/utils/services/Implementor.java
@@ -0,0 +1,24 @@
+package bjc.utils.services;
+
+import static java.lang.annotation.ElementType.TYPE;
+import static java.lang.annotation.RetentionPolicy.RUNTIME;
+
+import java.lang.annotation.*;
+
+/**
+ * Indicates the default implementation for a given service.
+ * 
+ * @author bjcul
+ *
+ */
+@Documented
+@Retention(RUNTIME)
+@Target(TYPE)
+public @interface Implementor {
+	/**
+	 * The default implementation for the service this annotates.
+	 * 
+	 * @return The default impl. for the service this annotates
+	 */
+	Class<?> value();
+}
diff --git a/base/src/main/java/bjc/utils/services/package-info.java b/base/src/main/java/bjc/utils/services/package-info.java
new file mode 100644
index 0000000..24f6855
--- /dev/null
+++ b/base/src/main/java/bjc/utils/services/package-info.java
@@ -0,0 +1 @@
+package bjc.utils.services;
\ No newline at end of file