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    }