Algorithmen & Datenstrukturen mit Java: Beispielklasse für einfach verkettete Listen |
1package ds.persistent.list;
2
3/** Implementation of single linked lists.
4 The element type is the example class E
5 In real world java progs, this would be a
6 generic type parameter.
7
8 This implementation is a PERSISTENT one.
9*/
10
11import ds.interfaces.List;
12import ds.util.E;
13import java.util.Iterator;
14
15import static ds.util.Undef.undefined;
16
17public abstract class LinkedList
18 implements List {
19
20 //----------------------------------------
21 // the smart constructors
22
23 // empty list
24 public static
25 LinkedList empty() {
26
27 return
28 EMPTY;
29 }
30
31 // singleton list
32 public static
33 LinkedList singleton(E e) {
34 return
35 EMPTY.cons(e);
36 }
37
38 // list from iterator
39 public static
40 LinkedList fromIterator(Iterator<E> elems) {
41
42 if ( elems.hasNext() ) {
43 E info = elems.next();
44 return
45 fromIterator(elems).cons(info);
46 }
47 return
48 empty();
49 }
50
51 //----------------------------------------
52 // public methods
53
54 public boolean inv() {
55 return true;
56 }
57
58 public abstract LinkedList init();
59 public abstract LinkedList tail();
60
61 public abstract LinkedList concat(List l2);
62
63 public LinkedList append(E e) {
64 return
65 concat(singleton(e));
66 }
67
68 public Node cons(E e) {
69 return
70 new Node(e, this);
71 }
72
73 public LinkedList reverse() {
74 return
75 reverse1(empty());
76 }
77 abstract protected LinkedList reverse1(LinkedList res);
78
79 // default impementation for copy
80 public LinkedList copy() {
81 return
82 this;
83 }
84
85 public Iterator<E> iterator() {
86 return
87 new ListIterator(this);
88 }
89
90 public String toString() {
91 return
92 (new ListIterator(this)).toString();
93 }
94
95 //----------------------------------------
96 // the empty list
97
98 // the "generic" empty list object, (the singleton has a raw type)
99
100 private static final LinkedList EMPTY
101 = new Empty();
102
103 // the singleton class for the empty list object
104
105 private static final
106 class Empty
107 extends LinkedList {
108
109 public boolean isEmpty() {
110 return true;
111 }
112 public boolean member(E e) {
113 return false;
114 }
115 public int length() {
116 return 0;
117 }
118 public E head() {
119 return
120 undefined("head of empty list");
121 }
122 public LinkedList tail() {
123 return
124 undefined("tail of empty list");
125 }
126 public E last() {
127 return
128 undefined("last of empty list");
129 }
130 public LinkedList init() {
131 return
132 undefined("init of empty list");
133 }
134 public E at(int i) {
135 return
136 undefined("at of empty list");
137 }
138 public LinkedList concat(List l2) {
139 return
140 (LinkedList)l2;
141 }
142
143 //----------------------------------------
144 // not public stuff
145
146 Empty() { }
147
148 protected LinkedList reverse1(LinkedList acc) {
149 return
150 acc;
151 }
152 }
153
154 //----------------------------------------
155 // the none empty list class
156
157 private static final
158 class Node
159 extends LinkedList {
160
161 public boolean isEmpty() {
162 return
163 false;
164 }
165
166 public boolean member(E e) {
167 return
168 e.equalTo(info)
169 ||
170 next.member(e);
171 }
172
173 public int length() {
174 return
175 1 + next.length();
176 }
177
178 public E head() {
179 return
180 info;
181 }
182
183 public LinkedList tail() {
184 return
185 next;
186 }
187
188 public E last() {
189 if ( next.isEmpty() )
190 return
191 info;
192 return
193 next.last();
194 }
195
196 public LinkedList init() {
197 if ( next.isEmpty() )
198 return
199 empty();
200 return
201 setNext(next.init());
202 }
203
204 public E at(int i) {
205 if ( i == 0 )
206 return
207 info;
208 return
209 next.at(i - 1);
210 }
211
212 public LinkedList concat(List l2) {
213 return
214 setNext(next.concat(l2));
215 }
216
217 /* destructive *
218 public LinkedList copy() { // duplicate all nodes
219 return
220 next.copy().cons(info);
221 }
222 /**/
223
224 //----------------------------------------
225 // not public stuff
226
227 private final E info;
228 private
229 /* persistent */ final /**/
230 LinkedList next;
231
232 Node(E i, LinkedList n) {
233 info = i;
234 next = n;
235 ++cntNode;
236 }
237
238 protected LinkedList reverse1(LinkedList acc) {
239 return
240 next.reverse1(setNext(acc));
241 }
242
243 Node setNext(LinkedList l2) {
244 /* persistent */
245 if ( l2 == next )
246 return
247 this;
248 return
249 l2.cons(info);
250
251 /* destructive *
252 next = l2;
253 return
254 this;
255 /**/
256 }
257 }
258
259 //----------------------------------------
260 // iterator class
261
262 private static
263 class ListIterator
264 extends ds.util.Iterator<E> {
265
266 List cur;
267
268 ListIterator(List l) {
269 cur = l;
270 ++cntIter;
271 }
272
273 public boolean hasNext() {
274 return
275 ! cur.isEmpty();
276 }
277
278 public E next() {
279 if ( cur.isEmpty() )
280 return
281 undefined("iterator exhausted");
282
283 E res = cur.head();
284 cur = cur.tail();
285 return
286 res;
287 }
288 }
289
290 //----------------------------------------
291 // profiling
292
293 private static int cntNode = 0;
294 private static int cntIter = 0;
295
296 public static String stats() {
297 return
298 "stats for ds.persistent.list.List:\n" +
299 "# new Node() : " + cntNode + "\n" +
300 "# new ListIterator() : " + cntIter + "\n";
301 }
302}
|
Letzte Änderung: 01.11.2017 | © Prof. Dr. Uwe Schmidt |