1 4 package gnu.lists; 5 import java.io.*; 6 7 16 17 public class Pair extends LList implements Externalizable 18 { 19 public Object car; 20 public Object cdr; 21 22 public Pair (Object carval, Object 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 ("not a true list"); 40 } 41 42 public boolean isEmpty() 43 { 44 return false; 45 } 46 47 public int length () 50 { 51 int n = 0; 54 Object slow = this; 55 Object 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 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 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 next = pair.cdr; 128 if (next instanceof Pair) 129 pair = (Pair) next; 130 else 131 return pair; 132 } 133 } 134 135 143 144 public int hashCode() 145 { 146 int hash = 1; 148 Object list = this; 149 while (list instanceof Pair) 150 { 151 Pair pair = (Pair) list; 152 Object 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 x1 = pair1.car; 170 Object 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 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 x1 = pair1.car; 199 Object x2 = pair2.car; 200 int d = ((Comparable ) x1).compareTo((Comparable ) 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 ) x1).compareTo((Comparable ) x2); 213 pair1 = (Pair) x1; 214 pair2 = (Pair) x2; 215 } 216 } 217 218 public int compareTo(Object obj) 219 { 220 if (obj == Empty) 221 return 1; 222 else 223 return compareTo(this, (Pair) obj); 224 } 225 226 227 public Object 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 (); 245 } 246 247 public boolean equals (Object 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 car, Object cdr) 256 { 257 return new Pair (car, cdr); 258 } 259 260 public Object [] toArray() 261 { 262 int len = size(); Object [] arr = new Object [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 [] toArray(Object [] arr) 281 { 282 int alen = arr.length; 283 int len = length(); 284 if (len > alen) 285 { 286 arr = new Object [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 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 319 { 320 car = in.readObject(); 321 cdr = in.readObject(); 322 } 323 324 325 public Object readResolve() throws ObjectStreamException 326 { 327 return this; 328 } 329 330 }; 331 | Popular Tags |