001    package fj.data.fingertrees;
002    
003    import fj.F;
004    import fj.F2;
005    import fj.P2;
006    import static fj.Function.curry;
007    
008    /**
009     * An inner node of the 2-3 tree.
010     */
011    public abstract class Node<V, A> {
012      private final Measured<V, A> m;
013      private final V measure;
014    
015      public abstract <B> B foldRight(final F<A, F<B, B>> f, final B z);
016    
017      public abstract <B> B foldLeft(final F<B, F<A, B>> f, final B z);
018    
019      public static <V, A, B> F<B, F<Node<V, A>, B>> foldLeft_(final F<B, F<A, B>> bff) {
020        return curry(new F2<B, Node<V, A>, B>() {
021          public B f(final B b, final Node<V, A> node) { return node.foldLeft(bff, b); }
022        });
023      }
024    
025      public static <V, A, B> F<B, F<Node<V, A>, B>> foldRight_(final F<A, F<B, B>> aff) {
026        return curry(new F2<B, Node<V, A>, B>() {
027          public B f(final B b, final Node<V, A> node) { return node.foldRight(aff, b); }
028        });
029      }
030    
031      public <B> Node<V, B> map(final F<A, B> f, final Measured<V, B> m) {
032        return match(new F<Node2<V, A>, Node<V, B>>() {
033          public Node<V, B> f(final Node2<V, A> node2) {
034            return new Node2<V, B>(m, node2.toVector().map(f));
035          }
036        }, new F<Node3<V, A>, Node<V, B>>() {
037          public Node<V, B> f(final Node3<V, A> node3) {
038            return new Node3<V, B>(m, node3.toVector().map(f));
039          }
040        });
041      }
042    
043      public static <V, A, B> F<Node<V, A>, Node<V, B>> liftM(final F<A, B> f, final Measured<V, B> m) {
044        return new F<Node<V, A>, Node<V, B>>() {
045          public Node<V, B> f(final Node<V, A> node) {
046            return node.map(f, m);
047          }
048        };
049      }
050    
051      public abstract Digit<V, A> toDigit();
052    
053      Node(final Measured<V, A> m, final V measure) {
054        this.m = m;
055        this.measure = measure;
056      }
057    
058      public V measure() {
059        return measure;
060      }
061    
062      protected Measured<V, A> measured() {
063        return m;
064      }
065    
066      public abstract P2<Integer, A> lookup(final F<V, Integer> o, final int i);
067    
068      public abstract <B> B match(final F<Node2<V, A>, B> n2, final F<Node3<V, A>, B> n3);
069    }