Java : Finger Trees
Finger TreesをJavaで実装してみた。
まあ、ネタなのでpushしかないけど、どういうデータ構造かを知るにはよいかも。
import java.util.ArrayList; import java.io.PrintStream; public abstract class FingerTree<A> { public static <A> FingerTree<A> create () { return new Empty<A>();} public abstract FingerTree<A> pushL (A a); public abstract FingerTree<A> pushR (A a); public abstract void print (PrintStream out); } class Empty<A> extends FingerTree<A>{ public FingerTree<A> pushL (A a){ return new Single<A>(a); } public FingerTree<A> pushR (A a){ return new Single<A>(a); } public void print (PrintStream out){} } class Single<A> extends FingerTree<A>{ final A data; Single(A a) { data = a;} public FingerTree<A> pushL (A a){ ArrayList<A> pr = new ArrayList<A>(1); pr.add(a); ArrayList<A> sf = new ArrayList<A>(1); sf.add(data); return new Deep<A>(pr,new Empty<Deep.Node<A>>(),sf); } public FingerTree<A> pushR (A a){ ArrayList<A> pr = new ArrayList<A>(1); pr.add(data); ArrayList<A> sf = new ArrayList<A>(1); sf.add(a); return new Deep<A>(pr,new Empty<Deep.Node<A>>(),sf); } public void print (PrintStream out){ Deep.Node.print(data,out); } } class Deep<A> extends FingerTree<A>{ ArrayList<A> pr; FingerTree<Node<A>> m; ArrayList<A> sf; Deep(ArrayList<A> pr, FingerTree<Node<A>> m, ArrayList<A> sf) { this.pr = pr; this.m = m; this.sf = sf; } public FingerTree<A> pushL (A a){ if (pr.size() > 4){ throw new IllegalStateException(); }else if (pr.size() == 4){ ArrayList<A> pr1 = new ArrayList<A>(2); pr1.add(a); pr1.add(pr.get(0)); Node<A> n = new Node<A>(pr.get(1),pr.get(2),pr.get(3)); return new Deep<A>(pr1,m.pushL(n),sf); }else{ ArrayList<A> pr1 = new ArrayList<A>(1 + pr.size()); pr1.add(a); pr1.addAll(pr); return new Deep<A>(pr1,m,sf); } } public FingerTree<A> pushR (A a){ if (sf.size() > 4){ throw new IllegalStateException(); }else if (sf.size() == 4){ ArrayList<A> sf1 = new ArrayList<A>(2); sf1.add(sf.get(3)); sf1.add(a); Node<A> n = new Node<A>(sf.get(0),sf.get(1),sf.get(2)); return new Deep<A>(pr,m.pushR(n),sf1); }else{ ArrayList<A> sf1 = new ArrayList<A>(1 + sf.size()); sf1.addAll(sf); sf1.add(a); return new Deep<A>(pr,m,sf1); } } public void print (PrintStream out){ for (A a:pr){ Node.print(a,out);} m.print(out); for (A a:sf){ Node.print(a,out);} } static class Node<A> { Object[] data = new Object[3]; boolean node2 = true; Node (A a, A b) { data[0] = a; data[1] = b; node2 = true;} Node (A a, A b, A c) { data[0] = a; data[1] = b; data[2] = c; node2 = false;} void add (A c) { if (node2) { data[2] = c; node2 = false;} else { throw new IllegalStateException();}} static <A> void print (A a, PrintStream out){ if (a instanceof Node){ Node n = (Node) a; print(n.data[0],out); print(n.data[1],out); if (! n.node2) { print(n.data[2],out);} }else{ out.print(a); out.print(", "); } } } }
次のテストコードを実行すると、
public class Main{ public static void main (String[] args) { FingerTree<Integer> ft = FingerTree.create(); for (int i=0; i<10; ++i){ ft = ft.pushL(i);} for (int i=11; i<20; ++i){ ft = ft.pushR(i);} ft.print(System.out); System.out.println(); } }
次のような結果に。
$ java Main 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 11, 12, 13, 14, 15, 16, 17, 18, 19,