Posted By

obrienm on 08/29/14


Tagged


Versions (?)

Editor Trees - EditTree Class


 / Published in: Java
 

Data Structures & Algorithm Analysis Project

  1. package editortrees;
  2.  
  3. // A height-balanced binary tree with rank that could be the basis for a text editor.
  4.  
  5. public class EditTree {
  6.  
  7. public Node root;
  8. private int size;
  9. int totalRotationCount;
  10.  
  11. /**
  12. * Construct an empty tree
  13. */
  14. public EditTree() {
  15. this.root = Node.NULL_NODE;
  16. this.size = 0;
  17. this.totalRotationCount = 0;
  18. }
  19.  
  20. /**
  21. * Construct a single-node tree whose element is c
  22. *
  23. * @param c
  24. */
  25. public EditTree(char c) {
  26. this.root = new Node(c);
  27. this.size = 1;
  28. this.totalRotationCount = 0;
  29. }
  30.  
  31. /**
  32. * Create an EditTree whose toString is s. This can be done in O(N) time,
  33. * where N is the length of the tree (repeatedly calling insert() would be
  34. * O(N log N), so you need to find a more efficient way to do this.
  35. *
  36. * @param s
  37. */
  38. public EditTree(String s) {
  39. this.root = new Node('x');
  40. this.root.buildStringTree(s);
  41. this.size = this.root.size;
  42. this.totalRotationCount = 0;
  43. }
  44.  
  45. /**
  46. * Make this tree be a copy of e, with all new nodes, but the same shape and
  47. * contents.
  48. *
  49. * @param e
  50. */
  51. public EditTree(EditTree e) {
  52. if (e.root != Node.NULL_NODE) {
  53. this.root = new Node();
  54. this.root.editTreeCopy(e.root);
  55. this.size = e.size;
  56. this.totalRotationCount = e.totalRotationCount;
  57. } else {
  58. this.root = Node.NULL_NODE;
  59. this.size = 0;
  60. this.totalRotationCount = 0;
  61. }
  62.  
  63. }
  64.  
  65. /**
  66. *
  67. * @return the height of this tree
  68. */
  69. public int height() {
  70. return this.root.height;
  71. }
  72.  
  73. /**
  74. *
  75. * returns the total number of rotations done in this tree since it was
  76. * created. A double rotation counts as two.
  77. *
  78. * @return number of rotations since tree was created.
  79. */
  80. public int totalRotationCount() {
  81. return this.totalRotationCount;
  82. }
  83.  
  84. /**
  85. * return the string produced by an inorder traversal of this tree
  86. */
  87. @Override
  88. public String toString() {
  89. if (this.root == Node.NULL_NODE) {
  90. return "";
  91. }
  92. return this.root.toString();
  93. }
  94.  
  95. /**
  96. *
  97. * @param pos
  98. * position in the tree
  99. * @return the character at that position
  100. * @throws IndexOutOfBoundsException
  101. */
  102. public char get(int pos) throws IndexOutOfBoundsException {
  103. if (pos < 0 || pos >= this.size || this.root == Node.NULL_NODE) {
  104. }
  105. return this.root.get(pos).element;
  106. }
  107.  
  108. /**
  109. *
  110. * @param c
  111. * character to add to the end of this tree.
  112. */
  113. public void add(char c) {
  114. if (this.root == Node.NULL_NODE) {
  115. this.root = new Node(c);
  116. this.size++;
  117. } else {
  118. this.add(c, this.size);
  119. }
  120. }
  121.  
  122. /**
  123. *
  124. * @param c
  125. * character to add
  126. * @param pos
  127. * character added in this inorder position
  128. * @throws IndexOutOfBoundsException
  129. * id pos is negative or too large for this tree
  130. */
  131. public void add(char c, int pos) throws IndexOutOfBoundsException {
  132. if (pos < 0 || pos > this.size) {
  133. }
  134. if (this.root == Node.NULL_NODE) {
  135. this.root = new Node(c);
  136. } else {
  137. this.root.add(c, pos, this);
  138. }
  139. this.size++;
  140. }
  141.  
  142. /**
  143. *
  144. * @return the number of nodes in this tree
  145. */
  146. public int size() {
  147. return this.size;
  148. }
  149.  
  150. /**
  151. *
  152. * @param pos
  153. * position of character to delete from this tree
  154. * @return the character that is deleted
  155. * @throws IndexOutOfBoundsException
  156. */
  157. public char delete(int pos) throws IndexOutOfBoundsException {
  158. if (pos < 0 || pos >= this.size || this.root == Node.NULL_NODE) {
  159. }
  160. if (this.size == 1) {
  161. char temp = this.root.element;
  162. this.root = Node.NULL_NODE;
  163. this.size = 0;
  164. return temp;
  165. }
  166. return this.root.get(pos).delete(this);
  167. }
  168.  
  169. /**
  170. * This method operates in O(length*log N), where N is the size of this
  171. * tree.
  172. *
  173. * @param pos
  174. * location of the beginning of the string to retrieve
  175. * @param length
  176. * length of the string to retrieve
  177. * @return string of length that starts in position pos
  178. * @throws IndexOutOfBoundsException
  179. * unless both pos and pos+length-1 are legitimate indexes
  180. * within this tree.
  181. */
  182. public String get(int pos, int length) throws IndexOutOfBoundsException {
  183. if (pos < 0 || (pos + length) > this.size) {
  184. throw new IndexOutOfBoundsException("The index is out of bounds!");
  185. }
  186. Node start = this.root.get(pos);
  187. return start.getString(length);
  188. }
  189.  
  190. /**
  191. * This method is provided for you, and should not need to be changed. If
  192. * split() and concatenate() are O(log N) operations as required, delete
  193. * should also be O(log N)
  194. *
  195. * @param start
  196. * position of beginning of string to delete
  197. *
  198. * @param length
  199. * length of string to delete
  200. * @return an EditTree containing the deleted string
  201. * @throws IndexOutOfBoundsException
  202. * unless both start and start+length-1 are in range for this
  203. * tree.
  204. */
  205. public EditTree delete(int start, int length)
  206. if (start < 0 || start + length >= this.size())
  207. (start < 0) ? "negative first argument to delete"
  208. : "delete range extends past end of string");
  209. EditTree t2 = this.split(start);
  210. EditTree t3 = t2.split(length);
  211. this.concatenate(t3);
  212. return t2;
  213. }
  214.  
  215. /**
  216. * Append (in time proportional to the log of the size of the larger tree)
  217. * the contents of the other tree to this one. Other should be made empty
  218. * after this operation.
  219. *
  220. * @param other
  221. * @throws IllegalArgumentException
  222. * if this == other
  223. */
  224. public void concatenate(EditTree other) throws IllegalArgumentException {
  225.  
  226. if (this == other) {
  227. throw new IllegalArgumentException("Invalid request!");
  228. }
  229. if (other.root == Node.NULL_NODE) {
  230. // do nothing
  231. }
  232. // If the original tree was empty it is just replaced with the other
  233. // tree.
  234. else if (this.root == Node.NULL_NODE) {
  235. this.root = new Node();
  236. this.root = other.root;
  237. this.size = other.size;
  238. other.size = 0;
  239. other.root = Node.NULL_NODE;
  240. }
  241. // If the trees are both of size 1 then the new tree is just the old
  242. // with the root's right the old root of the other tree.
  243. else if (this.size == 1 && other.size == 1) {
  244. this.root.right = other.root;
  245. this.root.right.parent = this.root;
  246. this.root.size++;
  247. this.size++;
  248. other.size = 0;
  249. other.root = Node.NULL_NODE;
  250. }
  251. // Traverses down to the far left leaf of the tree being concatenated to
  252. // the old tree and calls the Node concatenate method at that node.
  253. else {
  254. Node current = other.root;
  255. // Finds the far left leaf and adjusts sizes and ranks accordingly.
  256. while (current.left != Node.NULL_NODE) {
  257. current.rank--;
  258. current.size--;
  259. current = current.left;
  260. }
  261. this.root.concatenate(other.root, current);
  262. if (this.root.parent != Node.NULL_NODE) {
  263. this.root = this.root.parent;
  264. }
  265. // Fixes the trees' sizes and empties the other tree.
  266. this.size = this.size + other.size;
  267. other.size = 0;
  268. other.root = Node.NULL_NODE;
  269. }
  270. }
  271.  
  272. /**
  273. * This operation must be done in time proportional to the height of this
  274. * tree.
  275. *
  276. * @param pos
  277. * where to split this tree
  278. * @return a new tree containing all of the elements of this tree whose
  279. * positions are >= position. Their nodes are removed from this
  280. * tree.
  281. * @throws IndexOutOfBoundsException
  282. */
  283. public EditTree split(int pos) throws IndexOutOfBoundsException {
  284. if (pos < 0 || pos >= this.toString().length()) {
  285. "Invalid request!");
  286. }
  287. EditTree[] trees = new EditTree[2];
  288. trees = this.root.get(pos).split();
  289.  
  290. this.root = trees[0].root;
  291. if (this.root != Node.NULL_NODE) {
  292. this.setTreeSize();
  293. }
  294. if (trees[1].root != Node.NULL_NODE) {
  295. trees[1].setTreeSize();
  296. }
  297.  
  298. return trees[1];
  299.  
  300. }
  301.  
  302. /**
  303. * Don't worry if you can't do this one efficiently.
  304. *
  305. * @param s
  306. * the string to look for
  307. * @return the position in this tree of the first occurrence of s; -1 if s
  308. * does not occur
  309. */
  310. public int find(String s) {
  311. if (!this.toString().contains(s)) {
  312. return -1;
  313. }
  314. return this.toString().indexOf(s);
  315. }
  316.  
  317. /**
  318. *
  319. * @param s
  320. * the string to search for
  321. * @param pos
  322. * the position in the tree to begin the search
  323. * @return the position in this tree of the first occurrence of s that does
  324. * not occur before position pos; -1 if s does not occur
  325. */
  326. public int find(String s, int pos) {
  327. String current = this.toString().substring(pos);
  328. if (!current.contains(s)) {
  329. return -1;
  330. }
  331. return current.indexOf(s) + pos;
  332. }
  333.  
  334. /**
  335. * @return The root of this tree.
  336. */
  337. public Node getRoot() {
  338. return this.root;
  339. }
  340.  
  341. /**
  342. * Sets the tree size.
  343. */
  344. public void setTreeSize() {
  345. this.size = this.root.left.size + this.root.right.size + 1;
  346. }
  347.  
  348. }

Report this snippet  

You need to login to post a comment.