Mercurial > hg > Members > shoshi > AADS

annotate src/tree/AVLTreeMap.java @ 1:15920e9b562d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
added MulticastQueue.java the BlockingMulticastQueue
author Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
date Tue, 09 Aug 2011 11:13:36 +0900
parents a9cb12a7f995
children 36f2373f867b
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
a9cb12a7f995 hg init
misaka
parents:
diff changeset
1 package tree;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
2
a9cb12a7f995 hg init
misaka
parents:
diff changeset
3 public class AVLTreeMap<K extends Comparable<K>,V> implements Map<K,V>
a9cb12a7f995 hg init
misaka
parents:
diff changeset
4 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
5 private Node<K,V> root;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
6 private final Node<K,V> NULL_NODE = new Node<K,V>(null,null,-1,-1,null,null);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
7
a9cb12a7f995 hg init
misaka
parents:
diff changeset
8 public static void main(String args[])
a9cb12a7f995 hg init
misaka
parents:
diff changeset
9 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
10 AVLTreeMap<Integer,String> map = new AVLTreeMap<Integer,String>();
a9cb12a7f995 hg init
misaka
parents:
diff changeset
11
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
12 map.put(10,"10");
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
13 map.put(20,"20");
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
14 map.put(30,"20");
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
15 map.put(5,"5");
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
16 map.put(7,"7");
0
a9cb12a7f995 hg init
misaka
parents:
diff changeset
17 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
18
a9cb12a7f995 hg init
misaka
parents:
diff changeset
19 public AVLTreeMap()
a9cb12a7f995 hg init
misaka
parents:
diff changeset
20 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
21 root = null;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
22 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
23
a9cb12a7f995 hg init
misaka
parents:
diff changeset
24 @Override
a9cb12a7f995 hg init
misaka
parents:
diff changeset
25 public void put(K key,V value)
a9cb12a7f995 hg init
misaka
parents:
diff changeset
26 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
27 if(root == null){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
28 root = new Node<K,V>(key,value,0,0,NULL_NODE,NULL_NODE);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
29 return;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
30 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
31
a9cb12a7f995 hg init
misaka
parents:
diff changeset
32 root = _put(root,key,value);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
33 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
34
a9cb12a7f995 hg init
misaka
parents:
diff changeset
35 public Node<K,V> _put(Node<K,V> cur,K key,V value)
a9cb12a7f995 hg init
misaka
parents:
diff changeset
36 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
37 int result = cur.key.compareTo(key);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
38
a9cb12a7f995 hg init
misaka
parents:
diff changeset
39 if(result < 0){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
40 //right
a9cb12a7f995 hg init
misaka
parents:
diff changeset
41 if(cur.right == NULL_NODE){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
42 cur.right = new Node<K,V>(key,value,0,0,NULL_NODE,NULL_NODE);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
43 cur.rdepth = 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
44 return cur;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
45 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
46
a9cb12a7f995 hg init
misaka
parents:
diff changeset
47 cur.right = _put(cur.right,key,value);
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
48 cur.rdepth = Math.max(cur.right.ldepth,cur.right.rdepth) + 1;
0
a9cb12a7f995 hg init
misaka
parents:
diff changeset
49 int diff = cur.rdepth - cur.ldepth;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
50
a9cb12a7f995 hg init
misaka
parents:
diff changeset
51 if(diff > 1){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
52 //一重回転か二重回転か判断する。
a9cb12a7f995 hg init
misaka
parents:
diff changeset
53 //以下の式は一重回転の場合は rottype が正になるはず。負の場合は二重回転、0の場合はあり得ない。
a9cb12a7f995 hg init
misaka
parents:
diff changeset
54 int rottype = result * cur.right.key.compareTo(key);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
55 if(rottype > 0){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
56 return singleRotate(cur,OP_RIGHT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
57 }else{
a9cb12a7f995 hg init
misaka
parents:
diff changeset
58 return doubleRotate(cur,OP_RIGHTLEFT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
59 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
60 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
61 }else if(result > 0){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
62 //left
a9cb12a7f995 hg init
misaka
parents:
diff changeset
63 if(cur.left == NULL_NODE){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
64 cur.left = new Node<K,V>(key,value,0,0,NULL_NODE,NULL_NODE);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
65 cur.ldepth = 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
66 return cur;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
67 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
68
a9cb12a7f995 hg init
misaka
parents:
diff changeset
69 cur.left = _put(cur.left,key,value);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
70 cur.ldepth = Math.max(cur.left.ldepth,cur.left.rdepth) + 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
71 int diff = cur.ldepth - cur.rdepth;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
72
a9cb12a7f995 hg init
misaka
parents:
diff changeset
73 if(diff > 1){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
74 //一重回転か二重回転か判断する。
a9cb12a7f995 hg init
misaka
parents:
diff changeset
75 //以下の式は一重回転の場合は rottype が正になるはず。負の場合は二重回転、0の場合はあり得ない。
a9cb12a7f995 hg init
misaka
parents:
diff changeset
76 int rottype = result * cur.left.key.compareTo(key);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
77 if(rottype > 0){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
78 return singleRotate(cur,OP_LEFT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
79 }else{
a9cb12a7f995 hg init
misaka
parents:
diff changeset
80 return doubleRotate(cur,OP_LEFTRIGHT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
81 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
82 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
83 }else{
a9cb12a7f995 hg init
misaka
parents:
diff changeset
84 //find
a9cb12a7f995 hg init
misaka
parents:
diff changeset
85 cur.value = value;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
86 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
87
a9cb12a7f995 hg init
misaka
parents:
diff changeset
88 return cur;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
89 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
90
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
91 public V remove(K key)
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
92 {
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
93 RemoveResult<K,V> r = findRemoveTarget(root,key);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
94 root = r.cur;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
95 return r.target.value;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
96 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
97
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
98 private RemoveResult<K,V> findRemoveTarget(Node<K,V> cur,K key)
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
99 {
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
100 int result = cur.key.compareTo(key);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
101 if(result < 0){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
102 //right
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
103 if(cur == NULL_NODE){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
104 return new RemoveResult<K,V>(cur,NULL_NODE);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
105 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
106
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
107 RemoveResult<K,V> r = findRemoveTarget(cur.right,key);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
108 cur.right = r.cur;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
109 cur.rdepth = Math.max(cur.right.rdepth,cur.right.ldepth) + 1;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
110
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
111 int diff = cur.rdepth - cur.ldepth;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
112 if(diff > 1){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
113 int rottype = result * cur.right.key.compareTo(key);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
114 if(rottype > 0){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
115 r.cur = singleRotate(cur,OP_RIGHT);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
116 return r;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
117 }else{
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
118 r.cur = doubleRotate(cur,OP_RIGHTLEFT);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
119 return r;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
120 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
121 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
122
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
123 r.cur = cur;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
124 return r;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
125 }else if(result > 0 ){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
126 //left
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
127 if(cur == NULL_NODE){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
128 return new RemoveResult<K,V>(cur,NULL_NODE);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
129 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
130
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
131 RemoveResult<K,V> r = findRemoveTarget(cur.left,key);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
132 cur.left = r.cur;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
133 cur.ldepth = Math.max(cur.left.rdepth,cur.left.ldepth) + 1;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
134
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
135 int diff = cur.rdepth - cur.ldepth;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
136 if(diff > 1){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
137 int rottype = result * cur.left.key.compareTo(key);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
138 if(rottype > 0){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
139 r.cur = singleRotate(cur,OP_LEFT);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
140 return r;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
141 }else{
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
142 r.cur = doubleRotate(cur,OP_LEFTRIGHT);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
143 return r;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
144 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
145 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
146
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
147 r.cur = cur;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
148 return r;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
149 }else{
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
150 //find
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
151 if(cur.left == NULL_NODE && cur.right == NULL_NODE){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
152 //delete
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
153 return new RemoveResult<K,V>(NULL_NODE,cur);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
154 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
155
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
156 if(cur.left != NULL_NODE && cur.right == NULL_NODE){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
157 //replace left
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
158 return new RemoveResult<K,V>(cur.left,cur);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
159 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
160
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
161 if(cur.left == NULL_NODE && cur.right != NULL_NODE){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
162 //replace right
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
163 return new RemoveResult<K,V>(cur.right,cur);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
164 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
165
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
166 //both nodes are not null
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
167 RemoveResult<K,V> r = findSubstituteNode(cur.left);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
168 cur.key = r.target.key;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
169 cur.value = r.target.value;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
170 cur.right = r.cur;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
171 cur.rdepth = Math.max(cur.ldepth,cur.rdepth) + 1;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
172
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
173 int diff = cur.rdepth - cur.ldepth;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
174 if(diff > 1){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
175 r.cur = doubleRotate(cur,OP_LEFTRIGHT);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
176 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
177
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
178 return r;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
179 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
180 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
181
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
182 private RemoveResult<K,V> findSubstituteNode(Node<K,V> cur)
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
183 {
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
184 if(cur.right != NULL_NODE){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
185 RemoveResult<K,V> result = findSubstituteNode(cur.right);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
186 cur.right = result.cur;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
187 cur.rdepth = Math.max(cur.right.rdepth,cur.right.ldepth) + 1;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
188
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
189 int diff = cur.ldepth - cur.rdepth;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
190 if(diff > 1){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
191 result.cur = singleRotate(cur.left,OP_LEFT);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
192 return result;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
193 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
194
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
195 result.cur = cur;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
196 return result;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
197 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
198
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
199 RemoveResult<K,V> result = new RemoveResult<K,V>(cur.left,cur);
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
200 return result;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
201 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
202
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
203 private static class RemoveResult<K,V>
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
204 {
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
205 Node<K,V> cur;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
206 Node<K,V> target;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
207
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
208 public RemoveResult(Node<K,V> cur,Node<K,V> target)
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
209 {
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
210 this.cur = cur;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
211 this.target = target;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
212 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
213 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
214
0
a9cb12a7f995 hg init
misaka
parents:
diff changeset
215 private static final int OP_LEFT = 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
216 private static final int OP_RIGHT = 2;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
217
a9cb12a7f995 hg init
misaka
parents:
diff changeset
218 public Node<K,V> singleRotate(Node<K,V> target,int type)
a9cb12a7f995 hg init
misaka
parents:
diff changeset
219 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
220 switch(type){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
221 case OP_LEFT:
a9cb12a7f995 hg init
misaka
parents:
diff changeset
222 Node<K,V> left = target.left;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
223 target.left = left.right;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
224 left.right = target;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
225
a9cb12a7f995 hg init
misaka
parents:
diff changeset
226 target.ldepth = Math.max(target.left.rdepth,target.left.ldepth) + 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
227 left.rdepth = Math.max(left.right.rdepth,left.right.ldepth) + 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
228 return left;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
229 case OP_RIGHT:
a9cb12a7f995 hg init
misaka
parents:
diff changeset
230 Node<K,V> right = target.right;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
231 target.right = right.left;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
232 right.left = target;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
233
a9cb12a7f995 hg init
misaka
parents:
diff changeset
234 target.rdepth = Math.max(target.right.rdepth,target.right.ldepth) + 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
235 right.ldepth = Math.max(right.left.ldepth,right.left.rdepth) + 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
236 return right;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
237 default:
a9cb12a7f995 hg init
misaka
parents:
diff changeset
238 throw new IllegalArgumentException("invalid rotation type");
a9cb12a7f995 hg init
misaka
parents:
diff changeset
239 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
240 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
241
a9cb12a7f995 hg init
misaka
parents:
diff changeset
242 private static final int OP_LEFTRIGHT = 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
243 private static final int OP_RIGHTLEFT = 2;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
244
a9cb12a7f995 hg init
misaka
parents:
diff changeset
245 public Node<K,V> doubleRotate(Node<K,V> target,int type)
a9cb12a7f995 hg init
misaka
parents:
diff changeset
246 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
247 switch(type){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
248 case OP_LEFTRIGHT:
a9cb12a7f995 hg init
misaka
parents:
diff changeset
249 target.left = singleRotate(target.left,OP_RIGHT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
250 return singleRotate(target,OP_LEFT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
251 case OP_RIGHTLEFT:
a9cb12a7f995 hg init
misaka
parents:
diff changeset
252 target.right = singleRotate(target.right,OP_LEFT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
253 return singleRotate(target,OP_RIGHT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
254 default:
a9cb12a7f995 hg init
misaka
parents:
diff changeset
255 throw new IllegalArgumentException("invalid rotation type.");
a9cb12a7f995 hg init
misaka
parents:
diff changeset
256 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
257 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
258
a9cb12a7f995 hg init
misaka
parents:
diff changeset
259 @Override
a9cb12a7f995 hg init
misaka
parents:
diff changeset
260 public V get(K key)
a9cb12a7f995 hg init
misaka
parents:
diff changeset
261 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
262 Node<K,V> cur = root;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
263
a9cb12a7f995 hg init
misaka
parents:
diff changeset
264 while(cur != NULL_NODE){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
265 int result = cur.key.compareTo(key);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
266 if(result < 0){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
267 cur = cur.right;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
268 }else if(result > 0){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
269 cur = cur.left;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
270 }else{
a9cb12a7f995 hg init
misaka
parents:
diff changeset
271 //find
a9cb12a7f995 hg init
misaka
parents:
diff changeset
272 break;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
273 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
274 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
275
a9cb12a7f995 hg init
misaka
parents:
diff changeset
276 return cur.value;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
277 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
278
a9cb12a7f995 hg init
misaka
parents:
diff changeset
279 private static class Node<K,V>
a9cb12a7f995 hg init
misaka
parents:
diff changeset
280 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
281 K key;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
282 V value;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
283
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
284 int rdepth;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
285 int ldepth;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
286
0
a9cb12a7f995 hg init
misaka
parents:
diff changeset
287 Node<K,V> left;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
288 Node<K,V> right;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
289
a9cb12a7f995 hg init
misaka
parents:
diff changeset
290 public Node(K key,V value,int rdepth,int ldepth,Node<K,V> left,Node<K,V> right)
a9cb12a7f995 hg init
misaka
parents:
diff changeset
291 {
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
292 this.right = right;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
293 this.left = left;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
294 this.ldepth = ldepth;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
295 this.rdepth = rdepth;
0
a9cb12a7f995 hg init
misaka
parents:
diff changeset
296 this.key = key;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
297 this.value = value;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
298 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
299
a9cb12a7f995 hg init
misaka
parents:
diff changeset
300 @Override
a9cb12a7f995 hg init
misaka
parents:
diff changeset
301 public String toString()
a9cb12a7f995 hg init
misaka
parents:
diff changeset
302 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
303 return "[" + key + ":" + value + "]";
a9cb12a7f995 hg init
misaka
parents:
diff changeset
304 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
305 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
306 }