template<class T> class Collection {
protected:
	unsigned long count;
public:
	Collection(): count(0) {}

	virtual void clear() = 0;
	virtual void add(T &val) = 0;
	virtual const bool remove(T &val) = 0;

	const unsigned long size() const {return count;}
};

template<class T> class Node {
public:
	T val;

	Node(T &v): val(v) {}
	virtual ~Node() {}
};

template<class T> class ListNode: public Node<T> {
public:
	ListNode<T> *next, *prev;

	ListNode(T &v): Node<T>(v), next(0), prev(0) {}
	virtual ~ListNode() {
		if(next) next->prev = prev;
		if(prev) prev->next = next;			
	}
};

template<class T> class LinkedList: public Collection<T> {
protected:
	ListNode<T> *head, *tail;

public:
	class Iterator {
		friend class LinkedList<T>;
	protected:
		ListNode<T> *n;
		Iterator(ListNode<T> *start): n(start) {}
	public:
		Iterator(const Iterator &other): n(other.n) {}

		virtual T &val() {return n->val;}
		virtual void next() {if(n) n = n->next;}
		virtual void prev() {if(n) n = n->prev;}
		virtual const bool has_val() {return (n ? true : false); }
	};

	LinkedList(): Collection<T>(), head(0), tail(0) {};
	LinkedList(const LinkedList<T> &other): Collection<T>(), head(0), tail(0) {
		for(Iterator i = other.start(); i.has_val(); i.next())
			add(i.val());
	}
	virtual ~LinkedList() {clear();}

	LinkedList<T> &operator=(const LinkedList<T> &other) {
		clear();
		for(Iterator i = other.start(); i.has_val(); i.next())
			add(i.val());
		return *this;
	}

	virtual void clear() {
		ListNode<T> *n;
		while(head) {
			n = head;
			head = head->next;
			delete n;
		}
		tail = 0;
		Collection<T>::count = 0;
	}

	virtual Iterator start() const {return Iterator(head);}

	virtual void add_front(T &val) {
		ListNode<T> *n = new ListNode<T>(val);
		n->next = head;
		if(head) head->prev = n;
		head = n;
		if(!tail) tail = n;
		Collection<T>::count++;
	}

	virtual void add(T &val) {
		ListNode<T> *n = new ListNode<T>(val);
		n->prev = tail;
		if(tail) tail->next = n;
		tail = n;
		if(!head) head = n;
		Collection<T>::count++;
	}

	virtual const bool remove(T &val) {
		ListNode<T> *n = head;
		while(n) {
			if(n->val == val) {
				if(n == head) head = head->next;
				if(n == tail) tail = tail->prev;
				
				delete n;
				Collection<T>::count--;
				return true;
			} else
				n = n->next;
		}

		return false;
	}

	// queue/stack functions
	// stack - use push/pop
	// queue - use push_back/pop
	virtual void push(T val) {
		add_front(val);
	}

	virtual void push_back(T &val) {
		add(val);
	}

	virtual const bool pop(T &val) {
		if(!head) return false;

		ListNode<T> *n = head;
		if(head) {
			head = head->next;
			if(n == tail) tail = 0;
			val = n->val;
			delete n;
			Collection<T>::count--;
			return true;
		} else
			return false;
	}
};

template<class T> class DynamicArray: public Collection<T> {
protected:
	T *ar;

	unsigned long initial, limit, increment;

public:
	class Iterator {
		friend class DynamicArray<T>;
	protected:
		T *ar;
		unsigned long count;
		unsigned long pos;
		Iterator(T *a, const int c, unsigned long p): ar(a), count(c), pos(p) {}
	public:
		Iterator(const Iterator &other): ar(other.ar), count(other.count), pos(other.pos) {}

		virtual T &val() {return ar[pos];}
		virtual void next() {pos++;}
		virtual void prev() {pos--;}
		virtual const bool has_val() {return pos < count; }
	};

	DynamicArray(unsigned long init = 0, unsigned long inc = 1): Collection<T>(), ar(0), initial(init), limit(init), increment(inc) {
		if(limit) ar = (T *)malloc(limit * sizeof(T));
	}
	virtual ~DynamicArray() {if(ar) free(ar);}

	virtual void clear() {
		Collection<T>::count = 0;
		limit = initial;
		if(limit) ar = (T *)realloc(ar, limit * sizeof(T));
		else free(ar);
	}

	virtual Iterator start() {return Iterator(ar, Collection<T>::count, 0);}

	virtual void add(T &val) {
		if(Collection<T>::count == limit) {
			limit += increment;
			ar = (T *)realloc(ar, limit * sizeof(T));
			ar[Collection<T>::count++] = val;
		} else
			ar[Collection<T>::count++] = val;
	}

	virtual const bool remove(T &val) {
		for(unsigned long i = 0; i < Collection<T>::count; i++) {
			if(ar[i] == val) {
				memmove(ar + i, ar + i + 1, (Collection<T>::count - i) * sizeof(T));
				Collection<T>::count--;
				return true;
			}
		}
		return false;
	}

	virtual const bool remove(const unsigned long index) {
		if(index >= Collection<T>::count) return false;

		memmove(ar + index, ar + index + 1, (Collection<T>::count - index) * sizeof(T));
		Collection<T>::count--;
		return true;
	}

	virtual const bool insert(T &val, const unsigned long index) {
		if(index > Collection<T>::count) return false;

		if(Collection<T>::count == limit) {
			limit += increment;
			ar = (T *)realloc(ar, limit * sizeof(T));
		}

		if(index < Collection<T>::count)
			memmove(ar + index + 1, ar + index, (Collection<T>::count - index) * sizeof(T));
		
		ar[index] = val;
		Collection<T>::count++;
		return true;
	}

	virtual T &operator[](const int index) {
		return ar[index];
	}

	const bool index_of(const T &val, unsigned long &index) {
		for(int i = 0; i < Collection<T>::count; i++) {
			if(ar[index] == val) {
				index = i;
				return true;
			}
		}
		return false;
	}

	// stack functions
	virtual const bool pop(T &val) {
		if(Collection<T>::count) {
			val = ar[Collection<T>::count -1];
			remove(Collection<T>::count -1);
			return true;
		}
		return false;
	}

	virtual void push(T &val) {
		add(val);
	}
};

template<class T> class SortedDynamicArray: public DynamicArray<T> {
public:
	SortedDynamicArray(unsigned long init = 0, unsigned long inc = 1): DynamicArray<T>(init, inc) {}
	virtual ~SortedDynamicArray() {}

	const bool get_index(T &val, unsigned long &index) {
		unsigned long low  = 0;
		unsigned long high = Collection<T>::count-1;

		while( high < Collection<T>::count && low <= high )
		{  
			unsigned long i = ( low+high )/2;
			if ( DynamicArray<T>::ar[i] == val )
			{	index = i;
				return true;
			} else 
				if (DynamicArray<T>::ar[i] < val)
					low = i+1;
				else
					high = i-1;
		}

		index = low;
		return false;
	}

	virtual void add(T &val) {
		unsigned long index;
		get_index(val, index);
		insert(val, index);
	}
};

template<class T> class TreeNode: public Node<T> {
public:
	TreeNode<T> *parent, *left, *right;

	TreeNode(T &v, TreeNode<T> *par): Node<T>(v), parent(par), left(0), right(0) {}
	virtual ~TreeNode() {
		if(parent) {
			if(parent->left == this) parent->left = 0;
			else parent->right = 0;
		}
	}
};

template<class T> class BinaryTree: public Collection<T> {
protected:

	TreeNode<T> *root;

	TreeNode<T> *delete_node(TreeNode<T> *n) {
		if(n->left && n->right) {
			//if(rand() & 1) { // ?
				TreeNode<T> *minmax = n->left;
				while(minmax->right) minmax = minmax->right;
			//} else {
			//	Node *minmax = current->right;
			//	while(minmax->left) minmax = minmax->left;
			//}
			n->val = minmax->val;
			delete_node(minmax);
			Collection<T>::count--;
			return n;
		} else if(n->right) {
			if(n->parent) {
				if(n->parent->left = n) n->parent->left = n->right;
				else n->parent->right = n->right;
			} else
				root = n->right;
			n->right->parent = n->parent;
		} else if(n->left) {
			if(n->parent) {
				if(n->parent->left = n)	n->parent->left = n->left;
				else n->parent->right = n->left;
			} else
				root = n->left;
			n->left->parent = n->parent;
		} else {
			if(n == root) root = 0;
		}
		delete n;
		Collection<T>::count--;
		return 0;
	}

	void insert_node(TreeNode<T> *n) {
		TreeNode<T> *current = root, *parent = 0;
		while(current) {
			parent = current;
			if(n->val < current->val)
				current = current->left;
			else
				current = current->right;
		}

		if(parent) {
			if(n->val < parent->val) {
				parent->left = n;
				n->parent = parent;
			} else {
				parent->right = n;
				n->parent = parent;
			}
		} else
			root = n;

	}

public:
	class Iterator {
		friend class BinaryTree<T>;
	protected:

		class EvalNode {
		public:
			bool evaluate;
			TreeNode<T> *node;

			EvalNode(): evaluate(false), node(0) {}
			EvalNode(const bool eval, TreeNode<T> *n): evaluate(eval), node(n) {}
			const bool operator==(const EvalNode &other) const {return node == other.node;}
			EvalNode &operator=(const EvalNode &other) {evaluate = other.evaluate; node = other.node; return *this;}

		};

		TreeNode<T> *n;
		LinkedList<EvalNode> stack;

		
		Iterator(TreeNode<T> *start): n(0) {
			if(start) {
				stack.push(EvalNode(true, start));
				next();
			}
		}

	public:
		Iterator(const Iterator &other):n(other.n), stack(other.stack)  {}
		virtual ~Iterator() {}

		virtual T &val() {return n->val;}
		virtual void next() {
			EvalNode en;
			bool popped = false;
			while((popped = stack.pop(en)) && en.evaluate) {
				if(en.node->right) stack.push(EvalNode(true, en.node->right));
				stack.push(EvalNode(false, en.node));
				if(en.node->left) stack.push(EvalNode(true, en.node->left));
			}
			
			n = (popped ? en.node : 0);
		}
		virtual const bool has_val() {return (n ? true : false);}
	};

	BinaryTree(): Collection<T>(), root(0) {};
	BinaryTree(BinaryTree<T> &other): Collection<T>(), root(0) {
		for(Iterator i = other.start(); i.has_val(); i.next())
			add(i.val());
	}
	virtual ~BinaryTree() {clear();}

	BinaryTree &operator=(BinaryTree<T> &other) {
		clear();
		for(Iterator i = other.start(); i.has_val(); i.next())
			add(i.val());
		return *this;
	}

	virtual void clear() {
		TreeNode<T> *current = root, *parent = 0;
		while(current) {
			if(current->left) current = current->left;
			else if(current->right) current = current->right;
			else {
				parent = current->parent;
				delete current;
				current = parent;
			}
		}

		root = 0;
		Collection<T>::count = 0;
	}

	void add(T &val) {
		TreeNode<T> *n = new TreeNode<T>(val, 0);
		insert_node(n);
		Collection<T>::count++;
	}

	const bool remove(T &val) {
		TreeNode<T> *current = root;
		while(current) {
			if(current->val == val)
				break;
			else if(val < current->val)
				current = current->left;
			else 
				current = current->right;
		}

		if(current) {
			delete_node(current);
			return true;
		}

		return false;
	}

	Iterator start() {return Iterator(root);}
};

template<class A, class B> class Pair {
public:
	A first;
	B second;

	Pair(const A &f): first(f) {}
	Pair(const A &f, const B &s): first(f), second(s) {}
	Pair(Pair<A,B> &other): first(other.first), second(other.second) {}
	virtual ~Pair() {}

	const bool operator<(const Pair<A,B> &other) const {return first < other.first;}
	const bool operator==(const Pair<A,B> &other) const {return first == other.first;}
	Pair<A,B> &operator=(const Pair<A,B> &other) {first = other.first; second = other.second; return *this;}
};

template<class A, class B> class Map: public BinaryTree< Pair< A, B > > {
protected:
	
	const TreeNode<Pair< A, B > > *find(A &val) const {
		TreeNode<Pair< A, B > > *n = BinaryTree< Pair< A, B > >::root;
		while(n) {
			if(n->val.first == val)
				return n;
			else if(val < n->val.first)
				n = n->left;
			else
				n = n->right;

		}
		return 0;
	}
public:
	Map(): BinaryTree< Pair<A,B> >() {}
	virtual ~Map() {}

	void put(A &key, B &value) {
		add(Pair<A,B>(key, value));
	}

	const bool get(A &key, B &val) const {
		const TreeNode<Pair< A, B > > *n = find(key);
		if(n) {
			val = n->val.second;
			return true;
		} else
			return false;
	}

	B &operator[](A &key) {
		TreeNode<Pair< A, B > > *n = find(key);
		if(n)
			return n->val.second;
		else {
			Pair< A, B > p(key);
			TreeNode<Pair< A, B > > *n = new TreeNode<Pair< A, B > >(p, 0);
			insert_node(n);
			Collection< Pair< A, B > >::count++;
			return n->val.second;
		}
	}

	const bool exists(A &key) const {
		const TreeNode<Pair< A, B > > *n = find(key);
		if(n) {
			return true;
		} else
			return false;
	}

	const bool remove(A &key) {
		TreeNode<Pair< A, B > > *n = find(key);
		if(n) {
			delete_node(n);
			return true;
		} else
			return false;
	}
};