Weight Biased Leftist Tree

weight_biased_leftist_tree.cpp

#include<functional>
#ifndef WEIGHT_BIASED_LEFTIST_TREE
#define WEIGHT_BIASED_LEFTIST_TREE
template<typename T,typename _Compare=std::less<T> >
class wb_leftist_tree{
	private:
		struct node{
			T data;
			int size;
			node *l,*r;
			node(const T&d):data(d),size(1),l(0),r(0){}
		}*root;
		_Compare cmp;
		inline int size(node *o){return o?o->size:0;}
		node *merge(node *a,node *b){
			if(!a||!b)return a?a:b;
			if(cmp(a->data,b->data)){
				node *t=a;a=b;b=t;
			}
			a->r=merge(a->r,b);
			if(size(a->l)<size(a->r)){
				node *t=a->l;a->l=a->r;a->r=t;
			}
			a->size=size(a->l)+size(a->r)+1;
			return a;
		}
		void _clear(node *&o){
			if(o)_clear(o->l),_clear(o->r),delete o;
		}
	public:
		wb_leftist_tree():root(0){}
		~wb_leftist_tree(){_clear(root);}
		inline void clear(){
			_clear(root),root=0;
		}
		inline void join(wb_leftist_tree &o){
			root=merge(root,o.root);
			o.root=0;
		}
		inline void swap(wb_leftist_tree &o){
			node *t=root;
			root=o.root;
			o.root=t;
		}
		inline void push(const T&data){
			root=merge(root,new node(data));
		}
		inline void pop(){
			if(!root)return;
			node *tmd=merge(root->l,root->r);
			delete root;
			root=tmd;
		}
		inline const T& top(){return root->data;}
		inline int size(){return size(root);}
		inline bool empty(){return !size(root);}
};
#endif