001package iterator.listfour;
002import java.util.NoSuchElementException;
003import java.util.ConcurrentModificationException;
004
005/* public */
006interface MutList {
007        public Iterator newIterator();
008        public void insert(int i); // insert i at head of list
009        public void delete(int i); // delete first occurence of i in the list
010}
011
012/* public */
013interface Iterator {
014        public boolean hasNext();
015        public int next();
016}
017
018/* public */
019class MutListF {
020        private MutListF() {}
021        public static final MutList newI() {
022                return new MutListObj();
023        }
024}
025
026class MutListObj implements MutList, Changeable {
027        private List l = ListF.nil;
028        private int changeCount = 0;
029        public int changeCount() { return changeCount; }
030        public Iterator newIterator() { return l.newIterator(this); }
031        public String toString() { return l.toString(); }
032        public void insert(int i) {
033                changeCount++;
034                l = l.insert(i);
035        }
036        public void delete(int i) {
037                changeCount++;
038                l = l.delete(i);
039        }
040}
041
042/*
043 *************************************************************************
044 * Immutable List classes.
045 *************************************************************************
046 */
047interface Changeable {
048        public int changeCount();
049}
050
051interface List {
052        public Iterator newIterator(Changeable parent);
053        public List insert(int i);
054        public List delete(int i);
055}
056
057class ListF {
058        private ListF() {}
059        public static final List nil = new Nil(); /* Singleton */
060        public static final List cons(int hd, List tl) /* Factory */ {
061                return new Cons(hd, tl);
062        }
063}
064
065class Nil implements List {
066        Nil() {}
067        public String toString() { return "nil"; }
068        public Iterator newIterator(Changeable parent) {
069                return new NullIterator();
070        }
071        public List insert(int i) {
072                return ListF.cons(i, this);
073        }
074        public List delete(int i) {
075                throw new NoSuchElementException();
076        }
077}
078
079class Cons implements List {
080        final int hd;
081        final List tl;
082        Cons(int hd, List tl) { this.hd = hd; this.tl = tl; }
083        public String toString() { return hd + "::" + tl.toString(); }
084        public Iterator newIterator(Changeable parent) {
085                return new ListIterator(this, parent);
086        }
087        public List insert(int i) {
088                return ListF.cons(i, this);
089        }
090        public List delete(int i) {
091                if (hd == i) {
092                        return tl;
093                } else {
094                        List new_tl = tl.delete(i);
095                        return ListF.cons(hd, new_tl);
096                }
097        }
098}
099
100class NullIterator implements Iterator {
101        NullIterator() { }
102        public boolean hasNext() { return false; }
103        public int next() { throw new NoSuchElementException(); }
104}
105
106class ListIterator implements Iterator {
107        private List node;
108        private Changeable parent;
109        private int changeCount;
110        ListIterator(List node, Changeable parent) {
111                this.node = node;
112                this.parent = parent;
113                this.changeCount = parent.changeCount();
114        }
115        public boolean hasNext() {
116                if (changeCount != parent.changeCount())
117                        throw new ConcurrentModificationException();
118                return node != ListF.nil;
119        }
120        public int next() {
121                if (changeCount != parent.changeCount())
122                        throw new ConcurrentModificationException();
123                if (! hasNext())
124                        throw new NoSuchElementException();
125                int result = ((Cons)node).hd;
126                node = ((Cons)node).tl;
127                return result;
128        }
129}
130
131/*
132 *************************************************************************
133 * A test case.
134 *************************************************************************
135 */
136public class Main {
137        public static void main(String[] args) {
138                MutList test = MutListF.newI();
139                test.insert(3);
140                test.insert(2);
141                test.insert(1);
142                System.out.println(test);
143
144                int sum=0;
145                for (Iterator i = test.newIterator(); i.hasNext(); )
146                        sum += i.next();
147                System.out.println(sum);
148
149                List rev=ListF.nil;
150                for (Iterator i = test.newIterator(); i.hasNext(); )
151                        rev = ListF.cons(i.next(),rev);
152                System.out.println(rev);
153
154                for (Iterator i = test.newIterator(); i.hasNext(); )
155                        test.insert(4);
156        }
157}