RedBlackTree

RedBlack.hx

enum Color {
	R; B; BB; NB;
}

enum RedBlackTree<T> {
	T(c : Color, l : RedBlackTree<T>, v : T ,r : RedBlackTree<T>) : RedBlackTree<T>;
	E  : RedBlackTree<T>;
	EE : RedBlackTree<T>;
}

class RBTree {
	private static function redden<X>(t : RedBlackTree<X>) {
		return switch(t) {
			case T(_, a, x, b): T(R, a, x, b);
			case _			  : throw "Error";
		}
	}

	private static function blacken(t) {
		return switch (t) {
			case E | EE: E;
			case T(B, a, x, b) | T(BB, a, x, b): T(B, a, x, b);  
			case _: throw "root is never red";
		}
	}

	private static function blacker(c : Color) {
		return switch c {
			case NB: R;
			case R : B;
			case B : BB;
			case BB: throw "Error in blacker!";
		}
	}

	private static function nodeBlacker<X>(t : RedBlackTree<X>) {
		trace(t);
		return switch(t) {
			case E: EE;
			case T(c, l, x, r): T(blacker(c), l, x, r);
			case _: throw "Error";
		}
	}

	private static function redder(c : Color) {
		return switch c {
			case NB: throw 'Error in redder!';
			case R : NB;
			case B : R;
			case BB: B;
		}
	}

	private static function nodeRedder<X>(t : RedBlackTree<X>) {
		return switch(t) {
			case EE: E;
			case T(c, l, x, r): T(redder(c), l, x, r);
			case _: throw "Error";
		}
	}

	private static function balance<X>(color : Color, i : RedBlackTree<X>, j : X, k : RedBlackTree<X>) {
		return switch ([color, i, j, k]) {
			case [co, T(R, a, x, T(R, b, y, c)), z, d] |
				 [co, T(R, T(R, a, x, b), y, c), z, d] |
				 [co, a, x, T(R, T(R, b, y, c), z, d)] |
				 [co, a, x, T(R, b, y, T(R, c, z, d))] if (co == B || co == BB):
					T(redder(co), T(B, a, x, b), y, T(B, c, z, d)); 
			case [BB, a, x, T(NB, T(B, b, y, c), z, T(B, _, _, _))]:
					T(B, T(B, a, x, b), y, balance(B, c, z, redden(k)));
			case [BB, T(NB, a = T(B, _, _, _), x, T(B, b, y, c)), z, d]:
					T(B, balance(B, redden(a), x, b), y, T(B, c, z, d));
			case [co, a, x, b]:
					T(co, a, x, b);
		}
	}

	private static function isBB<X>(c : RedBlackTree<X>) : Bool {
		return switch(c) {
			case EE: true;
			case T(BB, _, _, _): true;
			case _ : false;
		}
	}

	private static function bubble<X>(c : Color, l : RedBlackTree<X>, x : X, r : RedBlackTree<X>) {
		return (isBB(l) || isBB(r)) ?
			balance(blacker(c), nodeRedder(l), x, nodeRedder(r))
			:
			balance(c, l, x, r);
	}

	public static function empty() {
		return E;
	}

	public static function member(x, t) {
		return switch(t) {
			case E: false;
			case T(_, l, y, r): if (x < y) member(x, r);
								else if (x > y) member(x, l);
								else true;
			case EE: throw "Error";
		}
	}

	public static function insert(x, t) {
		function ins(t) {
			return switch (t) {
				case E: T(R, E, x, E);
				case t = T(c, a, y, b):
					if (x < y) balance(c, ins(a), y, b);
					else if (x > y) balance(c, a, y, ins(b));
					else t;
				case EE: throw "Error";
			}
		}

		return switch(ins(t)) {
			case T(_, a, x, b): T(B, a, x, b);
			case _: throw "Error";
		}
	}

	private static function max(t) {
		return switch (t) {
			case E | EE: throw "error";
			case T(_, _, x, E): x;
			case T(_, _, _, r): max(r);
		}
	}

	private static function removeMax(t) {
		return switch (t) {
			case E | EE: throw "no maximum to remove";
			case T(c, l, x, E): remove(T(c, l, x, E));
			case T(c, l, x, r): bubble(c, l, x, (removeMax(r)));
		}
	}

	private static function remove(t) {
		return switch(t) {
			case E | EE: throw "error";
			case T(R, E, _, E): E;
			case T(B, E, _, E): EE;
			case T(B, E, _, t = T(R, a, x, b)) |
				 T(B, t = T(R, a, x, b), _, E): T(B, a, x, b);
			case T(c, l, x, r): bubble(c, removeMax(l), max(l), r);
		}
	}

	private static function del(x, t) {
		return switch (t) {
			case EE: throw "error";
			case E:	E;
			case T(c, a, y, b):
					if (x < y)
						bubble(c, del(x, a), y, b);
					else if (x > y)
						bubble(c, a, y, del(x, b));
					else
						remove(T(c, a, y, b));
		}
	}

	public static function delete(x, t) {
		return blacken(del(x, t));
	}
}

class RedBlack {
	static function main() {
		var t = RBTree.empty();

		for (i in 0...7) {
			t = RBTree.insert(i, t);
		}
		
		trace(RBTree.delete(5, t));
		return 0;
	}
}