001: // Copyright (c) 2001 Per M.A. Bothner and Brainfood Inc.
002: // This is free software; for terms and warranty disclaimer see ./COPYING.
003:
004: package gnu.lists;
005:
006: import java.io.PrintWriter;
007: import java.io.*;
008:
009: /**
010: * Semi-abstract class for traditions Lisp-style lists.
011: * A list is implemented as a chain of Pair objects, where the
012: * 'car' field of the Pair points to a data element, and the 'cdr'
013: * field points to the next Pair. (The names 'car' and 'cdr' are
014: * historical; they refer to hardware on machines form the 60's.)
015: * Includes singleton static Empty, and the Pair sub-class.
016: * @author Per Bothner
017: */
018:
019: public class LList extends AbstractSequence implements Sequence,
020: Externalizable {
021: /** Do not use - only public for serialization! */
022: public LList() {
023: }
024:
025: static public final LList Empty = new LList();
026:
027: /**
028: * A safe function to count the length of a list.
029: * @param obj the putative list to measure
030: * @param allowOtherSequence if a non-List Sequence is seen, allow that
031: * @return the length, or -1 for a circular list, or -2 for an improper list
032: */
033: static public int listLength(Object obj, boolean allowOtherSequence) {
034: // Based on list-length implementation in
035: // Guy L Steele jr: "Common Lisp: The Language", 2nd edition, page 414
036: int n = 0;
037: Object slow = obj;
038: Object fast = obj;
039: for (;;) {
040: if (fast == Empty)
041: return n;
042: if (!(fast instanceof Pair)) {
043: if (fast instanceof Sequence && allowOtherSequence) {
044: int j = ((Sequence) fast).size();
045: return j >= 0 ? n + j : j;
046: }
047: return -2;
048: }
049: Pair fast_pair = (Pair) fast;
050: if (fast_pair.cdr == Empty)
051: return n + 1;
052: if (fast == slow && n > 0)
053: return -1;
054: if (!(fast_pair.cdr instanceof Pair)) {
055: n++;
056: fast = fast_pair.cdr;
057: continue;
058: }
059: if (!(slow instanceof Pair))
060: return -2;
061: slow = ((Pair) slow).cdr;
062: fast = ((Pair) fast_pair.cdr).cdr;
063: n += 2;
064: }
065: }
066:
067: public boolean equals(Object obj) {
068: // Over-ridden in Pair!
069: return this == obj;
070: }
071:
072: public int size() {
073: // Over-ridden in Pair!
074: return 0;
075: }
076:
077: public boolean isEmpty() {
078: // Over-ridden in Pair!
079: return true;
080: }
081:
082: // Positions are represented in a non-obvious way. After a next(),
083: // xpos points to *two* Pairs before the logical iterator position
084: // (the cursor). This is because of the requirement for remove(),
085: // which needs to be able to remove the element *before* the cursor.
086: // But to unlink that element, we need to change the 'next' field
087: // of the Pair before that again.
088: // However, after a call to 'previous', we cannot cheaply move the
089: // xpos pointer backwards, so we leave it as is. Therefore, we
090: // get the rule that when isAfter() is false the cursor position is
091: // after the Pair pointed by xpos; when isAfter() is true then
092: // the cursor position is after the Pair ((Pair) xpos).cdr).
093: // If the cursor position is too early in the list to satisfy this
094: // invariant, then xpos==null.
095: // ??? Can we handle improper lists (whose tail is a sequence)? FIXME
096:
097: public void makePosition(int index, boolean isAfter,
098: PositionContainer poses, int positionNumber) {
099: int ipos = (index << 1) | (isAfter ? 1 : 0);
100: Object p = this ;
101: int skip = index;
102: if (isAfter) {
103: skip -= 2;
104: } else {
105: skip -= 1;
106: }
107: if (skip < 0)
108: p = null;
109: else {
110: while (--skip >= 0) {
111: p = ((Pair) p).cdr;
112: }
113: }
114: poses.setPosition(positionNumber, ipos, p);
115: poses.setSequence(positionNumber, this );
116: }
117:
118: protected int nextIndex(int ipos, Object xpos) {
119: return ipos >>> 1;
120: }
121:
122: protected boolean hasNext(int ipos, Object xpos) {
123: // Equivalent to getNext(ipos, xpos) != eofValue.
124: Object next;
125: if (xpos == null) {
126: if ((ipos >> 1) == 0)
127: return this != Empty;
128: return ((Pair) this ).cdr != Empty;
129: } else
130: next = ((Pair) xpos).cdr;
131: if ((ipos & 1) > 0) // if isAfter
132: next = ((Pair) next).cdr;
133: return next != Empty;
134: }
135:
136: public Object getNext(int ipos, Object xpos) {
137: int isAfter = (ipos & 1);
138: Object next;
139: if (isAfter > 0) {
140: if (xpos == null) {
141: next = this ;
142: if ((ipos >> 1) != 0)
143: next = ((Pair) next).cdr;
144: } else
145: next = ((Pair) (((Pair) xpos).cdr)).cdr;
146: } else {
147: if (xpos == null)
148: next = this ;
149: else
150: next = xpos;
151: }
152: if (next == Empty)
153: return eofValue;
154: return ((Pair) next).car;
155: }
156:
157: public Object get(int index) {
158: throw new ArrayIndexOutOfBoundsException(index);
159: }
160:
161: /* Count the length of a list.
162: * Note: does not catch circular lists!
163: * @param arg the list to count
164: * @return the length
165: */
166: static public final int length(Object arg) {
167: int count = 0;
168: for (; arg instanceof Pair; arg = ((Pair) arg).cdr)
169: count++;
170: return count;
171: }
172:
173: protected boolean isAfter(int ipos, Object xpos) {
174: return (ipos & 1) != 0;
175: }
176:
177: public boolean gotoNext(PositionContainer posSet, int posNumber) {
178: int ipos = posSet.getPositionInt(posNumber);
179: Object xpos = posSet.getPositionPtr(posNumber);
180: boolean isAfter = (ipos & 1) != 0;
181: if (xpos != null) {
182: if (isAfter)
183: xpos = ((Pair) xpos).cdr;
184: if (((Pair) xpos).cdr == Empty)
185: return false;
186: ipos = (ipos | 1) + 2;
187: } else if ((ipos >> 1) == 0) // position is 0
188: {
189: if (this == Empty)
190: return false;
191: ipos = (1 << 1) | 1;
192: } else // position is 1, iAfter must be true
193: {
194: xpos = this ;
195: if (((Pair) xpos).cdr == Empty)
196: return false;
197: ipos = (2 << 1) | 1;
198: }
199: posSet.setPosition(posNumber, ipos, xpos);
200: return true;
201: }
202:
203: public static LList makeList(Sequence vals) {
204: java.util.Enumeration e = ((AbstractSequence) vals).elements();
205: LList result = LList.Empty;
206: Pair last = null;
207: for (int i = 0; e.hasMoreElements(); i++) {
208: Pair pair = new Pair(e.nextElement(), LList.Empty);
209: if (last == null)
210: result = pair;
211: else
212: last.cdr = pair;
213: last = pair;
214: }
215: return result;
216: }
217:
218: public static LList makeList(Object[] vals, int offset, int length) {
219: LList result = LList.Empty;
220: for (int i = length; --i >= 0;)
221: result = new Pair(vals[offset + i], result);
222: return result;
223: }
224:
225: public static LList makeList(Object[] vals, int offset) {
226: /* DEBUGGING:
227: for (int i = 0; i < vals.length; i++)
228: {
229: if (i > 0)
230: System.err.print(", ");
231: System.err.println(vals[i]);
232: }
233: System.err.println("], "+offset+")");
234: */
235: LList result = LList.Empty;
236: for (int i = vals.length - offset; --i >= 0;)
237: result = new Pair(vals[offset + i], result);
238: return result;
239: }
240:
241: /* FIXME
242: public FVector toVector ()
243: {
244: int len = size();
245:
246: Object[] values = new Object[len];
247: Object list = this;
248: for (int i=0; i < len; i++)
249: {
250: Pair pair = (Pair) list;
251: values[i] = pair.car;
252: list = pair.cdr;
253: }
254: return new FVector (values);
255: }
256: */
257:
258: public void consume(Consumer out) {
259: Object list = this ;
260: String typeName = "list";
261: String type = typeName;
262: out.beginGroup(typeName, type);
263: while (list instanceof Pair) {
264: if (list != this )
265: out.writeChar(' ');
266: Pair pair = (Pair) list;
267: out.writeObject(pair.car);
268: list = pair.cdr;
269: }
270: if (list != Empty) {
271: out.writeChar(' ');
272: out.writeChars(". ");
273: out.writeObject(list);
274: }
275: out.endGroup(typeName);
276: }
277:
278: public void readExternal(ObjectInput in) throws IOException,
279: ClassNotFoundException {
280: }
281:
282: /**
283: * @serialData Write nothing.
284: * (Don't need to write anything.)
285: */
286: public void writeExternal(ObjectOutput out) throws IOException {
287: }
288:
289: public Object readResolve() throws ObjectStreamException {
290: return Empty;
291: }
292:
293: public static Pair list1(Object arg1) {
294: return new Pair(arg1, LList.Empty);
295: }
296:
297: public static Pair list2(Object arg1, Object arg2) {
298: return new Pair(arg1, new Pair(arg2, LList.Empty));
299: }
300:
301: public static Pair list3(Object arg1, Object arg2, Object arg3) {
302: return new Pair(arg1, new Pair(arg2,
303: new Pair(arg3, LList.Empty)));
304: }
305:
306: public static Pair list4(Object arg1, Object arg2, Object arg3,
307: Object arg4) {
308: return new Pair(arg1, new Pair(arg2, new Pair(arg3, new Pair(
309: arg4, LList.Empty))));
310: }
311:
312: /** Utility function used by compiler when inlining `list'. */
313: public static Pair chain1(Pair old, Object arg1) {
314: Pair p1 = new Pair(arg1, LList.Empty);
315: old.cdr = p1;
316: return p1;
317: }
318:
319: /** Utility function used by compiler when inlining `list'. */
320: public static Pair chain4(Pair old, Object arg1, Object arg2,
321: Object arg3, Object arg4) {
322: Pair p4 = new Pair(arg4, LList.Empty);
323: old.cdr = new Pair(arg1, new Pair(arg2, new Pair(arg3, p4)));
324: return p4;
325: }
326:
327: /** Reverse a list in place, by modifying the cdr fields. */
328: public static LList reverseInPlace(Object list) {
329: // Algorithm takes from reverse function in gcc's tree.c.
330: LList prev = Empty;
331: while (list != Empty) {
332: Pair pair = (Pair) list;
333: list = pair.cdr;
334: pair.cdr = prev;
335: prev = pair;
336: }
337: return prev;
338: }
339:
340: public static Object listTail(Object list, int count) {
341: while (--count >= 0) {
342: if (!(list instanceof Pair))
343: throw new IndexOutOfBoundsException(
344: "List is too short.");
345: Pair pair = (Pair) list;
346: list = pair.cdr;
347: }
348: return list;
349: }
350: }
|