KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gnu > lists > LList


1 // FIX BRL's use to toString
2

3 // Copyright (c) 2001, 2002, 2003 Per M.A. Bothner and Brainfood Inc.
4
// This is free software; for terms and warranty disclaimer see ./COPYING.
5

6 package gnu.lists;
7 import java.io.*;
8
9 /**
10  * Semi-abstract class for traditions Lisp-style lists.
11  * A list is implemented as a chain of Pair objects, where the
12  * 'car' field of the Pair points to a data element, and the 'cdr'
13  * field points to the next Pair. (The names 'car' and 'cdr' are
14  * historical; they refer to hardware on machines form the 60's.)
15  * Includes singleton static Empty, and the Pair sub-class.
16  * @author Per Bothner
17  */

18
19 public class LList extends ExtSequence
20   implements Sequence, Externalizable
21   /* #ifdef JAVA2 */
22   , Comparable JavaDoc
23   /* #endif */
24 {
25   /** Do not use - only public for serialization! */
26   public LList () { }
27
28   static public final LList Empty = new LList ();
29
30   /**
31    * A safe function to count the length of a list.
32    * @param obj the putative list to measure
33    * @param allowOtherSequence if a non-List Sequence is seen, allow that
34    * @return the length, or -1 for a circular list, or -2 for an improper list
35    */

36   static public int listLength(Object JavaDoc obj, boolean allowOtherSequence)
37   {
38     // Based on list-length implementation in
39
// Guy L Steele jr: "Common Lisp: The Language", 2nd edition, page 414
40
int n = 0;
41     Object JavaDoc slow = obj;
42     Object JavaDoc 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 JavaDoc obj)
76   {
77     // Over-ridden in Pair!
78
return this == obj;
79   }
80
81   /* #ifdef JAVA2 */
82   public int compareTo(Object JavaDoc obj)
83   { // Over-ridden in Pair!
84
return obj == Empty ? 0 : -1;
85   }
86   /* #endif */
87
88   public int size()
89   {
90     // Over-ridden in Pair!
91
return 0;
92   }
93
94   public boolean isEmpty()
95   {
96     // Over-ridden in Pair!
97
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 JavaDoc();
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 JavaDoc 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 JavaDoc();
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; // Overridden in Pair.
159
}
160
161   public int nextPos (int ipos)
162   {
163     return 0; // Overridden in Pair.
164
}
165
166   public Object JavaDoc getPosNext (int ipos)
167   {
168     return eofValue; // Overridden in Pair.
169
}
170
171   public Object JavaDoc getPosPrevious (int ipos)
172   {
173     return eofValue; // Overridden in Pair.
174
}
175
176   protected void setPosNext(int ipos, Object JavaDoc value)
177   {
178     if (ipos <= 0)
179       {
180     if (ipos == -1 || ! (this instanceof Pair))
181       throw new IndexOutOfBoundsException JavaDoc();
182     ((Pair) this).car = value;
183       }
184     else
185       PositionManager.getPositionObject(ipos).setNext(value);
186   }
187
188   protected void setPosPrevious(int ipos, Object JavaDoc value)
189   {
190     if (ipos <= 0)
191       {
192     if (ipos == 0 || ! (this instanceof Pair))
193       throw new IndexOutOfBoundsException JavaDoc();
194     ((Pair) this).lastPair().car = value;
195       }
196     else
197       PositionManager.getPositionObject(ipos).setPrevious(value);
198   }
199
200   public Object JavaDoc get (int index)
201   {
202     throw new IndexOutOfBoundsException JavaDoc();
203   }
204   
205   /* Count the length of a list.
206    * Note: does not catch circular lists!
207    * @param arg the list to count
208    * @return the length
209    */

210   static public final int length (Object JavaDoc arg)
211   {
212     int count = 0;
213     for ( ; arg instanceof Pair; arg = ((Pair)arg).cdr)
214       count++;
215     return count;
216   }
217
218   /* #ifdef JAVA2 */
219   public static LList makeList (java.util.List JavaDoc vals)
220   {
221     java.util.Iterator JavaDoc 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   /* #endif */
236   /* #ifndef JAVA2 */
237   // public static LList makeList (Sequence vals)
238
// {
239
// java.util.Enumeration e = ((AbstractSequence) vals).elements();
240
// LList result = LList.Empty;
241
// Pair last = null;
242
// while (e.hasMoreElements())
243
// {
244
// Pair pair = new Pair(e.nextElement(), LList.Empty);
245
// if (last == null)
246
// result = pair;
247
// else
248
// last.cdr = pair;
249
// last = pair;
250
// }
251
// return result;
252
// }
253
/* #endif */
254
255   public static LList makeList (Object JavaDoc[] 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 JavaDoc[] vals, int offset)
264   {
265     /* DEBUGGING:
266     for (int i = 0; i < vals.length; i++)
267       {
268     if (i > 0)
269       System.err.print(", ");
270     System.err.println(vals[i]);
271       }
272     System.err.println("], "+offset+")");
273     */

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   /* FIXME
281   public FVector toVector ()
282   {
283     int len = size();
284
285     Object[] values = new Object[len];
286     Object list = this;
287     for (int i=0; i < len; i++)
288       {
289     Pair pair = (Pair) list;
290     values[i] = pair.car;
291     list = pair.cdr;
292       }
293     return new FVector (values);
294   }
295   */

296
297   public void consume(Consumer out)
298   {
299     Object JavaDoc 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 JavaDoc
320   {
321   }
322
323   /**
324    * @serialData Write nothing.
325    * (Don't need to write anything.)
326    */

327   public void writeExternal(ObjectOutput out) throws IOException
328   {
329   }
330
331   public Object JavaDoc readResolve() throws ObjectStreamException
332   {
333     return Empty;
334   }
335
336   public static Pair list1(Object JavaDoc arg1)
337   {
338     return new Pair(arg1, LList.Empty);
339   }
340
341   public static Pair list2(Object JavaDoc arg1, Object JavaDoc arg2)
342   {
343     return new Pair(arg1, new Pair(arg2, LList.Empty));
344   }
345
346   public static Pair list3(Object JavaDoc arg1, Object JavaDoc arg2, Object JavaDoc arg3)
347   {
348     return new Pair(arg1, new Pair(arg2, new Pair(arg3, LList.Empty)));
349   }
350
351   public static Pair list4(Object JavaDoc arg1, Object JavaDoc arg2, Object JavaDoc arg3, Object JavaDoc arg4)
352   {
353     return new Pair(arg1, new Pair(arg2,
354                    new Pair(arg3, new Pair (arg4,
355                                 LList.Empty))));
356   }
357
358   /** Utility function used by compiler when inlining `list'. */
359   public static Pair chain1 (Pair old, Object JavaDoc arg1)
360   {
361     Pair p1 = new Pair(arg1, LList.Empty);
362     old.cdr = p1;
363     return p1;
364   }
365
366   /** Utility function used by compiler when inlining `list'. */
367   public static Pair chain4 (Pair old, Object JavaDoc arg1, Object JavaDoc arg2,
368               Object JavaDoc arg3, Object JavaDoc 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   /** Reverse a list in place, by modifying the cdr fields. */
376   public static LList reverseInPlace(Object JavaDoc list)
377   {
378     // Algorithm takes from reverse function in gcc's tree.c.
379
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 JavaDoc listTail(Object JavaDoc list, int count)
391   {
392     while (--count >= 0)
393       {
394     if (! (list instanceof Pair))
395       throw new IndexOutOfBoundsException JavaDoc("List is too short.");
396     Pair pair = (Pair) list;
397     list = pair.cdr;
398       }
399     return list;
400   }
401
402   /** SRFI-1's cons* and Common Lisp's list* function. */
403   public static Object JavaDoc consX (Object JavaDoc[] args)
404   {
405     // Error if args.length==0.
406
Object JavaDoc 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 JavaDoc toString ()
423   {
424     Object JavaDoc rest = this;
425     int i = 0;
426     StringBuffer JavaDoc sbuf = new StringBuffer JavaDoc(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   /** Helper to protect against pathological LLists (neithr Pair nor Empty). */
458   public static Object JavaDoc checkNonList (Object JavaDoc rest)
459   {
460     return rest instanceof LList ? "#<not a pair>" : rest;
461   }
462 }
463
Popular Tags