Implemented partitioning capabilities for lists

2 files changed, 154 insertions, 0 deletions

diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java
index d2f0988..72c5843 100644
--- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java
+++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java
@@ -1,3 +1,4 @@
+
 package bjc.utils.funcdata;
 
 import java.util.ArrayList;
@@ -434,4 +435,29 @@ public class FunctionalList<E> implements Cloneable {
 	public int getSize() {
 		return wrap.size();
 	}
+
+	/**
+	 * Partition this list into a list of sublists
+	 * 
+	 * @param nPerPart
+	 *            The size of elements to put into each one of the sublists
+	 * @return A list partitioned into partitions of size nPerPart
+	 */
+	public FunctionalList<FunctionalList<E>> partition(int nPerPart) {
+		FunctionalList<FunctionalList<E>> ret = new FunctionalList<>();
+
+		GenHolder<FunctionalList<E>> currPart = new GenHolder<>(
+				new FunctionalList<>());
+
+		this.forEach((val) -> {
+			if (currPart.unwrap((vl) -> vl.getSize() >= nPerPart)) {
+				ret.add(currPart.unwrap((vl) -> vl));
+				currPart.transform((vl) -> new FunctionalList<>());
+			} else {
+				currPart.unwrap((vl) -> vl.add(val));
+			}
+		});
+
+		return ret;
+	}
 }
diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcutils/ListUtils.java b/BJC-Utils2/src/main/java/bjc/utils/funcutils/ListUtils.java
new file mode 100644
index 0000000..1bc9a97
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/funcutils/ListUtils.java
@@ -0,0 +1,128 @@
+package bjc.utils.funcutils;
+
+import java.util.function.Consumer;
+import java.util.function.Function;
+
+import bjc.utils.data.GenHolder;
+import bjc.utils.funcdata.FunctionalList;
+
+/**
+ * Utilities for manipulating FunctionalLists that don't belong in the
+ * class itself
+ * 
+ * @author ben
+ *
+ */
+public class ListUtils {
+	private static final int MAX_NTRIESPART = 50;
+
+	/**
+	 * Implements a single group partitioning pass on a list
+	 * 
+	 * @author ben
+	 *
+	 * @param <E>
+	 *            The type of element in the list being partitioned
+	 */
+	private static final class GroupPartIteration<E>
+			implements Consumer<E> {
+		private FunctionalList<FunctionalList<E>>	ret;
+		private GenHolder<FunctionalList<E>>		currPart;
+		private FunctionalList<E>					rejects;
+		private GenHolder<Integer>					numInCurrPart;
+		private int									nPerPart;
+		private Function<E, Integer>				eleCount;
+
+		public GroupPartIteration(FunctionalList<FunctionalList<E>> ret,
+				GenHolder<FunctionalList<E>> currPart,
+				FunctionalList<E> rejects,
+				GenHolder<Integer> numInCurrPart, int nPerPart,
+				Function<E, Integer> eleCount) {
+			this.ret = ret;
+			this.currPart = currPart;
+			this.rejects = rejects;
+			this.numInCurrPart = numInCurrPart;
+			this.nPerPart = nPerPart;
+			this.eleCount = eleCount;
+		}
+
+		@Override
+		public void accept(E val) {
+			if (numInCurrPart.unwrap((vl) -> vl >= nPerPart)) {
+				ret.add(currPart.unwrap((vl) -> vl));
+
+				currPart.transform((vl) -> new FunctionalList<>());
+				numInCurrPart.transform((vl) -> 0);
+			} else {
+				int vCount = eleCount.apply(val);
+
+				if (numInCurrPart
+						.unwrap((vl) -> (vl + vCount) >= nPerPart)) {
+					rejects.add(val);
+				} else {
+					currPart.unwrap((vl) -> vl.add(val));
+					numInCurrPart.transform((vl) -> vl + vCount);
+				}
+			}
+		}
+	}
+
+	/**
+	 * Partition a list into a list of lists, where each element can count
+	 * for more than one element in a partition
+	 * 
+	 * @param list
+	 *            The list to partition
+	 * @param eleCount
+	 *            The function to determine the count for each element for
+	 * @param nPerPart
+	 *            The number of elements to put in each partition
+	 * @return A list partitioned according to the above rules
+	 */
+	public static <E> FunctionalList<FunctionalList<E>> groupPartition(
+			FunctionalList<E> list, Function<E, Integer> eleCount,
+			int nPerPart) {
+		/*
+		 * List that holds our results
+		 */
+		FunctionalList<FunctionalList<E>> ret = new FunctionalList<>();
+
+		/*
+		 * List that holds current partition
+		 */
+		GenHolder<FunctionalList<E>> currPart = new GenHolder<>(
+				new FunctionalList<>());
+		/*
+		 * List that holds elements rejected during current pass
+		 */
+		FunctionalList<E> rejects = new FunctionalList<>();
+
+		/*
+		 * The effective number of elements in the current partitition
+		 */
+		GenHolder<Integer> numInCurrPart = new GenHolder<>(0);
+
+		/*
+		 * Run up to a certain number of passes
+		 */
+		for (int nIterations = 0; nIterations < MAX_NTRIESPART
+				&& !rejects.isEmpty(); nIterations++) {
+			list.forEach(new GroupPartIteration<E>(ret, currPart, rejects,
+					numInCurrPart, nPerPart, eleCount));
+
+			if (rejects.isEmpty()) {
+				// Nothing was rejected, so we're done
+				return ret;
+			}
+		}
+
+		throw new IllegalArgumentException("Heuristic (more than "
+				+ MAX_NTRIESPART
+				+ " iterations of partitioning) detected unpartitionable list "
+				+ list.toString()
+				+ "\nThe following elements were not partitioned: "
+				+ rejects.toString() + "\nCurrent group in formation: "
+				+ currPart.unwrap((vl) -> vl.toString())
+				+ "\nPreviously formed groups: " + ret.toString());
+	}
+}