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 InternalError(); // 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 insertNeighbor(Object o, int side) { if (isEmpty()) { setLinks(new Cell(this), new Cell(this)); setData(o); father.balance(); return (AVLPosition) this; } return (side == LEFT)? left.insertNeighbor(o, LEFT) : right.insertNeighbor(o, RIGHT); } public AVL avl() { return avl; } private String adress() { return super.toString(); } public boolean isRoot() { return this.father == avl.rootFather; } public AVLPosition insertAfter(Object o) { return right.insertNeighbor(o, LEFT); } public AVLPosition insertBefore(Object o) { return left.insertNeighbor(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); 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(); } }