1 4 package gnu.lists; 5 import gnu.text.Char; 6 7 15 16 public class TreeList extends AbstractSequence 17 implements 18 19 21 XConsumer, PositionConsumer, Consumable 22 { 23 27 public Object [] objects; 28 public int oindex; 29 public char[] data; 30 public int gapStart; 31 public int gapEnd; 32 33 34 public int attrStart; 35 36 public int docStart; 37 38 public TreeList() 39 { 40 resizeObjects(); 41 gapEnd = 200; 42 data = new char[gapEnd]; 43 } 44 45 51 public TreeList(TreeList list, int startPosition, int endPosition) 52 { 53 this(); 54 list.consumeIRange(startPosition, endPosition, this); 55 } 56 57 public TreeList(TreeList list) 58 { 59 this(list, 0, list.data.length); 60 } 61 62 public void clear() 63 { 64 gapStart = 0; 65 gapEnd = data.length; 66 attrStart = 0; 67 if (gapEnd > 1500) 68 { 69 gapEnd = 200; 70 data = new char[gapEnd]; 71 } 72 objects = null; 73 oindex = 0; 74 resizeObjects(); 75 } 76 77 109 110 public static final int MAX_CHAR_SHORT = 0x9FFF; 111 112 113 static final int MIN_INT_SHORT = -0x1000; 115 116 static final int MAX_INT_SHORT = 0x1FFF; 118 119 static final int INT_SHORT_ZERO = 0xC000; 120 121 122 static final int OBJECT_REF_SHORT = 0xE000; 123 124 125 static final int OBJECT_REF_SHORT_INDEX_MAX = 0xFFF; 126 127 128 static final char OBJECT_REF_FOLLOWS = 0xF10D; 129 130 131 static final char POSITION_REF_FOLLOWS = 0xF10E; 132 133 135 protected static final char POSITION_PAIR_FOLLOWS = 0xF10F; 136 137 138 static final int BYTE_PREFIX = 0xF000; 139 140 141 static final char BOOL_FALSE = 0xF100; 142 143 144 static final char BOOL_TRUE = 0xF101; 145 146 151 public static final int INT_FOLLOWS = 0xF102; 152 153 158 static final int LONG_FOLLOWS = 0xF103; 159 160 165 static final int FLOAT_FOLLOWS = 0xF104; 166 167 172 static final int DOUBLE_FOLLOWS = 0xF105; 173 174 175 static final int CHAR_FOLLOWS = 0xF106; 176 177 182 static final int COMMENT = 0xF117; 183 184 190 protected static final int PROCESSING_INSTRUCTION = 0xF114; 191 192 197 static final int CDATA_SECTION = 0xF115; 198 199 200 static final int JOINER = 0xF116; 201 202 213 protected static final int BEGIN_ATTRIBUTE_LONG = 0xF109; 214 public static final int BEGIN_ATTRIBUTE_LONG_SIZE = 5; 215 216 217 static final int END_ATTRIBUTE = 0xF10A; 218 public static final int END_ATTRIBUTE_SIZE = 1; 219 220 233 protected static final int BEGIN_DOCUMENT = 0xF110; 234 235 236 protected static final int END_DOCUMENT = 0xF111; 237 238 242 public static final int BEGIN_ENTITY = 0xF112; 243 public static final int BEGIN_ENTITY_SIZE = 5; 244 245 protected static final int END_ENTITY = 0xF113; 246 247 253 protected static final int DOCUMENT_URI = 0xF118; 254 255 269 protected static final int BEGIN_GROUP_SHORT = 0xA000; 270 protected static final int BEGIN_GROUP_SHORT_INDEX_MAX = 0xFFF; 271 272 279 protected static final int END_GROUP_SHORT = 0xF10B; 280 281 299 protected static final int BEGIN_GROUP_LONG = 0xF108; 300 301 322 protected static final int END_GROUP_LONG = 0xF10C; 323 324 int currentParent = -1; 325 326 public void ensureSpace(int needed) 327 { 328 int avail = gapEnd - gapStart; 329 if (needed > avail) 330 { 331 int oldSize = data.length; 332 int neededSize = oldSize - avail + needed; 333 int newSize = 2 * oldSize; 334 if (newSize < neededSize) 335 newSize = neededSize; 336 char[] tmp = new char[newSize]; 337 if (gapStart > 0) 338 System.arraycopy(data, 0, tmp, 0, gapStart); 339 int afterGap = oldSize - gapEnd; 340 if (afterGap > 0) 341 System.arraycopy(data, gapEnd, tmp, newSize - afterGap, afterGap); 342 gapEnd = newSize - afterGap; 343 data = tmp; 344 } 345 } 346 347 public final void resizeObjects() 348 { 349 int oldLength; 350 int newLength; 351 Object [] tmp; 352 if (objects == null) 353 { 354 oldLength = 0; 355 newLength = 100; 356 tmp = new Object [newLength]; 357 } 358 else 359 { 360 oldLength = objects.length; 361 newLength = 2 * oldLength; 362 tmp = new Object [newLength]; 363 System.arraycopy(objects, 0, tmp, 0, oldLength); 364 } 365 objects = tmp; 366 } 367 368 public int find (Object arg1) 369 { 370 if (oindex == objects.length) 371 resizeObjects(); 372 objects[oindex] = arg1; 373 return oindex++; 374 } 375 376 377 final protected int getIntN(int index) 378 { 379 return (data[index] << 16) | (data[index + 1] & 0xFFFF); 380 } 381 382 383 final protected long getLongN(int index) 384 { 385 char[] data = this.data; return (data[index] & 0xFFFFL) << 48 387 | (data[index+1] & 0xFFFFL) << 32 388 | (data[index+2] & 0xFFFFL) << 16 389 | (data[index+3] & 0xFFFFL); 390 } 391 392 final public void setIntN(int index, int i) 393 { 394 data[index] = (char) (i >> 16); 395 data[index+1] = (char) i; 396 } 397 398 public void consume (SeqPosition position) 399 { 400 ensureSpace(3); 401 int index = find(position.copy()); 403 data[gapStart++] = POSITION_REF_FOLLOWS; 404 setIntN(gapStart, index); 405 gapStart += 2; 406 } 407 408 public void writePosition(AbstractSequence seq, int ipos) 409 { 410 ensureSpace(5); 411 data[gapStart] = POSITION_PAIR_FOLLOWS; 412 int seq_index = find(seq); 413 setIntN(gapStart+1, seq_index); 414 setIntN(gapStart+3, ipos); 415 gapStart += 5; 416 } 417 418 public void writeObject(Object v) 419 { 420 ensureSpace(3); 421 int index = find(v); 422 if (index < 0x1000) 423 data[gapStart++] = (char) (OBJECT_REF_SHORT | index); 424 else 425 { 426 data[gapStart++] = OBJECT_REF_FOLLOWS; 427 setIntN(gapStart, index); 428 gapStart += 2; 429 } 430 } 431 432 434 public void writeDocumentUri (Object uri) 435 { 436 ensureSpace(3); 437 int index = find(uri); 438 data[gapStart++] = DOCUMENT_URI; 439 setIntN(gapStart, index); 440 gapStart += 2; 441 } 442 443 public void writeComment(char[] chars, int offset, int length) 444 { 445 ensureSpace(3+length); 446 int i = gapStart; 447 data[i++] = COMMENT; 448 setIntN(i, length); 449 i += 2; 450 System.arraycopy(chars, offset, data, i, length); 451 gapStart = i + length; 452 } 453 454 public void writeProcessingInstruction(String target, char[] content, 455 int offset, int length) 456 { 457 ensureSpace(5+length); 458 int i = gapStart; 459 data[i++] = PROCESSING_INSTRUCTION; 460 int index = find(target); 461 setIntN(i, index); 462 setIntN(i+2, length); 463 i += 4; 464 System.arraycopy(content, offset, data, i, length); 465 gapStart = i + length; 466 } 467 468 public void beginGroup(Object type) 469 { 470 beginGroup(find(type)); 471 } 472 473 public void beginDocument() 474 { 475 ensureSpace(5+1); 476 gapEnd--; 477 int p = gapStart; 478 data[p] = BEGIN_DOCUMENT; 479 if (docStart != 0) 480 throw new Error ("nested document"); 481 docStart = p+1; 482 setIntN(p+1, gapEnd - data.length); 483 setIntN(p+3, currentParent == -1 ? -1 : currentParent-p); currentParent = p; 485 gapStart = p + 5; 486 currentParent = p; 487 data[gapEnd] = END_DOCUMENT; 488 } 489 490 public void endDocument() 491 { 492 if (data[gapEnd] != END_DOCUMENT || docStart <= 0 493 || data[currentParent] != BEGIN_DOCUMENT) 494 throw new Error ("unexpected endDocument"); 495 gapEnd++; 497 setIntN(docStart, gapStart - docStart + 1); 498 docStart = 0; 499 data[gapStart++] = END_DOCUMENT; 500 int parent = getIntN(currentParent+3); 501 currentParent = parent >= -1 ? parent : currentParent + parent; 502 } 503 504 public void beginEntity (Object base) 505 { 506 ensureSpace(BEGIN_ENTITY_SIZE+1); 507 gapEnd--; 508 int p = gapStart; 509 data[p] = BEGIN_ENTITY; 510 setIntN(p+1, find(base)); 511 setIntN(p+3, currentParent == -1 ? -1 : currentParent-p); gapStart = p + 5; 513 currentParent = p; 514 data[gapEnd] = END_ENTITY; 515 } 516 517 public void endEntity () 518 { 519 if (data[gapEnd] != END_ENTITY 520 || data[currentParent] != BEGIN_ENTITY) 521 throw new Error ("unexpected endEntity"); 522 gapEnd++; 524 data[gapStart++] = END_ENTITY; 525 int parent = getIntN(currentParent+3); 526 currentParent = parent >= -1 ? parent : currentParent + parent; 527 } 528 529 public void beginGroup(int index) 530 { 531 ensureSpace(3 + 7); 532 gapEnd -= 7; 533 data[gapStart++] = BEGIN_GROUP_LONG; 534 setIntN(gapStart, gapEnd - data.length); gapStart += 2; 536 data[gapEnd] = END_GROUP_LONG; 537 setIntN(gapEnd + 1, index); setIntN(gapEnd + 3, gapStart - 3); setIntN(gapEnd + 5, currentParent); currentParent = gapStart - 3; 541 } 542 543 public void setGroupName (int groupIndex, int nameIndex) 544 { 545 if (data[groupIndex] == BEGIN_GROUP_LONG) 546 { 547 int j = getIntN(groupIndex+1); 548 groupIndex = j + (j < 0 ? data.length : groupIndex); 549 } 550 if (groupIndex < gapEnd) 551 throw new Error ("setGroupName before gapEnd"); 552 setIntN(groupIndex + 1, nameIndex); 553 } 554 555 public void endGroup () 556 { 557 if (data[gapEnd] != END_GROUP_LONG) 558 throw new Error ("unexpected endGroup"); 559 int index = getIntN(gapEnd + 1); 560 int begin = getIntN(gapEnd + 3); 561 int parent = getIntN(gapEnd + 5); 562 currentParent = parent; 563 gapEnd += 7; 564 int offset = gapStart - begin; 565 int parentOffset = begin - parent; 566 if (index < BEGIN_GROUP_SHORT_INDEX_MAX 567 && offset < 0x10000 && parentOffset < 0x10000) 568 { 569 data[begin] = (char) (BEGIN_GROUP_SHORT | index); 570 data[begin + 1] = (char) offset; data[begin + 2] = (char) parentOffset; 572 data[gapStart] = END_GROUP_SHORT; 573 data[gapStart + 1] = (char) offset; gapStart += 2; 575 } 576 else 577 { 578 data[begin] = BEGIN_GROUP_LONG; 579 setIntN(begin + 1, offset); 580 data[gapStart] = END_GROUP_LONG; 581 setIntN(gapStart + 1, index); 582 setIntN(gapStart + 3, - offset); 583 if (parent >= gapStart || begin <= gapStart) 584 parent -= gapStart; 585 setIntN(gapStart + 5, parent); 586 gapStart += 7; 587 } 588 } 589 590 public void beginAttribute(Object attrType) 591 { 592 beginAttribute(find(attrType)); 593 } 594 595 public void beginAttribute(int index) 596 { 597 616 617 ensureSpace(5 + 1); 618 gapEnd--; 619 data[gapStart++] = BEGIN_ATTRIBUTE_LONG; 620 if (attrStart != 0) 621 throw new Error ("nested attribute"); 622 attrStart = gapStart; 623 setIntN(gapStart, index); 624 setIntN(gapStart + 2, gapEnd - data.length); 625 gapStart += 4; 626 data[gapEnd] = END_ATTRIBUTE; 627 } 628 629 public void setAttributeName (int attrIndex, int nameIndex) 630 { 631 setIntN(attrIndex + 1, nameIndex); 632 } 633 634 public void endAttribute() 635 { 636 if (attrStart <= 0) 637 return; 638 if (data[gapEnd] != END_ATTRIBUTE) 639 throw new Error ("unexpected endAttribute"); 640 gapEnd++; 642 setIntN(attrStart+2, gapStart - attrStart + 1); 643 attrStart = 0; 644 data[gapStart++] = END_ATTRIBUTE; 645 } 646 647 public Consumer append (char c) 648 { 649 write(c); 650 return this; 651 } 652 653 public void write (int c) 654 { 655 ensureSpace(3); 656 if (c <= MAX_CHAR_SHORT) 657 data[gapStart++] = (char) c; 658 else if (c < 0x10000) 659 { 660 data[gapStart++] = CHAR_FOLLOWS; 661 data[gapStart++] = (char) c; 662 } 663 else 664 Char.print(c, this); 665 } 666 667 public void writeBoolean(boolean v) 668 { 669 ensureSpace(1); 670 data[gapStart++] = v ? BOOL_TRUE : BOOL_FALSE; 671 } 672 673 public void writeByte(int v) 674 { 675 ensureSpace(1); 676 data[gapStart++] = (char) (BYTE_PREFIX + (v & 0xFF)); 677 } 678 679 public void writeInt(int v) 680 { 681 ensureSpace(3); 682 if (v >= MIN_INT_SHORT && v <= MAX_INT_SHORT) 683 data[gapStart++] = (char) (INT_SHORT_ZERO + v); 684 else 685 { 686 data[gapStart++] = INT_FOLLOWS; 687 setIntN(gapStart, v); 688 gapStart += 2; 689 } 690 } 691 692 public void writeLong(long v) 693 { 694 ensureSpace(5); 695 data[gapStart++] = LONG_FOLLOWS; 696 data[gapStart++] = (char) (v >>> 48); 697 data[gapStart++] = (char) (v >>> 32); 698 data[gapStart++] = (char) (v >>> 16); 699 data[gapStart++] = (char) v; 700 } 701 702 public void writeFloat(float v) 703 { 704 ensureSpace(3); 705 int i = Float.floatToIntBits(v); 706 data[gapStart++] = FLOAT_FOLLOWS; 707 data[gapStart++] = (char) (i >>> 16); 708 data[gapStart++] = (char) i; 709 } 710 711 public void writeDouble(double v) 712 { 713 ensureSpace(5); 714 long l = Double.doubleToLongBits(v); 715 data[gapStart++] = DOUBLE_FOLLOWS; 716 data[gapStart++] = (char) (l >>> 48); 717 data[gapStart++] = (char) (l >>> 32); 718 data[gapStart++] = (char) (l >>> 16); 719 data[gapStart++] = (char) l; 720 } 721 722 public boolean ignoring() 723 { 724 return false; 725 } 726 727 public void writeJoiner () 728 { 729 ensureSpace(1); 730 data[gapStart++] = JOINER; 731 } 732 733 public void write(char[] buf, int off, int len) 734 { 735 if (len == 0) 736 writeJoiner(); 737 ensureSpace(len); 738 while (len > 0) 739 { 740 char ch = buf[off++]; 741 len--; 742 if (ch <= MAX_CHAR_SHORT) 743 data[gapStart++] = ch; 744 else 745 { 746 write(ch); 747 ensureSpace(len); 748 } 749 } 750 } 751 752 public void write (String str) 753 { 754 write(str, 0, str.length()); 755 } 756 757 758 public void write (CharSequence str, int start, int length) 759 760 762 { 763 if (length == 0) 764 writeJoiner(); 765 ensureSpace(length); 766 while (length > 0) 767 { 768 char ch = str.charAt(start++); 769 length--; 770 if (ch <= MAX_CHAR_SHORT) 771 data[gapStart++] = ch; 772 else 773 { 774 write(ch); 775 ensureSpace(length); 776 } 777 } 778 } 779 780 public void writeCDATA (char[] chars, int offset, int length) 781 { 782 ensureSpace(3+length); 783 int i = gapStart; 784 data[i++] = CDATA_SECTION; 785 setIntN(i, length); 786 i += 2; 787 System.arraycopy(chars, offset, data, i, length); 788 gapStart = i + length; 789 } 790 791 792 public Consumer append (CharSequence csq) 793 { 794 if (csq == null) 795 csq = "null"; 796 return append(csq, 0, csq.length()); 797 } 798 799 public Consumer append (CharSequence csq, int start, int end) 800 { 801 if (csq == null) 802 csq = "null"; 803 for (int i = start; i < end; i++) 804 append(csq.charAt(i)); 805 return this; 806 } 807 808 818 819 public boolean isEmpty() 820 { 821 int pos = gapStart == 0 ? gapEnd : 0; 823 return pos == data.length; 824 } 825 826 public int size() 827 { 828 int size = 0; 829 int i = 0; 830 for (;;) 831 { 832 i = nextPos(i); 833 if (i == 0) 834 return size; 835 size++; 836 } 837 } 838 839 public int createPos(int index, boolean isAfter) 840 { 841 return createRelativePos(0, index, isAfter); 842 } 843 844 public final int posToDataIndex (int ipos) 845 { 846 if (ipos == -1) 847 return data.length; 848 int index = ipos >>> 1; 849 if ((ipos & 1) != 0) 850 index--; 851 if (index >= gapStart) 852 index += gapEnd - gapStart; 853 if ((ipos & 1) != 0) 854 { 855 index = nextDataIndex(index); 856 if (index < 0) 857 return data.length; 858 if (index == gapStart) 859 index += gapEnd - gapStart; 860 } 861 return index; 862 } 863 864 public int firstChildPos (int ipos) 865 { 866 int index = gotoChildrenStart(posToDataIndex(ipos)); 867 if (index < 0) 868 return 0; 869 return index << 1; 870 } 871 872 public final int gotoChildrenStart(int index) 873 { 874 if (index == data.length) 875 return -1; 876 char datum = data[index]; 877 if ((datum >= BEGIN_GROUP_SHORT 878 && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX) 879 || datum == BEGIN_GROUP_LONG) 880 index += 3; 881 else if (datum == BEGIN_DOCUMENT || datum == BEGIN_ENTITY) 882 index += 5; 883 else 884 return -1; 885 for (;;) 886 { 887 if (index >= gapStart) 888 index += gapEnd - gapStart; 889 datum = data[index]; 890 if (datum == BEGIN_ATTRIBUTE_LONG) 891 { 892 int end = getIntN(index+3); 893 index = end + (end < 0 ? data.length : index); 894 } 895 else if (datum == END_ATTRIBUTE || datum == JOINER) 896 index++; 897 else if (datum == DOCUMENT_URI) 898 index += 3; 899 else 900 break; 901 } 902 return index; 903 } 904 905 public int parentPos (int ipos) 906 { 907 int index = posToDataIndex(ipos); 908 for (;;) 909 { 910 index = parentOrEntityI(index); 911 if (index == -1) 912 return -1; 913 if (data[index] != BEGIN_ENTITY) 914 return index << 1; 915 } 916 } 917 918 public int parentOrEntityPos (int ipos) 919 { 920 int index = parentOrEntityI(posToDataIndex(ipos)); 921 return index < 0 ? -1 : index << 1; 922 } 923 924 public int parentOrEntityI (int index) 925 { 926 if (index == data.length) 927 return -1; 928 char datum = data[index]; 929 if (datum == BEGIN_DOCUMENT || datum == BEGIN_ENTITY) 930 { 931 int parent_offset = getIntN(index+3); 932 if (parent_offset >= -1) 933 return parent_offset; 934 else 935 return index + parent_offset; 936 } 937 if (datum >= BEGIN_GROUP_SHORT 938 && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX) 939 { 940 int parent_offset = data[index+2]; 941 return parent_offset == 0 ? -1 : index - parent_offset; 942 } 943 if (datum == BEGIN_GROUP_LONG) 944 { 945 int end_offset = getIntN(index+1); 946 end_offset += end_offset < 0 ? data.length : index; 947 int parent_offset = getIntN(end_offset+5); 948 if (parent_offset == 0) 949 return -1; 950 if (parent_offset < 0) 951 parent_offset += end_offset; 952 return parent_offset; 953 } 954 for (;;) 955 { 956 if (index == gapStart) 957 index = gapEnd; 958 if (index == data.length) 959 return -1; 960 datum = data[index]; 961 switch (datum) 962 { 963 case END_GROUP_SHORT: 964 return index - data[index+1]; 965 case END_GROUP_LONG: 966 int begin_offset = getIntN(index+3); 967 if (begin_offset < 0) 968 begin_offset += index; 969 return begin_offset; 970 case END_ATTRIBUTE: 971 index++; 972 continue; 973 case END_DOCUMENT: 974 return -1; 975 default: 976 index = nextDataIndex(index); 977 } 978 if (index < 0) 979 break; 980 } 981 return -1; 982 } 983 984 public int getAttributeCount (int parent) 985 { 986 int n = 0; 987 for (int attr = firstAttributePos(parent); 988 attr != 0 && getNextKind(attr) == Sequence.ATTRIBUTE_VALUE; 989 attr = nextPos(attr)) 990 n++; 991 return n; 992 } 993 994 public boolean gotoAttributesStart(TreePosition pos) 995 { 996 int index = gotoAttributesStart(pos.ipos >> 1); 997 if (index < 0) 998 return false; 999 pos.push(this, index << 1); 1000 return true; 1001 } 1002 1003 public int firstAttributePos (int ipos) 1004 { 1005 int index = gotoAttributesStart(posToDataIndex(ipos)); 1006 return index < 0 ? 0 : index << 1; 1007 } 1008 1009 public int gotoAttributesStart(int index) 1010 { 1011 if (index >= gapStart) 1012 index += gapEnd - gapStart; 1013 if (index == data.length) 1014 return -1; 1015 char datum = data[index]; 1016 if ((datum >= BEGIN_GROUP_SHORT 1017 && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX) 1018 || datum == BEGIN_GROUP_LONG) 1019 return index + 3; 1020 else 1021 return -1; 1022 } 1023 1024 public Object get (int index) 1025 { 1026 int i = 0; 1027 while (--index >= 0) 1028 { 1029 i = nextPos(i); 1030 if (i == 0) 1031 throw new IndexOutOfBoundsException (); 1032 } 1033 return getPosNext(i); 1034 } 1035 1036 public boolean consumeNext(int ipos, Consumer out) 1037 { 1038 if (! hasNext(ipos)) 1039 return false; 1040 int start = posToDataIndex(ipos); 1041 int end = nextNodeIndex(start, -1 >>> 1); 1042 if (end == start) 1043 end = nextDataIndex(start); 1044 if (end >= 0) 1045 consumeIRange(start, end, out); 1046 return true; 1047 } 1048 1049 public void consumePosRange(int startPos, int endPos, Consumer out) 1050 { 1051 consumeIRange(posToDataIndex(startPos), posToDataIndex(endPos), out); 1052 } 1053 1054 public int consumeIRange(int startPosition, int endPosition, Consumer out) 1055 { 1056 int pos = startPosition; 1057 int limit = startPosition <= gapStart && endPosition > gapStart ? gapStart 1058 : endPosition; 1059 int index; 1060 for (;;) 1061 { 1062 if (pos >= limit) 1063 { 1064 if (pos == gapStart && endPosition > gapEnd) 1065 { 1066 pos = gapEnd; 1067 limit = endPosition; 1068 } 1069 else 1070 break; 1071 } 1072 1073 char datum = data[pos++]; 1074 1075 if (datum <= MAX_CHAR_SHORT) 1076 { 1077 int start = pos - 1; 1078 int lim = limit; 1079 for (;;) 1080 { 1081 if (pos >= lim) 1082 break; 1083 datum = data[pos++]; 1084 if (datum > MAX_CHAR_SHORT) 1085 { 1086 pos--; 1087 break; 1088 } 1089 } 1090 out.write(data, start, pos - start); 1091 continue; 1092 } 1093 if (datum >= OBJECT_REF_SHORT 1094 && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX) 1095 { 1096 out.writeObject(objects[datum-OBJECT_REF_SHORT]); 1097 continue; 1098 } 1099 if (datum >= BEGIN_GROUP_SHORT 1100 && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX) 1101 { 1102 index = datum-BEGIN_GROUP_SHORT; 1103 out.beginGroup(objects[index]); 1104 pos += 2; 1105 continue; 1106 } 1107 1114 if (datum >= INT_SHORT_ZERO + MIN_INT_SHORT 1115 && datum <= INT_SHORT_ZERO + MAX_INT_SHORT) 1116 { 1117 out.writeInt(datum - INT_SHORT_ZERO); 1118 continue; 1119 } 1120 switch (datum) 1121 { 1122 case BEGIN_DOCUMENT: 1123 out.beginDocument(); 1124 pos += 4; 1125 continue; 1126 case END_DOCUMENT: 1127 out.endDocument(); 1128 continue; 1129 case BEGIN_ENTITY: 1130 if (out instanceof TreeList) 1131 ((TreeList) out).beginEntity(objects[getIntN(pos)]); 1132 pos += 4; 1133 continue; 1134 case END_ENTITY: 1135 if (out instanceof TreeList) 1136 ((TreeList) out).endEntity(); 1137 continue; 1138 case DOCUMENT_URI: 1139 if (out instanceof TreeList) 1140 ((TreeList) out).writeDocumentUri(objects[getIntN(pos)]); 1141 pos += 2; 1142 continue; 1143 case COMMENT: 1144 { 1145 int length = getIntN(pos); 1146 pos += 2; 1147 if (out instanceof XConsumer) 1148 ((XConsumer) out).writeComment(data, pos, length); 1149 pos += length; 1150 } 1151 continue; 1152 case CDATA_SECTION: 1153 { 1154 int length = getIntN(pos); 1155 pos += 2; 1156 if (out instanceof XConsumer) 1157 ((XConsumer) out).writeCDATA(data, pos, length); 1158 else 1159 out.write(data, pos, length); 1160 pos += length; 1161 } 1162 continue; 1163 case PROCESSING_INSTRUCTION: 1164 { 1165 String target = (String ) objects[getIntN(pos)]; 1166 int length = getIntN(pos+2); 1167 pos += 4; 1168 if (out instanceof XConsumer) 1169 ((XConsumer) out).writeProcessingInstruction(target, data, 1170 pos, length); 1171 pos += length; 1172 } 1173 continue; 1174 case BOOL_FALSE: 1175 case BOOL_TRUE: 1176 out.writeBoolean(datum != BOOL_FALSE); 1177 continue; 1178 case JOINER: 1179 out.write(""); 1180 continue; 1181 case CHAR_FOLLOWS: 1182 out.write(data, pos, 1 + datum - CHAR_FOLLOWS); 1183 pos++; 1184 continue; 1185 case POSITION_PAIR_FOLLOWS: 1186 { 1187 AbstractSequence seq = (AbstractSequence) objects[getIntN(pos)]; 1188 int ipos = getIntN(pos+2); 1189 if (out instanceof PositionConsumer) 1190 ((PositionConsumer) out).writePosition(seq, ipos); 1191 else 1192 out.writeObject(seq.getIteratorAtPos(ipos)); 1193 pos += 4; 1194 } 1195 continue; 1196 case POSITION_REF_FOLLOWS: 1197 if (out instanceof PositionConsumer) 1198 { 1199 ((PositionConsumer) out).consume((SeqPosition) objects[getIntN(pos)]); 1200 pos += 2; 1201 continue; 1202 } 1203 case OBJECT_REF_FOLLOWS: 1205 out.writeObject(objects[getIntN(pos)]); 1206 pos += 2; 1207 continue; 1208 case END_GROUP_SHORT: 1209 pos++; 1210 out.endGroup(); 1211 continue; 1212 case BEGIN_GROUP_LONG: 1213 index = getIntN(pos); 1214 index += index >= 0 ? pos - 1 : data.length; 1215 pos += 2; 1216 index = getIntN(index + 1); 1217 out.beginGroup(objects[index]); 1218 continue; 1219 case END_GROUP_LONG: 1220 index = getIntN(pos); 1221 out.endGroup(); 1222 pos += 6; 1223 continue; 1224 case BEGIN_ATTRIBUTE_LONG: 1225 index = getIntN(pos); 1226 out.beginAttribute(objects[index]); 1227 pos += 4; 1228 continue; 1229 case END_ATTRIBUTE: 1230 out.endAttribute(); 1231 continue; 1232 case INT_FOLLOWS: 1233 out.writeInt(getIntN(pos)); 1234 pos += 2; 1235 continue; 1236 case FLOAT_FOLLOWS: 1237 out.writeFloat(Float.intBitsToFloat(getIntN(pos))); 1238 pos += 2; 1239 continue; 1240 case LONG_FOLLOWS: 1241 out.writeLong(getLongN(pos)); 1242 pos += 4; 1243 continue; 1244 case DOUBLE_FOLLOWS: 1245 out.writeDouble(Double.longBitsToDouble(getLongN(pos))); 1246 pos += 4; 1247 continue; 1248 default: 1249 throw new Error ("unknown code:"+(int) datum); 1250 } 1251 } 1252 return pos; 1253 } 1254 1255 public void toString (String sep, StringBuffer sbuf) 1256 { 1257 int pos = 0; 1258 int limit = gapStart; 1259 int index; 1260 boolean seen = false; 1261 boolean inStartTag = false; 1262 boolean inAttribute = false; 1263 for (;;) 1264 { 1265 if (pos >= limit) 1266 { 1267 if (pos == gapStart) 1268 { 1269 pos = gapEnd; 1270 limit = data.length; 1271 if (pos == limit) 1272 break; 1273 } 1274 else 1275 break; 1276 } 1277 1278 char datum = data[pos++]; 1279 1280 if (datum <= MAX_CHAR_SHORT) 1281 { 1282 int start = pos - 1; 1283 int lim = limit; 1284 for (;;) 1285 { 1286 if (pos >= lim) 1287 break; 1288 datum = data[pos++]; 1289 if (datum > MAX_CHAR_SHORT) 1290 { 1291 pos--; 1292 break; 1293 } 1294 } 1295 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1296 sbuf.append(data, start, pos - start); 1297 seen = false; 1298 continue; 1299 } 1300 if (datum >= OBJECT_REF_SHORT 1301 && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX) 1302 { 1303 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1304 if (seen) sbuf.append(sep); else seen = true; 1305 sbuf.append(objects[datum-OBJECT_REF_SHORT]); 1306 continue; 1307 } 1308 if (datum >= BEGIN_GROUP_SHORT 1309 && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX) 1310 { 1311 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1312 index = datum-BEGIN_GROUP_SHORT; 1313 if (seen) sbuf.append(sep); 1314 sbuf.append('<'); 1315 sbuf.append(objects[index].toString()); 1316 pos += 2; 1317 seen = false; 1318 inStartTag = true; 1319 continue; 1320 } 1321 if (datum >= INT_SHORT_ZERO + MIN_INT_SHORT 1322 && datum <= INT_SHORT_ZERO + MAX_INT_SHORT) 1323 { 1324 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1325 if (seen) sbuf.append(sep); else seen = true; 1326 sbuf.append(datum - INT_SHORT_ZERO); 1327 continue; 1328 } 1329 switch (datum) 1330 { 1331 case BEGIN_DOCUMENT: 1332 case BEGIN_ENTITY: 1333 pos += 4; 1334 continue; 1335 case DOCUMENT_URI: 1336 pos += 2; 1337 continue; 1338 case COMMENT: 1339 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1340 index = getIntN(pos); pos += 2; 1342 sbuf.append("<!--"); 1343 sbuf.append(data, pos, index); 1344 sbuf.append("-->"); 1345 pos += index; 1346 continue; 1347 case CDATA_SECTION: 1348 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1349 index = getIntN(pos); pos += 2; 1351 sbuf.append("<![CDATA["); 1352 sbuf.append(data, pos, index); 1353 sbuf.append("]]>"); 1354 pos += index; 1355 continue; 1356 case PROCESSING_INSTRUCTION: 1357 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1358 sbuf.append("<?"); 1359 index = getIntN(pos); pos += 2; 1361 sbuf.append(objects[index]); 1362 index = getIntN(pos); pos += 2; 1364 if (index > 0) 1365 { 1366 sbuf.append(' '); 1367 sbuf.append(data, pos, index); 1368 pos += index; 1369 } 1370 sbuf.append("?>"); 1371 continue; 1372 case END_DOCUMENT: 1373 case END_ENTITY: 1374 continue; 1375 case BOOL_FALSE: 1376 case BOOL_TRUE: 1377 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1378 if (seen) sbuf.append(sep); else seen = true; 1379 sbuf.append(datum != BOOL_FALSE); 1380 continue; 1381 case JOINER: 1382 continue; 1383 case CHAR_FOLLOWS: 1384 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1385 sbuf.append(data, pos, 1 + datum - CHAR_FOLLOWS); 1386 seen = false; 1387 pos++; 1388 continue; 1389 case POSITION_PAIR_FOLLOWS: 1390 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1391 if (seen) sbuf.append(sep); else seen = true; 1392 { 1393 AbstractSequence seq = (AbstractSequence) objects[getIntN(pos)]; 1394 int ipos = getIntN(pos+2); 1395 sbuf.append(seq.getIteratorAtPos(ipos)); 1397 pos += 4; 1398 } 1399 continue; 1400 case POSITION_REF_FOLLOWS: 1401 case OBJECT_REF_FOLLOWS: 1402 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1403 if (seen) sbuf.append(sep); else seen = true; 1404 sbuf.append(objects[getIntN(pos)]); 1405 pos += 2; 1406 continue; 1407 case BEGIN_GROUP_LONG: 1408 index = getIntN(pos); 1409 index += index >= 0 ? pos - 1 : data.length; 1410 pos += 2; 1411 index = getIntN(index + 1); 1412 if (inStartTag) sbuf.append('>'); 1413 else if (seen) sbuf.append(sep); 1414 sbuf.append('<'); 1415 sbuf.append(objects[index]); 1416 seen = false; 1417 inStartTag = true; 1418 continue; 1419 case END_GROUP_LONG: 1420 case END_GROUP_SHORT: 1421 if (datum == END_GROUP_SHORT) 1422 { 1423 index = data[pos++]; 1424 index = data[pos - 2 - index] - BEGIN_GROUP_SHORT; 1425 } 1426 else 1427 { 1428 index = getIntN(pos); 1429 pos += 6; 1430 } 1431 if (inStartTag) 1432 sbuf.append("/>"); 1433 else 1434 { 1435 sbuf.append("</"); 1436 sbuf.append(objects[index]); 1437 sbuf.append('>'); 1438 } 1439 inStartTag = false; 1440 seen = true; 1441 continue; 1442 case BEGIN_ATTRIBUTE_LONG: 1443 index = getIntN(pos); 1444 sbuf.append(' '); 1445 sbuf.append(objects[index]); 1446 sbuf.append("=\""); 1447 inAttribute = true; 1448 inStartTag = false; 1449 pos += 4; 1450 continue; 1451 case END_ATTRIBUTE: 1452 sbuf.append('"'); 1453 inAttribute = false; 1454 inStartTag = true; 1455 seen = false; 1456 continue; 1457 case INT_FOLLOWS: 1458 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1459 if (seen) sbuf.append(sep); else seen = true; 1460 sbuf.append(getIntN(pos)); 1461 pos += 2; 1462 continue; 1463 case FLOAT_FOLLOWS: 1464 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1465 if (seen) sbuf.append(sep); else seen = true; 1466 sbuf.append(Float.intBitsToFloat(getIntN(pos))); 1467 pos += 2; 1468 continue; 1469 case LONG_FOLLOWS: 1470 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1471 if (seen) sbuf.append(sep); else seen = true; 1472 sbuf.append(getLongN(pos)); 1473 pos += 4; 1474 continue; 1475 case DOUBLE_FOLLOWS: 1476 if (inStartTag) { sbuf.append('>'); inStartTag = false; } 1477 if (seen) sbuf.append(sep); else seen = true; 1478 sbuf.append(Double.longBitsToDouble(getLongN(pos))); 1479 pos += 4; 1480 continue; 1481 default: 1482 throw new Error ("unknown code:"+(int) datum); 1483 } 1484 } 1485 } 1486 1487 public boolean hasNext(int ipos) 1488 { 1489 int index = posToDataIndex(ipos); 1490 if (index == data.length) 1491 return false; 1492 char ch = data[index]; 1493 return ch != END_ATTRIBUTE && ch != END_GROUP_SHORT 1494 && ch != END_GROUP_LONG && ch != END_DOCUMENT; 1495 } 1496 1497 public int getNextKind(int ipos) 1498 { 1499 return getNextKindI(posToDataIndex(ipos)); 1500 } 1501 1502 public int getNextKindI (int index) 1503 { 1504 if (index == data.length) 1505 return Sequence.EOF_VALUE; 1506 char datum = data[index]; 1507 if (datum <= MAX_CHAR_SHORT) 1508 return Sequence.CHAR_VALUE; 1509 if (datum >= OBJECT_REF_SHORT 1510 && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX) 1511 return Sequence.OBJECT_VALUE; 1512 if (datum >= BEGIN_GROUP_SHORT 1513 && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX) 1514 return Sequence.GROUP_VALUE; 1515 if ((datum & 0xFF00) == BYTE_PREFIX) 1516 return Sequence.TEXT_BYTE_VALUE; 1517 if (datum >= INT_SHORT_ZERO + MIN_INT_SHORT 1518 && datum <= INT_SHORT_ZERO + MAX_INT_SHORT) 1519 return Sequence.INT_S32_VALUE; 1520 switch (datum) 1521 { 1522 case BOOL_FALSE: 1523 case BOOL_TRUE: 1524 return Sequence.BOOLEAN_VALUE; 1525 case INT_FOLLOWS: 1526 return Sequence.INT_S32_VALUE; 1527 case LONG_FOLLOWS: 1528 return Sequence.INT_S64_VALUE; 1529 case FLOAT_FOLLOWS: 1530 return Sequence.FLOAT_VALUE; 1531 case DOUBLE_FOLLOWS: 1532 return Sequence.DOUBLE_VALUE; 1533 case CHAR_FOLLOWS: 1534 case BEGIN_DOCUMENT: 1535 return Sequence.DOCUMENT_VALUE; 1536 case BEGIN_ENTITY: 1537 return getNextKind((index+BEGIN_ENTITY_SIZE) << 1); 1538 case BEGIN_GROUP_LONG: 1539 return Sequence.GROUP_VALUE; 1540 case END_GROUP_SHORT: 1541 case END_GROUP_LONG: 1542 case END_ATTRIBUTE: 1543 case END_DOCUMENT: 1544 case END_ENTITY: 1545 return Sequence.EOF_VALUE; 1546 case BEGIN_ATTRIBUTE_LONG: 1547 return Sequence.ATTRIBUTE_VALUE; 1548 case CDATA_SECTION: 1549 return Sequence.CDATA_VALUE; 1550 case COMMENT: 1551 return Sequence.COMMENT_VALUE; 1552 case PROCESSING_INSTRUCTION: 1553 return Sequence.PROCESSING_INSTRUCTION_VALUE; 1554 case DOCUMENT_URI: case POSITION_REF_FOLLOWS: case POSITION_PAIR_FOLLOWS: 1557 case OBJECT_REF_FOLLOWS: 1558 case JOINER: default: 1560 return Sequence.OBJECT_VALUE; 1561 } 1562 1563 } 1564 1565 public Object getNextTypeObject (int ipos) 1566 { 1567 int index = posToDataIndex(ipos); 1568 char datum; 1569 for (;;) 1570 { 1571 if (index == data.length) 1572 return null; 1573 datum = data[index]; 1574 if (datum != BEGIN_ENTITY) 1575 break; 1576 index += BEGIN_ENTITY_SIZE; 1577 } 1578 if (datum >= BEGIN_GROUP_SHORT 1579 && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX) 1580 index = datum-BEGIN_GROUP_SHORT; 1581 else if (datum == BEGIN_GROUP_LONG) 1582 { 1583 int j = getIntN(index+1); 1584 j += j < 0 ? data.length : index; 1585 index = getIntN(j + 1); 1586 } 1587 else if (datum == BEGIN_ATTRIBUTE_LONG) 1588 index = getIntN(index + 1); 1589 else if (datum == PROCESSING_INSTRUCTION) 1590 index = getIntN(index + 1); 1591 else 1592 return null; 1593 return index < 0 ? null : objects[index]; 1594 } 1595 1596 public String getNextTypeName(int ipos) 1597 { 1598 Object type = getNextTypeObject(ipos); 1599 return type == null ? null : type.toString(); 1600 } 1601 1602 public Object getPosPrevious(int ipos) 1603 { 1604 if ((ipos & 1) != 0 && ipos != -1) 1605 return getPosNext(ipos - 3); 1606 else 1607 return super.getPosPrevious(ipos); 1608 } 1609 1610 private Object copyToList(int startPosition, int endPosition) 1611 { 1612 return new TreeList(this, startPosition, endPosition); 1613 } 1614 1615 1616 public int getPosNextInt (int ipos) 1617 { 1618 int index = posToDataIndex(ipos); 1619 if (index < data.length) 1620 { 1621 char datum = data[index]; 1622 if (datum >= INT_SHORT_ZERO + MIN_INT_SHORT 1623 && datum <= INT_SHORT_ZERO + MAX_INT_SHORT) 1624 return datum-INT_SHORT_ZERO; 1625 if (datum == INT_FOLLOWS) 1626 return getIntN(index+1); 1627 } 1628 return ((Number ) getPosNext(ipos)).intValue(); 1629 } 1630 1631 public Object getPosNext(int ipos) 1632 { 1633 int index = posToDataIndex(ipos); 1634 if (index == data.length) 1635 return Sequence.eofValue; 1636 char datum = data[index]; 1637 if (datum <= MAX_CHAR_SHORT) 1638 return Convert.toObject(datum); 1639 if (datum >= OBJECT_REF_SHORT 1640 && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX) 1641 return objects[datum-OBJECT_REF_SHORT]; 1642 if (datum >= BEGIN_GROUP_SHORT 1643 && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX) 1644 return copyToList(index, index + data[index+1] + 2); 1645 1649 if (datum >= INT_SHORT_ZERO + MIN_INT_SHORT 1650 && datum <= INT_SHORT_ZERO + MAX_INT_SHORT) 1651 return Convert.toObject(datum-INT_SHORT_ZERO); 1652 switch (datum) 1653 { 1654 case BEGIN_DOCUMENT: 1655 { 1656 int end_offset = getIntN(index+1); 1657 end_offset += end_offset < 0 ? data.length : index; 1658 end_offset++; 1659 1665 return copyToList(index, end_offset); 1666 } 1667 case BOOL_FALSE: 1668 case BOOL_TRUE: 1669 return Convert.toObject(datum != BOOL_FALSE); 1670 case INT_FOLLOWS: 1671 return Convert.toObject(getIntN(index+1)); 1672 case LONG_FOLLOWS: 1673 return Convert.toObject(getLongN(index+1)); 1674 case FLOAT_FOLLOWS: 1675 return Convert.toObject(Float.intBitsToFloat(getIntN(index+1))); 1676 case DOUBLE_FOLLOWS: 1677 return Convert.toObject(Double.longBitsToDouble(getLongN(index+1))); 1678 case CHAR_FOLLOWS: 1679 return Convert.toObject(data[index+1]); 1680 case BEGIN_ATTRIBUTE_LONG: 1681 { 1682 int end_offset = getIntN(index+3); 1683 end_offset += end_offset < 0 ? data.length : index; 1684 return copyToList(index, end_offset+1); 1685 } 1686 case BEGIN_GROUP_LONG: 1687 { 1688 int end_offset = getIntN(index+1); 1689 end_offset += end_offset < 0 ? data.length : index; 1690 return copyToList(index, end_offset+7); 1691 } 1692 case END_GROUP_SHORT: 1693 case END_GROUP_LONG: 1694 case END_ATTRIBUTE: 1695 case END_DOCUMENT: 1696 return Sequence.eofValue; 1697 case POSITION_REF_FOLLOWS: 1698 case OBJECT_REF_FOLLOWS: 1699 return objects[getIntN(index+1)]; 1700 case JOINER: 1701 return ""; 1702 case POSITION_PAIR_FOLLOWS: AbstractSequence seq = (AbstractSequence) objects[getIntN(index+1)]; 1704 ipos = getIntN(index+3); 1705 return seq.getIteratorAtPos(ipos); 1706 default: 1707 throw unsupported("getPosNext, code="+Integer.toHexString(datum)); 1708 } 1709 } 1710 1711 public void stringValue (int startIndex, int endIndex, StringBuffer sbuf) 1712 { 1713 int index = startIndex; 1714 while (index < endIndex && index >= 0) 1715 index = stringValue(false, index, sbuf); 1716 } 1717 1718 public int stringValue(int index, StringBuffer sbuf) 1719 { 1720 int next = nextNodeIndex(index, -1 >>> 1); 1721 if (next > index) 1722 { 1723 stringValue(index, next, sbuf); 1724 return index; 1725 } 1726 else 1727 return stringValue(false, index, sbuf); 1728 } 1729 1730 public int stringValue(boolean inGroup, int index, StringBuffer sbuf) 1731 { 1732 Object value = null; 1733 int doChildren = 0, j; 1734 if (index >= gapStart) 1735 index += gapEnd - gapStart; 1736 if (index == data.length) 1737 return -1; 1738 char datum = data[index]; 1739 index++; 1740 boolean spaceNeeded = false; 1741 if (datum <= MAX_CHAR_SHORT) 1742 { 1743 sbuf.append(datum); 1744 return index; 1745 } 1746 if (datum >= OBJECT_REF_SHORT 1747 && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX) 1748 { 1749 if (spaceNeeded) 1750 sbuf.append(' '); 1751 value = objects[datum-OBJECT_REF_SHORT]; 1752 spaceNeeded = false; 1753 } 1754 else if (datum >= BEGIN_GROUP_SHORT 1755 && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX) 1756 { 1757 doChildren = index + 2; 1758 index = data[index] + index + 1; 1759 } 1760 else if ((datum & 0xFF00) == BYTE_PREFIX) 1761 { 1762 sbuf.append(datum & 0xFF); 1763 return index; 1764 } 1765 else if (datum >= INT_SHORT_ZERO + MIN_INT_SHORT 1766 && datum <= INT_SHORT_ZERO + MAX_INT_SHORT) 1767 { 1768 sbuf.append((int) datum - INT_SHORT_ZERO); 1769 return index; 1770 } 1771 else 1772 { 1773 switch (datum) 1774 { 1775 case DOCUMENT_URI: 1776 return index + 2; 1777 case PROCESSING_INSTRUCTION: 1778 index += 2; 1779 1780 case CDATA_SECTION: 1781 case COMMENT: 1782 { 1783 int length = getIntN(index); 1784 index += 2; 1785 if (! inGroup || datum == CDATA_SECTION) 1786 sbuf.append(data, index, length); 1787 return index + length; 1788 } 1789 case BOOL_FALSE: 1790 case BOOL_TRUE: 1791 if (spaceNeeded) 1792 sbuf.append(' '); 1793 sbuf.append(datum != BOOL_FALSE); 1794 spaceNeeded = true; 1795 return index; 1796 case INT_FOLLOWS: 1797 if (spaceNeeded) 1798 sbuf.append(' '); 1799 sbuf.append(getIntN(index)); 1800 spaceNeeded = true; 1801 return index + 2; 1802 case LONG_FOLLOWS: 1803 if (spaceNeeded) 1804 sbuf.append(' '); 1805 sbuf.append(getLongN(index)); 1806 spaceNeeded = true; 1807 return index + 4; 1808 case FLOAT_FOLLOWS: 1809 if (spaceNeeded) 1810 sbuf.append(' '); 1811 sbuf.append(Float.intBitsToFloat(getIntN(index))); 1812 spaceNeeded = true; 1813 return index + 2; 1814 case DOUBLE_FOLLOWS: 1815 if (spaceNeeded) 1816 sbuf.append(' '); 1817 sbuf.append(Double.longBitsToDouble(getLongN(index))); 1818 spaceNeeded = true; 1819 return index + 4; 1820 case CHAR_FOLLOWS: 1821 spaceNeeded = false; 1822 sbuf.append(data[index]); 1823 return index + 1; 1824 case BEGIN_DOCUMENT: 1825 case BEGIN_ENTITY: 1826 doChildren = index + 4; 1827 j = getIntN(index); 1828 index = j + (j < 0 ? data.length + 1 : index); 1829 break; 1830 case BEGIN_GROUP_LONG: 1831 spaceNeeded = false; 1832 doChildren = index + 2; 1833 j = getIntN(index); 1834 j += j < 0 ? data.length : index-1; 1835 index = j + 7; 1836 break; 1837 case JOINER: 1838 spaceNeeded = false; 1839 break; 1840 case END_GROUP_SHORT: 1841 case END_GROUP_LONG: 1842 case END_ATTRIBUTE: 1843 case END_DOCUMENT: 1844 case END_ENTITY: 1845 return -1; 1846 case BEGIN_ATTRIBUTE_LONG: 1847 if (! inGroup) 1848 doChildren = index + 4; 1849 int end = getIntN(index+2); 1850 index = end + (end < 0 ? data.length + 1: index); 1851 break; 1852 case POSITION_PAIR_FOLLOWS: 1853 { 1854 AbstractSequence seq = (AbstractSequence) objects[getIntN(index)]; 1855 int ipos = getIntN(index+2); 1856 ((TreeList) seq).stringValue(inGroup, ipos >> 1, sbuf); 1857 index += 4; 1858 } 1859 break; 1860 case POSITION_REF_FOLLOWS: 1861 case OBJECT_REF_FOLLOWS: 1862 default: 1863 throw new Error ("unimplemented: "+Integer.toHexString(datum)+" at:"+index); 1864 } 1865 } 1866 if (value != null) 1867 sbuf.append(value); 1868 if (doChildren > 0) 1869 { 1870 do 1871 { 1872 doChildren = stringValue(true, doChildren, sbuf); 1873 } 1874 while (doChildren >= 0); 1875 } 1876 return index; 1877 } 1878 1879 public int createRelativePos(int istart, int offset, boolean isAfter) 1880 { 1881 if (isAfter) 1882 { 1883 if (offset == 0) 1884 { 1885 if ((istart & 1) != 0) 1886 return istart; 1887 if (istart == 0) 1888 return 1; 1889 } 1890 offset--; 1891 } 1892 if (offset < 0) 1893 throw unsupported("backwards createRelativePos"); 1894 int pos = posToDataIndex(istart); 1895 while (--offset >= 0) 1896 { 1897 pos = nextDataIndex(pos); 1898 if (pos < 0) 1899 throw new IndexOutOfBoundsException (); 1900 } 1901 if (pos >= gapEnd) 1902 pos -= gapEnd - gapStart; 1903 return isAfter ? ((pos + 1) << 1) | 1 : (pos << 1); 1904 } 1905 1906 1907 public final int nextNodeIndex (int pos, int limit) 1908 { 1909 if ((limit | 0x80000000) == -1) limit = data.length; 1911 for (;;) 1912 { 1913 if (pos == gapStart) 1914 pos = gapEnd; 1915 if (pos >= limit) 1916 return pos; 1917 char datum = data[pos]; 1918 if (datum <= MAX_CHAR_SHORT 1919 || (datum >= OBJECT_REF_SHORT 1920 && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX) 1921 || (datum >= INT_SHORT_ZERO + MIN_INT_SHORT 1922 && datum <= INT_SHORT_ZERO + MAX_INT_SHORT) 1923 || (datum & 0xFF00) == BYTE_PREFIX) 1924 { 1925 pos++; 1926 continue; 1927 } 1928 if (datum >= BEGIN_GROUP_SHORT 1929 && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX) 1930 return pos; 1931 switch (datum) 1932 { 1933 case DOCUMENT_URI: 1934 pos += 3; 1935 break; 1936 case JOINER: 1937 pos += 1; 1938 break; 1939 case PROCESSING_INSTRUCTION: 1940 case COMMENT: 1941 case BEGIN_DOCUMENT: 1942 case BEGIN_GROUP_LONG: 1943 case BEGIN_ATTRIBUTE_LONG: 1944 return pos; 1945 case BEGIN_ENTITY: 1946 pos += 5; 1947 break; 1948 case END_GROUP_SHORT: 1949 case END_GROUP_LONG: 1950 case END_ATTRIBUTE: 1951 case END_DOCUMENT: 1952 return pos; 1953 case CDATA_SECTION: 1954 default: 1955 pos = nextDataIndex(pos); 1956 continue; 1957 } 1958 } 1959 } 1960 1961 public int nextMatching(int startPos, ElementPredicate predicate, 1962 int endPos, boolean descend) 1963 { 1964 int start = posToDataIndex(startPos); 1965 int limit = posToDataIndex(endPos); 1966 int pos = start; 1967 if (predicate instanceof NodePredicate) 1968 pos = nextNodeIndex(pos, limit); 1969 boolean checkAttribute = false; boolean checkNode; 1971 boolean checkText; 1972 boolean checkGroup; if (predicate instanceof GroupPredicate) 1974 { 1975 checkNode = true; 1976 checkGroup = true; 1977 checkText = false; 1978 } 1979 else if (predicate instanceof AttributePredicate) 1980 { 1981 checkNode = true; 1982 checkGroup = false; 1983 checkText = false; 1984 } 1985 else 1986 { 1987 checkNode = true; 1988 checkGroup = true; 1989 checkText = true; 1990 } 1991 int next; 1992 for (;; pos = next) 1993 { 1994 if (pos == gapStart) 1995 pos = gapEnd; 1996 if (pos >= limit && limit != -1) 1997 return 0; 1998 int j; 1999 char datum = data[pos]; 2000 if (datum <= MAX_CHAR_SHORT 2001 || (datum >= OBJECT_REF_SHORT 2002 && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX) 2003 || (datum >= INT_SHORT_ZERO + MIN_INT_SHORT 2004 && datum <= INT_SHORT_ZERO + MAX_INT_SHORT)) 2005 { 2006 if (checkText && predicate.isInstancePos(this, pos << 1)) 2007 { 2008 if (pos >= gapEnd) 2009 pos -= gapEnd - gapStart; 2010 return pos << 1; 2011 } 2012 next = pos + 1; 2013 continue; 2014 } 2015 switch (datum) 2016 { 2017 case DOCUMENT_URI: 2018 next = pos + 3; 2019 continue; 2020 case BEGIN_DOCUMENT: 2021 next = pos + 5; 2022 if (checkNode) break; 2023 continue; 2024 case BEGIN_ENTITY: 2025 next = pos + 5; 2026 continue; 2027 case POSITION_REF_FOLLOWS: 2028 case OBJECT_REF_FOLLOWS: 2029 case INT_FOLLOWS: 2030 next = pos + 3; 2031 if (checkText) break; 2032 continue; 2033 case CHAR_FOLLOWS: 2034 next = pos + 2; 2035 continue; 2036 case END_GROUP_SHORT: 2037 if (! descend) 2038 return 0; 2039 next = pos + 2; 2040 continue; 2041 case POSITION_PAIR_FOLLOWS: 2042 next = pos + 5; 2043 if (checkText) break; 2044 continue; 2045 case END_GROUP_LONG: 2046 if (! descend) 2047 return 0; 2048 next = pos + 7; 2049 continue; 2050 case END_ATTRIBUTE: 2051 case END_DOCUMENT: 2052 if (! descend) 2053 return 0; 2054 2055 case END_ENTITY: 2056 next = pos + 1; 2057 continue; 2058 case BEGIN_ATTRIBUTE_LONG: 2059 if (checkNode) 2060 { 2061 j = getIntN(pos+3); 2062 next = j + 1 + (j < 0 ? data.length : pos); 2063 } 2064 else 2065 next = pos + 5; 2066 if (checkAttribute) break; 2067 continue; 2068 case BOOL_FALSE: 2069 case BOOL_TRUE: 2070 next = pos + 1; 2071 if (checkText) break; 2072 continue; 2073 case JOINER: 2074 next = pos + 1; 2075 continue; 2076 case LONG_FOLLOWS: 2077 case DOUBLE_FOLLOWS: 2078 next = pos + 5; 2079 if (checkText) break; 2080 continue; 2081 case PROCESSING_INSTRUCTION: 2082 next = pos + 5 + getIntN(pos+3); 2083 if (checkNode) break; 2084 continue; 2085 case COMMENT: 2086 next = pos + 3 + getIntN(pos+1); 2087 if (checkNode) break; 2088 continue; 2089 case CDATA_SECTION: 2090 next = pos + 3 + getIntN(pos+1); 2091 if (checkText) break; 2092 continue; 2093 case BEGIN_GROUP_LONG: 2094 if (descend) 2095 next = pos + 3; 2096 else 2097 { 2098 j = getIntN(pos+1); 2099 next = j + (j < 0 ? data.length : pos) + 7; 2100 } 2101 if (checkGroup) break; 2102 continue; 2103 default: 2104 if (datum >= BEGIN_GROUP_SHORT 2105 && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX) 2106 { 2107 if (descend) 2108 next = pos + 3; 2109 else 2110 next = pos + data[pos+1] + 2; 2111 if (checkGroup) break; 2112 } 2113 else 2114 throw new Error ("unknown code:"+(int) datum); 2115 continue; 2116 } 2117 if (pos > start && predicate.isInstancePos(this, pos << 1)) 2118 { 2119 if (pos >= gapEnd) 2120 pos -= gapEnd - gapStart; 2121 return pos << 1; 2122 } 2123 } 2124 } 2125 2126 public int nextPos (int position) 2127 { 2128 int index = posToDataIndex(position); 2129 if (index == data.length) 2130 return 0; 2131 if (index >= gapEnd) 2132 index -= gapEnd - gapStart; 2133 return (index << 1) + 3; 2134 } 2135 2136 public final int nextDataIndex(int pos) 2137 { 2138 if (pos == gapStart) 2139 pos = gapEnd; 2140 if (pos == data.length) 2141 return -1; 2142 int j; 2143 char datum = data[pos++]; 2144 if (datum <= MAX_CHAR_SHORT 2145 || (datum >= OBJECT_REF_SHORT 2146 && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX) 2147 || (datum >= INT_SHORT_ZERO + MIN_INT_SHORT 2148 && datum <= INT_SHORT_ZERO + MAX_INT_SHORT)) 2149 return pos; 2150 if (datum >= BEGIN_GROUP_SHORT 2151 && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX) 2152 return data[pos] + pos + 1; 2153 switch (datum) 2154 { 2155 case BEGIN_DOCUMENT: 2156 j = getIntN(pos); 2157 j += j < 0 ? data.length : pos-1; 2158 return j + 1; 2159 case BOOL_FALSE: 2162 case BOOL_TRUE: 2163 case JOINER: 2164 return pos; 2165 case CHAR_FOLLOWS: 2166 return pos + 1; 2167 case POSITION_REF_FOLLOWS: 2168 case OBJECT_REF_FOLLOWS: 2169 case INT_FOLLOWS: 2170 return pos + 2; 2171 case POSITION_PAIR_FOLLOWS: 2172 return pos + 4; 2173 case END_GROUP_SHORT: 2174 case END_GROUP_LONG: 2175 case END_ATTRIBUTE: 2176 case END_DOCUMENT: 2177 return -1; 2178 case BEGIN_GROUP_LONG: 2179 j = getIntN(pos); 2180 j += j < 0 ? data.length : pos-1; 2181 return j + 7; 2182 case BEGIN_ATTRIBUTE_LONG: 2183 j = getIntN(pos+2); 2184 j += j < 0 ? data.length : pos-1; 2185 return j + 1; 2186 case LONG_FOLLOWS: 2187 case DOUBLE_FOLLOWS: 2188 return pos + 4; 2189 case PROCESSING_INSTRUCTION: 2190 pos += 2; 2191 case CDATA_SECTION: 2193 case COMMENT: 2194 return pos + 2 + getIntN(pos); 2195 default: 2196 dump(); 2197 throw new Error ("unknown code:"+Integer.toHexString((int) datum)); 2198 } 2199 } 2200 2201 public Object documentUriOfPos (int pos) 2202 { 2203 int index = posToDataIndex(pos); 2204 if (index == data.length) 2205 return null; 2206 if (data[index] == BEGIN_DOCUMENT) 2207 { 2208 int next = index + 5; 2209 if (next == gapStart) 2210 next = gapEnd; 2211 if (next < data.length && data[next] == DOCUMENT_URI) 2212 return objects[getIntN(next+1)]; 2213 } 2214 return null; 2215 } 2216 2217 2218 public int compare(int ipos1, int ipos2) 2219 { 2220 int i1 = posToDataIndex(ipos1); 2226 int i2 = posToDataIndex(ipos2); 2227 return i1 < i2 ? -1 : i1 > i2 ? 1 : 0; 2228 } 2229 2230 protected int getIndexDifference(int ipos1, int ipos0) 2231 { 2232 int i0 = posToDataIndex(ipos0); 2233 int i1 = posToDataIndex(ipos1); 2234 boolean negate = false; 2235 if (i0 > i1) 2236 { 2237 negate = true; 2238 int i = i1; i1 = i0; i0 = i; 2239 } 2240 int i = 0; 2241 while (i0 < i1) 2242 { 2243 i0 = nextDataIndex(i0); 2244 i++; 2245 } 2246 return negate ? -i : i; 2247 } 2248 2249 public int hashCode() 2250 { 2251 return System.identityHashCode(this); 2253 } 2254 2255 public void consume(Consumer out) 2256 { 2257 consumeIRange(0, data.length, out); 2258 } 2259 2260 public void statistics () 2261 { 2262 java.io.PrintWriter out = new java.io.PrintWriter (System.out); 2263 statistics(out); 2264 out.flush(); 2265 } 2266 2267 public void statistics (java.io.PrintWriter out) 2268 { 2269 out.print("data array length: "); out.println(data.length); 2270 out.print("data array gap: "); out.println(gapEnd-gapStart); 2271 out.print("object array length: "); out.println(objects.length); 2272 } 2273 2274 public void dump () 2276 { 2277 java.io.PrintWriter out = new java.io.PrintWriter (System.out); 2278 2279 dump(out); 2280 out.flush(); 2281 } 2282 2283 public void dump (java.io.PrintWriter out) 2284 { 2285 out.println(getClass().getName()+" @"+Integer.toHexString(System.identityHashCode(this)) 2286 + " gapStart:"+gapStart+" gapEnd:"+gapEnd+" length:"+data.length); 2287 dump(out, 0, data.length); 2288 } 2289 2290 public void dump (java.io.PrintWriter out, int start, int limit) 2291 { 2292 int toskip = 0; 2293 boolean skipFollowingWords = true; 2295 for (int i = start; i < limit; i++) 2296 { 2297 2298 if (i < gapStart || i >= gapEnd) 2299 { 2300 int j; long l; 2301 int ch = data[i]; 2302 out.print(""+i+": 0x"+Integer.toHexString(ch)+'='+((short) ch)); 2303 if (--toskip < 0) 2304 { 2305 if (ch <= MAX_CHAR_SHORT) 2306 { 2307 if (ch >= ' ' && ch < 127) 2308 out.print("='"+((char)ch)+"'"); 2309 else if (ch=='\n') 2310 out.print("='\\n'"); 2311 else 2312 out.print("='\\u"+Integer.toHexString(ch)+"'"); 2313 } 2314 else if (ch >= OBJECT_REF_SHORT 2315 && ch <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX) 2316 { 2317 ch = ch - OBJECT_REF_SHORT; 2318 Object obj = objects[ch]; 2319 out.print("=Object#"+((int)ch)+'=' 2320 +obj+':'+obj.getClass().getName() 2321 +'@'+Integer.toHexString(System.identityHashCode(obj))); 2322 } 2323 else if (ch >= BEGIN_GROUP_SHORT 2324 && ch <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX) 2325 { 2326 ch = ch - BEGIN_GROUP_SHORT; 2327 j = data[i+1] + i; 2328 out.print("=BEGIN_GROUP_SHORT end:"+j+" index#"+((int)ch)+"=<"+objects[ch]+'>'); 2329 toskip = 2; 2330 } 2331 else if (ch >= INT_SHORT_ZERO + MIN_INT_SHORT 2332 && ch <= INT_SHORT_ZERO + MAX_INT_SHORT) 2333 { 2334 out.print("= INT_SHORT:"+(ch-INT_SHORT_ZERO)); 2335 } 2336 else 2337 { 2338 switch (ch) 2339 { 2340 case INT_FOLLOWS: 2341 j = getIntN(i+1); 2342 out.print("=INT_FOLLOWS value:"+j); 2343 toskip = 2; 2344 break; 2345 case LONG_FOLLOWS: 2346 l = getLongN(i+1); 2347 out.print("=LONG_FOLLOWS value:"+l); 2348 toskip = 4; 2349 break; 2350 case FLOAT_FOLLOWS: 2351 j = getIntN(i+1); 2352 out.write("=FLOAT_FOLLOWS value:" 2353 +Float.intBitsToFloat(j)); 2354 toskip = 2; 2355 break; 2356 case DOUBLE_FOLLOWS: 2357 l = getLongN(i+1); 2358 out.print("=DOUBLE_FOLLOWS value:" 2359 +Double.longBitsToDouble(l)); 2360 toskip = 4; 2361 break; 2362 case BEGIN_DOCUMENT: 2363 j = getIntN(i+1); 2364 j += j < 0 ? data.length : i; 2365 out.print("=BEGIN_DOCUMENT end:"); 2366 out.print(j); 2367 out.print(" parent:"); 2368 j = getIntN(i+3); 2369 out.print(j); 2370 toskip = 4; 2371 break; 2372 case BEGIN_ENTITY: 2373 j = getIntN(i+1); 2374 out.print("=BEGIN_ENTITY base:"); 2375 out.print(j); 2376 out.print(" parent:"); 2377 j = getIntN(i+3); 2378 out.print(j); 2379 toskip = 4; 2380 break; 2381 case END_ENTITY: 2382 out.print("=END_ENTITY"); 2383 break; 2384 case DOCUMENT_URI: 2385 out.print("=DOCUMENT_URI: "); 2386 j = getIntN(i+1); 2387 out.print(objects[j]); 2388 toskip = 2; 2389 break; 2390 case COMMENT: 2391 out.print("=COMMENT: '"); 2392 j = getIntN(i+1); 2393 out.write(data, i+3, j); 2394 out.print('\''); 2395 toskip = 2+j; 2396 break; 2397 case CDATA_SECTION: 2398 out.print("=CDATA: '"); 2399 j = getIntN(i+1); 2400 out.write(data, i+3, j); 2401 out.print('\''); 2402 toskip = 2+j; 2403 break; 2404 case PROCESSING_INSTRUCTION: 2405 out.print("=PROCESSING_INSTRUCTION: "); 2406 j = getIntN(i+1); 2407 out.print(objects[j]); 2408 out.print(" '"); 2409 j = getIntN(i+3); 2410 out.write(data, i+5, j); 2411 out.print('\''); 2412 toskip = 4+j; 2413 break; 2414 case END_DOCUMENT: 2415 out.print("=END_DOCUMENT"); 2416 break; 2417 case BOOL_FALSE: out.print("= false"); break; 2418 case BOOL_TRUE: out.print("= true"); break; 2419 case JOINER: out.print("= joiner"); break; 2420 case CHAR_FOLLOWS: 2421 out.print("=CHAR_FOLLOWS"); toskip = 1; break; 2422 case POSITION_REF_FOLLOWS: 2423 case OBJECT_REF_FOLLOWS: 2424 toskip = 2; break; 2425 case END_GROUP_SHORT: 2426 out.print("=END_GROUP_SHORT begin:"); 2427 j = i - data[i+1]; 2428 out.print(j); 2429 j = data[j] - BEGIN_GROUP_SHORT; 2430 out.print(" -> #"); 2431 out.print(j); 2432 out.print("=<"); 2433 out.print(objects[j]); 2434 out.print('>'); 2435 toskip = 1; break; 2436 case BEGIN_GROUP_LONG: 2437 j = getIntN(i+1); 2438 j += j < 0 ? data.length : i; 2439 out.print("=BEGIN_GROUP_LONG end:"); 2440 out.print(j); 2441 j = getIntN(j + 1); 2442 out.print(" -> #"); 2443 out.print(j); 2444 if (j >= 0 && j+1 < objects.length) 2445 out.print("=<"+objects[j]+'>'); 2446 else 2447 out.print("=<out-of-bounds>"); 2448 toskip = 2; 2449 break; 2450 case END_GROUP_LONG: 2451 j = getIntN(i+1); 2452 out.print("=END_GROUP_LONG name:"+j 2453 +"=<"+objects[j]+'>'); 2454 j = getIntN(i+3); 2455 j = j < 0 ? i + j : j; 2456 out.print(" begin:"+j); 2457 j = getIntN(i+5); 2458 j = j < 0 ? i + j : j; 2459 out.print(" parent:"+j); 2460 toskip = 6; 2461 break; 2462 case BEGIN_ATTRIBUTE_LONG: 2463 j = getIntN(i+1); 2464 out.print("=BEGIN_ATTRIBUTE name:"+j 2465 +"="+objects[j]); 2466 j = getIntN(i+3); 2467 j += j < 0 ? data.length : i; 2468 out.print(" end:"+j); 2469 toskip = 4; 2470 break; 2471 case END_ATTRIBUTE: out.print("=END_ATTRIBUTE"); break; 2472 case POSITION_PAIR_FOLLOWS: 2473 out.print("=POSITION_PAIR_FOLLOWS seq:"); 2474 { 2475 j = getIntN(i+1); out.print(j); 2476 out.print('='); 2477 Object seq = objects[j]; 2478 out.print(seq==null?null:seq.getClass().getName()); 2479 out.print('@'); 2480 if (seq == null) out.print("null"); 2481 else out.print(Integer.toHexString(System.identityHashCode(seq))); 2482 out.print(" ipos:"); 2483 out.print(getIntN(i+3)); 2484 } 2485 toskip = 4; 2486 2490 break; 2491 } 2492 } 2493 } 2494 out.println(); 2495 if (skipFollowingWords && toskip > 0) 2496 { 2497 i += toskip; 2498 toskip = 0; 2499 } 2500 } 2501 } 2502 } 2503 } 2505 | Popular Tags |