package plp.collection; public class AVL { private Cell rootFather; private class Cell implements AVLPosition { private AVL avl; private Cell left = null; private Cell right = null; private Cell father = null; private Object data = null; private int height = 0; private int size = 0; Cell(AVL avl) { // Only to create the rootFather of an AVL. this.avl = avl; father = null; } private Cell(Cell father) { this.avl = father.avl; this.father = father; } private void updateValues() { if (isEmpty()) { height = size = 0; } else { height = 1 + Math.max(left.height, right.height); size = left.size + right.size + 1; } } private void setLinks(Cell left, Cell right) { this.left = left; this.right = right; left.father = right.father = this; updateValues(); } private void setData(Object data) { if (this.data != null) { throw new Error(); // data cannot change ! } this.data = data; } // Rotations returns the new root of the subtree. private Cell rightRotation() { Cell tmp = left; setLinks(tmp.right, right); tmp.father = father; tmp.setLinks(tmp.left, this); return tmp; } private Cell leftRotation() { Cell tmp = right; setLinks(left, tmp.left); tmp.father = father; tmp.setLinks(this, tmp.right); return tmp; } private void replaceChild(Cell old, Cell newChild) { if (right == old) { right = newChild; } else { left = newChild; } newChild.father = this; } private void balance() { Cell root = this; Cell father = this.father; if (! isEmpty()) { if (left.height == right.height + 2) { if (left.right.height == left.left.height + 1) { setLinks(left.leftRotation(), right); } root = rightRotation(); } else if (right.height == left.height + 2) { if (right.left.height == right.right.height + 1) { setLinks(left, right.rightRotation()); } root = leftRotation(); } else { updateValues(); } father.replaceChild(this, root); } if (! root.isRoot()) { father.balance(); } } private static final int LEFT = 0; private static final int RIGHT = 1; private AVLPosition insert(Object o, int side) { if (isEmpty()) { setLinks(new Cell(this), new Cell(this)); setData(o); father.balance(); return this; } else { Cell c = side == LEFT ? left : right; return c.insert(o, side); } } public AVL avl() { return avl; } public boolean isRoot() { return this.father == avl.rootFather; } public AVLPosition insertAfter(Object o) { return right.insert(o, LEFT); } public AVLPosition insertBefore(Object o) { return left.insert(o, RIGHT); } private void removeAux(Cell toRemove) { if (right.isEmpty()) { Cell tmp = left; father.replaceChild(this, left); setLinks(toRemove.left, toRemove.right); toRemove.father.replaceChild(toRemove, this); tmp.balance(); } else { right.removeAux(toRemove); } } public void remove() { if (left.isEmpty()) { father.replaceChild(this, right); right.balance(); } else { left.removeAux(this); } } private boolean isEmpty() { return left == null; } public int rank() { // value from 0 to n-1 if (isRoot()) { return left.size; } else if (father.left == this) { return father.rank() - right.size - 1; } else { return father.rank() + left.size + 1; } } public Object data() { return data; } Cell positionAux(int rank) throws InvalidRankException { if (rank >= size) { throw new InvalidRankException(rank); } else if (rank == left.size) { return this; } else if (rank < left.size) { return left.positionAux(rank); } else { return right.positionAux(rank - left.size - 1); } } private int dfsAux(Object [] array, int index) { if (isEmpty()) { return index; } index = left.dfsAux(array, index); array[index++] = data; return right.dfsAux(array, index); } public String toString() { String s = ""; if (isEmpty()) { s = "EMPTY"; } else { s += data + "(height = " + height + " size = " + size + ")\n"; s += left + "\n"; s += right; } return s; } } // end of Cell class public AVL() { rootFather = new Cell(this); rootFather.left = new Cell(rootFather); } public AVLPosition root() { return rootFather.left; } public boolean isEmpty() { return ((Cell) root()).isEmpty(); } public int size() { return ((Cell) root()).size; } public Object data(int rank) throws InvalidRankException { return ((Cell) position(rank)).data; } public AVLPosition position(int rank) throws InvalidRankException { return ((Cell) root()).positionAux(rank); } public AVLPosition insertAt(Object o, int rank) throws InvalidRankException { Cell root = (Cell) root(); if (rank == 0) { if (isEmpty()) { root.setLinks(new Cell(root), new Cell(root)); root.setData(o); return root; } else { return position(rank).insertBefore(o); } } else { return position(rank - 1).insertAfter(o); } } public Object [] dfs() { Object [] array = new Object[size()]; ((Cell) root()).dfsAux(array, 0); return array; } public String toString() { return ((Cell) root()).toString(); } }