001: // FIX BRL's use to toString
002:
003: // Copyright (c) 2001, 2002, 2003 Per M.A. Bothner and Brainfood Inc.
004: // This is free software; for terms and warranty disclaimer see ./COPYING.
005:
006: package gnu.lists;
007:
008: import java.io.*;
009:
010: /**
011: * Semi-abstract class for traditions Lisp-style lists.
012: * A list is implemented as a chain of Pair objects, where the
013: * 'car' field of the Pair points to a data element, and the 'cdr'
014: * field points to the next Pair. (The names 'car' and 'cdr' are
015: * historical; they refer to hardware on machines form the 60's.)
016: * Includes singleton static Empty, and the Pair sub-class.
017: * @author Per Bothner
018: */
019:
020: public class LList extends ExtSequence implements Sequence,
021: Externalizable
022: /* #ifdef JAVA2 */
023: , Comparable
024: /* #endif */
025: {
026: /** Do not use - only public for serialization! */
027: public LList() {
028: }
029:
030: static public final LList Empty = new LList();
031:
032: /**
033: * A safe function to count the length of a list.
034: * @param obj the putative list to measure
035: * @param allowOtherSequence if a non-List Sequence is seen, allow that
036: * @return the length, or -1 for a circular list, or -2 for an improper list
037: */
038: static public int listLength(Object obj, boolean allowOtherSequence) {
039: // Based on list-length implementation in
040: // Guy L Steele jr: "Common Lisp: The Language", 2nd edition, page 414
041: int n = 0;
042: Object slow = obj;
043: Object fast = obj;
044: for (;;) {
045: if (fast == Empty)
046: return n;
047: if (!(fast instanceof Pair)) {
048: if (fast instanceof Sequence && allowOtherSequence) {
049: int j = ((Sequence) fast).size();
050: return j >= 0 ? n + j : j;
051: }
052: return -2;
053: }
054: Pair fast_pair = (Pair) fast;
055: if (fast_pair.cdr == Empty)
056: return n + 1;
057: if (fast == slow && n > 0)
058: return -1;
059: if (!(fast_pair.cdr instanceof Pair)) {
060: n++;
061: fast = fast_pair.cdr;
062: continue;
063: }
064: if (!(slow instanceof Pair))
065: return -2;
066: slow = ((Pair) slow).cdr;
067: fast = ((Pair) fast_pair.cdr).cdr;
068: n += 2;
069: }
070: }
071:
072: public boolean equals(Object obj) {
073: // Over-ridden in Pair!
074: return this == obj;
075: }
076:
077: /* #ifdef JAVA2 */
078: public int compareTo(Object obj) { // Over-ridden in Pair!
079: return obj == Empty ? 0 : -1;
080: }
081:
082: /* #endif */
083:
084: public int size() {
085: // Over-ridden in Pair!
086: return 0;
087: }
088:
089: public boolean isEmpty() {
090: // Over-ridden in Pair!
091: return true;
092: }
093:
094: public SeqPosition getIterator(int index) {
095: return new LListPosition(this , index, false);
096: }
097:
098: public int createPos(int index, boolean isAfter) {
099: ExtPosition pos = new LListPosition(this , index, isAfter);
100: return PositionManager.manager.register(pos);
101: }
102:
103: public int createRelativePos(int pos, int delta, boolean isAfter) {
104: boolean old_after = isAfterPos(pos);
105: if (delta < 0 || pos == 0)
106: return super .createRelativePos(pos, delta, isAfter);
107: if (delta == 0) {
108: if (isAfter == old_after)
109: return copyPos(pos);
110: if (isAfter && !old_after)
111: return super .createRelativePos(pos, delta, isAfter);
112: }
113: if (pos < 0)
114: throw new IndexOutOfBoundsException();
115: LListPosition old = (LListPosition) PositionManager
116: .getPositionObject(pos);
117: if (old.xpos == null)
118: return super .createRelativePos(pos, delta, isAfter);
119: LListPosition it = new LListPosition(old);
120: Object it_xpos = it.xpos;
121: int it_ipos = it.ipos;
122: if (isAfter && !old_after) {
123: delta--;
124: it_ipos += 3;
125: }
126: if (!isAfter && old_after) {
127: delta++;
128: it_ipos -= 3;
129: }
130: for (;;) {
131: if (!(it_xpos instanceof Pair))
132: throw new IndexOutOfBoundsException();
133: if (--delta < 0)
134: break;
135: Pair p = (Pair) it_xpos;
136: it_ipos += 2;
137: it_xpos = p.cdr;
138: }
139: it.ipos = it_ipos;
140: it.xpos = it_xpos;
141: return PositionManager.manager.register(it);
142: }
143:
144: public boolean hasNext(int ipos) {
145: return false; // Overridden in Pair.
146: }
147:
148: public int nextPos(int ipos) {
149: return 0; // Overridden in Pair.
150: }
151:
152: public Object getPosNext(int ipos) {
153: return eofValue; // Overridden in Pair.
154: }
155:
156: public Object getPosPrevious(int ipos) {
157: return eofValue; // Overridden in Pair.
158: }
159:
160: protected void setPosNext(int ipos, Object value) {
161: if (ipos <= 0) {
162: if (ipos == -1 || !(this instanceof Pair))
163: throw new IndexOutOfBoundsException();
164: ((Pair) this ).car = value;
165: } else
166: PositionManager.getPositionObject(ipos).setNext(value);
167: }
168:
169: protected void setPosPrevious(int ipos, Object value) {
170: if (ipos <= 0) {
171: if (ipos == 0 || !(this instanceof Pair))
172: throw new IndexOutOfBoundsException();
173: ((Pair) this ).lastPair().car = value;
174: } else
175: PositionManager.getPositionObject(ipos).setPrevious(value);
176: }
177:
178: public Object get(int index) {
179: throw new IndexOutOfBoundsException();
180: }
181:
182: /* Count the length of a list.
183: * Note: does not catch circular lists!
184: * @param arg the list to count
185: * @return the length
186: */
187: static public final int length(Object arg) {
188: int count = 0;
189: for (; arg instanceof Pair; arg = ((Pair) arg).cdr)
190: count++;
191: return count;
192: }
193:
194: /* #ifdef JAVA2 */
195: public static LList makeList(java.util.List vals) {
196: java.util.Iterator e = vals.iterator();
197: LList result = LList.Empty;
198: Pair last = null;
199: while (e.hasNext()) {
200: Pair pair = new Pair(e.next(), LList.Empty);
201: if (last == null)
202: result = pair;
203: else
204: last.cdr = pair;
205: last = pair;
206: }
207: return result;
208: }
209:
210: /* #endif */
211: /* #ifndef JAVA2 */
212: // public static LList makeList (Sequence vals)
213: // {
214: // java.util.Enumeration e = ((AbstractSequence) vals).elements();
215: // LList result = LList.Empty;
216: // Pair last = null;
217: // while (e.hasMoreElements())
218: // {
219: // Pair pair = new Pair(e.nextElement(), LList.Empty);
220: // if (last == null)
221: // result = pair;
222: // else
223: // last.cdr = pair;
224: // last = pair;
225: // }
226: // return result;
227: // }
228: /* #endif */
229:
230: public static LList makeList(Object[] vals, int offset, int length) {
231: LList result = LList.Empty;
232: for (int i = length; --i >= 0;)
233: result = new Pair(vals[offset + i], result);
234: return result;
235: }
236:
237: public static LList makeList(Object[] vals, int offset) {
238: /* DEBUGGING:
239: for (int i = 0; i < vals.length; i++)
240: {
241: if (i > 0)
242: System.err.print(", ");
243: System.err.println(vals[i]);
244: }
245: System.err.println("], "+offset+")");
246: */
247: LList result = LList.Empty;
248: for (int i = vals.length - offset; --i >= 0;)
249: result = new Pair(vals[offset + i], result);
250: return result;
251: }
252:
253: /* FIXME
254: public FVector toVector ()
255: {
256: int len = size();
257:
258: Object[] values = new Object[len];
259: Object list = this;
260: for (int i=0; i < len; i++)
261: {
262: Pair pair = (Pair) list;
263: values[i] = pair.car;
264: list = pair.cdr;
265: }
266: return new FVector (values);
267: }
268: */
269:
270: public void consume(Consumer out) {
271: Object list = this ;
272: out.startElement("list");
273: while (list instanceof Pair) {
274: if (list != this )
275: out.write(' ');
276: Pair pair = (Pair) list;
277: out.writeObject(pair.car);
278: list = pair.cdr;
279: }
280: if (list != Empty) {
281: out.write(' ');
282: out.write(". ");
283: out.writeObject(checkNonList(list));
284: }
285: out.endElement();
286: }
287:
288: public void readExternal(ObjectInput in) throws IOException,
289: ClassNotFoundException {
290: }
291:
292: /**
293: * @serialData Write nothing.
294: * (Don't need to write anything.)
295: */
296: public void writeExternal(ObjectOutput out) throws IOException {
297: }
298:
299: public Object readResolve() throws ObjectStreamException {
300: return Empty;
301: }
302:
303: public static Pair list1(Object arg1) {
304: return new Pair(arg1, LList.Empty);
305: }
306:
307: public static Pair list2(Object arg1, Object arg2) {
308: return new Pair(arg1, new Pair(arg2, LList.Empty));
309: }
310:
311: public static Pair list3(Object arg1, Object arg2, Object arg3) {
312: return new Pair(arg1, new Pair(arg2,
313: new Pair(arg3, LList.Empty)));
314: }
315:
316: public static Pair list4(Object arg1, Object arg2, Object arg3,
317: Object arg4) {
318: return new Pair(arg1, new Pair(arg2, new Pair(arg3, new Pair(
319: arg4, LList.Empty))));
320: }
321:
322: /** Utility function used by compiler when inlining `list'. */
323: public static Pair chain1(Pair old, Object arg1) {
324: Pair p1 = new Pair(arg1, LList.Empty);
325: old.cdr = p1;
326: return p1;
327: }
328:
329: /** Utility function used by compiler when inlining `list'. */
330: public static Pair chain4(Pair old, Object arg1, Object arg2,
331: Object arg3, Object arg4) {
332: Pair p4 = new Pair(arg4, LList.Empty);
333: old.cdr = new Pair(arg1, new Pair(arg2, new Pair(arg3, p4)));
334: return p4;
335: }
336:
337: /** Reverse a list in place, by modifying the cdr fields. */
338: public static LList reverseInPlace(Object list) {
339: // Algorithm takes from reverse function in gcc's tree.c.
340: LList prev = Empty;
341: while (list != Empty) {
342: Pair pair = (Pair) list;
343: list = pair.cdr;
344: pair.cdr = prev;
345: prev = pair;
346: }
347: return prev;
348: }
349:
350: public static Object listTail(Object list, int count) {
351: while (--count >= 0) {
352: if (!(list instanceof Pair))
353: throw new IndexOutOfBoundsException(
354: "List is too short.");
355: Pair pair = (Pair) list;
356: list = pair.cdr;
357: }
358: return list;
359: }
360:
361: /** SRFI-1's cons* and Common Lisp's list* function. */
362: public static Object consX(Object[] args) {
363: // Error if args.length==0.
364: Object first = args[0];
365: int n = args.length - 1;
366: if (n <= 0)
367: return first;
368: Pair result = new Pair(first, null);
369: Pair prev = result;
370: for (int i = 1; i < n; i++) {
371: Pair next = new Pair(args[i], null);
372: prev.cdr = next;
373: prev = next;
374: }
375: prev.cdr = args[n];
376: return result;
377: }
378:
379: public String toString() {
380: Object rest = this ;
381: int i = 0;
382: StringBuffer sbuf = new StringBuffer(100);
383: sbuf.append('(');
384: for (;;) {
385: if (rest == Empty)
386: break;
387: if (i > 0)
388: sbuf.append(' ');
389: if (i >= 10) {
390: sbuf.append("...");
391: break;
392: }
393: if (rest instanceof Pair) {
394: Pair pair = (Pair) rest;
395: sbuf.append(pair.car);
396: rest = pair.cdr;
397: } else {
398: sbuf.append(". ");
399: sbuf.append(checkNonList(rest));
400: break;
401: }
402: i++;
403: }
404: sbuf.append(')');
405: return sbuf.toString();
406: }
407:
408: /** Helper to protect against pathological LLists (neithr Pair nor Empty). */
409: public static Object checkNonList(Object rest) {
410: return rest instanceof LList ? "#<not a pair>" : rest;
411: }
412: }
|