Added headOption to Sqq and FingerTree. Added length to FingerTree. Added length property test to Seq and FingerTree

mperry · mperry · commit 7e1d3a9300af · 2015-10-10T21:22:08.000+10:00
diff --git a/core/src/main/java/fj/data/Seq.java b/core/src/main/java/fj/data/Seq.java
@@ -100,6 +100,10 @@ public Seq<A> snoc(final A a) {
    */
   public A head() { return ftree.head(); }
 
+  public Option<A> headOption() {
+      return ftree.headOption();
+  }
+
   /**
    * The last element of this sequence. This is an O(1) operation.
    *
diff --git a/core/src/main/java/fj/data/fingertrees/Deep.java b/core/src/main/java/fj/data/fingertrees/Deep.java
@@ -195,6 +195,12 @@ private static final <V, A> FingerTree<V, A> deepR(final Measured<V, A> measured
     }
   }
 
+    @Override
+    public int length() {
+        int midSize = middle.foldLeft((acc, n) -> acc + n.length(), 0);
+        return prefix.length() + midSize + suffix.length();
+    }
+
     private static <V, A> FingerTree<V, Node<V, A>> addDigits0(
             final Measured<V, A> m, final FingerTree<V, Node<V, A>> m1,
             final Digit<V, A> s1, final Digit<V, A> p2,
diff --git a/core/src/main/java/fj/data/fingertrees/Digit.java b/core/src/main/java/fj/data/fingertrees/Digit.java
@@ -159,4 +159,7 @@ Option<Digit<V, A>> init() {
   abstract P3<Option<Digit<V, A>>, A, Option<Digit<V, A>>> split1(final F<V, Boolean> predicate, final V acc);
 
   public abstract P2<Integer, A> lookup(final F<V, Integer> o, final int i);
+
+    public abstract int length();
+
 }
diff --git a/core/src/main/java/fj/data/fingertrees/Empty.java b/core/src/main/java/fj/data/fingertrees/Empty.java
@@ -37,7 +37,12 @@ public final class Empty<V, A> extends FingerTree<V, A> {
 
   @Override public P2<Integer, A> lookup(final F<V, Integer> o, final int i) { throw error("Lookup of empty tree."); }
 
-  @Override public <B> B foldRight(final F<A, F<B, B>> aff, final B z) {
+    @Override
+    public int length() {
+        return 0;
+    }
+
+    @Override public <B> B foldRight(final F<A, F<B, B>> aff, final B z) {
     return z;
   }
 
diff --git a/core/src/main/java/fj/data/fingertrees/FingerTree.java b/core/src/main/java/fj/data/fingertrees/FingerTree.java
@@ -4,6 +4,8 @@
 import fj.data.Option;
 import fj.data.Seq;
 
+import static fj.Monoid.intAdditionMonoid;
+
 /**
  * Provides 2-3 finger trees, a functional representation of persistent sequences supporting access to the ends in
  * amortized O(1) time. Concatenation and splitting time is O(log n) in the size of the smaller piece.
@@ -158,6 +160,10 @@ public static <V, A> MakeTree<V, A> mkTree(final Measured<V, A> m) {
    */
   public abstract A head();
 
+  public Option<A> headOption() {
+      return isEmpty() ? Option.<A>none() : Option.some(head());
+  }
+
   /**
    * The last element of this tree. This is an O(1) operation.
    *
@@ -215,4 +221,11 @@ public final P3<FingerTree<V, A>, A, FingerTree<V, A>> split1(final F<V, Boolean
   abstract P3<FingerTree<V, A>, A, FingerTree<V, A>> split1(final F<V, Boolean> predicate, final V acc);
 
   public abstract P2<Integer, A> lookup(final F<V, Integer> o, final int i);
+
+    public abstract int length();
+
+    public static <A> FingerTree<Integer, A> emptyIntAddition() {
+        return FingerTree.mkTree(FingerTree.<Integer, A>measured(intAdditionMonoid, Function.constant(1))).empty();
+    }
+
 }
diff --git a/core/src/main/java/fj/data/fingertrees/Four.java b/core/src/main/java/fj/data/fingertrees/Four.java
@@ -83,4 +83,9 @@ public V4<A> values() {
       }
     }
   }
+
+    @Override
+    public int length() {
+        return 4;
+    }
 }
diff --git a/core/src/main/java/fj/data/fingertrees/Node.java b/core/src/main/java/fj/data/fingertrees/Node.java
@@ -58,4 +58,6 @@ Measured<V, A> measured() {
   public abstract P2<Integer, A> lookup(final F<V, Integer> o, final int i);
 
   public abstract <B> B match(final F<Node2<V, A>, B> n2, final F<Node3<V, A>, B> n3);
+
+  public abstract int length();
 }
diff --git a/core/src/main/java/fj/data/fingertrees/Node2.java b/core/src/main/java/fj/data/fingertrees/Node2.java
@@ -58,7 +58,12 @@ public <B> B match(final F<Node2<V, A>, B> n2, final F<Node3<V, A>, B> n3) {
     return n2.f(this);
   }
 
-  public V2<A> toVector() {
+    @Override
+    public int length() {
+        return 2;
+    }
+
+    public V2<A> toVector() {
     return as;
   }
 }
diff --git a/core/src/main/java/fj/data/fingertrees/Node3.java b/core/src/main/java/fj/data/fingertrees/Node3.java
@@ -34,7 +34,12 @@ public <B> B match(final F<Node2<V, A>, B> n2, final F<Node3<V, A>, B> n3) {
     return n3.f(this);
   }
 
-  public Digit<V, A> toDigit() {
+    @Override
+    public int length() {
+        return 3;
+    }
+
+    public Digit<V, A> toDigit() {
     return new Three<V, A>(measured(), as);
   }
 
diff --git a/core/src/main/java/fj/data/fingertrees/One.java b/core/src/main/java/fj/data/fingertrees/One.java
@@ -49,4 +49,9 @@ public A value() {
   @Override public P2<Integer, A> lookup(final F<V, Integer> o, final int i) {
     return P.p(i, a);
   }
+
+    @Override
+    public int length() {
+        return 1;
+    }
 }
diff --git a/core/src/main/java/fj/data/fingertrees/Single.java b/core/src/main/java/fj/data/fingertrees/Single.java
@@ -86,7 +86,12 @@ public V measure() {
 
   @Override public P2<Integer, A> lookup(final F<V, Integer> o, final int i) { return p(i, a); }
 
-  /**
+    @Override
+    public int length() {
+        return 1;
+    }
+
+    /**
    * Returns the single element of this tree.
    *
    * @return the single element of this tree.
diff --git a/core/src/main/java/fj/data/fingertrees/Three.java b/core/src/main/java/fj/data/fingertrees/Three.java
@@ -73,4 +73,9 @@ public V3<A> values() {
       }
     }
   }
+
+    @Override
+    public int length() {
+        return 3;
+    }
 }
diff --git a/core/src/main/java/fj/data/fingertrees/Two.java b/core/src/main/java/fj/data/fingertrees/Two.java
@@ -64,4 +64,10 @@ public V2<A> values() {
       return P.p(i - s1, as._2());
     }
   }
+
+    @Override
+    public int length() {
+        return 2;
+    }
+
 }
diff --git a/props-core/src/test/java/fj/data/fingertrees/FingerTreeProperties.java b/props-core/src/test/java/fj/data/fingertrees/FingerTreeProperties.java
@@ -0,0 +1,26 @@
+package fj.data.fingertrees;
+
+import fj.test.Property;
+import fj.test.reflect.CheckParams;
+import fj.test.runner.PropertyTestRunner;
+import org.junit.runner.RunWith;
+
+import static fj.test.Arbitrary.arbInteger;
+import static fj.test.Arbitrary.arbList;
+import static fj.test.Property.prop;
+import static fj.test.Property.property;
+
+/**
+ * Created by MarkPerry on 10/10/2015.
+ */
+@RunWith(PropertyTestRunner.class)
+@CheckParams(maxSize = 10000)
+public class FingerTreeProperties {
+
+    public Property size() {
+        return property(arbList(arbInteger), list ->
+            prop(list.foldLeft((acc, i) -> acc.snoc(i), FingerTree.<Integer>emptyIntAddition()).length() == list.length())
+        );
+    }
+
+}
diff --git a/props-core/src/test/java/fj/data/fingertrees/FingerTreeTest.java b/props-core/src/test/java/fj/data/fingertrees/FingerTreeTest.java
@@ -0,0 +1,30 @@
+package fj.data.fingertrees;
+
+import fj.data.List;
+import org.junit.Test;
+
+import static fj.test.Property.prop;
+import static fj.test.Property.property;
+import static org.hamcrest.CoreMatchers.equalTo;
+import static org.junit.Assert.assertThat;
+
+/**
+ * Created by MarkPerry on 10/10/2015.
+ */
+public class FingerTreeTest {
+
+    @Test
+    public void size() {
+        validateSize(List.list(-92, 68, 54, -77, -18, 67));
+        validateSize(List.list(-92, 68, 54, -77, -18, 67, -60, 23, -70, 99, 66, -79, -5));
+    }
+
+    void validateSize(List<Integer> list) {
+        FingerTree<Integer, Integer> ft = list.foldLeft(
+            (acc, i) -> acc.snoc(i), FingerTree.<Integer>emptyIntAddition()
+        );
+        assertThat(ft.measure(), equalTo(list.length()));
+        assertThat(ft.length(), equalTo(list.length()));
+    }
+
+}
diff --git a/props-core/src/test/java/fj/data/properties/SeqProperties.java b/props-core/src/test/java/fj/data/properties/SeqProperties.java
@@ -16,9 +16,7 @@
 import static fj.Function.identity;
 import static fj.data.Option.none;
 import static fj.data.Option.some;
-import static fj.test.Arbitrary.arbInteger;
-import static fj.test.Arbitrary.arbSeq;
-import static fj.test.Arbitrary.arbitrary;
+import static fj.test.Arbitrary.*;
 import static fj.test.Property.implies;
 import static fj.test.Property.prop;
 import static fj.test.Property.property;
@@ -121,4 +119,11 @@ public Property foldRight() {
     return property(arbSeq(arbitrary(Gen.value(1))), seq ->
       prop(seq.foldRight((i, acc) -> acc + i, 0) == seq.length()));
   }
+
+    public Property length() {
+        return property(arbList(arbInteger), list ->
+            prop(Seq.seq(list).length() == list.length())
+        );
+    }
+
 }

Original file line number	Diff line number	Diff line change
`@@ -195,6 +195,12 @@ private static final <V, A> FingerTree<V, A> deepR(final Measured<V, A> measured`
`195`	`195`	`}`
`196`	`196`	`}`
`197`	`197`
	`198`	`+ @Override`
	`199`	`+ public int length() {`
	`200`	`+ int midSize = middle.foldLeft((acc, n) -> acc + n.length(), 0);`
	`201`	`+ return prefix.length() + midSize + suffix.length();`
	`202`	`+ }`
	`203`	`+`
`198`	`204`	`private static <V, A> FingerTree<V, Node<V, A>> addDigits0(`
`199`	`205`	`final Measured<V, A> m, final FingerTree<V, Node<V, A>> m1,`
`200`	`206`	`final Digit<V, A> s1, final Digit<V, A> p2,`
Original file line number	Diff line number	Diff line change
`@@ -159,4 +159,7 @@ Option<Digit<V, A>> init() {`
`159`	`159`	`abstract P3<Option<Digit<V, A>>, A, Option<Digit<V, A>>> split1(final F<V, Boolean> predicate, final V acc);`
`160`	`160`
`161`	`161`	`public abstract P2<Integer, A> lookup(final F<V, Integer> o, final int i);`
	`162`	`+`
	`163`	`+ public abstract int length();`
	`164`	`+`
`162`	`165`	`}`
Original file line number	Diff line number	Diff line change
`@@ -83,4 +83,9 @@ public V4<A> values() {`
`83`	`83`	`}`
`84`	`84`	`}`
`85`	`85`	`}`
	`86`	`+`
	`87`	`+ @Override`
	`88`	`+ public int length() {`
	`89`	`+ return 4;`
	`90`	`+ }`
`86`	`91`	`}`
Original file line number	Diff line number	Diff line change
`@@ -58,4 +58,6 @@ Measured<V, A> measured() {`
`58`	`58`	`public abstract P2<Integer, A> lookup(final F<V, Integer> o, final int i);`
`59`	`59`
`60`	`60`	`public abstract <B> B match(final F<Node2<V, A>, B> n2, final F<Node3<V, A>, B> n3);`
	`61`	`+`
	`62`	`+ public abstract int length();`
`61`	`63`	`}`
Original file line number	Diff line number	Diff line change
`@@ -58,7 +58,12 @@ public <B> B match(final F<Node2<V, A>, B> n2, final F<Node3<V, A>, B> n3) {`
`58`	`58`	`return n2.f(this);`
`59`	`59`	`}`
`60`	`60`
`61`		`- public V2<A> toVector() {`
	`61`	`+ @Override`
	`62`	`+ public int length() {`
	`63`	`+ return 2;`
	`64`	`+ }`
	`65`	`+`
	`66`	`+ public V2<A> toVector() {`
`62`	`67`	`return as;`
`63`	`68`	`}`
`64`	`69`	`}`
Original file line number	Diff line number	Diff line change
`@@ -34,7 +34,12 @@ public <B> B match(final F<Node2<V, A>, B> n2, final F<Node3<V, A>, B> n3) {`
`34`	`34`	`return n3.f(this);`
`35`	`35`	`}`
`36`	`36`
`37`		`- public Digit<V, A> toDigit() {`
	`37`	`+ @Override`
	`38`	`+ public int length() {`
	`39`	`+ return 3;`
	`40`	`+ }`
	`41`	`+`
	`42`	`+ public Digit<V, A> toDigit() {`
`38`	`43`	`return new Three<V, A>(measured(), as);`
`39`	`44`	`}`
`40`	`45`
Original file line number	Diff line number	Diff line change
`@@ -49,4 +49,9 @@ public A value() {`
`49`	`49`	`@Override public P2<Integer, A> lookup(final F<V, Integer> o, final int i) {`
`50`	`50`	`return P.p(i, a);`
`51`	`51`	`}`
	`52`	`+`
	`53`	`+ @Override`
	`54`	`+ public int length() {`
	`55`	`+ return 1;`
	`56`	`+ }`
`52`	`57`	`}`