Java : 遅延リスト

[id:lethevert:20060208:p3]
遅延リストを作ってみた。
以下、サンプルコード。

import java.util.List;
import java.util.Iterator;

public class Main {
  public static void main(String[] args) {

    //有限の遅延リスト Iteratorの利用
    List<Integer> list = new LazyList<Integer>() {
        protected boolean terminated(int index) {
          return index >= 5;
        }
        protected Integer create(int index) {
          return index;
        }
      };

    for(Integer i : list) {
      System.out.println((Integer) itr.next());
    }

    //無限の遅延リスト メモ化
    final List<Integer> fib = new LazyList<Integer>() {
        protected Integer create(int index) {
          if (index < 2) { return 1;}
          return get(index-1) + get(index-2);
        }
      };

    System.out.println(fib.get(100));
    System.out.println(fib.get(5)); //1 1 2 3 5 8
  }
}

で、これが実装。

import java.util.List;
import java.util.AbstractList;
import java.util.TreeMap;
import java.util.Iterator;

public abstract class LazyList<A> extends AbstractList<A> {
  private boolean sizeSupported = true;
  public int size() {
    throw new UnsupportedOperationException();
  }
  protected boolean terminated(int index) {
    if (sizeSupported) {
      try{
        if(index >= size()) { return true;}
      }catch(UnsupportedOperationException e) {
        sizeSupported = false;
      }
    }
    return false;
  }
  protected abstract A create(int index);

  public List<A> subList(final int fromIndex, final int toIndex) {
    if(fromIndex < 0) { throw new IndexOutOfBoundsException(); }
    if(fromIndex > toIndex) { throw new IndexOutOfBoundsException(); }
    try{
      if(toIndex > size()) { throw new IndexOutOfBoundsException(); }
    }catch(UnsupportedOperationException e){}

    final List<A> self = this;
    return new LazyList<A>() {
        public A create(int index) { return null;}
        public int size() { return toIndex - fromIndex;}
        public A get(int index) {
          return self.get(index + fromIndex);
        }
      };
  }

  private int upper = 0;
  private TreeMap<Integer, A> map = new TreeMap<Integer, A>();
  public A get(int index) {
    if(index < 0) { throw new IndexOutOfBoundsException(); }
    A ret = null;
    if(index < upper) {
      ret = map.get(index);
    }
    if(ret == null) {
      ret = create(index);
      map.put(index, ret);
      if (upper <= index) { upper = index+1;}
    }
    return ret;
  }

  public Iterator<A> iterator() {
    return new Iterator<A>() {
      int index = 0;
      public boolean hasNext() {
        return ! terminated(index);
      }
      public A next() {
        return get(index++);
      }
      public void remove() {
        throw new UnsupportedOperationException();
      }
    };
  }
}