|
1
16
17
18 package com.daffodilwoods.rbtreesizesequence.utils.rbtree;
19 import java.util.Comparator  ;
20
21 public class RootWrapper implements Comparable {
22
23 public RBTreeNode root;
24 private Comparator comparator;
25
26 public RootWrapper(){
27 }
28
29 public RootWrapper(RBTreeNode root) {
30 this.root = root;
31 if(this.root != null){
32 this.root.setColor(RBTreeNode.BLACK);
33 this.root.setParent(null);
34 }
35 }
36
37 public RootWrapper(RBTreeNode root, Comparator c) {
38 this.root = root;
39 this.comparator = c;
40 if(this.root != null){
41 this.root.setColor(RBTreeNode.BLACK);
42 this.root.setParent(null);
43 }
44 }
45
46 public void setRoot(RBTreeNode newRoot){
47 this.root = newRoot;
48 if(this.root != null){
49 this.root.setColor(RBTreeNode.BLACK);
50 this.root.setParent(null);
51 }
52 }
53
54 public RBTreeNode getRoot(){
55 return root;
56 }
57
58 private void showTree(RBTreeNode root){
59 if (root.left != null)
60 showTree(root.left);
61 root.show();
62 if (root.right != null)
63 showTree(root.right);
64 }
65
66 public void show(){
67 showTree(root);
68 }
69 public String toString(){
70 return getRoot() != null ? ("< " + first() + ", (" + getRoot().toString() + ") , " + last() + " >") : " <null Root> ";
71 }
72
73 private Object first(){
74 return firstNode().getKey();
75 }
76
77 private Object last(){
78 return lastNode().getKey();
79 }
80
81 private RBTreeNode firstNode() {
82 RBTreeNode root = getRoot();
83 if (root != null)
84 while (root.left != null)
85 root = root.left;
86 return root;
87 }
88
89 private RBTreeNode lastNode() {
90 RBTreeNode root = getRoot();
91 if (root != null)
92 while (root.right != null)
93 root = root.right;
94 return root;
95 }
96
97 public int getBlackHeight(){
98 return getBlackHeight(root);
99 }
100
101 private int getBlackHeight(RBTreeNode p){
102 int height = 0;
103 if (p != null)
104 while (p != null){
105 if(p.getColor()) height++;
106 p = p.getRight();
107 }
108 return height;
109 }
110
111 public int compareTo(Object obj){
112
113 if(root == obj) return 0;
114 return (comparator==null ? ((Comparable )root).compareTo(((RootWrapper)obj).getRoot())
115 : comparator.compare(root, obj));
116 }
117 }
118 |
Popular Tags |
Java API By Example, From Geeks To Geeks.