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 }