functionaljava#176: Implemented min, minKey, max and maxKey for tree maps. Added arbitrary tree maps.

mperry · mperry · commit 2ac9d5222842 · 2015-08-29T23:55:36.000+10:00
diff --git a/core/src/main/java/fj/data/TreeMap.java b/core/src/main/java/fj/data/TreeMap.java
@@ -308,6 +308,34 @@ public <W> TreeMap<K, W> map(final F<V, W> f) {
     return new TreeMap<K, W>(tree.map(TreeMap.<K, Option<W>>ord(o), g));
   }
 
+    /**
+     * Returns the minimum (key, value) pair in the tree if the tree is not empty.
+     */
+    public Option<P2<K, V>> min() {
+        return tree.min().map(p -> p(p._1(), p._2().some()));
+    }
+
+    /**
+     * Returns the minimum key in the tree if the tree is not empty.
+     */
+    public Option<K> minKey() {
+        return tree.min().map(p -> p._1());
+    }
+
+    /**
+     * Returns the maximum (key, value) pair in the tree if the tree is not empty.
+     */
+    public Option<P2<K, V>> max() {
+        return tree.max().map(p -> p(p._1(), p._2().some()));
+    }
+
+    /**
+     * Returns the maximum key in the tree if the tree is not empty.
+     */
+    public Option<K> maxKey() {
+        return tree.max().map(p -> p._1());
+    }
+
   	/**
 	 * The expression <code>t1.union(t2)</code> takes the left-biased union of <code>t1</code>
 	 * and <code>t2</code>. It prefers <code>t1</code> when duplicate keys are encountered.
diff --git a/core/src/test/java/fj/data/TreeMapTest.java b/core/src/test/java/fj/data/TreeMapTest.java
@@ -11,6 +11,7 @@
 import org.junit.Test;
 
 import static fj.P.p;
+import static fj.data.Option.none;
 import static fj.data.Option.some;
 import static org.hamcrest.CoreMatchers.equalTo;
 import static org.junit.Assert.assertEquals;
@@ -112,4 +113,13 @@ public void testString() {
 		assertThat(t2.toStream(), equalTo(s));
 	}
 
+    @Test
+    public void minKey() {
+        TreeMap<Integer, Integer> t1 = TreeMap.<Integer, Integer>empty(Ord.intOrd);
+        assertThat(t1.minKey(), equalTo(none()));
+        TreeMap<Integer, Integer> t2 = t1.set(1, 2).set(2, 4).set(10, 20).set(5, 10).set(0, 100);
+        assertThat(t2.minKey(), equalTo(some(0)));
+        assertThat(t2.delete(0).minKey(), equalTo(some(1)));
+    }
+
 }
diff --git a/props-core-scalacheck/src/main/scala/fj/data/ArbitraryTreeMap.scala b/props-core-scalacheck/src/main/scala/fj/data/ArbitraryTreeMap.scala
diff --git a/props-core-scalacheck/src/test/scala/fj/Tests.scala b/props-core-scalacheck/src/test/scala/fj/Tests.scala
@@ -13,7 +13,6 @@ object Tests {
     fj.data.CheckHashMap.properties,
     fj.data.CheckHashSet.properties,
     fj.data.CheckSet.properties,
-    fj.data.CheckTreeMap.properties,
     fj.control.parallel.CheckStrategy.properties,
     fj.control.parallel.CheckParModule.properties
   ).flatten
diff --git a/props-core-scalacheck/src/test/scala/fj/data/CheckTreeMap.scala b/props-core-scalacheck/src/test/scala/fj/data/CheckTreeMap.scala
diff --git a/props-core/src/test/java/fj/data/properties/TreeMapProperties.java b/props-core/src/test/java/fj/data/properties/TreeMapProperties.java
@@ -0,0 +1,69 @@
+package fj.data.properties;
+
+import fj.Equal;
+import fj.data.TreeMap;
+import fj.test.Arbitrary;
+import fj.test.Gen;
+import fj.test.Property;
+import fj.test.reflect.CheckParams;
+import fj.test.runner.PropertyTestRunner;
+import org.junit.runner.RunWith;
+
+import java.util.concurrent.atomic.AtomicInteger;
+
+import static fj.Equal.stringEqual;
+import static fj.Ord.intOrd;
+import static fj.test.Arbitrary.arbInteger;
+import static fj.test.Arbitrary.arbString;
+import static fj.test.Arbitrary.arbTreeMap;
+import static fj.test.Property.*;
+
+/**
+ * Created by MarkPerry on 29/08/2015.
+ */
+@RunWith(PropertyTestRunner.class)
+@CheckParams(maxSize = 10000)
+public class TreeMapProperties {
+
+    private static final int smallMax = 5;
+    private static final int midMax = 20;
+    public static final Arbitrary<TreeMap<Integer, String>> smallArbTreeMapIS = arbTreeMap(intOrd, arbInteger, arbString, smallMax);
+    public static final Arbitrary<TreeMap<Integer, String>> arbTreeMapIS = arbTreeMap(intOrd, arbInteger, arbString, midMax);
+
+    public Property empty() {
+        return property(smallArbTreeMapIS, tm -> impliesBoolean(tm.isEmpty(), tm.size() == 0));
+    }
+
+    public Property set() {
+        return property(arbTreeMapIS, arbInteger, arbString, (tm, k, v) ->
+            prop(stringEqual.eq(tm.set(k, v).get(k).some(), v))
+        );
+    }
+
+    public Property updateId() {
+        return property(arbTreeMapIS, arbInteger, arbString, (tm, k, v) ->
+            prop(stringEqual.eq(tm.set(k, v).update(k, x -> x)._2().get(k).some(), v))
+        );
+    }
+
+    public Property update() {
+        return property(arbTreeMapIS, arbInteger, arbString, arbString, (tm, k, v, v2) ->
+            prop(stringEqual.eq(tm.set(k, v).update(k, x -> x + v2)._2().get(k).some(), v + v2))
+        );
+    }
+
+    public Property minKey() {
+        return property(arbTreeMapIS, tm ->
+            impliesBoolean(!tm.isEmpty(), () -> Equal.intEqual.eq(tm.minKey().some(), tm.toStream().head()._1()))
+        );
+    }
+
+    public Property maxKey() {
+        return property(arbTreeMapIS, tm ->
+            impliesBoolean(!tm.isEmpty(),
+                () -> Equal.intEqual.eq(tm.maxKey().some(), tm.toStream().reverse().head()._1())
+            )
+        );
+    }
+
+}
diff --git a/quickcheck/src/main/java/fj/test/Arbitrary.java b/quickcheck/src/main/java/fj/test/Arbitrary.java
@@ -9,6 +9,8 @@
 import fj.F7;
 import fj.F8;
 import fj.Function;
+import fj.Bottom;
+
 import static fj.Function.compose;
 import static fj.P.p;
 import fj.P1;
@@ -1115,22 +1117,59 @@ public Stack<A> f(final Array<A> a) {
   }
 
   /**
-   * Returns an arbitrary implementation for tree maps.
+   * Returns an arbitrary implementation for java.util tree maps.
    *
    * @param ak An arbitrary implementation for the type over which the tree map's keys are defined.
    * @param av An arbitrary implementation for the type over which the tree map's values are
    *           defined.
    * @return An arbitrary implementation for tree maps.
    */
-  public static <K, V> Arbitrary<TreeMap<K, V>> arbTreeMap(final Arbitrary<K> ak, final Arbitrary<V> av) {
-    return arbitrary(arbHashtable(ak, av).gen.map(new F<Hashtable<K, V>, TreeMap<K, V>>() {
+  public static <K, V> Arbitrary<java.util.TreeMap<K, V>> arbJavaTreeMap(final Arbitrary<K> ak, final Arbitrary<V> av) {
+    return arbitrary(arbHashtable(ak, av).gen.map(new F<Hashtable<K, V>, java.util.TreeMap<K, V>>() {
       @SuppressWarnings({"UseOfObsoleteCollectionType"})
-      public TreeMap<K, V> f(final Hashtable<K, V> ht) {
-        return new TreeMap<K, V>(ht);
+      public java.util.TreeMap<K, V> f(final Hashtable<K, V> ht) {
+        return new java.util.TreeMap<K, V>(ht);
       }
     }));
   }
 
+    /**
+     * Returns an arbitrary implementation for tree maps.
+     */
+    public static <K, V> Arbitrary<fj.data.TreeMap<K, V>> arbTreeMap(Ord<K> ord, Arbitrary<List<P2<K, V>>> al) {
+        return arbitrary(al.gen.map(list -> fj.data.TreeMap.treeMap(ord, list)));
+    }
+
+    /**
+     * Returns an arbitrary implementation for tree maps.
+     */
+    public static <K, V> Arbitrary<fj.data.TreeMap<K, V>> arbTreeMap(Ord<K> ord, Arbitrary<K> ak, Arbitrary<V> av) {
+        return arbTreeMap(ord, arbList(arbP2(ak, av)));
+    }
+
+    /**
+     * Returns an arbitrary implementation for tree maps where the map size is the given arbitrary integer.
+     */
+    public static <K, V> Arbitrary<fj.data.TreeMap<K, V>> arbTreeMap(Ord<K> ord, Arbitrary<K> ak, Arbitrary<V> av, Arbitrary<Integer> ai) {
+        Gen<List<P2<K, V>>> gl2 = ai.gen.bind(i -> {
+            if (i < 0) {
+                Bottom.error("Undefined: arbitrary natural is negative (" + i + ")");
+            }
+            return Gen.sequenceN(Math.max(i, 0), Arbitrary.arbP2(ak, av).gen);
+        });
+        return arbTreeMap(ord, arbitrary(gl2));
+    }
+
+    /**
+     * Returns an arbitrary implementation for tree maps where the size is less than or equal to the max size.
+     */
+    public static <K, V> Arbitrary<fj.data.TreeMap<K, V>> arbTreeMap(Ord<K> ord, Arbitrary<K> ak, Arbitrary<V> av, int maxSize) {
+        if (maxSize < 0) {
+            Bottom.error("Undefined: arbitrary natural is negative (" + maxSize + ")");
+        }
+        return arbTreeMap(ord, ak, av, arbitrary(Gen.choose(0, maxSize)));
+    }
+
   /**
    * Returns an arbitrary implementation for tree sets.
    *
diff --git a/quickcheck/src/main/java/fj/test/Property.java b/quickcheck/src/main/java/fj/test/Property.java
@@ -362,6 +362,22 @@ public Result f(final Rand r) {
     });
   }
 
+    /**
+     * Returns a property that produces a result only if the given condition satisfies. The result
+     * will be taken from the given boolean b.
+     */
+    public static Property impliesBoolean(final boolean a, final boolean b) {
+        return implies(a, () -> Property.prop(b));
+    }
+
+    /**
+     * Returns a property that produces a result only if the given condition satisfies. The result
+     * will be taken from the given lazy boolean b.
+     */
+    public static Property impliesBoolean(final boolean a, final F0<Boolean> b) {
+        return implies(a, () -> Property.prop(b.f()));
+    }
+
   /**
    * Returns a property from the given function.
    *
diff --git a/quickcheck/src/main/java/fj/test/runner/PropertyTestRunner.java b/quickcheck/src/main/java/fj/test/runner/PropertyTestRunner.java
@@ -43,7 +43,8 @@ public void run(RunNotifier notifier) {
       CheckResult result = checkProperty(p._1(), p._2());
 
       try {
-        CheckResult.summaryEx.showS(result);
+          String s = CheckResult.summaryEx.showS(result);
+          System.out.println(getLabel(desc) + ": " + s);
       } catch (Throwable t) {
         notifier.fireTestFailure(new Failure(desc, t));
       }
@@ -52,6 +53,10 @@ public void run(RunNotifier notifier) {
     });
   }
 
+    private static String getLabel(Description d) {
+        return d.getDisplayName();
+    }
+
   private static CheckResult checkProperty(Property prop, Option<CheckParams> params) {
     for (CheckParams ps : params) {
       return prop.check(ps.minSuccessful(), ps.maxDiscarded(), ps.minSize(), ps.maxSize());
