001 package fj.data; 002 003 import fj.Function; 004 import static fj.Bottom.error; 005 import static fj.pre.Monoid.intAdditionMonoid; 006 import static fj.data.fingertrees.FingerTree.measured; 007 import static fj.pre.Ord.intOrd; 008 import fj.data.fingertrees.FingerTree; 009 import fj.data.fingertrees.MakeTree; 010 import fj.data.fingertrees.Measured; 011 012 /** 013 * Provides an immutable finite sequence, implemented as a finger tree. This structure gives O(1) access to 014 * the head and tail, as well as O(log n) random access and concatenation of sequences. 015 */ 016 public final class Seq<A> { 017 private static <A> MakeTree<Integer, A> mkTree() { 018 return FingerTree.mkTree(Seq.<A>elemMeasured()); 019 } 020 021 private final FingerTree<Integer, A> ftree; 022 023 private Seq(final FingerTree<Integer, A> ftree) { 024 this.ftree = ftree; 025 } 026 027 private static <A> Measured<Integer, A> elemMeasured() { 028 return measured(intAdditionMonoid, Function.<A, Integer>constant(1)); 029 } 030 031 /** 032 * The empty sequence. 033 * 034 * @return A sequence with no elements. 035 */ 036 public static <A> Seq<A> empty() { 037 return new Seq<A>(Seq.<A>mkTree().empty()); 038 } 039 040 /** 041 * A singleton sequence. 042 * 043 * @param a The single element in the sequence. 044 * @return A new sequence with the given element in it. 045 */ 046 public static <A> Seq<A> single(final A a) { 047 return new Seq<A>(Seq.<A>mkTree().single(a)); 048 } 049 050 /** 051 * Inserts the given element at the front of this sequence. 052 * 053 * @param a An element to insert at the front of this sequence. 054 * @return A new sequence with the given element at the front. 055 */ 056 public Seq<A> cons(final A a) { 057 return new Seq<A>(ftree.cons(a)); 058 } 059 060 /** 061 * Inserts the given element at the end of this sequence. 062 * 063 * @param a An element to insert at the end of this sequence. 064 * @return A new sequence with the given element at the end. 065 */ 066 public Seq<A> snoc(final A a) { 067 return new Seq<A>(ftree.snoc(a)); 068 } 069 070 /** 071 * Appends the given sequence to this sequence. 072 * 073 * @param as A sequence to append to this one. 074 * @return A new sequence with the given sequence appended to this one. 075 */ 076 public Seq<A> append(final Seq<A> as) { 077 return new Seq<A>(ftree.append(as.ftree)); 078 } 079 080 /** 081 * Checks if this is the empty sequence. 082 * 083 * @return True if this sequence is empty, otherwise false. 084 */ 085 public boolean isEmpty() { 086 return ftree.isEmpty(); 087 } 088 089 /** 090 * Returns the number of elements in this sequence. 091 * 092 * @return the number of elements in this sequence. 093 */ 094 public int length() { 095 return ftree.measure(); 096 } 097 098 /** 099 * Returns the element at the given index. 100 * 101 * @param i The index of the element to return. 102 * @return The element at the given index, or throws an error if the index is out of bounds. 103 */ 104 public A index(final int i) { 105 if (i < 0 || i >= length()) 106 throw error("Index " + i + "out of bounds."); 107 return ftree.lookup(Function.<Integer>identity(), i)._2(); 108 } 109 }