You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
656 lines
17 KiB
Java
656 lines
17 KiB
Java
package com.jwetherell.algorithms.data_structures;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.List;
|
|
import java.util.Random;
|
|
|
|
import com.jwetherell.algorithms.data_structures.interfaces.IList;
|
|
|
|
/**
|
|
* A Treap is a self-balancing binary search tree that uses randomization to maintain
|
|
* a low height. In this version, it is used emulate the operations of an array and linked list.
|
|
*
|
|
* Time Complexity: Assuming the join/merge functions have constant complexity.
|
|
* add(value), add(index,value), remove(index), set(index,value), get(index) all have O(log N).
|
|
* remove(value), get(value), contains(value) all have O(N).
|
|
*
|
|
* Space Complexity: O(N)
|
|
*
|
|
* Note: This implementation is 0-based, meaning that all
|
|
* indices from 0 to size() - 1, inclusive, are accessible.
|
|
*
|
|
* http://en.wikipedia.org/wiki/Treap
|
|
*
|
|
* @author Justin Wetherell <phishman3579@gmail.com>
|
|
*/
|
|
@SuppressWarnings("unchecked")
|
|
public class ImplicitKeyTreap<T> implements IList<T> {
|
|
|
|
private static final Random RANDOM = new Random();
|
|
|
|
private static int randomSeed = Integer.MAX_VALUE; // This should be at least twice the number of Nodes
|
|
|
|
protected Node<T> root = null;
|
|
protected int size = 0;
|
|
|
|
/**
|
|
* Default constructor.
|
|
*/
|
|
public ImplicitKeyTreap() { }
|
|
|
|
/**
|
|
* Constructor with a random seed.
|
|
*
|
|
* @param randomSeed to use.
|
|
*/
|
|
public ImplicitKeyTreap(int randomSeed) {
|
|
this();
|
|
ImplicitKeyTreap.randomSeed = randomSeed;
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*
|
|
* Note: adds to the end of the treap (rightmost node)
|
|
*/
|
|
@Override
|
|
public boolean add(T value) {
|
|
final T t = add(size, value);
|
|
return (t!=null);
|
|
}
|
|
|
|
/**
|
|
* Insert value at index
|
|
*
|
|
* @param index to insert value
|
|
* @param value to insert
|
|
*/
|
|
public T add(int index, T value) {
|
|
addAtIndexAndUpdate(index, value);
|
|
|
|
// Check to make sure value was added
|
|
final Node<T> n = getNodeByIndex(index);
|
|
if (n == null)
|
|
return null;
|
|
return n.value;
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public boolean remove(T value) {
|
|
// See if value already exists
|
|
final int idx = getIndexByValue(value);
|
|
if (idx < 0)
|
|
return false;
|
|
|
|
final T t = removeAtIndex(idx);
|
|
return (t!=null);
|
|
}
|
|
|
|
/**
|
|
* Remove value at index
|
|
*
|
|
* @param index to remove value
|
|
* @return value or null if not found
|
|
*/
|
|
public T removeAtIndex(int index) {
|
|
// See if index already exists
|
|
Node<T> n = getNodeByIndex(index);
|
|
if (n == null)
|
|
return null;
|
|
|
|
removeAtIndexAndUpdate(index);
|
|
return n.value;
|
|
}
|
|
|
|
/**
|
|
* Set value at index
|
|
*
|
|
* @param index to remove value
|
|
* @return value or null if not found
|
|
*/
|
|
public T set(int index, T value) {
|
|
// See if index already exists
|
|
final Node<T> n = getNodeByIndex(index);
|
|
if (n == null)
|
|
return null;
|
|
|
|
n.value = value;
|
|
return n.value;
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public boolean contains(T value) {
|
|
final Node<T> n = getNodeByValue(value);
|
|
return (n!=null);
|
|
}
|
|
|
|
/**
|
|
* Get value at index
|
|
*
|
|
* @param index to remove value
|
|
*/
|
|
public T getAtIndex(int index) {
|
|
final Node<T> n = getNodeByIndex(index);
|
|
if (n == null)
|
|
return null;
|
|
return n.value;
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public void clear() {
|
|
root = null;
|
|
size = 0;
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public int size() {
|
|
return size;
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public boolean validate() {
|
|
if (root == null)
|
|
return true;
|
|
return validateNode(root);
|
|
}
|
|
|
|
private boolean validateNode(Node<T> node) {
|
|
final Node<T> left = node.left;
|
|
final Node<T> right = node.right;
|
|
|
|
if (left != null) {
|
|
if (node.priority < left.priority)
|
|
return validateNode(left);
|
|
return false;
|
|
}
|
|
if (right != null) {
|
|
if (node.priority < right.priority)
|
|
return validateNode(right);
|
|
return false;
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public List<T> toList() {
|
|
return (new JavaCompatibleArrayList<T>(this));
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public java.util.Collection<T> toCollection() {
|
|
return (new JavaCompatibleArrayList<T>(this));
|
|
}
|
|
|
|
/**
|
|
* Split the treap at index
|
|
*
|
|
* @param index to split at
|
|
*
|
|
* @return Pair which contains root of both trees
|
|
*/
|
|
public Pair<T> split(int index) {
|
|
final Pair<T> p = split((Node<T>)root, index);
|
|
if (p.left != null)
|
|
p.left.parent = null;
|
|
if (p.right != null)
|
|
p.right.parent = null;
|
|
return p;
|
|
}
|
|
|
|
public void addAtIndexAndUpdate(int index, T value) {
|
|
root = insert(((Node<T>)root), index, value);
|
|
if (root == null)
|
|
size = 0;
|
|
else
|
|
size = (((Node<T>)root).size);
|
|
}
|
|
|
|
private void removeAtIndexAndUpdate(int index) {
|
|
root = remove(((Node<T>)root), index);
|
|
if (root == null)
|
|
size = 0;
|
|
else
|
|
size = (((Node<T>)root).size);
|
|
}
|
|
|
|
private Node<T> getNodeByValue(T value) {
|
|
return getNodeByValue(root,value);
|
|
}
|
|
|
|
private Node<T> getNodeByIndex(int index) {
|
|
if (root == null)
|
|
return null;
|
|
|
|
final Node<T> l = (Node<T>)root.left;
|
|
final Node<T> r = (Node<T>)root.right;
|
|
final int leftSize = ((l!=null)?l.size:0);
|
|
final int idx = leftSize;
|
|
|
|
if (idx == index) {
|
|
return root;
|
|
} else if (index < leftSize) {
|
|
return getNodeByIndex(l, idx, index);
|
|
} else {
|
|
return getNodeByIndex(r, idx, index);
|
|
}
|
|
}
|
|
|
|
private int getIndexByValue(T value) {
|
|
final Node<T> node = (Node<T>)root;
|
|
if (value == null || node == null)
|
|
return Integer.MIN_VALUE;
|
|
|
|
final Node<T> l = (Node<T>)node.left;
|
|
final Node<T> r = (Node<T>)node.right;
|
|
final int leftSize = ((l!=null)?l.size:0);
|
|
final int idx = leftSize;
|
|
|
|
if (value.equals(node.value))
|
|
return idx;
|
|
|
|
int i = getIndexByValue(l, idx, value);
|
|
if (i >= 0)
|
|
return i;
|
|
|
|
i = getIndexByValue(r, idx, value);
|
|
return i;
|
|
}
|
|
|
|
/**
|
|
* Split the treap rooted at node at given index
|
|
*
|
|
* @param node which represents root
|
|
* @param index in treap to split
|
|
*
|
|
* @return Pair which contains root of both trees
|
|
*/
|
|
public static <T> Pair<T> split(Node<T> node, int index) {
|
|
if (node == null)
|
|
return new Pair<T>(null, null);
|
|
|
|
final int leftSize = (node.left!=null?
|
|
((Node<T>)node.left).size
|
|
:
|
|
0);
|
|
if (index <= leftSize) {
|
|
final Pair<T> sub = split((Node<T>)node.left, index);
|
|
node.left = sub.right;
|
|
if (node.left != null)
|
|
node.left.parent = node;
|
|
sub.right = node;
|
|
node.update();
|
|
return sub;
|
|
}
|
|
// else
|
|
final Pair<T> sub = split((Node<T>)node.right, (index - leftSize - 1));
|
|
node.right = sub.left;
|
|
if (node.right != null)
|
|
node.right.parent = node;
|
|
sub.left = node;
|
|
node.update();
|
|
return sub;
|
|
}
|
|
|
|
/**
|
|
* Merge treaps from given left and right nodes
|
|
*
|
|
* @param left node which represents root of left treap
|
|
* @param right node which represents root of great treap
|
|
*
|
|
* @return treap from merged treaps
|
|
*/
|
|
public static <T> Node<T> merge(Node<T> left, Node<T> right) {
|
|
if (left == null)
|
|
return right;
|
|
|
|
if (right == null)
|
|
return left;
|
|
|
|
if (left.priority < right.priority) {
|
|
left.right = merge((Node<T>)left.right, right);
|
|
if (left.right != null)
|
|
left.right.parent = left;
|
|
left.update();
|
|
return left;
|
|
}
|
|
// else
|
|
right.left = merge(left, (Node<T>)right.left);
|
|
if (right.left != null)
|
|
right.left.parent = right;
|
|
right.update();
|
|
return right;
|
|
}
|
|
|
|
private static <T> Node<T> insert(Node<T> root, int index, T value) {
|
|
final Pair<T> p = split(root, index);
|
|
return merge(merge((Node<T>)p.left, new Node<T>(value)), (Node<T>)p.right);
|
|
}
|
|
|
|
private static <T> Node<T> remove(Node<T> root, int index) {
|
|
final Pair<T> p = split(root, index);
|
|
final int leftSize = (p.left!=null?
|
|
((Node<T>)p.left).size
|
|
:
|
|
0);
|
|
return merge(p.left, (split(p.right, (index + 1 - leftSize))).right);
|
|
}
|
|
|
|
private static <T> Node<T> getNodeByValue(Node<T> node, T value) {
|
|
if (node == null)
|
|
return null;
|
|
|
|
if (node.value.equals(value))
|
|
return node;
|
|
|
|
Node<T> n = getNodeByValue(node.left, value);
|
|
if (n == null)
|
|
n = getNodeByValue(node.right, value);
|
|
return n;
|
|
}
|
|
|
|
private static <T> Node<T> getNodeByIndex(Node<T> node, int parentIndex, int index) {
|
|
if (node == null)
|
|
return null;
|
|
|
|
final Node<T> p = (Node<T>)node.parent;
|
|
final Node<T> l = (Node<T>)node.left;
|
|
final Node<T> r = (Node<T>)node.right;
|
|
final int leftSize = ((l!=null)?l.size:0);
|
|
final int rightSize = ((r!=null)?r.size:0);
|
|
|
|
int idx = Integer.MIN_VALUE;
|
|
if (p!=null && node.equals(p.left)) {
|
|
// left
|
|
idx = parentIndex - rightSize - 1;
|
|
} else if (p!=null && node.equals(p.right)) {
|
|
// right
|
|
idx = leftSize + parentIndex + 1;
|
|
} else {
|
|
throw new RuntimeException("I do not have a parent :-(");
|
|
}
|
|
|
|
if (idx == index)
|
|
return node;
|
|
|
|
if (index <= idx) {
|
|
return getNodeByIndex(l, idx, index);
|
|
} else {
|
|
return getNodeByIndex(r, idx, index);
|
|
}
|
|
}
|
|
|
|
private static <T> int getIndexByValue(Node<T> node, int parentIndex, T value) {
|
|
if (node == null)
|
|
return Integer.MIN_VALUE;
|
|
|
|
final Node<T> p = (Node<T>)node.parent;
|
|
final Node<T> l = (Node<T>)node.left;
|
|
final Node<T> r = (Node<T>)node.right;
|
|
final int leftSize = ((l!=null)?l.size:0);
|
|
final int rightSize = ((r!=null)?r.size:0);
|
|
|
|
int idx = Integer.MIN_VALUE;
|
|
if (p!=null && node.equals(p.left)) {
|
|
// left
|
|
idx = parentIndex - rightSize - 1;
|
|
} else if (p!=null && node.equals(p.right)) {
|
|
// right
|
|
idx = leftSize + parentIndex + 1;
|
|
} else {
|
|
throw new RuntimeException("I do not have a parent :-(");
|
|
}
|
|
|
|
if (value.equals(node.value))
|
|
return idx;
|
|
|
|
int i = getIndexByValue(l, idx, value);
|
|
if (i >= 0)
|
|
return i;
|
|
|
|
i = getIndexByValue(r, idx, value);
|
|
return i;
|
|
}
|
|
|
|
public T[] inOrder() {
|
|
return inOrder(root,size);
|
|
}
|
|
|
|
public static <T> T[] inOrder(Node<T> node, int size) {
|
|
T[] data = (T[]) new Object[size];
|
|
if (node == null)
|
|
return data;
|
|
|
|
inOrder(node, data, 0);
|
|
return data;
|
|
}
|
|
|
|
private static <T> int inOrder(Node<T> node, T[] data, int idx) {
|
|
if (node == null)
|
|
return idx;
|
|
|
|
idx = inOrder(node.left, data, idx);
|
|
data[idx++] = node.value;
|
|
idx = inOrder(node.right, data, idx);
|
|
return idx;
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public String toString() {
|
|
return TreePrinter.getString(this);
|
|
}
|
|
|
|
public static class Node<T> {
|
|
|
|
private T value = null;
|
|
private int priority;
|
|
private int size;
|
|
private Node<T> parent = null;
|
|
private Node<T> left = null;
|
|
private Node<T> right = null;
|
|
|
|
private Node(T id) {
|
|
this(null, id);
|
|
}
|
|
|
|
private Node(Node<T> parent, T id) {
|
|
this.parent = parent;
|
|
this.value = id;
|
|
this.size = 1;
|
|
this.priority = RANDOM.nextInt(randomSeed);
|
|
}
|
|
|
|
public int getSize() {
|
|
return size;
|
|
}
|
|
|
|
private void update() {
|
|
size = 1 + (left!=null?
|
|
((Node<T>)left).size
|
|
:
|
|
0)
|
|
+ (right!=null?
|
|
((Node<T>)right).size
|
|
:
|
|
0);
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public String toString() {
|
|
return "id=" + value + " parent=" + ((parent != null) ? parent.value : "NULL") + " left="
|
|
+ ((left != null) ? left.value : "NULL") + " right=" + ((right != null) ? right.value : "NULL");
|
|
}
|
|
}
|
|
|
|
public static class Pair<T> {
|
|
|
|
private Node<T> left;
|
|
private Node<T> right;
|
|
|
|
private Pair(Node<T> left, Node<T> right) {
|
|
this.left = left;
|
|
this.right = right;
|
|
}
|
|
|
|
public Node<T> getLesser() {
|
|
return left;
|
|
}
|
|
|
|
public Node<T> getGreater() {
|
|
return right;
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public String toString() {
|
|
return "left={"+left.toString()+"} right={"+right.toString()+"}";
|
|
}
|
|
}
|
|
|
|
public static class JavaCompatibleArrayList<T> extends java.util.AbstractList<T> implements java.util.RandomAccess {
|
|
|
|
private ImplicitKeyTreap<T> list = null;
|
|
|
|
public JavaCompatibleArrayList(ImplicitKeyTreap<T> list) {
|
|
this.list = list;
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public boolean add(T value) {
|
|
return list.add(value);
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public boolean remove(Object value) {
|
|
return list.remove((T)value);
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public boolean contains(Object value) {
|
|
return list.contains((T)value);
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public int size() {
|
|
return list.size;
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public void add(int index, T value) {
|
|
list.add(index, value);
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public T remove(int index) {
|
|
return list.removeAtIndex(index);
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public T get(int index) {
|
|
T t = list.getAtIndex(index);
|
|
if (t!=null)
|
|
return t;
|
|
throw new IndexOutOfBoundsException();
|
|
}
|
|
|
|
/**
|
|
* {@inheritDoc}
|
|
*/
|
|
@Override
|
|
public T set(int index, T value) {
|
|
return list.set(index, value);
|
|
}
|
|
}
|
|
|
|
protected static class TreePrinter {
|
|
|
|
public static <T> String getString(ImplicitKeyTreap<T> tree) {
|
|
if (tree.root == null)
|
|
return "Tree has no nodes.";
|
|
return getString(tree.root, "", true);
|
|
}
|
|
|
|
private static <T> String getString(Node<T> node, String prefix, boolean isTail) {
|
|
StringBuilder builder = new StringBuilder();
|
|
|
|
if (node.parent != null) {
|
|
String side = "left";
|
|
if (node.equals(node.parent.right))
|
|
side = "right";
|
|
builder.append(prefix + (isTail ? "└── " : "├── ") + "(" + side + ") " + node.value + "\n");
|
|
} else {
|
|
builder.append(prefix + (isTail ? "└── " : "├── ") + node.value + "\n");
|
|
}
|
|
List<Node<T>> children = null;
|
|
if (node.left != null || node.right != null) {
|
|
children = new ArrayList<Node<T>>(2);
|
|
if (node.left != null)
|
|
children.add(node.left);
|
|
if (node.right != null)
|
|
children.add(node.right);
|
|
}
|
|
if (children != null) {
|
|
for (int i = 0; i < children.size() - 1; i++) {
|
|
builder.append(getString(children.get(i), prefix + (isTail ? " " : "│ "), false));
|
|
}
|
|
if (children.size() >= 1) {
|
|
builder.append(getString(children.get(children.size() - 1), prefix + (isTail ? " " : "│ "), true));
|
|
}
|
|
}
|
|
|
|
return builder.toString();
|
|
}
|
|
}
|
|
}
|
|
|