001    // Copyright 2007 Waterken Inc. under the terms of the MIT X license
002    // found at http://www.opensource.org/licenses/mit-license.html
003    package org.ref_send.list;
004    
005    import static org.ref_send.promise.Eventual.near;
006    import static org.ref_send.promise.Eventual.ref;
007    
008    import java.io.Serializable;
009    import java.util.Iterator;
010    import java.util.NoSuchElementException;
011    
012    import org.joe_e.Equatable;
013    import org.joe_e.Struct;
014    import org.ref_send.promise.Promise;
015    import org.ref_send.promise.Receiver;
016    
017    /**
018     * A linked list.
019     * @param <T> element type
020     */
021    public final class
022    List<T> implements Iterable<T>, Serializable {
023        static private final long serialVersionUID = 1L;
024    
025        static protected final class
026        Link<T> implements Equatable, Serializable {
027            static private final long serialVersionUID = 1L;
028    
029            protected Promise<Link<T>> next;
030            protected T value;
031        }
032    
033        /**
034         * first element link
035         */
036        protected Promise<Link<T>> first;
037    
038        /**
039         * first unused link
040         */
041        protected Link<T> last;
042    
043        /**
044         * link count
045         */
046        private long capacity;
047    
048        /**
049         * element count
050         */
051        private long size;
052    
053        private
054        List() {
055            last = new Link<T>();
056            last.next = ref(last);
057            first = last.next;
058            capacity = 1;
059            size = 0;
060        }
061    
062        /**
063         * Constructs a list.
064         * @param <T> element type
065         */
066        static public <T> List<T>
067        list() { return new List<T>(); }
068    
069        // java.lang.Iterable interface
070    
071        /**
072         * Iterates over the values in this list.
073         * @return forward iterator over this list
074         */
075        public final Iterator<T>
076        iterator() { return new IteratorX(); }
077    
078        protected final class
079        IteratorX implements Iterator<T>, Serializable {
080            static private final long serialVersionUID = 1L;
081    
082            private Link<T> current = near(first);
083    
084            public boolean
085            hasNext() { return current != last; }
086    
087            public T
088            next() {
089                if (current == last) { throw new NoSuchElementException(); }
090                final T r = current.value;
091                current = near(current.next);
092                return r;
093            }
094    
095            public void
096            remove() { throw new UnsupportedOperationException(); }
097        }
098    
099        // org.ref_send.list.List interface
100    
101        /**
102         * Is the element count zero?
103         */
104        public boolean
105        isEmpty() { return 0 == size; }
106    
107        /**
108         * Gets the element count.
109         */
110        public long
111        getSize() { return size; }
112    
113        /**
114         * Gets the front value.
115         * @return front value
116         * @throws NullPointerException list is empty
117         */
118        public T
119        getFront() throws NullPointerException {
120            if (0 == size) { throw new NullPointerException(); }
121            return near(first).value;
122        }
123    
124        /**
125         * Removes the front element.
126         * @return removed value
127         * @throws NullPointerException list is empty
128         */
129        public T
130        pop() throws NullPointerException {
131            if (0 == size) { throw new NullPointerException(); }
132            final Link<T> x = near(first);
133            final T r = x.value;
134            x.value = null;
135            first = x.next;
136            size -= 1;
137            return r;
138        }
139    
140        /**
141         * Appends a value.
142         * @param value value to append
143         */
144        public void
145        append(final T value) {
146            last.value = value;
147            size += 1;
148            if (capacity == size) {
149                final Link<T> spare = new Link<T>();
150                spare.next = last.next;
151                last.next = ref(spare);
152                capacity += 1;
153            }
154            last = near(last.next);
155        }
156        
157        /**
158         * Constructs an {@linkplain #append append}er.
159         */
160        public Receiver<T>
161        appender() { return new Appender(); }
162    
163        protected final class
164        Appender extends Struct implements Receiver<T>, Serializable {
165            static private final long serialVersionUID = 1L;
166    
167            public void
168            apply(final T value) { append(value); }
169        }
170    }