001: // Copyright (c) 2001, 2003 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.*;
007:
008: /** A "pair" object, as used in Lisp-like languages.
009: * When used to implement a list, the 'car' field contains an
010: * element's value, and the 'cdr' field points to either the next Pair
011: * or LList.Empty (which represents the end of the list). (The names
012: * "car" and "cdr" [pronounced "coulder"] are historical; better names
013: * might be "value" and "next".) While a Pair is normally usued to
014: * implement a linked list, sometimes the 'cdr' field ponus to some
015: * other non-list object; this is traditionally callled a "dotted list".
016: */
017:
018: public class Pair extends LList implements Externalizable {
019: public Object car;
020: public Object cdr;
021:
022: public Pair(Object carval, Object cdrval) {
023: car = carval;
024: cdr = cdrval;
025: }
026:
027: public Pair() {
028: }
029:
030: public int size() {
031: int n = listLength(this , true);
032: if (n >= 0)
033: return n;
034: if (n == -1)
035: return Integer.MAX_VALUE;
036: throw new RuntimeException("not a true list");
037: }
038:
039: public boolean isEmpty() {
040: return false;
041: }
042:
043: // A generalization of LList.list_length
044: // FIXME is this needed, given listLength?
045: public int length() {
046: // Based on list-length implementation in
047: // Guy L Steele jr: "Common Lisp: The Language", 2nd edition, page 414
048: int n = 0;
049: Object slow = this ;
050: Object fast = this ;
051: for (;;) {
052: if (fast == Empty)
053: return n;
054: if (!(fast instanceof Pair)) {
055: if (fast instanceof Sequence) {
056: int j = ((Sequence) fast).size();
057: return j >= 0 ? n + j : j;
058: }
059: return -2;
060: }
061: Pair fast_pair = (Pair) fast;
062: if (fast_pair.cdr == Empty)
063: return n + 1;
064: if (fast == slow && n > 0)
065: return -1;
066: if (!(fast_pair.cdr instanceof Pair)) {
067: n++;
068: fast = fast_pair.cdr;
069: continue;
070: }
071: if (!(slow instanceof Pair))
072: return -2;
073: slow = ((Pair) slow).cdr;
074: fast = ((Pair) fast_pair.cdr).cdr;
075: n += 2;
076: }
077: }
078:
079: public boolean hasNext(int ipos) {
080: if (ipos <= 0)
081: return ipos == 0;
082: return PositionManager.getPositionObject(ipos).hasNext();
083: }
084:
085: public int nextPos(int ipos) {
086: if (ipos <= 0) {
087: if (ipos < 0)
088: return 0;
089: return PositionManager.manager.register(new LListPosition(
090: this , 1, true));
091: }
092: LListPosition it = (LListPosition) PositionManager
093: .getPositionObject(ipos);
094: return it.gotoNext() ? ipos : 0;
095: }
096:
097: public Object getPosNext(int ipos) {
098: if (ipos <= 0)
099: return ipos == 0 ? car : eofValue;
100: return PositionManager.getPositionObject(ipos).getNext();
101: }
102:
103: public Object getPosPrevious(int ipos) {
104: if (ipos <= 0)
105: return ipos == 0 ? eofValue : lastPair().car;
106: return PositionManager.getPositionObject(ipos).getPrevious();
107: }
108:
109: public final Pair lastPair() {
110: Pair pair = this ;
111: for (;;) {
112: Object next = pair.cdr;
113: if (next instanceof Pair)
114: pair = (Pair) next;
115: else
116: return pair;
117: }
118: }
119:
120: /*
121: public void print(java.io.PrintWriter ps)
122: {
123: ps.print("(");
124: printNoParen(this, ps);
125: ps.print(")");
126: }
127: */
128:
129: public int hashCode() {
130: // Compatible with the AbstractSequence hashCode for true lists.
131: int hash = 1;
132: Object list = this ;
133: while (list instanceof Pair) {
134: Pair pair = (Pair) list;
135: Object obj = pair.car;
136: hash = 31 * hash + (obj == null ? 0 : obj.hashCode());
137: list = pair.cdr;
138: }
139: if (list != LList.Empty && list != null)
140: hash = hash ^ list.hashCode();
141: return hash;
142: }
143:
144: static public boolean equals(Pair pair1, Pair pair2) {
145: if (pair1 == pair2)
146: return true;
147: if (pair1 == null || pair2 == null)
148: return false;
149: for (;;) {
150: Object x1 = pair1.car;
151: Object x2 = pair2.car;
152: if (x1 != x2 && (x1 == null || !x1.equals(x2)))
153: return false;
154: x1 = pair1.cdr;
155: x2 = pair2.cdr;
156: if (x1 == x2)
157: return true;
158: if (x1 == null || x2 == null)
159: return false;
160: if (!(x1 instanceof Pair) || !(x2 instanceof Pair))
161: return x1.equals(x2);
162: pair1 = (Pair) x1;
163: pair2 = (Pair) x2;
164:
165: }
166: }
167:
168: /* #ifdef JAVA2 */
169: static public int compareTo(Pair pair1, Pair pair2) {
170: if (pair1 == pair2)
171: return 0;
172: if (pair1 == null)
173: return -1;
174: if (pair2 == null)
175: return 1;
176: for (;;) {
177: Object x1 = pair1.car;
178: Object x2 = pair2.car;
179: int d = ((Comparable) x1).compareTo((Comparable) x2);
180: if (d != 0)
181: return d;
182: x1 = pair1.cdr;
183: x2 = pair2.cdr;
184: if (x1 == x2)
185: return 0;
186: if (x1 == null)
187: return -1;
188: if (x2 == null)
189: return 1;
190: if (!(x1 instanceof Pair) || !(x2 instanceof Pair))
191: return ((Comparable) x1).compareTo((Comparable) x2);
192: pair1 = (Pair) x1;
193: pair2 = (Pair) x2;
194: }
195: }
196:
197: public int compareTo(Object obj) {
198: if (obj == Empty)
199: return 1;
200: else
201: return compareTo(this , (Pair) obj);
202: }
203:
204: /* #endif */
205:
206: public Object get(int index) {
207: Pair pair = this ;
208: int i = index;
209: while (i > 0) {
210: i--;
211: if (pair.cdr instanceof Pair)
212: pair = (Pair) pair.cdr;
213: else if (pair.cdr instanceof Sequence)
214: return ((Sequence) pair.cdr).get(i);
215: else
216: break;
217: }
218: if (i == 0)
219: return pair.car;
220: else
221: throw new IndexOutOfBoundsException();
222: }
223:
224: public boolean equals(Object obj) {
225: if ((obj != null) && (obj instanceof Pair))
226: return equals(this , (Pair) obj);
227: else
228: return false;
229: }
230:
231: public static Pair make(Object car, Object cdr) {
232: return new Pair(car, cdr);
233: }
234:
235: public Object[] toArray() {
236: int len = size(); // size()
237: Object[] arr = new Object[len];
238: int i = 0;
239: Sequence rest = this ;
240: for (; i < len && rest instanceof Pair; i++) {
241: Pair pair = (Pair) rest;
242: arr[i] = pair.car;
243: rest = (Sequence) pair.cdr;
244: }
245: int prefix = i;
246: for (; i < len; i++) {
247: arr[i] = rest.get(i - prefix);
248: }
249: return arr;
250: }
251:
252: public Object[] toArray(Object[] arr) {
253: int alen = arr.length;
254: int len = length();
255: if (len > alen) {
256: // FIXME Collection spec requires arr to keep same run-time type
257: arr = new Object[len];
258: alen = len;
259: }
260: int i = 0;
261: Sequence rest = this ;
262: for (; i < len && rest instanceof Pair; i++) {
263: Pair pair = (Pair) rest;
264: arr[i] = pair.car;
265: rest = (Sequence) pair.cdr;
266: }
267: int prefix = i;
268: for (; i < len; i++) {
269: arr[i] = rest.get(i - prefix);
270: }
271: if (len < alen)
272: arr[len] = null;
273: return arr;
274: }
275:
276: /**
277: * @serialData Write the car followed by the cdr.
278: */
279: public void writeExternal(ObjectOutput out) throws IOException {
280: out.writeObject(car);
281: out.writeObject(cdr);
282: }
283:
284: public void readExternal(ObjectInput in) throws IOException,
285: ClassNotFoundException {
286: car = in.readObject();
287: cdr = in.readObject();
288: }
289:
290: /** Needed to override readResolve in LList. */
291: public Object readResolve() throws ObjectStreamException {
292: return this;
293: }
294:
295: };
|