|
1
3
6 package gnu.lists;
7 import java.io.*;
8
9
18
19 public class LList extends ExtSequence
20 implements Sequence, Externalizable
21
22 , Comparable 
23
24 {
25
26 public LList () { }
27
28 static public final LList Empty = new LList ();
29
30
36 static public int listLength(Object obj, boolean allowOtherSequence)
37 {
38 int n = 0;
41 Object slow = obj;
42 Object fast = obj;
43 for (;;)
44 {
45 if (fast == Empty)
46 return n;
47 if (! (fast instanceof Pair))
48 {
49 if (fast instanceof Sequence && allowOtherSequence)
50 {
51 int j = ((Sequence) fast).size ();
52 return j >= 0 ? n + j : j;
53 }
54 return -2;
55 }
56 Pair fast_pair = (Pair) fast;
57 if (fast_pair.cdr == Empty)
58 return n+1;
59 if (fast == slow && n > 0)
60 return -1;
61 if (! (fast_pair.cdr instanceof Pair))
62 {
63 n++;
64 fast = fast_pair.cdr;
65 continue;
66 }
67 if (!(slow instanceof Pair))
68 return -2;
69 slow = ((Pair)slow).cdr;
70 fast = ((Pair)fast_pair.cdr).cdr;
71 n += 2;
72 }
73 }
74
75 public boolean equals (Object obj)
76 {
77 return this == obj;
79 }
80
81
82 public int compareTo(Object obj)
83 { return obj == Empty ? 0 : -1;
85 }
86
87
88 public int size()
89 {
90 return 0;
92 }
93
94 public boolean isEmpty()
95 {
96 return true;
98 }
99
100 public SeqPosition getIterator(int index)
101 {
102 return new LListPosition(this, index, false);
103 }
104
105 public int createPos(int index, boolean isAfter)
106 {
107 ExtPosition pos = new LListPosition(this, index, isAfter);
108 return PositionManager.manager.register(pos);
109 }
110
111 public int createRelativePos(int pos, int delta, boolean isAfter)
112 {
113 boolean old_after = isAfterPos(pos);
114 if (delta < 0 || pos == 0)
115 return super.createRelativePos(pos, delta, isAfter);
116 if (delta == 0)
117 {
118 if (isAfter == old_after)
119 return copyPos(pos);
120 if (isAfter && ! old_after)
121 return super.createRelativePos(pos, delta, isAfter);
122 }
123 if (pos < 0)
124 throw new IndexOutOfBoundsException ();
125 LListPosition old = (LListPosition) PositionManager.getPositionObject(pos);
126 if (old.xpos == null)
127 return super.createRelativePos(pos, delta, isAfter);
128 LListPosition it = new LListPosition(old);
129 Object it_xpos = it.xpos;
130 int it_ipos = it.ipos;
131 if (isAfter && ! old_after)
132 {
133 delta--;
134 it_ipos += 3;
135 }
136 if (! isAfter && old_after)
137 {
138 delta++;
139 it_ipos -= 3;
140 }
141 for (;;)
142 {
143 if (! (it_xpos instanceof Pair))
144 throw new IndexOutOfBoundsException ();
145 if (--delta < 0)
146 break;
147 Pair p = (Pair) it_xpos;
148 it_ipos += 2;
149 it_xpos = p.cdr;
150 }
151 it.ipos = it_ipos;
152 it.xpos = it_xpos;
153 return PositionManager.manager.register(it);
154 }
155
156 public boolean hasNext (int ipos)
157 {
158 return false; }
160
161 public int nextPos (int ipos)
162 {
163 return 0; }
165
166 public Object getPosNext (int ipos)
167 {
168 return eofValue; }
170
171 public Object getPosPrevious (int ipos)
172 {
173 return eofValue; }
175
176 protected void setPosNext(int ipos, Object value)
177 {
178 if (ipos <= 0)
179 {
180 if (ipos == -1 || ! (this instanceof Pair))
181 throw new IndexOutOfBoundsException ();
182 ((Pair) this).car = value;
183 }
184 else
185 PositionManager.getPositionObject(ipos).setNext(value);
186 }
187
188 protected void setPosPrevious(int ipos, Object value)
189 {
190 if (ipos <= 0)
191 {
192 if (ipos == 0 || ! (this instanceof Pair))
193 throw new IndexOutOfBoundsException ();
194 ((Pair) this).lastPair().car = value;
195 }
196 else
197 PositionManager.getPositionObject(ipos).setPrevious(value);
198 }
199
200 public Object get (int index)
201 {
202 throw new IndexOutOfBoundsException ();
203 }
204
205
210 static public final int length (Object arg)
211 {
212 int count = 0;
213 for ( ; arg instanceof Pair; arg = ((Pair)arg).cdr)
214 count++;
215 return count;
216 }
217
218
219 public static LList makeList (java.util.List vals)
220 {
221 java.util.Iterator e = vals.iterator();
222 LList result = LList.Empty;
223 Pair last = null;
224 while (e.hasNext())
225 {
226 Pair pair = new Pair(e.next(), LList.Empty);
227 if (last == null)
228 result = pair;
229 else
230 last.cdr = pair;
231 last = pair;
232 }
233 return result;
234 }
235
236
237
254
255 public static LList makeList (Object [] vals, int offset, int length)
256 {
257 LList result = LList.Empty;
258 for (int i = length; --i >= 0; )
259 result = new Pair (vals[offset+i], result);
260 return result;
261 }
262
263 public static LList makeList (Object [] vals, int offset)
264 {
265
274 LList result = LList.Empty;
275 for (int i = vals.length - offset; --i >= 0; )
276 result = new Pair (vals[offset+i], result);
277 return result;
278 }
279
280
296
297 public void consume(Consumer out)
298 {
299 Object list = this;
300 out.beginGroup("list");
301 while (list instanceof Pair)
302 {
303 if (list != this)
304 out.write(' ');
305 Pair pair = (Pair) list;
306 out.writeObject(pair.car);
307 list = pair.cdr;
308 }
309 if (list != Empty)
310 {
311 out.write(' ');
312 out.write(". ");
313 out.writeObject(checkNonList(list));
314 }
315 out.endGroup();
316 }
317
318 public void readExternal(ObjectInput in)
319 throws IOException, ClassNotFoundException
320 {
321 }
322
323
327 public void writeExternal(ObjectOutput out) throws IOException
328 {
329 }
330
331 public Object readResolve() throws ObjectStreamException
332 {
333 return Empty;
334 }
335
336 public static Pair list1(Object arg1)
337 {
338 return new Pair(arg1, LList.Empty);
339 }
340
341 public static Pair list2(Object arg1, Object arg2)
342 {
343 return new Pair(arg1, new Pair(arg2, LList.Empty));
344 }
345
346 public static Pair list3(Object arg1, Object arg2, Object arg3)
347 {
348 return new Pair(arg1, new Pair(arg2, new Pair(arg3, LList.Empty)));
349 }
350
351 public static Pair list4(Object arg1, Object arg2, Object arg3, Object arg4)
352 {
353 return new Pair(arg1, new Pair(arg2,
354 new Pair(arg3, new Pair (arg4,
355 LList.Empty))));
356 }
357
358
359 public static Pair chain1 (Pair old, Object arg1)
360 {
361 Pair p1 = new Pair(arg1, LList.Empty);
362 old.cdr = p1;
363 return p1;
364 }
365
366
367 public static Pair chain4 (Pair old, Object arg1, Object arg2,
368 Object arg3, Object arg4)
369 {
370 Pair p4 = new Pair(arg4, LList.Empty);
371 old.cdr = new Pair(arg1, new Pair(arg2, new Pair(arg3, p4)));
372 return p4;
373 }
374
375
376 public static LList reverseInPlace(Object list)
377 {
378 LList prev = Empty;
380 while (list != Empty)
381 {
382 Pair pair = (Pair) list;
383 list = pair.cdr;
384 pair.cdr = prev;
385 prev = pair;
386 }
387 return prev;
388 }
389
390 public static Object listTail(Object list, int count)
391 {
392 while (--count >= 0)
393 {
394 if (! (list instanceof Pair))
395 throw new IndexOutOfBoundsException ("List is too short.");
396 Pair pair = (Pair) list;
397 list = pair.cdr;
398 }
399 return list;
400 }
401
402
403 public static Object consX (Object [] args)
404 {
405 Object first = args[0];
407 int n = args.length - 1;
408 if (n <= 0)
409 return first;
410 Pair result = new Pair(first, null);
411 Pair prev = result;
412 for (int i = 1; i < n; i++)
413 {
414 Pair next = new Pair(args[i], null);
415 prev.cdr = next;
416 prev = next;
417 }
418 prev.cdr = args[n];
419 return result;
420 }
421
422 public String toString ()
423 {
424 Object rest = this;
425 int i = 0;
426 StringBuffer sbuf = new StringBuffer (100);
427 sbuf.append('(');
428 for (;;)
429 {
430 if (rest == Empty)
431 break;
432 if (i > 0)
433 sbuf.append(' ');
434 if (i >= 10)
435 {
436 sbuf.append("...");
437 break;
438 }
439 if (rest instanceof Pair)
440 {
441 Pair pair = (Pair) rest;
442 sbuf.append(pair.car);
443 rest = pair.cdr;
444 }
445 else
446 {
447 sbuf.append(". ");
448 sbuf.append(checkNonList(rest));
449 break;
450 }
451 i++;
452 }
453 sbuf.append(')');
454 return sbuf.toString();
455 }
456
457
458 public static Object checkNonList (Object rest)
459 {
460 return rest instanceof LList ? "#<not a pair>" : rest;
461 }
462 }
463 |
Popular Tags |
Java API By Example, From Geeks To Geeks.