aboutsummaryrefslogtreecommitdiffstats
path: root/meowpp/dsa
diff options
context:
space:
mode:
Diffstat (limited to 'meowpp/dsa')
-rw-r--r--meowpp/dsa/DisjointSet.h32
-rw-r--r--meowpp/dsa/DisjointSet.hpp52
-rw-r--r--meowpp/dsa/Heaps.h84
-rw-r--r--meowpp/dsa/KD_Tree.h75
-rw-r--r--meowpp/dsa/KD_Tree.hpp196
-rw-r--r--meowpp/dsa/MergeableHeap.hpp146
-rw-r--r--meowpp/dsa/SplayTree.h103
-rw-r--r--meowpp/dsa/SplayTree.hpp505
8 files changed, 1193 insertions, 0 deletions
diff --git a/meowpp/dsa/DisjointSet.h b/meowpp/dsa/DisjointSet.h
new file mode 100644
index 0000000..1ea6d97
--- /dev/null
+++ b/meowpp/dsa/DisjointSet.h
@@ -0,0 +1,32 @@
+#ifndef DisjointSet_H__
+#define DisjointSet_H__
+
+#include <vector>
+#include <cstdlib>
+
+namespace meow{
+ class DisjointSet{
+ private:
+ size_t n;
+ std::vector<size_t> father;
+ std::vector<size_t> depth;
+ //
+ size_t _root(size_t now);
+ size_t _merge(size_t a, size_t b);
+ public:
+ DisjointSet();
+ DisjointSet(size_t _n);
+ DisjointSet(DisjointSet const& dsj);
+ //
+ size_t root (size_t a ) const;
+ size_t size ( ) const;
+ //
+ void reset(size_t _n );
+ size_t merge(size_t a, size_t b);
+ };
+}
+
+#include "DisjointSet.hpp"
+
+
+#endif // DisjointSet_H__
diff --git a/meowpp/dsa/DisjointSet.hpp b/meowpp/dsa/DisjointSet.hpp
new file mode 100644
index 0000000..3b66626
--- /dev/null
+++ b/meowpp/dsa/DisjointSet.hpp
@@ -0,0 +1,52 @@
+#include <vector>
+#include <cstdlib>
+
+namespace meow{
+ inline size_t DisjointSet::_root(size_t now){
+ if(father[now] == now) return now;
+ return (father[now] = _root(father[now]));
+ }
+ inline size_t DisjointSet::_merge(size_t a, size_t b){
+ a = _root(a);
+ b = _root(b);
+ if(a == b) return a;
+ if(depth[a] > depth[b]){
+ father[b] = a;
+ return a;
+ }else{
+ father[a] = b;
+ if(depth[a] == depth[b]){
+ depth[b]++;
+ }
+ return b;
+ }
+ }
+ //
+ inline DisjointSet::DisjointSet(): n(0){ }
+ inline DisjointSet::DisjointSet(size_t _n): n(0){
+ reset(_n);
+ }
+ inline DisjointSet::DisjointSet(DisjointSet const& dsj){
+ n = dsj.n;
+ father = dsj.father;
+ depth = dsj.depth;
+ }
+ //
+ inline size_t DisjointSet::root(size_t a) const{
+ return ((DisjointSet*)this)->_root(a);
+ }
+ inline size_t DisjointSet::size() const{ return n; }
+ //
+ inline void DisjointSet::reset(size_t _n){
+ n = _n;
+ father.resize(n);
+ depth .resize(n);
+ for(size_t i = 0; i < n; i++){
+ father[i] = i;
+ depth [i] = 1;
+ }
+ }
+ inline size_t DisjointSet::merge(size_t a, size_t b){
+ return _merge(a, b);
+ }
+}
diff --git a/meowpp/dsa/Heaps.h b/meowpp/dsa/Heaps.h
new file mode 100644
index 0000000..cac3e01
--- /dev/null
+++ b/meowpp/dsa/Heaps.h
@@ -0,0 +1,84 @@
+#ifndef Heap_H__
+#define Heap_H__
+
+#include <cstdlib>
+
+namespace meow{
+ /*********************************************************
+ @asciidoc
+ === MergeableHeap<Key, Value>
+ .Description
+ MergeableHeap is a kind of maximum-heap with an extra method `merge`,
+ which will merge another MergeableHeap into itself.
+
+ .Support methods
+ * N <- number of elements in the heap
+ * M <- number of elements in the other heap if need
+ [options="header",width="100%",cols="1>,1<s,5<,1<,1<,10<",grid="rows"]
+ |=======================================================================
+ |Const?|Name| Parameters| Return Type| Time Complexity| Description
+ ||operator= | (MergeableHeap const&)| *this | O(N)
+ | Copy operator.
+ ||moveTo | (MergeableHeap*) | void | O(M)
+ | Transform the this->data to the heap specified in parameters
+ |const|top | () | Element | O(1)
+ | Return the maximum element in the heap.
+ |const|size | () | size_t | O(1)
+ | Return the number of elements in the heap.
+ |const|empty| () | bool | O(1)
+ | Return whether the heap is empty or not.
+ ||push |(Element) |void | O(log N)
+ | Add a element into the heap
+ ||pop |() |void | O(log N)
+ | Delete the maximum element from the heap
+ ||merge |(MergeableHeap*) |void | O(log M)
+ | Merge the specified MergeableHeap(with size=M) into itself
+ ||clear |() |void | O(N)
+ | Delete all elements from the heap
+ |=======================================================================
+
+WARNING: Consider there are two MergeableHeap `A` and `B`.
+`B` will become empty after you call `A.merge(&B)`.
+The data in `B` will override by data in `A` and `A` will become empty after
+you call `A.moveTo(&B)`
+ @asciidoc-
+ *********************************************************/
+ template<class Element>
+ class MergeableHeap{ // maximum-heap
+ private:
+ struct Node{
+ Element value;
+ Node* l_child;
+ Node* r_child;
+ size_t weight;
+ Node(Element const& _value);
+ };
+ //
+ Node* root;
+ //
+ void clear(Node* _node );
+ Node* dup (Node* _node2 );
+ Node* merge(Node* _left, Node* _right);
+ public:
+ MergeableHeap();
+ MergeableHeap(MergeableHeap const& _heap2);
+ //
+ ~MergeableHeap();
+ //
+ MergeableHeap& operator=(MergeableHeap const& _heap2);
+ void moveTo(MergeableHeap* _heap2);
+ //
+ Element const& top () const;
+ size_t size () const;
+ size_t empty() const;
+ //
+ void push (Element const& _value);
+ void pop ( );
+ void clear( );
+ void merge(MergeableHeap* _heap2);
+ };
+}
+
+#include "MergeableHeap.hpp"
+
+#endif // Heap_H__
diff --git a/meowpp/dsa/KD_Tree.h b/meowpp/dsa/KD_Tree.h
new file mode 100644
index 0000000..0abc358
--- /dev/null
+++ b/meowpp/dsa/KD_Tree.h
@@ -0,0 +1,75 @@
+#ifndef KD_Tree_H__
+#define KD_Tree_H__
+
+#include <list>
+#include <vector>
+#include <cstdlib>
+
+namespace meow{
+ template<class Keys, class Key, class Value>
+ class KD_Tree{
+ private:
+ struct Node{
+ Keys key;
+ Value value;
+ ssize_t lChild;
+ ssize_t rChild;
+ Node(Keys _key, Value _value, ssize_t _l_child, ssize_t _r_child);
+ };
+ typedef std::vector<Node> Nodes;
+ class Sorter{
+ private:
+ Nodes const& nodes;
+ size_t cmp;
+ public:
+ Sorter(Nodes const& _nodes, size_t _cmp);
+ bool operator()(size_t const& a, size_t const& b) const;
+ };
+ typedef std::vector<Value> Values;
+ struct Answer{
+ Node const& node;
+ Key dist2;
+ Answer(Node const& _node, Key _dist2);
+ bool operator<(Answer const& b) const;
+ };
+ typedef typename std::list<Answer> AnswerList;
+ typedef typename AnswerList::iterator AnswerListIterator;
+ //
+ const ssize_t NIL;
+ //
+ Nodes nodes;
+ size_t root;
+ bool needRebuild;
+ size_t dimension;
+ //
+ Key distance2(Keys const& k1, Keys const& k2) const;
+ size_t query(Keys const& key,
+ size_t k,
+ size_t index,
+ int depth,
+ std::vector<Key>& dist2_v,
+ Key dist2_s,
+ AnswerList* ret) const;
+ ssize_t build(ssize_t beg,
+ ssize_t end,
+ std::vector<size_t>* orders,
+ int depth);
+ public:
+ KD_Tree();
+ KD_Tree(size_t _dimension);
+ ~KD_Tree();
+ //
+ void insert(Keys const& key, Value value);
+ void build();
+ //
+ Value query (Keys const& point, int k) const;
+ Values rangeQuery(Keys const& point, int k) const;
+ //
+ void clear();
+ void reset(size_t _dimension);
+ };
+}
+
+#include "KD_Tree.hpp"
+
+#endif // KD_Tree_H__
diff --git a/meowpp/dsa/KD_Tree.hpp b/meowpp/dsa/KD_Tree.hpp
new file mode 100644
index 0000000..9e9a925
--- /dev/null
+++ b/meowpp/dsa/KD_Tree.hpp
@@ -0,0 +1,196 @@
+#include <cstdlib>
+#include <list>
+#include <vector>
+#include <algorithm>
+#include <set>
+#include "utility.h"
+
+namespace meow{
+ template<class Keys, class Key, class Value>
+ inline KD_Tree<Keys,Key,Value>::Node::Node(Keys _key,
+ Value _value,
+ ssize_t _l_child,
+ ssize_t _r_child):
+ key(_key), value(_value), lChild(_l_child), rChild(_r_child){ }
+ //
+ template<class Keys, class Key, class Value>
+ inline KD_Tree<Keys, Key, Value>::Sorter::Sorter(KD_Tree::Nodes const& _nodes,
+ size_t _cmp):
+ nodes(_nodes), cmp(_cmp){ }
+ template<class Keys, class Key, class Value>
+ inline bool
+ KD_Tree<Keys, Key, Value>::Sorter::operator()(size_t const& a,
+ size_t const& b) const{
+ if(nodes[a].key[cmp] != nodes[b].key[cmp]){
+ return (nodes[a].key[cmp] < nodes[b].key[cmp]);
+ }
+ return (nodes[a].value < nodes[b].value);
+ }
+ //
+ template<class Keys, class Key, class Value>
+ inline KD_Tree<Keys, Key, Value>::Answer::Answer(Node const& _node,
+ Key _dist2):
+ node(_node), dist2(_dist2){ }
+ template<class Keys, class Key, class Value>
+ inline bool
+ KD_Tree<Keys, Key, Value>::Answer::operator<(Answer const& b) const{
+ if(dist2 != b.dist2) return (dist2 < b.dist2);
+ return (node.value < b.node.value);
+ }
+ //
+ template<class Keys, class Key, class Value>
+ inline Key KD_Tree<Keys, Key, Value>::distance2(Keys const& k1,
+ Keys const& k2) const{
+ Key ret(0);
+ for(size_t i = 0; i < dimension; i++)
+ ret += squ(k1[i] - k2[i]);
+ return ret;
+ }
+ template<class Keys, class Key, class Value>
+ inline size_t KD_Tree<Keys, Key, Value>::query(Keys const& key,
+ size_t k,
+ size_t index,
+ int depth,
+ std::vector<Key>& dist2_v,
+ Key dist2_s,
+ KD_Tree::AnswerList* ret) const{
+ if(index == NIL){
+ return 0;
+ }
+ size_t cmp = depth % dimension;
+ ssize_t right_side, opposite, size;
+ ssize_t sz, other;
+ if(key[cmp] <= nodes[index].key[cmp]){
+ right_side = nodes[index].lChild;
+ opposite = nodes[index].rChild;
+ }else{
+ right_side = nodes[index].rChild;
+ opposite = nodes[index].lChild;
+ }
+ size = query(key, k, right_side, depth + 1, dist2_v, dist2_s, ret);
+ Answer my_ans(nodes[index], distance2(nodes[index].key, key));
+ if(size < k || my_ans < *(ret->rbegin())){
+ KD_Tree::AnswerListIterator it = ret->begin();
+ while(it != ret->end() && !(my_ans < *it)) it++;
+ ret->insert(it, my_ans);
+ size++;
+ }
+ Key dist2_old = dist2_v[cmp];
+ dist2_v[cmp] = squ(nodes[index].key[cmp] - key[cmp]);
+ dist2_s += dist2_v[cmp] - dist2_old;
+ if(size < k || (*(ret->rbegin())).dist2 >= dist2_s){
+ KD_Tree::AnswerList ret2;
+ size += query(key, k, opposite, depth + 1, dist2_v, dist2_s, &ret2);
+ KD_Tree::AnswerListIterator it1, it2;
+ for(it1 = ret->begin(), it2 = ret2.begin(); it2 != ret2.end(); it2++){
+ while(it1 != ret->end() && *it1 < *it2) it1++;
+ it1 = ++(ret->insert(it1, *it2));
+ }
+ }
+ if(size > k){
+ for(int i = size - k; i--; ){
+ ret->pop_back();
+ }
+ size = k;
+ }
+ dist2_v[cmp] = dist2_old;
+ return size;
+ }
+ template<class Keys, class Key, class Value>
+ inline ssize_t KD_Tree<Keys, Key, Value>::build(ssize_t beg,
+ ssize_t end,
+ std::vector<size_t>* orders,
+ int depth){
+ if(beg > end){
+ return NIL;
+ }
+ ssize_t mid = (beg + end) / 2;
+ size_t cmp = depth % 2;
+ std::set<size_t> right;
+ for(ssize_t i = mid + 1; i <= end; i++){
+ right.insert(orders[cmp][i]);
+ }
+ for(int i = 0; i < dimension; i++){
+ if(i == cmp) continue;
+ size_t aa = beg, bb = mid + 1;
+ for(int j = beg; j <= end; j++){
+ if(orders[i][j] == orders[cmp][mid]){
+ orders[dimension][mid] = orders[i][j];
+ }else if(right.find(orders[i][j]) != right.end()){
+ orders[dimension][bb++] = orders[i][j];
+ }else{
+ orders[dimension][aa++] = orders[i][j];
+ }
+ }
+ for(int j = beg; j <= end; j++){
+ orders[i][j] = orders[dimension][j];
+ }
+ }
+ nodes[orders[cmp][mid]].lChild = build(beg, mid - 1, orders, depth + 1);
+ nodes[orders[cmp][mid]].rChild = build(mid + 1, end, orders, depth + 1);
+ return orders[cmp][mid];
+ }
+ template<class Keys, class Key, class Value>
+ inline KD_Tree<Keys, Key, Value>::KD_Tree():
+ NIL(-1), root(NIL), needRebuild(false), dimension(1){ }
+ template<class Keys, class Key, class Value>
+ inline KD_Tree<Keys, Key, Value>::KD_Tree(size_t _dimension):
+ NIL(-1), root(NIL), needRebuild(false), dimension(_dimension){ }
+ template<class Keys, class Key, class Value>
+ inline KD_Tree<Keys, Key, Value>::~KD_Tree(){ }
+ template<class Keys, class Key, class Value>
+ inline void KD_Tree<Keys, Key, Value>::insert(Keys const& key, Value value){
+ nodes.push_back(Node(key, value, NIL, NIL));
+ needRebuild = true;
+ }
+ template<class Keys, class Key, class Value>
+ inline void KD_Tree<Keys, Key, Value>::build(){
+ if(needRebuild){
+ std::vector<size_t> orders[dimension + 1];
+ for(int j = 0; j < dimension + 1; j++){
+ orders[j].resize(nodes.size());
+ }
+ for(int j = 0; j < dimension; j++){
+ for(size_t i = 0, I = nodes.size(); i < I; i++){
+ orders[j][i] = i;
+ }
+ std::sort(orders[j].begin(), orders[j].end(), Sorter(nodes, j));
+ }
+ root = build(0, (ssize_t)nodes.size() - 1, orders, 0);
+ needRebuild = false;
+ }
+ }
+ template<class Keys, class Key, class Value>
+ inline Value KD_Tree<Keys, Key, Value>::query(Keys const& point, int k) const{
+ ((KD_Tree*)this)->build();
+ KD_Tree::AnswerList ret;
+ std::vector<Key> tmp(dimension, Key(0));
+ query(point, k, root, 0, tmp, Key(0), &ret);
+ return (*(ret.rbegin())).node.value;
+ }
+ template<class Keys, class Key, class Value>
+ inline typename KD_Tree<Keys, Key, Value>::Values
+ KD_Tree<Keys, Key, Value>::rangeQuery(Keys const& point, int k) const{
+ ((KD_Tree*)this)->build();
+ KD_Tree::AnswerList ret;
+ std::vector<Key> tmp(dimension, Key(0));
+ query(point, k, root, 0, tmp, Key(0), &ret);
+ KD_Tree::Values ret_val(ret.size());
+ int i = 0;
+ for(KD_Tree::AnswerListIterator it = ret.begin(); it != ret.end(); it++){
+ ret_val[i++] = (*it).node.value;
+ }
+ return ret_val;
+ }
+ template<class Keys, class Key, class Value>
+ inline void KD_Tree<Keys, Key, Value>::clear(){
+ root = NIL;
+ nodes.clear();
+ needRebuild = false;
+ }
+ template<class Keys, class Key, class Value>
+ inline void KD_Tree<Keys, Key, Value>::reset(size_t _dimension){
+ clear();
+ dimension = _dimension;
+ }
+}
diff --git a/meowpp/dsa/MergeableHeap.hpp b/meowpp/dsa/MergeableHeap.hpp
new file mode 100644
index 0000000..de3aea9
--- /dev/null
+++ b/meowpp/dsa/MergeableHeap.hpp
@@ -0,0 +1,146 @@
+// @class name : MergeableHeap
+// @implement : Leftist Tree
+
+#include <cstdlib>
+
+namespace meow{
+ //////////////////////////////////////////////////////////
+ // **# MergeableHeap--Node-- constructor #** //
+ //////////////////////////////////////////////////////////
+ template<class Element>
+ inline
+ MergeableHeap<Element>::Node::Node(Element const& _value): // Node
+ value(_value), l_child(NULL), r_child(NULL), weight(1){ }
+
+ //////////////////////////////////////////////////////////
+ // **# MergeableHeap -- clear, duplicate #** //
+ //////////////////////////////////////////////////////////
+ template<class Element>
+ inline void
+ MergeableHeap<Element>::clear(Node* _node){ //clear
+ if(_node != NULL){
+ clear(_node->l_child);
+ clear(_node->r_child);
+ delete _node;
+ }
+ }
+ template<class Element>
+ inline typename MergeableHeap<Element>::Node*
+ MergeableHeap<Element>::dup(Node* _node2){ // dup
+ if(_node2 == NULL) return NULL;
+ Node* ret = new Node(_node2->value);
+ ret->l_child = dup(_node2->l_child);
+ ret->r_child = dup(_node2->r_child);
+ ret->weight = 1;
+ ret->weight += (ret->l_child == NULL ? 0 : ret->l_child->weight);
+ ret->weight += (ret->r_child == NULL ? 0 : ret->r_child->weight);
+ return ret;
+ }
+
+ //////////////////////////////////////////////////////////
+ // **# MergeableHeap -- merge #** //
+ //////////////////////////////////////////////////////////
+ template<class Element>
+ inline typename MergeableHeap<Element>::Node*
+ MergeableHeap<Element>::merge(Node* _left, Node* _right){ //merge
+ if(_left == NULL) return _right;
+ if(_right == NULL) return _left;
+ if(_left->value < _right->value){
+ std::swap(_left, _right);
+ }
+ _left->r_child = merge(_left->r_child, _right);
+ size_t lw = (_left->l_child == NULL ? 0 : _left->l_child->weight);
+ size_t rw = (_left->r_child == NULL ? 0 : _left->r_child->weight);
+ if(lw < rw){
+ std::swap(_left->l_child, _left->r_child);
+ }
+ _left->weight = 1 + lw + rw;
+ return _left;
+ }
+
+ //////////////////////////////////////////////////////////
+ // **# MergeableHeap -- constrctors/destructors #** //
+ //////////////////////////////////////////////////////////
+ template<class Element>
+ inline
+ MergeableHeap<Element>::MergeableHeap(): //MergeableHeap
+ root(NULL){ }
+ template<class Element>
+ inline
+ MergeableHeap<Element>::MergeableHeap(MergeableHeap const& _heap2):
+ root(NULL){
+ root = dup(_heap2.root);
+ }
+ template<class Element>
+ inline
+ MergeableHeap<Element>::~MergeableHeap(){ //~MergeableHeap
+ clear(root);
+ }
+
+ //////////////////////////////////////////////////////////
+ //**# MergeableHeap -- copy operation/data transform #**//
+ //////////////////////////////////////////////////////////
+ template<class Element>
+ inline MergeableHeap<Element>&
+ MergeableHeap<Element>::operator=(MergeableHeap const& _heap2){ // =
+ root = dup(_heap2.root);
+ return *this;
+ }
+ template<class Element>
+ inline void
+ MergeableHeap<Element>::moveTo(MergeableHeap* _heap2){ // moveTo
+ _heap2->clear();
+ _heap2->root = root;
+ root = NULL;
+ }
+ //////////////////////////////////////////////////////////
+ // **# MergeableHeap -- access: top, size, emtpy #** //
+ //////////////////////////////////////////////////////////
+ template<class Element>
+ inline Element const&
+ MergeableHeap<Element>::top() const{ // top
+ return root->value;
+ }
+ template<class Element>
+ inline size_t
+ MergeableHeap<Element>::size() const{ // size
+ return (root == NULL ? 0 : root->weight);
+ }
+ template<class Element>
+ inline size_t
+ MergeableHeap<Element>::empty() const{ // empty
+ return (size() == 0);
+ }
+ //////////////////////////////////////////////////////////
+ // **# MergeableHeap -- update: push, pop, merge #** //
+ //////////////////////////////////////////////////////////
+ template<class Element>
+ inline void
+ MergeableHeap<Element>::push(Element const& _value){ // push
+ Node* new_node = new Node(_value);
+ root = merge(root, new_node);
+ }
+ template<class Element>
+ inline void
+ MergeableHeap<Element>::pop(){ // pop
+ Node* l = root->l_child;
+ Node* r = root->r_child;
+ delete root;
+ root = merge(l, r);
+ }
+ template<class Element>
+ inline void
+ MergeableHeap<Element>::merge(MergeableHeap* _heap2){ // merge
+ root = merge(root, _heap2->root);
+ _heap2->root = NULL;
+ }
+ //////////////////////////////////////////////////////////
+ // **# MergeableHeap -- refresh: clear #** //
+ //////////////////////////////////////////////////////////
+ template<class Element>
+ inline void
+ MergeableHeap<Element>::clear(){ // clear
+ clear(root);
+ root = NULL;
+ }
+}
diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h
new file mode 100644
index 0000000..78b54f6
--- /dev/null
+++ b/meowpp/dsa/SplayTree.h
@@ -0,0 +1,103 @@
+#ifndef SplayTree_h__
+#define SplayTree_h__
+
+#include "utility.h"
+
+namespace meow{
+ template<class Key, class Value>
+ class SplayTree{
+ private:
+ struct Node{
+ Key _key;
+ Key _keyOffset;
+ Value _value;
+ size_t _size;
+ Node* _parent;
+ Node* _lChild;
+ Node* _rChild;
+ //
+ Node(Key const& __key, Value const& __value);
+ };
+ //
+ Node* _root;
+ //
+ void offsetAdd (Node* __node, Key const& __delta) const;
+ void offsetDown (Node* __node ) const;
+ void sizeUpdate (Node* __node ) const;
+ void connectLChild(Node* __parent, Node* __child ) const;
+ void connectRChild(Node* __parent, Node* __child ) const;
+ //
+ Node* clear(Node* __node);
+ Node* dup (Node* __node);
+ //
+ void rotate( Node* __parent, Node* __child) const;
+ void rotate(Node* __grand, Node* __parent, Node* __child) const;
+ Node* splay(Node* __node) const;
+ //
+ Node* findKey (Node* __node, Key const& __key) const;
+ Node* findMinMax(Node* __node, bool minimum ) const;
+ Node* findOrder (Node* __node, size_t __order ) const;
+ //
+ void split(Node* __root, Node** __left, Node** __right);
+ Node* merge( Node* __left, Node* __right);
+ //
+ void print(Node* __now, int __depth) const;
+ public:
+ class Element{
+ private:
+ typedef std::pair<Key const&, Value&> Entry;
+ Entry* _entry;
+ Node * _node;
+ //
+ void reset(Node* __node);
+ public:
+ Element();
+ Element(Node* __node);
+ Element(Element const& __iterator2);
+ ~Element();
+ //
+ Element& operator=(Element const& __e2);
+ //
+ Entry* operator->();
+ Entry& operator *();
+ //
+ bool operator==(Element const& __e2) const;
+ bool operator!=(Element const& __e2) const;
+ };
+ //
+ SplayTree();
+ SplayTree(SplayTree const& __tree2);
+ ~SplayTree();
+ //
+ SplayTree& operator=(SplayTree const& __tree2);
+ void moveTo(SplayTree* __tree2);
+ //
+ Element lowerBound(Key const& __key) const;
+ Element upperBound(Key const& __key) const;
+ Element rLowerBound(Key const& __key) const;
+ Element rUpperBound(Key const& __key) const;
+ Element find (Key const& __key) const;
+ Element order(size_t __order ) const;
+ Element first( ) const;
+ Element last ( ) const;
+ Element end( ) const;
+ //
+ size_t size() const;
+ bool empty() const;
+ //
+ void clear();
+ void keyOffset(Key const& __delta);
+ bool insert (Key const& __key, Value const& __value);
+ bool erase (Key const& __key);
+ Value& operator[](Key const& __key);
+ void splitOut(Key const& __upper_bound, SplayTree* __right);
+ bool mergeAfter(SplayTree* __tree2);
+ bool merge (SplayTree* __tree2);
+ //
+ void print() const;
+ };
+}
+
+#include "SplayTree.hpp"
+
+#endif // SplayTree_h__
diff --git a/meowpp/dsa/SplayTree.hpp b/meowpp/dsa/SplayTree.hpp
new file mode 100644
index 0000000..835664f
--- /dev/null
+++ b/meowpp/dsa/SplayTree.hpp
@@ -0,0 +1,505 @@
+
+namespace meow{
+ template<class Key, class Value>
+ inline SplayTree<Key, Value>::Node::Node(Key const& __key,
+ Value const& __value):
+ _key(__key),
+ _keyOffset(0),
+ _value(__value),
+ _size(1),
+ _parent(NULL),
+ _lChild(NULL),
+ _rChild(NULL){ }
+ //
+ template<class Key, class Value>
+ inline void SplayTree<Key, Value>::offsetAdd(Node* __node,
+ Key const& __delta) const{
+ __node->_key = __node->_key + __delta;
+ __node->_keyOffset = __node->_keyOffset + __delta;
+ }
+ template<class Key, class Value>
+ inline void SplayTree<Key, Value>::sizeUpdate(Node* __node) const{
+ __node->_size = 1;
+ if(__node->_lChild != NULL) __node->_size += __node->_lChild->_size;
+ if(__node->_rChild != NULL) __node->_size += __node->_rChild->_size;
+ }
+ template<class Key, class Value>
+ inline void
+ SplayTree<Key, Value>::offsetDown(Node* __node) const{
+ if(__node->_lChild != NULL) offsetAdd(__node->_lChild, __node->_keyOffset);
+ if(__node->_rChild != NULL) offsetAdd(__node->_rChild, __node->_keyOffset);
+ __node->_keyOffset = 0;
+ }
+ //
+ template<class Key, class Value>
+ inline void SplayTree<Key, Value>::connectLChild(Node* __parent,
+ Node* __child) const{
+ if(__parent != NULL) __parent->_lChild = __child;
+ if(__child != NULL) __child ->_parent = __parent;
+ }
+ template<class Key, class Value>
+ inline void SplayTree<Key, Value>::connectRChild(Node* __parent,
+ Node* __child) const{
+ if(__parent != NULL) __parent->_rChild = __child;
+ if(__child != NULL) __child ->_parent = __parent;
+ }
+ //
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Node*
+ SplayTree<Key, Value>::clear(Node* __node){
+ if(__node != NULL){
+ clear(__node->_lChild);
+ clear(__node->_rChild);
+ delete __node;
+ }
+ return NULL;
+ }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::dup(Node* __node){
+ if(__node == NULL){
+ return NULL;
+ }
+ Node* node = Node(__node->_key, __node->_value);
+ connectLChild(node, dup(__node->_lChild));
+ connectRChild(node, dup(__node->_rChild));
+ return node;
+ }
+ //
+ template<class Key, class Value>
+ inline void SplayTree<Key, Value>::rotate(Node* __parent,
+ Node* __child) const{
+ if(__parent->_lChild == __child){
+ connectLChild(__parent, __child->_rChild);
+ connectRChild(__child , __parent);
+ }else{
+ connectRChild(__parent, __child->_lChild);
+ connectLChild(__child , __parent);
+ }
+ sizeUpdate(__parent);
+ sizeUpdate(__child );
+ }
+ template<class Key, class Value>
+ inline void SplayTree<Key, Value>::rotate(Node* __grand,
+ Node* __parent,
+ Node* __child) const{
+ if(__grand->_lChild == __parent){
+ if(__parent->_lChild == __child){
+ connectLChild(__grand , __parent->_rChild);
+ connectLChild(__parent, __child ->_rChild);
+ connectRChild(__child , __parent);
+ connectRChild(__parent, __grand );
+ }else{
+ connectRChild(__parent, __child->_lChild);
+ connectLChild(__grand , __child->_rChild);
+ connectLChild(__child, __parent);
+ connectRChild(__child, __grand );
+ }
+ }else if(__grand->_rChild == __parent){
+ if(__parent->_rChild == __child){
+ connectRChild(__grand , __parent->_lChild);
+ connectRChild(__parent, __child ->_lChild);
+ connectLChild(__child , __parent);
+ connectLChild(__parent, __grand );
+ }else{
+ connectRChild(__grand , __child->_lChild);
+ connectLChild(__parent, __child->_rChild);
+ connectLChild(__child, __grand );
+ connectRChild(__child, __parent);
+ }
+ }
+ sizeUpdate(__grand );
+ sizeUpdate(__parent);
+ sizeUpdate(__child );
+ }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::splay(Node* __node) const{
+ if(__node == NULL){
+ return NULL;
+ }
+ for(Node *parent, *grand, *child = __node; child->_parent != NULL; ){
+ parent = child ->_parent;
+ grand = parent->_parent;
+ if(grand == NULL){
+ rotate(parent, child);
+ break;
+ }else{
+ Node* g_grand = grand->_parent;
+ rotate(grand, parent, child);
+ if(g_grand == NULL){
+ break;
+ }
+ if(g_grand->_lChild == grand) connectLChild(g_grand, child);
+ else connectRChild(g_grand, child);
+ }
+ }
+ return __node;
+ }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::findKey(Node* __node,
+ Key const& __key) const{
+ Node* ret = __node;
+ for(Key offset_sum = 0; __node != NULL; offset_sum += ret->_keyOffset){
+ offsetDown(__node);
+ ret = __node;
+ if(!(__key < offset_sum + __node->_key)){
+ if(!(offset_sum + __node->_key< __key)){
+ break;
+ }
+ __node = __node->_rChild;
+ }else{
+ __node = __node->_lChild;
+ }
+ }
+ return ret;
+ }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::findMinMax(Node* __node,
+ bool minimum) const{
+ Node* ret = __node;
+ while(__node != NULL){
+ offsetDown(__node);
+ ret = __node;
+ __node = (minimum ? __node->_lChild : __node->_rChild);
+ }
+ return ret;
+ }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::findOrder(Node* __node,
+ size_t __order) const{
+ Node* ret = __node;
+ while(__node != NULL){
+ offsetDown(__node);
+ ret = __node;
+ size_t ord = 1 + (__node->_lChild == NULL ? 0 : __node->_lChild->_size);
+ if(ord == __order){
+ return ret;
+ }else if(ord < __order){
+ __node = __node->_rChild;
+ __order -= ord;
+ }else{
+ __node = __node->_lChild;
+ }
+ }
+ return ret;
+ }
+ template<class Key, class Value>
+ inline void SplayTree<Key, Value>::split(Node* __root,
+ Node** __left, Node** __right){
+ if(__root == NULL){
+ *__left = NULL;
+ *__right = NULL;
+ return ;
+ }
+ offsetDown(__root);
+ *__left = __root;
+ *__right = __root->_rChild;
+ if(*__right != NULL){
+ (*__left )->_rChild = NULL;
+ (*__right)->_parent = NULL;
+ sizeUpdate(*__left);
+ }
+ }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Node* SplayTree<Key, Value>::merge(Node* __left, Node* __right){
+ if(__left == NULL) return __right;
+ if(__right == NULL) return __left ;
+ offsetDown(__left);
+ connectRChild(__left, __right);
+ sizeUpdate(__left);
+ return __left;
+ }
+ template<class Key, class Value>
+ inline void SplayTree<Key, Value>::print(Node* __now, int __depth) const{
+ if(__now == NULL) return ;
+ printf("%*s [%llX]:\tParent=%llX Left=%llX Right=%llX\n",
+ __depth * 2, "",
+ (long long unsigned)__now,
+ (long long unsigned)__now->_parent,
+ (long long unsigned)__now->_lChild,
+ (long long unsigned)__now->_rChild);
+ print(__now->_lChild, __depth + 1);
+ print(__now->_rChild, __depth + 1);
+ }
+ //
+ template<class Key, class Value>
+ inline void SplayTree<Key, Value>::Element::reset(Node* __node){
+ _node = __node;
+ delete _entry;
+ if(__node == NULL){
+ _entry = NULL;
+ }else{
+ _entry = new Entry(__node->_key, __node->_value);
+ }
+ }
+ template<class Key, class Value>
+ inline SplayTree<Key, Value>::Element::Element():
+ _entry(NULL),
+ _node(NULL){ }
+ template<class Key, class Value>
+ inline SplayTree<Key, Value>::Element::Element(Node* __node):
+ _entry(NULL),
+ _node(NULL){ reset(__node); }
+ template<class Key, class Value>
+ inline SplayTree<Key, Value>::Element::Element(Element const& __element2):
+ _entry(NULL),
+ _node(NULL){ reset(__element2._node); }
+ template<class Key, class Value>
+ inline SplayTree<Key, Value>::Element::~Element(){ delete _entry; }
+ //
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Element&
+ SplayTree<Key, Value>::Element::operator=(Element const& __e2){
+ reset(__e2._node);
+ return *this;
+ }
+ //
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Element::Entry* SplayTree<Key, Value>::Element::operator->(){ return _entry; }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Element::Entry& SplayTree<Key, Value>::Element::operator*(){ return *_entry; }
+ //
+ template<class Key, class Value>
+ inline bool
+ SplayTree<Key, Value>::Element::operator==(Element const& __e2) const{
+ return (_node == __e2._node);
+ }
+ template<class Key, class Value>
+ inline bool
+ SplayTree<Key, Value>::Element::operator!=(Element const& __e2) const{
+ return (_node != __e2._node);
+ }
+ //
+ template<class Key, class Value>
+ inline SplayTree<Key, Value>::SplayTree():
+ _root(NULL){ }
+ template<class Key, class Value>
+ inline SplayTree<Key, Value>::SplayTree(SplayTree const& __tree2):
+ _root(NULL){
+ _root = dup(__tree2._root);
+ }
+ template<class Key, class Value>
+ inline SplayTree<Key, Value>::~SplayTree(){
+ clear(_root);
+ }
+ template<class Key, class Value>
+ inline SplayTree<Key, Value>& SplayTree<Key, Value>::operator=(SplayTree const& __tree2){
+ clear(_root);
+ _root = dup(__tree2._root);
+ return *this;
+ }
+ //
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::lowerBound(Key const& __key) const{
+ SplayTree* me = (SplayTree*)this;
+ me->_root = splay(findKey(me->_root, __key));
+ me->_root->_parent = NULL;
+ if(_root == NULL || !(_root->_key < __key)){
+ return Element(_root);
+ }
+ if(_root->_rChild == NULL){
+ return NULL;
+ }
+ me->_root = splay(findMinMax(me->_root->_rChild, true));
+ me->_root->_parent = NULL;
+ return Element(_root);
+ }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::upperBound(Key const& __key) const{
+ SplayTree* me = (SplayTree*)this;
+ me->_root = splay(findKey(me->_root, __key));
+ me->_root->_parent = NULL;
+ if(_root == NULL || __key < _root->_key){
+ return Element(_root);
+ }
+ if(_root->_rChild == NULL){
+ return NULL;
+ }
+ me->_root = splay(findMinMax(me->_root->_rChild, true));
+ me->_root->_parent = NULL;
+ return Element(_root);
+ }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::rLowerBound(Key const& __key) const{
+ SplayTree* me = (SplayTree*)this;
+ me->_root = splay(findKey(me->_root, __key));
+ me->_root->_parent = NULL;
+ if(_root == NULL || !(__key < _root->_key)){
+ return Element(_root);
+ }
+ if(_root->_lChild == NULL){
+ return NULL;
+ }
+ me->_root = splay(findMinMax(me->_root->_lChild, false));
+ me->_root->_parent = NULL;
+ return Element(_root);
+ }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::rUpperBound(Key const& __key) const{
+ SplayTree* me = (SplayTree*)this;
+ me->_root = splay(findKey(me->_root, __key));
+ me->_root->_parent = NULL;
+ if(_root == NULL || _root->_key < __key){
+ return Element(_root);
+ }
+ if(_root->_lChild == NULL){
+ return NULL;
+ }
+ me->_root = splay(findMinMax(me->_root->_lChild, false));
+ me->_root->_parent = NULL;
+ return Element(_root);
+ }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::find(Key const& __key) const{
+ SplayTree* me = (SplayTree*)this;
+ me->_root = splay(findKey(me->_root, __key));
+ me->_root->_parent = NULL;
+ if(_root != NULL && _root->_key == __key){
+ return Element(_root);
+ }
+ return Element(NULL);
+ }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::order(size_t __order) const{
+ SplayTree* me = (SplayTree*)this;
+ me->_root = splay(findOrder(me->_root, __order + 1));
+ me->_root->_parent = NULL;
+ return Element(_root);
+ }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::first() const{
+ SplayTree* me = (SplayTree*)this;
+ me->_root = splay(findMinMax(me->_root, true));
+ me->_root->_parent = NULL;
+ return Element(_root);
+ }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::last() const{
+ SplayTree* me = (SplayTree*)this;
+ me->_root = splay(findMinMax(me->_root, false));
+ me->_root->_parent = NULL;
+ return Element(_root);
+ }
+ template<class Key, class Value>
+ inline typename SplayTree<Key, Value>::Element SplayTree<Key, Value>::end() const{ return Element(NULL); }
+ template<class Key, class Value>
+ inline size_t SplayTree<Key, Value>::size() const{
+ return (_root == NULL ? 0 : _root->_size);
+ }
+ template<class Key, class Value>
+ inline bool SplayTree<Key, Value>::empty() const{ return (size() == 0); }
+ //
+ template<class Key, class Value>
+ inline void SplayTree<Key, Value>::clear(){
+ clear(_root);
+ _root = NULL;
+ }
+ template<class Key, class Value>
+ inline void SplayTree<Key, Value>::keyOffset(Key const& __delta){
+ if(_root != NULL){
+ offsetAdd(_root, __delta);
+ }
+ }
+ template<class Key, class Value>
+ inline bool SplayTree<Key, Value>::insert(Key const& __key,
+ Value const& __value){
+ if(_root == NULL){
+ _root = new Node(__key, __value);
+ return true;
+ }
+ Node* parent = findKey(_root, __key);
+ Node* new_node;
+ if(parent->_key < __key){
+ connectRChild(parent, new_node = new Node(__key, __value));
+ }else if(__key < parent->_key){
+ connectLChild(parent, new_node = new Node(__key, __value));
+ }else{
+ _root = splay(parent);
+ _root->_parent = NULL;
+ return false;
+ }
+ _root = splay(new_node);
+ _root->_parent = NULL;
+ return true;
+ }
+ template<class Key, class Value>
+ inline bool SplayTree<Key, Value>::erase(Key const& __key){
+ if(_root == NULL){
+ return false;
+ }
+ Node* body = findKey(_root, __key);
+ if(body->_key < __key || __key < body->_key){
+ return false;
+ }
+ Node* ghost;
+ if(body->_rChild == NULL){
+ ghost = body->_lChild;
+ }else{
+ ghost = findMinMax(body->_rChild, true);
+ connectLChild(ghost, body->_lChild);
+ if(ghost != body->_rChild){
+ connectLChild(ghost->_parent, ghost->_lChild);
+ connectLChild(ghost, body->_rChild);
+ }
+ }
+ if(body->_parent != NULL && body->_parent->_lChild == body){
+ connectLChild(body->_parent, ghost);
+ }else{
+ connectRChild(body->_parent, ghost);
+ }
+ _root = splay(ghost != NULL ? ghost : body->_parent);
+ _root->_parent = NULL;
+ return true;
+ }
+ template<class Key, class Value>
+ inline Value& SplayTree<Key, Value>::operator[](Key const& __key){
+ if(find(__key) == end()){
+ insert(__key, Value());
+ }
+ return find(__key)->second;
+ }
+ template<class Key, class Value>
+ inline void SplayTree<Key, Value>::splitOut(Key const& __upper_bound,
+ SplayTree* __right){
+ __right->clear();
+ rLowerBound(__upper_bound);
+ split(_root, &_root, &(__right->_root));
+ }
+ template<class Key, class Value>
+ inline bool SplayTree<Key, Value>::mergeAfter(SplayTree* __tree2){
+ if(_root == NULL || __tree2->_root == NULL ||
+ last()->first < __tree2->first()->first){
+ _root = merge(_root, __tree2->_root);
+ __tree2->_root = NULL;
+ return true;
+ }
+ return false;
+ }
+ template<class Key, class Value>
+ inline bool SplayTree<Key, Value>::merge(SplayTree* __tree2){
+ if(_root == NULL || __tree2->_root == NULL){
+ _root = merge(_root, __tree2->_root);
+ }else{
+ if(last()->first < __tree2->first()->first){
+ _root = merge(_root, __tree2->_root);
+ __tree2->_root = NULL;
+ }else if(__tree2->last()->first < first()->first){
+ _root = merge(__tree2->_root, _root);
+ }else{
+ return false;
+ }
+ }
+ __tree2->_root = NULL;
+ return true;
+ }
+ template<class Key, class Value>
+ inline void SplayTree<Key, Value>::print() const{
+ print(_root, 0);
+ }
+ template<class Key, class Value>
+ inline void SplayTree<Key, Value>::moveTo(SplayTree* __tree2){
+ __tree2->clear();
+ __tree2->_root = _root;
+ _root = NULL;
+ }
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-28 00:18:41 +0800