From d5052f1c296dddf51b3e83d59bf3e3c1952cb2d0 Mon Sep 17 00:00:00 2001 From: cathook Date: Sun, 1 Jun 2014 13:56:57 +0800 Subject: big chnage --- doc/html/MergeableHeap_8h_source.html | 193 ++++++++++++++++++++++++++++++++++ 1 file changed, 193 insertions(+) create mode 100644 doc/html/MergeableHeap_8h_source.html (limited to 'doc/html/MergeableHeap_8h_source.html') diff --git a/doc/html/MergeableHeap_8h_source.html b/doc/html/MergeableHeap_8h_source.html new file mode 100644 index 0000000..d397f82 --- /dev/null +++ b/doc/html/MergeableHeap_8h_source.html @@ -0,0 +1,193 @@ + + + + + + + +Templates -- Meow: meowpp/dsa/MergeableHeap.h Source File + + + + + + + + + + + +
+
+ + + + + + + +
+
Templates -- Meow +  1.1.2 +
+
不能,也不應該先編譯成obj-file的templates
+
+
+ + +
+
+ +
+
+
+ +
+
+
+
MergeableHeap.h
+
+
+Go to the documentation of this file.
1 #ifndef dsa_MergeableHeap_H__
+
2 #define dsa_MergeableHeap_H__
+
3 
+
4 #include <cstdlib>
+
5 #include <algorithm>
+
6 
+
7 namespace meow {
+
8 
+
29 template<class Element>
+
30 class MergeableHeap { // maximum-heap
+
31 private:
+
32  struct Node {
+
33  Element value_;
+
34  Node* lChild_;
+
35  Node* rChild_;
+
36  size_t weight_;
+
37  Node(Element const& value):
+
38  value_(value), lChild_(NULL), rChild_(NULL), weight_(1){
+
39  }
+
40  };
+
41 
+
42  Node* root_;
+
43 
+
44  void clear(Node* node) {
+
45  if (node != NULL) {
+
46  clear(node->lChild_);
+
47  clear(node->rChild_);
+
48  delete node;
+
49  }
+
50  }
+
51  Node* dup(Node* node) {
+
52  if (node == NULL) return NULL;
+
53  Node* ret = new Node(node->value_);
+
54  ret->lChild_ = dup(node->lChild_);
+
55  ret->rChild_ = dup(node->rChild_);
+
56  ret->weight_ = 1;
+
57  ret->weight_ += (ret->lChild_ == NULL ? 0 : ret->lChild_->weight_);
+
58  ret->weight_ += (ret->rChild_ == NULL ? 0 : ret->rChild_->weight_);
+
59  return ret;
+
60  }
+
61  Node* merge(Node* left, Node* right) {
+
62  if (left == NULL) return right;
+
63  if (right == NULL) return left;
+
64  if (left->value_ < right->value_) {
+
65  std::swap(left, right);
+
66  }
+
67  left->rChild_ = merge(left->rChild_, right);
+
68  size_t lw = (left->lChild_ == NULL ? 0 : left->lChild_->weight_);
+
69  size_t rw = (left->rChild_ == NULL ? 0 : left->rChild_->weight_);
+
70  if (lw < rw) {
+
71  std::swap(left->lChild_, left->rChild_);
+
72  }
+
73  left->weight_ = 1 + lw + rw;
+
74  return left;
+
75  }
+
76 public:
+
78  MergeableHeap(): root_(NULL){
+
79  }
+
80 
+
82  MergeableHeap(MergeableHeap const& heap2): root_(dup(heap2.root_)) {
+
83  }
+
84 
+
86  ~MergeableHeap(){
+
87  clear(root_);
+
88  }
+
89 
+
91  MergeableHeap& copyFrom(MergeableHeap const& heap2) {
+
92  delete root_;
+
93  root_ = dup(heap2.root_);
+
94  return *this;
+
95  }
+
96 
+
100  void moveTo(MergeableHeap* heap2){
+
101  heap2->clear();
+
102  heap2->root_ = root_;
+
103  root_ = NULL;
+
104  }
+
105 
+
109  Element const& top() const {
+
110  return root_->value_;
+
111  }
+
112 
+
116  size_t size() const {
+
117  return (root_ == NULL ? 0 : root_->weight_);
+
118  }
+
119 
+
123  bool empty() const {
+
124  return (size() == 0);
+
125  }
+
126 
+
130  void push(Element const& value) {
+
131  root_ = merge(root_, new Node(value));
+
132  }
+
133 
+
137  void pop() {
+
138  Node* l = root_->lChild_;
+
139  Node* r = root_->rChild_;
+
140  delete root_;
+
141  root_ = merge(l, r);
+
142  }
+
143 
+
147  void clear() {
+
148  clear(root_);
+
149  root_ = NULL;
+
150  }
+
151 
+
155  void merge(MergeableHeap* heap2) {
+
156  root_ = merge(root_, heap2->root_);
+
157  heap2->root_ = NULL;
+
158  }
+
159 
+
161  MergeableHeap& operator=(MergeableHeap const& heap2) {
+
162  return copyFrom(heap2);
+
163  }
+
164 };
+
165 
+
166 }
+
167 
+
168 #endif // dsa_MergeableHeap_H__
+
+
+ + + + + -- cgit