1 16 17 package com.lowagie.text.pdf.hyphenation; 18 19 import java.io.Serializable ; 20 import java.util.Enumeration ; 21 import java.util.Stack ; 22 23 64 65 public class TernaryTree implements Cloneable , Serializable { 66 67 74 75 private static final long serialVersionUID = 5313366505322983510L; 76 77 81 protected char[] lo; 82 83 86 protected char[] hi; 87 88 91 protected char[] eq; 92 93 102 protected char[] sc; 103 104 107 protected CharVector kv; 108 109 protected char root; 110 protected char freenode; 111 protected int length; 113 protected static final int BLOCK_SIZE = 2048; 115 TernaryTree() { 116 init(); 117 } 118 119 protected void init() { 120 root = 0; 121 freenode = 1; 122 length = 0; 123 lo = new char[BLOCK_SIZE]; 124 hi = new char[BLOCK_SIZE]; 125 eq = new char[BLOCK_SIZE]; 126 sc = new char[BLOCK_SIZE]; 127 kv = new CharVector(); 128 } 129 130 138 public void insert(String key, char val) { 139 int len = key.length() 141 + 1; if (freenode + len > eq.length) { 143 redimNodeArrays(eq.length + BLOCK_SIZE); 144 } 145 char strkey[] = new char[len--]; 146 key.getChars(0, len, strkey, 0); 147 strkey[len] = 0; 148 root = insert(root, strkey, 0, val); 149 } 150 151 public void insert(char[] key, int start, char val) { 152 int len = strlen(key) + 1; 153 if (freenode + len > eq.length) { 154 redimNodeArrays(eq.length + BLOCK_SIZE); 155 } 156 root = insert(root, key, start, val); 157 } 158 159 162 private char insert(char p, char[] key, int start, char val) { 163 int len = strlen(key, start); 164 if (p == 0) { 165 p = freenode++; 169 eq[p] = val; length++; 171 hi[p] = 0; 172 if (len > 0) { 173 sc[p] = 0xFFFF; lo[p] = (char)kv.alloc(len 175 + 1); strcpy(kv.getArray(), lo[p], key, start); 177 } else { 178 sc[p] = 0; 179 lo[p] = 0; 180 } 181 return p; 182 } 183 184 if (sc[p] == 0xFFFF) { 185 char pp = freenode++; 189 lo[pp] = lo[p]; eq[pp] = eq[p]; lo[p] = 0; 192 if (len > 0) { 193 sc[p] = kv.get(lo[pp]); 194 eq[p] = pp; 195 lo[pp]++; 196 if (kv.get(lo[pp]) == 0) { 197 lo[pp] = 0; 199 sc[pp] = 0; 200 hi[pp] = 0; 201 } else { 202 sc[pp] = 0xFFFF; 204 } 205 } else { 206 sc[pp] = 0xFFFF; 209 hi[p] = pp; 210 sc[p] = 0; 211 eq[p] = val; 212 length++; 213 return p; 214 } 215 } 216 char s = key[start]; 217 if (s < sc[p]) { 218 lo[p] = insert(lo[p], key, start, val); 219 } else if (s == sc[p]) { 220 if (s != 0) { 221 eq[p] = insert(eq[p], key, start + 1, val); 222 } else { 223 eq[p] = val; 225 } 226 } else { 227 hi[p] = insert(hi[p], key, start, val); 228 } 229 return p; 230 } 231 232 235 public static int strcmp(char[] a, int startA, char[] b, int startB) { 236 for (; a[startA] == b[startB]; startA++, startB++) { 237 if (a[startA] == 0) { 238 return 0; 239 } 240 } 241 return a[startA] - b[startB]; 242 } 243 244 247 public static int strcmp(String str, char[] a, int start) { 248 int i, d, len = str.length(); 249 for (i = 0; i < len; i++) { 250 d = (int)str.charAt(i) - a[start + i]; 251 if (d != 0) { 252 return d; 253 } 254 if (a[start + i] == 0) { 255 return d; 256 } 257 } 258 if (a[start + i] != 0) { 259 return (int)-a[start + i]; 260 } 261 return 0; 262 263 } 264 265 public static void strcpy(char[] dst, int di, char[] src, int si) { 266 while (src[si] != 0) { 267 dst[di++] = src[si++]; 268 } 269 dst[di] = 0; 270 } 271 272 public static int strlen(char[] a, int start) { 273 int len = 0; 274 for (int i = start; i < a.length && a[i] != 0; i++) { 275 len++; 276 } 277 return len; 278 } 279 280 public static int strlen(char[] a) { 281 return strlen(a, 0); 282 } 283 284 public int find(String key) { 285 int len = key.length(); 286 char strkey[] = new char[len + 1]; 287 key.getChars(0, len, strkey, 0); 288 strkey[len] = 0; 289 290 return find(strkey, 0); 291 } 292 293 public int find(char[] key, int start) { 294 int d; 295 char p = root; 296 int i = start; 297 char c; 298 299 while (p != 0) { 300 if (sc[p] == 0xFFFF) { 301 if (strcmp(key, i, kv.getArray(), lo[p]) == 0) { 302 return eq[p]; 303 } else { 304 return -1; 305 } 306 } 307 c = key[i]; 308 d = c - sc[p]; 309 if (d == 0) { 310 if (c == 0) { 311 return eq[p]; 312 } 313 i++; 314 p = eq[p]; 315 } else if (d < 0) { 316 p = lo[p]; 317 } else { 318 p = hi[p]; 319 } 320 } 321 return -1; 322 } 323 324 public boolean knows(String key) { 325 return (find(key) >= 0); 326 } 327 328 private void redimNodeArrays(int newsize) { 330 int len = newsize < lo.length ? newsize : lo.length; 331 char[] na = new char[newsize]; 332 System.arraycopy(lo, 0, na, 0, len); 333 lo = na; 334 na = new char[newsize]; 335 System.arraycopy(hi, 0, na, 0, len); 336 hi = na; 337 na = new char[newsize]; 338 System.arraycopy(eq, 0, na, 0, len); 339 eq = na; 340 na = new char[newsize]; 341 System.arraycopy(sc, 0, na, 0, len); 342 sc = na; 343 } 344 345 public int size() { 346 return length; 347 } 348 349 public Object clone() { 350 TernaryTree t = new TernaryTree(); 351 t.lo = (char[])this.lo.clone(); 352 t.hi = (char[])this.hi.clone(); 353 t.eq = (char[])this.eq.clone(); 354 t.sc = (char[])this.sc.clone(); 355 t.kv = (CharVector)this.kv.clone(); 356 t.root = this.root; 357 t.freenode = this.freenode; 358 t.length = this.length; 359 360 return t; 361 } 362 363 369 protected void insertBalanced(String [] k, char[] v, int offset, int n) { 370 int m; 371 if (n < 1) { 372 return; 373 } 374 m = n >> 1; 375 376 insert(k[m + offset], v[m + offset]); 377 insertBalanced(k, v, offset, m); 378 379 insertBalanced(k, v, offset + m + 1, n - m - 1); 380 } 381 382 383 386 public void balance() { 387 389 int i = 0, n = length; 390 String [] k = new String [n]; 391 char[] v = new char[n]; 392 Iterator iter = new Iterator(); 393 while (iter.hasMoreElements()) { 394 v[i] = iter.getValue(); 395 k[i++] = (String )iter.nextElement(); 396 } 397 init(); 398 insertBalanced(k, v, 0, n); 399 400 } 403 404 417 public void trimToSize() { 418 balance(); 420 421 redimNodeArrays(freenode); 423 424 CharVector kx = new CharVector(); 426 kx.alloc(1); 427 TernaryTree map = new TernaryTree(); 428 compact(kx, map, root); 429 kv = kx; 430 kv.trimToSize(); 431 } 432 433 private void compact(CharVector kx, TernaryTree map, char p) { 434 int k; 435 if (p == 0) { 436 return; 437 } 438 if (sc[p] == 0xFFFF) { 439 k = map.find(kv.getArray(), lo[p]); 440 if (k < 0) { 441 k = kx.alloc(strlen(kv.getArray(), lo[p]) + 1); 442 strcpy(kx.getArray(), k, kv.getArray(), lo[p]); 443 map.insert(kx.getArray(), k, (char)k); 444 } 445 lo[p] = (char)k; 446 } else { 447 compact(kx, map, lo[p]); 448 if (sc[p] != 0) { 449 compact(kx, map, eq[p]); 450 } 451 compact(kx, map, hi[p]); 452 } 453 } 454 455 456 public Enumeration keys() { 457 return new Iterator(); 458 } 459 460 public class Iterator implements Enumeration { 461 462 465 int cur; 466 467 470 String curkey; 471 472 private class Item implements Cloneable { 473 char parent; 474 char child; 475 476 public Item() { 477 parent = 0; 478 child = 0; 479 } 480 481 public Item(char p, char c) { 482 parent = p; 483 child = c; 484 } 485 486 public Object clone() { 487 return new Item(parent, child); 488 } 489 490 } 491 492 495 Stack ns; 496 497 500 StringBuffer ks; 501 502 public Iterator() { 503 cur = -1; 504 ns = new Stack (); 505 ks = new StringBuffer (); 506 rewind(); 507 } 508 509 public void rewind() { 510 ns.removeAllElements(); 511 ks.setLength(0); 512 cur = root; 513 run(); 514 } 515 516 public Object nextElement() { 517 String res = curkey; 518 cur = up(); 519 run(); 520 return res; 521 } 522 523 public char getValue() { 524 if (cur >= 0) { 525 return eq[cur]; 526 } 527 return 0; 528 } 529 530 public boolean hasMoreElements() { 531 return (cur != -1); 532 } 533 534 537 private int up() { 538 Item i = new Item(); 539 int res = 0; 540 541 if (ns.empty()) { 542 return -1; 543 } 544 545 if (cur != 0 && sc[cur] == 0) { 546 return lo[cur]; 547 } 548 549 boolean climb = true; 550 551 while (climb) { 552 i = (Item)ns.pop(); 553 i.child++; 554 switch (i.child) { 555 case 1: 556 if (sc[i.parent] != 0) { 557 res = eq[i.parent]; 558 ns.push(i.clone()); 559 ks.append(sc[i.parent]); 560 } else { 561 i.child++; 562 ns.push(i.clone()); 563 res = hi[i.parent]; 564 } 565 climb = false; 566 break; 567 568 case 2: 569 res = hi[i.parent]; 570 ns.push(i.clone()); 571 if (ks.length() > 0) { 572 ks.setLength(ks.length() - 1); } 574 climb = false; 575 break; 576 577 default: 578 if (ns.empty()) { 579 return -1; 580 } 581 climb = true; 582 break; 583 } 584 } 585 return res; 586 } 587 588 591 private int run() { 592 if (cur == -1) { 593 return -1; 594 } 595 596 boolean leaf = false; 597 while (true) { 598 while (cur != 0) { 600 if (sc[cur] == 0xFFFF) { 601 leaf = true; 602 break; 603 } 604 ns.push(new Item((char)cur, '\u0000')); 605 if (sc[cur] == 0) { 606 leaf = true; 607 break; 608 } 609 cur = lo[cur]; 610 } 611 if (leaf) { 612 break; 613 } 614 cur = up(); 616 if (cur == -1) { 617 return -1; 618 } 619 } 620 StringBuffer buf = new StringBuffer (ks.toString()); 623 if (sc[cur] == 0xFFFF) { 624 int p = lo[cur]; 625 while (kv.get(p) != 0) { 626 buf.append(kv.get(p++)); 627 } 628 } 629 curkey = buf.toString(); 630 return 0; 631 } 632 633 } 634 635 public void printStats() { 636 System.out.println("Number of keys = " + Integer.toString(length)); 637 System.out.println("Node count = " + Integer.toString(freenode)); 638 System.out.println("Key Array length = " 640 + Integer.toString(kv.length())); 641 642 652 653 } 654 655 667 668 } 669 670 | Popular Tags |