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(); } }; } }