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.*;
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: /*
080: public void print(java.io.PrintWriter ps)
081: {
082: ps.print("(");
083: printNoParen(this, ps);
084: ps.print(")");
085: }
086: */
087:
088: public int hashCode() {
089: // Compatible with the AbstractSequence hashCode for true lists.
090: int hash = 1;
091: Object list = this ;
092: while (list instanceof Pair) {
093: Pair pair = (Pair) list;
094: Object obj = pair.car;
095: hash = 31 * hash + (obj == null ? 0 : obj.hashCode());
096: list = pair.cdr;
097: }
098: if (list != LList.Empty && list != null)
099: hash = hash ^ list.hashCode();
100: return hash;
101: }
102:
103: static public boolean equals(Pair pair1, Pair pair2) {
104: if (pair1 == pair2)
105: return true;
106: if (pair1 == null || pair2 == null)
107: return false;
108: for (;;) {
109: Object x1 = pair1.car;
110: Object x2 = pair2.car;
111: if (x1 != x2 && (x1 == null || !x1.equals(x2)))
112: return false;
113: x1 = pair1.cdr;
114: x2 = pair2.cdr;
115: if (x1 == x2)
116: return true;
117: if (x1 == null || x2 == null)
118: return false;
119: if (!(x1 instanceof Pair) || !(x2 instanceof Pair))
120: return x1.equals(x2);
121: pair1 = (Pair) x1;
122: pair2 = (Pair) x2;
123:
124: }
125: }
126:
127: public Object get(int index) {
128: Pair pair = this ;
129: int i = index;
130: while (i > 0) {
131: i--;
132: if (pair.cdr instanceof Pair)
133: pair = (Pair) pair.cdr;
134: else if (pair.cdr instanceof Sequence)
135: return ((Sequence) pair.cdr).get(i);
136: else
137: break;
138: }
139: if (i == 0)
140: return pair.car;
141: else
142: throw new IndexOutOfBoundsException();
143: }
144:
145: public boolean equals(Object obj) {
146: if ((obj != null) && (obj instanceof Pair))
147: return equals(this , (Pair) obj);
148: else
149: return false;
150: }
151:
152: public static Pair make(Object car, Object cdr) {
153: return new Pair(car, cdr);
154: }
155:
156: public Object[] toArray() {
157: int len = size(); // size()
158: Object[] arr = new Object[len];
159: int i = 0;
160: Sequence rest = this ;
161: for (; i < len && rest instanceof Pair; i++) {
162: Pair pair = (Pair) rest;
163: arr[i] = pair.car;
164: rest = (Sequence) pair.cdr;
165: }
166: int prefix = i;
167: for (; i < len; i++) {
168: arr[i] = rest.get(i - prefix);
169: }
170: return arr;
171: }
172:
173: public Object[] toArray(Object[] arr) {
174: int alen = arr.length;
175: int len = length();
176: if (len > alen) {
177: // FIXME Collection spec requires arr to keep same run-time type
178: arr = new Object[len];
179: alen = len;
180: }
181: int i = 0;
182: Sequence rest = this ;
183: for (; i < len && rest instanceof Pair; i++) {
184: Pair pair = (Pair) rest;
185: arr[i] = pair.car;
186: rest = (Sequence) pair.cdr;
187: }
188: int prefix = i;
189: for (; i < len; i++) {
190: arr[i] = rest.get(i - prefix);
191: }
192: if (len < alen)
193: arr[len] = null;
194: return arr;
195: }
196:
197: /**
198: * @serialData Write the car followed by the cdr.
199: */
200: public void writeExternal(ObjectOutput out) throws IOException {
201: out.writeObject(car);
202: out.writeObject(cdr);
203: }
204:
205: public void readExternal(ObjectInput in) throws IOException,
206: ClassNotFoundException {
207: car = in.readObject();
208: cdr = in.readObject();
209: }
210: };
|