Mercurial > projects > dwt-addons

comparison dwtx/jface/text/TreeLineTracker.d @ 134:51e6e63f930e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Regex fix for casts
author Frank Benoit <benoit@tionex.de>
date Sun, 24 Aug 2008 01:46:20 +0200
parents 7d818bd32d63
children 6dcb0baaa031
comparison
equal deleted inserted replaced
133:7d818bd32d63 134:51e6e63f930e
320 final List lines= tracker.getLines(); 320 final List lines= tracker.getLines();
321 final int n= lines.size(); 321 final int n= lines.size();
322 if (n is 0) 322 if (n is 0)
323 return; 323 return;
324 324
325 Line line= (Line) lines.get(0); 325 Line line= cast(Line) lines.get(0);
326 String delim= line.delimiter; 326 String delim= line.delimiter;
327 if (delim is null) 327 if (delim is null)
328 delim= NO_DELIM; 328 delim= NO_DELIM;
329 int length= line.length; 329 int length= line.length;
330 fRoot= new Node(length, delim); 330 fRoot= new Node(length, delim);
331 Node node= fRoot; 331 Node node= fRoot;
332 332
333 for (int i= 1; i < n; i++) { 333 for (int i= 1; i < n; i++) {
334 line= (Line) lines.get(i); 334 line= cast(Line) lines.get(i);
335 delim= line.delimiter; 335 delim= line.delimiter;
336 if (delim is null) 336 if (delim is null)
337 delim= NO_DELIM; 337 delim= NO_DELIM;
338 length= line.length; 338 length= line.length;
339 node= insertAfter(node, length, delim); 339 node= insertAfter(node, length, delim);
340 } 340 }
341 341
342 if (node.delimiter !is NO_DELIM) 342 if (node.delimiter !is NO_DELIM)
343 insertAfter(node, 0, NO_DELIM); 343 insertAfter(node, 0, NO_DELIM);
344 344
345 if (ASSERT) checkTree(); 345 if cast(ASSERT) checkTree();
346 } 346 }
347 347
348 /** 348 /**
349 * Returns the node (line) including a certain offset. If the offset is between two 349 * Returns the node (line) including a certain offset. If the offset is between two
350 * lines, the line starting at <code>offset</code> is returned. 350 * lines, the line starting at <code>offset</code> is returned.
502 * previous structural position of <code>node</code>. 502 * previous structural position of <code>node</code>.
503 * 503 *
504 * @param node the node to rotate around 504 * @param node the node to rotate around
505 */ 505 */
506 private void rotateLeft(Node node) { 506 private void rotateLeft(Node node) {
507 if (ASSERT) Assert.isNotNull(node); 507 if cast(ASSERT) Assert.isNotNull(node);
508 Node child= node.right; 508 Node child= node.right;
509 if (ASSERT) Assert.isNotNull(child); 509 if cast(ASSERT) Assert.isNotNull(child);
510 bool leftChild= node.parent is null || node is node.parent.left; 510 bool leftChild= node.parent is null || node is node.parent.left;
511 511
512 // restructure 512 // restructure
513 setChild(node.parent, child, leftChild); 513 setChild(node.parent, child, leftChild);
514 514
527 * previous structural position of <code>node</code>. 527 * previous structural position of <code>node</code>.
528 * 528 *
529 * @param node the node to rotate around 529 * @param node the node to rotate around
530 */ 530 */
531 private void rotateRight(Node node) { 531 private void rotateRight(Node node) {
532 if (ASSERT) Assert.isNotNull(node); 532 if cast(ASSERT) Assert.isNotNull(node);
533 Node child= node.left; 533 Node child= node.left;
534 if (ASSERT) Assert.isNotNull(child); 534 if cast(ASSERT) Assert.isNotNull(child);
535 bool leftChild= node.parent is null || node is node.parent.left; 535 bool leftChild= node.parent is null || node is node.parent.left;
536 536
537 setChild(node.parent, child, leftChild); 537 setChild(node.parent, child, leftChild);
538 538
539 setChild(node, child.right, true); 539 setChild(node, child.right, true);
703 rebalanceAfterInsertionRight(node); 703 rebalanceAfterInsertionRight(node);
704 break; 704 break;
705 case 0: 705 case 0:
706 break; 706 break;
707 default: 707 default:
708 if (ASSERT) 708 if cast(ASSERT)
709 Assert.isTrue(false); 709 Assert.isTrue(false);
710 } 710 }
711 return; 711 return;
712 } 712 }
713 } 713 }
721 Node parent= node.parent; 721 Node parent= node.parent;
722 if (node.balance is 1) { 722 if (node.balance is 1) {
723 singleLeftRotation(node, parent); 723 singleLeftRotation(node, parent);
724 } else if (node.balance is -1) { 724 } else if (node.balance is -1) {
725 rightLeftRotation(node, parent); 725 rightLeftRotation(node, parent);
726 } else if (ASSERT) { 726 } else if cast(ASSERT) {
727 Assert.isTrue(false); 727 Assert.isTrue(false);
728 } 728 }
729 } 729 }
730 730
731 /** 731 /**
737 Node parent= node.parent; 737 Node parent= node.parent;
738 if (node.balance is -1) { 738 if (node.balance is -1) {
739 singleRightRotation(node, parent); 739 singleRightRotation(node, parent);
740 } else if (node.balance is 1) { 740 } else if (node.balance is 1) {
741 leftRightRotation(node, parent); 741 leftRightRotation(node, parent);
742 } else if (ASSERT) { 742 } else if cast(ASSERT) {
743 Assert.isTrue(false); 743 Assert.isTrue(false);
744 } 744 }
745 } 745 }
746 746
747 /* 747 /*
748 * @see dwtx.jface.text.ILineTracker#replace(int, int, java.lang.String) 748 * @see dwtx.jface.text.ILineTracker#replace(int, int, java.lang.String)
749 */ 749 */
750 public final void replace(int offset, int length, String text) throws BadLocationException { 750 public final void replace(int offset, int length, String text) throws BadLocationException {
751 if (ASSERT) checkTree(); 751 if cast(ASSERT) checkTree();
752 752
753 // Inlined nodeByOffset as we need both node and offset 753 // Inlined nodeByOffset as we need both node and offset
754 int remaining= offset; 754 int remaining= offset;
755 Node first= fRoot; 755 Node first= fRoot;
756 final int firstNodeOffset; 756 final int firstNodeOffset;
771 remaining -= first.length; 771 remaining -= first.length;
772 first= first.right; 772 first= first.right;
773 } 773 }
774 } 774 }
775 // Inline nodeByOffset end 775 // Inline nodeByOffset end
776 if (ASSERT) Assert.isTrue(first !is null); 776 if cast(ASSERT) Assert.isTrue(first !is null);
777 777
778 Node last; 778 Node last;
779 if (offset + length < firstNodeOffset + first.length) 779 if (offset + length < firstNodeOffset + first.length)
780 last= first; 780 last= first;
781 else 781 else
782 last= nodeByOffset(offset + length); 782 last= nodeByOffset(offset + length);
783 if (ASSERT) Assert.isTrue(last !is null); 783 if cast(ASSERT) Assert.isTrue(last !is null);
784 784
785 int firstLineDelta= firstNodeOffset + first.length - offset; 785 int firstLineDelta= firstNodeOffset + first.length - offset;
786 if (first is last) 786 if (first is last)
787 replaceInternal(first, text, length, firstLineDelta); 787 replaceInternal(first, text, length, firstLineDelta);
788 else 788 else
789 replaceFromTo(first, last, text, length, firstLineDelta); 789 replaceFromTo(first, last, text, length, firstLineDelta);
790 790
791 if (ASSERT) checkTree(); 791 if cast(ASSERT) checkTree();
792 } 792 }
793 793
794 /** 794 /**
795 * Replace happening inside a single line. 795 * Replace happening inside a single line.
796 * 796 *
911 * 911 *
912 * @param node the node to adjust 912 * @param node the node to adjust
913 * @param delta the character delta to add to the node's length 913 * @param delta the character delta to add to the node's length
914 */ 914 */
915 private void updateLength(Node node, int delta) { 915 private void updateLength(Node node, int delta) {
916 if (ASSERT) Assert.isTrue(node.length + delta >= 0); 916 if cast(ASSERT) Assert.isTrue(node.length + delta >= 0);
917 917
918 // update the node itself 918 // update the node itself
919 node.length += delta; 919 node.length += delta;
920 920
921 // check deletion 921 // check deletion
976 * node. 976 * node.
977 * 977 *
978 * @param node the node to delete. 978 * @param node the node to delete.
979 */ 979 */
980 private void delete(Node node) { 980 private void delete(Node node) {
981 if (ASSERT) Assert.isTrue(node !is null); 981 if cast(ASSERT) Assert.isTrue(node !is null);
982 if (ASSERT) Assert.isTrue(node.length is 0); 982 if cast(ASSERT) Assert.isTrue(node.length is 0);
983 983
984 Node parent= node.parent; 984 Node parent= node.parent;
985 Node toUpdate; // the parent of the node that lost a child 985 Node toUpdate; // the parent of the node that lost a child
986 bool lostLeftChild; 986 bool lostLeftChild;
987 bool isLeftChild= parent is null || node is parent.left; 987 bool isLeftChild= parent is null || node is parent.left;
1016 } else { 1016 } else {
1017 // 3) hard case - replace node with its successor 1017 // 3) hard case - replace node with its successor
1018 Node successor= successor(node); 1018 Node successor= successor(node);
1019 1019
1020 // successor exists (otherwise node would not have right child, case 1) 1020 // successor exists (otherwise node would not have right child, case 1)
1021 if (ASSERT) Assert.isNotNull(successor); 1021 if cast(ASSERT) Assert.isNotNull(successor);
1022 // successor has no left child (a left child would be the real successor of node) 1022 // successor has no left child (a left child would be the real successor of node)
1023 if (ASSERT) Assert.isTrue(successor.left is null); 1023 if cast(ASSERT) Assert.isTrue(successor.left is null);
1024 if (ASSERT) Assert.isTrue(successor.line is 0); 1024 if cast(ASSERT) Assert.isTrue(successor.line is 0);
1025 // successor is the left child of its parent (otherwise parent would be smaller and 1025 // successor is the left child of its parent (otherwise parent would be smaller and
1026 // hence the real successor) 1026 // hence the real successor)
1027 if (ASSERT) Assert.isTrue(successor is successor.parent.left); 1027 if cast(ASSERT) Assert.isTrue(successor is successor.parent.left);
1028 // successor is not a child of node (would have been covered by 2a) 1028 // successor is not a child of node (would have been covered by 2a)
1029 if (ASSERT) Assert.isTrue(successor.parent !is node); 1029 if cast(ASSERT) Assert.isTrue(successor.parent !is node);
1030 1030
1031 toUpdate= successor.parent; 1031 toUpdate= successor.parent;
1032 lostLeftChild= true; 1032 lostLeftChild= true;
1033 1033
1034 // update relative indices 1034 // update relative indices
1085 return; 1085 return;
1086 break; // propagate up 1086 break; // propagate up
1087 case 0: 1087 case 0:
1088 break; // propagate up 1088 break; // propagate up
1089 default: 1089 default:
1090 if (ASSERT) 1090 if cast(ASSERT)
1091 Assert.isTrue(false); 1091 Assert.isTrue(false);
1092 } 1092 }
1093 1093
1094 node= parent; 1094 node= parent;
1095 } 1095 }
1114 rotateLeft(parent); 1114 rotateLeft(parent);
1115 node.balance= -1; 1115 node.balance= -1;
1116 parent.balance= 1; 1116 parent.balance= 1;
1117 return true; 1117 return true;
1118 } else { 1118 } else {
1119 if (ASSERT) Assert.isTrue(false); 1119 if cast(ASSERT) Assert.isTrue(false);
1120 return true; 1120 return true;
1121 } 1121 }
1122 } 1122 }
1123 1123
1124 /** 1124 /**
1140 rotateRight(parent); 1140 rotateRight(parent);
1141 node.balance= 1; 1141 node.balance= 1;
1142 parent.balance= -1; 1142 parent.balance= -1;
1143 return true; 1143 return true;
1144 } else { 1144 } else {
1145 if (ASSERT) Assert.isTrue(false); 1145 if cast(ASSERT) Assert.isTrue(false);
1146 return true; 1146 return true;
1147 } 1147 }
1148 } 1148 }
1149 1149
1150 /** 1150 /**
1174 if (child is parent.left) 1174 if (child is parent.left)
1175 return parent; 1175 return parent;
1176 child= parent; 1176 child= parent;
1177 parent= child.parent; 1177 parent= child.parent;
1178 } 1178 }
1179 if (ASSERT) Assert.isTrue(node.delimiter is NO_DELIM); 1179 if cast(ASSERT) Assert.isTrue(node.delimiter is NO_DELIM);
1180 return null; 1180 return null;
1181 } 1181 }
1182 1182
1183 /** 1183 /**
1184 * Searches the left-most node in a given subtree. 1184 * Searches the left-most node in a given subtree.
1401 * @see java.lang.Object#toString() 1401 * @see java.lang.Object#toString()
1402 */ 1402 */
1403 public String toString() { 1403 public String toString() {
1404 int depth= computeDepth(fRoot); 1404 int depth= computeDepth(fRoot);
1405 int WIDTH= 30; 1405 int WIDTH= 30;
1406 int leaves= (int) Math.pow(2, depth - 1); 1406 int leaves= cast(int) Math.pow(2, depth - 1);
1407 int width= WIDTH * leaves; 1407 int width= WIDTH * leaves;
1408 String empty= "."; //$NON-NLS-1$ 1408 String empty= "."; //$NON-NLS-1$
1409 1409
1410 List roots= new LinkedList(); 1410 List roots= new LinkedList();
1411 roots.add(fRoot); 1411 roots.add(fRoot);
1421 // print nodes 1421 // print nodes
1422 for (ListIterator it= roots.listIterator(); it.hasNext();) { 1422 for (ListIterator it= roots.listIterator(); it.hasNext();) {
1423 // pad before 1423 // pad before
1424 buf.append(space, 0, spaces); 1424 buf.append(space, 0, spaces);
1425 1425
1426 Node node= (Node) it.next(); 1426 Node node= cast(Node) it.next();
1427 String box; 1427 String box;
1428 // replace the node with its children 1428 // replace the node with its children
1429 if (node is null) { 1429 if (node is null) {
1430 it.add(null); 1430 it.add(null);
1431 box= empty; 1431 box= empty;
1461 */ 1461 */
1462 private byte computeDepth(Node root) { 1462 private byte computeDepth(Node root) {
1463 if (root is null) 1463 if (root is null)
1464 return 0; 1464 return 0;
1465 1465
1466 return (byte) (Math.max(computeDepth(root.left), computeDepth(root.right)) + 1); 1466 return cast(byte) (Math.max(computeDepth(root.left), computeDepth(root.right)) + 1);
1467 } 1467 }
1468 1468
1469 /** 1469 /**
1470 * Debug-only method that checks the tree structure and the differential offsets. 1470 * Debug-only method that checks the tree structure and the differential offsets.
1471 */ 1471 */
1495 byte rightDepth= checkTreeStructure(node.right); 1495 byte rightDepth= checkTreeStructure(node.right);
1496 Assert.isTrue(node.balance is rightDepth - leftDepth); 1496 Assert.isTrue(node.balance is rightDepth - leftDepth);
1497 Assert.isTrue(node.left is null || node.left.parent is node); 1497 Assert.isTrue(node.left is null || node.left.parent is node);
1498 Assert.isTrue(node.right is null || node.right.parent is node); 1498 Assert.isTrue(node.right is null || node.right.parent is node);
1499 1499
1500 return (byte) (Math.max(rightDepth, leftDepth) + 1); 1500 return cast(byte) (Math.max(rightDepth, leftDepth) + 1);
1501 } 1501 }
1502 1502
1503 /** 1503 /**
1504 * Debug-only method that checks the differential offsets of the tree, starting at 1504 * Debug-only method that checks the differential offsets of the tree, starting at
1505 * <code>node</code> and continuing until <code>last</code>. 1505 * <code>node</code> and continuing until <code>last</code>.