aboutsummaryrefslogtreecommitdiffstats
path: root/meowpp/dsa
diff options
context:
space:
mode:
Diffstat (limited to 'meowpp/dsa')
-rw-r--r--meowpp/dsa/BinaryIndexTree.h10
-rw-r--r--meowpp/dsa/BinaryIndexTree.hpp7
-rw-r--r--meowpp/dsa/DisjointSet.h8
-rw-r--r--meowpp/dsa/DisjointSet.hpp3
-rw-r--r--meowpp/dsa/KD_Tree.h10
-rw-r--r--meowpp/dsa/KD_Tree.hpp8
-rw-r--r--meowpp/dsa/MergeableHeap.h6
-rw-r--r--meowpp/dsa/MergeableHeap.hpp4
-rw-r--r--meowpp/dsa/SegmentTree.h32
-rw-r--r--meowpp/dsa/SegmentTree.hpp8
-rw-r--r--meowpp/dsa/SplayTree.h13
-rw-r--r--meowpp/dsa/SplayTree.hpp25
-rw-r--r--meowpp/dsa/SplayTree_Range.h15
-rw-r--r--meowpp/dsa/SplayTree_Range.hpp28
-rw-r--r--meowpp/dsa/VP_Tree.h17
-rw-r--r--meowpp/dsa/VP_Tree.hpp38
16 files changed, 94 insertions, 138 deletions
diff --git a/meowpp/dsa/BinaryIndexTree.h b/meowpp/dsa/BinaryIndexTree.h
index 4b1b23a..36f24d7 100644
--- a/meowpp/dsa/BinaryIndexTree.h
+++ b/meowpp/dsa/BinaryIndexTree.h
@@ -1,5 +1,9 @@
-#ifndef __BinaryIndexTree_H__
-#define __BinaryIndexTree_H__
+#ifndef dsa_BinaryIndexTree_H__
+#define dsa_BinaryIndexTree_H__
+
+#include <cstdlib>
+
+#include <vector>
namespace meow{
//#
@@ -65,5 +69,5 @@ namespace meow{
#include "BinaryIndexTree.hpp"
-#endif // BinaryIndexTree_H__
+#endif // dsa_BinaryIndexTree_H__
diff --git a/meowpp/dsa/BinaryIndexTree.hpp b/meowpp/dsa/BinaryIndexTree.hpp
index e7e146a..f84a931 100644
--- a/meowpp/dsa/BinaryIndexTree.hpp
+++ b/meowpp/dsa/BinaryIndexTree.hpp
@@ -1,3 +1,10 @@
+#include "BinaryIndexTree.h"
+
+#include <cstdlib>
+
+#include <vector>
+#include <algorithm>
+
namespace meow{
template<class Value>
diff --git a/meowpp/dsa/DisjointSet.h b/meowpp/dsa/DisjointSet.h
index b918adb..bb777e1 100644
--- a/meowpp/dsa/DisjointSet.h
+++ b/meowpp/dsa/DisjointSet.h
@@ -1,9 +1,9 @@
-#ifndef DisjointSet_H__
-#define DisjointSet_H__
+#ifndef dsa_DisjointSet_H__
+#define dsa_DisjointSet_H__
+#include <cstdlib>
#include <vector>
-#include <cstdlib>
namespace meow{
//#
@@ -70,4 +70,4 @@ namespace meow{
#include "DisjointSet.hpp"
-#endif // DisjointSet_H__
+#endif // dsa_DisjointSet_H__
diff --git a/meowpp/dsa/DisjointSet.hpp b/meowpp/dsa/DisjointSet.hpp
index 3b66626..98b2b98 100644
--- a/meowpp/dsa/DisjointSet.hpp
+++ b/meowpp/dsa/DisjointSet.hpp
@@ -1,3 +1,6 @@
+#include "DisjointSet.h"
+
+
#include <vector>
#include <cstdlib>
diff --git a/meowpp/dsa/KD_Tree.h b/meowpp/dsa/KD_Tree.h
index 216d9c9..b4e579c 100644
--- a/meowpp/dsa/KD_Tree.h
+++ b/meowpp/dsa/KD_Tree.h
@@ -1,10 +1,10 @@
-#ifndef KD_Tree_H__
-#define KD_Tree_H__
+#ifndef dsa_KD_Tree_H__
+#define dsa_KD_Tree_H__
-#include <vector>
#include <cstdlib>
+
+#include <vector>
#include <queue>
-#include "../utility.h"
namespace meow{
//#
@@ -159,4 +159,4 @@ namespace meow{
#include "KD_Tree.hpp"
-#endif // KD_Tree_H__
+#endif // dsa_KD_Tree_H__
diff --git a/meowpp/dsa/KD_Tree.hpp b/meowpp/dsa/KD_Tree.hpp
index 7fea6da..735d4af 100644
--- a/meowpp/dsa/KD_Tree.hpp
+++ b/meowpp/dsa/KD_Tree.hpp
@@ -1,8 +1,14 @@
+#include "KD_Tree.h"
+
+
+#include "../utility.h"
+#include "../math/utility.h"
+
#include <cstdlib>
+
#include <vector>
#include <algorithm>
#include <queue>
-#include "../utility.h"
namespace meow{
////////////////////////////////////////////////////////////////////
diff --git a/meowpp/dsa/MergeableHeap.h b/meowpp/dsa/MergeableHeap.h
index ddcd8a5..0ddb100 100644
--- a/meowpp/dsa/MergeableHeap.h
+++ b/meowpp/dsa/MergeableHeap.h
@@ -1,5 +1,5 @@
-#ifndef Heap_H__
-#define Heap_H__
+#ifndef dsa_MergeableHeap_H__
+#define dsa_MergeableHeap_H__
#include <cstdlib>
@@ -105,4 +105,4 @@ namespace meow{
#include "MergeableHeap.hpp"
-#endif // Heap_H__
+#endif // dsa_MergeableHeap_H__
diff --git a/meowpp/dsa/MergeableHeap.hpp b/meowpp/dsa/MergeableHeap.hpp
index e7f5978..1470ac3 100644
--- a/meowpp/dsa/MergeableHeap.hpp
+++ b/meowpp/dsa/MergeableHeap.hpp
@@ -1,5 +1,9 @@
+#include "MergeableHeap.h"
+
#include <cstdlib>
+#include <algorithm>
+
namespace meow{
//////////////////////////////////////////////////////////
// **# MergeableHeap--Node-- constructor #** //
diff --git a/meowpp/dsa/SegmentTree.h b/meowpp/dsa/SegmentTree.h
index 4bed51b..52d5a6f 100644
--- a/meowpp/dsa/SegmentTree.h
+++ b/meowpp/dsa/SegmentTree.h
@@ -1,5 +1,9 @@
-#ifndef SegmentTree_H__
-#define SegmentTree_H__
+#ifndef dsa_SegmentTree_H__
+#define dsa_SegmentTree_H__
+
+#include <cstdlib>
+
+#include <vector>
namespace meow{
//#
@@ -83,28 +87,8 @@ namespace meow{
//#|將區間 `[first,last]` 全部都加上 `delta`
void offset (ssize_t __first, ssize_t __last, Value const& __delta);
- //
- void print(){
- for(int i = 0; i < _size; i++){
- query(i, i);
- }
- printf("\n");
- for(int depth = 0, count = 1, size = _size, id = 0;
- size > 0;
- depth++, count *= 2, size /= 2){
- for(int j = 0; j < count; j++, id++){
- printf("[%3d%c%3d%*s]",
- _nodes[id]._value.value,
- _nodes[id]._sameFlag ? 's' : ' ',
- _nodes[id]._offset.value,
- size * 9 - 9,
- "");
- }
- printf("\n");
- }
- }
- //#|=====================================================================
+ //#|=====================================================================
};
//#
//# '''
@@ -113,4 +97,4 @@ namespace meow{
#include "SegmentTree.hpp"
-#endif
+#endif // dsa_SegmentTree_H__
diff --git a/meowpp/dsa/SegmentTree.hpp b/meowpp/dsa/SegmentTree.hpp
index a2b74e8..bdd43fb 100644
--- a/meowpp/dsa/SegmentTree.hpp
+++ b/meowpp/dsa/SegmentTree.hpp
@@ -1,5 +1,11 @@
-#include "../utility.h"
+#include "SegmentTree.h"
+
+#include "../math/utility.h"
+
+#include <cstdlib>
+
+#include <vector>
#include <algorithm>
namespace meow{
diff --git a/meowpp/dsa/SplayTree.h b/meowpp/dsa/SplayTree.h
index 38cbe7f..da451b0 100644
--- a/meowpp/dsa/SplayTree.h
+++ b/meowpp/dsa/SplayTree.h
@@ -1,7 +1,9 @@
-#ifndef SplayTree_h__
-#define SplayTree_h__
+#ifndef dsa_SplayTree_h__
+#define dsa_SplayTree_h__
-#include "../utility.h"
+#include <cstdlib>
+
+#include <utility>
namespace meow{
//#
@@ -53,8 +55,6 @@ namespace meow{
//
void split(Node* __root, Node** __left, Node** __right);
Node* merge( Node* __left, Node* __right);
- //
- void print(Node* __now, int __depth) const;
public:
//#==== Custom Type Definitions
//#
@@ -215,7 +215,6 @@ namespace meow{
bool merge(SplayTree* __tree2);
- void print() const;
//#|=====================================================================
};
//#
@@ -233,4 +232,4 @@ namespace meow{
#include "SplayTree.hpp"
-#endif // SplayTree_h__
+#endif // dsa_SplayTree_h__
diff --git a/meowpp/dsa/SplayTree.hpp b/meowpp/dsa/SplayTree.hpp
index de08f63..3b08c14 100644
--- a/meowpp/dsa/SplayTree.hpp
+++ b/meowpp/dsa/SplayTree.hpp
@@ -1,3 +1,9 @@
+#include "SplayTree.h"
+
+
+#include <cstdlib>
+
+#include <utility>
namespace meow{
///////////////////////////// **# Node #** /////////////////////////
@@ -161,20 +167,6 @@ namespace meow{
__left->syncUp();
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]:(%lu)\tParent=%llX Left=%llX Right=%llX\n",
- __depth * 2, "",
- (long long unsigned)__now,
- __now->_size,
- (long long unsigned)__now->_parent,
- (long long unsigned)__now->_child[0],
- (long long unsigned)__now->_child[1]);
- print(__now->_child[0], __depth + 1);
- print(__now->_child[1], __depth + 1);
- }
///////////////////////// **# Element ##* //////////////////////////
template<class Key, class Value>
inline void SplayTree<Key, Value>::Element::reset(Node* __node){
@@ -441,10 +433,5 @@ namespace meow{
__tree2->_root = NULL;
return true;
}
- template<class Key, class Value>
- inline void
- SplayTree<Key, Value>::print() const{
- print(_root, 0);
- }
}
diff --git a/meowpp/dsa/SplayTree_Range.h b/meowpp/dsa/SplayTree_Range.h
index e5124c8..0abdc24 100644
--- a/meowpp/dsa/SplayTree_Range.h
+++ b/meowpp/dsa/SplayTree_Range.h
@@ -1,7 +1,11 @@
-#ifndef SplayTree_Range_h__
-#define SplayTree_Range_h__
+#ifndef dsa_SplayTree_Range_h__
+#define dsa_SplayTree_Range_h__
-#include "../utility.h"
+#include <cstdlib>
+
+#include <utility>
+
+#include "../math/utility.h"
namespace meow{
//#
@@ -57,8 +61,6 @@ namespace meow{
//
void split(Node* __root, Node** __left, Node** __right);
Node* merge( Node* __left, Node* __right);
- //
- void print(Node* __now, int __depth) const;
public:
//#==== Custom Type Definitions
//#
@@ -239,7 +241,6 @@ namespace meow{
bool merge(SplayTree_Range* __tree2);
- void print() const;
//#|=====================================================================
};
//#
@@ -257,4 +258,4 @@ namespace meow{
#include "SplayTree_Range.hpp"
-#endif // SplayTree_Range_h__
+#endif // dsa_SplayTree_Range_h__
diff --git a/meowpp/dsa/SplayTree_Range.hpp b/meowpp/dsa/SplayTree_Range.hpp
index 1f216cf..def7ef7 100644
--- a/meowpp/dsa/SplayTree_Range.hpp
+++ b/meowpp/dsa/SplayTree_Range.hpp
@@ -1,3 +1,11 @@
+#include "SplayTree_Range.h"
+
+
+#include <cstdlib>
+
+#include <utility>
+
+#include "../math/utility.h"
namespace meow{
///////////////////////////// **# Node #** /////////////////////////
@@ -192,21 +200,6 @@ namespace meow{
__left->syncUp();
return __left;
}
- //
- template<class Key, class Value>
- inline void SplayTree_Range<Key, Value>::print(Node* __now,
- int __depth) const{
- if(__now == NULL) return ;
- printf("%*s [%llX]:(%lu)\tParent=%llX Left=%llX Right=%llX\n",
- __depth * 2, "",
- (long long unsigned)__now,
- __now->_size,
- (long long unsigned)__now->_parent,
- (long long unsigned)__now->_child[0],
- (long long unsigned)__now->_child[1]);
- print(__now->_child[0], __depth + 1);
- print(__now->_child[1], __depth + 1);
- }
///////////////////////// **# Element ##* //////////////////////////
template<class Key, class Value>
inline void SplayTree_Range<Key, Value>::Element::reset(Node* __node){
@@ -509,10 +502,5 @@ namespace meow{
__tree2->_root = NULL;
return true;
}
- template<class Key, class Value>
- inline void
- SplayTree_Range<Key, Value>::print() const{
- print(_root, 0);
- }
}
diff --git a/meowpp/dsa/VP_Tree.h b/meowpp/dsa/VP_Tree.h
index 1877b74..e2daa28 100644
--- a/meowpp/dsa/VP_Tree.h
+++ b/meowpp/dsa/VP_Tree.h
@@ -1,11 +1,13 @@
-#ifndef VP_Tree_H__
-#define VP_Tree_H__
+#ifndef dsa_VP_Tree_H__
+#define dsa_VP_Tree_H__
+
+#include "../math/utility.h"
+
+#include <cstdlib>
#include <list>
#include <vector>
-#include <cstdlib>
#include <queue>
-#include "../utility.h"
namespace meow{
//#
@@ -90,9 +92,6 @@ namespace meow{
Answers* __out) const;
void clear(Node* __root);
Node* dup(Node* __root);
- //
- void print(Node* __node, int depth = 1,
- Node* __parent = NULL, bool __near = true) const;
public:
VP_Tree();
VP_Tree(VP_Tree const& __tree2);
@@ -152,8 +151,6 @@ namespace meow{
//#|=====================================================================
-
- void print() const;
};
//#
//#[NOTE]
@@ -170,4 +167,4 @@ namespace meow{
#include "VP_Tree.hpp"
-#endif // VP_Tree_H__
+#endif // dsa_VP_Tree_H__
diff --git a/meowpp/dsa/VP_Tree.hpp b/meowpp/dsa/VP_Tree.hpp
index ba97ad7..2026050 100644
--- a/meowpp/dsa/VP_Tree.hpp
+++ b/meowpp/dsa/VP_Tree.hpp
@@ -1,7 +1,10 @@
+#include "VP_Tree.h"
#include <cstdlib>
+
#include <algorithm>
-#include "../utility.h"
+#include <stack>
+#include "../math/utility.h"
namespace meow{
///////////////////// **# Node #** ///////////////////////
@@ -51,7 +54,6 @@ namespace meow{
Scalar const& __b2,
Scalar const& __c2) const{
// test if sqrt(__a2) +- sqrt(|__b2|) <= sqrt(__c2)
- //printf("abc = %lld %lld %lld\n", __a2, __b2, __c2);
if(__b2 < 0){
return -distanceCompare(__c2, -__b2, __a2);
}
@@ -170,29 +172,6 @@ namespace meow{
ret->_farChild = dup(__root->_farChild );
return ret;
}
- /////////////////////// **# print #** ////////////////////
- template<class Vector, class Scalar>
- inline void
- VP_Tree<Vector, Scalar>::print(Node* __node, int depth,
- Node* __parent, bool __near) const{
- if(__node == NULL) return ;
- printf("%*s%c)Me<%lld,%lld>, rad2 = %7lld",
- depth * 2, "",
- __near ? 'N' : 'F',
- _vectors[__node->_index][0], _vectors[__node->_index][1],
- __node->_threshold);
- if(__parent != NULL){
- printf(" ---<%lld,%lld>:: %lld\n",
- _vectors[__parent->_index][0],
- _vectors[__parent->_index][1],
- distance2(_vectors[__parent->_index],
- _vectors[__node ->_index]));
- }else{
- printf("\n");
- }
- print(__node->_nearChild, depth + 1, __node, true );
- print(__node->_farChild , depth + 1, __node, false);
- }
///////// **# construre/destructure/copy oper #** ////////
template<class Vector, class Scalar>
inline
@@ -293,13 +272,4 @@ namespace meow{
_dimension = std::max((size_t)1, __dimension);
return _dimension;
}
-
- /////////////////////// **# print #** ////////////////////
- template<class Vector, class Scalar>
- void inline
- VP_Tree<Vector, Scalar>::print() const{
- printf("\nsize = %lu, dimension = %lu\n", _vectors.size(), _dimension);
- print(_root, 1);
- printf("\n\n");
- }
};
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-05 08:45:30 +0800