KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gnu > lists > Pair


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

4 package gnu.lists;
5 import java.io.*;
6
7 /** A "pair" object, as used in Lisp-like languages.
8  * When used to implement a list, the 'car' field contains an
9  * element's value, and the 'cdr' field points to either the next Pair
10  * or LList.Empty (which represents the end of the list). (The names
11  * "car" and "cdr" [pronounced "coulder"] are historical; better names
12  * might be "value" and "next".) While a Pair is normally usued to
13  * implement a linked list, sometimes the 'cdr' field ponus to some
14  * other non-list object; this is traditionally callled a "dotted list".
15  */

16
17 public class Pair extends LList implements Externalizable
18 {
19    public Object JavaDoc car;
20    public Object JavaDoc cdr;
21
22   public Pair (Object JavaDoc carval, Object JavaDoc cdrval)
23   {
24     car = carval;
25     cdr = cdrval;
26   }
27
28   public Pair ()
29   {
30   }
31
32   public int size()
33   {
34     int n = listLength(this, true);
35     if (n >= 0)
36       return n;
37     if (n == -1)
38       return Integer.MAX_VALUE;
39     throw new RuntimeException JavaDoc("not a true list");
40   }
41
42   public boolean isEmpty()
43   {
44     return false;
45   }
46
47   // A generalization of LList.list_length
48
// FIXME is this needed, given listLength?
49
public int length ()
50   {
51     // Based on list-length implementation in
52
// Guy L Steele jr: "Common Lisp: The Language", 2nd edition, page 414
53
int n = 0;
54     Object JavaDoc slow = this;
55     Object JavaDoc fast = this;
56     for (;;)
57       {
58     if (fast == Empty)
59       return n;
60     if (! (fast instanceof Pair))
61       {
62         if (fast instanceof Sequence)
63           {
64         int j = ((Sequence) fast).size();
65         return j >= 0 ? n + j : j;
66           }
67         return -2;
68       }
69     Pair fast_pair = (Pair) fast;
70     if (fast_pair.cdr == Empty)
71       return n+1;
72     if (fast == slow && n > 0)
73       return -1;
74     if (! (fast_pair.cdr instanceof Pair))
75       {
76         n++;
77         fast = fast_pair.cdr;
78         continue;
79       }
80     if (!(slow instanceof Pair))
81       return -2;
82     slow = ((Pair)slow).cdr;
83     fast = ((Pair)fast_pair.cdr).cdr;
84     n += 2;
85       }
86   }
87
88   public boolean hasNext (int ipos)
89   {
90     if (ipos <= 0)
91       return ipos == 0;
92     return PositionManager.getPositionObject(ipos).hasNext();
93   }
94
95   public int nextPos (int ipos)
96   {
97     if (ipos <= 0)
98       {
99     if (ipos < 0)
100       return 0;
101     return PositionManager.manager
102       .register(new LListPosition(this, 1, true));
103       }
104     LListPosition it = (LListPosition) PositionManager.getPositionObject(ipos);
105     return it.gotoNext() ? ipos : 0;
106   }
107
108   public Object JavaDoc getPosNext (int ipos)
109   {
110     if (ipos <= 0)
111       return ipos == 0 ? car : eofValue;
112     return PositionManager.getPositionObject(ipos).getNext();
113   }
114
115   public Object JavaDoc getPosPrevious (int ipos)
116   {
117     if (ipos <= 0)
118       return ipos == 0 ? eofValue : lastPair().car;
119     return PositionManager.getPositionObject(ipos).getPrevious();
120   }
121
122   public final Pair lastPair()
123   {
124     Pair pair = this;
125     for (;;)
126       {
127     Object JavaDoc next = pair.cdr;
128     if (next instanceof Pair)
129       pair = (Pair) next;
130     else
131       return pair;
132       }
133   }
134
135   /*
136   public void print(java.io.PrintWriter ps)
137   {
138     ps.print("(");
139     printNoParen(this, ps);
140     ps.print(")");
141   }
142   */

143
144   public int hashCode()
145   {
146     // Compatible with the AbstractSequence hashCode for true lists.
147
int hash = 1;
148     Object JavaDoc list = this;
149     while (list instanceof Pair)
150       {
151     Pair pair = (Pair) list;
152     Object JavaDoc obj = pair.car;
153     hash = 31*hash + (obj==null ? 0 : obj.hashCode());
154     list = pair.cdr;
155       }
156     if (list != LList.Empty && list != null)
157       hash = hash ^ list.hashCode();
158     return hash;
159   }
160
161   static public boolean equals (Pair pair1, Pair pair2)
162   {
163     if (pair1 == pair2)
164       return true;
165     if (pair1 == null || pair2 == null)
166       return false;
167     for (;;)
168       {
169     Object JavaDoc x1 = pair1.car;
170     Object JavaDoc x2 = pair2.car;
171     if (x1 != x2 && (x1 == null || ! x1.equals(x2)))
172       return false;
173     x1 = pair1.cdr;
174     x2 = pair2.cdr;
175     if (x1 == x2)
176       return true;
177     if (x1 == null || x2 == null)
178       return false;
179     if (! (x1 instanceof Pair) || !(x2 instanceof Pair))
180       return x1.equals(x2);
181     pair1 = (Pair) x1;
182     pair2 = (Pair) x2;
183       
184       }
185   }
186
187   /* #ifdef JAVA2 */
188   static public int compareTo (Pair pair1, Pair pair2)
189   {
190     if (pair1 == pair2)
191       return 0;
192     if (pair1 == null )
193       return -1;
194     if (pair2 == null)
195       return 1;
196     for (;;)
197       {
198         Object JavaDoc x1 = pair1.car;
199         Object JavaDoc x2 = pair2.car;
200         int d = ((Comparable JavaDoc) x1).compareTo((Comparable JavaDoc) x2);
201         if (d != 0)
202           return d;
203         x1 = pair1.cdr;
204         x2 = pair2.cdr;
205         if (x1 == x2)
206           return 0;
207         if (x1 == null)
208           return -1;
209         if (x2 == null)
210           return 1;
211         if (! (x1 instanceof Pair) || !(x2 instanceof Pair))
212           return ((Comparable JavaDoc) x1).compareTo((Comparable JavaDoc) x2);
213         pair1 = (Pair) x1;
214         pair2 = (Pair) x2;
215       }
216   }
217
218   public int compareTo(Object JavaDoc obj)
219   {
220     if (obj == Empty)
221       return 1;
222     else
223       return compareTo(this, (Pair) obj);
224   }
225   /* #endif */
226
227   public Object JavaDoc get (int index)
228   {
229     Pair pair = this;
230     int i = index;
231     while (i > 0)
232       {
233     i--;
234     if (pair.cdr instanceof Pair)
235       pair = (Pair)pair.cdr;
236     else if (pair.cdr instanceof Sequence)
237       return ((Sequence)pair.cdr).get(i);
238     else
239       break;
240       }
241     if (i == 0)
242       return pair.car;
243     else
244       throw new IndexOutOfBoundsException JavaDoc ();
245   }
246
247   public boolean equals (Object JavaDoc obj)
248   {
249     if ((obj != null) && (obj instanceof Pair))
250       return equals (this, (Pair) obj);
251     else
252       return false;
253   }
254
255   public static Pair make (Object JavaDoc car, Object JavaDoc cdr)
256   {
257     return new Pair (car, cdr);
258   }
259
260   public Object JavaDoc[] toArray()
261   {
262     int len = size(); // size()
263
Object JavaDoc[] arr = new Object JavaDoc[len];
264     int i = 0;
265     Sequence rest = this;
266     for ( ; i < len && rest instanceof Pair; i++)
267     {
268       Pair pair = (Pair) rest;
269       arr[i] = pair.car;
270       rest = (Sequence) pair.cdr;
271     }
272     int prefix = i;
273     for ( ; i < len; i++)
274     {
275       arr[i] = rest.get(i - prefix);
276     }
277     return arr;
278   }
279
280   public Object JavaDoc[] toArray(Object JavaDoc[] arr)
281   {
282     int alen = arr.length;
283     int len = length();
284     if (len > alen)
285     {
286       // FIXME Collection spec requires arr to keep same run-time type
287
arr = new Object JavaDoc[len];
288       alen = len;
289     }
290     int i = 0;
291     Sequence rest = this;
292     for ( ; i < len && rest instanceof Pair; i++)
293     {
294       Pair pair = (Pair) rest;
295       arr[i] = pair.car;
296       rest = (Sequence) pair.cdr;
297     }
298     int prefix = i;
299     for ( ; i < len; i++)
300     {
301       arr[i] = rest.get(i - prefix);
302     }
303     if (len < alen)
304       arr[len] = null;
305     return arr;
306   }
307
308   /**
309    * @serialData Write the car followed by the cdr.
310    */

311   public void writeExternal(ObjectOutput out) throws IOException
312   {
313     out.writeObject(car);
314     out.writeObject(cdr);
315   }
316
317   public void readExternal(ObjectInput in)
318     throws IOException, ClassNotFoundException JavaDoc
319   {
320     car = in.readObject();
321     cdr = in.readObject();
322   }
323
324   /** Needed to override readResolve in LList. */
325   public Object JavaDoc readResolve() throws ObjectStreamException
326   {
327     return this;
328   }
329
330 };
331
Popular Tags