001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.math3.geometry.partitioning.utilities;
018
019 /** This class implements AVL trees.
020 *
021 * <p>The purpose of this class is to sort elements while allowing
022 * duplicate elements (i.e. such that {@code a.equals(b)} is
023 * true). The {@code SortedSet} interface does not allow this, so
024 * a specific class is needed. Null elements are not allowed.</p>
025 *
026 * <p>Since the {@code equals} method is not sufficient to
027 * differentiate elements, the {@link #delete delete} method is
028 * implemented using the equality operator.</p>
029 *
030 * <p>In order to clearly mark the methods provided here do not have
031 * the same semantics as the ones specified in the
032 * {@code SortedSet} interface, different names are used
033 * ({@code add} has been replaced by {@link #insert insert} and
034 * {@code remove} has been replaced by {@link #delete
035 * delete}).</p>
036 *
037 * <p>This class is based on the C implementation Georg Kraml has put
038 * in the public domain. Unfortunately, his <a
039 * href="www.purists.org/georg/avltree/index.html">page</a> seems not
040 * to exist any more.</p>
041 *
042 * @param <T> the type of the elements
043 *
044 * @version $Id: AVLTree.java 1416643 2012-12-03 19:37:14Z tn $
045 * @since 3.0
046 */
047 public class AVLTree<T extends Comparable<T>> {
048
049 /** Top level node. */
050 private Node top;
051
052 /** Build an empty tree.
053 */
054 public AVLTree() {
055 top = null;
056 }
057
058 /** Insert an element in the tree.
059 * @param element element to insert (silently ignored if null)
060 */
061 public void insert(final T element) {
062 if (element != null) {
063 if (top == null) {
064 top = new Node(element, null);
065 } else {
066 top.insert(element);
067 }
068 }
069 }
070
071 /** Delete an element from the tree.
072 * <p>The element is deleted only if there is a node {@code n}
073 * containing exactly the element instance specified, i.e. for which
074 * {@code n.getElement() == element}. This is purposely
075 * <em>different</em> from the specification of the
076 * {@code java.util.Set} {@code remove} method (in fact,
077 * this is the reason why a specific class has been developed).</p>
078 * @param element element to delete (silently ignored if null)
079 * @return true if the element was deleted from the tree
080 */
081 public boolean delete(final T element) {
082 if (element != null) {
083 for (Node node = getNotSmaller(element); node != null; node = node.getNext()) {
084 // loop over all elements neither smaller nor larger
085 // than the specified one
086 if (node.element == element) {
087 node.delete();
088 return true;
089 } else if (node.element.compareTo(element) > 0) {
090 // all the remaining elements are known to be larger,
091 // the element is not in the tree
092 return false;
093 }
094 }
095 }
096 return false;
097 }
098
099 /** Check if the tree is empty.
100 * @return true if the tree is empty
101 */
102 public boolean isEmpty() {
103 return top == null;
104 }
105
106
107 /** Get the number of elements of the tree.
108 * @return number of elements contained in the tree
109 */
110 public int size() {
111 return (top == null) ? 0 : top.size();
112 }
113
114 /** Get the node whose element is the smallest one in the tree.
115 * @return the tree node containing the smallest element in the tree
116 * or null if the tree is empty
117 * @see #getLargest
118 * @see #getNotSmaller
119 * @see #getNotLarger
120 * @see Node#getPrevious
121 * @see Node#getNext
122 */
123 public Node getSmallest() {
124 return (top == null) ? null : top.getSmallest();
125 }
126
127 /** Get the node whose element is the largest one in the tree.
128 * @return the tree node containing the largest element in the tree
129 * or null if the tree is empty
130 * @see #getSmallest
131 * @see #getNotSmaller
132 * @see #getNotLarger
133 * @see Node#getPrevious
134 * @see Node#getNext
135 */
136 public Node getLargest() {
137 return (top == null) ? null : top.getLargest();
138 }
139
140 /** Get the node whose element is not smaller than the reference object.
141 * @param reference reference object (may not be in the tree)
142 * @return the tree node containing the smallest element not smaller
143 * than the reference object or null if either the tree is empty or
144 * all its elements are smaller than the reference object
145 * @see #getSmallest
146 * @see #getLargest
147 * @see #getNotLarger
148 * @see Node#getPrevious
149 * @see Node#getNext
150 */
151 public Node getNotSmaller(final T reference) {
152 Node candidate = null;
153 for (Node node = top; node != null;) {
154 if (node.element.compareTo(reference) < 0) {
155 if (node.right == null) {
156 return candidate;
157 }
158 node = node.right;
159 } else {
160 candidate = node;
161 if (node.left == null) {
162 return candidate;
163 }
164 node = node.left;
165 }
166 }
167 return null;
168 }
169
170 /** Get the node whose element is not larger than the reference object.
171 * @param reference reference object (may not be in the tree)
172 * @return the tree node containing the largest element not larger
173 * than the reference object (in which case the node is guaranteed
174 * not to be empty) or null if either the tree is empty or all its
175 * elements are larger than the reference object
176 * @see #getSmallest
177 * @see #getLargest
178 * @see #getNotSmaller
179 * @see Node#getPrevious
180 * @see Node#getNext
181 */
182 public Node getNotLarger(final T reference) {
183 Node candidate = null;
184 for (Node node = top; node != null;) {
185 if (node.element.compareTo(reference) > 0) {
186 if (node.left == null) {
187 return candidate;
188 }
189 node = node.left;
190 } else {
191 candidate = node;
192 if (node.right == null) {
193 return candidate;
194 }
195 node = node.right;
196 }
197 }
198 return null;
199 }
200
201 /** Enum for tree skew factor. */
202 private static enum Skew {
203 /** Code for left high trees. */
204 LEFT_HIGH,
205
206 /** Code for right high trees. */
207 RIGHT_HIGH,
208
209 /** Code for Skew.BALANCED trees. */
210 BALANCED;
211 }
212
213 /** This class implements AVL trees nodes.
214 * <p>AVL tree nodes implement all the logical structure of the
215 * tree. Nodes are created by the {@link AVLTree AVLTree} class.</p>
216 * <p>The nodes are not independant from each other but must obey
217 * specific balancing constraints and the tree structure is
218 * rearranged as elements are inserted or deleted from the tree. The
219 * creation, modification and tree-related navigation methods have
220 * therefore restricted access. Only the order-related navigation,
221 * reading and delete methods are public.</p>
222 * @see AVLTree
223 */
224 public class Node {
225
226 /** Element contained in the current node. */
227 private T element;
228
229 /** Left sub-tree. */
230 private Node left;
231
232 /** Right sub-tree. */
233 private Node right;
234
235 /** Parent tree. */
236 private Node parent;
237
238 /** Skew factor. */
239 private Skew skew;
240
241 /** Build a node for a specified element.
242 * @param element element
243 * @param parent parent node
244 */
245 Node(final T element, final Node parent) {
246 this.element = element;
247 left = null;
248 right = null;
249 this.parent = parent;
250 skew = Skew.BALANCED;
251 }
252
253 /** Get the contained element.
254 * @return element contained in the node
255 */
256 public T getElement() {
257 return element;
258 }
259
260 /** Get the number of elements of the tree rooted at this node.
261 * @return number of elements contained in the tree rooted at this node
262 */
263 int size() {
264 return 1 + ((left == null) ? 0 : left.size()) + ((right == null) ? 0 : right.size());
265 }
266
267 /** Get the node whose element is the smallest one in the tree
268 * rooted at this node.
269 * @return the tree node containing the smallest element in the
270 * tree rooted at this node or null if the tree is empty
271 * @see #getLargest
272 */
273 Node getSmallest() {
274 Node node = this;
275 while (node.left != null) {
276 node = node.left;
277 }
278 return node;
279 }
280
281 /** Get the node whose element is the largest one in the tree
282 * rooted at this node.
283 * @return the tree node containing the largest element in the
284 * tree rooted at this node or null if the tree is empty
285 * @see #getSmallest
286 */
287 Node getLargest() {
288 Node node = this;
289 while (node.right != null) {
290 node = node.right;
291 }
292 return node;
293 }
294
295 /** Get the node containing the next smaller or equal element.
296 * @return node containing the next smaller or equal element or
297 * null if there is no smaller or equal element in the tree
298 * @see #getNext
299 */
300 public Node getPrevious() {
301
302 if (left != null) {
303 final Node node = left.getLargest();
304 if (node != null) {
305 return node;
306 }
307 }
308
309 for (Node node = this; node.parent != null; node = node.parent) {
310 if (node != node.parent.left) {
311 return node.parent;
312 }
313 }
314
315 return null;
316
317 }
318
319 /** Get the node containing the next larger or equal element.
320 * @return node containing the next larger or equal element (in
321 * which case the node is guaranteed not to be empty) or null if
322 * there is no larger or equal element in the tree
323 * @see #getPrevious
324 */
325 public Node getNext() {
326
327 if (right != null) {
328 final Node node = right.getSmallest();
329 if (node != null) {
330 return node;
331 }
332 }
333
334 for (Node node = this; node.parent != null; node = node.parent) {
335 if (node != node.parent.right) {
336 return node.parent;
337 }
338 }
339
340 return null;
341
342 }
343
344 /** Insert an element in a sub-tree.
345 * @param newElement element to insert
346 * @return true if the parent tree should be re-Skew.BALANCED
347 */
348 boolean insert(final T newElement) {
349 if (newElement.compareTo(this.element) < 0) {
350 // the inserted element is smaller than the node
351 if (left == null) {
352 left = new Node(newElement, this);
353 return rebalanceLeftGrown();
354 }
355 return left.insert(newElement) ? rebalanceLeftGrown() : false;
356 }
357
358 // the inserted element is equal to or greater than the node
359 if (right == null) {
360 right = new Node(newElement, this);
361 return rebalanceRightGrown();
362 }
363 return right.insert(newElement) ? rebalanceRightGrown() : false;
364
365 }
366
367 /** Delete the node from the tree.
368 */
369 public void delete() {
370 if ((parent == null) && (left == null) && (right == null)) {
371 // this was the last node, the tree is now empty
372 element = null;
373 top = null;
374 } else {
375
376 Node node;
377 Node child;
378 boolean leftShrunk;
379 if ((left == null) && (right == null)) {
380 node = this;
381 element = null;
382 leftShrunk = node == node.parent.left;
383 child = null;
384 } else {
385 node = (left != null) ? left.getLargest() : right.getSmallest();
386 element = node.element;
387 leftShrunk = node == node.parent.left;
388 child = (node.left != null) ? node.left : node.right;
389 }
390
391 node = node.parent;
392 if (leftShrunk) {
393 node.left = child;
394 } else {
395 node.right = child;
396 }
397 if (child != null) {
398 child.parent = node;
399 }
400
401 while (leftShrunk ? node.rebalanceLeftShrunk() : node.rebalanceRightShrunk()) {
402 if (node.parent == null) {
403 return;
404 }
405 leftShrunk = node == node.parent.left;
406 node = node.parent;
407 }
408
409 }
410 }
411
412 /** Re-balance the instance as left sub-tree has grown.
413 * @return true if the parent tree should be reSkew.BALANCED too
414 */
415 private boolean rebalanceLeftGrown() {
416 switch (skew) {
417 case LEFT_HIGH:
418 if (left.skew == Skew.LEFT_HIGH) {
419 rotateCW();
420 skew = Skew.BALANCED;
421 right.skew = Skew.BALANCED;
422 } else {
423 final Skew s = left.right.skew;
424 left.rotateCCW();
425 rotateCW();
426 switch(s) {
427 case LEFT_HIGH:
428 left.skew = Skew.BALANCED;
429 right.skew = Skew.RIGHT_HIGH;
430 break;
431 case RIGHT_HIGH:
432 left.skew = Skew.LEFT_HIGH;
433 right.skew = Skew.BALANCED;
434 break;
435 default:
436 left.skew = Skew.BALANCED;
437 right.skew = Skew.BALANCED;
438 }
439 skew = Skew.BALANCED;
440 }
441 return false;
442 case RIGHT_HIGH:
443 skew = Skew.BALANCED;
444 return false;
445 default:
446 skew = Skew.LEFT_HIGH;
447 return true;
448 }
449 }
450
451 /** Re-balance the instance as right sub-tree has grown.
452 * @return true if the parent tree should be reSkew.BALANCED too
453 */
454 private boolean rebalanceRightGrown() {
455 switch (skew) {
456 case LEFT_HIGH:
457 skew = Skew.BALANCED;
458 return false;
459 case RIGHT_HIGH:
460 if (right.skew == Skew.RIGHT_HIGH) {
461 rotateCCW();
462 skew = Skew.BALANCED;
463 left.skew = Skew.BALANCED;
464 } else {
465 final Skew s = right.left.skew;
466 right.rotateCW();
467 rotateCCW();
468 switch (s) {
469 case LEFT_HIGH:
470 left.skew = Skew.BALANCED;
471 right.skew = Skew.RIGHT_HIGH;
472 break;
473 case RIGHT_HIGH:
474 left.skew = Skew.LEFT_HIGH;
475 right.skew = Skew.BALANCED;
476 break;
477 default:
478 left.skew = Skew.BALANCED;
479 right.skew = Skew.BALANCED;
480 }
481 skew = Skew.BALANCED;
482 }
483 return false;
484 default:
485 skew = Skew.RIGHT_HIGH;
486 return true;
487 }
488 }
489
490 /** Re-balance the instance as left sub-tree has shrunk.
491 * @return true if the parent tree should be reSkew.BALANCED too
492 */
493 private boolean rebalanceLeftShrunk() {
494 switch (skew) {
495 case LEFT_HIGH:
496 skew = Skew.BALANCED;
497 return true;
498 case RIGHT_HIGH:
499 if (right.skew == Skew.RIGHT_HIGH) {
500 rotateCCW();
501 skew = Skew.BALANCED;
502 left.skew = Skew.BALANCED;
503 return true;
504 } else if (right.skew == Skew.BALANCED) {
505 rotateCCW();
506 skew = Skew.LEFT_HIGH;
507 left.skew = Skew.RIGHT_HIGH;
508 return false;
509 } else {
510 final Skew s = right.left.skew;
511 right.rotateCW();
512 rotateCCW();
513 switch (s) {
514 case LEFT_HIGH:
515 left.skew = Skew.BALANCED;
516 right.skew = Skew.RIGHT_HIGH;
517 break;
518 case RIGHT_HIGH:
519 left.skew = Skew.LEFT_HIGH;
520 right.skew = Skew.BALANCED;
521 break;
522 default:
523 left.skew = Skew.BALANCED;
524 right.skew = Skew.BALANCED;
525 }
526 skew = Skew.BALANCED;
527 return true;
528 }
529 default:
530 skew = Skew.RIGHT_HIGH;
531 return false;
532 }
533 }
534
535 /** Re-balance the instance as right sub-tree has shrunk.
536 * @return true if the parent tree should be reSkew.BALANCED too
537 */
538 private boolean rebalanceRightShrunk() {
539 switch (skew) {
540 case RIGHT_HIGH:
541 skew = Skew.BALANCED;
542 return true;
543 case LEFT_HIGH:
544 if (left.skew == Skew.LEFT_HIGH) {
545 rotateCW();
546 skew = Skew.BALANCED;
547 right.skew = Skew.BALANCED;
548 return true;
549 } else if (left.skew == Skew.BALANCED) {
550 rotateCW();
551 skew = Skew.RIGHT_HIGH;
552 right.skew = Skew.LEFT_HIGH;
553 return false;
554 } else {
555 final Skew s = left.right.skew;
556 left.rotateCCW();
557 rotateCW();
558 switch (s) {
559 case LEFT_HIGH:
560 left.skew = Skew.BALANCED;
561 right.skew = Skew.RIGHT_HIGH;
562 break;
563 case RIGHT_HIGH:
564 left.skew = Skew.LEFT_HIGH;
565 right.skew = Skew.BALANCED;
566 break;
567 default:
568 left.skew = Skew.BALANCED;
569 right.skew = Skew.BALANCED;
570 }
571 skew = Skew.BALANCED;
572 return true;
573 }
574 default:
575 skew = Skew.LEFT_HIGH;
576 return false;
577 }
578 }
579
580 /** Perform a clockwise rotation rooted at the instance.
581 * <p>The skew factor are not updated by this method, they
582 * <em>must</em> be updated by the caller</p>
583 */
584 private void rotateCW() {
585
586 final T tmpElt = element;
587 element = left.element;
588 left.element = tmpElt;
589
590 final Node tmpNode = left;
591 left = tmpNode.left;
592 tmpNode.left = tmpNode.right;
593 tmpNode.right = right;
594 right = tmpNode;
595
596 if (left != null) {
597 left.parent = this;
598 }
599 if (right.right != null) {
600 right.right.parent = right;
601 }
602
603 }
604
605 /** Perform a counter-clockwise rotation rooted at the instance.
606 * <p>The skew factor are not updated by this method, they
607 * <em>must</em> be updated by the caller</p>
608 */
609 private void rotateCCW() {
610
611 final T tmpElt = element;
612 element = right.element;
613 right.element = tmpElt;
614
615 final Node tmpNode = right;
616 right = tmpNode.right;
617 tmpNode.right = tmpNode.left;
618 tmpNode.left = left;
619 left = tmpNode;
620
621 if (right != null) {
622 right.parent = this;
623 }
624 if (left.left != null) {
625 left.left.parent = left;
626 }
627
628 }
629
630 }
631
632 }