You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hugegraph.apache.org by je...@apache.org on 2022/05/18 03:29:04 UTC
[incubator-hugegraph-commons] 01/01: add Cmn to CollectionUtil
This is an automated email from the ASF dual-hosted git repository.
jermy pushed a commit to branch add-cmn
in repository https://gitbox.apache.org/repos/asf/incubator-hugegraph-commons.git
commit 97d28172fe1368c9596484f3e868ff8a006db414
Author: Zhangmei Li <li...@baidu.com>
AuthorDate: Wed May 18 11:27:34 2022 +0800
add Cmn to CollectionUtil
Change-Id: I873e5c41229a8743ca5753d11c3b5e608b2e9298
---
.../com/baidu/hugegraph/util/CollectionUtil.java | 72 ++++++++++++++++++++++
.../hugegraph/unit/util/CollectionUtilTest.java | 50 +++++++++++++++
2 files changed, 122 insertions(+)
diff --git a/hugegraph-common/src/main/java/com/baidu/hugegraph/util/CollectionUtil.java b/hugegraph-common/src/main/java/com/baidu/hugegraph/util/CollectionUtil.java
index 85ab87c..31c64b3 100644
--- a/hugegraph-common/src/main/java/com/baidu/hugegraph/util/CollectionUtil.java
+++ b/hugegraph-common/src/main/java/com/baidu/hugegraph/util/CollectionUtil.java
@@ -30,6 +30,7 @@ import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ThreadLocalRandom;
+import java.util.function.Function;
public final class CollectionUtil {
@@ -236,4 +237,75 @@ public final class CollectionUtil {
}
return result;
}
+
+ /**
+ * Traverse C(m, n) combinations of a list to find first matched
+ * result combination and call back with the result.
+ * @param all list to contain all items for combination
+ * @param m m of C(m, n)
+ * @param n n of C(m, n)
+ * @return true if matched any kind of items combination else false, the
+ * callback can always return false if want to traverse all combinations
+ */
+ public static <T> boolean cmn(List<T> all, int m, int n,
+ Function<List<T>, Boolean> callback) {
+ return cmn(all, m, n, 0, null, callback);
+ }
+
+ /**
+ * Traverse C(m, n) combinations of a list to find first matched
+ * result combination and call back with the result.
+ * @param all list to contain all items for combination
+ * @param m m of C(m, n)
+ * @param n n of C(m, n)
+ * @param current current position in list
+ * @param result list to contains selected items
+ * @return true if matched any kind of items combination else false, the
+ * callback can always return false if want to traverse all combinations
+ */
+ private static <T> boolean cmn(List<T> all, int m, int n,
+ int current, List<T> result,
+ Function<List<T>, Boolean> callback) {
+ assert m <= all.size();
+ assert n <= m;
+ assert current <= all.size();
+ if (result == null) {
+ result = new ArrayList<>(n);
+ }
+
+ if (n == 0) {
+ assert result.size() > 0 : result;
+ // All n items are selected
+ List<T> tmpResult = Collections.unmodifiableList(result);
+ return callback.apply(tmpResult);
+ }
+ if (m == n) {
+ // No choice, select all n items, we don't update the `result` here
+ List<T> tmpResult = new ArrayList<>(result);
+ tmpResult.addAll(all.subList(current, all.size()));
+ return callback.apply(tmpResult);
+ }
+
+ if (current >= all.size()) {
+ // Reach the end of items
+ return false;
+ }
+
+ // Select current item, continue to select C(m-1, n-1)
+ int index = result.size();
+ result.add(all.get(current));
+ ++current;
+ if (cmn(all, m - 1, n - 1, current, result, callback)) {
+ // NOTE: we can pop the tailing items if want to keep result clear
+ return true;
+ }
+ // Not select current item, pop it and continue to select C(m-1, n)
+ result.remove(index);
+ assert result.size() == index : result;
+ if (cmn(all, m - 1, n, current, result, callback)) {
+ return true;
+ }
+
+ return false;
+ }
}
diff --git a/hugegraph-common/src/test/java/com/baidu/hugegraph/unit/util/CollectionUtilTest.java b/hugegraph-common/src/test/java/com/baidu/hugegraph/unit/util/CollectionUtilTest.java
index a1e4750..695aad8 100644
--- a/hugegraph-common/src/test/java/com/baidu/hugegraph/unit/util/CollectionUtilTest.java
+++ b/hugegraph-common/src/test/java/com/baidu/hugegraph/unit/util/CollectionUtilTest.java
@@ -417,4 +417,54 @@ public class CollectionUtilTest extends BaseUnitTest {
Assert.assertEquals(ImmutableList.of("E", "D", "C", "B", "A"),
ImmutableList.copyOf(decrOrdered.values()));
}
+
+ @Test
+ public void testCmn() {
+ List<Integer> list = ImmutableList.of(1, 2, 3, 4, 5);
+
+ // Test C(5, 2) with all combinations
+ List<List<Integer>> tuples = new ArrayList<>();
+ boolean found;
+ found = CollectionUtil.cmn(list, list.size(), 2, tuple -> {
+ tuples.add(new ArrayList<>(tuple));
+ return false;
+ });
+ Assert.assertFalse(found);
+ Assert.assertEquals(10, tuples.size());
+
+ // Test C(5, 2) with one combination
+ tuples .clear();
+ found = CollectionUtil.cmn(list, list.size(), 2, tuple -> {
+ if (tuple.equals(ImmutableList.of(2, 3))) {
+ tuples.add(new ArrayList<>(tuple));
+ return true;
+ }
+ return false;
+ });
+ Assert.assertTrue(found);
+ Assert.assertEquals(1, tuples.size());
+ Assert.assertEquals(ImmutableList.of(2, 3), tuples.get(0));
+
+ // Test C(5, 3) with all combinations
+ List<List<Integer>> triples = new ArrayList<>();
+ found = CollectionUtil.cmn(list, list.size(), 3, triple -> {
+ triples.add(new ArrayList<>(triple));
+ return false;
+ });
+ Assert.assertFalse(found);
+ Assert.assertEquals(10, triples.size());
+
+ // Test C(5, 3) with one combination
+ triples.clear();
+ found = CollectionUtil.cmn(list, list.size(), 3, triple -> {
+ if (triple.equals(ImmutableList.of(2, 3, 5))) {
+ triples.add(new ArrayList<>(triple));
+ return true;
+ }
+ return false;
+ });
+ Assert.assertTrue(found);
+ Assert.assertEquals(1, triples.size());
+ Assert.assertEquals(ImmutableList.of(2, 3, 5), triples.get(0));
+ }
}