An array with \$O(\log\ n)\$ time complexity for all operations

Question

Does this exist already? It's an array (=variable-size list with integer indices) where add/remove/set and get all take \$O(\log\ n)\$ time.

I couldn't find this anywhere, so I made up the name "Log-N array" and implemented it in Java.

Rationale: The more often you add or remove entries with your ArrayList, the more you will want to switch to something like this where adding and removing anywhere in the list is \$O(\log\ n)\$ instead of \$O(n)\$.

(Being a tree, it uses more memory than ArrayList though.)

Benchmarks indicate reasonable performance (e. g. ~100 ns for an access in a large array).

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; }
}

Here are some tests.

static void test_LogNArray() {
 test_LogNArray(1000);
}
static void test_LogNArray(int n) {
 LogNArray<String> l = new LogNArray();
 assertEqualsVerbose(0, l.size());
 for (int i = -1; i < 2; i++) { int _i = i ; assertException(new Runnable() { public void run() { try { l.get(_i) ;
} catch (Exception __e) { throw rethrow(__e); } } public String toString() { return "l.get(_i)"; }}); }
 l.add("hello");
 assertEqualsVerbose(1, l.size());
 assertException(new Runnable() { public void run() { try { l.get(-1) ;
} catch (Exception __e) { throw rethrow(__e); } } public String toString() { return "l.get(-1)"; }});
 assertEqualsVerbose("hello", l.get(0));
 assertException(new Runnable() { public void run() { try { l.get(1) ;
} catch (Exception __e) { throw rethrow(__e); } } public String toString() { return "l.get(1)"; }});
 Random random = predictableRandom();
 // n random insertions, complete check
 List<String> refl = new ArrayList();
 l.clear();
 for (int _repeat_0 = 0; _repeat_0 < n; _repeat_0++) {
 int i = random(random, l(refl)+1);
 String id = randomID(random);
 print("add " + i + " " + id);
 refl.add(i, id);
 l.add(i, id);
 assertEquals(l(l), l(refl));
 }
 assertEqualsVerbose(l(l), l(refl));
 for (int i = 0; i < l(refl); i++)
 assertEquals(l.get(i), refl.get(i));
 // overwriting
 for (int _repeat_1 = 0; _repeat_1 < n; _repeat_1++) {
 int i = random(random, l(refl));
 String id = randomID(random);
 print("set " + i + " " + id);
 assertEquals(l.set(i, id), refl.set(i, id));
 assertEquals(l(l), l(refl));
 }
 // n random deletions, check after each turn
 for (int _repeat_2 = 0; _repeat_2 < n; _repeat_2++) {
 int i = random(random, l(refl));
 print("remove " + i);
 assertEquals(l.remove(i), refl.remove(i));
 assertEqualsVerbose(l(l), l(refl));
 for (int j = 0; j < l(refl); j++)
 assertEquals(l.get(j), refl.get(j));
 }
 System.out.println("LogNArray works (tested up to size " + n + ")! :)");
}
static int l(Collection l) { return l == null ? 0 : l.size(); }
static int l(String s) { return s == null ? 0 : s.length(); }
static <A> A print(A a) { System.out.println(a); return a; }
static int random(Random r, int n) {
 return n <= 0 ? 0 : r.nextInt(n);
}
static void silentException(Throwable e) {}
static <A> A assertEqualsVerbose(Object x, A y) {
 assertEqualsVerbose((String) null, x, y);
 return y;
}
static <A> A assertEqualsVerbose(String msg, Object x, A y) {
 if (!eq(x, y)) {
 throw fail((msg != null ? msg + ": " : "") + /*sfu*/(y) + " != " + /*sfu*/(x));
 } else
 print("OK: " + /*sfu*/(x));
 return y;
}
static void assertException(Runnable r) {
 assertFail(r);
}
static RuntimeException rethrow(Throwable t) {
 throw t instanceof RuntimeException ? (RuntimeException) t : new RuntimeException(t);
}
static RuntimeException rethrow(String msg, Throwable t) {
 throw new RuntimeException(msg, t);
}
static Random predictableRandom() {
 return new Random(0);
}
static int randomID_defaultLength = 12;
static String randomID(int length) {
 return makeRandomID(length);
}
static String randomID(Random r, int length) {
 return makeRandomID(r, length);
}
static String randomID() {
 return randomID(randomID_defaultLength);
}
static String randomID(Random r) {
 return randomID(r, randomID_defaultLength);
}
static <A> A assertEquals(Object x, A y) {
 return assertEquals(null, x, y);
}
static <A> A assertEquals(String msg, Object x, A y) {
 if (assertVerbose()) return assertEqualsVerbose(msg, x, y);
 if (!(x == null ? y == null : x.equals(y)))
 throw fail((msg != null ? msg + ": " : "") + y + " != " + x);
 return y;
}
static boolean eq(Object a, Object b) {
 return a == null ? b == null : a == b || b != null && a.equals(b);
}
static RuntimeException fail() { throw new RuntimeException("fail"); }
static RuntimeException fail(Throwable e) { throw asRuntimeException(e); }
static RuntimeException fail(Object msg) { throw new RuntimeException(String.valueOf(msg)); }
static RuntimeException fail(String msg) { throw new RuntimeException(msg == null ? "" : msg); }
static RuntimeException fail(String msg, Throwable innerException) { throw new RuntimeException(msg, innerException); }
static void assertFail(Runnable r) {
 try {
 r.run();
 } catch (Throwable e) {
 silentException(e);
 return;
 }
 throw fail("No exception thrown!");
}
static String makeRandomID(int length) {
 return makeRandomID(length, defaultRandomGenerator());
}
static String makeRandomID(int length, Random random) {
 char[] id = new char[length];
 for (int i = 0; i < id.length; i++)
 id[i] = (char) ((int) 'a' + random.nextInt(26));
 return new String(id);
}
static String makeRandomID(Random r, int length) {
 return makeRandomID(length, r);
}
static ThreadLocal<Boolean> assertVerbose_value = new ThreadLocal();
static void assertVerbose(boolean b) {
 assertVerbose_value.set(b);
}
static boolean assertVerbose() { return isTrue(assertVerbose_value.get()); }
static String str(Object o) {
 return o == null ? "null" : o.toString();
}
static String str(char[] c) {
 return new String(c);
}
static RuntimeException asRuntimeException(Throwable t) {
 return t instanceof RuntimeException ? (RuntimeException) t : new RuntimeException(t);
}
static Random defaultRandomGenerator() {
 return ThreadLocalRandom.current();
}
static boolean isTrue(Object o) {
 if (o instanceof Boolean)
 return ((Boolean) o).booleanValue();
 if (o == null) return false;
 if (o instanceof ThreadLocal)
 return isTrue(((ThreadLocal) o).get());
 throw fail(getClassName(o));
}
static String getClassName(Object o) {
 return o == null ? "null" : o instanceof Class ? ((Class) o).getName() : o.getClass().getName();
}
static <A> A println(A a) {
 return print(a);
}

• Riccardo Biraghi: I am not aware of anything similar being available natively in Java, but Apache Commons does have something like it: commons.apache.org/proper/commons-collections/javadocs/api-4.4/…
• Stefan Reich: @RiccardoBiraghi Yes TreeList does seem similar. They are using an AVL tree instead of a red-black tree which will change performance and/or memory use somewhat.

Answer 1

Import

import java.util.*;

The class does not need to import the whole java.util package. Instead it only needs:

import java.util.AbstractList;
import java.util.RandomAccess;

The benefits are:

• avoid namespace collisions
• better readability, because you know the dependencies at a glance
• faster compilation

Comments

Variable Declaration

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

private Value val; // associated data
private Node<Value> left, right; // links to left and right subtrees
private int sizeAndColor; // subtree count + color (highest bit)

int black = 0; // number of black links on path from root to min

Code should be self-documenting, which means that you do not need a comment to understand the code. In the above case the comments are redundant - there is no logic, just simple declaration of variables..

Instead of int black = 0 maybe int numberOfBlackNodes = 0 is better?

JavaDoc

Wikipedia describes JavaDoc as:

Javadoc [...] is a documentation generator [...] for the Java language [...] for generating API documentation in HTML format from Java source code.

Additionally, if you work with an IDE like Eclipse or IntelliJ, a JavaDoc provides you quick access to documentation from inside the IDE.

public class LogNArray<Value> extends AbstractList<Value> implements RandomAccess {
 // Structure is a left-leaning red-black BST, 2-3 version

// BST helper node data type
private final static class Node<Value> {

// is node x red; false if x is null ?
private boolean isRed(Node<Value> x) {

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

The above snippets are some potential candidates for a JavaDoc.

/**
 * number of {@link Node}s in a subtree
 *
 * @param x root of the subtree
 * @return size of subtree or 0 if x is null
 */
private int size(Node<Value> x) {

Code that is Commented Out

In several places I see something like:

private Node<Value> rotateLeft(Node<Value> h) {
 // assert (h != null) && isRed(h.right);

private Node<Value> moveRedLeft(Node<Value> h) {
 // assert (h != null);
 // assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);

If you want to save code do not comment it out - instead use a Version Control like Git or SVN.

Code that is commented out decreases the readability level over 9000, because a reader does not know if this is code that could be a hint, or it is a untested feature, or or or ..

Since it is commented out, you can remove it without affecting the program.

Naming

private Value val; // associated data
private Node<Value> left, right; // links to left and right subtrees
private int sizeAndColor; // subtree count + color (highest bit)

With the comments you try to express what these variables stand for:

private Value associated; 
private Node<Value> leftSubtree, rightSubtree;
private int countAndColor;

One Declaration per Line

From Oracle's Code Conventions:

6.1 Number Per Line
One declaration per line is recommended since it encourages commenting. In other words,

In general, the fewer things that happen on a line, the better. At first glance I didn't see that there were two variables at all.

private Node<Value> left, right; // links to left and right subtrees

private Node<Value> leftSubtree;
private Node<Value> rightSubtree;

@Override

LogNArray extends AbstractList and overrides multiple methods:

• size()
• isEmpty()
• add(int, Value)
• remove(int)
• get(int)
• set(int, Value)

These should be annotated with @Override to enable the compiler to warn if you haven't overridden a method, for example if you have a typo in a method name.

Code Duplication

Personally for me !isRed is a code duplication, because it tries to express that a node is black and the ! is an operation on isRed.

When I search inside my IDE for !isRed it gives me back 9 uses on 6 lines.

private boolean isBlack(Node<Value> x) {
 return !isRed(x);
}

With this method we can increase the readability of the following, for example:

// if both children of root are black, set root to red
if (!isRed(root.left) && !isRed(root.right))
 root.setColor(RED);

In this case a comment is needed to describe what happens. But we could simply use isBlack to make the code self documenting:

if (isBlack(root.left) && isBlack(root.right))
 root.setColor(RED);

Unused Code

private final static class Node<Value> {
/* ... */
Node() {}

The default constructor Node() {} is declared explicitly, but is not used, so we could delete it safely.

Test

I recommend to use tools for testing like jUnit, which provides many methods including asserts, so you do not need to implement them yourself.

The method test_LogNArray is 52 lines long. Methods in general should be as short as possible but the important part for a test is, that a reader needs to understand the test case.

You can achieve shorter test methods by testing only one thing (for example a method) per test.

Additionally, no test should depend on any other test. Since you have only one test method, all things inside it depend on each other. For example, you are testing if the size is 0 first and on the same instance if it is 1 after adding something to it. Now the next test will depend on the item that was already added - so you can't test things that are only possible with an empty array.

A test should follow the AAA-Pattern, where a test is grouped in three blocks:

• arrange the test case,
• act on the object under test, and
• assert what you expect.

The name of a test is a matter of taste. I prefer a pattern of given__when__then which leads to a long method names. but simple names like sizeOnAnEmpyArrayIs0 are fine too - feel free to choose better names! :]

First Test Case

LogNArray<String> l = new LogNArray();
assertEqualsVerbose(0, l.size());

@Test
void given_emptyArray_when_countSize_then_expect0 {
 // arrange
 LogNArray<String> array = new LogNArray();
 // act
 int size = array.size();
 // assert
 assertEquals(0, size)
}

Second Test Case

for (int i = -1; i < 2; i++) { int _i = i ; assertException(new Runnable() { public void run() { try { l.get(_i) ;
} catch (Exception __e) { throw rethrow(__e); } } public String toString() { return "l.get(_i)"; }}); }

At first glance I didn't see what was going on, so I needed to beautify it:

for (int i = -1; i < 2; i++) {
 int _i = i ; 
 assertException(new Runnable() {
 public void run() { 
 try { 
 l.get(_i) ;
 } catch (Exception __e) { throw rethrow(__e); } } 
 public String toString() { return "l.get(_i)"; }}
 ); 
}

@Test
void given_emptyArrayAndAnIndex_when_getValueOnIndex_then_throwsIndexOutOfBoundsException {
 // arrange
 LogNArray<String> array = new LogNArray();
 int index = 5;
 // act and assert
 assertThrows(IndexOutOfBoundsException.class, array.get(index));
}

Third Test Case

l.add("hello");
assertEqualsVerbose(1, l.size());

@Test
void given_oneItem_when_countSize_then_expect1() {
 // arrange
 LogNArray<String> array = new LogNArray();
 array.add("hello");
 // act
 int size = array.size();
 // assert
 assertEquals(1, size);
}

And so on..

• Stefan Reich: Wow, nice, thanks for your effort. Some of the code came from a generator (the unnecessary RuntimeException stuff), could have cleaned that up before, sorry.
• Stefan Reich: I do have to say that that low-level language stuff is not very important (how many lines a method has, how many declarations per line...). AI (natural language) is the next level above Java. If our IDEs were more like AI programs, they'd pick up everything about our code without us following many standards.