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,