diff options
| author | cathook <b01902109@csie.ntu.edu.tw> | 2014-05-02 04:10:56 +0800 |
|---|---|---|
| committer | cathook <b01902109@csie.ntu.edu.tw> | 2014-05-02 04:10:56 +0800 |
| commit | 33d419e4d54d969798af80f05e05f0c447a99594 (patch) | |
| tree | c78355a2d334e34df865aca865dbb4864a85820c /meowpp.test | |
| parent | d2d7a49563a8f04bd07264a4a989d5656313d375 (diff) | |
| download | meow-33d419e4d54d969798af80f05e05f0c447a99594.tar meow-33d419e4d54d969798af80f05e05f0c447a99594.tar.gz meow-33d419e4d54d969798af80f05e05f0c447a99594.tar.bz2 meow-33d419e4d54d969798af80f05e05f0c447a99594.tar.lz meow-33d419e4d54d969798af80f05e05f0c447a99594.tar.xz meow-33d419e4d54d969798af80f05e05f0c447a99594.tar.zst meow-33d419e4d54d969798af80f05e05f0c447a99594.zip | |
big change about dir structure
Diffstat (limited to 'meowpp.test')
28 files changed, 2470 insertions, 0 deletions
diff --git a/meowpp.test/.gitignore b/meowpp.test/.gitignore new file mode 100644 index 0000000..37272fe --- /dev/null +++ b/meowpp.test/.gitignore @@ -0,0 +1,2 @@ +obj/* +bin/* diff --git a/meowpp.test/GNUmakefile b/meowpp.test/GNUmakefile new file mode 120000 index 0000000..b62d958 --- /dev/null +++ b/meowpp.test/GNUmakefile @@ -0,0 +1 @@ +../GNUmakefile/GNUmakefile
\ No newline at end of file diff --git a/meowpp.test/GNUmakefile.dependency.bash b/meowpp.test/GNUmakefile.dependency.bash new file mode 120000 index 0000000..c2558c7 --- /dev/null +++ b/meowpp.test/GNUmakefile.dependency.bash @@ -0,0 +1 @@ +../GNUmakefile/GNUmakefile.dependency.bash
\ No newline at end of file diff --git a/meowpp.test/GNUmakefile.targets b/meowpp.test/GNUmakefile.targets new file mode 100644 index 0000000..1fba995 --- /dev/null +++ b/meowpp.test/GNUmakefile.targets @@ -0,0 +1,8 @@ + +TARGETS := $(TARGETS) $(BIN)/dsa +dsa_OBJS := $(OBJ)/BinaryIndexTree.o $(OBJ)/DisjointSet.o $(OBJ)/KD_Tree.o $(OBJ)/MergeableHeap.o $(OBJ)/SegmentTree.o $(OBJ)/SplayTree.o $(OBJ)/SplayTree_Range.o $(OBJ)/VP_Tree.o +dsa_LIBS := +$(BIN)/dsa: $(OBJ)/dsa.o $(dsa_OBJS) + @echo Target: $@... + @$(CXX) $^ $(CXXFLAGS) `pkg-config --cflags --libs $(dsa_LIBS) 2>/dev/null` -o $@ + diff --git a/meowpp.test/dep/BinaryIndexTree.d b/meowpp.test/dep/BinaryIndexTree.d new file mode 100644 index 0000000..9d65fb9 --- /dev/null +++ b/meowpp.test/dep/BinaryIndexTree.d @@ -0,0 +1,33 @@ +dep/BinaryIndexTree.d:: src/BinaryIndexTree.cpp inc/meowpp/dsa/BinaryIndexTree.h inc/meowpp/dsa/BinaryIndexTree.hpp inc/meowpp/dsa/BinaryIndexTree.h inc/meowpp/utility.h inc/meowpp/utility.hpp inc/meowpp/utility.h inc/meowpp.h inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/../math/Matrix.hpp inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/Vector2D.hpp inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/utility.h inc/meowpp/geo/../math/utility.hpp inc/meowpp/geo/../math/utility.h inc/meowpp/geo/Vector3D.h inc/meowpp/geo/Vector3D.hpp inc/meowpp/geo/Vector3D.h inc/meowpp/Usage.h inc/meowpp/Usage.hpp inc/meowpp/Usage.h inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/Properties.hpp inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/ObjSelector.h + $(DEPENDENCY_CREATER) "`$(CXX_DEP) $(CXXFLAGS) $<`" $@ + + +src/BinaryIndexTree.cpp::; +inc/meowpp/dsa/BinaryIndexTree.h::; +inc/meowpp/dsa/BinaryIndexTree.hpp::; +inc/meowpp/dsa/BinaryIndexTree.h::; +inc/meowpp/utility.h::; +inc/meowpp/utility.hpp::; +inc/meowpp/utility.h::; +inc/meowpp.h::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/../math/Matrix.hpp::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/Vector2D.hpp::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/../math/utility.hpp::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/geo/Vector3D.hpp::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/Usage.h::; +inc/meowpp/Usage.hpp::; +inc/meowpp/Usage.h::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/Properties.hpp::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/ObjSelector.h::; diff --git a/meowpp.test/dep/Colors.d b/meowpp.test/dep/Colors.d new file mode 100644 index 0000000..eef06e4 --- /dev/null +++ b/meowpp.test/dep/Colors.d @@ -0,0 +1,47 @@ +dep/Colors.d:: src/Colors.cpp inc/meowpp/colors/RGB.h inc/meowpp/colors/../geo/Vector3D.h inc/meowpp/colors/../geo/../math/Matrix.h inc/meowpp/colors/../geo/../math/Matrix.hpp inc/meowpp/colors/../geo/../math/Matrix.h inc/meowpp/colors/../geo/Vector3D.hpp inc/meowpp/colors/../geo/Vector3D.h inc/meowpp/colors/../geo/../math/utility.h inc/meowpp/colors/../geo/../math/utility.hpp inc/meowpp/colors/../geo/../math/utility.h inc/meowpp/colors/RGB.hpp inc/meowpp/colors/RGB.h inc/meowpp/colors/../math/utility.h inc/meowpp/colors/../math/Matrix.h inc/meowpp/colors/YUV.h inc/meowpp/colors/YUV.hpp inc/meowpp/colors/YUV.h inc/meowpp/colors/HSL.h inc/meowpp/colors/HSL.hpp inc/meowpp/colors/HSL.h inc/meowpp/colors/HSV.h inc/meowpp/colors/HSV.hpp inc/meowpp/colors/HSV.h inc/meowpp/utility.h inc/meowpp/utility.hpp inc/meowpp/utility.h inc/meowpp.h inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/Vector2D.hpp inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/utility.h inc/meowpp/geo/Vector3D.h inc/meowpp/Usage.h inc/meowpp/Usage.hpp inc/meowpp/Usage.h inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/Properties.hpp inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/ObjSelector.h + $(DEPENDENCY_CREATER) "`$(CXX_DEP) $(CXXFLAGS) $<`" $@ + + +src/Colors.cpp::; +inc/meowpp/colors/RGB.h::; +inc/meowpp/colors/../geo/Vector3D.h::; +inc/meowpp/colors/../geo/../math/Matrix.h::; +inc/meowpp/colors/../geo/../math/Matrix.hpp::; +inc/meowpp/colors/../geo/../math/Matrix.h::; +inc/meowpp/colors/../geo/Vector3D.hpp::; +inc/meowpp/colors/../geo/Vector3D.h::; +inc/meowpp/colors/../geo/../math/utility.h::; +inc/meowpp/colors/../geo/../math/utility.hpp::; +inc/meowpp/colors/../geo/../math/utility.h::; +inc/meowpp/colors/RGB.hpp::; +inc/meowpp/colors/RGB.h::; +inc/meowpp/colors/../math/utility.h::; +inc/meowpp/colors/../math/Matrix.h::; +inc/meowpp/colors/YUV.h::; +inc/meowpp/colors/YUV.hpp::; +inc/meowpp/colors/YUV.h::; +inc/meowpp/colors/HSL.h::; +inc/meowpp/colors/HSL.hpp::; +inc/meowpp/colors/HSL.h::; +inc/meowpp/colors/HSV.h::; +inc/meowpp/colors/HSV.hpp::; +inc/meowpp/colors/HSV.h::; +inc/meowpp/utility.h::; +inc/meowpp/utility.hpp::; +inc/meowpp/utility.h::; +inc/meowpp.h::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/Vector2D.hpp::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/Usage.h::; +inc/meowpp/Usage.hpp::; +inc/meowpp/Usage.h::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/Properties.hpp::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/ObjSelector.h::; diff --git a/meowpp.test/dep/DisjointSet.d b/meowpp.test/dep/DisjointSet.d new file mode 100644 index 0000000..c78c810 --- /dev/null +++ b/meowpp.test/dep/DisjointSet.d @@ -0,0 +1,32 @@ +dep/DisjointSet.d:: src/DisjointSet.cpp inc/meowpp/dsa/DisjointSet.h inc/meowpp/dsa/DisjointSet.hpp inc/meowpp/dsa/DisjointSet.h inc/meowpp.h inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/../math/Matrix.hpp inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/Vector2D.hpp inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/utility.h inc/meowpp/geo/../math/utility.hpp inc/meowpp/geo/../math/utility.h inc/meowpp/geo/Vector3D.h inc/meowpp/geo/Vector3D.hpp inc/meowpp/geo/Vector3D.h inc/meowpp/Usage.h inc/meowpp/Usage.hpp inc/meowpp/Usage.h inc/meowpp/utility.h inc/meowpp/utility.hpp inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/Properties.hpp inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/ObjSelector.h + $(DEPENDENCY_CREATER) "`$(CXX_DEP) $(CXXFLAGS) $<`" $@ + + +src/DisjointSet.cpp::; +inc/meowpp/dsa/DisjointSet.h::; +inc/meowpp/dsa/DisjointSet.hpp::; +inc/meowpp/dsa/DisjointSet.h::; +inc/meowpp.h::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/../math/Matrix.hpp::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/Vector2D.hpp::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/../math/utility.hpp::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/geo/Vector3D.hpp::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/Usage.h::; +inc/meowpp/Usage.hpp::; +inc/meowpp/Usage.h::; +inc/meowpp/utility.h::; +inc/meowpp/utility.hpp::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/Properties.hpp::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/ObjSelector.h::; diff --git a/meowpp.test/dep/KD_Tree.d b/meowpp.test/dep/KD_Tree.d new file mode 100644 index 0000000..3200809 --- /dev/null +++ b/meowpp.test/dep/KD_Tree.d @@ -0,0 +1,36 @@ +dep/KD_Tree.d:: src/KD_Tree.cpp inc/meowpp/dsa/KD_Tree.h inc/meowpp/dsa/KD_Tree.hpp inc/meowpp/dsa/KD_Tree.h inc/meowpp/dsa/../utility.h inc/meowpp/dsa/../utility.hpp inc/meowpp/dsa/../utility.h inc/meowpp/dsa/../math/utility.h inc/meowpp/dsa/../math/utility.hpp inc/meowpp/dsa/../math/utility.h inc/meowpp/utility.h inc/meowpp.h inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/../math/Matrix.hpp inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/Vector2D.hpp inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/utility.h inc/meowpp/geo/Vector3D.h inc/meowpp/geo/Vector3D.hpp inc/meowpp/geo/Vector3D.h inc/meowpp/Usage.h inc/meowpp/Usage.hpp inc/meowpp/Usage.h inc/meowpp/utility.h inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/Properties.hpp inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/ObjSelector.h + $(DEPENDENCY_CREATER) "`$(CXX_DEP) $(CXXFLAGS) $<`" $@ + + +src/KD_Tree.cpp::; +inc/meowpp/dsa/KD_Tree.h::; +inc/meowpp/dsa/KD_Tree.hpp::; +inc/meowpp/dsa/KD_Tree.h::; +inc/meowpp/dsa/../utility.h::; +inc/meowpp/dsa/../utility.hpp::; +inc/meowpp/dsa/../utility.h::; +inc/meowpp/dsa/../math/utility.h::; +inc/meowpp/dsa/../math/utility.hpp::; +inc/meowpp/dsa/../math/utility.h::; +inc/meowpp/utility.h::; +inc/meowpp.h::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/../math/Matrix.hpp::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/Vector2D.hpp::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/geo/Vector3D.hpp::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/Usage.h::; +inc/meowpp/Usage.hpp::; +inc/meowpp/Usage.h::; +inc/meowpp/utility.h::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/Properties.hpp::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/ObjSelector.h::; diff --git a/meowpp.test/dep/Matrix.d b/meowpp.test/dep/Matrix.d new file mode 100644 index 0000000..27f106e --- /dev/null +++ b/meowpp.test/dep/Matrix.d @@ -0,0 +1,30 @@ +dep/Matrix.d:: src/Matrix.cpp inc/meowpp/math/Matrix.h inc/meowpp/math/Matrix.hpp inc/meowpp/math/Matrix.h inc/meowpp.h inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/Vector2D.hpp inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/utility.h inc/meowpp/geo/../math/utility.hpp inc/meowpp/geo/../math/utility.h inc/meowpp/geo/Vector3D.h inc/meowpp/geo/Vector3D.hpp inc/meowpp/geo/Vector3D.h inc/meowpp/Usage.h inc/meowpp/Usage.hpp inc/meowpp/Usage.h inc/meowpp/utility.h inc/meowpp/utility.hpp inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/Properties.hpp inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/ObjSelector.h + $(DEPENDENCY_CREATER) "`$(CXX_DEP) $(CXXFLAGS) $<`" $@ + + +src/Matrix.cpp::; +inc/meowpp/math/Matrix.h::; +inc/meowpp/math/Matrix.hpp::; +inc/meowpp/math/Matrix.h::; +inc/meowpp.h::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/Vector2D.hpp::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/../math/utility.hpp::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/geo/Vector3D.hpp::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/Usage.h::; +inc/meowpp/Usage.hpp::; +inc/meowpp/Usage.h::; +inc/meowpp/utility.h::; +inc/meowpp/utility.hpp::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/Properties.hpp::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/ObjSelector.h::; diff --git a/meowpp.test/dep/MergeableHeap.d b/meowpp.test/dep/MergeableHeap.d new file mode 100644 index 0000000..a350868 --- /dev/null +++ b/meowpp.test/dep/MergeableHeap.d @@ -0,0 +1,33 @@ +dep/MergeableHeap.d:: src/MergeableHeap.cpp inc/meowpp/dsa/MergeableHeap.h inc/meowpp/dsa/MergeableHeap.hpp inc/meowpp/dsa/MergeableHeap.h inc/meowpp/utility.h inc/meowpp/utility.hpp inc/meowpp/utility.h inc/meowpp.h inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/../math/Matrix.hpp inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/Vector2D.hpp inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/utility.h inc/meowpp/geo/../math/utility.hpp inc/meowpp/geo/../math/utility.h inc/meowpp/geo/Vector3D.h inc/meowpp/geo/Vector3D.hpp inc/meowpp/geo/Vector3D.h inc/meowpp/Usage.h inc/meowpp/Usage.hpp inc/meowpp/Usage.h inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/Properties.hpp inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/ObjSelector.h + $(DEPENDENCY_CREATER) "`$(CXX_DEP) $(CXXFLAGS) $<`" $@ + + +src/MergeableHeap.cpp::; +inc/meowpp/dsa/MergeableHeap.h::; +inc/meowpp/dsa/MergeableHeap.hpp::; +inc/meowpp/dsa/MergeableHeap.h::; +inc/meowpp/utility.h::; +inc/meowpp/utility.hpp::; +inc/meowpp/utility.h::; +inc/meowpp.h::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/../math/Matrix.hpp::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/Vector2D.hpp::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/../math/utility.hpp::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/geo/Vector3D.hpp::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/Usage.h::; +inc/meowpp/Usage.hpp::; +inc/meowpp/Usage.h::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/Properties.hpp::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/ObjSelector.h::; diff --git a/meowpp.test/dep/SegmentTree.d b/meowpp.test/dep/SegmentTree.d new file mode 100644 index 0000000..bda120e --- /dev/null +++ b/meowpp.test/dep/SegmentTree.d @@ -0,0 +1,34 @@ +dep/SegmentTree.d:: src/SegmentTree.cpp inc/meowpp/dsa/SegmentTree.h inc/meowpp/dsa/SegmentTree.hpp inc/meowpp/dsa/SegmentTree.h inc/meowpp/dsa/../math/utility.h inc/meowpp/dsa/../math/utility.hpp inc/meowpp/dsa/../math/utility.h inc/meowpp/utility.h inc/meowpp/utility.hpp inc/meowpp/utility.h inc/meowpp.h inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/../math/Matrix.hpp inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/Vector2D.hpp inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/utility.h inc/meowpp/geo/Vector3D.h inc/meowpp/geo/Vector3D.hpp inc/meowpp/geo/Vector3D.h inc/meowpp/Usage.h inc/meowpp/Usage.hpp inc/meowpp/Usage.h inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/Properties.hpp inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/ObjSelector.h + $(DEPENDENCY_CREATER) "`$(CXX_DEP) $(CXXFLAGS) $<`" $@ + + +src/SegmentTree.cpp::; +inc/meowpp/dsa/SegmentTree.h::; +inc/meowpp/dsa/SegmentTree.hpp::; +inc/meowpp/dsa/SegmentTree.h::; +inc/meowpp/dsa/../math/utility.h::; +inc/meowpp/dsa/../math/utility.hpp::; +inc/meowpp/dsa/../math/utility.h::; +inc/meowpp/utility.h::; +inc/meowpp/utility.hpp::; +inc/meowpp/utility.h::; +inc/meowpp.h::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/../math/Matrix.hpp::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/Vector2D.hpp::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/geo/Vector3D.hpp::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/Usage.h::; +inc/meowpp/Usage.hpp::; +inc/meowpp/Usage.h::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/Properties.hpp::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/ObjSelector.h::; diff --git a/meowpp.test/dep/SplayTree.d b/meowpp.test/dep/SplayTree.d new file mode 100644 index 0000000..79a1502 --- /dev/null +++ b/meowpp.test/dep/SplayTree.d @@ -0,0 +1,33 @@ +dep/SplayTree.d:: src/SplayTree.cpp inc/meowpp/dsa/SplayTree.h inc/meowpp/dsa/SplayTree.hpp inc/meowpp/dsa/SplayTree.h inc/meowpp/utility.h inc/meowpp/utility.hpp inc/meowpp/utility.h inc/meowpp.h inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/../math/Matrix.hpp inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/Vector2D.hpp inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/utility.h inc/meowpp/geo/../math/utility.hpp inc/meowpp/geo/../math/utility.h inc/meowpp/geo/Vector3D.h inc/meowpp/geo/Vector3D.hpp inc/meowpp/geo/Vector3D.h inc/meowpp/Usage.h inc/meowpp/Usage.hpp inc/meowpp/Usage.h inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/Properties.hpp inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/ObjSelector.h + $(DEPENDENCY_CREATER) "`$(CXX_DEP) $(CXXFLAGS) $<`" $@ + + +src/SplayTree.cpp::; +inc/meowpp/dsa/SplayTree.h::; +inc/meowpp/dsa/SplayTree.hpp::; +inc/meowpp/dsa/SplayTree.h::; +inc/meowpp/utility.h::; +inc/meowpp/utility.hpp::; +inc/meowpp/utility.h::; +inc/meowpp.h::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/../math/Matrix.hpp::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/Vector2D.hpp::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/../math/utility.hpp::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/geo/Vector3D.hpp::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/Usage.h::; +inc/meowpp/Usage.hpp::; +inc/meowpp/Usage.h::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/Properties.hpp::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/ObjSelector.h::; diff --git a/meowpp.test/dep/SplayTree_Range.d b/meowpp.test/dep/SplayTree_Range.d new file mode 100644 index 0000000..e16c7a3 --- /dev/null +++ b/meowpp.test/dep/SplayTree_Range.d @@ -0,0 +1,34 @@ +dep/SplayTree_Range.d:: src/SplayTree_Range.cpp inc/meowpp/dsa/SplayTree_Range.h inc/meowpp/dsa/../math/utility.h inc/meowpp/dsa/../math/utility.hpp inc/meowpp/dsa/../math/utility.h inc/meowpp/dsa/SplayTree_Range.hpp inc/meowpp/dsa/SplayTree_Range.h inc/meowpp/utility.h inc/meowpp/utility.hpp inc/meowpp/utility.h inc/meowpp.h inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/../math/Matrix.hpp inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/Vector2D.hpp inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/utility.h inc/meowpp/geo/Vector3D.h inc/meowpp/geo/Vector3D.hpp inc/meowpp/geo/Vector3D.h inc/meowpp/Usage.h inc/meowpp/Usage.hpp inc/meowpp/Usage.h inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/Properties.hpp inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/ObjSelector.h + $(DEPENDENCY_CREATER) "`$(CXX_DEP) $(CXXFLAGS) $<`" $@ + + +src/SplayTree_Range.cpp::; +inc/meowpp/dsa/SplayTree_Range.h::; +inc/meowpp/dsa/../math/utility.h::; +inc/meowpp/dsa/../math/utility.hpp::; +inc/meowpp/dsa/../math/utility.h::; +inc/meowpp/dsa/SplayTree_Range.hpp::; +inc/meowpp/dsa/SplayTree_Range.h::; +inc/meowpp/utility.h::; +inc/meowpp/utility.hpp::; +inc/meowpp/utility.h::; +inc/meowpp.h::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/../math/Matrix.hpp::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/Vector2D.hpp::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/geo/Vector3D.hpp::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/Usage.h::; +inc/meowpp/Usage.hpp::; +inc/meowpp/Usage.h::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/Properties.hpp::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/ObjSelector.h::; diff --git a/meowpp.test/dep/VP_Tree.d b/meowpp.test/dep/VP_Tree.d new file mode 100644 index 0000000..30cbd22 --- /dev/null +++ b/meowpp.test/dep/VP_Tree.d @@ -0,0 +1,39 @@ +dep/VP_Tree.d:: src/VP_Tree.cpp inc/meowpp/dsa/VP_Tree.h inc/meowpp/dsa/../math/utility.h inc/meowpp/dsa/../math/utility.hpp inc/meowpp/dsa/../math/utility.h inc/meowpp/dsa/VP_Tree.hpp inc/meowpp/dsa/VP_Tree.h inc/meowpp/dsa/KD_Tree.h inc/meowpp/dsa/KD_Tree.hpp inc/meowpp/dsa/KD_Tree.h inc/meowpp/dsa/../utility.h inc/meowpp/dsa/../utility.hpp inc/meowpp/dsa/../utility.h inc/meowpp/utility.h inc/meowpp.h inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/../math/Matrix.hpp inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/Vector2D.hpp inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/utility.h inc/meowpp/geo/Vector3D.h inc/meowpp/geo/Vector3D.hpp inc/meowpp/geo/Vector3D.h inc/meowpp/Usage.h inc/meowpp/Usage.hpp inc/meowpp/Usage.h inc/meowpp/utility.h inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/Properties.hpp inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/ObjSelector.h + $(DEPENDENCY_CREATER) "`$(CXX_DEP) $(CXXFLAGS) $<`" $@ + + +src/VP_Tree.cpp::; +inc/meowpp/dsa/VP_Tree.h::; +inc/meowpp/dsa/../math/utility.h::; +inc/meowpp/dsa/../math/utility.hpp::; +inc/meowpp/dsa/../math/utility.h::; +inc/meowpp/dsa/VP_Tree.hpp::; +inc/meowpp/dsa/VP_Tree.h::; +inc/meowpp/dsa/KD_Tree.h::; +inc/meowpp/dsa/KD_Tree.hpp::; +inc/meowpp/dsa/KD_Tree.h::; +inc/meowpp/dsa/../utility.h::; +inc/meowpp/dsa/../utility.hpp::; +inc/meowpp/dsa/../utility.h::; +inc/meowpp/utility.h::; +inc/meowpp.h::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/../math/Matrix.hpp::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/Vector2D.hpp::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/geo/Vector3D.hpp::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/Usage.h::; +inc/meowpp/Usage.hpp::; +inc/meowpp/Usage.h::; +inc/meowpp/utility.h::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/Properties.hpp::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/ObjSelector.h::; diff --git a/meowpp.test/dep/dsa.d b/meowpp.test/dep/dsa.d new file mode 100644 index 0000000..e2db740 --- /dev/null +++ b/meowpp.test/dep/dsa.d @@ -0,0 +1,30 @@ +dep/dsa.d:: src/dsa.cpp inc/meowpp.h inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/../math/Matrix.hpp inc/meowpp/geo/../math/Matrix.h inc/meowpp/geo/Vector2D.hpp inc/meowpp/geo/Vector2D.h inc/meowpp/geo/../math/utility.h inc/meowpp/geo/../math/utility.hpp inc/meowpp/geo/../math/utility.h inc/meowpp/geo/Vector3D.h inc/meowpp/geo/Vector3D.hpp inc/meowpp/geo/Vector3D.h inc/meowpp/Usage.h inc/meowpp/Usage.hpp inc/meowpp/Usage.h inc/meowpp/utility.h inc/meowpp/utility.hpp inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/Properties.hpp inc/meowpp/oo/Properties.h inc/meowpp/oo/ObjBase.h inc/meowpp/oo/ObjSelector.h inc/meowpp/Usage.h + $(DEPENDENCY_CREATER) "`$(CXX_DEP) $(CXXFLAGS) $<`" $@ + + +src/dsa.cpp::; +inc/meowpp.h::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/../math/Matrix.hpp::; +inc/meowpp/geo/../math/Matrix.h::; +inc/meowpp/geo/Vector2D.hpp::; +inc/meowpp/geo/Vector2D.h::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/../math/utility.hpp::; +inc/meowpp/geo/../math/utility.h::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/geo/Vector3D.hpp::; +inc/meowpp/geo/Vector3D.h::; +inc/meowpp/Usage.h::; +inc/meowpp/Usage.hpp::; +inc/meowpp/Usage.h::; +inc/meowpp/utility.h::; +inc/meowpp/utility.hpp::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/Properties.hpp::; +inc/meowpp/oo/Properties.h::; +inc/meowpp/oo/ObjBase.h::; +inc/meowpp/oo/ObjSelector.h::; +inc/meowpp/Usage.h::; diff --git a/meowpp.test/inc/meowpp b/meowpp.test/inc/meowpp new file mode 120000 index 0000000..304fa84 --- /dev/null +++ b/meowpp.test/inc/meowpp @@ -0,0 +1 @@ +../../meowpp
\ No newline at end of file diff --git a/meowpp.test/inc/meowpp.h b/meowpp.test/inc/meowpp.h new file mode 100644 index 0000000..8e6e181 --- /dev/null +++ b/meowpp.test/inc/meowpp.h @@ -0,0 +1,34 @@ +#ifndef __meowpp_h__ +#define __meowpp_h__ + +#include "meowpp/geo/Vector2D.h" +#include "meowpp/geo/Vector3D.h" + +#include "meowpp/Usage.h" +#include "meowpp/oo/Properties.h" +#include "meowpp/oo/ObjBase.h" +#include "meowpp/oo/ObjSelector.h" + +extern int count; + +class TestFunction: public meow::ObjBase{ + public: + virtual ~TestFunction(){ }; + virtual bool run() = 0; + virtual std::string name () const = 0; + virtual std::string description() const = 0; +}; + +#define TEST(__A,__B) \ +class Test##__A: public TestFunction{ \ + public: \ + \ + meow::ObjBase* create() const{ return new Test##__A(); } \ + bool run(); \ + std::string name() const{ return #__A; } \ + std::string description() const{ return __B; } \ +}; \ +static meow::ObjSelector<0> _(meow::stringPrintf("%d", count++), new Test##__A()); \ +inline bool Test##__A::run() + +#endif // __meowpp_h__ diff --git a/meowpp.test/src/BinaryIndexTree.cpp b/meowpp.test/src/BinaryIndexTree.cpp new file mode 100644 index 0000000..0b81f10 --- /dev/null +++ b/meowpp.test/src/BinaryIndexTree.cpp @@ -0,0 +1,57 @@ +#include "meowpp/dsa/BinaryIndexTree.h" +#include "meowpp/utility.h" + +#include "meowpp.h" + +#include <vector> + +static int N = 100000; + +static std::vector<int> array; + +inline int sum(int k){ + int x = 0; + for(int i = 0; i <= k; i++){ + x += array[i]; + } + return x; +} + +static meow::BinaryIndexTree<int> bit; + +TEST(BinaryIndexTree, "Test with large data"){ + size_t tMe = 0, tBi = 0, t0; + for(int z = 0; z < 10; z++){ + meow::messagePrintf(1, "test %d", z); + bit.reset(N, 0); + array.clear(); + array.resize(N, 0); + + int NN = rand() % 10000; + for(int i = 0; i < NN; i++){ + int index = rand() % N; + if(rand() & 1){ + int val = rand() % 1000; + t0 = clock(); array[i] += val; tMe += clock() - t0; + t0 = clock(); bit.update(i, val); tBi += clock() - t0; + }else{ + if(sum(index) != bit.query(index)){ + meow::messagePrintf(-1, "range-sum query fail"); + return false; + } + } + } + int s = 0; + for(int i = 0; i < N; i++){ + s += array[i]; + if(s != bit.query(i)){ + meow::messagePrintf(-1, "range-sum query fail"); + return false; + } + } + meow::messagePrintf(-1, "ok %.3f/%.3f", + tBi * 1.0 / CLOCKS_PER_SEC, + tMe * 1.0 / CLOCKS_PER_SEC); + } + return true; +}; diff --git a/meowpp.test/src/Colors.cpp b/meowpp.test/src/Colors.cpp new file mode 100644 index 0000000..3233cf6 --- /dev/null +++ b/meowpp.test/src/Colors.cpp @@ -0,0 +1,130 @@ +#include "meowpp/colors/RGB.h" +#include "meowpp/colors/YUV.h" +#include "meowpp/colors/HSL.h" +#include "meowpp/colors/HSV.h" +#include "meowpp/utility.h" + +#include "meowpp.h" + +TEST(Colors, "Transformations"){ + meow::RGBf rgb, rgb2; + meow::YUVf yuv, yuv2; + meow::HSLf hsl, hsl2; + meow::HSVf hsv, hsv2; + bool ok = true; + double eps; + eps = 1e-8; + meow::messagePrintf(1, "rgb ---> hsl ---> rgb ---> hsl (eps = %e)", eps); + for(int i = 0; ok && i < 100000; i++){ + rgb.r(meow::ratioMapping(0.0, 1.0, 1.0 * rand() / RAND_MAX, rgb.rMin(), rgb.rMax())); + rgb.g(meow::ratioMapping(0.0, 1.0, 1.0 * rand() / RAND_MAX, rgb.gMin(), rgb.gMax())); + rgb.b(meow::ratioMapping(0.0, 1.0, 1.0 * rand() / RAND_MAX, rgb.bMin(), rgb.bMax())); + meow::RGB_to_HSL(rgb , &hsl ); + meow::HSL_to_RGB(hsl , &rgb2); + meow::RGB_to_HSL(rgb2, &hsl2); + if(meow::noEPS(rgb.r() - rgb2.r(), eps) != 0 || + meow::noEPS(rgb.g() - rgb2.g(), eps) != 0 || + meow::noEPS(rgb.b() - rgb2.b(), eps) != 0) ok = false; + if(meow::noEPS(hsl.h() - hsl2.h(), eps) != 0 || + meow::noEPS(hsl.s() - hsl2.s(), eps) != 0 || + meow::noEPS(hsl.l() - hsl2.l(), eps) != 0) ok = false; + } + if(ok) meow::messagePrintf(-1, "ok!"); + else{ meow::messagePrintf(-1, "fail"); return false; } + // + eps = 1e-8; + meow::messagePrintf(1, "rgb ---> hsv ---> rgb ---> hsv (eps = %e)", eps); + for(int i = 0; ok && i < 100000; i++){ + rgb.r(meow::ratioMapping(0.0, 1.0, 1.0 * rand() / RAND_MAX, rgb.rMin(), rgb.rMax())); + rgb.g(meow::ratioMapping(0.0, 1.0, 1.0 * rand() / RAND_MAX, rgb.gMin(), rgb.gMax())); + rgb.b(meow::ratioMapping(0.0, 1.0, 1.0 * rand() / RAND_MAX, rgb.bMin(), rgb.bMax())); + meow::RGB_to_HSV(rgb , &hsv ); + meow::HSV_to_RGB(hsv , &rgb2); + meow::RGB_to_HSV(rgb2, &hsv2); + if(meow::noEPS(rgb.r() - rgb2.r(), eps) != 0 || + meow::noEPS(rgb.g() - rgb2.g(), eps) != 0 || + meow::noEPS(rgb.b() - rgb2.b(), eps) != 0) ok = false; + if(meow::noEPS(hsv.h() - hsv2.h(), eps) != 0 || + meow::noEPS(hsv.s() - hsv2.s(), eps) != 0 || + meow::noEPS(hsv.v() - hsv2.v(), eps) != 0) ok = false; + } + if(ok) meow::messagePrintf(-1, "ok!"); + else{ meow::messagePrintf(-1, "fail"); return false; } + // + /* + eps = 1e-3; + meow::messagePrintf(1, "yuv ---> hsl ---> yuv ---> hsl"); + for(int i = 0; ok && i < 100000; i++){ + yuv.y(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.yMin(), yuv.yMax())); + yuv.u(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.uMin(), yuv.uMax())); + yuv.v(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.vMin(), yuv.vMax())); + meow::YUV_to_HSL(yuv , &hsl ); + meow::HSL_to_YUV(hsl , &yuv2); + meow::YUV_to_HSL(yuv2, &hsl2); + if(meow::noEPS(yuv.y() - yuv2.y(), eps) != 0 || + meow::noEPS(yuv.u() - yuv2.u(), eps) != 0 || + meow::noEPS(yuv.v() - yuv2.v(), eps) != 0) ok = false; + if(meow::noEPS(hsl.h() - hsl2.h(), eps) != 0 || + meow::noEPS(hsl.s() - hsl2.s(), eps) != 0 || + meow::noEPS(hsl.l() - hsl2.l(), eps) != 0) ok = false; + } + if(ok) meow::messagePrintf(-1, "ok!"); + else{ meow::messagePrintf(-1, "fail"); return false; } + // */ + /* + meow::messagePrintf(1, "yuv ---> hsv ---> yuv ---> hsv"); + for(int i = 0; ok && i < 100000; i++){ + yuv.y(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.yMin(), yuv.yMax())); + yuv.u(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.uMin(), yuv.uMax())); + yuv.v(meow::ratioMapping(0, 1, 1.0 * rand() / RAND_MAX, yuv.vMin(), yuv.vMax())); + meow::YUV_to_HSV(yuv , &hsv ); + meow::HSV_to_YUV(hsv , &yuv2); + meow::YUV_to_HSV(yuv2, &hsv2); + if(meow::noEPS(yuv.y() - yuv2.y(), eps) != 0 || + meow::noEPS(yuv.u() - yuv2.u(), eps) != 0 || + meow::noEPS(yuv.v() - yuv2.v(), eps) != 0) ok = false; + if(meow::noEPS(hsv.h() - hsv2.h(), eps) != 0 || + meow::noEPS(hsv.s() - hsv2.s(), eps) != 0 || + meow::noEPS(hsv.v() - hsv2.v(), eps) != 0) ok = false; + } + if(ok) meow::messagePrintf(-1, "ok!"); + else{ meow::messagePrintf(-1, "fail"); return false; } + // */ + eps = 1e-3; + meow::messagePrintf(1, "rgb ---> yuv ---> rgb ---> yuv (eps = %e)", eps); + for(int i = 0; ok && i < 100000; i++){ + rgb.r(meow::ratioMapping(0.0, 1.0, 1.0 * rand() / RAND_MAX, rgb.rMin(), rgb.rMax())); + rgb.g(meow::ratioMapping(0.0, 1.0, 1.0 * rand() / RAND_MAX, rgb.gMin(), rgb.gMax())); + rgb.b(meow::ratioMapping(0.0, 1.0, 1.0 * rand() / RAND_MAX, rgb.bMin(), rgb.bMax())); + meow::RGB_to_YUV(rgb , &yuv ); + meow::YUV_to_RGB(yuv , &rgb2); + meow::RGB_to_YUV(rgb2, &yuv2); + if(meow::noEPS(rgb.r() - rgb2.r(), eps) != 0 || + meow::noEPS(rgb.g() - rgb2.g(), eps) != 0 || + meow::noEPS(rgb.b() - rgb2.b(), eps) != 0) ok = false; + if(meow::noEPS(yuv.y() - yuv2.y(), eps) != 0 || + meow::noEPS(yuv.u() - yuv2.u(), eps) != 0 || + meow::noEPS(yuv.v() - yuv2.v(), eps) != 0) ok = false; + } + if(ok) meow::messagePrintf(-1, "ok!"); + else{ meow::messagePrintf(-1, "fail"); return false; } + eps = 1e-8; + meow::messagePrintf(1, "hsl ---> hsv ---> hsl ---> hsv (eps = %e)", eps); + for(int i = 0; ok && i < 100000; i++){ + hsl.h(meow::ratioMapping(0.0, 1.0, 1.0 * rand() / RAND_MAX, hsl.hMin(), hsl.hMax())); + hsl.s(meow::ratioMapping(0.0, 1.0, 1.0 * rand() / RAND_MAX, hsl.sMin(), hsl.sMax())); + hsl.l(meow::ratioMapping(0.0, 1.0, 1.0 * rand() / RAND_MAX, hsl.lMin(), hsl.lMax())); + meow::HSL_to_HSV(hsl , &hsv ); + meow::HSV_to_HSL(hsv , &hsl2); + meow::HSL_to_HSV(hsl2, &hsv2); + if(meow::noEPS(hsl.h() - hsl2.h(), eps) != 0 || + meow::noEPS(hsl.s() - hsl2.s(), eps) != 0 || + meow::noEPS(hsl.l() - hsl2.l(), eps) != 0) ok = false; + if(meow::noEPS(hsv.h() - hsv2.h(), eps) != 0 || + meow::noEPS(hsv.s() - hsv2.s(), eps) != 0 || + meow::noEPS(hsv.v() - hsv2.v(), eps) != 0) ok = false; + } + if(ok) meow::messagePrintf(-1, "ok!"); + else{ meow::messagePrintf(-1, "fail"); return false; } + return true; +}; diff --git a/meowpp.test/src/DisjointSet.cpp b/meowpp.test/src/DisjointSet.cpp new file mode 100644 index 0000000..ca9db24 --- /dev/null +++ b/meowpp.test/src/DisjointSet.cpp @@ -0,0 +1,82 @@ +#include "meowpp/dsa/DisjointSet.h" + +#include "meowpp.h" + +#include <vector> + + +TEST(DisjointSet, "..."){ + int N = 10000000; + meow::DisjointSet dsj(N); + + meow::messagePrintf(1, "merge(0, 1) merge(0, 2) merge(0, 3) ... (N = %d)", N); + for(int i = 1; i < N; i++){ + dsj.merge(0, i); + } + int root = dsj.root(0); + for(int i = 1; i < N; i++){ + if(root != (int)dsj.root(i)){ + meow::messagePrintf(-1, "fail"); + return false; + } + } + meow::messagePrintf(-1, "ok"); + // + + dsj.reset(N); + meow::messagePrintf(1, "merge(0, 1) merge(1, 2) merge(2, 3) ... (N = %d)", N); + for(int i = 1; i < N; i++){ + dsj.merge(i - 1, i); + } + root = dsj.root(0); + for(int i = 1; i < N; i++){ + if(root != (int)dsj.root(i)){ + meow::messagePrintf(-1, "fail"); + return false; + } + } + meow::messagePrintf(-1, "ok"); + // + + int M = 1000; + N = 1000000; + dsj.reset(N); + std::vector<int> used(N, -1); + std::vector<int> nums[M]; + + meow::messagePrintf(1, "random test (N = %d)", N); + for(int i = 0; i < N / 10; i++){ + int grp = rand() % M; + int who; + while(used[who = rand() % N] != -1); + nums[grp].push_back(who); + used[who] = grp; + } + meow::messagePrintf(0, "data created"); + for(int i = 0; i < M; i++){ + for(int k = 0; k < 100; k++){ + int j1 = rand() % nums[i].size(); + int j2 = rand() % nums[i].size(); + dsj.merge(nums[i][j1], nums[i][j2]); + } + for(size_t j = 1; j < nums[i].size(); j++){ + dsj.merge(nums[i][0], nums[i][j]); + } + } + for(int i = 0; i < N; i++){ + bool ok = false; + if((int)used[i] == -1 && (int)dsj.root(i) == i){ + ok = true; + }else{ + if(dsj.root(i) == dsj.root(nums[used[i]][0])){ + ok = true; + } + } + if(!ok){ + meow::messagePrintf(-1, "fail"); + return false; + } + } + meow::messagePrintf(-1, "ok"); + return true; +}; diff --git a/meowpp.test/src/KD_Tree.cpp b/meowpp.test/src/KD_Tree.cpp new file mode 100644 index 0000000..1a61238 --- /dev/null +++ b/meowpp.test/src/KD_Tree.cpp @@ -0,0 +1,190 @@ +#include "meowpp/dsa/KD_Tree.h" +#include "meowpp/utility.h" + +#include "meowpp.h" + +#include <vector> + +#include <cmath> +#include <cstdlib> +#include <algorithm> +#include <ctime> +#include <queue> + +static int N = 10000; +static int D = 5; + +static double dist2(std::vector<double> const& v1, std::vector<double> const& v2){ + double ret = 0; + for(int i = 0; i < D; i++){ + ret += meow::squ(v1[i] - v2[i]); + } + return ret; +} + +static std::vector< std::vector<double> > data; +static std::vector< double > dist; +static std::vector< int > order; + + +struct Answer{ + double dist; + int id; + Answer(double _dist, int _id): dist(_dist), id(_id){ } + bool operator<(Answer const& b) const{ + if(dist != b.dist) return (dist < b.dist); + return (id < b.id); + } +}; + + +static void find(std::vector<double> const& v, int k){ + std::priority_queue<Answer> qu; + for(int i = 0; i < k; i++){ + qu.push(Answer(dist2(v, data[i]), i)); + } + for(int i = k; i < N; i++){ + qu.push(Answer(dist2(v, data[i]), i)); + qu.pop(); + } + order.resize(k); + for(int i = qu.size() - 1; i >= 0; i--){ + order[i] = qu.top().id; + qu.pop(); + } +} + +static std::vector<double> v; + +/* +static bool sf(const int& a, const int& b){ + if(dist[a] != dist[b]) + return (dist[a] < dist[b]); + return (a < b); +} + +static void show(std::vector<double> const& ask, std::vector<int> kd, std::vector<int> me, int k){ + if(N <= 30 && D <= 3){ + printf("\nData:\n"); + for(int i = 0; i < N; i++){ + printf(" %2d) <", i); + for(int j = 0; j < D; j++){ + printf("%.7f", data[i][j]); + if(j < D - 1) printf(", "); + else printf(">"); + } + printf("\n"); + } + printf("Ask <"); + for(int j = 0; j < D; j++){ + printf("%.7f", ask[j]); + if(j < D - 1) printf(", "); + else printf(">"); + } + printf("\n"); + printf("MyAnswer: "); + for(int i = 0; i < k; i++) printf("%d ", me[i]); + printf("\n"); + printf("KdAnswer: "); + for(int i = 0; i < k; i++) printf("%d ", kd[i]); + printf("\n"); + order.resize(N); + dist .resize(N); + for(int i = 0; i < N; i++){ + dist [i] = dist2(ask, data[i]); + order[i] = i; + } + std::sort(order.begin(), order.end(), sf); + printf("Sorted:\n"); + for(int i = 0; i < N; i++){ + printf(" %2d) <", order[i]); + for(int j = 0; j < D; j++){ + printf("%.7f", data[order[i]][j]); + if(j < D - 1) printf(", "); + else printf(">"); + } + printf(" ((%.7f))", dist[order[i]]); + printf("\n"); + } + } +} +// */ + +struct Node{ + std::vector<double> v; + int id; + double& operator[](size_t d) { return v[d]; } + double operator[](size_t d) const { return v[d]; } + bool operator<(Node const& n) const{ return (id < n.id); } +}; + +TEST(KD_Tree, "It is very slow"){ + + int t0, t1, t2; + + meow::KD_Tree<Node, double> tree(D); + + meow::messagePrintf(1, "Create data (N = %d, D = %d)", N, D); + data.resize(N); + for(int i = 0; i < N; i++){ + data[i].resize(D); + Node nd; + nd.v.resize(D); + nd.id = i; + for(int j = 0; j < D; j++){ + data[i][j] = 12345.0 * (1.0 * rand() / RAND_MAX - 0.3); + nd[j] = data[i][j]; + } + tree.insert(nd); + } + meow::messagePrintf(-1, "ok"); + meow::messagePrintf(1, "build"); + t0 = clock(); + tree.build(); + meow::messagePrintf(-1, "ok, %.3f seconds", (clock() - t0) * 1.0 / CLOCKS_PER_SEC); + + meow::messagePrintf(1, "query..."); + v.resize(D); + meow::KD_Tree<Node, double>::Vectors ret; + for(int k = 1; k <= std::min(100, N); k++){ + meow::messagePrintf(1, "range k = %d", k); + t1 = t2 = 0; + for(int i = 0; i < 10; i++){ + Node nd; + nd.v.resize(D); + for(int d = 0; d < D; d++){ + v[d] = 12345.0 * (1.0 * rand() / RAND_MAX - 0.3); + nd[d] = v[d]; + } + t0 = clock(); + tree.build(); + ret = tree.query(nd, k, true); + t1 += clock() - t0; + + t0 = clock(); + find(v, k); + t2 += clock() - t0; + if((int)ret.size() != (int)std::min(k, N)){ + meow::messagePrintf(-1, "(%d)query fail, size error", i); + meow::messagePrintf(-1, "fail"); + return false; + } + for(int kk = 1; kk <= k; kk++){ + if(order[kk - 1] != ret[kk - 1].id){ + //show(v, ret, order, k); + meow::messagePrintf(-1, "(%d)query fail", i); + meow::messagePrintf(-1, "fail"); + return false; + } + } + } + meow::messagePrintf(-1, "ok %.3f/%.3f", + t1 * 1.0 / CLOCKS_PER_SEC, + t2 * 1.0 / CLOCKS_PER_SEC + ); + } + meow::messagePrintf(-1, "ok"); + + + return true; +}; diff --git a/meowpp.test/src/Matrix.cpp b/meowpp.test/src/Matrix.cpp new file mode 100644 index 0000000..6ef94b7 --- /dev/null +++ b/meowpp.test/src/Matrix.cpp @@ -0,0 +1,45 @@ +#include "meowpp/math/Matrix.h" + +#include "meowpp.h" + +#include <cmath> +#include <cstdlib> + +using namespace meow; + + + +void print(Matrix<int> const& m){ + for(size_t r = 0; r < m.rows(); r++){ + printf("["); + for(size_t c = 0; c < m.cols(); c++){ + printf("%8d", m(r, c)); + } + printf("]\n"); + } +} + +TEST(Matrix, "Unfinished"){ + Matrix<int> a(3, 4, 0); + Matrix<int> b(3, 4, 0); + Matrix<int> c(4, 5, 0); + for(int i = 0; i < 3; i++){ + for(int j = 0; j < 4; j++){ + a.entry(i, j, rand() % 100); + b.entry(i, j, rand() % 100); + } + } + for(int i = 0; i < 4; i++){ + for(int j = 0; j < 5; j++){ + c.entry(i, j, rand() % 100); + } + } + printf("A = \n"); print(a); + printf("B = \n"); print(b); + printf("C = \n"); print(b); + printf("A + B = \n"); print(a + b); + printf("A * C = \n"); print(a * c); + printf("A * B^T = \n"); print(a * b.transpose()); + + return true; +}; diff --git a/meowpp.test/src/MergeableHeap.cpp b/meowpp.test/src/MergeableHeap.cpp new file mode 100644 index 0000000..78eed00 --- /dev/null +++ b/meowpp.test/src/MergeableHeap.cpp @@ -0,0 +1,74 @@ +#include "meowpp/dsa/MergeableHeap.h" +#include "meowpp/utility.h" + +#include "meowpp.h" + +#include <vector> +#include <queue> +#include <cstdlib> + + +TEST(MergeableHeap, "..."){ + int N = 10; + std::vector<std::priority_queue<int> > nhp; + std::vector<meow::MergeableHeap<int> > mhp; + for(int i = 0; i < 10; i++){ + int MM = 5000 + rand() % 10000; + meow::messagePrintf(1, "%d-th test (M = %5d)", i, MM); + nhp.clear(); nhp.resize(N); + mhp.clear(); mhp.resize(N); + int tn = 0, tm = 0, t0; + for(int j = 0; j < MM; j++){ + if((rand() & 3) == 0){ + int a = rand() % N; + int num = rand(); + t0 = clock(); nhp[a].push(num); tn += clock() - t0; + t0 = clock(); mhp[a].push(num); tm += clock() - t0; + }else if(rand() & 1){ + int a = rand() % N; + t0 = clock(); + if(!nhp[a].empty()) nhp[a].pop(); + tn += clock() - t0; + t0 = clock(); + if(!mhp[a].empty()) mhp[a].pop(); + tm += clock() - t0; + }else{ + int a = rand() % N, b = rand() % N; + if(b == a) b = (b + 1) % N; + t0 = clock(); + for( ; !nhp[b].empty(); nhp[b].pop()){ + nhp[a].push(nhp[b].top()); + } + tn += clock() - t0; + t0 = clock(); + mhp[a].merge(&mhp[b]); + tm += clock() - t0; + } + } + bool ok = true; + for(int j = 0; j < N; j++){ + while(!nhp[j].empty() && !mhp[j].empty()){ + if(nhp[j].top() != mhp[j].top()){ + ok = false; + break; + } + nhp[j].pop(); + mhp[j].pop(); + } + if(mhp[j].empty() != nhp[j].empty()){ + ok = false; + } + if(ok == false) break; + } + ok = true; + if(!ok){ + meow::messagePrintf(-1, "fail"); + return false; + }else{ + meow::messagePrintf(-1, "ok %.3f/%.3f", + tm * 1.0 / CLOCKS_PER_SEC, + tn * 1.0 / CLOCKS_PER_SEC ); + } + } + return true; +}; diff --git a/meowpp.test/src/SegmentTree.cpp b/meowpp.test/src/SegmentTree.cpp new file mode 100644 index 0000000..f92f55f --- /dev/null +++ b/meowpp.test/src/SegmentTree.cpp @@ -0,0 +1,157 @@ +#include "meowpp/dsa/SegmentTree.h" +#include "meowpp/utility.h" + +#include "meowpp.h" + +#include <ctime> +#include <algorithm> + +struct RangeMax{ + int value; + // + RangeMax(){} + RangeMax(int _value): value(_value){ } + RangeMax(RangeMax const& b): value(b.value){ } + // + RangeMax operator*(size_t n) const{ return RangeMax(value); } + RangeMax operator|(RangeMax const& b) const{ return RangeMax(std::max(value, b.value)); } + RangeMax operator+(RangeMax const& b) const{ return RangeMax(b.value + value); } + bool operator==(RangeMax const& b) const{ return (value == b.value); } +}; +struct RangeSum{ + int value; + // + RangeSum(){} + RangeSum(int _value): value(_value){ } + RangeSum(RangeSum const& b): value(b.value){ } + // + RangeSum operator*(size_t n) const{ return RangeSum(n * value); } + RangeSum operator|(RangeSum const& b) const{ return RangeSum(value + b.value); } + RangeSum operator+(RangeSum const& b) const{ return RangeSum(b.value + value); } + bool operator==(RangeSum const& b) const{ return (value == b.value); } +}; + +meow::SegmentTree<RangeMax> s_max; +meow::SegmentTree<RangeSum> s_sum; + +static int N = 1000000; + +std::vector<int> array; + +void override(int a, int b, int c){ + for(int i = a; i <= b; i++) + array[i] = c; +} +void offset(int a, int b, int c){ + for(int i = a; i <= b; i++) + array[i] += c; +} +int bmax(int a, int b){ + int ret = array[a]; + for(int i = a + 1; i <= b; i++) + ret = std::max(ret, array[i]); + return ret; +} +int bsum(int a, int b){ + int sum = 0; + for(int i = a; i <= b; i++) + sum += array[i]; + return sum; +} + +void show(){ + if(N <= 20){ + printf("\n"); + printf("Me : "); + for(int i = 0; i < N; i++){ + printf("%4d ", array[i]); + } + printf("\n"); + printf("Sum: "); + for(int i = 0; i < N; i++){ + printf("%4d ", s_sum.query(i, i).value); + } + printf("\n"); + printf("Max: "); + for(int i = 0; i < N; i++){ + printf("%4d ", s_max.query(i, i).value); + } + printf("\n"); + } +} + +TEST(SegmentTree, "..."){ + s_max.reset(N); + s_sum.reset(N); + s_max.override(0, N - 1, RangeMax(0)); + s_sum.override(0, N - 1, RangeSum(0)); + array.resize(N, 0); + + for(int z = 0; z < 10; z++){ + meow::messagePrintf(1, "test %d", z); + int tMe = 0, tSeg = 0, t0; + int NN = 1 + rand() % 100; + for(int i = 0; i < NN; i++){ + int a = rand() % N; + int b = rand() % (N - a) + a; + int k = rand() % 20000 - 10000; + bool over = (rand() % 2 == 1); + if(over){ + t0 = clock(); + s_max.override(a, b, RangeMax(k)); + s_sum.override(a, b, RangeSum(k)); + tSeg += clock() - t0; + t0 = clock(); + override(a, b, k); + tMe += clock() - t0; + }else{ + t0 = clock(); + s_max.offset(a, b, RangeMax(k)); + s_sum.offset(a, b, RangeSum(k)); + tSeg = clock() - t0; + t0 = clock(); + offset(a, b, k); + tMe += clock() - t0; + } + /* + printf("\n"); + printf("%s %d~%d with %d", over ? "override" : "offset", a, b, k); + show(); + printf("max:"); s_max.print(); + printf("sum:"); s_sum.print(); + // */ + } + NN = 1 + rand() % 100; + for(int i = 0; i < NN; i++){ + int a = rand() % N; + int b = rand() % (N - a) + a; + + t0 = clock(); + RangeMax m(s_max.query(a, b)); + RangeSum s(s_sum.query(a, b)); + tSeg += clock() - t0; + t0 = clock(); + int mm = bmax(a, b); + int ss = bsum(a, b); + tMe += clock() - t0; + if(m.value != mm){ + printf("ask %d~%d, me %d/%d seg %d/%d\n", a, b, mm, ss, m.value, s.value); + meow::messagePrintf(-1, "range-max query fail"); + return false; + } + if(s.value != ss){ + printf("ask %d~%d, max/sum = me %d/%d seg %d/%d\n", a, b, mm, ss, m.value, s.value); + meow::messagePrintf(-1, "range-sum query fail"); + return false; + } + } + meow::messagePrintf(-1, "ok, %.3f/%.3f", + 1.0 * tSeg / CLOCKS_PER_SEC, + 1.0 * tMe / CLOCKS_PER_SEC); + s_max.reset(N); + s_sum.reset(N); + array.clear(); + array.resize(N, 0); + } + return true; +}; diff --git a/meowpp.test/src/SplayTree.cpp b/meowpp.test/src/SplayTree.cpp new file mode 100644 index 0000000..9855307 --- /dev/null +++ b/meowpp.test/src/SplayTree.cpp @@ -0,0 +1,477 @@ +#include "meowpp/dsa/SplayTree.h" +#include "meowpp/utility.h" + +#include "meowpp.h" + +#include <algorithm> +#include <utility> +#include <map> +#include <cstdlib> + +static int N; + +static bool detail_fg; + +typedef typename std::map <int, double>:: iterator IterN; +typedef typename std::map <int, double>::reverse_iterator IterR; +typedef typename meow::SplayTree<int, double>::Element IterS; + +static std::vector< std::map <int, double> > normal; +static std::vector<meow::SplayTree<int, double> > splay; + +static void show(bool fg = false){ + if(fg){ + for(int i = 0; i < N; i++){ + printf("normal %d-%lu: ", i, normal[i].size()); + for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ + printf("%d/%.2f ", it->first, it->second); + } + printf("\n"); + printf("splay %d-%lu: ", i, splay[i].size()); + for(size_t j = 0; j < splay[i].size(); j++){ + IterS it = splay[i].order(j); + printf("%d/%.2f ", it->first, it->second); + } + printf("\n"); + } + printf("\n"); + } +} + +static bool lowerBound(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= lowerBound(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].lowerBound (key); (*tS) += clock() - t0; + t0 = clock(); IterN a = normal[i].lower_bound(key); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second, + (b == splay[i].end()) ? 0 : b->second); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second == b->second); +} +static bool upperBound(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= upperBound(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].upperBound (key); (*tS) += clock() - t0; + t0 = clock(); IterN a = normal[i].upper_bound(key); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay [i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second, + (b == splay [i].end()) ? 0 : b->second); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second == b->second); +} +static bool rLowerBound(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= rLowerBound(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].rLowerBound(key); (*tS) += clock() - t0; + t0 = clock(); + IterN a, z; + if(normal[i].size() == 0 || normal[i].begin()->first > key){ + a = normal[i].end(); + }else{ + for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); z++, a++){ + if(z->first > key){ + break; + } + } + } + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second, + (b == splay[i].end()) ? 0 : b->second); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second == b->second); +} +static bool rUpperBound(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= rUpperBound(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].rUpperBound(key); (*tS) += clock() - t0; + t0 = clock(); + IterN a, z; + if(normal[i].begin() == normal[i].end()){ + a = normal[i].end(); + }else{ + if(normal[i].begin()->first >= key) a = normal[i].end(); + else{ + for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); a++, z++){ + if(z->first >= key) + break; + } + } + } + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second, + (b == splay[i].end()) ? 0 : b->second); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second == b->second); +} +static bool find(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= find(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].find(key); (*tS) += clock() - t0; + t0 = clock(); IterN a = normal[i].find(key); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second, + (b == splay[i].end()) ? 0 : b->second); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second == b->second); +} +static bool order(int i, int order, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= order(%d, %d)\n", i, order); + t0 = clock(); IterS b = splay[i].order(order); (*tS) += clock() - t0; + t0 = clock(); + IterN a = normal[i].begin(); + for(int k = 0; k < order; k++) a++; + (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second, + (b == splay[i].end()) ? 0 : b->second); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second == b->second); +} +static bool first_last(int i, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= first_last(%d)\n", i); + IterN a; + t0 = clock(); IterS b = splay[i].first (); (*tS) += clock() - t0; + t0 = clock(); a = normal[i].begin(); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second, + (b == splay[i].end()) ? 0 : b->second); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()); + else{ + if((a->first == b->first && a->second == b->second) == false){ + return false; + } + } + t0 = clock(); b = splay[i].last (); (*tS) += clock() - t0; + t0 = clock(); IterR r = normal[i].rbegin(); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (r == normal[i].rend()) ? 0 : r->first, + (b == splay[i].end()) ? 0 : b->first, + (r == normal[i].rend()) ? 0 : r->second, + (b == splay[i].end()) ? 0 : b->second); + if((r == normal[i].rend()) != (b == splay[i].end())) return false; + if(r == normal[i].rend()); + else{ + if((r->first == b->first && r->second == b->second) == false){ + return false; + } + } + return true; +} +/* +static bool insert(int i, int key, double val, size_t* tN, size_t* tS){ + size_t t0; + if(rand() & 1){ + t0 = clock(); splay [i].insert(key, val); (*tS) += clock() - t0; + t0 = clock(); normal[i].insert(std::pair<int, double>(key, val)); (*tN) += clock() - t0; + }else{ + t0 = clock(); splay [i][key] = val; (*tS) += clock() - t0; + t0 = clock(); normal[i][key] = val; (*tN) += clock() - t0; + } + detail_fg && printf("============= insert(%d, %d)\n", i, key); + show(detail_fg); + return true; +} +// */ +static bool split(int i, int j, int key, size_t* tN, size_t* tS){ + size_t t0; + if(i == j){ + return true; + } + detail_fg && printf("============= split(%d, %d, %d)\n", i, j, key); + t0 = clock(); splay[i].splitOut(key, &splay[j]); *tS += clock() - t0; + t0 = clock(); + normal[j].clear(); + for(IterN it; (it = normal[i].upper_bound(key)) != normal[i].end(); ){ + normal[j].insert(*it); + normal[i].erase(it); + } + *tN += clock() - t0; + show(detail_fg); + return true; +} +static bool merge(int i, int j, int key, size_t* tN, size_t* tS){ + size_t t0; + if(i == j){ + return true; + } + if(rand() & 1){ + t0 = clock(); + if(splay[i].size() > 0) + while(splay[j].size() > 0 && + splay[j].first()->first <= splay[i].last()->first){ + splay[j].erase(splay[j].first()->first); + } + *tS += clock() - t0; + t0 = clock(); + if(normal[i].size() > 0) + while(normal[j].size() > 0 && + normal[j].begin()->first <= normal[i].rbegin()->first) + normal[j].erase(normal[j].begin()); + *tN += clock() - t0; + } + t0 = clock(); splay[i].merge(&splay[j]); *tS += clock() - t0; + t0 = clock(); + if(normal[i].size() == 0 || normal[j].size() == 0 || + normal[i].rbegin()->first < normal[j].begin()->first || + normal[j].rbegin()->first < normal[i].begin()->first + ){ + for(IterN it = normal[j].begin(); it != normal[j].end(); it++){ + normal[i].insert(*it); + } + normal[j].clear(); + } + *tN += clock() - t0; + detail_fg && printf("============= merge(%d, %d)\n", i, j); + show(detail_fg); + return true; +} +static bool erase(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= erase(%d, %d)\n", i, key); + t0 = clock(); splay[i].erase(key); (*tS) += clock() - t0; + t0 = clock(); normal[i].erase(key); (*tN) += clock() - t0; + show(detail_fg); + return true; +} +static bool keyOffset(int i, int delta, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= keyOffset(%d, %d)\n", i, delta); + t0 = clock(); splay[i].keyOffset(delta); (*tS) += clock() - t0; + t0 = clock(); + std::map<int, double> tmp = normal[i]; + normal[i].clear(); + for(IterN it = tmp.begin(); it != tmp.end(); it++){ + normal[i].insert(std::pair<int, double>(it->first + delta, it->second)); + } + (*tN) += clock() - t0; + show(detail_fg); + return true; +} +/* +static bool valueOffset(int i, double delta, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= valueOffset(%d, %f)\n", i, delta); + t0 = clock(); splay[i].valueOffset(delta); (*tS) += clock() - t0; + t0 = clock(); + for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ + it->second += delta; + } + (*tN) += clock() - t0; + show(detail_fg); + return true; +} +// */ +static bool copy(int i, int j, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("copy(%d, %d)\n", i, j); + t0 = clock(); splay[i] = splay[j]; (*tS) += clock() - t0; + t0 = clock(); normal[i] = normal[j]; (*tN) += clock() - t0; + show(detail_fg); + return true; +} + +static bool check(){ + for(int i = 0; i < N; i++){ + if(normal[i].size() != splay[i].size()) return false; + int j = 0; + for(IterN it = normal[i].begin(); it != normal[i].end(); it++, j++){ + if(it->first != splay[i].order(j)->first || + it->second != splay[i].order(j)->second) + return false; + } + } + return true; +} + +TEST(SplayTree, "Seems buggy"){ + detail_fg = false; + N = 5; + for(int i = 0; i < 10; i++){ + normal.clear(); + splay .clear(); + normal.resize(N); + splay .resize(N); + size_t tn = 0, tm = 0; + int op = 1 + rand() % 2000000; + meow::messagePrintf(1, "%d-th test, N = %d, op = %7d", i, N, op); + while(op--){ + int wh = rand() % 60; + int i1 = rand() % N, i2, k = rand() % 60; + while((i2 = rand() % N) == i1); + switch(wh){ + case 0: + if(lowerBound(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "lowerBound"); + show(true); + return false; + } + break; + case 1: + if(rUpperBound(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "rUpperBound"); + show(true); + return false; + } + break; + case 2: + if(rLowerBound(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "rLowerBound"); + show(true); + return false; + } + break; + case 3: + if(upperBound(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "upperBound"); + show(true); + return false; + } + break; + case 4: + case 5: + case 6: + if(find(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "find"); + show(true); + return false; + } + break; + case 7: + case 8: + case 9: + if(normal[i1].size() > 0){ + if(order(i1, rand() % normal[i1].size(), &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "order"); + show(true); + return false; + } + break; + } + case 10: + if(first_last(i1, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "first_last"); + show(true); + return false; + } + break; + case 21: + case 22: + case 23: + case 24: + case 25: + case 26: + if(split(i1, i2, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "split"); + show(true); + return false; + } + break; + case 27: + case 28: + case 29: + case 30: + case 31: + case 32: + case 33: + case 34: + case 35: + case 36: + if(merge(i1, i2, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "merge"); + show(true); + return false; + } + break; + case 37: + case 38: + case 39: + case 40: + if(erase(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "erase"); + show(true); + return false; + } + break; + case 41: + case 42: + case 43: + case 44: + case 45: + case 46: + case 47: + case 48: + case 49: + if(keyOffset(i1, ((rand() & 2) - 1) * k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "keyOffset"); + show(true); + return false; + } + break; + case 50: + case 51: + case 52: + if(copy(i1, i2, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "copy"); + show(true); + return false; + } + break; + case 53: + case 54: + case 55: + case 56: + case 57: + case 58: + case 59: + op++; + /* + if(valueOffset(i1, 1.0 * rand() / RAND_MAX * 100, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "valueOffset"); + show(true); + return false; + } + break; + // */ + } + } + if(!check()){ + meow::messagePrintf(-1, "fail"); + show(true); + return false; + } + meow::messagePrintf(-1, "ok %.3f/%.3f", + tm * 1.0 / CLOCKS_PER_SEC, + tn * 1.0 / CLOCKS_PER_SEC); + } + return true; +}; diff --git a/meowpp.test/src/SplayTree_Range.cpp b/meowpp.test/src/SplayTree_Range.cpp new file mode 100644 index 0000000..085b5bf --- /dev/null +++ b/meowpp.test/src/SplayTree_Range.cpp @@ -0,0 +1,561 @@ +#include "meowpp/dsa/SplayTree_Range.h" +#include "meowpp/utility.h" + +#include "meowpp.h" + +#include <algorithm> +#include <utility> +#include <map> +#include <cstdlib> +#include <cmath> + +static int min_sum; +struct Double{ + double k; + Double(): k(0){ } + Double(double _k): k(0){ } + bool operator==(const Double& b) const{ return fabs(k - b.k) <= 1e-9; } + bool operator!=(const Double& b) const{ return fabs(k - b.k) > 1e-9; } + bool operator<(const Double& b) const{ return k < b.k; } + Double operator+(const Double& b) const{ return Double(k + b.k); } + Double operator*(size_t& b) const{ + if(min_sum == 0) return Double(k); + else return Double(k * b); + } + Double operator|(const Double& b) const{ + if(min_sum == 0) return Double(std::min(k, b.k)); + else return Double(k + b.k); + } +}; + +static int N; + +static bool detail_fg; + +typedef typename std::map <int, Double>:: iterator IterN; +typedef typename std::map <int, Double>::reverse_iterator IterR; +typedef typename meow::SplayTree_Range<int, Double>::Element IterS; + +static std::vector< std::map <int, Double> > normal; +static std::vector<meow::SplayTree_Range<int, Double> > splay; + +static void show(bool fg = false){ + if(fg){ + for(int i = 0; i < N; i++){ + printf("normal %d-%lu: ", i, normal[i].size()); + for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ + printf("%d/%.2f ", it->first, it->second.k); + } + printf("\n"); + printf("splay %d-%lu: ", i, splay[i].size()); + for(size_t j = 0; j < splay[i].size(); j++){ + IterS it = splay[i].order(j); + printf("%d/%.2f ", it->first, it->second.k); + } + printf("\n"); + } + printf("\n"); + } +} + +static bool lowerBound(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= lowerBound(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].lowerBound (key); (*tS) += clock() - t0; + t0 = clock(); IterN a = normal[i].lower_bound(key); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second.k, + (b == splay[i].end()) ? 0 : b->second.k); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second.k == b->second.k); +} +static bool upperBound(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= upperBound(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].upperBound (key); (*tS) += clock() - t0; + t0 = clock(); IterN a = normal[i].upper_bound(key); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay [i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second.k, + (b == splay [i].end()) ? 0 : b->second.k); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second.k == b->second.k); +} +static bool rLowerBound(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= rLowerBound(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].rLowerBound(key); (*tS) += clock() - t0; + t0 = clock(); + IterN a, z; + if(normal[i].size() == 0 || normal[i].begin()->first > key){ + a = normal[i].end(); + }else{ + for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); z++, a++){ + if(z->first > key){ + break; + } + } + } + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second.k, + (b == splay[i].end()) ? 0 : b->second.k); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second.k == b->second.k); +} +static bool rUpperBound(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= rUpperBound(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].rUpperBound(key); (*tS) += clock() - t0; + t0 = clock(); + IterN a, z; + if(normal[i].begin() == normal[i].end()){ + a = normal[i].end(); + }else{ + if(normal[i].begin()->first >= key) a = normal[i].end(); + else{ + for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); a++, z++){ + if(z->first >= key) + break; + } + } + } + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second.k, + (b == splay[i].end()) ? 0 : b->second.k); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second.k == b->second.k); +} +static bool find(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= find(%d, %d)\n", i, key); + t0 = clock(); IterS b = splay [i].find(key); (*tS) += clock() - t0; + t0 = clock(); IterN a = normal[i].find(key); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second.k, + (b == splay[i].end()) ? 0 : b->second.k); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second.k == b->second.k); +} +static bool order(int i, int order, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= order(%d, %d)\n", i, order); + t0 = clock(); IterS b = splay[i].order(order); (*tS) += clock() - t0; + t0 = clock(); + IterN a = normal[i].begin(); + for(int k = 0; k < order; k++) a++; + (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second.k, + (b == splay[i].end()) ? 0 : b->second.k); + show(detail_fg); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()) return true; + return (a->first == b->first && a->second.k == b->second.k); +} +static bool first_last(int i, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= first_last(%d)\n", i); + IterN a; + t0 = clock(); IterS b = splay[i].first (); (*tS) += clock() - t0; + t0 = clock(); a = normal[i].begin(); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (a == normal[i].end()) ? 0 : a->first, + (b == splay[i].end()) ? 0 : b->first, + (a == normal[i].end()) ? 0 : a->second.k, + (b == splay[i].end()) ? 0 : b->second.k); + if((a == normal[i].end()) != (b == splay[i].end())) return false; + if( a == normal[i].end()); + else{ + if((a->first == b->first && a->second.k == b->second.k) == false){ + return false; + } + } + t0 = clock(); b = splay[i].last (); (*tS) += clock() - t0; + t0 = clock(); IterR r = normal[i].rbegin(); (*tN) += clock() - t0; + detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n", + (r == normal[i].rend()) ? 0 : r->first, + (b == splay[i].end()) ? 0 : b->first, + (r == normal[i].rend()) ? 0 : r->second.k, + (b == splay[i].end()) ? 0 : b->second.k); + if((r == normal[i].rend()) != (b == splay[i].end())) return false; + if(r == normal[i].rend()); + else{ + if((r->first == b->first && r->second.k == b->second.k) == false){ + return false; + } + } + return true; +} +static bool insert(int i, int key, Double val, size_t* tN, size_t* tS){ + size_t t0; + if(rand() & 1){ + t0 = clock(); splay [i].insert(key, val); (*tS) += clock() - t0; + t0 = clock(); normal[i].insert(std::pair<int, Double>(key, val)); (*tN) += clock() - t0; + }else{ + t0 = clock(); splay [i][key] = val; (*tS) += clock() - t0; + t0 = clock(); normal[i][key] = val; (*tN) += clock() - t0; + } + detail_fg && printf("============= insert(%d, %d)\n", i, key); + show(detail_fg); + return true; +} +static bool split(int i, int j, int key, size_t* tN, size_t* tS){ + size_t t0; + if(i == j){ + return true; + } + detail_fg && printf("============= split(%d, %d, %d)\n", i, j, key); + t0 = clock(); splay[i].splitOut(key, &splay[j]); *tS += clock() - t0; + t0 = clock(); + normal[j].clear(); + for(IterN it; (it = normal[i].upper_bound(key)) != normal[i].end(); ){ + normal[j].insert(*it); + normal[i].erase(it); + } + *tN += clock() - t0; + show(detail_fg); + return true; +} +static bool merge(int i, int j, int key, size_t* tN, size_t* tS){ + size_t t0; + if(i == j){ + return true; + } + if(rand() & 1){ + t0 = clock(); + if(splay[i].size() > 0) + while(splay[j].size() > 0 && + splay[j].first()->first <= splay[i].last()->first){ + splay[j].erase(splay[j].first()->first); + } + *tS += clock() - t0; + t0 = clock(); + if(normal[i].size() > 0) + while(normal[j].size() > 0 && + normal[j].begin()->first <= normal[i].rbegin()->first) + normal[j].erase(normal[j].begin()); + *tN += clock() - t0; + } + t0 = clock(); splay[i].merge(&splay[j]); *tS += clock() - t0; + t0 = clock(); + if(normal[i].size() == 0 || normal[j].size() == 0 || + normal[i].rbegin()->first < normal[j].begin()->first || + normal[j].rbegin()->first < normal[i].begin()->first + ){ + for(IterN it = normal[j].begin(); it != normal[j].end(); it++){ + normal[i].insert(*it); + } + normal[j].clear(); + } + *tN += clock() - t0; + detail_fg && printf("============= merge(%d, %d)\n", i, j); + show(detail_fg); + return true; +} +static bool erase(int i, int key, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= erase(%d, %d)\n", i, key); + t0 = clock(); splay[i].erase(key); (*tS) += clock() - t0; + t0 = clock(); normal[i].erase(key); (*tN) += clock() - t0; + show(detail_fg); + return true; +} +static bool keyOffset(int i, int delta, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= keyOffset(%d, %d)\n", i, delta); + t0 = clock(); splay[i].keyOffset(delta); (*tS) += clock() - t0; + t0 = clock(); + std::map<int, Double> tmp = normal[i]; + normal[i].clear(); + for(IterN it = tmp.begin(); it != tmp.end(); it++){ + normal[i].insert(std::pair<int, Double>(it->first + delta, it->second.k)); + } + (*tN) += clock() - t0; + show(detail_fg); + return true; +} +static bool valueOffset(int i, Double delta, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= valueOffset(%d, %f)\n", i, delta.k); + t0 = clock(); splay[i].valueOffset(delta); (*tS) += clock() - t0; + t0 = clock(); + for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ + it->second = it->second + delta; + } + (*tN) += clock() - t0; + show(detail_fg); + return true; +} +static bool valueOverride(int i, Double value, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= valueOverride(%d, %f)\n", i, value.k); + t0 = clock(); splay[i].valueOverride(value); (*tS) += clock() - t0; + t0 = clock(); + for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ + it->second.k = value.k; + } + (*tN) += clock() - t0; + show(detail_fg); + return true; +} +static bool query(int i, int a, int b, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("============= query(%d, %d, %d)\n", i, a, b); + Double ans1, ans2 = 0; + if((rand() & 3) == 3){ + t0 = clock(); ans1 = splay[i].query(); (*tS) += clock() - t0; + t0 = clock(); + for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ + ans2 = ans2 | it->second.k; + } + }else{ + t0 = clock(); ans1 = splay[i].query(a, b); (*tS) += clock() - t0; + t0 = clock(); + for(IterN it = normal[i].begin(); it != normal[i].end(); it++){ + if(a <= it->first && it->first <= b) + ans2 = ans2 | it->second.k; + } + } + detail_fg && printf(">>get %f %f\n", ans1.k, ans2.k); + show(detail_fg); + return true; +} +static bool copy(int i, int j, size_t* tN, size_t* tS){ + size_t t0; + detail_fg && printf("copy(%d, %d)\n", i, j); + t0 = clock(); splay[i] = splay[j]; (*tS) += clock() - t0; + t0 = clock(); normal[i] = normal[j]; (*tN) += clock() - t0; + show(detail_fg); + return true; +} + +static bool check(){ + for(int i = 0; i < N; i++){ + if(normal[i].size() != splay[i].size()) return false; + int j = 0; + for(IterN it = normal[i].begin(); it != normal[i].end(); it++, j++){ + if(it->first != splay[i].order(j)->first || + it->second.k != splay[i].order(j)->second.k) + return false; + } + } + return true; +} + +TEST(SplayTree_Range, "..."){ + detail_fg = false; + N = 5; + for(int i = 0; i < 10; i++){ + normal.clear(); + splay .clear(); + normal.resize(N); + splay .resize(N); + size_t tn = 0, tm = 0; + int op = 1 + rand() % 2000000; + min_sum = rand() & 1; + meow::messagePrintf(1, "%d-th test, N = %d, op = %7d", i, N, op); + while(op--){ + int wh = rand() % 100; + int i1 = rand() % N, i2, k = rand() % 60; + while((i2 = rand() % N) == i1); + switch(wh){ + case 0: + if(lowerBound(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "lowerBound"); + show(true); + return false; + } + break; + case 1: + if(rUpperBound(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "rUpperBound"); + show(true); + return false; + } + break; + case 2: + if(rLowerBound(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "rLowerBound"); + show(true); + return false; + } + break; + case 3: + if(upperBound(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "upperBound"); + show(true); + return false; + } + break; + case 4: + case 5: + case 6: + if(find(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "find"); + show(true); + return false; + } + break; + case 7: + case 8: + case 9: + if(normal[i1].size() > 0){ + if(order(i1, rand() % normal[i1].size(), &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "order"); + show(true); + return false; + } + break; + } + case 10: + if(first_last(i1, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "first_last"); + show(true); + return false; + } + break; + case 11: + case 12: + case 13: + case 14: + case 15: + case 16: + case 17: + case 18: + case 19: + case 20: + if(insert(i1, k, rand() * 1.0 / RAND_MAX * 50 + 1, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "insert"); + show(true); + return false; + } + break; + case 21: + case 22: + case 23: + case 24: + case 25: + case 26: + if(split(i1, i2, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "split"); + show(true); + return false; + } + break; + case 27: + case 28: + case 29: + case 30: + case 31: + case 32: + case 33: + case 34: + case 35: + case 36: + if(merge(i1, i2, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "merge"); + show(true); + return false; + } + break; + case 37: + case 38: + case 39: + case 40: + if(erase(i1, k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "erase"); + show(true); + return false; + } + break; + case 41: + case 42: + case 43: + case 44: + case 45: + case 46: + case 47: + case 48: + case 49: + if(keyOffset(i1, ((rand() & 2) - 1) * k, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "keyOffset"); + show(true); + return false; + } + break; + case 50: + case 51: + case 52: + if(copy(i1, i2, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "copy"); + show(true); + return false; + } + break; + case 53: + case 54: + case 55: + case 56: + case 57: + case 58: + case 59: + if(valueOverride(i1, 1.0 * rand() / RAND_MAX * 100 + 1, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "valueOffset"); + show(true); + return false; + } + break; + case 60: + case 61: + case 62: + case 63: + case 64: + case 65: + case 66: + if(valueOffset(i1, 1.0 * rand() / RAND_MAX * 100 + 1, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "valueOffset"); + show(true); + return false; + } + break; + default: + if(query(i1, rand() % 200 - 100, rand() % 200 - 100, &tn, &tm) == false){ + meow::messagePrintf(-1, "fail(%s)", "query"); + show(true); + return false; + } + break; + } + } + if(!check()){ + meow::messagePrintf(-1, "fail"); + show(true); + return false; + } + meow::messagePrintf(-1, "ok %.3f/%.3f", + tm * 1.0 / CLOCKS_PER_SEC, + tn * 1.0 / CLOCKS_PER_SEC); + } + return true; +}; diff --git a/meowpp.test/src/VP_Tree.cpp b/meowpp.test/src/VP_Tree.cpp new file mode 100644 index 0000000..c30b118 --- /dev/null +++ b/meowpp.test/src/VP_Tree.cpp @@ -0,0 +1,185 @@ +#include "meowpp/dsa/VP_Tree.h" +#include "meowpp/dsa/KD_Tree.h" +#include "meowpp/utility.h" + + +#include "meowpp.h" + +#include <vector> + +#include <cmath> +#include <cstdlib> +#include <algorithm> +#include <ctime> + +#include <queue> + +static int N = 100000; +static int D = 32; +static int MAX = 1000; + +typedef long long lnt; + +struct MyVector{ + std::vector<lnt> v; + int w; + // + MyVector(MyVector const& _v): v(_v.v), w(_v.w){ } + MyVector( ):v(D){ for(int i = 0; i < D; i++){ v[i] = (lnt)rand() % MAX; } } + MyVector(lnt k):v(D){ for(int i = 0; i < D; i++){ v[i] = k; } } + // + lnt & operator[](size_t n) { return v[n]; } + lnt const& operator[](size_t n) const{ return v[n]; } + bool operator<(MyVector const& v2) const{ return (w < v2.w); } + bool operator==(MyVector const& v2) const{ + for(int i = 0; i < D; i++) if(v[i] != v2[i]) return false; + return (w == v2.w); + } +}; + + +static lnt dist2(MyVector const& v1, MyVector const& v2){ + lnt k = 0; + for(int i = 0; i < D; i++){ + k += (v1[i] - v2[i]) * (v1[i] - v2[i]); + } + return k; +} + +static std::vector<MyVector> data; + +void show(MyVector const& v, std::vector<MyVector> const& r1, std::vector<MyVector> const& r2){ + if(N <= 20 && r1.size() <= 7){ + printf("\n"); + for(int i = 0; i < N; i++){ + printf("%3d) ", data[i].w); + for(int j = 0; j < D; j++) + printf("%8lld ", data[i][j]); + printf(" ===> %lld\n", dist2(data[i], v)); + } + printf("\n"); + printf("ask) "); + for(int j = 0; j < D; j++) + printf("%8lld ", v[j]); + printf("\n"); + printf("---------\n"); + for(size_t i = 0; i < r1.size(); i++){ + printf("%3d) ", r1[i].w); + for(int j = 0; j < D; j++) + printf("%8lld ", r1[i][j]); + printf(" ===> %lld\n", dist2(r1[i], v)); + } + printf("---------\n"); + for(size_t i = 0; i < r2.size(); i++){ + printf("%3d) ", r2[i].w); + for(int j = 0; j < D; j++) + printf("%8lld ", r2[i][j]); + printf(" ===> %lld\n", dist2(r2[i], v)); + } + } +} + +namespace VP{ + struct Answer{ + int i; + lnt d; + // + Answer(int _i, lnt _d): i(_i), d(_d){ } + Answer(Answer const& _a): i(_a.i), d(_a.d){ } + // + bool operator<(Answer const& b) const{ + if(d != b.d) return (d < b.d); + else return (data[i] < data[b.i]); + } + }; +} + +static std::vector<MyVector> find(MyVector const& v, int k){ + std::priority_queue<VP::Answer> qu; + for(int i = 0; i < std::min(k, N); i++){ + qu.push(VP::Answer(i, dist2(v, data[i]))); + } + for(int i = std::min(k, N); i < N; i++){ + qu.push(VP::Answer(i, dist2(v, data[i]))); + qu.pop(); + } + std::vector<MyVector> ret(qu.size()); + for(int i = (ssize_t)qu.size() - 1; i >= 0; i--){ + ret[i] = data[qu.top().i]; + qu.pop(); + } + return ret; +} + +TEST(VP_Tree, "A little bit slow"){ + int t0, t1, t2; + + meow::VP_Tree<MyVector, lnt> tree(D); + + meow::messagePrintf(1, "Create data (N = %d, D = %d)", N, D); + data.resize(N); + for(int i = 0; i < N; i++){ + if(i <= N / 10) + data[i] = MyVector((lnt)i); + else{ + for(int j = 0; j < D; j++){ + data[i][j] = rand() % MAX; + } + } + } + for(int i = 0; i < N; i++){ + data[i].w = i; + } + for(int i = 0; i < N; i++){ + tree.insert(data[i]); + } + meow::messagePrintf(-1, "ok"); + meow::messagePrintf(1, "build"); + t0 = clock(); + tree.build(); + //tree.print(); + meow::messagePrintf(-1, "ok, %.3f seconds", (clock() - t0) * 1.0 / CLOCKS_PER_SEC); + + meow::messagePrintf(1, "query..."); + meow::KD_Tree<MyVector, lnt>::Vectors ret1, ret2; + for(int k = 1; k <= std::min(100, N); k++){ + meow::messagePrintf(1, "range k = %d", k); + t1 = t2 = 0; + for(int i = 0; i < 10; i++){ + MyVector ask; + + t0 = clock(); + tree.build(); + ret1 = tree.query(ask, k, true); + t1 += clock() - t0; + + t0 = clock(); + ret2 = find(ask, k); + t2 += clock() - t0; + + if(ret1.size() != ret2.size() && false){ + meow::messagePrintf(-1, "(%d)query fail, size error", i); + meow::messagePrintf(-1, "fail"); + return false; + } + for(int kk = 0, KK = ret1.size(); kk < KK; kk++){ + if(ret1[kk] == ret2[kk]){ + continue; + } + show(ask, ret1, ret2); + meow::messagePrintf(-1, "(%d)query fail", i); + meow::messagePrintf(-1, "fail"); + return false; + } + } + meow::messagePrintf(-1, "ok %.3f/%.3f", + t1 * 1.0 / CLOCKS_PER_SEC, + t2 * 1.0 / CLOCKS_PER_SEC + ); + } + meow::messagePrintf(-1, "ok"); + + + return true; +}; +; diff --git a/meowpp.test/src/dsa.cpp b/meowpp.test/src/dsa.cpp new file mode 100644 index 0000000..c380098 --- /dev/null +++ b/meowpp.test/src/dsa.cpp @@ -0,0 +1,84 @@ +#include "meowpp.h" + +#include <vector> +#include <string> +#include <cstdlib> +#include <ctime> + +#include "meowpp/Usage.h" + +//////////////////////////// +meow::Usage usg("meowpp"), usg2; +int count = 0; +//////////////////////// + +int main(int argc, char** argv){ + std::vector<std::string> ids(meow::ObjSelector<0>::lst()); + usg2.addOption('t', "Select which subject to test", + "<number>", "", + false); + for(size_t i = 0; i < ids.size(); i++){ + TestFunction* tmp = (TestFunction*)meow::ObjSelector<0>::get(ids[i]); + usg2.addOptionValueAccept('t', ids[i], tmp->name() + ", " + tmp->description()); + delete tmp; + } + + usg.addOption('h', "Display this help document"); + usg.addUsageBegin("<name> is a little test program to check whether" + "the data structures in the template is correct by" + "random generate lots of data to test"); + usg.addUsageEnd ("zzzzzzzzzzzzzzz...."); + usg.import(usg2); + + std::string err; + if(usg.setArguments(argc, argv, &err) == false){ + printf("%s\n\n%s\n", err.c_str(), usg.getUsage().c_str()); + return 1; + }else if(usg.hasOptionSetup('h')){ + printf("%s", usg.getUsage().c_str()); + return 0; + }else{ + usg2.update(usg); + if(usg2.getOptionValuesCount('t') > 0){ + for(int i = 0, I = usg2.getOptionValuesCount('t'); i < I; i++){ + std::string wh = usg2.getOptionValue('t', i); + TestFunction* f = (TestFunction*)meow::ObjSelector<0>::get(wh); + if(f->run() == false){ + printf("error occure on %s\n", f->name().c_str()); + return 1; + }else{ + printf("%s success\n", f->name().c_str()); + } + delete f; + } + }else{ + while(true){ + for(int i = 0, I = ids.size(); i < I; i++){ + TestFunction* tmp = (TestFunction*)meow::ObjSelector<0>::get(ids[i]); + printf(" %s) %s\n", ids[i].c_str(), tmp->name().c_str()); + delete tmp; + } + printf("please select(EOF to quit): "); + int id; + if(!~scanf("%d", &id)){ + break; + } + printf("\n"); + TestFunction* f = (TestFunction*)meow::ObjSelector<0>::get(meow::stringPrintf("%d", id)); + if(f == NULL){ + printf("Bad value!\n\n"); + continue; + } + if(f->run() == false){ + printf("error occure on %s\n", f->name().c_str()); + return 1; + }else{ + printf("%s success\n", f->name().c_str()); + } + delete f; + } + printf("\n"); + } + } + return 0; +} |