fork download
copy 
  1. template <class T>
  2. struct treap {
  3. private:
  4. 	struct node {
  5. 		T key;
  6. 		unsigned long long priority;
  7. 		unsigned size;
  8. 		node *left, *right;
  9. 	};
  10. 	struct xorshift {
  11. 		unsigned long long x,y,z,w;
  12. 		xorshift(): x(1234567891011121314), y(91734892562378), z(77777777777777), w(986732789462378) {}
  13. 		unsigned long long next() {
  14. 			unsigned long long t=x^(x<<11);
  15. 			x=y;y=z;z=w;
  16. 			return w=w^(w>>19)^t^(t>>8);
  17. 		}
  18. 	};
  19. 	typedef node *node_ptr;
  20. 	node_ptr root;
  21. 	xorshift rng;
  22. 	unsigned long long next() {
  23. 		return rng.next();
  24. 	}
  25. 	node_ptr new_node(T key) {
  26. 		node_ptr res=(node_ptr)malloc(sizeof(node));
  27. 		res->key=key;
  28. 		res->priority=next();
  29. 		res->size=1;
  30. 		res->left=NULL;
  31. 		res->right=NULL;
  32. 		return res;
  33. 	}
  34. 	unsigned size(node_ptr &root) {
  35. 		if(root==NULL) return 0;
  36. 		else return root->size;
  37. 	}
  38. 	void update_size(node_ptr &root) {
  39. 		if(root!=NULL) root->size=1+size(root->left)+size(root->right);
  40. 	}
  41. 	node_ptr right_rotation(node_ptr x) {
  42. 		node_ptr y=x->left,t2=y->right;
  43. 		x->left=t2;
  44. 		y->right=x;
  45. 		update_size(x);
  46. 		update_size(y);
  47. 		return y;
  48. 	}
  49. 	node_ptr left_rotation(node_ptr y) {
  50. 		node_ptr x=y->right,t2=x->left;
  51. 		y->right=t2;
  52. 		x->left=y;
  53. 		update_size(y);
  54. 		update_size(x);
  55. 		return x;
  56. 	}
  57. 	node_ptr insert(node_ptr root, T key) {
  58. 		if(root==NULL) {
  59. 			return new_node(key);
  60. 		}
  61. 		else if(key<root->key) {
  62. 			root->left=insert(root->left,key);
  63. 			if(root->left->priority>root->priority) root=right_rotation(root);
  64. 		}
  65. 		else {
  66. 			root->right=insert(root->right,key);
  67. 			if(root->right->priority>root->priority) root=left_rotation(root);
  68. 		}
  69. 		update_size(root);
  70. 		return root;
  71. 	}
  72. 	node_ptr remove_it(node_ptr root) {
  73. 		if(root->left==NULL && root->right==NULL) {
  74. 			return NULL;
  75. 		}
  76. 		if(root->left==NULL) {
  77. 			root=left_rotation(root);
  78. 			root->left=remove_it(root->left);
  79. 			update_size(root);
  80. 			return root;
  81. 		}
  82. 		if(root->right==NULL) {
  83. 			root=right_rotation(root);
  84. 			root->right=remove_it(root->right);
  85. 			update_size(root);
  86. 			return root;
  87. 		}
  88. 		if(root->left->priority>root->right->priority) {
  89. 			root=right_rotation(root);
  90. 			root->right=remove_it(root->right);
  91. 		}
  92. 		else {
  93. 			root=left_rotation(root);
  94. 			root->left=remove_it(root->left);
  95. 		}
  96. 		update_size(root);
  97. 		return root;
  98. 	}
  99. 	node_ptr erase(node_ptr root, T key) {
  100. 		if(key<root->key) {
  101. 			root->left=erase(root->left,key);
  102. 		}
  103. 		else if(key>root->key) {
  104. 			root->right=erase(root->right,key);
  105. 		}
  106. 		else {
  107. 			root=remove_it(root);
  108. 		}
  109. 		update_size(root);
  110. 		return root;
  111. 	}
  112. 	unsigned count_less(node_ptr root, T key) {
  113. 		if(root==NULL) return 0;
  114. 		else if(key<root->key) return count_less(root->left,key);
  115. 		else if(key==root->key) return size(root->left);
  116. 		else return 1+size(root->left)+count_less(root->right,key);
  117. 	}
  118. 	T kth(node_ptr root, unsigned k) {
  119. 		if(1+size(root->left)==k) return root->key;
  120. 		else if(k<=size(root->left)) return kth(root->left,k);
  121. 		else return kth(root->right,k-1-size(root->left));
  122. 	}
  123. 	bool find(node_ptr root, T key) {
  124. 		if(root==NULL) return false;
  125. 		else if(key<root->key) return find(root->left,key);
  126. 		else if(key>root->key) return find(root->right,key);
  127. 		else return true;
  128. 	}
  129. public:
  130. 	treap(): root(NULL) {}
  131. 	void clear() {
  132. 		root=NULL;
  133. 		rng=xorshift();
  134. 	}
  135. 	unsigned size() {
  136. 		return size(root);
  137. 	}
  138. 	bool empty() {
  139. 		return (size()==0);
  140. 	}
  141. 	bool find(T key) {
  142. 		return find(root,key);
  143. 	}
  144. 	void insert(T key) {
  145. 		if(find(key)==false) root=insert(root,key);
  146. 	}
  147. 	void erase(T key) {
  148. 		if(find(key)==true) root=erase(root,key);
  149. 	}
  150. 	T kth(unsigned k) {
  151. 		return kth(root,k);
  152. 	}
  153. 	unsigned count_less(T key) {
  154. 		return count_less(root,key);
  155. 	}	
  156. };
  157.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In member function 'treap<T>::node* treap<T>::new_node(T)':
prog.cpp:26:45: error: there are no arguments to 'malloc' that depend on a template parameter, so a declaration of 'malloc' must be available [-fpermissive]
   node_ptr res=(node_ptr)malloc(sizeof(node));
                                             ^
prog.cpp:26:45: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
prog.cpp:30:13: error: 'NULL' was not declared in this scope
   res->left=NULL;
             ^
prog.cpp: In member function 'unsigned int treap<T>::size(treap<T>::node*&)':
prog.cpp:35:12: error: 'NULL' was not declared in this scope
   if(root==NULL) return 0;
            ^
prog.cpp: In member function 'void treap<T>::update_size(treap<T>::node*&)':
prog.cpp:39:12: error: 'NULL' was not declared in this scope
   if(root!=NULL) root->size=1+size(root->left)+size(root->right);
            ^
prog.cpp: In member function 'treap<T>::node* treap<T>::insert(treap<T>::node_ptr, T)':
prog.cpp:58:12: error: 'NULL' was not declared in this scope
   if(root==NULL) {
            ^
prog.cpp: In member function 'treap<T>::node* treap<T>::remove_it(treap<T>::node_ptr)':
prog.cpp:73:18: error: 'NULL' was not declared in this scope
   if(root->left==NULL && root->right==NULL) {
                  ^
prog.cpp:76:18: error: 'NULL' was not declared in this scope
   if(root->left==NULL) {
                  ^
prog.cpp:82:19: error: 'NULL' was not declared in this scope
   if(root->right==NULL) {
                   ^
prog.cpp: In member function 'unsigned int treap<T>::count_less(treap<T>::node_ptr, T)':
prog.cpp:113:12: error: 'NULL' was not declared in this scope
   if(root==NULL) return 0;
            ^
prog.cpp: In member function 'bool treap<T>::find(treap<T>::node_ptr, T)':
prog.cpp:124:12: error: 'NULL' was not declared in this scope
   if(root==NULL) return false;
            ^
prog.cpp: In constructor 'treap<T>::treap()':
prog.cpp:130:16: error: 'NULL' was not declared in this scope
  treap(): root(NULL) {}
                ^
prog.cpp: In member function 'void treap<T>::clear()':
prog.cpp:132:8: error: 'NULL' was not declared in this scope
   root=NULL;
        ^
stdout
copy 
Standard output is empty
https://ideone.com/8DUWwZ
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!