1 | import java.util.*; |
2 | |
3 | public class LogNArray<Value> extends AbstractList<Value> implements RandomAccess { |
4 | // Structure is a left-leaning red-black BST, 2-3 version |
5 | |
6 | private static final boolean RED = true; |
7 | private static final boolean BLACK = false; |
8 | |
9 | private Node<Value> root; // root of the BST |
10 | |
11 | // BST helper node data type |
12 | private final static class Node<Value> { |
13 | private Value val; // associated data |
14 | private Node<Value> left, right; // links to left and right subtrees |
15 | private int sizeAndColor; // subtree count + color (highest bit) |
16 | |
17 | Node() {} |
18 | |
19 | Node(Value val, boolean color, int size) { |
20 | this.val = val; |
21 | sizeAndColor = size | (color ? 0x80000000 : 0); |
22 | } |
23 | |
24 | int size() { return sizeAndColor & 0x7FFFFFFF; } |
25 | boolean color() { return sizeAndColor < 0; } |
26 | |
27 | void setSize(int size) { sizeAndColor = sizeAndColor & 0x80000000 | size; } |
28 | void setColor(boolean color) { sizeAndColor = size() | (color ? 0x80000000 : 0); } |
29 | } |
30 | |
31 | // is node x red; false if x is null ? |
32 | private boolean isRed(Node<Value> x) { |
33 | if (x == null) return false; |
34 | return x.color() == RED; |
35 | } |
36 | |
37 | // number of node in subtree rooted at x; 0 if x is null |
38 | private int size(Node<Value> x) { |
39 | if (x == null) return 0; |
40 | return x.size(); |
41 | } |
42 | |
43 | |
44 | public int size() { |
45 | return size(root); |
46 | } |
47 | |
48 | public boolean isEmpty() { |
49 | return root == null; |
50 | } |
51 | |
52 | |
53 | public void add(int idx, Value val) { |
54 | if (idx < 0 || idx > size()) throw new IndexOutOfBoundsException(idx + " / " + size()); |
55 | |
56 | root = add(root, idx, val); |
57 | root.setColor(BLACK); |
58 | } |
59 | |
60 | // insert the value pair in index k of subtree rooted at h |
61 | private Node<Value> add(Node<Value> h, int k, Value val) { |
62 | if (h == null) return new Node(val, RED, 1); |
63 | |
64 | int t = size(h.left); |
65 | if (k < t) |
66 | // replace / fit in left child |
67 | h.left = add(h.left, k, val); |
68 | else if (k == t) { |
69 | // move value to right child, replace value |
70 | h.right = add(h.right, 0, h.val); |
71 | h.val = val; |
72 | } else |
73 | // replace / fit in right child |
74 | h.right = add(h.right, k-t-1, val); |
75 | |
76 | // fix-up any right-leaning links |
77 | if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); |
78 | if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); |
79 | if (isRed(h.left) && isRed(h.right)) flipColors(h); |
80 | h.setSize(size(h.left) + size(h.right) + 1); |
81 | |
82 | return h; |
83 | } |
84 | |
85 | public Value remove(int idx) { |
86 | Value oldValue = get(idx); |
87 | |
88 | // if both children of root are black, set root to red |
89 | if (!isRed(root.left) && !isRed(root.right)) |
90 | root.setColor(RED); |
91 | |
92 | root = remove(root, idx); |
93 | if (root != null) root.setColor(BLACK); |
94 | |
95 | return oldValue; |
96 | } |
97 | |
98 | private Node<Value> remove(Node<Value> h, int k) { |
99 | int t = size(h.left); |
100 | if (k < t) { // remove from left child |
101 | if (!isRed(h.left) && !isRed(h.left.left)) |
102 | h = moveRedLeft(h); |
103 | h.left = remove(h.left, k); |
104 | } else { // remove from center or right child |
105 | if (isRed(h.left)) { |
106 | h = rotateRight(h); |
107 | t = size(h.left); |
108 | } |
109 | if (h.right == null) return null; // drop whole node |
110 | if (!isRed(h.right) && !isRed(h.right.left)) { |
111 | h = moveRedRight(h); |
112 | t = size(h.left); |
113 | } |
114 | if (k == t) { // replace center value with min of right child |
115 | h.val = nodeAtIndex(h.right, 0).val; |
116 | h.right = remove(h.right, 0); |
117 | } |
118 | else h.right = remove(h.right, k-t-1); |
119 | } |
120 | return balance(h); |
121 | } |
122 | |
123 | // make a left-leaning link lean to the right |
124 | private Node<Value> rotateRight(Node<Value> h) { |
125 | // assert (h != null) && isRed(h.left); |
126 | Node<Value> x = h.left; |
127 | h.left = x.right; |
128 | x.right = h; |
129 | x.setColor(x.right.color()); |
130 | x.right.setColor(RED); |
131 | x.setSize(h.size()); |
132 | h.setSize(size(h.left) + size(h.right) + 1); |
133 | return x; |
134 | } |
135 | |
136 | // make a right-leaning link lean to the left |
137 | private Node<Value> rotateLeft(Node<Value> h) { |
138 | // assert (h != null) && isRed(h.right); |
139 | Node<Value> x = h.right; |
140 | h.right = x.left; |
141 | x.left = h; |
142 | x.setColor(x.left.color()); |
143 | x.left.setColor(RED); |
144 | x.setSize(h.size()); |
145 | h.setSize(size(h.left) + size(h.right) + 1); |
146 | return x; |
147 | } |
148 | |
149 | // flip the colors of a node and its two children |
150 | private void flipColors(Node<Value> h) { |
151 | // h must have opposite color of its two children |
152 | // assert (h != null) && (h.left != null) && (h.right != null); |
153 | // assert (!isRed(h) && isRed(h.left) && isRed(h.right)) |
154 | // || (isRed(h) && !isRed(h.left) && !isRed(h.right)); |
155 | h.setColor(!h.color()); |
156 | h.left.setColor(!h.left.color()); |
157 | h.right.setColor(!h.right.color()); |
158 | } |
159 | |
160 | // Assuming that h is red and both h.left and h.left.left |
161 | // are black, make h.left or one of its children red. |
162 | private Node<Value> moveRedLeft(Node<Value> h) { |
163 | // assert (h != null); |
164 | // assert isRed(h) && !isRed(h.left) && !isRed(h.left.left); |
165 | |
166 | flipColors(h); |
167 | if (isRed(h.right.left)) { |
168 | h.right = rotateRight(h.right); |
169 | h = rotateLeft(h); |
170 | flipColors(h); |
171 | } |
172 | return h; |
173 | } |
174 | |
175 | // Assuming that h is red and both h.right and h.right.left |
176 | // are black, make h.right or one of its children red. |
177 | private Node<Value> moveRedRight(Node<Value> h) { |
178 | // assert (h != null); |
179 | // assert isRed(h) && !isRed(h.right) && !isRed(h.right.left); |
180 | flipColors(h); |
181 | if (isRed(h.left.left)) { |
182 | h = rotateRight(h); |
183 | flipColors(h); |
184 | } |
185 | return h; |
186 | } |
187 | |
188 | // restore red-black tree invariant |
189 | private Node<Value> balance(Node<Value> h) { |
190 | // assert (h != null); |
191 | |
192 | if (isRed(h.right)) h = rotateLeft(h); |
193 | if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); |
194 | if (isRed(h.left) && isRed(h.right)) flipColors(h); |
195 | |
196 | h.setSize(size(h.left) + size(h.right) + 1); |
197 | return h; |
198 | } |
199 | |
200 | |
201 | /** |
202 | * Returns the height of the BST (for debugging). |
203 | * @return the height of the BST (a 1-node tree has height 0) |
204 | */ |
205 | public int height() { |
206 | return height(root); |
207 | } |
208 | |
209 | private int height(Node<Value> x) { |
210 | if (x == null) return -1; |
211 | return 1 + Math.max(height(x.left), height(x.right)); |
212 | } |
213 | |
214 | public Value get(int k) { |
215 | return nodeAtIndex(k).val; |
216 | } |
217 | |
218 | public Value set(int k, Value val) { |
219 | Node<Value> n = nodeAtIndex(k); |
220 | Value oldValue = n.val; |
221 | n.val = val; |
222 | return oldValue; |
223 | } |
224 | |
225 | public Node<Value> nodeAtIndex(int k) { |
226 | if (k < 0 || k >= size()) { |
227 | throw new IndexOutOfBoundsException(k + " / " + size()); |
228 | } |
229 | return nodeAtIndex(root, k); |
230 | } |
231 | |
232 | // the key of rank k in the subtree rooted at x |
233 | private Node<Value> nodeAtIndex(Node<Value> x, int k) { |
234 | // assert x != null; |
235 | // assert k >= 0 && k < size(x); |
236 | int t = size(x.left); |
237 | if (t > k) return nodeAtIndex(x.left, k); |
238 | else if (t < k) return nodeAtIndex(x.right, k-t-1); |
239 | else return x; |
240 | } |
241 | |
242 | private boolean check() { |
243 | if (!isSizeConsistent()) System.out.println("Subtree counts not consistent"); |
244 | if (!is23()) System.out.println("Not a 2-3 tree"); |
245 | if (!isBalanced()) System.out.println("Not balanced"); |
246 | return isSizeConsistent() && is23() && isBalanced(); |
247 | } |
248 | |
249 | // are the size fields correct? |
250 | private boolean isSizeConsistent() { return isSizeConsistent(root); } |
251 | private boolean isSizeConsistent(Node<Value> x) { |
252 | if (x == null) return true; |
253 | if (x.size() != size(x.left) + size(x.right) + 1) return false; |
254 | return isSizeConsistent(x.left) && isSizeConsistent(x.right); |
255 | } |
256 | |
257 | // Does the tree have no red right links, and at most one (left) |
258 | // red links in a row on any path? |
259 | private boolean is23() { return is23(root); } |
260 | private boolean is23(Node<Value> x) { |
261 | if (x == null) return true; |
262 | if (isRed(x.right)) return false; |
263 | if (x != root && isRed(x) && isRed(x.left)) |
264 | return false; |
265 | return is23(x.left) && is23(x.right); |
266 | } |
267 | |
268 | // do all paths from root to leaf have same number of black edges? |
269 | private boolean isBalanced() { |
270 | int black = 0; // number of black links on path from root to min |
271 | Node<Value> x = root; |
272 | while (x != null) { |
273 | if (!isRed(x)) black++; |
274 | x = x.left; |
275 | } |
276 | return isBalanced(root, black); |
277 | } |
278 | |
279 | // does every path from the root to a leaf have the given number of black links? |
280 | private boolean isBalanced(Node<Value> x, int black) { |
281 | if (x == null) return black == 0; |
282 | if (!isRed(x)) black--; |
283 | return isBalanced(x.left, black) && isBalanced(x.right, black); |
284 | } |
285 | |
286 | public void clear() { root = null; } |
287 | } |
download show line numbers debug dex old transpilations
Travelled to 6 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt
No comments. add comment
Snippet ID: | #1024437 |
Snippet name: | LogNArray in Java |
Eternal ID of this version: | #1024437/2 |
Text MD5: | 02ed635e17e655e25682264ec5293e74 |
Author: | stefan |
Category: | javax |
Type: | JavaX fragment (include) |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2019-08-12 17:24:56 |
Source code size: | 9077 bytes / 287 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 191 / 217 |
Version history: | 1 change(s) |
Referenced in: | [show references] |