Mercurial > hg > Members > shoshi > AADS

annotate src/tree/AVLTreeMap.java @ 3:24613dfbaeab default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
finished implementing AVL-Tree remove operation
author Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
date Wed, 10 Aug 2011 23:35:57 +0900
parents 36f2373f867b
children
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");
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
14 map.put(30,"30");
1
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");
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
17
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
18 map.remove(20);
0
a9cb12a7f995 hg init
misaka
parents:
diff changeset
19 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
20
a9cb12a7f995 hg init
misaka
parents:
diff changeset
21 public AVLTreeMap()
a9cb12a7f995 hg init
misaka
parents:
diff changeset
22 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
23 root = null;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
24 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
25
a9cb12a7f995 hg init
misaka
parents:
diff changeset
26 @Override
a9cb12a7f995 hg init
misaka
parents:
diff changeset
27 public void put(K key,V value)
a9cb12a7f995 hg init
misaka
parents:
diff changeset
28 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
29 if(root == null){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
30 root = new Node<K,V>(key,value,0,0,NULL_NODE,NULL_NODE);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
31 return;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
32 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
33
a9cb12a7f995 hg init
misaka
parents:
diff changeset
34 root = _put(root,key,value);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
35 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
36
a9cb12a7f995 hg init
misaka
parents:
diff changeset
37 public Node<K,V> _put(Node<K,V> cur,K key,V value)
a9cb12a7f995 hg init
misaka
parents:
diff changeset
38 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
39 int result = cur.key.compareTo(key);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
40
a9cb12a7f995 hg init
misaka
parents:
diff changeset
41 if(result < 0){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
42 //right
a9cb12a7f995 hg init
misaka
parents:
diff changeset
43 if(cur.right == NULL_NODE){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
44 cur.right = new Node<K,V>(key,value,0,0,NULL_NODE,NULL_NODE);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
45 cur.rdepth = 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
46 return cur;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
47 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
48
a9cb12a7f995 hg init
misaka
parents:
diff changeset
49 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
50 cur.rdepth = Math.max(cur.right.ldepth,cur.right.rdepth) + 1;
0
a9cb12a7f995 hg init
misaka
parents:
diff changeset
51 int diff = cur.rdepth - cur.ldepth;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
52
a9cb12a7f995 hg init
misaka
parents:
diff changeset
53 if(diff > 1){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
54 //一重回転か二重回転か判断する。
a9cb12a7f995 hg init
misaka
parents:
diff changeset
55 //以下の式は一重回転の場合は rottype が正になるはず。負の場合は二重回転、0の場合はあり得ない。
a9cb12a7f995 hg init
misaka
parents:
diff changeset
56 int rottype = result * cur.right.key.compareTo(key);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
57 if(rottype > 0){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
58 return singleRotate(cur,OP_RIGHT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
59 }else{
a9cb12a7f995 hg init
misaka
parents:
diff changeset
60 return doubleRotate(cur,OP_RIGHTLEFT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
61 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
62 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
63 }else if(result > 0){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
64 //left
a9cb12a7f995 hg init
misaka
parents:
diff changeset
65 if(cur.left == NULL_NODE){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
66 cur.left = new Node<K,V>(key,value,0,0,NULL_NODE,NULL_NODE);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
67 cur.ldepth = 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
68 return cur;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
69 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
70
a9cb12a7f995 hg init
misaka
parents:
diff changeset
71 cur.left = _put(cur.left,key,value);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
72 cur.ldepth = Math.max(cur.left.ldepth,cur.left.rdepth) + 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
73 int diff = cur.ldepth - cur.rdepth;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
74
a9cb12a7f995 hg init
misaka
parents:
diff changeset
75 if(diff > 1){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
76 //一重回転か二重回転か判断する。
a9cb12a7f995 hg init
misaka
parents:
diff changeset
77 //以下の式は一重回転の場合は rottype が正になるはず。負の場合は二重回転、0の場合はあり得ない。
a9cb12a7f995 hg init
misaka
parents:
diff changeset
78 int rottype = result * cur.left.key.compareTo(key);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
79 if(rottype > 0){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
80 return singleRotate(cur,OP_LEFT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
81 }else{
a9cb12a7f995 hg init
misaka
parents:
diff changeset
82 return doubleRotate(cur,OP_LEFTRIGHT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
83 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
84 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
85 }else{
a9cb12a7f995 hg init
misaka
parents:
diff changeset
86 //find
a9cb12a7f995 hg init
misaka
parents:
diff changeset
87 cur.value = value;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
88 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
89
a9cb12a7f995 hg init
misaka
parents:
diff changeset
90 return cur;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
91 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
92
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
93 public V remove(K _key)
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
94 {
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
95 RemoveResult<K,V> r = removeTarget(root,_key);
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
96 root = r.cur;
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
97 return r.removed.value;
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
98 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
99
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
100 private RemoveResult<K,V> removeTarget(Node<K,V> _cur,K _key)
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
101 {
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
102 int result = _cur.key.compareTo(_key);
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
103
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
104 if(result < 0){
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
105 //right
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
106 if(_cur.right == NULL_NODE){
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
107 //not found
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
108 return new RemoveResult<K,V>(_cur,NULL_NODE);
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
109 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
110
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
111 RemoveResult<K,V> r = removeTarget(_cur.right,_key);
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
112 _cur.right = r.cur;
3
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
113 r.cur = _cur;
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
114 _cur.rdepth = Math.max(_cur.right.ldepth,_cur.right.rdepth) + 1;
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
115
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
116 //要素の削除では，部分木の要素が減ったと考えるのではなく，もう片方の部分木の要素が増えたと考えれば書きやすい
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
117 int diff = _cur.ldepth - _cur.rdepth;
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
118 if(diff > 1){
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
119 //determine that rotation will be single or double
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
120 Node<K,V> left = _cur.left;
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
121 int rottype = left.ldepth - left.rdepth;
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
122 if(rottype >= 0){
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
123 r.cur = singleRotate(_cur,OP_LEFT);
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
124 }else{
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
125 r.cur = doubleRotate(_cur,OP_LEFTRIGHT);
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
126 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
127 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
128
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
129 return r;
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
130 }else if(result > 0){
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
131 //left
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
132 if(_cur.left == NULL_NODE){
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
133 //not found
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
134 return new RemoveResult<K,V>(_cur,NULL_NODE);
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
135 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
136
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
137 RemoveResult<K,V> r = removeTarget(_cur.right,_key);
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
138 _cur.left = r.cur;
3
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
139 r.cur = _cur;
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
140 _cur.rdepth = Math.max(_cur.right.ldepth,_cur.right.rdepth) + 1;
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
141
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
142 int diff = _cur.rdepth - _cur.ldepth;
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
143 if(diff > 1){
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
144 //determine that rotation will be single or double
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
145 Node<K,V> right = _cur.right;
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
146 int rottype = right.rdepth - right.ldepth;
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
147 if(rottype >= 0){
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
148 r.cur = singleRotate(_cur,OP_RIGHT);
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
149 }else{
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
150 r.cur = doubleRotate(_cur,OP_RIGHTLEFT);
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
151 }
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
152 }
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
153 }
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
154
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
155 //find.
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
156
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
157 //見つかったので，ノードの代わりのノードを検索する．
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
158 RemoveResult<K,V> r = findNearestNode(_cur.left);
3
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
159 if(r == null){
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
160 //左部分木は存在していない、そのため右部分木をかわりに配置する
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
161 r = new RemoveResult<K,V>(_cur,_cur.right);
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
162 }else{
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
163 //左部分木より代替ノードを取得した
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
164 r.removed = new Node<K,V>(_cur.key,_cur.value,0,0,NULL_NODE,NULL_NODE);
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
165 _cur.key = r.removed.key;
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
166 _cur.value = r.removed.value;
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
167 _cur.left = r.cur;
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
168 r.cur = _cur;
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
169
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
170 _cur.ldepth = Math.max(_cur.left.ldepth,_cur.left.rdepth) + 1;
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
171
3
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
172 int diff = _cur.rdepth - _cur.ldepth;
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
173 if(diff > 1){
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
174 Node<K,V> right = _cur.right;
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
175 int rottype = right.rdepth - right.ldepth;
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
176 if(rottype >= 0){
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
177 r.cur = singleRotate(_cur,OP_RIGHT);
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
178 }else{
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
179 r.cur = doubleRotate(_cur,OP_RIGHTLEFT);
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
180 }
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
181 }
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
182
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
183 r.removed = _cur;
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
184 }
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
185
3
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
186 return r;
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
187 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
188
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
189 public RemoveResult<K,V> findNearestNode(Node<K,V> _cur)
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
190 {
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
191 if(_cur == NULL_NODE){
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
192 return null;
1
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
3
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
195 RemoveResult<K,V> r = findNearestNode(_cur.right);
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
196 if(r == null){
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
197 r = new RemoveResult<K,V>(_cur,_cur.left);
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
198 return r;
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
199 }
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
200 _cur.right = r.cur;
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
201 _cur.ldepth = Math.max(_cur.left.ldepth,_cur.left.rdepth) + 1;
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
202 r.cur = _cur;
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
203 int diff = _cur.rdepth - _cur.ldepth;
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
204
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
205 if(diff > 1){
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
206 Node<K,V> left = _cur.left;
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
207 int rottype = left.ldepth - left.rdepth;
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
208 if(rottype >= 0){
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
209 r.cur = singleRotate(_cur,OP_LEFT);
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
210 }else{
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
211 r.cur = doubleRotate(_cur,OP_LEFTRIGHT);
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
212 }
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
213 }
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
214
24613dfbaeab finished implementing AVL-Tree remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
215 return r;
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
216 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
217
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
218 public static class RemoveResult<K,V>
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
219 {
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
220 public Node<K,V> removed;
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
221 public Node<K,V> cur;
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
222
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
223 public RemoveResult(Node<K,V> _removed,Node<K,V> _cur)
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
224 {
2
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
225 removed = _removed;
36f2373f867b added AVLTree.java remove operation
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
226 cur = _cur;
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
227 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
228 }
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
229
0
a9cb12a7f995 hg init
misaka
parents:
diff changeset
230 private static final int OP_LEFT = 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
231 private static final int OP_RIGHT = 2;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
232
a9cb12a7f995 hg init
misaka
parents:
diff changeset
233 public Node<K,V> singleRotate(Node<K,V> target,int type)
a9cb12a7f995 hg init
misaka
parents:
diff changeset
234 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
235 switch(type){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
236 case OP_LEFT:
a9cb12a7f995 hg init
misaka
parents:
diff changeset
237 Node<K,V> left = target.left;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
238 target.left = left.right;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
239 left.right = target;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
240
a9cb12a7f995 hg init
misaka
parents:
diff changeset
241 target.ldepth = Math.max(target.left.rdepth,target.left.ldepth) + 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
242 left.rdepth = Math.max(left.right.rdepth,left.right.ldepth) + 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
243 return left;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
244 case OP_RIGHT:
a9cb12a7f995 hg init
misaka
parents:
diff changeset
245 Node<K,V> right = target.right;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
246 target.right = right.left;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
247 right.left = target;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
248
a9cb12a7f995 hg init
misaka
parents:
diff changeset
249 target.rdepth = Math.max(target.right.rdepth,target.right.ldepth) + 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
250 right.ldepth = Math.max(right.left.ldepth,right.left.rdepth) + 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
251 return right;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
252 default:
a9cb12a7f995 hg init
misaka
parents:
diff changeset
253 throw new IllegalArgumentException("invalid rotation type");
a9cb12a7f995 hg init
misaka
parents:
diff changeset
254 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
255 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
256
a9cb12a7f995 hg init
misaka
parents:
diff changeset
257 private static final int OP_LEFTRIGHT = 1;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
258 private static final int OP_RIGHTLEFT = 2;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
259
a9cb12a7f995 hg init
misaka
parents:
diff changeset
260 public Node<K,V> doubleRotate(Node<K,V> target,int type)
a9cb12a7f995 hg init
misaka
parents:
diff changeset
261 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
262 switch(type){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
263 case OP_LEFTRIGHT:
a9cb12a7f995 hg init
misaka
parents:
diff changeset
264 target.left = singleRotate(target.left,OP_RIGHT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
265 return singleRotate(target,OP_LEFT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
266 case OP_RIGHTLEFT:
a9cb12a7f995 hg init
misaka
parents:
diff changeset
267 target.right = singleRotate(target.right,OP_LEFT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
268 return singleRotate(target,OP_RIGHT);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
269 default:
a9cb12a7f995 hg init
misaka
parents:
diff changeset
270 throw new IllegalArgumentException("invalid rotation type.");
a9cb12a7f995 hg init
misaka
parents:
diff changeset
271 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
272 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
273
a9cb12a7f995 hg init
misaka
parents:
diff changeset
274 @Override
a9cb12a7f995 hg init
misaka
parents:
diff changeset
275 public V get(K key)
a9cb12a7f995 hg init
misaka
parents:
diff changeset
276 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
277 Node<K,V> cur = root;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
278
a9cb12a7f995 hg init
misaka
parents:
diff changeset
279 while(cur != NULL_NODE){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
280 int result = cur.key.compareTo(key);
a9cb12a7f995 hg init
misaka
parents:
diff changeset
281 if(result < 0){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
282 cur = cur.right;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
283 }else if(result > 0){
a9cb12a7f995 hg init
misaka
parents:
diff changeset
284 cur = cur.left;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
285 }else{
a9cb12a7f995 hg init
misaka
parents:
diff changeset
286 //find
a9cb12a7f995 hg init
misaka
parents:
diff changeset
287 break;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
288 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
289 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
290
a9cb12a7f995 hg init
misaka
parents:
diff changeset
291 return cur.value;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
292 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
293
a9cb12a7f995 hg init
misaka
parents:
diff changeset
294 private static class Node<K,V>
a9cb12a7f995 hg init
misaka
parents:
diff changeset
295 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
296 K key;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
297 V value;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
298
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
299 int rdepth;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
300 int ldepth;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
301
0
a9cb12a7f995 hg init
misaka
parents:
diff changeset
302 Node<K,V> left;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
303 Node<K,V> right;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
304
a9cb12a7f995 hg init
misaka
parents:
diff changeset
305 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
306 {
1
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
307 this.right = right;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
308 this.left = left;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
309 this.ldepth = ldepth;
15920e9b562d added MulticastQueue.java the BlockingMulticastQueue
Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
310 this.rdepth = rdepth;
0
a9cb12a7f995 hg init
misaka
parents:
diff changeset
311 this.key = key;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
312 this.value = value;
a9cb12a7f995 hg init
misaka
parents:
diff changeset
313 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
314
a9cb12a7f995 hg init
misaka
parents:
diff changeset
315 @Override
a9cb12a7f995 hg init
misaka
parents:
diff changeset
316 public String toString()
a9cb12a7f995 hg init
misaka
parents:
diff changeset
317 {
a9cb12a7f995 hg init
misaka
parents:
diff changeset
318 return "[" + key + ":" + value + "]";
a9cb12a7f995 hg init
misaka
parents:
diff changeset
319 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
320 }
a9cb12a7f995 hg init
misaka
parents:
diff changeset
321 }