LogNArray in Java [1024437]

import java.util.*;

public class LogNArray<Value> extends AbstractList<Value> implements RandomAccess {
  // Structure is a left-leaning red-black BST, 2-3 version
 
  private static final boolean RED   = true;
  private static final boolean BLACK = false;

  private Node<Value> root;     // root of the BST

  // BST helper node data type
  private final static class Node<Value> {
    private Value val;         // associated data
    private Node<Value> left, right;  // links to left and right subtrees
    private int sizeAndColor; // subtree count + color (highest bit)
    
    Node() {}

    Node(Value val, boolean color, int size) {
      this.val = val;
      sizeAndColor = size | (color ? 0x80000000 : 0);
    }
    
    int size() { return sizeAndColor & 0x7FFFFFFF; }
    boolean color() { return sizeAndColor < 0; }
    
    void setSize(int size) { sizeAndColor = sizeAndColor & 0x80000000 | size; }
    void setColor(boolean color) { sizeAndColor = size() | (color ? 0x80000000 : 0); }
  }

  // is node x red; false if x is null ?
  private boolean isRed(Node<Value> x) {
      if (x == null) return false;
      return x.color() == RED;
  }

  // number of node in subtree rooted at x; 0 if x is null
  private int size(Node<Value> x) {
      if (x == null) return 0;
      return x.size();
  } 


  public int size() {
      return size(root);
  }

  public boolean isEmpty() {
      return root == null;
  }


  public void add(int idx, Value val) {
    if (idx < 0 || idx > size()) throw new IndexOutOfBoundsException(idx + " / " + size());
    
    root = add(root, idx, val);
    root.setColor(BLACK);
  }

  // insert the value pair in index k of subtree rooted at h
  private Node<Value> add(Node<Value> h, int k, Value val) { 
    if (h == null) return new Node(val, RED, 1);

    int t = size(h.left);
    if (k < t)
      // replace / fit in left child
      h.left = add(h.left, k, val);
    else if (k == t) {
      // move value to right child, replace value
      h.right = add(h.right, 0, h.val);
      h.val = val;
    } else
      // replace / fit in right child
      h.right = add(h.right, k-t-1, val); 

    // fix-up any right-leaning links
    if (isRed(h.right) && !isRed(h.left))      h = rotateLeft(h);
    if (isRed(h.left)  &&  isRed(h.left.left)) h = rotateRight(h);
    if (isRed(h.left)  &&  isRed(h.right))     flipColors(h);
    h.setSize(size(h.left) + size(h.right) + 1);

    return h;
  }

  public Value remove(int idx) { 
    Value oldValue = get(idx);
    
    // if both children of root are black, set root to red
    if (!isRed(root.left) && !isRed(root.right))
      root.setColor(RED);

    root = remove(root, idx);
    if (root != null) root.setColor(BLACK);

    return oldValue;
  }

  private Node<Value> remove(Node<Value> h, int k) { 
    int t = size(h.left);
    if (k < t) { // remove from left child
      if (!isRed(h.left) && !isRed(h.left.left))
        h = moveRedLeft(h);
      h.left = remove(h.left, k);
    } else { // remove from center or right child
      if (isRed(h.left)) {
        h = rotateRight(h);
        t = size(h.left);
      }
      if (h.right == null) return null; // drop whole node
      if (!isRed(h.right) && !isRed(h.right.left)) {
        h = moveRedRight(h);
        t = size(h.left);
      }
      if (k == t) { // replace center value with min of right child
        h.val = nodeAtIndex(h.right, 0).val;
        h.right = remove(h.right, 0);
      }
      else h.right = remove(h.right, k-t-1);
    }
    return balance(h);
  }

  // make a left-leaning link lean to the right
  private Node<Value> rotateRight(Node<Value> h) {
      // assert (h != null) && isRed(h.left);
      Node<Value> x = h.left;
      h.left = x.right;
      x.right = h;
      x.setColor(x.right.color());
      x.right.setColor(RED);
      x.setSize(h.size());
      h.setSize(size(h.left) + size(h.right) + 1);
      return x;
  }

  // make a right-leaning link lean to the left
  private Node<Value> rotateLeft(Node<Value> h) {
      // assert (h != null) && isRed(h.right);
      Node<Value> x = h.right;
      h.right = x.left;
      x.left = h;
      x.setColor(x.left.color());
      x.left.setColor(RED);
      x.setSize(h.size());
      h.setSize(size(h.left) + size(h.right) + 1);
      return x;
  }

  // flip the colors of a node and its two children
  private void flipColors(Node<Value> h) {
      // h must have opposite color of its two children
      // assert (h != null) && (h.left != null) && (h.right != null);
      // assert (!isRed(h) &&  isRed(h.left) &&  isRed(h.right))
      //    || (isRed(h)  && !isRed(h.left) && !isRed(h.right));
      h.setColor(!h.color());
      h.left.setColor(!h.left.color());
      h.right.setColor(!h.right.color());
  }

  // Assuming that h is red and both h.left and h.left.left
  // are black, make h.left or one of its children red.
  private Node<Value> moveRedLeft(Node<Value> h) {
      // assert (h != null);
      // assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);

      flipColors(h);
      if (isRed(h.right.left)) { 
          h.right = rotateRight(h.right);
          h = rotateLeft(h);
          flipColors(h);
      }
      return h;
  }

  // Assuming that h is red and both h.right and h.right.left
  // are black, make h.right or one of its children red.
  private Node<Value> moveRedRight(Node<Value> h) {
      // assert (h != null);
      // assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);
      flipColors(h);
      if (isRed(h.left.left)) { 
          h = rotateRight(h);
          flipColors(h);
      }
      return h;
  }

  // restore red-black tree invariant
  private Node<Value> balance(Node<Value> h) {
      // assert (h != null);

      if (isRed(h.right))                      h = rotateLeft(h);
      if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
      if (isRed(h.left) && isRed(h.right))     flipColors(h);

      h.setSize(size(h.left) + size(h.right) + 1);
      return h;
  }


  /**
   * Returns the height of the BST (for debugging).
   * @return the height of the BST (a 1-node tree has height 0)
   */
  public int height() {
      return height(root);
  }
  
  private int height(Node<Value> x) {
      if (x == null) return -1;
      return 1 + Math.max(height(x.left), height(x.right));
  }
  
  public Value get(int k) {
    return nodeAtIndex(k).val;
  }

  public Value set(int k, Value val) {
    Node<Value> n = nodeAtIndex(k);
    Value oldValue = n.val;
    n.val = val;
    return oldValue;
  }

  public Node<Value> nodeAtIndex(int k) {
      if (k < 0 || k >= size()) {
          throw new IndexOutOfBoundsException(k + " / " + size());
      }
      return nodeAtIndex(root, k);
  }

  // the key of rank k in the subtree rooted at x
  private Node<Value> nodeAtIndex(Node<Value> x, int k) {
      // assert x != null;
      // assert k >= 0 && k < size(x);
      int t = size(x.left); 
      if      (t > k) return nodeAtIndex(x.left,  k); 
      else if (t < k) return nodeAtIndex(x.right, k-t-1); 
      else            return x; 
  } 
  
  private boolean check() {
      if (!isSizeConsistent()) System.out.println("Subtree counts not consistent");
      if (!is23())             System.out.println("Not a 2-3 tree");
      if (!isBalanced())       System.out.println("Not balanced");
      return isSizeConsistent() && is23() && isBalanced();
  }

  // are the size fields correct?
  private boolean isSizeConsistent() { return isSizeConsistent(root); }
  private boolean isSizeConsistent(Node<Value> x) {
      if (x == null) return true;
      if (x.size() != size(x.left) + size(x.right) + 1) return false;
      return isSizeConsistent(x.left) && isSizeConsistent(x.right);
  } 

  // Does the tree have no red right links, and at most one (left)
  // red links in a row on any path?
  private boolean is23() { return is23(root); }
  private boolean is23(Node<Value> x) {
      if (x == null) return true;
      if (isRed(x.right)) return false;
      if (x != root && isRed(x) && isRed(x.left))
          return false;
      return is23(x.left) && is23(x.right);
  } 

  // do all paths from root to leaf have same number of black edges?
  private boolean isBalanced() { 
      int black = 0;     // number of black links on path from root to min
      Node<Value> x = root;
      while (x != null) {
          if (!isRed(x)) black++;
          x = x.left;
      }
      return isBalanced(root, black);
  }

  // does every path from the root to a leaf have the given number of black links?
  private boolean isBalanced(Node<Value> x, int black) {
      if (x == null) return black == 0;
      if (!isRed(x)) black--;
      return isBalanced(x.left, black) && isBalanced(x.right, black);
  }
  
  public void clear() { root = null; }
}

Travelled to 6 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt

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:	116 / 144
Version history:	1 change(s)
Referenced in:	[show references]

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	}

< > BotCompany Repo | #1024437 // LogNArray in Java

JavaX fragment (include)