Changeset 2018
 Timestamp:
 Jul 12, 2006, 9:57:12 PM (14 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

toimperative/trunk/java/org/refal/plus/Expr.java
r1978 r2018 7 7 /* 8 8 * TODO: 9 *  Insert assertions in all unsafe methods.10 *  Add holes around exprs.11 9 *  Add clone() implementation. 12 10 *  Implement Serializable. … … 16 14 implements Comparable, Cloneable 17 15 { 16 public static final Expr empty = new Expr(0); 17 18 private static final Object border = new Object (); 19 20 private final Object[] terms; 21 22 private final int start; 23 24 private final int length; 25 26 /* 27 * Several variables for gathering some statistics about expression 28 * concatenations. 29 * Do not affect Expr operation. 30 */ 18 31 public static int no_copy = 0; 19 32 public static int left_copy = 0; … … 21 34 public static int both_copy = 0; 22 35 23 public static final Expr empty = new Expr(0); 24 25 private static final Object border = new Object (); 26 27 private final Object[] expr; 28 29 private final int index; 30 31 private final int length; 32 33 /** 34 * Creates empty expression 35 * 36 */ 37 public Expr() { 38 index = 0; 36 /** 37 * Creates empty expression. 38 */ 39 public Expr () { 40 start = 0; 39 41 length = 0; 40 expr = empty.expr; 41 } 42 43 /** 44 * Creates the expression of the `size` length 45 * 46 * @param size  47 * the size of the expression 48 */ 49 private Expr(int size) { 50 length = size; 51 expr = new Object[size*2]; 52 index = size/2; 53 if (index > 0) 54 expr[index  1] = border; 55 if (index + length < expr.length) 56 expr[index + length] = border; 57 } 58 59 /** 60 * Creates subexpression 42 terms = empty.terms; 43 } 44 45 /** 46 * Creates an expression with given length. 47 */ 48 protected Expr (int len) { 49 assert len >= 0; 50 length = len; 51 terms = new Object[len*2]; 52 start = len/2; 53 if (start > 0) 54 terms[start  1] = border; 55 if (start + length < terms.length) 56 terms[start + length] = border; 57 } 58 59 /** 60 * Creates subexpression. 61 61 * 62 62 * @param e  63 * the expression63 * source expression 64 64 * @param i  65 * the beginning of the expression65 * index where subexpression starts 66 66 * @param len  67 * the length of the expression 68 */ 69 public Expr(Expr e, int i, int len) { 70 expr = e.expr; 71 index = e.index + i; 67 * subexpression length 68 */ 69 public Expr (Expr e, int i, int len) { 70 assert i >= 0; 71 assert len >= 0; 72 assert e.length  len >= i; 73 terms = e.terms; 74 start = e.start + i; 72 75 length = len; 73 76 } 74 77 75 78 /** 76 * Element at position `i` 79 * Element at position `i`. 77 80 * 78 81 * @param i  79 82 * position of the term 80 * @return Object 81 */ 82 public Object at(int i) { 83 return expr[index + i]; 84 } 85 86 /** 87 * The length of expression 88 * 89 * @return 90 */ 91 public int getLen() { 83 */ 84 public Object at (int i) { 85 assert 0 <= i && i < length; 86 return terms[start + i]; 87 } 88 89 /** 90 * The length of expression. 91 */ 92 public int getLen () { 92 93 return length; 93 94 } 94 95 95 public boolean equals (Object o) {96 public boolean equals (Object o) { 96 97 return (o instanceof Expr) && equals((Expr) o); 97 98 } 98 99 99 100 /** 100 * Checks whether two expressions are equal 101 * 102 * @param e  103 * the expression 104 * @return boolean 105 */ 106 public boolean equals(Expr e) { 101 * Checks whether two expressions are equal. 102 */ 103 public boolean equals (Expr e) { 107 104 if (length != e.length) 108 105 return false; 109 if ( expr == e.expr && index == e.index)106 if (terms == e.terms && start == e.start) 110 107 return true; 111 for (int i = index, j = e.index; i < length + index; i++, j++) { 112 if (expr[i] instanceof Comparable) { 113 if (!expr[i].equals(e.expr[j])) 114 return false; 115 } else { 116 if (expr[i] != e.expr[j]) 117 return false; 108 for (int i = start, j = e.start; i < start + length; i++, j++) { 109 if (terms[i] == e.terms[j]) 110 continue; 111 if (terms[i] instanceof Comparable) { 112 if (terms[i].equals(e.terms[j])) 113 continue; 118 114 } 115 return false; 119 116 } 120 117 … … 122 119 * Check how this affects efficiency! 123 120 */ 124 // expr = e.expr;121 // terms = e.terms; 125 122 // index = e.index; 126 123 /* … … 131 128 132 129 /** 133 * Checks whether this expr equals to the subexpr of another expression e134 * starting at index i130 * Checks whether this expr equals to the subexpr of another expression `e` 131 * starting at index `i` 135 132 * 136 133 * @param e  … … 138 135 * @param i  139 136 * the position 140 * @return boolean 141 */ 142 public boolean eq(Expr e, int i) { 143 if (expr == e.expr && index == e.index + i) 137 */ 138 public boolean eq (Expr e, int i) { 139 assert i >= 0; 140 assert e.length  i >= length; 141 if (terms == e.terms && start == e.start + i) 144 142 return true; 145 for (int k = index, j = e.index + i; k < length + index; k++, j++) { 146 if (expr[k] instanceof Comparable) { 147 if (!expr[k].equals(e.expr[j])) 148 return false; 149 } else { 150 if (expr[k] != e.expr[j]) 151 return false; 143 for (int k = start, j = e.start + i; k < start + length; k++, j++) { 144 if (terms[k] == e.terms[j]) 145 continue; 146 if (terms[k] instanceof Comparable) { 147 if (terms[k].equals(e.terms[j])) 148 continue; 152 149 } 150 return false; 153 151 } 154 152 … … 156 154 * Check how this affects efficiency! 157 155 */ 158 // expr = e.expr;156 // terms = e.terms; 159 157 // index = e.index + i; 160 158 /* … … 164 162 } 165 163 166 public int compareTo(Object o) { 167 if (!(o instanceof Expr)) 168 throw new ClassCastException(); 164 public int compareTo (Object o) { 169 165 Expr e = (Expr) o; 170 166 // if (equals(e)) // Check how this affects efficiency! 171 167 // return 0; 172 int compare_len = 1; 168 int compare_len = 1; 173 169 int min_len = length; 174 if (length > e.length) 175 { 170 if (length > e.length) { 176 171 compare_len = 1; 177 172 min_len = e.length; 178 173 } 179 else if (length == e.length) 180 { 174 else if (length == e.length) { 181 175 compare_len = 0; 182 176 } 183 for (int i = index, j = e.index; min_len > 0; min_len, i++, j++) 184 { 177 for (int i = start, j = e.start; min_len > 0; min_len, i++, j++) { 185 178 int res; 186 Class c1 = expr[i].getClass(); 187 Class c2 = e.expr[j].getClass(); 188 if (c1 == c2) 189 { 190 try 191 { 192 res = ((Comparable) expr[i]).compareTo(e.expr[j]); 179 Class c1 = terms[i].getClass(); 180 Class c2 = e.terms[j].getClass(); 181 if (c1 != c2) { 182 if (RefalRuntime.getPriority(c1) < RefalRuntime.getPriority(c2)) 183 res = 1; 184 else 185 res = 1; 186 } 187 else { 188 try { 189 res = ((Comparable) terms[i]).compareTo(e.terms[j]); 193 190 } 194 catch (ClassCastException _) 195 { 196 int h1 = expr[i].hashCode(); 197 int h2 = e.expr[j].hashCode(); 191 catch (ClassCastException _) { 192 int h1 = terms[i].hashCode(); 193 int h2 = e.terms[j].hashCode(); 198 194 if (h1 > h2) res = 1; 199 195 else if (h1 < h2) res = 1; … … 205 201 } 206 202 } 207 else208 {209 if (RefalRuntime.getPriority(c1) < RefalRuntime.getPriority(c2))210 res = 1;211 else212 res = 1;213 }214 203 if (res != 0) return res; 215 204 } … … 218 207 219 208 /** 220 * Concatenate two expressions 221 * 222 * @param e1,e2  223 * the expressions 224 * @return Expr 225 */ 226 public Expr(Expr e1, Expr e2) { 209 * Concatenates two expressions. 210 */ 211 public Expr (Expr e1, Expr e2) { 227 212 length = e1.length + e2.length; 228 if (length != 0) 213 if (length == 0) { 214 start = 0; 215 terms = empty.terms; 216 return; 217 } 218 if (e1.length == 0) { 219 terms = e2.terms; 220 start = e2.start; 221 no_copy++; 222 return; 223 } 224 if (e2.length == 0) { 225 terms = e1.terms; 226 start = e1.start; 227 no_copy++; 228 return; 229 } 230 if (e1.terms == e2.terms && e1.start + e1.length == e2.start) { 231 terms = e1.terms; 232 start = e1.start; 233 no_copy++; 234 return; 235 } 236 int e1_end = e1.start + e1.length; 237 if (e1.terms.length  e1_end >= e2.length && 238 e1.terms[e1_end] == border) 229 239 { 230 if (e1.length == 0) 231 { 232 expr = e2.expr; 233 index = e2.index; 234 no_copy++; 235 } 236 else if (e2.length == 0) 237 { 238 expr = e1.expr; 239 index = e1.index; 240 no_copy++; 241 } 242 else if (e1.expr == e2.expr && e1.index + e1.length == e2.index) 243 { 244 expr = e1.expr; 245 index = e1.index; 246 no_copy++; 247 } 248 else if (e1.expr.length  e1.index  e1.length >= e2.length && 249 e1.expr[e1.index + e1.length] == border) 250 { 251 expr = e1.expr; 252 index = e1.index; 253 if (index + length < expr.length) 254 expr[index + length] = border; 255 System.arraycopy(e2.expr, e2.index, expr, index + e1.length, e2.length); 256 right_copy++; 257 } 258 else if (e1.length <= e2.index && 259 e2.expr[e2.index  1] == border) 260 { 261 expr = e2.expr; 262 index = e2.index  e1.length; 263 if (index > 0) 264 expr[index  1] = border; 265 System.arraycopy(e1.expr, e1.index, expr, index, e1.length); 266 left_copy++; 267 } 268 else 269 { 270 expr = new Object[length*2]; 271 index = length/2; 272 expr[index  1] = border; 273 expr[index + length] = border; 274 System.arraycopy(e1.expr, e1.index, expr, index, e1.length); 275 System.arraycopy(e2.expr, e2.index, expr, index + e1.length, e2.length); 276 both_copy++; 277 } 278 } 279 else 280 { 281 index = 0; 282 expr = empty.expr; 283 } 284 } 285 286 public Expr(Expr e1, Object t2) { 240 terms = e1.terms; 241 start = e1.start; 242 if (start + length < terms.length) 243 terms[start + length] = border; 244 System.arraycopy(e2.terms, e2.start, terms, e1_end, e2.length); 245 right_copy++; 246 return; 247 } 248 if (e1.length <= e2.start && e2.terms[e2.start  1] == border) { 249 terms = e2.terms; 250 start = e2.start  e1.length; 251 if (start > 0) 252 terms[start  1] = border; 253 System.arraycopy(e1.terms, e1.start, terms, start, e1.length); 254 left_copy++; 255 return; 256 } 257 terms = new Object[length*2]; 258 start = length/2; 259 terms[start  1] = border; 260 terms[start + length] = border; 261 System.arraycopy(e1.terms, e1.start, terms, start, e1.length); 262 System.arraycopy(e2.terms, e2.start, terms, start + e1.length, e2.length); 263 both_copy++; 264 } 265 266 /** 267 * Adds one term to the right of the expression. 268 */ 269 public Expr (Expr e1, Object t2) { 287 270 length = e1.length + 1; 288 if (e1.expr.length  e1.index  e1.length > 0 && 289 e1.expr[e1.index + e1.length] == border) 290 { 291 index = e1.index; 292 expr = e1.expr; 293 expr[index + e1.length] = t2; 294 if (index + length < expr.length) 295 expr[index + length] = border; 271 int e1_end = e1.start + e1.length; 272 if (e1.terms.length  e1_end > 0 && e1.terms[e1_end] == border) { 273 start = e1.start; 274 terms = e1.terms; 275 terms[e1_end] = t2; 276 if (start + length < terms.length) 277 terms[start + length] = border; 296 278 right_copy++; 297 } 298 else 299 { 300 expr = new Object[length*2]; 301 index = 0; 302 expr[index + length] = border; 303 System.arraycopy(e1.expr, e1.index, expr, index, e1.length); 304 expr[index + e1.length] = t2; 305 both_copy++; 306 } 307 } 308 279 return; 280 } 281 terms = new Object[length*2]; 282 start = 0; 283 terms[start + length] = border; 284 System.arraycopy(e1.terms, e1.start, terms, start, e1.length); 285 terms[start + e1.length] = t2; 286 both_copy++; 287 } 288 289 /** 290 * Concatenates parts of two given expressions. 291 */ 309 292 public Expr(Expr e1, int i1, int len1, Expr e2, int i2, int len2) { 310 length = len1 + len2; 311 index = 0; 312 expr = new Object[length]; 313 System.arraycopy(e1.expr, e1.index + i1, expr, index, len1); 314 System.arraycopy(e2.expr, e2.index + i2, expr, index + len1, len2); 315 } 316 317 public static Expr concat(Expr[] arr) { 293 this(len1 + len2); 294 assert i1 >= 0; 295 assert len1 >= 0; 296 assert e1.length  len1 >= i1; 297 assert i2 >= 0; 298 assert len2 >= 0; 299 assert e2.length  len2 >= i2; 300 System.arraycopy(e1.terms, e1.start + i1, terms, start, len1); 301 System.arraycopy(e2.terms, e2.start + i2, terms, start + len1, len2); 302 } 303 304 /** 305 * Concatenates all expressions from the given array. 306 */ 307 public static Expr concat (Expr[] arr) { 318 308 int length = 0; 319 309 for (int i = 0; i < arr.length; i++) … … 322 312 return empty; 323 313 Expr e = new Expr(length); 324 for (int i = 0, index = e.index; i < arr.length; index += arr[i].length, i++) 325 System.arraycopy(arr[i].expr, arr[i].index, e.expr, index, arr[i].length); 314 for (int i = 0, index = e.start; i < arr.length; index += arr[i].length, i++) 315 System.arraycopy(arr[i].terms, arr[i].start, 316 e.terms, index, arr[i].length); 326 317 return e; 327 318 } 328 319 329 320 /** 330 * Creates expression from the Object 331 * 332 * @param obj  333 * Object 334 */ 335 public Expr(Object obj) { 321 * Creates expression from the Object. 322 */ 323 public Expr (Object obj) { 336 324 length = 1; 337 expr = new Object[length*2]; 338 expr[0] = obj; 339 index = 0; 340 expr[1] = border; 341 } 342 343 /** 344 * Creates expression from the array of Objects 345 * 346 * @param arr  347 * Object[] 348 */ 349 public Expr(Object[] arr) { 325 terms = new Object[2]; 326 terms[0] = obj; 327 terms[1] = border; 328 start = 0; 329 } 330 331 /** 332 * Creates expression from the array of Objects. 333 * The returned expression is backed by the array, so the array shouldn't 334 * be changed after invocation of this method. 335 */ 336 public Expr (Object[] arr) { 350 337 length = arr.length; 351 expr = arr; 352 index = 0; 353 } 354 355 /** 356 * Creates expression from a subarray of an array of Objects 357 * 358 * @param arr  359 * Object[] 360 */ 361 public Expr(Object[] arr, int i, int len) { 338 terms = arr; 339 start = 0; 340 } 341 342 /** 343 * Creates expression from a subarray of an array of Objects. 344 * The returned expression is backed by the array, so the array shouldn't 345 * be changed after invocation of this method (at least its part from `i` 346 * to `i + len` shouldn't be changed). 347 */ 348 public Expr (Object[] arr, int i, int len) { 349 assert i >= 0; 350 assert len >= 0; 351 assert arr.length  len >= i; 362 352 length = len; 363 expr = arr; 364 index = i; 365 if (index > 0) 366 expr[index  1] = border; 367 if (index + length < expr.length) 368 expr[index + length] = border; 369 } 370 371 /** 372 * Returns the contents of the expr. 353 terms = arr; 354 start = i; 355 } 356 357 /** 358 * Returns the contents of this expr. 373 359 */ 374 360 public Object[] toArray() { 375 361 Object[] arr = new Object[length]; 376 System.arraycopy( expr, index, arr, 0, length);362 System.arraycopy(terms, start, arr, 0, length); 377 363 return arr; 378 364 } 379 365 380 public void copyToArray(Object[] arr, int where, int what, int len) { 381 // FIXME: insert here assertion length  len >= what 382 System.arraycopy(expr, index + what, arr, where, len); 366 /** 367 * Writes the contents of this expr to the given array. 368 */ 369 public void toArray (Object[] arr, int where, int what, int len) { 370 assert length  len >= what; 371 System.arraycopy(terms, start + what, arr, where, len); 383 372 } 384 373 … … 386 375 * Creates expression from a sequence of chars. 387 376 */ 388 public static Expr fromSequence (CharSequence seq) {377 public static Expr fromSequence (CharSequence seq) { 389 378 Expr e = new Expr(seq.length()); 390 for (int i = 0, j = e. index; i < e.length; i++, j++)391 e. expr[j] = new Character(seq.charAt(i));379 for (int i = 0, j = e.start; i < e.length; i++, j++) 380 e.terms[j] = new Character(seq.charAt(i)); 392 381 return e; 393 382 } 394 383 395 384 /** 396 * Checks whether term is a symbol 385 * Checks whether term is a symbol. 397 386 * 398 387 * @param i  399 388 * the position 400 * @return boolean401 */402 public boolean symbolAt(int i) {403 return !( expr[index+ i] instanceof Expr);404 } 405 406 public boolean isEmpty () {389 */ 390 public boolean symbolAt (int i) { 391 assert 0 <= i && i < length; 392 return !(terms[start + i] instanceof Expr); 393 } 394 395 public boolean isEmpty () { 407 396 return length == 0; 408 397 } 409 398 410 public String toString () {399 public String toString () { 411 400 return new String(toStringBuffer()); 412 401 } … … 414 403 public StringBuffer toStringBuffer () { 415 404 StringBuffer str = new StringBuffer(length); 416 for (int i = index, last = index + length; i < last; i++) {417 if ( expr[i] instanceof Expr)405 for (int i = start, end = start + length; i < end; i++) { 406 if (terms[i] instanceof Expr) 418 407 str.append('(') 419 .append(((Expr) expr[i]).toStringBuffer())408 .append(((Expr)terms[i]).toStringBuffer()) 420 409 .append(')'); 421 410 else 422 str.append( expr[i].toString());411 str.append(terms[i].toString()); 423 412 } 424 413 return str; … … 429 418 StringBuffer str = new StringBuffer(2*length); 430 419 boolean chars = false; 431 for (int i = index, last = index + length; i < last; i++) {432 Object o = expr[i];420 for (int i = start, end = start + length; i < end; i++) { 421 Object o = terms[i]; 433 422 if (o instanceof Character) { 434 423 if (!chars) { … … 470 459 471 460 public SplitIterator leftSplit (int l) { 472 // FIXME: insert here assertion length >= l473 461 return new SplitIterator(this, l); 474 462 } 475 463 476 464 public SplitIterator rightSplit (int r) { 477 // FIXME: insert here assertion length >= r478 465 return new SplitIterator(this, length  r); 479 466 } … … 490 477 491 478 public SplitIterator next () { 492 left = new Expr(left, 0, left.length + 1); 493 right = new Expr(right, 1, right.length  1); 479 left = new Expr(left.terms, left.start, left.length + 1); 480 right = 481 right.length > 0 ? new Expr(right, 1, right.length  1) : null; 494 482 return this; 495 483 } 496 484 497 485 public SplitIterator prev () { 498 left = new Expr(left, 0, left.length  1);499 right = new Expr(right , 1, right.length + 1);486 left = left.length > 0 ? new Expr(left, 0, left.length  1) : null; 487 right = new Expr(right.terms, right.start  1, right.length + 1); 500 488 return this; 501 489 } 502 490 503 491 public boolean isValid () { 504 return right .length >= 0 && left.length >= 0;492 return right != null && left != null; 505 493 } 506 494
Note: See TracChangeset
for help on using the changeset viewer.