From 72d4af22710317acffab861421c4364b1780b6fe Mon Sep 17 00:00:00 2001 From: Charles McGarvey Date: Fri, 21 Aug 2009 00:13:20 -0600 Subject: [PATCH] initial working frustum culling implementation --- configure.ac | 4 +- data/scenes/Test.json | 2 +- src/Makefile.am | 6 + src/Moof/Aabb.cc | 83 +- src/Moof/Aabb.hh | 31 + src/Moof/Camera.cc | 49 +- src/Moof/Camera.hh | 18 +- src/Moof/Engine.cc | 12 +- src/Moof/Engine.hh | 2 +- src/Moof/Entity.hh | 20 +- src/Moof/Frustum.cc | 109 ++ src/Moof/Frustum.hh | 26 +- src/Moof/Hash.cc | 104 ++ src/Moof/Hash.hh | 56 + src/Moof/Math.hh | 2 +- src/Moof/Mippleton.hh | 31 +- src/Moof/Octree.hh | 298 ++++- src/Moof/Plane.cc | 70 ++ src/Moof/Plane.hh | 50 +- src/Moof/Scene.cc | 88 +- src/Moof/Scene.hh | 6 +- src/Moof/Sphere.cc | 55 + src/Moof/Sphere.hh | 77 ++ src/Moof/Texture.cc | 9 +- src/Moof/Texture.hh | 2 + src/Moof/Tree.hh | 231 +++- src/Moof/stlplus/containers.hpp | 23 + src/Moof/stlplus/containers_fixes.hpp | 133 +++ src/Moof/stlplus/digraph.hpp | 507 +++++++++ src/Moof/stlplus/digraph.tpp | 1483 +++++++++++++++++++++++++ src/Moof/stlplus/exceptions.hpp | 71 ++ src/Moof/stlplus/foursome.hpp | 59 + src/Moof/stlplus/foursome.tpp | 59 + src/Moof/stlplus/hash.hpp | 196 ++++ src/Moof/stlplus/hash.tpp | 575 ++++++++++ src/Moof/stlplus/matrix.hpp | 62 ++ src/Moof/stlplus/matrix.tpp | 215 ++++ src/Moof/stlplus/ntree.hpp | 364 ++++++ src/Moof/stlplus/ntree.tpp | 913 +++++++++++++++ src/Moof/stlplus/safe_iterator.hpp | 155 +++ src/Moof/stlplus/safe_iterator.tpp | 373 +++++++ src/Moof/stlplus/smart_ptr.hpp | 256 +++++ src/Moof/stlplus/smart_ptr.tpp | 343 ++++++ src/Moof/stlplus/triple.hpp | 54 + src/Moof/stlplus/triple.tpp | 56 + src/YoinkApp.cc | 61 +- 46 files changed, 7242 insertions(+), 157 deletions(-) create mode 100644 src/Moof/Frustum.cc create mode 100644 src/Moof/Hash.cc create mode 100644 src/Moof/Hash.hh create mode 100644 src/Moof/Plane.cc create mode 100644 src/Moof/Sphere.cc create mode 100644 src/Moof/Sphere.hh create mode 100755 src/Moof/stlplus/containers.hpp create mode 100755 src/Moof/stlplus/containers_fixes.hpp create mode 100755 src/Moof/stlplus/digraph.hpp create mode 100755 src/Moof/stlplus/digraph.tpp create mode 100755 src/Moof/stlplus/exceptions.hpp create mode 100755 src/Moof/stlplus/foursome.hpp create mode 100755 src/Moof/stlplus/foursome.tpp create mode 100755 src/Moof/stlplus/hash.hpp create mode 100755 src/Moof/stlplus/hash.tpp create mode 100755 src/Moof/stlplus/matrix.hpp create mode 100755 src/Moof/stlplus/matrix.tpp create mode 100755 src/Moof/stlplus/ntree.hpp create mode 100755 src/Moof/stlplus/ntree.tpp create mode 100755 src/Moof/stlplus/safe_iterator.hpp create mode 100755 src/Moof/stlplus/safe_iterator.tpp create mode 100755 src/Moof/stlplus/smart_ptr.hpp create mode 100755 src/Moof/stlplus/smart_ptr.tpp create mode 100755 src/Moof/stlplus/triple.hpp create mode 100755 src/Moof/stlplus/triple.tpp diff --git a/configure.ac b/configure.ac index 7884e48..e8d8d9b 100644 --- a/configure.ac +++ b/configure.ac @@ -39,8 +39,8 @@ AC_ARG_ENABLE([debug], [debug=$enableval if test x$debug = xyes then - CFLAGS="-Wall -Werror -g -O0 -DDEBUG" - CXXFLAGS="-Wall -Werror -g -O0 -DDEBUG" + CFLAGS="-Wall -Werror -gstabs+ -O0 -DDEBUG" + CXXFLAGS="-Wall -Werror -gstabs+ -O0 -DDEBUG" else CFLAGS="-O2 -DNDEBUG" CXXFLAGS="-O2 -DNDEBUG" diff --git a/data/scenes/Test.json b/data/scenes/Test.json index 562a3be..db9ba5d 100644 --- a/data/scenes/Test.json +++ b/data/scenes/Test.json @@ -1,6 +1,6 @@ { "playfield_bounds": [0, 0, -100, 1280, 500, 100], - "maximum_bounds": [-160, 0, -192, 1440, 512, 224], + "maximum_bounds": [-165, -5, -197, 1445, 517, 229], "instructions": [ diff --git a/src/Makefile.am b/src/Makefile.am index 62c10ca..1d320e6 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -20,13 +20,17 @@ libmoof_la_SOURCES = \ Moof/Engine.hh \ Moof/Entity.hh \ Moof/Event.hh \ + Moof/Frustum.cc \ Moof/Frustum.hh \ + Moof/Hash.cc \ + Moof/Hash.hh \ Moof/Interpolator.hh \ Moof/Math.hh \ Moof/Mippleton.hh \ Moof/Octree.hh \ Moof/OpenGL.cc \ Moof/OpenGL.hh \ + Moof/Plane.cc \ Moof/Plane.hh \ Moof/Profiler.hh \ Moof/Random.cc \ @@ -42,6 +46,8 @@ libmoof_la_SOURCES = \ Moof/Settings.cc \ Moof/Settings.hh \ Moof/Singleton.hh \ + Moof/Sphere.cc \ + Moof/Sphere.hh \ Moof/StringTools.cc \ Moof/StringTools.hh \ Moof/Texture.cc \ diff --git a/src/Moof/Aabb.cc b/src/Moof/Aabb.cc index d81c971..c844251 100644 --- a/src/Moof/Aabb.cc +++ b/src/Moof/Aabb.cc @@ -28,11 +28,83 @@ #include #include +#include +#include namespace Mf { +void Aabb::getOctant(Aabb& octant, int num) const +{ + Vector3 mid = getCenter(); + + switch (num) + { + case 0: + octant.init(Vector3(min[0], min[1], mid[2]), + Vector3(mid[0], mid[1], max[2])); + break; + case 1: + octant.init(Vector3(mid[0], min[1], mid[2]), + Vector3(max[0], mid[1], max[2])); + break; + case 2: + octant.init(mid, max); + break; + case 3: + octant.init(Vector3(min[0], mid[1], mid[2]), + Vector3(mid[0], max[1], max[2])); + break; + case 4: + octant.init(min, mid); + break; + case 5: + octant.init(Vector3(mid[0], min[1], min[2]), + Vector3(max[0], mid[1], mid[2])); + break; + case 6: + octant.init(Vector3(mid[0], mid[1], min[2]), + Vector3(max[0], max[1], mid[2])); + break; + case 7: + octant.init(Vector3(min[0], mid[1], min[2]), + Vector3(mid[0], max[1], mid[2])); + break; + } +} + + +void Aabb::getCorners(Vector3 corners[8]) const +{ + corners[0][0] = min[0]; corners[0][1] = min[1]; corners[0][2] = max[2]; + corners[1][0] = max[0]; corners[1][1] = min[1]; corners[1][2] = max[2]; + corners[2][0] = max[0]; corners[2][1] = max[1]; corners[2][2] = max[2]; + corners[3][0] = min[0]; corners[3][1] = max[1]; corners[3][2] = max[2]; + corners[4][0] = min[0]; corners[4][1] = min[1]; corners[4][2] = min[2]; + corners[5][0] = max[0]; corners[5][1] = min[1]; corners[5][2] = min[2]; + corners[6][0] = max[0]; corners[6][1] = max[1]; corners[6][2] = min[2]; + corners[7][0] = min[0]; corners[7][1] = max[1]; corners[7][2] = min[2]; +} + + +void Aabb::encloseVertices(const Vector3 vertices[], unsigned count) +{ + min = vertices[0]; + max = vertices[0]; + + for (unsigned i = 1; i < count; ++i) + { + if (vertices[i][0] < min[0]) min[0] = vertices[i][0]; + if (vertices[i][0] > max[0]) max[0] = vertices[i][0]; + if (vertices[i][1] < min[1]) min[1] = vertices[i][1]; + if (vertices[i][1] > max[1]) max[1] = vertices[i][1]; + if (vertices[i][2] < min[2]) min[2] = vertices[i][2]; + if (vertices[i][2] > max[2]) max[2] = vertices[i][2]; + } +} + + void Aabb::draw(Scalar alpha) const { Scalar vertices[] = {min[0], min[1], min[2], @@ -52,14 +124,23 @@ void Aabb::draw(Scalar alpha) const 4, 5, 6, 7}; glEnableClientState(GL_VERTEX_ARRAY); + glDisableClientState(GL_TEXTURE_COORD_ARRAY); glVertexPointer(3, GL_SCALAR, 0, vertices); + glPolygonMode(GL_FRONT_AND_BACK, GL_LINE); + Texture::resetBind(); + glDrawElements(GL_QUADS, sizeof(indices), GL_UNSIGNED_BYTE, indices); + + glEnableClientState(GL_TEXTURE_COORD_ARRAY); + //glDisableClientState(GL_VERTEX_ARRAY); + + glPolygonMode(GL_FRONT_AND_BACK, GL_FILL); } bool Aabb::isVisible(const Camera& cam) const { - return cam.getFrustum().checkAabb(*this); + return cam.getFrustum().containsAabb(*this); } diff --git a/src/Moof/Aabb.hh b/src/Moof/Aabb.hh index f51531a..457d198 100644 --- a/src/Moof/Aabb.hh +++ b/src/Moof/Aabb.hh @@ -32,6 +32,7 @@ #include #include #include +#include namespace Mf { @@ -104,6 +105,36 @@ struct Aabb : public Cullable, public Drawable (min[2] + max[2]) / 2.0); } + void getOctant(Aabb& octant, int num) const; + + inline Plane getPlaneXY() const + { + Plane plane; + plane.normal = Vector3(0.0, 0.0, 1.0); + plane.d = cml::dot(-plane.normal, getCenter()); + return plane; + } + + inline Plane getPlaneXZ() const + { + Plane plane; + plane.normal = Vector3(0.0, 1.0, 0.0); + plane.d = cml::dot(-plane.normal, getCenter()); + return plane; + } + + inline Plane getPlaneYZ() const + { + Plane plane; + plane.normal = Vector3(1.0, 0.0, 0.0); + plane.d = cml::dot(-plane.normal, getCenter()); + return plane; + } + + void getCorners(Vector3 corners[8]) const; + + void encloseVertices(const Vector3 vertices[], unsigned count); + void draw(Scalar alpha = 0.0) const; bool isVisible(const Camera& cam) const; }; diff --git a/src/Moof/Camera.cc b/src/Moof/Camera.cc index 26e24ba..cdebc7a 100644 --- a/src/Moof/Camera.cc +++ b/src/Moof/Camera.cc @@ -28,6 +28,7 @@ #include #include +#include namespace Mf { @@ -35,31 +36,47 @@ namespace Mf { void Camera::setPosition(const Vector3& point) { - //position_ = point; - Vector3 coeff[2] = {position_, point}; - pInterp_.init(coeff, 0.1); + position_ = point; + //Vector3 coeff[2] = {position_, point}; + //pInterp_.init(coeff, 0.1); } void Camera::setRotation(const Quaternion& rotation) { rotation_ = rotation; - //srcRotation_ = rotation_; - //dstRotation_ = rotation; - //tInterp_ = 0.0; } -void Camera::update(Scalar t, Scalar dt) + +void Camera::setProjection(const Matrix4& projection) { - pInterp_.update(dt); - position_ = pInterp_.getState(0.0); + projection_ = projection; +} - //tInterp_ += dt * 10.0; - //rotation_ = cml::slerp(srcRotation_, dstRotation_, cml::clamp(tInterp_, 0.0, 1.0)); - //rotation_.normalize(); +void Camera::setProjection(Scalar fovy, Scalar aspect, Scalar near, Scalar far) +{ + cml::matrix_perspective_yfov_RH(projection_, fovy, aspect, near, far, + cml::z_clip_neg_one); calculateSecondary(); } +void Camera::uploadProjectionToGL() const +{ + glMatrixMode(GL_PROJECTION); + glLoadMatrix(projection_.data()); + + glMatrixMode(GL_MODELVIEW); +} + +void Camera::update(Scalar t, Scalar dt) +{ + //pInterp_.update(dt); + //position_ = pInterp_.getState(0.0); + + //calculateSecondary(); +} + + void Camera::lookAt(const Vector3& point) { quaternion_rotation_aim_at(rotation_, position_, point); @@ -150,13 +167,15 @@ void Camera::adjustFromInput(const Event& event) void Camera::calculateSecondary() { - matrix_rotation_quaternion(transformation_, rotation_); + matrix_rotation_quaternion(modelview_, rotation_); Matrix4 translate; matrix_translation(translate, position_); - //transformation_ = translate * transformation_; - transformation_ *= translate; + //modelview_ = translate * modelview_; + modelview_ *= translate; + + frustum_.init(modelview_, projection_); } diff --git a/src/Moof/Camera.hh b/src/Moof/Camera.hh index 0aa5dc9..63d0074 100644 --- a/src/Moof/Camera.hh +++ b/src/Moof/Camera.hh @@ -47,19 +47,22 @@ public: position_(0.0, 0.0, 0.0) { quaternion_rotation_world_y(rotation_, 0.0); - srcRotation_ = rotation_; - dstRotation_ = rotation_; calculateSecondary(); } void setPosition(const Vector3& point); void setRotation(const Quaternion& rotation); + void setProjection(const Matrix4& projection); + void setProjection(Scalar fovy, Scalar aspect, Scalar near, Scalar far); + + void uploadProjectionToGL() const; + void lookAt(const Vector3& point); - const Matrix4& getTransformation() const + const Matrix4& getModelviewMatrix() const { - return transformation_; + return modelview_; } const Frustum& getFrustum() const @@ -73,15 +76,12 @@ public: private: Vector3 position_; Quaternion rotation_; + Matrix4 projection_; - Matrix4 transformation_; + Matrix4 modelview_; Frustum frustum_; Lerpv3 pInterp_; - - Quaternion srcRotation_; - Quaternion dstRotation_; - Scalar tInterp_; }; diff --git a/src/Moof/Engine.cc b/src/Moof/Engine.cc index be8ca5f..53fca73 100644 --- a/src/Moof/Engine.cc +++ b/src/Moof/Engine.cc @@ -103,7 +103,7 @@ public: * The main loop. This just calls dispatchEvents(), update(), and draw() * over and over again. The timing of the update and draw are decoupled. * The actual frame rate is also calculated here. This function will return - * with a value of 0 if the member variable running becomes true. + * the exit code used to stop the loop. */ int run() @@ -141,6 +141,10 @@ public: nextStep += timestep; } + if (ticksNow >= nextStep) + { + nextStep = ticksNow + timestep; + } if (ticksNow >= nextDraw) { @@ -179,7 +183,7 @@ public: } while (running); - return 0; + return exitCode; } @@ -216,6 +220,7 @@ public: VideoPtr video; bool running; + int exitCode; Scalar timestep; Scalar drawRate; @@ -238,9 +243,10 @@ int Engine::run() return impl_->run(); } -void Engine::stop() +void Engine::stop(int exitCode) { impl_->running = false; + impl_->exitCode = exitCode; } diff --git a/src/Moof/Engine.hh b/src/Moof/Engine.hh index 2d7dfd6..76120c4 100644 --- a/src/Moof/Engine.hh +++ b/src/Moof/Engine.hh @@ -53,7 +53,7 @@ public: virtual ~Engine(); int run(); - void stop(); + void stop(int exitCode = 0); void setTimestep(Scalar ts); Scalar getTimestep(); diff --git a/src/Moof/Entity.hh b/src/Moof/Entity.hh index 7595054..f593d0c 100644 --- a/src/Moof/Entity.hh +++ b/src/Moof/Entity.hh @@ -34,26 +34,42 @@ #include #include #include +#include namespace Mf { +class Camera; + /** - * Interface for game objects that can be drawn to the screen and half a + * Interface for game objects that can be drawn to the screen and have a * specified size. */ class Entity : public Drawable, public Cullable { public: + inline virtual ~Entity() {} + const Aabb& getAabb() const { return aabb_; } + const Sphere& getSphere() const + { + return sphere_; + } + + virtual void drawIfVisible(Scalar alpha, const Camera& cam) const + { + if (isVisible(cam)) draw(alpha); + } + protected: - Aabb aabb_; + Aabb aabb_; + Sphere sphere_; }; typedef boost::shared_ptr EntityPtr; diff --git a/src/Moof/Frustum.cc b/src/Moof/Frustum.cc new file mode 100644 index 0000000..4dc6340 --- /dev/null +++ b/src/Moof/Frustum.cc @@ -0,0 +1,109 @@ + +/******************************************************************************* + + Copyright (c) 2009, Charles McGarvey + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +*******************************************************************************/ + +#include +#include +#include + + +namespace Mf { + + +void Frustum::init(const Matrix4& modelview, const Matrix4& projection) +{ + Scalar planes[6][4]; + + cml::extract_frustum_planes(modelview, projection, planes, + cml::z_clip_neg_one); + + planes_[0] = Plane(planes[0][0], planes[0][1], planes[0][2], planes[0][3]); + planes_[1] = Plane(planes[1][0], planes[1][1], planes[1][2], planes[1][3]); + planes_[2] = Plane(planes[2][0], planes[2][1], planes[2][2], planes[2][3]); + planes_[3] = Plane(planes[3][0], planes[3][1], planes[3][2], planes[3][3]); + planes_[4] = Plane(planes[4][0], planes[4][1], planes[4][2], planes[4][3]); + planes_[5] = Plane(planes[5][0], planes[5][1], planes[5][2], planes[5][3]); +} + +void Frustum::init(const Matrix4& modelview, Scalar fovy, Scalar aspect, + Scalar near, Scalar far) +{ + Matrix4 projection; + + cml::matrix_perspective_yfov_RH(projection, fovy, aspect, near, far, + cml::z_clip_neg_one); + + init(modelview, projection); +} + +Frustum::Collision Frustum::containsAabb(const Aabb& aabb) const +{ + Vector3 corners[8]; + int nTotalInside = 0; + + aabb.getCorners(corners); + + for (int i = 0; i < 6; ++i) + { + int nInside = 8; + + for (int j = 0; j < 8; ++j) + { + if (planes_[i].intersectsPoint(corners[j]) == + Plane::NEGATIVE) + { + --nInside; + } + } + + if (nInside == 0) return OUTSIDE; + else if (nInside == 8) ++nTotalInside; + } + + if (nTotalInside == 6) return INSIDE; + else return INTERSECT; +} + + +Frustum::Collision Frustum::containsSphere(const Sphere& sphere) const +{ + for (int i = 0; i < 6; ++i) + { + Plane::Halfspace halfspace = planes_[i].intersectsSphere(sphere); + + if (halfspace == Plane::NEGATIVE) return OUTSIDE; + else if (halfspace == Plane::INTERSECT) return INTERSECT; + } + + return INSIDE; +} + + +} // namespace Mf + +/** vim: set ts=4 sw=4 tw=80: *************************************************/ + diff --git a/src/Moof/Frustum.hh b/src/Moof/Frustum.hh index ac2b353..a50dc83 100644 --- a/src/Moof/Frustum.hh +++ b/src/Moof/Frustum.hh @@ -29,6 +29,7 @@ #ifndef _MOOF_FRUSTUM_HH_ #define _MOOF_FRUSTUM_HH_ +#include #include @@ -36,11 +37,11 @@ namespace Mf { class Aabb; +class Sphere; class Frustum { - //Matrix4 projection; - Plane left, right, bottom, top, near, far; + Plane planes_[6]; // left, right, bottom, top, near, far public: typedef enum @@ -50,16 +51,23 @@ public: INTERSECT = 2 } Collision; - //Frustum() {} - //Frustum(Scalar l, Scalar r, Scalar b, Scalar t, Scalar n, Scalar f); - //Frustum(Scalar fovy, Scalar aspect, Scalar near, Scalar far); - - inline Collision checkAabb(const Aabb& aabb) const + Frustum() {} + inline Frustum(const Matrix4& modelview, const Matrix4& projection) + { + init(modelview, projection); + } + inline Frustum(const Matrix4& modelview, Scalar fovy, Scalar aspect, + Scalar near, Scalar far) { - return INSIDE; + init(modelview, fovy, aspect, near, far); } + + void init(const Matrix4& modelview, const Matrix4& projection); + void init(const Matrix4& modelview, Scalar fovy, Scalar aspect, Scalar near, + Scalar far); - //const Matrix4& getMatrix() const; + Collision containsAabb(const Aabb& aabb) const; + Collision containsSphere(const Sphere& sphere) const; }; diff --git a/src/Moof/Hash.cc b/src/Moof/Hash.cc new file mode 100644 index 0000000..457c353 --- /dev/null +++ b/src/Moof/Hash.cc @@ -0,0 +1,104 @@ + +/******************************************************************************* + + Copyright (c) 2009, Charles McGarvey + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +*******************************************************************************/ + +#include "Hash.hh" + + +namespace Mf { + + +//----------------------------------------------------------------------------- +// MurmurHash2, by Austin Appleby + +// Note - This code makes a few assumptions about how your machine behaves - + +// 1. We can read a 4-byte value from any address without crashing +// 2. sizeof(int) == 4 + +// And it has a few limitations - + +// 1. It will not work incrementally. +// 2. It will not produce the same results on little-endian and big-endian +// machines. + +unsigned int MurmurHash2_(const void* key, int len, unsigned int seed) +{ + // 'm' and 'r' are mixing constants generated offline. + // They're not really 'magic', they just happen to work well. + + const unsigned int m = 0x5bd1e995; + const int r = 24; + + // Initialize the hash to a 'random' value + + unsigned int h = seed ^ len; + + // Mix 4 bytes at a time into the hash + + const unsigned char* data = (const unsigned char*)key; + + while (len >= 4) + { + unsigned int k = *(unsigned int*)data; + + k *= m; + k ^= k >> r; + k *= m; + + h *= m; + h ^= k; + + data += 4; + len -= 4; + } + + // Handle the last few bytes of the input array + + switch (len) + { + case 3: h ^= data[2] << 16; + case 2: h ^= data[1] << 8; + case 1: h ^= data[0]; + h *= m; + }; + + // Do a few final mixes of the hash to ensure the last few + // bytes are well-incorporated. + + h ^= h >> 13; + h *= m; + h ^= h >> 15; + + return h; +} + + +} // namespace Mf + +/** vim: set ts=4 sw=4 tw=80: *************************************************/ + diff --git a/src/Moof/Hash.hh b/src/Moof/Hash.hh new file mode 100644 index 0000000..c069544 --- /dev/null +++ b/src/Moof/Hash.hh @@ -0,0 +1,56 @@ + +/******************************************************************************* + + Copyright (c) 2009, Charles McGarvey + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +*******************************************************************************/ + +#ifndef _MOOF_HASH_HH_ +#define _MOOF_HASH_HH_ + +#include + +#include + + +namespace Mf { + + +unsigned MurmurHash2_(const void* key, int len, unsigned seed); + +struct hash_string +{ + inline unsigned operator()(const std::string& val) const + { + return MurmurHash2_(val.data(), val.length(), -1); + } +}; + + +} // namespace Mf + +#endif // _MOOF_HASH_HH_ + +/** vim: set ts=4 sw=4 tw=80: *************************************************/ + diff --git a/src/Moof/Math.hh b/src/Moof/Math.hh index 4e1cda8..26c4b51 100644 --- a/src/Moof/Math.hh +++ b/src/Moof/Math.hh @@ -85,7 +85,7 @@ const Scalar EPSILON = 0.000001; * Check the equality of scalars with a certain degree of error allowed. */ -inline bool checkEquality(Scalar a, Scalar b, Scalar epsilon = EPSILON) +inline bool isEqual(Scalar a, Scalar b, Scalar epsilon = EPSILON) { return std::abs(a - b) < epsilon; } diff --git a/src/Moof/Mippleton.hh b/src/Moof/Mippleton.hh index 95d3f21..7058ecc 100644 --- a/src/Moof/Mippleton.hh +++ b/src/Moof/Mippleton.hh @@ -38,25 +38,26 @@ * after the last interested code releases its hold on the object. */ -#include +#include #include - namespace Mf { template class Mippleton { - typedef std::pair ptr_value_t; - typedef std::pair ptr_map_pair_t; - typedef std::map ptr_map_t; + typedef std::pair ptr_value_t; + typedef std::pair ptr_map_pair_t; + typedef stlplus::hash ptr_map_t; + //typedef std::map ptr_map_t; - static ptr_map_t ptrs_; - std::string name_; + static ptr_map_t ptrs_; + std::string name_; public: - explicit Mippleton(const std::string& name) : name_(name) {} + explicit Mippleton(const std::string& name) : + name_(name) {} inline const std::string& getName() const { @@ -65,11 +66,11 @@ public: inline static T* retain(const std::string& name) { - typename ptr_map_t::iterator it; + typename ptr_map_t::iterator it = ptrs_.find(name); - if ((it = ptrs_.find(name)) != ptrs_.end()) + if (it != ptrs_.end()) { - (*it).second.first++; + ++((*it).second.first); return (*it).second.second; } else @@ -84,10 +85,10 @@ public: { typename ptr_map_t::iterator it; - if ((it = ptrs_.find(name)) != ptrs_.end() && -(*it).second.first == 0) + if ((it = ptrs_.find(name)) != ptrs_.end() && --(*it).second.first == 0) { delete (*it).second.second; - ptrs_.erase(it); + ptrs_.erase((*it).first); } } @@ -98,7 +99,9 @@ public: }; template -std::map > Mippleton::ptrs_; +stlplus::hash< std::string,std::pair,hash_string > +//std::map< std::string,std::pair > + Mippleton::ptrs_; } // namespace Mf diff --git a/src/Moof/Octree.hh b/src/Moof/Octree.hh index 2ee617f..78d3aa8 100644 --- a/src/Moof/Octree.hh +++ b/src/Moof/Octree.hh @@ -33,52 +33,308 @@ #include +#include +#include +#include #include +#include #include namespace Mf { -class Entity; +struct OctreeNode : public Entity +{ + std::list objects; + + OctreeNode() + { + aabb_.min = Vector3(-1.0, -1.0, -1.0); + aabb_.max = Vector3(1.0, 1.0, 1.0); + sphere_.init(Vector3(0.0, 0.0, 0.0), 1.41421); + } + + OctreeNode(const Aabb& aabb) + { + aabb_ = aabb; + sphere_.point = aabb.getCenter(); + sphere_.radius = (aabb.min - sphere_.point).length(); + } + + void draw(Scalar alpha) const + { + std::list::const_iterator it; + + for (it = objects.begin(); it != objects.end(); ++it) + { + (*it)->draw(alpha); + } + if (!objects.empty()) + aabb_.draw(); // temporary + } + + void drawIfVisible(Scalar alpha, const Camera& cam) const + { + std::list::const_iterator it; + + for (it = objects.begin(); it != objects.end(); ++it) + { + (*it)->drawIfVisible(alpha, cam); + } + if (!objects.empty()) + aabb_.draw(); + } + + bool isVisible(const Camera& cam) const + { + if (sphere_.isVisible(cam)) + { + return aabb_.isVisible(cam); + } + + return false; + } +}; -class Octree + +class Octree; +typedef boost::shared_ptr OctreePtr; + +class Octree : public Tree { + + Octree() {} + + explicit Octree(const OctreeNode& initNode) : + Tree(initNode) {} + public: - class Node + inline static OctreePtr createNewNode(const OctreeNode& item) + { + OctreePtr newNode = OctreePtr(new Octree(item)); + init(newNode); + return newNode; + } + + + static Tree::WeakPtr add(Ptr node, EntityPtr entity) { - Aabb aabb_; - Vector3 center_; + Plane::Halfspace halfspace; + int octantNum = -1; + + Plane xy = node->node.getAabb().getPlaneXY(); + halfspace = xy.intersectsSphere(entity->getSphere()); - std::list > objects_; + if (halfspace == Plane::POSITIVE) + { + Plane xz = node->node.getAabb().getPlaneXZ(); + halfspace = xz.intersectsSphere(entity->getSphere()); - public: + if (halfspace == Plane::POSITIVE) + { + Plane yz = node->node.getAabb().getPlaneYZ(); + halfspace = yz.intersectsSphere(entity->getSphere()); - Node() : - aabb_(-1.0, -1.0, -1.0, 1.0, 1.0, 1.0), - center_(0.0, 0.0, 0.0) {} + if (halfspace == Plane::POSITIVE) + { + octantNum = 2; + } + else if (halfspace == Plane::NEGATIVE) + { + octantNum = 3; + } + } + else if (halfspace == Plane::NEGATIVE) + { + Plane yz = node->node.getAabb().getPlaneYZ(); + halfspace = yz.intersectsSphere(entity->getSphere()); - Node(const Aabb& aabb) : - aabb_(aabb), - center_(aabb.getCenter()) {} - }; + if (halfspace == Plane::POSITIVE) + { + octantNum = 1; + } + else if (halfspace == Plane::NEGATIVE) + { + octantNum = 0; + } + } + } + else if (halfspace == Plane::NEGATIVE) + { + Plane xz = node->node.getAabb().getPlaneXZ(); + halfspace = xz.intersectsSphere(entity->getSphere()); - Octree() : - root_(new Tree()) {} + if (halfspace == Plane::POSITIVE) + { + Plane yz = node->node.getAabb().getPlaneYZ(); + halfspace = yz.intersectsSphere(entity->getSphere()); - Octree(const Aabb& aabb) : - root_(new Tree(Node(aabb))) {} + if (halfspace == Plane::POSITIVE) + { + octantNum = 6; + } + else if (halfspace == Plane::NEGATIVE) + { + octantNum = 7; + } + } + else if (halfspace == Plane::NEGATIVE) + { + Plane yz = node->node.getAabb().getPlaneYZ(); + halfspace = yz.intersectsSphere(entity->getSphere()); + if (halfspace == Plane::POSITIVE) + { + octantNum = 5; + } + else if (halfspace == Plane::NEGATIVE) + { + octantNum = 4; + } + } + } - Tree::WeakPtr add(EntityPtr object); + if (octantNum == -1) + { + node->node.objects.push_front(entity); + return node; + } + else + { + if (node->isLeaf()) + { + addChildren(node); + } + + Ptr child = node->getChild(octantNum); + if (child) + { + return add(child, entity); + } + else + { + std::cerr << "no child at index " << octantNum << std::endl; + return Ptr(); + } + //return WeakPtr(); + } + } + + static void addChildren(Ptr node) + { + Aabb octant; + + for (int i = 0; i < 8; ++i) + { + node->node.getAabb().getOctant(octant, i); + //OctreeNode octantNode(octant); + + Ptr newChild = createNewNode(octant); + node->addChild(newChild); + } + } + + void draw(Ptr node, Scalar alpha) + { + if (!node) + { + std::cerr << "null child :-(" << std::endl; + return; + } + + node->node.draw(alpha); + + if (!node->isLeaf()) + { + Ptr firstChild = node->getFirstChild(); + Ptr temp = firstChild; + + if (!firstChild) + { + std::cerr << "node is not a leaf, but has no first child :-(" << std::endl; + return; + } + + do + { + draw(temp, alpha); + temp = temp->getNextSibling(); + } + while (temp && temp != firstChild); + } + } + + void drawIfVisible(Ptr node, Scalar alpha, const Camera& cam) + { + //node.drawIfVisible(alpha, cam); + + if (!node) + { + std::cerr << "null child :-(" << std::endl; + return; + } + + Frustum::Collision collision = + cam.getFrustum().containsSphere(node->node.getSphere()); + if (collision == Frustum::OUTSIDE) return; + + collision = cam.getFrustum().containsAabb(node->node.getAabb()); + if (collision == Frustum::OUTSIDE) return; + + + if (collision == Frustum::INSIDE) + { + node->node.draw(alpha); + } + else // collision == Frustum::INTERSECT + { + node->node.drawIfVisible(alpha, cam); + } + + if (!node->isLeaf()) + { + Ptr firstChild = node->getFirstChild(); + Ptr temp = firstChild; + + if (!firstChild) + { + std::cerr << "node is not a leaf, but has no first child :-(" << std::endl; + return; + } + + if (collision == Frustum::INSIDE) + { + do + { + draw(temp, alpha); + temp = temp->getNextSibling(); + } + while (temp && temp != firstChild); + } + else // collision == Frustum::INTERSECT + { + do + { + drawIfVisible(temp, alpha, cam); + temp = temp->getNextSibling(); + } + while (temp && temp != firstChild); + } + } + } + + void drawIfVisible(Scalar alpha, const Camera& cam) + { + drawIfVisible(getThis(), alpha, cam); + } -private: - Tree::Ptr root_; }; + } // namespace Mf #endif // _MOOF_OCTREE_HH_ diff --git a/src/Moof/Plane.cc b/src/Moof/Plane.cc new file mode 100644 index 0000000..975ef13 --- /dev/null +++ b/src/Moof/Plane.cc @@ -0,0 +1,70 @@ + +/******************************************************************************* + + Copyright (c) 2009, Charles McGarvey + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +*******************************************************************************/ + +#include "Aabb.hh" +#include "Plane.hh" +#include "Sphere.hh" + + +namespace Mf { + + +Plane::Halfspace Plane::intersectsAabb(const Aabb& aabb) const +{ + Vector3 corners[8]; + int nPositive = 8; + + aabb.getCorners(corners); + + for (int i = 0; i < 8; ++i) + { + if (intersectsPoint(corners[i]) == NEGATIVE) + { + --nPositive; + } + } + + if (nPositive == 0) return NEGATIVE; + else if (nPositive == 8) return POSITIVE; + else return INTERSECT; +} + +Plane::Halfspace Plane::intersectsSphere(const Sphere& sphere) const +{ + Scalar distance = getDistanceToPoint(sphere.point); + + if (distance < -sphere.radius) return NEGATIVE; + else if (distance < sphere.radius) return INTERSECT; + else return POSITIVE; +} + + +} // namespace Mf + +/** vim: set ts=4 sw=4 tw=80: *************************************************/ + diff --git a/src/Moof/Plane.hh b/src/Moof/Plane.hh index 797edc0..248a312 100644 --- a/src/Moof/Plane.hh +++ b/src/Moof/Plane.hh @@ -35,11 +35,55 @@ namespace Mf { -class Plane +class Aabb; +class Sphere; + + +struct Plane { - Vector4 components; + Vector3 normal; + Scalar d; + + typedef enum + { + NEGATIVE = -1, + INTERSECT = 0, + POSITIVE = 1 + } Halfspace; + + Plane() {} + Plane(const Vector3& vector, Scalar scalar) : + normal(vector), + d(scalar) {} + Plane(Scalar a, Scalar b, Scalar c, Scalar scalar) : + normal(a, b, c), + d(scalar) {} + + + void normalize() + { + Scalar mag = normal.length(); + + normal /= mag; + d /= mag; + } + + inline Scalar getDistanceToPoint(const Vector3& point) const + { + return cml::dot(point, normal) + d; + } + + inline Halfspace intersectsPoint(const Vector3& point) const + { + Scalar distance = getDistanceToPoint(point); + + if (isEqual(distance, 0.0)) return INTERSECT; + else if (distance < 0.0) return NEGATIVE; + else return POSITIVE; + } -public: + Halfspace intersectsAabb(const Aabb& aabb) const; + Halfspace intersectsSphere(const Sphere& sphere) const; }; diff --git a/src/Moof/Scene.cc b/src/Moof/Scene.cc index adec6ec..85e5be7 100644 --- a/src/Moof/Scene.cc +++ b/src/Moof/Scene.cc @@ -70,6 +70,10 @@ class Scene::SceneImpl : public Mippleton { std::cerr << "no coords for tile's texture" << std::endl; } + + aabb_.encloseVertices(vertices, 4); + sphere_.point = aabb_.getCenter(); + sphere_.radius = (aabb_.min - sphere_.point).length(); } void setDetail(long detail) @@ -98,34 +102,17 @@ class Scene::SceneImpl : public Mippleton glColor4f(1.0f, 1.0f, 1.0f, 1.0f); tilemap_.bind(); - //glEnableClientState(GL_VERTEX_ARRAY); - //glEnableClientState(GL_TEXTURE_COORD_ARRAY); - - //glVertexPointer(3, GL_SCALAR, 0, vertices_); - //glTexCoordPointer(2, GL_SCALAR, 0, texCoords_); - - //glDrawArrays(GL_TRIANGLE_FAN, 0, sizeof(vertices_)); + glVertexPointer(3, GL_SCALAR, 0, vertices_); + glTexCoordPointer(2, GL_SCALAR, 0, texCoords_); - //glDisableClientState(GL_VERTEX_ARRAY); - //glDisableClientState(GL_TEXTURE_COORD_ARRAY); - - glBegin(GL_TRIANGLE_FAN); - glTexCoord2f(texCoords_[0], texCoords_[1]); - glVertex3v(vertices_); - glTexCoord2f(texCoords_[2], texCoords_[3]); - glVertex3v(vertices_+3); - glTexCoord2f(texCoords_[4], texCoords_[5]); - glVertex3v(vertices_+6); - glTexCoord2f(texCoords_[6], texCoords_[7]); - glVertex3v(vertices_+9); - glEnd(); + glDrawArrays(GL_TRIANGLE_FAN, 0, 4); glDisable(GL_BLEND); } bool isVisible(const Camera& cam) const { - return aabb_.isVisible(cam); + return sphere_.isVisible(cam); } private: @@ -393,7 +380,8 @@ public: Quad* quad = new Quad(quadVertices, texture, indices[h][w]); boost::shared_ptr quadPtr(quad); - objects.push_back(quadPtr); + //objects.push_back(quadPtr); + Octree::add(octree, quadPtr); } } } @@ -473,7 +461,8 @@ public: boost::shared_ptr quadPtr(quad); - objects.push_back(quadPtr); + //objects.push_back(quad_Ptr); + Octree::add(octree, quadPtr); } } @@ -502,6 +491,15 @@ public: { loadBox(maximumBounds, (*it).second); } + else + { + std::cerr << "maximum bounds required in scene" << std::endl; + return; + } + + //OctreeNode rootNode(maximumBounds); + octree = Octree::createNewNode(maximumBounds); + if ((it = rootObj.find("instructions")) != rootObj.end()) { loadInstructions((*it).second); @@ -509,19 +507,36 @@ public: } - void draw(Scalar alpha) + void draw(Scalar alpha, const Camera& cam) const { - QuadVector::iterator it; + //QuadVector::const_iterator it; - for (it = objects.begin(); it != objects.end(); ++it) - { - //std::cout << "draw object"; - (*it)->draw(alpha); - } + glEnableClientState(GL_VERTEX_ARRAY); + glEnableClientState(GL_TEXTURE_COORD_ARRAY); + + octree->drawIfVisible(alpha, cam); + + //int objectsDrawn = 0; + + //for (it = objects.begin(); it != objects.end(); ++it) + //{ + //if ((*it)->isVisible(cam)) + //{ + ////std::cout << "draw object"; + //(*it)->draw(); + + //objectsDrawn++; + //} + //} + + //std::cout << objectsDrawn << std::endl; + + glDisableClientState(GL_VERTEX_ARRAY); + glDisableClientState(GL_TEXTURE_COORD_ARRAY); glPolygonMode(GL_FRONT_AND_BACK, GL_LINE); - glBindTexture(GL_TEXTURE_2D, 0); + Texture::resetBind(); glColor3f(0.0f, 1.0f, 0.0f); playfieldBounds.draw(); glColor3f(0.0f, 0.0f, 1.0f); @@ -534,8 +549,9 @@ public: Aabb playfieldBounds; Aabb maximumBounds; - typedef std::vector< boost::shared_ptr > QuadVector; - QuadVector objects; + //typedef std::vector< boost::shared_ptr > QuadVector; + //QuadVector objects; + OctreePtr octree; }; @@ -544,15 +560,15 @@ Scene::Scene(const std::string& name) : impl_(Scene::SceneImpl::retain(name), &Scene::SceneImpl::release) {} -void Scene::draw(Scalar alpha) const +void Scene::draw(Scalar alpha, const Camera& cam) const { // pass through - impl_->draw(alpha); + impl_->draw(alpha, cam); } void Scene::refresh() { - impl_->objects.clear(); + //impl_->objects.clear(); impl_->loadFromFile(); } diff --git a/src/Moof/Scene.hh b/src/Moof/Scene.hh index db25db7..08ab6cc 100644 --- a/src/Moof/Scene.hh +++ b/src/Moof/Scene.hh @@ -40,12 +40,14 @@ namespace Mf { -class Scene : public Resource, public Drawable +class Camera; + +class Scene : public Resource { public: Scene(const std::string& name); - void draw(Scalar alpha) const; + void draw(Scalar alpha, const Camera& cam) const; void refresh(); static std::string getPathToResource(const std::string& name); diff --git a/src/Moof/Sphere.cc b/src/Moof/Sphere.cc new file mode 100644 index 0000000..352d58d --- /dev/null +++ b/src/Moof/Sphere.cc @@ -0,0 +1,55 @@ + +/******************************************************************************* + + Copyright (c) 2009, Charles McGarvey + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +*******************************************************************************/ + +#include +#include +#include + + +namespace Mf { + + +void Sphere::encloseVertices(const Vector3 vertices[], unsigned count) +{ +} + +void Sphere::draw(Scalar alpha) const +{ + +} + +bool Sphere::isVisible(const Camera& cam) const +{ + return cam.getFrustum().containsSphere(*this); +} + + +} // namespace Mf + +/** vim: set ts=4 sw=4 tw=80: *************************************************/ + diff --git a/src/Moof/Sphere.hh b/src/Moof/Sphere.hh new file mode 100644 index 0000000..b20ca74 --- /dev/null +++ b/src/Moof/Sphere.hh @@ -0,0 +1,77 @@ + +/******************************************************************************* + + Copyright (c) 2009, Charles McGarvey + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +*******************************************************************************/ + +#ifndef _MOOF_SPHERE_HH_ +#define _MOOF_SPHERE_HH_ + +#include +#include +#include + + +namespace Mf { + + +/** + * Axis-aligned Bounding Box + */ + +struct Sphere : public Cullable, public Drawable +{ + Vector3 point; + Scalar radius; + + Sphere() {} + + Sphere(const Vector3& p, Scalar r) : + point(p), + radius(r) {} + + Sphere(Scalar x, Scalar y, Scalar z, Scalar r) : + point(x, y, z), + radius(r) {} + + inline void init(const Vector3& p, Scalar r) + { + point = p; + radius = r; + } + + void encloseVertices(const Vector3 vertices[], unsigned count); + + void draw(Scalar alpha = 0.0) const; + bool isVisible(const Camera& cam) const; +}; + + +} // namespace Mf + +#endif // _MOOF_SPHERE_HH_ + +/** vim: set ts=4 sw=4 tw=80: *************************************************/ + diff --git a/src/Moof/Texture.cc b/src/Moof/Texture.cc index 128d54f..dc9407a 100644 --- a/src/Moof/Texture.cc +++ b/src/Moof/Texture.cc @@ -414,6 +414,13 @@ GLuint Texture::getObject() const } +void Texture::resetBind() +{ + glBindTexture(GL_TEXTURE_2D, 0); + TextureImpl::globalObject_ = 0; +} + + unsigned Texture::getWidth() const { // pass through @@ -454,7 +461,7 @@ void Texture::setWrapT(GLuint wrap) std::string Texture::getPathToResource(const std::string& name) { - // TODO named resources must be png for now + // TODO named texture resources must be png for now return Resource::getPathToResource("textures/" + name + ".png"); } diff --git a/src/Moof/Texture.hh b/src/Moof/Texture.hh index d2b2359..9d17eb8 100644 --- a/src/Moof/Texture.hh +++ b/src/Moof/Texture.hh @@ -53,6 +53,8 @@ public: void bind() const; GLuint getObject() const; + static void resetBind(); + unsigned getWidth() const; unsigned getHeight() const; diff --git a/src/Moof/Tree.hh b/src/Moof/Tree.hh index 2b5fdb8..b3f6a97 100644 --- a/src/Moof/Tree.hh +++ b/src/Moof/Tree.hh @@ -40,50 +40,81 @@ template class Tree { public: - typedef boost::shared_ptr Ptr; - typedef boost::weak_ptr WeakPtr; + typedef boost::shared_ptr Ptr; + typedef boost::weak_ptr WeakPtr; -private: + T node; + +protected: WeakPtr parent_; WeakPtr prevSibling_; Ptr next_; WeakPtr lastDescendant_; + inline static void init(Ptr itself) + { + itself->prevSibling_ = itself; + itself->lastDescendant_ = itself; + } + + Tree() {} + + explicit Tree(const T& item) : + node(item) {} + public: - T data; + inline void print() const + { + std::cout << "==================" << std::endl; + std::cout << " Node: " << getThis() << std::endl; + std::cout << " Parent: " << parent_.lock() << std::endl; + std::cout << " PrevSib: " << prevSibling_.lock() << std::endl; + std::cout << " Next: " << next_ << std::endl; + std::cout << "LastDesc: " << lastDescendant_.lock() << std::endl; + //std::cout << " Value: " << node << std::endl; + std::cout << "==================" << std::endl; + } - Tree() {} - Tree(const T& item) : - data(item) {} + inline static Ptr createNewNode() + { + Ptr newNode = Ptr(new Tree()); + } - inline Ptr next() const + inline static Ptr createNewNode(const T& item) + { + Ptr newNode = Ptr(new Tree(item)); + init(newNode); + return newNode; + } + + inline Ptr getNext() const { return next_; } - inline Ptr prev() const + inline Ptr getPrevious() const { - Ptr parent = parent_.lock(); + Ptr parent = getParent(); if (parent) { - if (parent->next_.get() == this) + if (parent->getNext().get() == this) { return parent; } else { - return prevSibling_.lock()->lastDescendant_.lock(); + return prevSibling_.lock()->getLastDescendant(); } } return Ptr(); } - inline Ptr firstChild() const + inline Ptr getFirstChild() const { - if (next_ && next_->parent_.lock().get() == this) + if (next_ && next_->getParent().get() == this) { return next_; } @@ -91,9 +122,9 @@ public: return Ptr(); } - inline Ptr lastChild() const + inline Ptr getLastChild() const { - Ptr child = firstChild(); + Ptr child = getFirstChild(); if (child) { @@ -103,11 +134,23 @@ public: return child; } - inline Ptr nextSibling() const + inline Ptr getChild(int index) const + { + Ptr child = getFirstChild(); + + for (int i = 0; child && i < index; ++i) + { + child = child->getNextSibling(); + } + + return child; + } + + inline Ptr getNextSibling() const { - Ptr sibling = lastDescendant_.lock()->next_; + Ptr sibling = getLastDescendant()->getNext(); - if (sibling && sibling->parent_.lock() != parent_.lock()) + if (sibling && sibling->getParent() != getParent()) { return Ptr(); } @@ -115,11 +158,11 @@ public: return sibling; } - inline Ptr prevSibling() const + inline Ptr getPreviousSibling() const { - Ptr parent = parent_.lock(); + Ptr parent = getParent(); - if (parent && parent->next_.get() != this) + if (parent && parent->getNext().get() != this) { return prevSibling_.lock(); } @@ -127,6 +170,50 @@ public: return Ptr(); } + inline Ptr getParent() const + { + return parent_.lock(); + } + + inline Ptr getLastDescendant() const + { + return lastDescendant_.lock(); + } + + inline Ptr getThis() const + { + if (next_) + { + return next_->getPrevious(); + } + + return getLastDescendant(); + } + + inline bool isRoot() const + { + return getParent().get() == 0; + } + + inline bool isLeaf() const + { + return getLastDescendant().get() == this; + } + + inline bool isDescendantOf(Ptr ancestor) const + { + Ptr temp = getParent(); + + while (temp) + { + if (temp.get() == this) return true; + + temp = temp->getParent(); + } + + return false; + } + class Iterator { @@ -137,12 +224,110 @@ public: }; - void insert() + void addChild(Ptr subtree) { + //WeakPtr parent_; + //WeakPtr prevSibling_; + //Ptr next_; + //WeakPtr lastDescendant_; + + subtree->remove(); + + Ptr firstChild = getFirstChild(); + Ptr lastChild = getLastChild(); + Ptr nextSibling = getNextSibling(); + Ptr lastDescendant = getLastDescendant(); + Ptr newLastDescendant = subtree->getLastDescendant(); + Ptr parent = getThis(); + + // 1. If parent is leaf, set parent.next to subtree. + + if (isLeaf()) + { + next_ = subtree; + } + + // 2. Set parent.last_descendant to subtree.last_descendant. + + Ptr temp = parent; + while (temp && temp->getLastDescendant() == lastDescendant) + { + temp->lastDescendant_ = newLastDescendant; + temp = temp->getParent(); + } + + // 3. Set subtree.parent to parent. + + subtree->parent_ = parent; + + // 4. Set parent.first_child.prev_sibling to subtree. + + if (firstChild) + { + firstChild->prevSibling_ = subtree; + } + + // 5. Set subtree.prev_sibling to parent.last_child. + // 6. Set parent.last_child.last_descendant.next to subtree. + + if (lastChild) + { + subtree->prevSibling_ = lastChild; + lastChild->getLastDescendant()->next_ = subtree; + } + else + { + subtree->prevSibling_ = subtree; + } + + // 7. Set subtree.last_descendant.next to parent.next_sibling. + + if (nextSibling) + { + subtree->getLastDescendant()->next_ = nextSibling; + } } void remove() { + Ptr parent = getParent(); + Ptr prevSibling = getPreviousSibling(); + Ptr nextSibling = getNextSibling(); + Ptr lastDescendant = getLastDescendant(); + Ptr previous = getPrevious(); + + Ptr newLastDescendant; + + // 1. Fix last descendant of each direct ancestor. + + if (prevSibling) newLastDescendant = prevSibling->getLastDescendant(); + else newLastDescendant = parent; + + Ptr temp = parent; + while (temp && temp->getLastDescendant() == lastDescendant) + { + temp->lastDescendant_ = newLastDescendant; + temp = temp->getParent(); + } + + // 2. Fix next of previous. + + if (previous) + { + previous->next_ = nextSibling; + } + + // 3. Fix the previous sibling of next sibling. + + if (nextSibling) + { + nextSibling->prevSibling_ = prevSibling; + } + + // 4. Once detached, the subtree root has no parent or siblings. + + parent_.reset(); + prevSibling_ = getThis(); } }; diff --git a/src/Moof/stlplus/containers.hpp b/src/Moof/stlplus/containers.hpp new file mode 100755 index 0000000..5863758 --- /dev/null +++ b/src/Moof/stlplus/containers.hpp @@ -0,0 +1,23 @@ +#ifndef STLPLUS_CONTAINERS +#define STLPLUS_CONTAINERS +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +// Allows all the STLplus containers to be included in one go + +//////////////////////////////////////////////////////////////////////////////// + +#include "digraph.hpp" +#include "foursome.hpp" +#include "hash.hpp" +#include "matrix.hpp" +#include "ntree.hpp" +#include "smart_ptr.hpp" +#include "triple.hpp" + +//////////////////////////////////////////////////////////////////////////////// +#endif diff --git a/src/Moof/stlplus/containers_fixes.hpp b/src/Moof/stlplus/containers_fixes.hpp new file mode 100755 index 0000000..618ef84 --- /dev/null +++ b/src/Moof/stlplus/containers_fixes.hpp @@ -0,0 +1,133 @@ +#ifndef STLPLUS_CONTAINERS_FIXES +#define STLPLUS_CONTAINERS_FIXES +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +// Contains work arounds for OS or Compiler specific problems with container +// templates + +//////////////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////////////// +// Unnecessary compiler warnings +//////////////////////////////////////////////////////////////////////////////// + +#ifdef _MSC_VER +// Microsoft Visual Studio +// shut up the following irritating warnings +// 4275 - VC6, exported class was derived from a class that was not exported +// 4786 - VC6, identifier string exceeded maximum allowable length and was truncated (only affects debugger) +// 4305 - VC6, identifier type was converted to a smaller type +// 4503 - VC6, decorated name was longer than the maximum the compiler allows (only affects debugger) +// 4309 - VC6, type conversion operation caused a constant to exceeded the space allocated for it +// 4290 - VC6, C++ exception specification ignored +// 4800 - VC6, forcing value to bool 'true' or 'false' (performance warning) +// 4355 - VC6, 'this' : used in base member initializer list +// 4675 - VC7.1, "change" in function overload resolution _might_ have altered program +// 4996 - VC8, 'xxxx' was declared deprecated +#pragma warning(disable: 4275 4786 4305 4503 4309 4290 4800 4355 4675 4996) +#endif + +#ifdef __BORLANDC__ +// Borland +// Shut up the following irritating warnings +// 8008 - Condition is always true. +// Whenever the compiler encounters a constant comparison that (due to +// the nature of the value being compared) is always true or false, it +// issues this warning and evaluates the condition at compile time. +// 8026 - Functions with exception specifications are not expanded inline +// 8027 - Functions with xxx are not expanded inline +// 8060 - Possibly incorrect assignment. +// This warning is generated when the compiler encounters an assignment +// operator as the main operator of a conditional expression (part of +// an if, while, or do-while statement). This is usually a +// typographical error for the equality operator. +// 8066 - Unreachable code. +// A break, continue, goto, or return statement was not followed by a +// label or the end of a loop or function. The compiler checks while, +// do, and for loops with a constant test condition, and attempts to +// recognize loops that can't fall through. +#pragma warn -8008 +#pragma warn -8026 +#pragma warn -8027 +#pragma warn -8060 +#pragma warn -8066 +#endif + +//////////////////////////////////////////////////////////////////////////////// +// Problems with the typename keyword +//////////////////////////////////////////////////////////////////////////////// + +// There are problems with using the 'typename' keyword. Technically, if you +// use a type member of a template class (i.e. a type declared within the +// template class by a local typedef), you need to tell the compiler that it +// is a type name. This is because the compiler cannot work out whether a +// member is a type, a method or a data field at compile time. However, +// support for the typename keyword has traditionally been incomplete in both +// gcc and Visual Studio. I have used macros to try to resolve this issue. The +// macros add the keyword for compiler versions that require it and omit it +// for compiler versions that do not support it + +// There are five places where typename keywords cause problems: +// +// 1) in a typedef where a template class's member type is being mapped onto +// a type definition within another template class or function +// e.g. template fn () { +// typedef typename someclass::member_type local_type; +// ^^^^^^^^ +// 2) in a function parameter declaration, with similar rules to the above +// e.g. template fn (typename someclass::member_type) +// ^^^^^^^^ +// 3) in instantiating a template, the parameter to the template, with similar rules to the above +// e.g. template_class::member_type> +// ^^^^^^^^ +// 4) Return expressions +// e.g. return typename ntree::const_iterator(this,m_root); +// ^^^^^^^^ +// 5) Creating temporary objects when passing arguments to a function or constructor +// e.g. return typename ntree::const_prefix_iterator(typename ntree::const_iterator(this,m_root)); +// ^^^^^^^^ +// Note that the typename keyword is only required when the type being referred to is a member of a template class +// +// So far it *seems* as if all compilers either require all of them or none of +// them, so this set of situations can be handled by a single macro + +// default values, overridden for individual problem cases below +#define TYPENAME typename + +// GCC +// - pre-version 3 didn't handle typename in any of these cases +// - version 3 onwards, typename is required for all three cases as per default +#ifdef __GNUC__ +#if __GNUC__ < 3 +#undef TYPENAME +#define TYPENAME +#endif +#endif + +// Visual Studio +// - version 6 (compiler v.12) cannot handle typename in any of these cases +// - version 7 (.NET) (compiler v.13) requires a typename in a parameter specification but supports all +// - version 8 (2005) (compiler v.14) requires parameters and templates, supports all +#ifdef _MSC_VER +#if _MSC_VER < 1300 +#undef TYPENAME +#define TYPENAME +#endif +#endif + +// Borland +// - doesn't handle typename in 5.5, does in 5.82, not sure about other cases +#ifdef __BORLANDC__ +#if __BORLANDC__ <= 0x550 +#undef TYPENAME +#define TYPENAME +#endif +#endif + +//////////////////////////////////////////////////////////////////////////////// +#endif diff --git a/src/Moof/stlplus/digraph.hpp b/src/Moof/stlplus/digraph.hpp new file mode 100755 index 0000000..8281998 --- /dev/null +++ b/src/Moof/stlplus/digraph.hpp @@ -0,0 +1,507 @@ +#ifndef STLPLUS_DIGRAPH +#define STLPLUS_DIGRAPH +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +// STL-style Directed graph template component +// Digraph stands for directed-graph, i.e. all arcs have a direction + +//////////////////////////////////////////////////////////////////////////////// +#include "containers_fixes.hpp" +#include "safe_iterator.hpp" +#include "exceptions.hpp" +#include +#include +#include + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // Internals + + template class digraph_node; + template class digraph_arc; + template class digraph; + + //////////////////////////////////////////////////////////////////////////////// + // The Digraph iterator classes + // a digraph_iterator points to a node whilst a digraph_arc_iterator points to an arc + // Note that these are redefined as: + // digraph::iterator - points to a non-const node + // digraph::const_iterator - points to a const node + // digraph::arc_iterator - points to a non-const arc + // digraph::const_arc_iterator - points to a const arc + // and this is the form in which they should be used + + template + class digraph_iterator : public safe_iterator, digraph_node > + { + public: + friend class digraph; + + // local type definitions + // an iterator points to an object whilst a const_iterator points to a const object + typedef digraph_iterator iterator; + typedef digraph_iterator const_iterator; + typedef digraph_iterator this_iterator; + typedef NRef reference; + typedef NPtr pointer; + + // constructor to create a null iterator - you must assign a valid value to this iterator before using it + digraph_iterator(void); + ~digraph_iterator(void); + + // Type conversion methods allow const_iterator and iterator to be converted + // convert an iterator/const_iterator to a const_iterator + const_iterator constify(void) const; + // convert an iterator/const_iterator to an iterator + iterator deconstify(void) const; + + // increment/decrement operators used to step through the set of all nodes in a graph + // it is only legal to increment a valid iterator + // pre-increment + this_iterator& operator ++ (void) + throw(null_dereference,end_dereference); + // post-increment + this_iterator operator ++ (int) + throw(null_dereference,end_dereference); + // pre-decrement + this_iterator& operator -- (void) + throw(null_dereference,end_dereference); + // post-decrement + this_iterator operator -- (int) + throw(null_dereference,end_dereference); + + // test useful for testing whether iteration has completed and for inclusion in other containers + // Note: this class also inherits the safe_iterator methods: valid(), null(), end() + bool operator == (const this_iterator& r) const; + bool operator != (const this_iterator& r) const; + bool operator < (const this_iterator& r) const; + + // access the node data - a const_iterator gives you a const element, an iterator a non-const element + // it is illegal to dereference an invalid (i.e. null or end) iterator + reference operator*(void) const + throw(null_dereference,end_dereference); + pointer operator->(void) const + throw(null_dereference,end_dereference); + + public: + // constructor used by digraph to create a non-null iterator + explicit digraph_iterator(digraph_node* node); + // constructor used by digraph to create an end iterator + explicit digraph_iterator(const digraph* owner); + // used to create an alias of an iterator + explicit digraph_iterator(const safe_iterator, digraph_node >& iterator); + }; + + //////////////////////////////////////////////////////////////////////////////// + + template + class digraph_arc_iterator : public safe_iterator, digraph_arc > + { + public: + friend class digraph; + + // local type definitions + // an iterator points to an object whilst a const_iterator points to a const object + typedef digraph_arc_iterator iterator; + typedef digraph_arc_iterator const_iterator; + typedef digraph_arc_iterator this_iterator; + typedef ARef reference; + typedef APtr pointer; + + // constructor to create a null iterator - you must assign a valid value to this iterator before using it + digraph_arc_iterator(void); + ~digraph_arc_iterator(void); + + // Type conversion methods allow const_iterator and iterator to be converted + // convert an iterator/const_iterator to a const_iterator + const_iterator constify(void) const; + // convert an iterator/const_iterator to an iterator + iterator deconstify(void) const; + + // increment/decrement operators used to step through the set of all nodes in a graph + // it is only legal to increment a valid iterator + // pre-increment + this_iterator& operator ++ (void) + throw(null_dereference,end_dereference); + // post-increment + this_iterator operator ++ (int) + throw(null_dereference,end_dereference); + // pre-decrement + this_iterator& operator -- (void) + throw(null_dereference,end_dereference); + // post-decrement + this_iterator operator -- (int) + throw(null_dereference,end_dereference); + + // test useful for testing whether iteration has completed and for inclusion in other containers + // Note: this class also inherits the safe_iterator methods: valid(), null(), end() + bool operator == (const this_iterator&) const; + bool operator != (const this_iterator&) const; + bool operator < (const this_iterator&) const; + + // access the node data - a const_iterator gives you a const element, an iterator a non-const element + // it is illegal to dereference an invalid (i.e. null or end) iterator + reference operator*(void) const + throw(null_dereference,end_dereference); + pointer operator->(void) const + throw(null_dereference,end_dereference); + + public: + // constructor used by digraph to create a non-null iterator + explicit digraph_arc_iterator(digraph_arc* arc); + // constructor used by digraph to create an end iterator + explicit digraph_arc_iterator(const digraph* owner); + // used to create an alias of an iterator + explicit digraph_arc_iterator(const safe_iterator, digraph_arc >& iterator); + }; + + //////////////////////////////////////////////////////////////////////////////// + // The Graph class + // NT is the Node type and AT is the Arc type + //////////////////////////////////////////////////////////////////////////////// + + template + class digraph + { + public: + // STL-like typedefs for the types and iterators + typedef NT node_type; + typedef AT arc_type; + typedef digraph_iterator iterator; + typedef digraph_iterator const_iterator; + typedef digraph_arc_iterator arc_iterator; + typedef digraph_arc_iterator const_arc_iterator; + + // supplementary types used throughout + + // a path is represented as a vector of arcs so the forward traversal is + // done by going from begin() to end() or 0 to size-1 - of course a backward + // traversal can be done by traversing the vector backwards + typedef std::vector arc_vector; + typedef std::vector const_arc_vector; + const_arc_vector constify_arcs(const arc_vector&) const + throw(wrong_object,null_dereference,end_dereference); + arc_vector deconstify_arcs(const const_arc_vector&) const + throw(wrong_object,null_dereference,end_dereference); + + // a path vector is a vector of paths used to represent all the paths from one node to another + // there is no particular ordering to the paths in the vector + typedef std::vector path_vector; + typedef std::vector const_path_vector; + const_path_vector constify_paths(const path_vector&) const + throw(wrong_object,null_dereference,end_dereference); + path_vector deconstify_paths(const const_path_vector&) const + throw(wrong_object,null_dereference,end_dereference); + + // a node vector is a simple vector of nodes used to represent the reachable sets + // there is no particular ordering to the nodes in the vector + typedef std::vector node_vector; + typedef std::vector const_node_vector; + const_node_vector constify_nodes(const node_vector&) const + throw(wrong_object,null_dereference,end_dereference); + node_vector deconstify_nodes(const const_node_vector&) const + throw(wrong_object,null_dereference,end_dereference); + + // callback used in the path algorithms to select which arcs to consider + typedef bool (*arc_select_fn) (const digraph&, const_arc_iterator); + + // a value representing an unknown offset + // Note that it's static so use in the form digraph::npos() + static unsigned npos(void); + + ////////////////////////////////////////////////////////////////////////// + // Constructors, destructors and copies + + digraph(void); + ~digraph(void); + + // copy constructor and assignment both copy the graph + digraph(const digraph&); + digraph& operator=(const digraph&); + + ////////////////////////////////////////////////////////////////////////// + // Basic Node functions + // Nodes are referred to by iterators created when the node is inserted. + // Iterators remain valid unless the node is erased (they are list iterators, so no resize problems) + // It is also possible to walk through all the nodes using a list-like start() to end() loop + // Each node has a set of input arcs and output arcs. These are indexed by an unsigned i.e. they form a vector. + // The total number of inputs is the fanin and the total number of outputs is the fanout. + // The contents of the node (type NT) are accessed, of course, by dereferencing the node iterator. + + // tests for the number of nodes and the special test for zero nodes + bool empty(void) const; + unsigned size(void) const; + + // add a new node and return its iterator + iterator insert(const NT& node_data); + + // remove a node and return the iterator to the next node + // erasing a node erases its arcs + iterator erase(iterator) + throw(wrong_object,null_dereference,end_dereference); + // remove all nodes + void clear(void); + + // traverse all the nodes in no particular order using STL-style iteration + const_iterator begin(void) const; + iterator begin(void); + const_iterator end(void) const; + iterator end(void); + + // access the inputs of this node + // the fanin is the number of inputs and the inputs are accessed using an index from 0..fanin-1 + unsigned fanin(const_iterator) const + throw(wrong_object,null_dereference,end_dereference); + unsigned fanin(iterator) + throw(wrong_object,null_dereference,end_dereference); + const_arc_iterator input(const_iterator, unsigned) const + throw(wrong_object,null_dereference,end_dereference,std::out_of_range); + arc_iterator input(iterator, unsigned) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range); + + // access the outputs of this node + // the fanout is the number of outputs and the outputs are accessed using an index from 0..fanout-1 + unsigned fanout(const_iterator) const + throw(wrong_object,null_dereference,end_dereference); + unsigned fanout(iterator) + throw(wrong_object,null_dereference,end_dereference); + const_arc_iterator output(const_iterator, unsigned) const + throw(wrong_object,null_dereference,end_dereference,std::out_of_range); + arc_iterator output(iterator, unsigned) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range); + + // convenience routines for getting the set of all inputs or all outputs as vectors + const_arc_vector inputs(const_iterator) const + throw(wrong_object,null_dereference,end_dereference); + arc_vector inputs(iterator) + throw(wrong_object,null_dereference,end_dereference); + const_arc_vector outputs(const_iterator) const + throw(wrong_object,null_dereference,end_dereference); + arc_vector outputs(iterator) + throw(wrong_object,null_dereference,end_dereference); + + // find the output index of an arc which goes from this node + // returns digraph::npos if the arc is not an output of from + unsigned output_offset(const_iterator from, const_arc_iterator arc) const + throw(wrong_object,null_dereference,end_dereference); + unsigned output_offset(iterator from, arc_iterator arc) + throw(wrong_object,null_dereference,end_dereference); + // ditto for an input arc + unsigned input_offset(const_iterator to, const_arc_iterator arc) const + throw(wrong_object,null_dereference,end_dereference); + unsigned input_offset(iterator to, arc_iterator arc) + throw(wrong_object,null_dereference,end_dereference); + + ////////////////////////////////////////////////////////////////////////// + // Basic Arc functions + // to avoid name conflicts, arc functions have the arc_ prefix + // Arcs, like nodes, are referred to by a list iterator which is returned by the arc_insert function + // They may also be visited from arc_begin() to arc_end() + // Each arc has a from field and a to field which contain the node iterators of the endpoints of the arc + // Of course, the arc data can be accessed by simply dereferencing the iterator + + // tests for the number of arcs and the special test for zero arcs + bool arc_empty (void) const; + unsigned arc_size(void) const; + + // add a new arc and return its iterator + arc_iterator arc_insert(iterator from, iterator to, const AT& arc_data = AT()) + throw(wrong_object,null_dereference,end_dereference); + + // remove an arc and return the iterator to the next arc + arc_iterator arc_erase(arc_iterator) + throw(wrong_object,null_dereference,end_dereference); + // remove all arcs + void arc_clear(void); + + // traverse all the arcs in no particular order using STL-style iteration + const_arc_iterator arc_begin(void) const; + arc_iterator arc_begin(void); + const_arc_iterator arc_end(void) const; + arc_iterator arc_end(void); + + // find the node that an arc points from or to + const_iterator arc_from(const_arc_iterator) const + throw(wrong_object,null_dereference,end_dereference); + iterator arc_from(arc_iterator) + throw(wrong_object,null_dereference,end_dereference); + const_iterator arc_to(const_arc_iterator) const + throw(wrong_object,null_dereference,end_dereference); + iterator arc_to(arc_iterator) + throw(wrong_object,null_dereference,end_dereference); + + // reconnect an arc to a different from and to node + void arc_move(arc_iterator arc, iterator from, iterator to) + throw(wrong_object,null_dereference,end_dereference); + // reconnect just the from node + void arc_move_from(arc_iterator arc, iterator from) + throw(wrong_object,null_dereference,end_dereference); + // reconnect just the to node + void arc_move_to(arc_iterator arc, iterator to) + throw(wrong_object,null_dereference,end_dereference); + // reverse the arc direction so that to becomes from and vice-versa + void arc_flip(arc_iterator arc) + throw(wrong_object,null_dereference,end_dereference); + + //////////////////////////////////////////////////////////////////////////////// + // Adjacency algorithms + + // test whether the nodes are adjacent i.e. whether there is an arc going from from to to + bool adjacent(const_iterator from, const_iterator to) const + throw(wrong_object,null_dereference,end_dereference); + bool adjacent(iterator from, iterator to) + throw(wrong_object,null_dereference,end_dereference); + + // as above, but returns the arc that makes the nodes adjacent + // returns the first arc if there's more than one, returns arc_end() if there are none + const_arc_iterator adjacent_arc(const_iterator from, const_iterator to) const + throw(wrong_object,null_dereference,end_dereference); + arc_iterator adjacent_arc(iterator from, iterator to) + throw(wrong_object,null_dereference,end_dereference); + + // as above, but returns the set of all arcs that make two nodes adjacent (there may be more than one) + // returns an empty vector if there are none + const_arc_vector adjacent_arcs(const_iterator from, const_iterator to) const + throw(wrong_object,null_dereference,end_dereference); + arc_vector adjacent_arcs(iterator from, iterator to) + throw(wrong_object,null_dereference,end_dereference); + + // return the adjacency sets for the node inputs or outputs, i.e. the set of nodes adjacent to this node + // each adjacent node will only be entered once even if there are multiple arcs between the nodes + const_node_vector input_adjacencies(const_iterator to) const + throw(wrong_object,null_dereference,end_dereference); + node_vector input_adjacencies(iterator to) + throw(wrong_object,null_dereference,end_dereference); + const_node_vector output_adjacencies(const_iterator from) const + throw(wrong_object,null_dereference,end_dereference); + node_vector output_adjacencies(iterator from) + throw(wrong_object,null_dereference,end_dereference); + + //////////////////////////////////////////////////////////////////////////////// + // Topographical Sort Algorithm + // This generates a node ordering such that each node is visited after its fanin nodes. + + // This only generates a valid ordering for a DAG. + + // The return value is a pair : + // - the node vector which is a set of iterators to the nodes in sorted order + // - the arc vector is the set of backward ards that were broken to achieve the sort + // If the arc vector is empty then the graph formed a DAG. + + // The arc selection callback can be used to ignore arcs that are not part + // of the ordering, i.e. arcs that are meant to be backwards arcs + + std::pair sort(arc_select_fn = 0) const; + std::pair sort(arc_select_fn = 0); + + // Simplified variant of above for graphs that are known to be DAGs. + // If the sort fails due to backward arcs, the + // return vector is empty. Note that this will also be empty if the graph + // has no nodes in it, so use the empty() method to differentiate. + + const_node_vector dag_sort(arc_select_fn = 0) const; + node_vector dag_sort(arc_select_fn = 0); + + //////////////////////////////////////////////////////////////////////////////// + // Basic Path Algorithms + // A path is a series of arcs - you can use arc_from and arc_to to convert + // that into a series of nodes. All the path algorithms take an arc_select + // which allows arcs to be selected or rejected for consideration in a path. + + // A selection callback function is applied to each arc in the traversal and + // returns true if the arc is to be selected and false if the arc is to be + // rejected. If no function is provided the arc is selected. If you want to + // use arc selection you should create a function with the type profile given + // by the arc_select_fn type. The select function is passed both the graph and + // the arc iterator so that it is possible to select an arc on the basis of + // the nodes it is connected to. + + // Note: I used a callback because the STL-like predicate idea wasn't working for me... + + // test for the existence of a path from from to to + bool path_exists(const_iterator from, const_iterator to, arc_select_fn = 0) const + throw(wrong_object,null_dereference,end_dereference); + bool path_exists(iterator from, iterator to, arc_select_fn = 0) + throw(wrong_object,null_dereference,end_dereference); + + // get the set of all paths from from to to + const_path_vector all_paths(const_iterator from, const_iterator to, arc_select_fn = 0) const + throw(wrong_object,null_dereference,end_dereference); + path_vector all_paths(iterator from, iterator to, arc_select_fn = 0) + throw(wrong_object,null_dereference,end_dereference); + + // get the set of all nodes that can be reached by any path from from + const_node_vector reachable_nodes(const_iterator from, arc_select_fn = 0) const + throw(wrong_object,null_dereference,end_dereference); + node_vector reachable_nodes(iterator from, arc_select_fn = 0) + throw(wrong_object,null_dereference,end_dereference); + + // get the set of all nodes that can reach to to by any path + const_node_vector reaching_nodes(const_iterator to, arc_select_fn = 0) const + throw(wrong_object,null_dereference,end_dereference); + node_vector reaching_nodes(iterator to, arc_select_fn = 0) + throw(wrong_object,null_dereference,end_dereference); + + //////////////////////////////////////////////////////////////////////////////// + // Unweighted Shortest path algorithms + + // find the shortest path from from to to + // This is an unweighted shortest path algorithm, i.e. the weight of each + // arc is assumed to be 1, so just counts the number of arcs + // if there is more than one shortest path it returns the first one + // If there are no paths, returns an empty path + const_arc_vector shortest_path(const_iterator from, const_iterator to, arc_select_fn = 0) const + throw(wrong_object,null_dereference,end_dereference); + arc_vector shortest_path(iterator from, iterator to, arc_select_fn = 0) + throw(wrong_object,null_dereference,end_dereference); + + // find the set of shortest paths from from to any other node in the graph + // that is reachable (i.e. for which path_exists() is true) + // This is an unweighted shortest path, so just counts the number of arcs + // if there is more than one shortest path to a node it returns the first one + // If there are no paths, returns an empty list + const_path_vector shortest_paths(const_iterator from, arc_select_fn = 0) const + throw(wrong_object,null_dereference,end_dereference); + path_vector shortest_paths(iterator from, arc_select_fn = 0) + throw(wrong_object,null_dereference,end_dereference); + + private: + friend class digraph_iterator; + friend class digraph_iterator; + friend class digraph_arc_iterator; + friend class digraph_arc_iterator; + + typedef std::set const_iterator_set; + typedef TYPENAME const_iterator_set::iterator const_iterator_set_iterator; + + bool path_exists_r(const_iterator from, const_iterator to, const_iterator_set& visited, arc_select_fn) const + throw(wrong_object,null_dereference,end_dereference); + + void all_paths_r(const_iterator from, const_iterator to, const_arc_vector& so_far, const_path_vector& result, arc_select_fn) const + throw(wrong_object,null_dereference,end_dereference); + + void reachable_nodes_r(const_iterator from, const_iterator_set& visited, arc_select_fn) const + throw(wrong_object,null_dereference,end_dereference); + + void reaching_nodes_r(const_iterator to, const_iterator_set& visited, arc_select_fn) const + throw(wrong_object,null_dereference,end_dereference); + + digraph_node* m_nodes_begin; + digraph_node* m_nodes_end; + digraph_arc* m_arcs_begin; + digraph_arc* m_arcs_end; + }; + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + +#include "digraph.tpp" +#endif diff --git a/src/Moof/stlplus/digraph.tpp b/src/Moof/stlplus/digraph.tpp new file mode 100755 index 0000000..c10586b --- /dev/null +++ b/src/Moof/stlplus/digraph.tpp @@ -0,0 +1,1483 @@ +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +// Note: I tried to write this using STL lists for the node and arc lists, but +// it got far too hairy. The specific problem is that I wanted a digraph +// iterator to contain a list::iterator so I needed to be able to generate a +// list::iterator from a node or arc and STL list iterators don't give you that +// functionality. I tried burgling the data structures, but that was +// non-portable between different STL implementations so needed lots of #ifdefs +// and so was mind-bogglingly awful and unreadable - in other words a +// maintenance nightmare. I gave up and impemented my own lists - not difficult. + +// I use circular double-linked lists. The circular design means that both +// ends of the list are equally accessible in unit time. An empty list +// contains no objects. There is no end node in the list - unlike the STL +// lists which have a dummy node for end iterators to point to - +// conceptually the end iterator points one element beyond the end of the +// list. However, I implement the end iterator concept in the iterator +// itself, so do not need the dummy end node. + +//////////////////////////////////////////////////////////////////////////////// +#include +#include + +//////////////////////////////////////////////////////////////////////////////// +// Internals + +namespace stlplus +{ + + template + class digraph_node + { + public: + master_iterator, digraph_node > m_master; + NT m_data; + digraph_node* m_prev; + digraph_node* m_next; + std::vector*> m_inputs; + std::vector*> m_outputs; + public: + digraph_node(const digraph* owner, const NT& d = NT()) : + m_master(owner,this), m_data(d), m_prev(0), m_next(0) + { + } + ~digraph_node(void) + { + } + }; + + template + class digraph_arc + { + public: + master_iterator, digraph_arc > m_master; + AT m_data; + digraph_arc* m_prev; + digraph_arc* m_next; + digraph_node* m_from; + digraph_node* m_to; + digraph_arc(const digraph* owner, digraph_node* from = 0, digraph_node* to = 0, const AT& d = AT()) : + m_master(owner,this), m_data(d), m_prev(0), m_next(0), m_from(from), m_to(to) + { + } + }; + + //////////////////////////////////////////////////////////////////////////////// + // Iterators + //////////////////////////////////////////////////////////////////////////////// + + //////////////////////////////////////////////////////////////////////////////// + // Node iterator + + // construct a null iterator + template + digraph_iterator::digraph_iterator(void) + { + } + + // valid iterator + template + digraph_iterator::digraph_iterator(digraph_node* node) : + safe_iterator,digraph_node >(node->m_master) + { + } + + // end iterator + template + digraph_iterator::digraph_iterator(const digraph* owner) : + safe_iterator,digraph_node >(owner) + { + } + + // alias an iterator + template + digraph_iterator::digraph_iterator(const safe_iterator, digraph_node >& iterator) : + safe_iterator,digraph_node >(iterator) + { + } + + // destructor + template + digraph_iterator::~digraph_iterator(void) + { + } + + template + TYPENAME digraph_iterator::const_iterator digraph_iterator::constify (void) const + { + return digraph_iterator(*this); + } + + template + TYPENAME digraph_iterator::iterator digraph_iterator::deconstify (void) const + { + return digraph_iterator(*this); + } + + template + TYPENAME digraph_iterator::this_iterator& digraph_iterator::operator ++ (void) + throw(null_dereference,end_dereference) + { + this->assert_valid(); + if (this->node()->m_next) + this->set(this->node()->m_next->m_master); + else + this->set_end(); + return *this; + } + + template + TYPENAME digraph_iterator::this_iterator digraph_iterator::operator ++ (int) + throw(null_dereference,end_dereference) + { + // post-increment is defined in terms of the pre-increment + digraph_iterator result(*this); + ++(*this); + return result; + } + + template + TYPENAME digraph_iterator::this_iterator& digraph_iterator::operator -- (void) + throw(null_dereference,end_dereference) + { + this->assert_valid(); + if (this->node()->m_prev) + this->set(this->node()->m_prev->m_master); + else + this->set_end(); + return *this; + } + + template + TYPENAME digraph_iterator::this_iterator digraph_iterator::operator -- (int) + throw(null_dereference,end_dereference) + { + // post-decrement is defined in terms of the pre-decrement + digraph_iterator result(*this); + --(*this); + return result; + } + + template + bool digraph_iterator::operator == (const TYPENAME digraph_iterator::this_iterator& r) const + { + return equal(r); + } + + template + bool digraph_iterator::operator != (const TYPENAME digraph_iterator::this_iterator& r) const + { + return !operator==(r); + } + + template + bool digraph_iterator::operator < (const TYPENAME digraph_iterator::this_iterator& r) const + { + return compare(r) < 0; + } + + template + TYPENAME digraph_iterator::reference digraph_iterator::operator*(void) const + throw(null_dereference,end_dereference) + { + this->assert_valid(); + return this->node()->m_data; + } + + template + TYPENAME digraph_iterator::pointer digraph_iterator::operator->(void) const + throw(null_dereference,end_dereference) + { + return &(operator*()); + } + + //////////////////////////////////////////////////////////////////////////////// + // Arc Iterator + + template + digraph_arc_iterator::digraph_arc_iterator(void) + { + } + + // valid iterator + template + digraph_arc_iterator::digraph_arc_iterator(digraph_arc* arc) : + safe_iterator,digraph_arc >(arc->m_master) + { + } + + // end iterator + template + digraph_arc_iterator::digraph_arc_iterator(const digraph* owner) : + safe_iterator,digraph_arc >(owner) + { + } + + // alias an iterator + template + digraph_arc_iterator::digraph_arc_iterator(const safe_iterator, digraph_arc >& iterator) : + safe_iterator,digraph_arc >(iterator) + { + } + + template + digraph_arc_iterator::~digraph_arc_iterator(void) + { + } + + template + TYPENAME digraph_arc_iterator::const_iterator digraph_arc_iterator::constify (void) const + { + return digraph_arc_iterator(*this); + } + + template + TYPENAME digraph_arc_iterator::iterator digraph_arc_iterator::deconstify (void) const + { + return digraph_arc_iterator(*this); + } + + template + TYPENAME digraph_arc_iterator::this_iterator& digraph_arc_iterator::operator ++ (void) + throw(null_dereference,end_dereference) + { + this->assert_valid(); + if (this->node()->m_next) + this->set(this->node()->m_next->m_master); + else + this->set_end(); + return *this; + } + + template + TYPENAME digraph_arc_iterator::this_iterator digraph_arc_iterator::operator ++ (int) + throw(null_dereference,end_dereference) + { + // post-increment is defined in terms of the pre-increment + digraph_arc_iterator result(*this); + ++(*this); + return result; + } + + template + TYPENAME digraph_arc_iterator::this_iterator& digraph_arc_iterator::operator -- (void) + throw(null_dereference,end_dereference) + { + this->assert_valid(); + if (this->node()->m_prev) + this->set(this->node()->m_prev->m_master); + else + this->set_end(); + return *this; + } + + template + TYPENAME digraph_arc_iterator::this_iterator digraph_arc_iterator::operator -- (int) + throw(null_dereference,end_dereference) + { + // post-decrement is defined in terms of the pre-decrement + digraph_arc_iterator result(*this); + --(*this); + return result; + } + + template + bool digraph_arc_iterator::operator == (const TYPENAME digraph_arc_iterator::this_iterator& r) const + { + return equal(r); + } + + template + bool digraph_arc_iterator::operator != (const TYPENAME digraph_arc_iterator::this_iterator& r) const + { + return !operator==(r); + } + + template + bool digraph_arc_iterator::operator < (const TYPENAME digraph_arc_iterator::this_iterator& r) const + { + return compare(r) < 0; + } + + template + TYPENAME digraph_arc_iterator::reference digraph_arc_iterator::operator*(void) const + throw(null_dereference,end_dereference) + { + this->assert_valid(); + return this->node()->m_data; + } + + template + TYPENAME digraph_arc_iterator::pointer digraph_arc_iterator::operator->(void) const + throw(null_dereference,end_dereference) + { + return &(operator*()); + } + + //////////////////////////////////////////////////////////////////////////////// + // subtype utilities + + template + TYPENAME digraph::const_arc_vector digraph::constify_arcs(const TYPENAME digraph::arc_vector& arcs) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > result; + for (unsigned i = 0; i < arcs.size(); i++) + { + arcs[i].assert_valid(this); + result.push_back(arcs[i].constify()); + } + return result; + } + + template + TYPENAME digraph::arc_vector digraph::deconstify_arcs(const TYPENAME digraph::const_arc_vector& arcs) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > result; + for (unsigned i = 0; i < arcs.size(); i++) + { + arcs[i].assert_valid(this); + result.push_back(arcs[i].deconstify()); + } + return result; + } + + template + TYPENAME digraph::const_path_vector digraph::constify_paths(const TYPENAME digraph::path_vector& paths) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > > result; + for (unsigned i = 0; i < paths.size(); i++) + result.push_back(constify_arcs(paths[i])); + return result; + } + + template + TYPENAME digraph::path_vector digraph::deconstify_paths(const TYPENAME digraph::const_path_vector& paths) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > > result; + for (unsigned i = 0; i < paths.size(); i++) + result.push_back(deconstify_arcs(paths[i])); + return result; + } + + template + TYPENAME digraph::const_node_vector digraph::constify_nodes(const TYPENAME digraph::node_vector& nodes) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > result; + for (unsigned i = 0; i < nodes.size(); i++) + { + nodes[i].assert_valid(this); + result.push_back(nodes[i].constify()); + } + return result; + } + + template + TYPENAME digraph::node_vector digraph::deconstify_nodes(const TYPENAME digraph::const_node_vector& nodes) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > result; + for (unsigned i = 0; i < nodes.size(); i++) + { + nodes[i].assert_valid(this); + result.push_back(nodes[i].deconstify()); + } + return result; + } + + template + unsigned digraph::npos(void) + { + return(unsigned)-1; + } + + //////////////////////////////////////////////////////////////////////////////// + // Constructors etc. + + template + digraph::digraph(void) : + m_nodes_begin(0), m_nodes_end(0), m_arcs_begin(0), m_arcs_end(0) + { + // node and arc lists are circular double-linked lists + // they start out empty (no dummy end node) + } + + template + digraph::~digraph(void) + { + clear(); + } + + template + digraph::digraph(const digraph& r) : + m_nodes_begin(0), m_nodes_end(0), m_arcs_begin(0), m_arcs_end(0) + { + *this = r; + } + + template + digraph& digraph::operator=(const digraph& r) + { + // make it self-copy safe i.e. a=a; is a valid instruction + if (this == &r) return *this; + clear(); + // first phase is to copy the nodes, creating a map of cross references from the old nodes to their new equivalents + std::map, digraph_iterator > xref; + for (digraph_iterator n = r.begin(); n != r.end(); n++) + xref[n] = insert(*n); + // second phase is to copy the arcs, using the map to convert the old to and from nodes to the new nodes + for (digraph_arc_iterator a = r.arc_begin(); a != r.arc_end(); a++) + arc_insert(xref[r.arc_from(a)],xref[r.arc_to(a)],*a); + return *this; + } + + //////////////////////////////////////////////////////////////////////////////// + // Basic Node functions + + template + bool digraph::empty(void) const + { + return m_nodes_begin == 0; + } + + template + unsigned digraph::size(void) const + { + unsigned count = 0; + for (digraph_iterator i = begin(); i != end(); i++) + count++; + return count; + } + + template + TYPENAME digraph::iterator digraph::insert(const NT& node_data) + { + digraph_node* new_node = new digraph_node(this,node_data); + if (!m_nodes_end) + { + // insert into an empty list + m_nodes_begin = new_node; + m_nodes_end = new_node; + } + else + { + // insert at the end of the list + new_node->m_prev = m_nodes_end; + m_nodes_end->m_next = new_node; + m_nodes_end = new_node; + } + return digraph_iterator(new_node); + } + + template + TYPENAME digraph::iterator digraph::erase(TYPENAME digraph::iterator iter) + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + // remove all arcs connected to this node first + // use arc_erase rather than arcs.erase because that tidies up the node at the other end of the arc too + for (unsigned i = fanin(iter); i--; ) + arc_erase(input(iter,i)); + for (unsigned j = fanout(iter); j--; ) + arc_erase(output(iter,j)); + // now unlink the node from the list and delete it + if (iter.node()->m_next) + iter.node()->m_next->m_prev = iter.node()->m_prev; + if (iter.node()->m_prev) + iter.node()->m_prev->m_next = iter.node()->m_next; + digraph_node* next = iter.node()->m_next; + delete iter.node(); + // return the next node in the list + if (next) + return digraph_iterator(next); + else + return digraph_iterator(this); + } + + template + void digraph::clear(void) + { + // clearing the nodes also clears the arcs + for (digraph_iterator i = begin(); i != end(); ) + i = erase(i); + } + + template + TYPENAME digraph::const_iterator digraph::begin(void) const + { + if (m_nodes_begin) + return digraph_iterator(m_nodes_begin); + else + return digraph_iterator(this); + } + + template + TYPENAME digraph::iterator digraph::begin(void) + { + if (m_nodes_begin) + return digraph_iterator(m_nodes_begin); + else + return digraph_iterator(this); + } + + template + TYPENAME digraph::const_iterator digraph::end(void) const + { + return digraph_iterator(this); + } + + template + TYPENAME digraph::iterator digraph::end(void) + { + return digraph_iterator(this); + } + + template + unsigned digraph::fanin(TYPENAME digraph::const_iterator iter) const + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return iter.node()->m_inputs.size(); + } + + template + unsigned digraph::fanin(TYPENAME digraph::iterator iter) + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return iter.node()->m_inputs.size(); + } + + template + TYPENAME digraph::const_arc_iterator digraph::input(TYPENAME digraph::const_iterator iter, unsigned i) const + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + iter.assert_valid(this); + if (i >= iter.node()->m_inputs.size()) throw std::out_of_range("digraph::input"); + return digraph_arc_iterator(iter.node()->m_inputs[i]); + } + + template + TYPENAME digraph::arc_iterator digraph::input(TYPENAME digraph::iterator iter, unsigned i) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + iter.assert_valid(this); + if (i >= iter.node()->m_inputs.size()) throw std::out_of_range("digraph::input"); + return digraph_arc_iterator(iter.node()->m_inputs[i]); + } + + template + unsigned digraph::fanout(TYPENAME digraph::const_iterator iter) const + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return iter.node()->m_outputs.size(); + } + + template + unsigned digraph::fanout(TYPENAME digraph::iterator iter) + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return iter.node()->m_outputs.size(); + } + + template + TYPENAME digraph::const_arc_iterator digraph::output(TYPENAME digraph::const_iterator iter, unsigned i) const + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + iter.assert_valid(this); + if (i >= iter.node()->m_outputs.size()) throw std::out_of_range("digraph::output"); + return digraph_arc_iterator(iter.node()->m_outputs[i]); + } + + template + TYPENAME digraph::arc_iterator digraph::output(TYPENAME digraph::iterator iter, unsigned i) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + iter.assert_valid(this); + if (i >= iter.node()->m_outputs.size()) throw std::out_of_range("digraph::output"); + return digraph_arc_iterator(iter.node()->m_outputs[i]); + } + + template + TYPENAME digraph::const_arc_vector digraph::inputs(TYPENAME digraph::const_iterator node) const + throw(wrong_object,null_dereference,end_dereference) + { + node.assert_valid(this); + std::vector > result; + for (unsigned i = 0; i < fanin(node); i++) + result.push_back(input(node,i)); + return result; + } + + template + TYPENAME digraph::arc_vector digraph::inputs(TYPENAME digraph::iterator node) + throw(wrong_object,null_dereference,end_dereference) + { + node.assert_valid(this); + std::vector > result; + for (unsigned i = 0; i < fanin(node); i++) + result.push_back(input(node,i)); + return result; + } + + template + TYPENAME digraph::const_arc_vector digraph::outputs(TYPENAME digraph::const_iterator node) const + throw(wrong_object,null_dereference,end_dereference) + { + node.assert_valid(this); + std::vector > result; + for (unsigned i = 0; i < fanout(node); i++) + result.push_back(output(node,i)); + return result; + } + + template + TYPENAME digraph::arc_vector digraph::outputs(TYPENAME digraph::iterator node) + throw(wrong_object,null_dereference,end_dereference) + { + node.assert_valid(this); + std::vector > result; + for (unsigned i = 0; i < fanout(node); i++) + result.push_back(output(node,i)); + return result; + } + + template + unsigned digraph::output_offset(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_arc_iterator arc) const + throw(wrong_object,null_dereference,end_dereference) + { + from.assert_valid(this); + arc.assert_valid(this); + for (unsigned i = 0; i < fanout(from); i++) + { + if (output(from,i) == arc) + return i; + } + return digraph::npos(); + } + + template + unsigned digraph::output_offset(TYPENAME digraph::iterator from, + TYPENAME digraph::arc_iterator arc) + throw(wrong_object,null_dereference,end_dereference) + { + from.assert_valid(this); + arc.assert_valid(this); + for (unsigned i = 0; i < fanout(from); i++) + { + if (output(from,i) == arc) + return i; + } + return digraph::npos(); + } + + template + unsigned digraph::input_offset(TYPENAME digraph::const_iterator to, + TYPENAME digraph::const_arc_iterator arc) const + throw(wrong_object,null_dereference,end_dereference) + { + to.assert_valid(this); + arc.assert_valid(this); + for (unsigned i = 0; i < fanin(to); i++) + { + if (input(to,i) == arc) + return i; + } + return digraph::npos(); + } + + template + unsigned digraph::input_offset(TYPENAME digraph::iterator to, + TYPENAME digraph::arc_iterator arc) + throw(wrong_object,null_dereference,end_dereference) + { + to.assert_valid(this); + arc.assert_valid(this); + for (unsigned i = 0; i < fanin(to); i++) + { + if (input(to,i) == arc) + return i; + } + return digraph::npos(); + } + + //////////////////////////////////////////////////////////////////////////////// + // Basic Arc functions + + template + bool digraph::arc_empty(void) const + { + return m_arcs_end == 0; + } + + template + unsigned digraph::arc_size(void) const + { + unsigned count = 0; + for (digraph_arc_iterator i = arc_begin(); i != arc_end(); i++) + count++; + return count; + } + + template + TYPENAME digraph::arc_iterator digraph::arc_insert(TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to, + const AT& arc_data) + throw(wrong_object,null_dereference,end_dereference) + { + from.assert_valid(this); + to.assert_valid(this); + // create the new arc and link it in to the arc list + digraph_arc* new_arc = new digraph_arc(this, from.node(), to.node(), arc_data); + if (!m_arcs_end) + { + // insert into an empty list + m_arcs_begin = new_arc; + m_arcs_end = new_arc; + } + else + { + // insert at the end of the list + new_arc->m_prev = m_arcs_end; + m_arcs_end->m_next = new_arc; + m_arcs_end = new_arc; + } + // add this arc to the inputs and outputs of the end nodes + from.node()->m_outputs.push_back(new_arc); + to.node()->m_inputs.push_back(new_arc); + return digraph_arc_iterator(new_arc); + } + + template + TYPENAME digraph::arc_iterator digraph::arc_erase(TYPENAME digraph::arc_iterator iter) + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + // first remove this arc's pointers from the from/to nodes + for (TYPENAME std::vector*>::iterator i = iter.node()->m_to->m_inputs.begin(); i != iter.node()->m_to->m_inputs.end(); ) + { + if (*i == iter.node()) + i = iter.node()->m_to->m_inputs.erase(i); + else + i++; + } + for (TYPENAME std::vector*>::iterator o = iter.node()->m_from->m_outputs.begin(); o != iter.node()->m_from->m_outputs.end(); ) + { + if (*o == iter.node()) + o = iter.node()->m_from->m_outputs.erase(o); + else + o++; + } + // now unlink the arc from the list and delete it + if (iter.node()->m_next) + iter.node()->m_next->m_prev = iter.node()->m_prev; + if (iter.node()->m_prev) + iter.node()->m_prev->m_next = iter.node()->m_next; + digraph_arc* next = iter.node()->m_next; + delete iter.node(); + if (next) + return digraph_arc_iterator(next); + else + return digraph_arc_iterator(this); + } + + template + void digraph::arc_clear(void) + { + for (digraph_arc_iterator a = arc_begin(); a != arc_end(); ) + a = arc_erase(a); + } + + template + TYPENAME digraph::const_arc_iterator digraph::arc_begin(void) const + { + if (m_arcs_begin) + return digraph_arc_iterator(m_arcs_begin); + else + return digraph_arc_iterator(this); + } + + template + TYPENAME digraph::arc_iterator digraph::arc_begin(void) + { + if (m_arcs_begin) + return digraph_arc_iterator(m_arcs_begin); + else + return digraph_arc_iterator(this); + } + + template + TYPENAME digraph::const_arc_iterator digraph::arc_end(void) const + { + return digraph_arc_iterator(this); + } + + template + TYPENAME digraph::arc_iterator digraph::arc_end(void) + { + return digraph_arc_iterator(this); + } + + template + TYPENAME digraph::const_iterator digraph::arc_from(TYPENAME digraph::const_arc_iterator iter) const + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return digraph_iterator(iter.node()->m_from); + } + + template + TYPENAME digraph::iterator digraph::arc_from(TYPENAME digraph::arc_iterator iter) + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return digraph_iterator(iter.node()->m_from); + } + + template + TYPENAME digraph::const_iterator digraph::arc_to(TYPENAME digraph::const_arc_iterator iter) const + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return digraph_iterator(iter.node()->m_to); + } + + template + TYPENAME digraph::iterator digraph::arc_to(TYPENAME digraph::arc_iterator iter) + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return digraph_iterator(iter.node()->m_to); + } + + template + void digraph::arc_move(TYPENAME digraph::arc_iterator arc, + TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to) + throw(wrong_object,null_dereference,end_dereference) + { + arc_move_to(arc,to); + arc_move_from(arc,from); + } + + template + void digraph::arc_move_from(TYPENAME digraph::arc_iterator arc, + TYPENAME digraph::iterator from) + throw(wrong_object,null_dereference,end_dereference) + { + arc.assert_valid(this); + from.assert_valid(this); + for (TYPENAME std::vector*>::iterator o = arc.node()->m_from->m_outputs.begin(); o != arc.node()->m_from->m_outputs.end(); ) + { + if (*o == arc.node()) + o = arc.node()->m_from->m_outputs.erase(o); + else + o++; + } + from.node()->m_outputs.push_back(arc.node()); + arc.node()->m_from = from.node(); + } + + template + void digraph::arc_move_to(TYPENAME digraph::arc_iterator arc, + TYPENAME digraph::iterator to) + throw(wrong_object,null_dereference,end_dereference) + { + arc.assert_valid(this); + to.assert_valid(this); + for (TYPENAME std::vector*>::iterator i = arc.node()->m_to->m_inputs.begin(); i != arc.node()->m_to->m_inputs.end(); ) + { + if (*i == arc.node()) + i = arc.node()->m_to->m_inputs.erase(i); + else + i++; + } + to.node()->m_inputs.push_back(arc.node()); + arc.node()->m_to = to.node(); + } + + template + void digraph::arc_flip(TYPENAME digraph::arc_iterator arc) + throw(wrong_object,null_dereference,end_dereference) + { + arc_move(arc,arc_to(arc),arc_from(arc)); + } + + //////////////////////////////////////////////////////////////////////////////// + // Adjacency Algorithms + + template + bool digraph::adjacent(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to) const + throw(wrong_object,null_dereference,end_dereference) + { + return adjacent_arc(from,to) != arc_end(); + } + + template + bool digraph::adjacent(TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to) + throw(wrong_object,null_dereference,end_dereference) + { + return adjacent_arc(from,to) != arc_end(); + } + + template + TYPENAME digraph::const_arc_iterator digraph::adjacent_arc(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to) const + throw(wrong_object,null_dereference,end_dereference) + { + from.assert_valid(this); + to.assert_valid(this); + for (unsigned arc = 0; arc < fanout(from); arc++) + { + if (arc_to(output(from, arc)) == to) + return output(from,arc); + } + return arc_end(); + } + + template + TYPENAME digraph::arc_iterator digraph::adjacent_arc(TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to) + throw(wrong_object,null_dereference,end_dereference) + { + return adjacent_arc(from.constify(), to.constify()).deconstify(); + } + + template + TYPENAME digraph::const_arc_vector digraph::adjacent_arcs(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to) const + throw(wrong_object,null_dereference,end_dereference) + { + from.assert_valid(this); + to.assert_valid(this); + std::vector > result; + for (unsigned arc = 0; arc < fanout(from); arc++) + { + if (arc_to(output(from, arc)) == to) + result.push_back(output(from,arc)); + } + return result; + } + + template + TYPENAME digraph::arc_vector digraph::adjacent_arcs(TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_arcs(adjacent_arcs(from.constify(), to.constify())); + } + + template + TYPENAME digraph::const_node_vector digraph::input_adjacencies(TYPENAME digraph::const_iterator to) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > result; + for (unsigned arc = 0; arc < fanin(to); arc++) + { + digraph_iterator from = arc_from(input(to, arc)); + if (std::find(result.begin(), result.end(), from) == result.end()) + result.push_back(from); + } + return result; + } + + template + TYPENAME digraph::node_vector digraph::input_adjacencies(TYPENAME digraph::iterator to) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_nodes(input_adjacencies(to.constify())); + } + + template + TYPENAME digraph::const_node_vector digraph::output_adjacencies(TYPENAME digraph::const_iterator from) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > result; + for (unsigned arc = 0; arc < fanout(from); arc++) + { + digraph_iterator to = arc_to(output(from, arc)); + if (find(result.begin(), result.end(), to) == result.end()) + result.push_back(to); + } + return result; + } + + template + TYPENAME digraph::node_vector digraph::output_adjacencies(TYPENAME digraph::iterator from) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_nodes(output_adjacencies(from.constify())); + } + + //////////////////////////////////////////////////////////////////////////////// + // Topographical Sort Algorithms + + template + std::pair::const_node_vector, TYPENAME digraph::const_arc_vector> + digraph::sort(TYPENAME digraph::arc_select_fn select) const + { + std::vector > result; + std::vector > errors; + // build a map containing the number of fanins to each node that must be visited before this one + std::map,unsigned> fanin_map; + for (digraph_iterator n = begin(); n != end(); n++) + { + unsigned predecessors = 0; + // only count predecessors connected by selected arcs + for (unsigned f = 0; f < fanin(n); f++) + { + digraph_arc_iterator input_arc = input(n,f); + digraph_iterator predecessor = arc_from(input_arc); + if (!select || select(*this,input_arc)) + predecessors++; + } + if (predecessors == 0) + { + result.push_back(n); + } + else + { + fanin_map[n] = predecessors; + } + } + // main algorithm applies the topographical sort repeatedly. For a DAG, it + // will complete first time. However, with backward arcs, the first + // iteration will fail. The algorithm then tries breaking random arcs to try + // to get an ordering. + for(unsigned i = 0; !fanin_map.empty(); ) + { + // now visit each node in traversal order, decrementing the fanin count of + // all successors. As each successor's fanin count goes to zero, it is + // appended to the result. + for (; i < result.size(); i++) + { + // Note: dereferencing gives us a node iterator + digraph_iterator current = result[i]; + for (unsigned f = 0; f < fanout(current); f++) + { + // only consider successors connected by selected arcs + digraph_arc_iterator output_arc = output(current, f); + digraph_iterator successor = arc_to(output_arc); + if (!select || select(*this,output_arc)) + { + // don't consider arcs that have been eliminated to break a loop + if (fanin_map.find(successor) != fanin_map.end()) + { + --fanin_map[successor]; + if ((fanin_map[successor]) == 0) + { + result.push_back(successor); + fanin_map.erase(fanin_map.find(successor)); + } + } + } + } + } + if (!fanin_map.empty()) + { + // there must be backward arcs preventing completion + // try removing arcs from the sort to get a partial ordering containing all the nodes + + // select an arc that is still relevant to the sort and break it + // first select a node that has non-zero fanin and its predecessor that has non-zero fanin + digraph_iterator stuck_node = fanin_map.begin()->first; + for (unsigned f = 0; f < fanin(stuck_node); f++) + { + // now successively remove input arcs that are still part of the sort until the fanin reduces to zero + // first find a relevant arc - this must be a selected arc that has not yet been traversed by the first half of the algorithm + digraph_arc_iterator input_arc = input(stuck_node, f); + if (!select || select(*this,input_arc)) + { + digraph_iterator predecessor = arc_from(input_arc); + if (fanin_map.find(predecessor) != fanin_map.end()) + { + // found the right combination - remove this arc and then drop out of the fanin loop to restart the outer sort loop + errors.push_back(input_arc); + --fanin_map[stuck_node]; + if ((fanin_map[stuck_node]) == 0) + { + result.push_back(stuck_node); + fanin_map.erase(fanin_map.find(stuck_node)); + break; + } + } + } + } + } + } + return std::make_pair(result,errors); + } + + template + std::pair::node_vector, TYPENAME digraph::arc_vector> + digraph::sort(TYPENAME digraph::arc_select_fn select) + { + std::pair >, + std::vector > > const_result = + const_cast*>(this)->sort(select); + + std::pair >, + std::vector > > result = + std::make_pair(deconstify_nodes(const_result.first),deconstify_arcs(const_result.second)); + return result; + } + + template + TYPENAME digraph::const_node_vector digraph::dag_sort(TYPENAME digraph::arc_select_fn select) const + { + std::pair >, + std::vector > > result = sort(select); + if (result.second.empty()) return result.first; + return std::vector >(); + } + + template + TYPENAME digraph::node_vector digraph::dag_sort(TYPENAME digraph::arc_select_fn select) + { + return deconstify_nodes(const_cast*>(this)->dag_sort(select)); + } + //////////////////////////////////////////////////////////////////////////////// + // Path Algorithms + + template + bool digraph::path_exists_r(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to, + TYPENAME digraph::const_iterator_set& visited, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // Recursive part of the digraph::path_exists function. This is based on a + // depth first search algorithm and stops the moment it finds a path + // regardless of its length. Simply traverse every output and recurse on that + // node until we find the to node or run out of things to recurse on. However, + // to avoid infinite recursion due to cycles in the graph, I need to maintain + // a set of visited nodes. The visited set is updated when a candidate is + // found but tested before the recursion on the candidate so that the number of + // function calls is minimised. + for (unsigned i = 0; i < fanout(from); i++) + { + digraph_arc_iterator arc = output(from,i); + if (!select || select(*this, arc)) + { + digraph_iterator node = arc_to(arc); + // if the node is the target, return immediately + if (node == to) return true; + // update the visited set and give up if the insert fails, which indicates that the node has already been visited + if (!(visited.insert(node).second)) return false; + // now recurse - a path exists from from to to if a path exists from an adjacent node to to + if (path_exists_r(node,to,visited,select)) return true; + } + } + return false; + } + + template + bool digraph::path_exists(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // set up the recursion with its initial visited set and then recurse + std::set > visited; + visited.insert(from); + return path_exists_r(from, to, visited, select); + } + + template + bool digraph::path_exists(TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to, + TYPENAME digraph::arc_select_fn select) + throw(wrong_object,null_dereference,end_dereference) + { + return path_exists(from.constify(), to.constify(), select); + } + + template + void digraph::all_paths_r(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to, + TYPENAME digraph::const_arc_vector& so_far, + TYPENAME digraph::const_path_vector& result, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // This is the recursive part of the all_paths function. The field so_far + // contains the path so far so that when 'to' is reached, the path is + // complete. It serves the same purpose as the visited set in the path_exists + // function except that it also preserves the path order. It also serves the + // purpose of detecting cycles and thus stopping infinite recursion. Every + // time the recursion reaches the to node, a copy of so_far is appended to the + // path set. + for (unsigned i = 0; i < fanout(from); i++) + { + digraph_arc_iterator candidate = output(from,i); + // assert_valid that the arc is selected and then assert_valid that the candidate has not + // been visited on this path and only allow further recursion if it hasn't + if ((!select || select(*this, candidate)) && std::find(so_far.begin(), so_far.end(), candidate) == so_far.end()) + { + // extend the path tracing the route to this arc + so_far.push_back(candidate); + // if the candidate arc points to the target, update the result set and prevent further recursion, otherwise recurse + if (arc_to(candidate) == to) + result.push_back(so_far); + else + all_paths_r(arc_to(candidate),to,so_far,result,select); + so_far.pop_back(); + } + } + } + + template + TYPENAME digraph::const_path_vector + digraph::all_paths(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // set up the recursion with empty data fields and then recurse + std::vector > > result; + std::vector > so_far; + all_paths_r(from, to, so_far, result, select); + return result; + } + + template + TYPENAME digraph::path_vector + digraph::all_paths(TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to, + TYPENAME digraph::arc_select_fn select) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_paths(all_paths(from.constify(), to.constify(), select)); + } + + template + void digraph::reachable_nodes_r(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator_set& visited, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // The recursive part of the reachable_nodes function. + // This is a depth-first traversal again but this time it carries on to find all the reachable nodes + // Just keep recursing on all the adjacent nodes of each node, skipping already visited nodes to avoid cycles + for (unsigned i = 0; i < fanout(from); i++) + { + digraph_arc_iterator arc = output(from,i); + if (!select || select(*this,arc)) + { + digraph_iterator candidate = arc_to(arc); + if (visited.insert(candidate).second) + reachable_nodes_r(candidate,visited,select); + } + } + } + + template + TYPENAME digraph::const_node_vector + digraph::reachable_nodes(TYPENAME digraph::const_iterator from, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // seed the recursion, marking the starting node as already visited + std::set > visited; + visited.insert(from); + reachable_nodes_r(from, visited, select); + // convert the visited set into the required output form + // exclude the starting node + std::vector > result; + for (TYPENAME std::set >::iterator i = visited.begin(); i != visited.end(); i++) + if (*i != from) + result.push_back(*i); + return result; + } + + template + TYPENAME digraph::node_vector + digraph::reachable_nodes(TYPENAME digraph::iterator from, + TYPENAME digraph::arc_select_fn select) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_nodes(reachable_nodes(from.constify(), select)); + } + + template + void digraph::reaching_nodes_r(TYPENAME digraph::const_iterator to, + TYPENAME digraph::const_iterator_set& visited, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // The recursive part of the reaching_nodes function. + // Just like the reachable_nodes_r function but it goes backwards + for (unsigned i = 0; i < fanin(to); i++) + { + digraph_arc_iterator arc = input(to,i); + if (!select || select(*this,arc)) + { + digraph_iterator candidate = arc_from(input(to,i)); + if (visited.insert(candidate).second) + reaching_nodes_r(candidate,visited,select); + } + } + } + + template + TYPENAME digraph::const_node_vector + digraph::reaching_nodes(TYPENAME digraph::const_iterator to, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // seed the recursion, marking the starting node as already visited + std::set > visited; + visited.insert(to); + reaching_nodes_r(to,visited,select); + // convert the visited set into the required output form + // exclude the end node + std::vector > result; + for (TYPENAME std::set >::iterator i = visited.begin(); i != visited.end(); i++) + if (*i != to) + result.push_back(*i); + return result; + } + + template + TYPENAME digraph::node_vector + digraph::reaching_nodes(TYPENAME digraph::iterator to, + TYPENAME digraph::arc_select_fn select) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_nodes(reaching_nodes(to.constify(),select)); + } + + //////////////////////////////////////////////////////////////////////////////// + // Shortest Path Algorithms + + template + TYPENAME digraph::const_arc_vector + digraph::shortest_path(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > > paths = all_paths(from,to,select); + std::vector > shortest; + for (TYPENAME std::vector > >::iterator i = paths.begin(); i != paths.end(); i++) + if (shortest.empty() || i->size() < shortest.size()) + shortest = *i; + return shortest; + } + + template + TYPENAME digraph::arc_vector + digraph::shortest_path(TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to, + TYPENAME digraph::arc_select_fn select) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_arcs(shortest_path(from.constify(),to.constify(),select)); + } + + template + TYPENAME digraph::const_path_vector + digraph::shortest_paths(TYPENAME digraph::const_iterator from, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + from.assert_valid(this); + // This is an unweighted shortest path algorithm based on the algorithm from + // Weiss's book. This is essentially a breadth-first traversal or graph + // colouring algorithm. It is an iterative algorithm, so no recursion here! It + // works by creating a node queue initialised with the starting node. It then + // consumes the queue from front to back. For each node, it finds the + // successors and appends them to the queue. If a node is already 'known' it + // is not added - this avoids cycles. Thus the queue insert ordering + // represents the breadth-first ordering. On the way it creates a map of + // visited nodes. This is a map not a set because it also stores the arc that + // nominated this node as a shortest path. The full path can then be recreated + // from the map by just walking back through the predecessors. The depth (or + // colour) can be determined by the path length. + std::vector > > result; + // initialise the iteration by creating a queue and adding the start node + std::deque > nodes; + nodes.push_back(from); + // Create a map to store the set of known nodes mapped to their predecessor + // arcs. Initialise it with the current node, which has no predecessor. Note + // that the algorithm uses the feature of digraph iterators that they can be + // null iterators and that all null iterators are equal. + typedef std::map, + digraph_arc_iterator > known_map; + known_map known; + known.insert(std::make_pair(from,digraph_arc_iterator())); + // now the iterative part of the algorithm + while(!nodes.empty()) + { + // pop the queue to get the next node to process - unfortunately the STL + // deque::pop does not return the popped value + digraph_iterator current = nodes.front(); + nodes.pop_front(); + // now visit all the successors + for (unsigned i = 0; i < fanout(current); i++) + { + digraph_arc_iterator next_arc = output(current,i); + // assert_valid whether the successor arc is a selected arc and can be part of a path + if (!select || select(*this,next_arc)) + { + digraph_iterator next = arc_to(next_arc); + // Discard any successors that are known because to be known already they + // must have another shorter path. Otherwise add the successor node to the + // queue to be visited later. To minimise the overhead of map lookup I use + // the usual trick of trying to insert the node and determining whether + // the node was known by the success or failure of the insertion - this is + // a Good STL Trick (TM). + if (known.insert(std::make_pair(next,next_arc)).second) + nodes.push_back(next); + } + } + } + // The map contains the results as an unordered set of nodes, mapped to their + // predecessor arcs and weight. This now needs to be converted into a set of + // paths. This is done by starting with a node from the map, finding its + // predecessor arc and therefore its predecessor node, looking that up in the + // map to find its predecessor and so on until the start node is reached (it + // has a null predecessor). Note that the known set includes the from node + // which does not generate a path. + for (TYPENAME known_map::iterator i = known.begin(); i != known.end(); i++) + { + if (i->first != from) + { + const_arc_vector this_path; + for (TYPENAME known_map::iterator node = i; + node->second.valid(); + node = known.find(arc_from(node->second))) + this_path.insert(this_path.begin(),node->second); + result.push_back(this_path); + } + } + return result; + } + + template + TYPENAME digraph::path_vector + digraph::shortest_paths(TYPENAME digraph::iterator from, + TYPENAME digraph::arc_select_fn select) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_paths(shortest_paths(from.constify(),select)); + } + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus diff --git a/src/Moof/stlplus/exceptions.hpp b/src/Moof/stlplus/exceptions.hpp new file mode 100755 index 0000000..3549ff4 --- /dev/null +++ b/src/Moof/stlplus/exceptions.hpp @@ -0,0 +1,71 @@ +#ifndef STLPLUS_EXCEPTIONS +#define STLPLUS_EXCEPTIONS +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +// The set of general exceptions thrown by STLplus components + +//////////////////////////////////////////////////////////////////////////////// +#include "containers_fixes.hpp" +#include +#include + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // Thrown if a pointer or an iterator is dereferenced when it is null + + class null_dereference : public std::logic_error + { + public: + null_dereference(const std::string& description) throw() : + std::logic_error(std::string("stlplus::null_dereference: ") + description) {} + ~null_dereference(void) throw() {} + }; + + //////////////////////////////////////////////////////////////////////////////// + // Thrown if an iterator is dereferenced when it is pointing to the end element + + class end_dereference : public std::logic_error + { + public: + end_dereference(const std::string& description) throw() : + std::logic_error("stlplus::end_dereference: " + description) {} + ~end_dereference(void) throw() {} + }; + + //////////////////////////////////////////////////////////////////////////////// + // Thrown if an iterator is used with the wrong container. In other words, an + // iterator is created as a pointer to a sub-object within a container. If + // that iterator is then used with a different container, this exception is + // thrown. + + class wrong_object : public std::logic_error + { + public: + wrong_object(const std::string& description) throw() : + std::logic_error("stlplus::wrong_object: " + description) {} + ~wrong_object(void) throw() {} + }; + + //////////////////////////////////////////////////////////////////////////////// + // Thrown if an attempt is made to copy an object that is uncopyable + + class illegal_copy : public std::logic_error + { + public: + illegal_copy(const std::string& description) throw() : + std::logic_error("stlplus::illegal_copy: " + description) {} + ~illegal_copy(void) throw() {} + }; + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + +#endif diff --git a/src/Moof/stlplus/foursome.hpp b/src/Moof/stlplus/foursome.hpp new file mode 100755 index 0000000..36437f1 --- /dev/null +++ b/src/Moof/stlplus/foursome.hpp @@ -0,0 +1,59 @@ +#ifndef STLPLUS_FOURSOME +#define STLPLUS_FOURSOME +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton, from an original by Dan Milton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +// The next in the series pair->triple->foursome + +// Originally called quadruple but that clashed (as did quad) with system +// libraries on some operating systems + +//////////////////////////////////////////////////////////////////////////////// +#include "containers_fixes.hpp" + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // the foursome class + + template + struct foursome + { + typedef T1 first_type; + typedef T2 second_type; + typedef T3 third_type; + typedef T4 fourth_type; + + T1 first; + T2 second; + T3 third; + T4 fourth; + + foursome(void); + foursome(const T1& p1, const T2& p2, const T3& p3, const T4& p4); + foursome(const foursome& t2); + }; + + //////////////////////////////////////////////////////////////////////////////// + // creation + + template + foursome make_foursome(const T1& first, const T2& second, const T3& third, const T4& fourth); + + //////////////////////////////////////////////////////////////////////////////// + // comparison + + template + bool operator == (const foursome& left, const foursome& right); + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + +#include "foursome.tpp" +#endif diff --git a/src/Moof/stlplus/foursome.tpp b/src/Moof/stlplus/foursome.tpp new file mode 100755 index 0000000..f1dd9b3 --- /dev/null +++ b/src/Moof/stlplus/foursome.tpp @@ -0,0 +1,59 @@ +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton, from an original by Dan Milton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +//////////////////////////////////////////////////////////////////////////////// + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // the foursome class + + template + foursome::foursome(void) : + first(), second(), third(), fourth() + { + } + + template + foursome::foursome(const T1& p1, const T2& p2, const T3& p3, const T4& p4) : + first(p1), second(p2), third(p3), fourth(p4) + { + } + + template + foursome::foursome(const foursome& t2) : + first(t2.first), second(t2.second), third(t2.third), fourth(t2.fourth) + { + } + + //////////////////////////////////////////////////////////////////////////////// + // creation + + template + foursome make_foursome(const T1& first, const T2& second, const T3& third, const T4& fourth) + { + return foursome(first,second,third,fourth); + } + + //////////////////////////////////////////////////////////////////////////////// + // comparison + + template + bool operator == (const foursome& left, const foursome& right) + { + // foursomes are equal if all elements are equal + return + left.first == right.first && + left.second == right.second && + left.third == right.third && + left.fourth == right.fourth; + } + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus diff --git a/src/Moof/stlplus/hash.hpp b/src/Moof/stlplus/hash.hpp new file mode 100755 index 0000000..05d3b7d --- /dev/null +++ b/src/Moof/stlplus/hash.hpp @@ -0,0 +1,196 @@ +#ifndef STLPLUS_HASH +#define STLPLUS_HASH +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +// A chained hash table using STL semantics + +//////////////////////////////////////////////////////////////////////////////// +#include "containers_fixes.hpp" +#include "exceptions.hpp" +#include "safe_iterator.hpp" +#include + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // internals + + template class hash; + template class hash_element; + + //////////////////////////////////////////////////////////////////////////////// + // iterator class + + template + class hash_iterator : public safe_iterator,hash_element > + { + public: + friend class hash; + + // local type definitions + // an iterator points to a value whilst a const_iterator points to a const value + typedef V value_type; + typedef hash_iterator > iterator; + typedef hash_iterator > const_iterator; + typedef hash_iterator this_iterator; + typedef V& reference; + typedef V* pointer; + + // constructor to create a null iterator - you must assign a valid value to this iterator before using it + // any attempt to dereference or use a null iterator is an error + // the only valid thing you can do is assign an iterator to it + hash_iterator(void); + ~hash_iterator(void); + + // Type conversion methods allow const_iterator and iterator to be converted + // convert an iterator/const_iterator to a const_iterator + const_iterator constify(void) const; + // convert an iterator/const_iterator to an iterator + iterator deconstify(void) const; + + // increment operators used to step through the set of all values in a hash + // it is only legal to increment a valid iterator + // there's no decrement - I've only implemented this as a unidirectional iterator + // pre-increment + this_iterator& operator ++ (void) + throw(null_dereference,end_dereference); + // post-increment + this_iterator operator ++ (int) + throw(null_dereference,end_dereference); + + // test useful for testing whether iteration has completed + bool operator == (const this_iterator& r) const; + bool operator != (const this_iterator& r) const; + bool operator < (const this_iterator& r) const; + + // access the value - a const_iterator gives you a const value, an iterator a non-const value + // it is illegal to dereference an invalid (i.e. null or end) iterator + reference operator*(void) const + throw(null_dereference,end_dereference); + pointer operator->(void) const + throw(null_dereference,end_dereference); + + private: + friend class hash_element; + + // constructor used by hash to create a non-null iterator + // you cannot create a valid iterator except by calling a hash method that returns one + explicit hash_iterator(hash_element* element); + // constructor used to create an end iterator + explicit hash_iterator(const hash* owner); + // used to create an alias of an iterator + explicit hash_iterator(const safe_iterator, hash_element >& iterator); + }; + + //////////////////////////////////////////////////////////////////////////////// + // Hash class + // K = key type + // T = value type + // H = hash function object with the profile 'unsigned H(const K&)' + // E = equal function object with profile 'bool E(const K&, const K&)' defaults to equal_to which in turn calls '==' + + template > + class hash + { + public: + typedef unsigned size_type; + typedef K key_type; + typedef T data_type; + typedef T mapped_type; + typedef std::pair value_type; + typedef hash_iterator iterator; + typedef hash_iterator const_iterator; + + // construct a hash table with specified number of bins + // the default 0 bins means leave it to the table to decide + // specifying 0 bins also enables auto-rehashing, otherwise auto-rehashing defaults off + hash(unsigned bins = 0); + ~hash(void); + + // copy and equality copy the data elements but not the size of the copied table + hash(const hash&); + hash& operator = (const hash&); + + // test for an empty table and for the size of a table + // efficient because the size is stored separately from the table contents + bool empty(void) const; + unsigned size(void) const; + + // test for equality - two hashes are equal if they contain equal values + bool operator == (const hash&) const; + bool operator != (const hash&) const; + + // switch auto-rehash on + void auto_rehash(void); + // switch auto-rehash off + void manual_rehash(void); + // force a rehash now + // default of 0 means implement built-in size calculation for rehashing (recommended - it doubles the number of bins) + void rehash(unsigned bins = 0); + // test the loading ratio, which is the size divided by the number of bins + // use this if you are doing your own rehashing + // the recommendation is to double the bins when the loading exceeds 0.5 which is what auto-rehashing does + float loading(void) const; + + // test for the presence of a key + bool present(const K& key) const; + // provide map equivalent key count function (0 or 1, as not a multimap) + size_type count(const K& key) const; + + // insert a new key/data pair - replaces any previous value for this key + iterator insert(const K& key, const T& data); + // insert a copy of the pair into the table (std::map compatible) + std::pair insert(const value_type& value); + // insert a new key and return the iterator so that the data can be filled in + iterator insert(const K& key); + + // remove a key/data pair from the hash table + bool erase(const K& key); + // remove all elements from the hash table + void erase(void); + // provide the std::map equivalent clear function + void clear(void); + + // find a key and return an iterator to it + // The iterator is like a pointer to a pair + // end() is returned if the find fails + const_iterator find(const K& key) const; + iterator find(const K& key); + + // returns the data corresponding to the key + // const version is used for const hashes and cannot change the hash, so failure causes an exception + // non-const version is for non-const hashes and is like map - it creates a new key/data pair if find fails + const T& operator[] (const K& key) const throw(std::out_of_range); + T& operator[] (const K& key); + + // iterators allow the hash table to be traversed + // iterators remain valid unless an item is removed or unless a rehash happens + const_iterator begin(void) const; + iterator begin(void); + const_iterator end(void) const; + iterator end(void); + + // internals + private: + friend class hash_element; + friend class hash_iterator >; + friend class hash_iterator >; + + unsigned m_rehash; + unsigned m_bins; + unsigned m_size; + hash_element** m_values; + }; + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + +#include "hash.tpp" +#endif diff --git a/src/Moof/stlplus/hash.tpp b/src/Moof/stlplus/hash.tpp new file mode 100755 index 0000000..bcb5bc5 --- /dev/null +++ b/src/Moof/stlplus/hash.tpp @@ -0,0 +1,575 @@ +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +//////////////////////////////////////////////////////////////////////////////// + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // the element stored in the hash + + template + class hash_element + { + public: + master_iterator, hash_element > m_master; + std::pair m_value; + hash_element* m_next; + unsigned m_hash; + + hash_element(const hash* owner, const K& key, const T& data, unsigned hash) : + m_master(owner,this), m_value(key,data), m_next(0), m_hash(hash) + { + } + + hash_element(const hash* owner, const std::pair& value, unsigned hash) : + m_master(owner,this), m_value(value), m_next(0), m_hash(hash) + { + } + + ~hash_element(void) + { + m_next = 0; + m_hash = 0; + } + + const hash* owner(void) const + { + return m_master.owner(); + } + + // generate the bin number from the hash value and the owner's number of bins + unsigned bin(void) const + { + return m_hash % (owner()->m_bins); + } + }; + + //////////////////////////////////////////////////////////////////////////////// + // iterator + + // null constructor + template + hash_iterator::hash_iterator(void) + { + } + + // non-null constructor used from within the hash to construct a valid iterator + template + hash_iterator::hash_iterator(hash_element* element) : + safe_iterator,hash_element >(element->m_master) + { + } + + // constructor used to create an end iterator + template + hash_iterator::hash_iterator(const hash* owner) : + safe_iterator,hash_element >(owner) + { + } + + template + hash_iterator::hash_iterator(const safe_iterator, hash_element >& iterator) : + safe_iterator,hash_element >(iterator) + { + } + + // destructor + + template + hash_iterator::~hash_iterator(void) + { + } + + // mode conversions + + template + TYPENAME hash_iterator::const_iterator hash_iterator::constify(void) const + { + return hash_iterator >(*this); + } + + template + TYPENAME hash_iterator::iterator hash_iterator::deconstify(void) const + { + return hash_iterator >(*this); + } + + // increment operator looks for the next element in the table + // if there isn't one, then this becomes an end() iterator with m_bin = m_bins + template + TYPENAME hash_iterator::this_iterator& hash_iterator::operator ++ (void) + throw(null_dereference,end_dereference) + { + this->assert_valid(); + if (this->node()->m_next) + set(this->node()->m_next->m_master); + else + { + // failing that, subsequent hash values are tried until either an element is found or there are no more bins + // in which case it becomes an end() iterator + hash_element* element = 0; + unsigned current_bin = this->node()->bin(); + for(current_bin++; !element && (current_bin < this->owner()->m_bins); current_bin++) + element = this->owner()->m_values[current_bin]; + if (element) + set(element->m_master); + else + this->set_end(); + } + return *this; + } + + // post-increment is defined in terms of pre-increment + template + TYPENAME hash_iterator::this_iterator hash_iterator::operator ++ (int) + throw(null_dereference,end_dereference) + { + hash_iterator old(*this); + ++(*this); + return old; + } + + // two iterators are equal if they point to the same element + // both iterators must be non-null and belong to the same table + template + bool hash_iterator::operator == (const hash_iterator& r) const + { + return equal(r); + } + + template + bool hash_iterator::operator != (const hash_iterator& r) const + { + return !operator==(r); + } + + template + bool hash_iterator::operator < (const hash_iterator& r) const + { + return compare(r) < 0; + } + + // iterator dereferencing is only legal on a non-null iterator + template + V& hash_iterator::operator*(void) const + throw(null_dereference,end_dereference) + { + this->assert_valid(); + return this->node()->m_value; + } + + template + V* hash_iterator::operator->(void) const + throw(null_dereference,end_dereference) + { + return &(operator*()); + } + + //////////////////////////////////////////////////////////////////////////////// + // hash + + // totally arbitrary initial size used for auto-rehashed tables + static unsigned hash_default_bins = 127; + + // constructor + // tests whether the user wants auto-rehash + // sets the rehash point to be a loading of 1.0 by setting it to the number of bins + // uses the user's size unless this is zero, in which case implement the default + + template + hash::hash(unsigned bins) : + m_rehash(bins), m_bins(bins > 0 ? bins : hash_default_bins), m_size(0), m_values(0) + { + m_values = new hash_element*[m_bins]; + for (unsigned i = 0; i < m_bins; i++) + m_values[i] = 0; + } + + template + hash::~hash(void) + { + // delete all the elements + clear(); + // and delete the data structure + delete[] m_values; + m_values = 0; + } + + // as usual, implement the copy constructor i.t.o. the assignment operator + + template + hash::hash(const hash& right) : + m_rehash(right.m_rehash), m_bins(right.m_bins), m_size(0), m_values(0) + { + m_values = new hash_element*[right.m_bins]; + // copy the rehash behaviour as well as the size + for (unsigned i = 0; i < m_bins; i++) + m_values[i] = 0; + *this = right; + } + + // assignment operator + // this is done by copying the elements + // the source and target hashes can be different sizes + // the hash is self-copy safe, i.e. it is legal to say x = x; + + template + hash& hash::operator = (const hash& r) + { + // make self-copy safe + if (&r == this) return *this; + // remove all the existing elements + clear(); + // copy the elements across - remember that this is rehashing because the two + // tables can be different sizes so there is no quick way of doing this by + // copying the lists + for (hash_iterator > i = r.begin(); i != r.end(); ++i) + insert(i->first, i->second); + return *this; + } + + // number of values in the hash + template + bool hash::empty(void) const + { + return m_size == 0; + } + + template + unsigned hash::size(void) const + { + return m_size; + } + + // equality + template + bool hash::operator == (const hash& right) const + { + // this table is the same as the right table if they are the same table! + if (&right == this) return true; + // they must be the same size to be equal + if (m_size != right.m_size) return false; + // now every key in this must be in right and have the same data + for (hash_iterator > i = begin(); i != end(); i++) + { + hash_iterator > found = right.find(i->first); + if (found == right.end()) return false; + if (!(i->second == found->second)) return false; + } + return true; + } + + // set up the hash to auto-rehash at a specific size + // setting the rehash size to 0 forces manual rehashing + template + void hash::auto_rehash(void) + { + m_rehash = m_bins; + } + + template + void hash::manual_rehash(void) + { + m_rehash = 0; + } + + // the rehash function + // builds a new hash table and moves the elements (without copying) from the old to the new + // I store the un-modulused hash value in the element for more efficient rehashing + // passing 0 to the bins parameter does auto-rehashing + // passing any other value forces the number of bins + + template + void hash::rehash(unsigned bins) + { + // user specified size: just take the user's value + // auto calculate: if the load is high, increase the size; else do nothing + unsigned new_bins = bins ? bins : m_bins; + if (bins == 0 && m_size > 0) + { + // these numbers are pretty arbitrary + // TODO - make them user-customisable? + float load = loading(); + if (load > 2.0) + new_bins = (unsigned)(m_bins * load); + else if (load > 1.0) + new_bins = m_bins * 2; + } + if (new_bins == m_bins) return; + // set the new rehashing point if auto-rehashing is on + if (m_rehash) m_rehash = new_bins; + // move aside the old structure + hash_element** old_values = m_values; + unsigned old_bins = m_bins; + // create a replacement structure + m_values = new hash_element*[new_bins]; + for (unsigned i = 0; i < new_bins; i++) + m_values[i] = 0; + m_bins = new_bins; + // move all the old elements across, rehashing each one + for (unsigned j = 0; j < old_bins; j++) + { + while(old_values[j]) + { + // unhook from the old structure + hash_element* current = old_values[j]; + old_values[j] = current->m_next; + // rehash using the stored hash value + unsigned bin = current->bin(); + // hook it into the new structure + current->m_next = m_values[bin]; + m_values[bin] = current; + } + } + // now delete the old structure + delete[] old_values; + } + + // the loading is the average number of elements per bin + // this simplifies to the total elements divided by the number of bins + + template + float hash::loading(void) const + { + return (float)m_size / (float)m_bins; + } + + // remove all elements from the table + + template + void hash::erase(void) + { + // unhook the list elements and destroy them + for (unsigned i = 0; i < m_bins; i++) + { + hash_element* current = m_values[i]; + while(current) + { + hash_element* next = current->m_next; + delete current; + current = next; + } + m_values[i] = 0; + } + m_size = 0; + } + + // test for whether a key is present in the table + + template + bool hash::present(const K& key) const + { + return find(key) != end(); + } + + template + TYPENAME hash::size_type hash::count(const K& key) const + { + return present() ? 1 : 0; + } + + // add a key and data element to the table - defined in terms of the general-purpose pair insert function + + template + TYPENAME hash::iterator hash::insert(const K& key, const T& data) + { + return insert(std::pair(key,data)).first; + } + + // insert a key/data pair into the table + // this removes any old value with the same key since there is no multihash functionality + + template + std::pair::iterator, bool> hash::insert(const std::pair& value) + { + // if auto-rehash is enabled, implement the auto-rehash before inserting the new value + // the table is rehashed if this insertion makes the loading exceed 1.0 + if (m_rehash && (m_size >= m_rehash)) rehash(); + // calculate the new hash value + unsigned hash_value_full = H()(value.first); + unsigned bin = hash_value_full % m_bins; + bool inserted = true; + // unhook any previous value with this key + // this has been inlined from erase(key) so that the hash value is not calculated twice + hash_element* previous = 0; + for (hash_element* current = m_values[bin]; current; previous = current, current = current->m_next) + { + // first check the full stored hash value + if (current->m_hash != hash_value_full) continue; + + // next try the equality operator + if (!E()(current->m_value.first, value.first)) continue; + + // unhook this value and destroy it + if (previous) + previous->m_next = current->m_next; + else + m_values[bin] = current->m_next; + delete current; + m_size--; + + // we've overwritten a previous value + inserted = false; + + // assume there can only be one match so we can give up now + break; + } + // now hook in a new list element at the start of the list for this hash value + hash_element* new_item = new hash_element(this, value, hash_value_full); + new_item->m_next = m_values[bin]; + m_values[bin] = new_item; + // increment the size count + m_size++; + // construct an iterator from the list node, and return whether inserted + return std::make_pair(hash_iterator >(new_item), inserted); + } + + // insert a key with an empty data field ready to be filled in later + + template + TYPENAME hash::iterator hash::insert(const K& key) + { + return insert(key,T()); + } + + // remove a key from the table - return true if the key was found and removed, false if it wasn't present + + template + bool hash::erase(const K& key) + { + unsigned hash_value_full = H()(key); + unsigned bin = hash_value_full % m_bins; + // scan the list for an element with this key + // need to keep a previous pointer because the lists are single-linked + hash_element* previous = 0; + for (hash_element* current = m_values[bin]; current; previous = current, current = current->m_next) + { + // first check the full stored hash value + if (current->m_hash != hash_value_full) continue; + + // next try the equality operator + if (!E()(current->m_value.first, key)) continue; + + // found this key, so unhook the element from the list + if (previous) + previous->m_next = current->m_next; + else + m_values[bin] = current->m_next; + // destroy it + delete current; + // remember to maintain the size count + m_size--; + return true; + } + return false; + } + + template + void hash::clear(void) + { + erase(); + } + + // search for a key in the table and return an iterator to it + // if the search fails, returns an end() iterator + + template + TYPENAME hash::const_iterator hash::find(const K& key) const + { + // scan the list for this key's hash value for the element with a matching key + unsigned hash_value_full = H()(key); + unsigned bin = hash_value_full % m_bins; + for (hash_element* current = m_values[bin]; current; current = current->m_next) + { + if (current->m_hash == hash_value_full && E()(current->m_value.first, key)) + return hash_iterator >(current); + } + return end(); + } + + template + TYPENAME hash::iterator hash::find(const K& key) + { + // scan the list for this key's hash value for the element with a matching key + unsigned hash_value_full = H()(key); + unsigned bin = hash_value_full % m_bins; + for (hash_element* current = m_values[bin]; current; current = current->m_next) + { + if (current->m_hash == hash_value_full && E()(current->m_value.first, key)) + return hash_iterator >(current); + } + return end(); + } + + // table lookup by key using the index operator[], returning a reference to the data field, not an iterator + // this is rather like the std::map's [] operator + // the difference is that I have a const and non-const version + // the const version will not create the element if not present already, but the non-const version will + // the non-const version is compatible with the behaviour of the map + + template + const T& hash::operator[] (const K& key) const throw(std::out_of_range) + { + // this const version cannot change the hash, so has to raise an exception if the key is missing + hash_iterator > found = find(key); + if (found == end()) + throw std::out_of_range("key not found in stlplus::hash::operator[]"); + return found->second; + } + + template + T& hash::operator[] (const K& key) + { + // this non-const version can change the hash, so creates a new element if the key is missing + hash_iterator > found = find(key); + if (found == end()) + found = insert(key); + return found->second; + } + + // iterators + + template + TYPENAME hash::const_iterator hash::begin(void) const + { + // find the first element + for (unsigned bin = 0; bin < m_bins; bin++) + if (m_values[bin]) + return hash_iterator >(m_values[bin]); + // if the hash is empty, return the end iterator + return end(); + } + + template + TYPENAME hash::iterator hash::begin(void) + { + // find the first element + for (unsigned bin = 0; bin < m_bins; bin++) + if (m_values[bin]) + return hash_iterator >(m_values[bin]); + // if the hash is empty, return the end iterator + return end(); + } + + template + TYPENAME hash::const_iterator hash::end(void) const + { + return hash_iterator >(this); + } + + template + TYPENAME hash::iterator hash::end(void) + { + return hash_iterator >(this); + } + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + diff --git a/src/Moof/stlplus/matrix.hpp b/src/Moof/stlplus/matrix.hpp new file mode 100755 index 0000000..fd0a512 --- /dev/null +++ b/src/Moof/stlplus/matrix.hpp @@ -0,0 +1,62 @@ +#ifndef STLPLUS_MATRIX +#define STLPLUS_MATRIX +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +// General-purpose 2D matrix data structure + +//////////////////////////////////////////////////////////////////////////////// +#include "containers_fixes.hpp" + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + + template class matrix + { + public: + matrix(unsigned rows = 0, unsigned cols = 0, const T& fill = T()) throw(); + ~matrix(void) throw(); + + matrix(const matrix&) throw(); + matrix& operator =(const matrix&) throw(); + + void resize(unsigned rows, unsigned cols, const T& fill = T()) throw(); + + unsigned rows(void) const throw(); + unsigned columns(void) const throw(); + + void erase(const T& fill = T()) throw(); + void erase(unsigned row, unsigned col, const T& fill = T()) throw(std::out_of_range); + void insert(unsigned row, unsigned col, const T&) throw(std::out_of_range); + const T& item(unsigned row, unsigned col) const throw(std::out_of_range); + T& item(unsigned row, unsigned col) throw(std::out_of_range); + const T& operator()(unsigned row, unsigned col) const throw(std::out_of_range); + T& operator()(unsigned row, unsigned col) throw(std::out_of_range); + + void fill(const T& item = T()) throw(); + void fill_column(unsigned col, const T& item = T()) throw(std::out_of_range); + void fill_row(unsigned row, const T& item = T()) throw(std::out_of_range); + void fill_leading_diagonal(const T& item = T()) throw(); + void fill_trailing_diagonal(const T& item = T()) throw(); + void make_identity(const T& one, const T& zero = T()) throw(); + + void transpose(void) throw(); + + private: + unsigned m_rows; + unsigned m_cols; + T** m_data; + }; + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + +#include "matrix.tpp" +#endif diff --git a/src/Moof/stlplus/matrix.tpp b/src/Moof/stlplus/matrix.tpp new file mode 100755 index 0000000..65ec779 --- /dev/null +++ b/src/Moof/stlplus/matrix.tpp @@ -0,0 +1,215 @@ +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +//////////////////////////////////////////////////////////////////////////////// + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + + template + matrix::matrix(unsigned rows, unsigned cols, const T& fill) throw() + { + m_rows = 0; + m_cols = 0; + m_data = 0; + resize(rows,cols,fill); + } + + template + matrix::~matrix(void) throw() + { + for (unsigned row = 0; row < m_rows; row++) + delete[] m_data[row]; + delete[] m_data; + } + + template + matrix::matrix(const matrix& r) throw() + { + m_rows = 0; + m_cols = 0; + m_data = 0; + *this = r; + } + + template + matrix& matrix::operator =(const matrix& right) throw() + { + // clear the old values + for (unsigned row = 0; row < m_rows; row++) + delete[] m_data[row]; + delete[] m_data; + m_rows = 0; + m_cols = 0; + m_data = 0; + // now reconstruct with the new + resize(right.m_rows, right.m_cols); + for (unsigned row = 0; row < m_rows; row++) + for (unsigned col = 0; col < m_cols; col++) + m_data[row][col] = right.m_data[row][col]; + return *this; + } + + template + void matrix::resize(unsigned rows, unsigned cols, const T& fill) throw() + { + // a grid is an array of rows, where each row is an array of T + // a zero-row or zero-column matrix has a null grid + // TODO - make this exception-safe - new could throw here and that would cause a memory leak + T** new_grid = 0; + if (rows && cols) + { + new_grid = new T*[rows]; + for (unsigned row = 0; row < rows; row++) + { + new_grid[row] = new T[cols]; + // copy old items to the new grid but only within the bounds of the intersection of the old and new grids + // fill the rest of the grid with the initial value + for (unsigned col = 0; col < cols; col++) + if (row < m_rows && col < m_cols) + new_grid[row][col] = m_data[row][col]; + else + new_grid[row][col] = fill; + } + } + // destroy the old grid + for (unsigned row = 0; row < m_rows; row++) + delete[] m_data[row]; + delete[] m_data; + // move the new data into the matrix + m_data = new_grid; + m_rows = rows; + m_cols = cols; + } + + template + unsigned matrix::rows(void) const throw() + { + return m_rows; + } + + template + unsigned matrix::columns(void) const throw() + { + return m_cols; + } + + template + void matrix::erase(const T& fill) throw() + { + for (unsigned row = 0; row < m_rows; row++) + for (unsigned col = 0; col < m_cols; col++) + insert(row,col,fill); + } + + template + void matrix::erase(unsigned row, unsigned col, const T& fill) throw(std::out_of_range) + { + insert(row,col,fill); + } + + template + void matrix::insert(unsigned row, unsigned col, const T& element) throw(std::out_of_range) + { + if (row >= m_rows) throw std::out_of_range("matrix::insert row"); + if (col >= m_cols) throw std::out_of_range("matrix::insert col"); + m_data[row][col] = element; + } + + template + const T& matrix::item(unsigned row, unsigned col) const throw(std::out_of_range) + { + if (row >= m_rows) throw std::out_of_range("matrix::item row"); + if (col >= m_cols) throw std::out_of_range("matrix::item col"); + return m_data[row][col]; + } + + template + T& matrix::item(unsigned row, unsigned col) throw(std::out_of_range) + { + if (row >= m_rows) throw std::out_of_range("matrix::item row"); + if (col >= m_cols) throw std::out_of_range("matrix::item col"); + return m_data[row][col]; + } + + template + const T& matrix::operator()(unsigned row, unsigned col) const throw(std::out_of_range) + { + if (row >= m_rows) throw std::out_of_range("matrix::operator() row"); + if (col >= m_cols) throw std::out_of_range("matrix::operator() col"); + return m_data[row][col]; + } + + template + T& matrix::operator()(unsigned row, unsigned col) throw(std::out_of_range) + { + if (row >= m_rows) throw std::out_of_range("matrix::operator() row"); + if (col >= m_cols) throw std::out_of_range("matrix::operator() col"); + return m_data[row][col]; + } + + template + void matrix::fill(const T& item) throw() + { + erase(item); + } + + template + void matrix::fill_column(unsigned col, const T& item) throw (std::out_of_range) + { + if (col >= m_cols) throw std::out_of_range("matrix::fill_column"); + for (unsigned row = 0; row < m_rows; row++) + insert(row, col, item); + } + + template + void matrix::fill_row(unsigned row, const T& item) throw (std::out_of_range) + { + if (row >= m_rows) throw std::out_of_range("matrix::fill_row"); + for (unsigned col = 0; col < m_cols; col++) + insert(row, col, item); + } + + template + void matrix::fill_leading_diagonal(const T& item) throw() + { + for (unsigned i = 0; i < m_cols && i < m_rows; i++) + insert(i, i, item); + } + + template + void matrix::fill_trailing_diagonal(const T& item) throw() + { + for (unsigned i = 0; i < m_cols && i < m_rows; i++) + insert(i, m_cols-i-1, item); + } + + template + void matrix::make_identity(const T& one, const T& zero) throw() + { + fill(zero); + fill_leading_diagonal(one); + } + + template + void matrix::transpose(void) throw() + { + // no gain in manipulating this, since building a new matrix is no less efficient + matrix transposed(columns(), rows()); + for (unsigned row = 0; row < rows(); row++) + for (unsigned col = 0; col < columns(); col++) + transposed.insert(col,row,item(row,col)); + // TODO - avoid an extra copy by swapping the member data here + *this = transposed; + } + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + diff --git a/src/Moof/stlplus/ntree.hpp b/src/Moof/stlplus/ntree.hpp new file mode 100755 index 0000000..33817e2 --- /dev/null +++ b/src/Moof/stlplus/ntree.hpp @@ -0,0 +1,364 @@ +#ifndef STLPLUS_NTREE +#define STLPLUS_NTREE +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +// A templated n-ary tree data structure. STL-like but the definition of +// iterators is really only applicable to one-dimensional structures. I use +// iterators to access tree nodes, but there is no increment or decrement +// operators for them. I also define prefix and postfix traversal iterators +// which do have increment. + +//////////////////////////////////////////////////////////////////////////////// +#include "containers_fixes.hpp" +#include "exceptions.hpp" +#include "safe_iterator.hpp" + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // Internals + + template class ntree_node; + template class ntree; + template class ntree_iterator; + template class ntree_prefix_iterator; + template class ntree_postfix_iterator; + + //////////////////////////////////////////////////////////////////////////////// + // Iterators + + // Simple iterators which are just used as pointers to tree nodes. These have + // no increment or decrement operations defined. An uninitialised iterator is + // null - similarly, if you ask for the root of an empty tree or the parent of + // the root node then you get a null iterator. + + template + class ntree_iterator : public safe_iterator,ntree_node > + { + public: + // local type definitions + // an iterator points to an object whilst a const_iterator points to a const object + typedef ntree_iterator iterator; + typedef ntree_iterator const_iterator; + typedef ntree_iterator this_iterator; + typedef TRef reference; + typedef TPtr pointer; + + // constructor to create a null iterator - you must assign a valid value to this iterator before using it + ntree_iterator(void); + ~ntree_iterator(void); + + // Type conversion methods allow const_iterator and iterator to be converted + const_iterator constify(void) const; + iterator deconstify(void) const; + + // tests useful for putting iterators into other STL structures and for testing whether iteration has completed + bool operator == (const this_iterator& r) const; + bool operator != (const this_iterator& r) const; + bool operator < (const this_iterator& r) const; + + // access the node data - a const_iterator gives you a const element, an iterator a non-const element + // it is illegal to dereference an invalid (i.e. null or end) iterator + reference operator*(void) const + throw(null_dereference,end_dereference); + pointer operator->(void) const + throw(null_dereference,end_dereference); + + friend class ntree; + friend class ntree_prefix_iterator; + friend class ntree_postfix_iterator; + + public: + // Note: I had to make this public to get round a compiler problem - it should be private + // you cannot create a valid iterator except by calling an ntree method that returns one + // constructor used by ntree to create a non-null iterator + explicit ntree_iterator(ntree_node* node); + // constructor used by ntree to create an end iterator + explicit ntree_iterator(const ntree* owner); + // used to create an alias of an iterator + explicit ntree_iterator(const safe_iterator, ntree_node >& iterator); + }; + + // Traversal iterators are like iterators but they have increment operators (++) + // - prefix_iterator visits the nodes of the tree in prefix order + // - postfix_iterator visits the nodes of the tree in postfix order. + // There is no such thing as infix order for an n-ary tree and you cannot + // traverse backwards with these iterators. These follow the STL convention in + // that you iterate from a begin to an end - in this case ntree exports + // prefix_begin()/prefix_end() and postfix_begin()/postfix_end(). You can + // simplify these iterators to the basic iterator above for functions that + // require a simple iterator. + + template + class ntree_prefix_iterator + { + public: + typedef ntree_prefix_iterator iterator; + typedef ntree_prefix_iterator const_iterator; + typedef ntree_prefix_iterator this_iterator; + typedef ntree_iterator simple_iterator; + typedef TRef reference; + typedef TPtr pointer; + + // constructor to create a null iterator - you must assign a valid value to this iterator before using it + ntree_prefix_iterator(void); + ~ntree_prefix_iterator(void); + + // tests + // a null iterator is one that has not been initialised with a value yet + // i.e. you just declared it but didn't assign to it + bool null(void) const; + // an end iterator is one that points to the end element of the list of nodes + // in STL conventions this is one past the last valid element and must not be dereferenced + bool end(void) const; + // a valid iterator is one that can be dereferenced + // i.e. non-null and non-end + bool valid(void) const; + + // Type conversion methods allow const_iterator and iterator to be converted + // convert an iterator/const_iterator to a const_iterator + const_iterator constify(void) const; + iterator deconstify(void) const; + + // generate a simple iterator from a traversal iterator + ntree_iterator simplify(void) const; + + // tests useful for putting iterators into other STL structures and for testing whether iteration has completed + bool operator == (const this_iterator& r) const; + bool operator != (const this_iterator& r) const; + bool operator < (const this_iterator& r) const; + + // increment/decrement operators used to step through the set of all nodes in a graph + // it is only legal to increment a valid iterator + // pre-increment + this_iterator& operator ++ (void) + throw(null_dereference,end_dereference); + // post-increment + this_iterator operator ++ (int) + throw(null_dereference,end_dereference); + + // access the node data - a const_iterator gives you a const element, an iterator a non-const element + // it is illegal to dereference an invalid (i.e. null or end) iterator + reference operator*(void) const + throw(null_dereference,end_dereference); + pointer operator->(void) const + throw(null_dereference,end_dereference); + + friend class ntree; + friend class ntree_iterator; + + private: + ntree_iterator m_iterator; + + explicit ntree_prefix_iterator(const ntree_iterator& i); + const ntree_iterator& get_iterator(void) const; + ntree_iterator& get_iterator(void); + }; + + //////////////////////////////////////////////////////////////////////////////// + + template + class ntree_postfix_iterator + { + public: + typedef ntree_postfix_iterator iterator; + typedef ntree_postfix_iterator const_iterator; + typedef ntree_postfix_iterator this_iterator; + typedef ntree_iterator simple_iterator; + typedef TRef reference; + typedef TPtr pointer; + + // constructor to create a null iterator - you must assign a valid value to this iterator before using it + ntree_postfix_iterator(void); + ~ntree_postfix_iterator(void); + + // tests + // a null iterator is one that has not been initialised with a value yet + // i.e. you just declared it but didn't assign to it + bool null(void) const; + // an end iterator is one that points to the end element of the list of nodes + // in STL conventions this is one past the last valid element and must not be dereferenced + bool end(void) const; + // a valid iterator is one that can be dereferenced + // i.e. non-null and non-end + bool valid(void) const; + + // Type conversion methods allow const_iterator and iterator to be converted + // convert an iterator/const_iterator to a const_iterator + const_iterator constify(void) const; + iterator deconstify(void) const; + + // generate a simple iterator from a traversal iterator + ntree_iterator simplify(void) const; + + // tests useful for putting iterators into other STL structures and for testing whether iteration has completed + bool operator == (const this_iterator& r) const; + bool operator != (const this_iterator& r) const; + bool operator < (const this_iterator& r) const; + + // increment/decrement operators used to step through the set of all nodes in a graph + // it is only legal to increment a valid iterator + // pre-increment + this_iterator& operator ++ (void) + throw(null_dereference,end_dereference); + // post-increment + this_iterator operator ++ (int) + throw(null_dereference,end_dereference); + + // access the node data - a const_iterator gives you a const element, an iterator a non-const element + // it is illegal to dereference an invalid (i.e. null or end) iterator + reference operator*(void) const + throw(null_dereference,end_dereference); + pointer operator->(void) const + throw(null_dereference,end_dereference); + + friend class ntree; + friend class ntree_iterator; + + private: + ntree_iterator m_iterator; + + explicit ntree_postfix_iterator(const ntree_iterator& i); + const ntree_iterator& get_iterator(void) const; + ntree_iterator& get_iterator(void); + }; + + //////////////////////////////////////////////////////////////////////////////// + // The Ntree class + //////////////////////////////////////////////////////////////////////////////// + + template + class ntree + { + public: + // STL-like typedefs for the types and iterators + typedef T value_type; + + typedef ntree_iterator iterator; + typedef ntree_iterator const_iterator; + + typedef ntree_prefix_iterator prefix_iterator; + typedef ntree_prefix_iterator const_prefix_iterator; + + typedef ntree_postfix_iterator postfix_iterator; + typedef ntree_postfix_iterator const_postfix_iterator; + + ////////////////////////////////////////////////////////////////////////////// + // Constructors, destructors and copies + + ntree(void); + ~ntree(void); + + // copy constructor and assignment both copy the tree + ntree(const ntree&); + ntree& operator=(const ntree&); + + ////////////////////////////////////////////////////////////////////////////// + // size tests + + // tests on whole tree + bool empty(void) const; + unsigned size(void) const; + + // tests for number of nodes in subtree starting at node + unsigned size(const const_iterator& node) const + throw(wrong_object,null_dereference,end_dereference); + unsigned size(const iterator& node) + throw(wrong_object,null_dereference,end_dereference); + + // test for depth of tree from root to node + unsigned depth(const const_iterator& node) const + throw(wrong_object,null_dereference,end_dereference); + unsigned depth(const iterator& node) + throw(wrong_object,null_dereference,end_dereference); + + ////////////////////////////////////////////////////////////////////////////// + // direct traversal + + const_iterator root(void) const; + iterator root(void); + + unsigned children(const const_iterator& node) const + throw(wrong_object,null_dereference,end_dereference); + unsigned children(const iterator& node) + throw(wrong_object,null_dereference,end_dereference); + + const_iterator child(const const_iterator& node, unsigned child) const + throw(wrong_object,null_dereference,end_dereference,std::out_of_range); + iterator child(const iterator& node, unsigned child) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range); + + const_iterator parent(const const_iterator& node) const + throw(wrong_object,null_dereference,end_dereference); + iterator parent(const iterator& node) + throw(wrong_object,null_dereference,end_dereference); + + ////////////////////////////////////////////////////////////////////////////// + // iterator traversal + + const_prefix_iterator prefix_begin(void) const; + prefix_iterator prefix_begin(void); + const_prefix_iterator prefix_end(void) const; + prefix_iterator prefix_end(void); + + const_postfix_iterator postfix_begin(void) const; + postfix_iterator postfix_begin(void); + const_postfix_iterator postfix_end(void) const; + postfix_iterator postfix_end(void); + + ////////////////////////////////////////////////////////////////////////////// + // modification + + iterator insert(const T&); + + iterator insert(const iterator& node, unsigned child, const T&) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range); + iterator append(const iterator& node, const T&) + throw(wrong_object,null_dereference,end_dereference); + + iterator insert(const iterator& node, unsigned child, const ntree&) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range); + iterator append(const iterator& node, const ntree&) + throw(wrong_object,null_dereference,end_dereference); + + iterator push(const iterator& node, const T&) + throw(wrong_object,null_dereference,end_dereference); + void pop(const iterator& node, unsigned child) + throw(wrong_object,null_dereference,end_dereference); + + void erase(void); + void erase(const iterator& node) + throw(wrong_object,null_dereference,end_dereference); + void erase(const iterator& node, unsigned child) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range); + + ntree subtree(void); + ntree subtree(const iterator& node) + throw(wrong_object,null_dereference,end_dereference); + ntree subtree(const iterator& node, unsigned child) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range); + + ntree cut(void); + ntree cut(const iterator& node) + throw(wrong_object,null_dereference,end_dereference); + ntree cut(const iterator& node, unsigned child) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range); + + ////////////////////////////////////////////////////////////////////////////// + + private: + ntree_node* m_root; + }; + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + +#include "ntree.tpp" +#endif diff --git a/src/Moof/stlplus/ntree.tpp b/src/Moof/stlplus/ntree.tpp new file mode 100755 index 0000000..6fd019d --- /dev/null +++ b/src/Moof/stlplus/ntree.tpp @@ -0,0 +1,913 @@ +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +//////////////////////////////////////////////////////////////////////////////// +#include +#include + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // ntree_node + + template + class ntree_node + { + public: + master_iterator, ntree_node > m_master; + T m_data; + ntree_node* m_parent; + std::vector*> m_children; + + public: + ntree_node(const ntree* owner, const T& data = T()) : + m_master(owner,this), m_data(data), m_parent(0) + { + } + + void change_owner(const ntree* owner) + { + m_master.change_owner(owner); + for (TYPENAME std::vector*>::iterator i = m_children.begin(); i != m_children.end(); i++) + (*i)->change_owner(owner); + } + + ~ntree_node(void) + { + m_parent = 0; + for (TYPENAME std::vector*>::iterator i = m_children.begin(); i != m_children.end(); i++) + delete *i; + } + + }; + + template + static ntree_node* ntree_copy(const ntree* new_owner, ntree_node* root) + { + if (!root) return 0; + ntree_node* new_tree = new ntree_node(new_owner, root->m_data); + for (TYPENAME std::vector*>::iterator i = root->m_children.begin(); i != root->m_children.end(); i++) + { + ntree_node* new_child = ntree_copy(new_owner, *i); + new_tree->m_children.push_back(new_child); + new_child->m_parent = new_tree; + } + return new_tree; + } + + template + static unsigned ntree_size(ntree_node* root) + { + if (!root) return 0; + unsigned result = 1; + for (TYPENAME std::vector*>::iterator i = root->m_children.begin(); i != root->m_children.end(); i++) + result += ntree_size(*i); + return result; + } + + template + static unsigned ntree_depth(ntree_node* root) + { + unsigned depth = 0; + for (ntree_node* i = root; i; i = i->m_parent) + depth++; + return depth; + } + + //////////////////////////////////////////////////////////////////////////////// + // ntree_iterator + + // constructor to create a null iterator - you must assign a valid value to this iterator before using it + template + ntree_iterator::ntree_iterator(void) + { + } + + // used to create an alias of an iterator + template + ntree_iterator::ntree_iterator(const safe_iterator, ntree_node >& iterator) : + safe_iterator,ntree_node >(iterator) + { + } + + // constructor used by ntree to create a non-null iterator + template + ntree_iterator::ntree_iterator(ntree_node* node) : + safe_iterator,ntree_node >(node->m_master) + { + } + + // constructor used by ntree to create an end iterator + template + ntree_iterator::ntree_iterator(const ntree* owner) : + safe_iterator,ntree_node >(owner) + { + } + + // destructor + template + ntree_iterator::~ntree_iterator(void) + { + } + + template + TYPENAME ntree_iterator::const_iterator ntree_iterator::constify(void) const + { + return ntree_iterator(*this); + } + + template + TYPENAME ntree_iterator::iterator ntree_iterator::deconstify(void) const + { + return ntree_iterator(*this); + } + + template + bool ntree_iterator::operator == (const TYPENAME ntree_iterator::this_iterator& r) const + { + return equal(r); + } + + template + bool ntree_iterator::operator != (const TYPENAME ntree_iterator::this_iterator& r) const + { + return !operator==(r); + } + + template + bool ntree_iterator::operator < (const TYPENAME ntree_iterator::this_iterator& r) const + { + return compare(r) < 0; + } + + template + TYPENAME ntree_iterator::reference ntree_iterator::operator*(void) const + throw(null_dereference,end_dereference) + { + this->assert_valid(); + return this->node()->m_data; + } + + template + TYPENAME ntree_iterator::pointer ntree_iterator::operator->(void) const + throw(null_dereference,end_dereference) + { + return &(operator*()); + } + + //////////////////////////////////////////////////////////////////////////////// + // ntree_prefix_iterator + + template + ntree_prefix_iterator::ntree_prefix_iterator(void) + { + } + + template + ntree_prefix_iterator::~ntree_prefix_iterator(void) + { + } + + template + ntree_prefix_iterator::ntree_prefix_iterator(const ntree_iterator& i) : + m_iterator(i) + { + // this is initialised with the root node + // which is also the first node in prefix traversal order + } + + template + bool ntree_prefix_iterator::null(void) const + { + return m_iterator.null(); + } + + template + bool ntree_prefix_iterator::end(void) const + { + return m_iterator.end(); + } + + template + bool ntree_prefix_iterator::valid(void) const + { + return m_iterator.valid(); + } + + template + TYPENAME ntree_prefix_iterator::const_iterator ntree_prefix_iterator::constify(void) const + { + return ntree_prefix_iterator(m_iterator); + } + + template + TYPENAME ntree_prefix_iterator::iterator ntree_prefix_iterator::deconstify(void) const + { + return ntree_prefix_iterator(m_iterator); + } + + template + ntree_iterator ntree_prefix_iterator::simplify(void) const + { + return m_iterator; + } + + template + bool ntree_prefix_iterator::operator == (const TYPENAME ntree_prefix_iterator::this_iterator& r) const + { + return m_iterator == r.m_iterator; + } + + template + bool ntree_prefix_iterator::operator != (const TYPENAME ntree_prefix_iterator::this_iterator& r) const + { + return m_iterator != r.m_iterator; + } + + template + bool ntree_prefix_iterator::operator < (const TYPENAME ntree_prefix_iterator::this_iterator& r) const + { + return m_iterator < r.m_iterator; + } + + template + TYPENAME ntree_prefix_iterator::this_iterator& ntree_prefix_iterator::operator ++ (void) + throw(null_dereference,end_dereference) + { + // pre-increment operator + // algorithm: if there are any children, visit child 0, otherwise, go to + // parent and deduce which child the start node was of that parent - if + // there are further children, go into the next one. Otherwise, go up the + // tree and test again for further children. Return null if there are no + // further nodes + m_iterator.assert_valid(); + ntree_node* old_node = m_iterator.node(); + if (!old_node->m_children.empty()) + { + // simply take the first child of this node + m_iterator.set(old_node->m_children[0]->m_master); + } + else + { + // this loop walks up the parent pointers + // either it will walk off the top and exit or a new node will be found and the loop will exit + for (;;) + { + // go up a level + ntree_node* parent = old_node->m_parent; + if (!parent) + { + // we've walked off the top of the tree, so return end + m_iterator.set_end(); + break; + } + else + { + // otherwise walk down the next child - if there is one + // find which index the old node was relative to this node + TYPENAME std::vector*>::iterator found = + std::find(parent->m_children.begin(), parent->m_children.end(), old_node); + // if this was found, then see if there is another and if so return that + found++; + if (found != parent->m_children.end()) + { + // visit the next child + m_iterator.set((*found)->m_master); + break; + } + else + { + // keep going up + old_node = parent; + } + } + } + } + return *this; + } + + template + TYPENAME ntree_prefix_iterator::this_iterator ntree_prefix_iterator::operator ++ (int) + throw(null_dereference,end_dereference) + { + // post-increment is defined in terms of the pre-increment + ntree_prefix_iterator result(*this); + ++(*this); + return result; + } + + template + TYPENAME ntree_prefix_iterator::reference ntree_prefix_iterator::operator*(void) const + throw(null_dereference,end_dereference) + { + return m_iterator.operator*(); + } + + template + TYPENAME ntree_prefix_iterator::pointer ntree_prefix_iterator::operator->(void) const + throw(null_dereference,end_dereference) + { + return m_iterator.operator->(); + } + + template + const ntree_iterator& ntree_prefix_iterator::get_iterator(void) const + { + return m_iterator; + } + + template + ntree_iterator& ntree_prefix_iterator::get_iterator(void) + { + return m_iterator; + } + + //////////////////////////////////////////////////////////////////////////////// + // ntree_postfix_iterator + + template + ntree_postfix_iterator::ntree_postfix_iterator(void) + { + } + + template + ntree_postfix_iterator::~ntree_postfix_iterator(void) + { + } + + template + ntree_postfix_iterator::ntree_postfix_iterator(const ntree_iterator& i) : + m_iterator(i) + { + // this is initialised with the root node + // initially traverse to the first node to be visited + if (m_iterator.valid()) + { + ntree_node* node = m_iterator.node(); + while (!node->m_children.empty()) + node = node->m_children[0]; + m_iterator.set(node->m_master); + } + } + + template + bool ntree_postfix_iterator::null(void) const + { + return m_iterator.null(); + } + + template + bool ntree_postfix_iterator::end(void) const + { + return m_iterator.end(); + } + + template + bool ntree_postfix_iterator::valid(void) const + { + return m_iterator.valid(); + } + + template + TYPENAME ntree_postfix_iterator::const_iterator ntree_postfix_iterator::constify(void) const + { + return ntree_postfix_iterator(m_iterator); + } + + template + TYPENAME ntree_postfix_iterator::iterator ntree_postfix_iterator::deconstify(void) const + { + return ntree_postfix_iterator(m_iterator); + } + + template + ntree_iterator ntree_postfix_iterator::simplify(void) const + { + return m_iterator; + } + + template + bool ntree_postfix_iterator::operator == (const TYPENAME ntree_postfix_iterator::this_iterator& r) const + { + return m_iterator == r.m_iterator; + } + + template + bool ntree_postfix_iterator::operator != (const TYPENAME ntree_postfix_iterator::this_iterator& r) const + { + return m_iterator != r.m_iterator; + } + + template + bool ntree_postfix_iterator::operator < (const TYPENAME ntree_postfix_iterator::this_iterator& r) const + { + return m_iterator < r.m_iterator; + } + + template + TYPENAME ntree_postfix_iterator::this_iterator& ntree_postfix_iterator::operator ++ (void) + throw(null_dereference,end_dereference) + { + // pre-increment operator + // algorithm: this node has been visited, therefore all children must have + // already been visited. So go to parent. Return null if the parent is null. + // Otherwise deduce which child the start node was of that parent - if there + // are further children, go into the next one and then walk down any + // subsequent first-child pointers to the bottom. Otherwise, if there are no + // children then the parent node is the next in the traversal. + m_iterator.assert_valid(); + // go up a level + ntree_node* old_node = m_iterator.node(); + ntree_node* parent = old_node->m_parent; + if (!parent) + { + // we've walked off the top of the tree, so return end + m_iterator.set_end(); + } + else + { + // otherwise find which index the old node was relative to this node + TYPENAME std::vector*>::iterator found = + std::find(parent->m_children.begin(), parent->m_children.end(), old_node); + // if this was found, then see if there is another + found++; + if (found != parent->m_children.end()) + { + // if so traverse to it and walk down the leftmost child pointers to the bottom of the new sub-tree + ntree_node* new_node = *found; + while (!new_node->m_children.empty()) + new_node = new_node->m_children[0]; + m_iterator.set(new_node->m_master); + } + else + { + // the parent's children have all been visited - so the parent is visited + m_iterator.set(parent->m_master); + } + } + return *this; + } + + template + TYPENAME ntree_postfix_iterator::this_iterator ntree_postfix_iterator::operator ++ (int) + throw(null_dereference,end_dereference) + { + // post-increment is defined in terms of the pre-increment + ntree_postfix_iterator result(*this); + ++(*this); + return result; + } + + template + TYPENAME ntree_postfix_iterator::reference ntree_postfix_iterator::operator*(void) const + throw(null_dereference,end_dereference) + { + return m_iterator.operator*(); + } + + template + TYPENAME ntree_postfix_iterator::pointer ntree_postfix_iterator::operator->(void) const + throw(null_dereference,end_dereference) + { + return m_iterator.operator->(); + } + + template + const ntree_iterator& ntree_postfix_iterator::get_iterator(void) const + { + return m_iterator; + } + + template + ntree_iterator& ntree_postfix_iterator::get_iterator(void) + { + return m_iterator; + } + + //////////////////////////////////////////////////////////////////////////////// + //////////////////////////////////////////////////////////////////////////////// + // ntree + //////////////////////////////////////////////////////////////////////////////// + //////////////////////////////////////////////////////////////////////////////// + + template + ntree::ntree(void) : m_root(0) + { + } + + template + ntree::~ntree(void) + { + if (m_root) delete m_root; + } + + template + ntree::ntree(const ntree& r) : m_root(0) + { + *this = r; + } + + template + ntree& ntree::operator=(const ntree& r) + { + if (m_root) delete m_root; + m_root = ntree_copy(this, r.m_root); + return *this; + } + + template + bool ntree::empty(void) const + { + return m_root == 0; + } + + template + unsigned ntree::size(void) const + { + return ntree_size(m_root); + } + + template + unsigned ntree::size(const TYPENAME ntree::const_iterator& i) const + throw(wrong_object,null_dereference,end_dereference) + { + i.assert_valid(this); + return ntree_size(i.node()); + } + + template + unsigned ntree::size(const TYPENAME ntree::iterator& i) + throw(wrong_object,null_dereference,end_dereference) + { + i.assert_valid(this); + return ntree_size(i.node()); + } + + template + unsigned ntree::depth(const TYPENAME ntree::const_iterator& i) const + throw(wrong_object,null_dereference,end_dereference) + { + i.assert_valid(this); + return ntree_depth(i.node()); + } + + template + unsigned ntree::depth(const TYPENAME ntree::iterator& i) + throw(wrong_object,null_dereference,end_dereference) + { + i.assert_valid(this); + return ntree_depth(i.node()); + } + + template + TYPENAME ntree::const_iterator ntree::root(void) const + { + if (!m_root) return ntree_iterator(this); + return ntree_iterator(m_root); + } + + template + TYPENAME ntree::iterator ntree::root(void) + { + if (!m_root) return ntree_iterator(this); + return ntree_iterator(m_root); + } + + template + unsigned ntree::children(const TYPENAME ntree::const_iterator& i) const + throw(wrong_object,null_dereference,end_dereference) + { + i.assert_valid(this); + return i.node()->m_children.size(); + } + + template + unsigned ntree::children(const ntree_iterator& i) + throw(wrong_object,null_dereference,end_dereference) + { + i.assert_valid(this); + return i.node()->m_children.size(); + } + + template + TYPENAME ntree::const_iterator ntree::child(const TYPENAME ntree::const_iterator& i, unsigned child) const + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + i.assert_valid(this); + if (child >= children(i)) throw std::out_of_range("stlplus::ntree"); + return ntree_iterator(i.node()->m_children[child]); + } + + template + TYPENAME ntree::iterator ntree::child(const TYPENAME ntree::iterator& i, unsigned child) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + i.assert_valid(this); + if (child >= children(i)) throw std::out_of_range("stlplus::ntree"); + return ntree_iterator(i.node()->m_children[child]); + } + + template + TYPENAME ntree::const_iterator ntree::parent(const TYPENAME ntree::const_iterator& i) const + throw(wrong_object,null_dereference,end_dereference) + { + i.assert_valid(this); + ntree_node* parent = i.node()->m_parent; + if (!parent) return ntree_iterator(this); + return ntree_iterator(parent); + } + + template + TYPENAME ntree::iterator ntree::parent(const TYPENAME ntree::iterator& i) + throw(wrong_object,null_dereference,end_dereference) + { + i.assert_valid(this); + ntree_node* parent = i.node()->m_parent; + if (!parent) return ntree_iterator(this); + return ntree_iterator(parent); + } + + template + TYPENAME ntree::const_prefix_iterator ntree::prefix_begin(void) const + { + return ntree_prefix_iterator(root()); + } + + template + TYPENAME ntree::prefix_iterator ntree::prefix_begin(void) + { + return ntree_prefix_iterator(root()); + } + + template + TYPENAME ntree::const_prefix_iterator ntree::prefix_end(void) const + { + return ntree_prefix_iterator(ntree_iterator(this)); + } + + template + TYPENAME ntree::prefix_iterator ntree::prefix_end(void) + { + return ntree_prefix_iterator(ntree_iterator(this)); + } + + template + TYPENAME ntree::const_postfix_iterator ntree::postfix_begin(void) const + { + return ntree_postfix_iterator(root()); + } + + template + TYPENAME ntree::postfix_iterator ntree::postfix_begin(void) + { + return ntree_postfix_iterator(root()); + } + + template + TYPENAME ntree::const_postfix_iterator ntree::postfix_end(void) const + { + return ntree_postfix_iterator(ntree_iterator(this)); + } + + template + TYPENAME ntree::postfix_iterator ntree::postfix_end(void) + { + return ntree_postfix_iterator(ntree_iterator(this)); + } + + template + TYPENAME ntree::iterator ntree::insert(const T& data) + { + // insert a new node as the root + return insert(ntree_iterator(this), 0, data); + } + + template + TYPENAME ntree::iterator ntree::insert(const TYPENAME ntree::iterator& i, unsigned offset, const T& data) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + // if i is the end iterator, this means insert a new root + if (i.end()) + erase(); + else + { + i.assert_valid(this); + if (offset > children(i)) throw std::out_of_range("stlplus::ntree"); + } + ntree_node* new_node = new ntree_node(this,data); + if (i.end()) + { + m_root = new_node; + } + else + { + i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node); + new_node->m_parent = i.node(); + } + return ntree_iterator(new_node); + } + + template + TYPENAME ntree::iterator ntree::append(const TYPENAME ntree::iterator& i, const T& data) + throw(wrong_object,null_dereference,end_dereference) + { + return insert(i, i.node()->m_children.size(), data); + } + + template + TYPENAME ntree::iterator ntree::insert(const TYPENAME ntree::iterator& i, unsigned offset, const ntree& tree) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + // insert a whole tree as a child of i + i.assert_valid(this); + if (offset > children(i)) throw std::out_of_range("stlplus::ntree"); + ntree_node* new_node = ntree_copy(this, tree.m_root); + i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node); + new_node->m_parent = i.node(); + return ntree_iterator(new_node); + } + + template + TYPENAME ntree::iterator ntree::append(const TYPENAME ntree::iterator& i, const ntree& tree) + throw(wrong_object,null_dereference,end_dereference) + { + return insert(i, children(i), tree); + } + + template + TYPENAME ntree::iterator ntree::push(const TYPENAME ntree::iterator& node, const T& data) + throw(wrong_object,null_dereference,end_dereference) + { + // insert a new node to replace the existing node in the tree + // making the original node the child of the new node + // i.e. (node) becomes (new)->(node) + // afterwards, the iterator still points to the old node, now the child + // returns the iterator to the new node + node.assert_valid(this); + ntree_node* new_node = new ntree_node(this,data); + if (node.node() == m_root) + { + // pushing the root node + m_root = new_node; + new_node->m_parent = 0; + } + else + { + // pushing a sub-node + *(std::find(node.node()->m_parent->m_children.begin(), node.node()->m_parent->m_children.end(), node.node())) = new_node; + new_node->m_parent = node.node()->m_parent; + } + // link up the old node as the child of the new node + new_node->m_children.insert(new_node->m_children.begin(),node.node()); + node.node()->m_parent = new_node; + return ntree_iterator(new_node); + } + + template + void ntree::pop(const TYPENAME ntree::iterator& parent, unsigned offset) + throw(wrong_object,null_dereference,end_dereference) + { + // inverse of push + // removes the specified child of the parent node, adding its children to the parent node at the same offset + parent.assert_valid(this); + ntree_node* node = parent.node(); + if (offset >= node->m_children.size()) throw std::out_of_range("stlplus::ntree"); + // move the grandchildren first + ntree_node* child = parent.node()->m_children[offset]; + while (!child->m_children.empty()) + { + // remove the last grandchild and insert into node just after the child to be removed + ntree_node* grandchild = child->m_children[child->m_children.size()-1]; + child->m_children.pop_back(); + node->m_children.insert(node->m_children.begin()+offset+1, grandchild); + grandchild->m_parent = node; + } + // now remove the child + node->m_children.erase(node->m_children.begin()+offset); + delete child; + } + + template + void ntree::erase(void) + { + // erase the whole tree + erase(root()); + } + + template + void ntree::erase(const TYPENAME ntree::iterator& i) + throw(wrong_object,null_dereference,end_dereference) + { + if (!i.end()) + { + // erase this node and its subtree + // do this by erasing this child of its parent + // handle the case of erasing the root + i.assert_valid(this); + ntree_node* node = i.node(); + if (node == m_root) + { + delete m_root; + m_root = 0; + } + else + { + ntree_node* parent = node->m_parent; + // impossible for parent to be null - should assert this + TYPENAME std::vector*>::iterator found = + std::find(parent->m_children.begin(), parent->m_children.end(), node); + // impossible for find to fail - should assert this + parent->m_children.erase(found); + delete node; + } + } + } + + template + void ntree::erase(const TYPENAME ntree::iterator& i, unsigned offset) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + erase(child(i, offset)); + } + + template + ntree ntree::subtree(void) + { + return subtree(root()); + } + + template + ntree ntree::subtree(const TYPENAME ntree::iterator& i) + throw(wrong_object,null_dereference,end_dereference) + { + ntree result; + if (!i.end()) + { + i.assert_valid(this); + result.m_root = ntree_copy(&result, i.node()); + } + return result; + } + + template + ntree ntree::subtree(const TYPENAME ntree::iterator& i, unsigned offset) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + return subtree(child(i, offset)); + } + + template + ntree ntree::cut(void) + { + return cut(root()); + } + + template + ntree ntree::cut(const TYPENAME ntree::iterator& i) + throw(wrong_object,null_dereference,end_dereference) + { + ntree result; + if (!i.end()) + { + i.assert_valid(this); + ntree_node* node = i.node(); + if (node == m_root) + { + result.m_root = m_root; + m_root = 0; + } + else + { + ntree_node* parent = node->m_parent; + // impossible for parent to be null - should assert this + TYPENAME std::vector*>::iterator found = + std::find(parent->m_children.begin(), parent->m_children.end(), node); + // impossible for find to fail - should assert this + result.m_root = *found; + parent->m_children.erase(found); + } + if (result.m_root) + { + result.m_root->m_parent = 0; + result.m_root->set_new_owner(&result); + } + } + return result; + } + + template + ntree ntree::cut(const TYPENAME ntree::iterator& i, unsigned offset) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + return cut(child(i, offset)); + } + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + diff --git a/src/Moof/stlplus/safe_iterator.hpp b/src/Moof/stlplus/safe_iterator.hpp new file mode 100755 index 0000000..5bf80fb --- /dev/null +++ b/src/Moof/stlplus/safe_iterator.hpp @@ -0,0 +1,155 @@ +#ifndef STLPLUS_SAFE_ITERATOR +#define STLPLUS_SAFE_ITERATOR +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +// The STLplus safe_iterator superclasses. This implements the STLplus safe +// iterator principles. Data structures can then be built using subclasses +// of safe_iterator for their iterator objects and they will inherit the +// safe iterator behaviour. + +// The data structure must contain a master iterator for each node in the +// structure. When an iterator is returned to the user, it must be created +// by the master iterator. When a node is removed from the data structure, +// its master iterator is destroyed. This sets all iterators pointing to the +// master iterator to end iterators. + +//////////////////////////////////////////////////////////////////////////////// +#include "containers_fixes.hpp" +#include "exceptions.hpp" + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // internals + + template + class safe_iterator_body; + + template + class safe_iterator; + + //////////////////////////////////////////////////////////////////////////////// + // Master Iterator + // Create one of these in each node in the data structure + // Generate iterators by obtaining a safe-iterator object from the master iterator + //////////////////////////////////////////////////////////////////////////////// + + template + class master_iterator + { + public: + + // construct a valid master iterator connected to the node + master_iterator(const O* owner, N* node) throw(); + + // destructor - disconnects all iterators from the node + ~master_iterator(void) throw(); + + // dereference + N* node(void) const throw(); + const O* owner(void) const throw(); + + // when you move a node from one owner to another, call this on the node's master iterator + // this effectively moves all other iterators to the node so that they are owned by the new owner too + void change_owner(const O* owner) throw(); + + friend class safe_iterator; + private: + master_iterator(const master_iterator&) throw(); + master_iterator& operator=(const master_iterator&) throw(); + safe_iterator_body* m_body; + }; + + //////////////////////////////////////////////////////////////////////////////// + // Safe Iterator + //////////////////////////////////////////////////////////////////////////////// + + template + class safe_iterator + { + public: + + // construct a null iterator + safe_iterator(void) throw(); + + // construct a valid iterator by aliasing from the owner node's master iterator + safe_iterator(const master_iterator&) throw(); + + // copy constructor does aliasing + safe_iterator(const safe_iterator&) throw(); + + // alias an iterator by assignment + safe_iterator& operator=(const safe_iterator&) throw(); + + // destructor + ~safe_iterator(void) throw(); + + // reassignment to another node used in increment/decrement operation + void set(const master_iterator&) throw(); + + // dereference + N* node(void) const throw(); + const O* owner(void) const throw(); + + // change to a null iterator - i.e. one that does not belong to any object + // this does not affect any other iterators pointing to the same node + void set_null(void) throw(); + + //////////////////////////////////////////////////////////////////////////////// + // operations for clients that do not have a master end iterator + // alternatively, have a master end iterator as part of the container + // and call constructor(master_end) or set(master_end) + + // construct an end iterator + safe_iterator(const O* owner) throw(); + + // change to an end iterator - e.g. as a result of incrementing off the end + void set_end(void) throw(); + + //////////////////////////////////////////////////////////////////////////////// + // tests + + // comparison + bool equal(const safe_iterator& right) const throw(); + int compare(const safe_iterator& right) const throw(); + + // a null iterator is one that has not been initialised with a value yet + // i.e. you just declared it but didn't assign to it + bool null(void) const throw(); + + // an end iterator is one that points to the end element of the list of nodes + // in STL conventions this is one past the last valid element and must not be dereferenced + bool end(void) const throw(); + + // a valid iterator is one that can be dereferenced + // i.e. non-null and non-end + bool valid(void) const throw(); + + // check the rules for a valid iterator that can be dereferenced + // optionally also check that the iterator is owned by the owner + void assert_valid(void) const throw(null_dereference,end_dereference); + void assert_valid(const O* owner) const throw(wrong_object,null_dereference,end_dereference); + // assert the rules for a non-null iterator - i.e. valid or end, values that occur in increment operations + void assert_non_null(void) const throw(null_dereference); + // assert that this iterator is owned by this container + void assert_owner(const O* owner) const throw(wrong_object); + + //////////////////////////////////////////////////////////////////////////////// + + friend class master_iterator; + private: + safe_iterator_body* m_body; + }; + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + +#include "safe_iterator.tpp" +#endif diff --git a/src/Moof/stlplus/safe_iterator.tpp b/src/Moof/stlplus/safe_iterator.tpp new file mode 100755 index 0000000..14d89b9 --- /dev/null +++ b/src/Moof/stlplus/safe_iterator.tpp @@ -0,0 +1,373 @@ +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // body class implements the aliasing behaviour + + template + class safe_iterator_body + { + private: + const O* m_owner; + N* m_node; + unsigned m_count; + + public: + + safe_iterator_body(const O* owner, N* node) throw() : + m_owner(owner), m_node(node), m_count(1) + { +// std::cerr << "constructing " +// << std::hex << ((unsigned long)this) +// << " => " << ((unsigned long)m_owner) << ":" << ((unsigned long)m_node) +// << ":" << std::dec << m_count << std::endl; + } + + ~safe_iterator_body(void) throw() + { +// std::cerr << "destroying " +// << std::hex << ((unsigned long)this) +// << " => " << ((unsigned long)m_owner) << ":" << ((unsigned long)m_node) +// << ":" << std::dec << m_count << std::endl; + m_owner = 0; + m_node = 0; + } + + unsigned count(void) const + { + return m_count; + } + + void increment(void) + { + ++m_count; +// std::cerr << "incremented " +// << std::hex << ((unsigned long)this) +// << " => " << ((unsigned long)m_owner) << ":" << ((unsigned long)m_node) +// << ":" << std::dec << m_count << std::endl; + } + + bool decrement(void) + { + --m_count; +// std::cerr << "decremented " +// << std::hex << ((unsigned long)this) +// << " => " << ((unsigned long)m_owner) << ":" << ((unsigned long)m_node) +// << ":" << std::dec << m_count << std::endl; + return m_count == 0; + } + + N* node(void) const throw() + { + return m_node; + } + + const O* owner(void) const throw() + { + return m_owner; + } + + void change_owner(const O* owner) + { + m_owner = owner; + } + + bool equal(const safe_iterator_body* right) const throw() + { +// return m_node == right->m_node; + return compare(right) == 0; + } + + int compare(const safe_iterator_body* right) const throw() + { + return ((long)m_node) - ((long)right->m_node); + } + + bool null(void) const throw() + { + return m_owner == 0; + } + + bool end(void) const throw() + { + return m_owner != 0 && m_node == 0; + } + + bool valid(void) const throw() + { + return m_owner != 0 && m_node != 0; + } + + void set_end(void) throw() + { + m_node = 0; + } + + void set_null(void) throw() + { + m_owner = 0; + m_node = 0; + } + + void assert_valid(void) const throw(null_dereference,end_dereference) + { + if (null()) + throw null_dereference("stlplus::safe_iterator"); + if (end()) + throw end_dereference("stlplus::safe_iterator"); + } + + void assert_non_null(void) const throw(null_dereference) + { + if (null()) + throw null_dereference("stlplus::safe_iterator"); + } + + void assert_owner(const O* owner) const throw(wrong_object) + { + if (owner != m_owner) + throw wrong_object("stlplus::safe_iterator"); + } + }; + + + //////////////////////////////////////////////////////////////////////////////// + // Master Iterator + //////////////////////////////////////////////////////////////////////////////// + + // construct a valid iterator + template + master_iterator::master_iterator(const O* owner, N* node) throw() : + m_body(new safe_iterator_body(owner,node)) + { + } + + // destructor - disconnect all iterators from the node + // this usually happens when the node is deleted and must invalidate all aliases + template + master_iterator::~master_iterator(void) throw() + { + m_body->set_end(); + if(m_body->decrement()) + { + delete m_body; + m_body = 0; + } + } + + // dereference + template + N* master_iterator::node(void) const throw() + { + return m_body->node(); + } + + template + const O* master_iterator::owner(void) const throw() + { + return m_body->owner(); + } + + // when you move a node from one owner to another, call this on the node's iterator + // this effectively moves all iterators to the node so that they are owned by the new owner too + template + void master_iterator::change_owner(const O* owner) throw() + { + m_body->change_owner(owner); + } + + //////////////////////////////////////////////////////////////////////////////// + // Safe Iterator + //////////////////////////////////////////////////////////////////////////////// + + // construct a null iterator + // later assignment of a valid iterator to this is done by using step + template + safe_iterator::safe_iterator(void) throw() : + m_body(new safe_iterator_body(0,0)) + { + } + + // construct a valid iterator by aliasing from the owner node's master iterator + template + safe_iterator::safe_iterator(const master_iterator& r) throw() : + m_body(0) + { + m_body = r.m_body; + m_body->increment(); + } + + // construct a valid iterator by aliasing from the owner node's master iterator + template + safe_iterator::safe_iterator(const safe_iterator& r) throw() : + m_body(0) + { + m_body = r.m_body; + m_body->increment(); + } + + // assignment implements dealiasing followed by aliasing + template + safe_iterator& safe_iterator::operator=(const safe_iterator& r) throw() + { + if (m_body != r.m_body) + { + if (m_body->decrement()) + delete m_body; + m_body = r.m_body; + m_body->increment(); + } + return *this; + } + + // destructor - implements dealiasing + template + safe_iterator::~safe_iterator(void) throw() + { + if(m_body->decrement()) + { + delete m_body; + m_body = 0; + } + } + + + // increment/decrement operation + // implements dealiasing followed by aliasing + template + void safe_iterator::set(const master_iterator& r) throw() + { + if (m_body != r.m_body) + { + if (m_body->decrement()) + delete m_body; + m_body = r.m_body; + m_body->increment(); + } + } + + // dereference + template + N* safe_iterator::node(void) const throw() + { + return m_body->node(); + } + + template + const O* safe_iterator::owner(void) const throw() + { + return m_body->owner(); + } + + // change to a null iterator - i.e. one that doees not belong to any object + // this does not affect any other iterators pointing to the same node + template + void safe_iterator::set_null(void) throw() + { + if (m_body->count() == 1) + { + // no aliases, so just make this null + m_body->set_null(); + } + else + { + // create a new body which is null so as not to affect any other aliases + m_body->decrement(); + m_body = new safe_iterator_body(0,0); + } + } + + //////////////////////////////////////////////////////////////////////////////// + // operations for clients that do not have a master end iterator + // alternatively, have a master end iterator as part of the container + // and call constructor(master_end) or step(master_end) + + // construct an end iterator + template + safe_iterator::safe_iterator(const O* owner) throw() : + m_body(new safe_iterator_body(owner,0)) + { + } + + // change to an end iterator - e.g. as a result of incrementing off the end + template + void safe_iterator::set_end(void) throw() + { + if (m_body->count() == 1) + { + // no aliases, so just make this an end iterator + m_body->set_end(); + } + else + { + // create a new body which is null so as not to affect any other aliases + m_body->decrement(); + m_body = new safe_iterator_body(owner(),0); + } + } + + //////////////////////////////////////////////////////////////////////////////// + // tests + + // comparison + template + bool safe_iterator::equal(const safe_iterator& right) const throw() + { + return compare(right) == 0; + } + + template + int safe_iterator::compare(const safe_iterator& right) const throw() + { + if (m_body == right.m_body) return 0; + return m_body->compare(right.m_body); + } + + // a null iterator is one that has not been initialised with a value yet + template + bool safe_iterator::null(void) const throw() + { + return m_body->null(); + } + + // an end iterator is one that points to the end element of the list of nodes + template + bool safe_iterator::end(void) const throw() + { + return m_body->end(); + } + + // a valid iterator is one that can be dereferenced + template + bool safe_iterator::valid(void) const throw() + { + return m_body->valid(); + } + + // check the rules for a valid iterator that can be dereferenced + template + void safe_iterator::assert_valid(void) const throw(null_dereference,end_dereference) + { + m_body->assert_valid(); + } + + template + void safe_iterator::assert_valid(const O* owner) const throw(wrong_object,null_dereference,end_dereference) + { + m_body->assert_valid(); + m_body->assert_owner(owner); + } + + template + void safe_iterator::assert_non_null(void) const throw(null_dereference) + { + m_body->assert_non_null(); + } + + template + void safe_iterator::assert_owner(const O* owner) const throw(wrong_object) + { + m_body->assert_owner(owner); + } + +} // end namespace stlplus diff --git a/src/Moof/stlplus/smart_ptr.hpp b/src/Moof/stlplus/smart_ptr.hpp new file mode 100755 index 0000000..d1395f5 --- /dev/null +++ b/src/Moof/stlplus/smart_ptr.hpp @@ -0,0 +1,256 @@ +#ifndef STLPLUS_SMART_PTR +#define STLPLUS_SMART_PTR +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +// A smart pointer is a memory-managing pointer to an object. If you like, it +// is a zero-dimensional container. + +// Assignment of smart pointers result in multiple aliases of the same object. +// The term alias is used to differentiate from conventional pointers because +// the semantics are different. + +// Aliases can be turned into copies if the pointed-to class supports copying. + +// The base class is smart_ptr_base which defines the common interface. Then +// there are three subclasses which have the same interface but different copy +// semantics: + +// - smart_ptr for simple types and classes which have copy constructors +// - smart_ptr_clone for polymorphic class hierarchies which are copied using a clone method +// - smart_ptr_nocopy for any class that cannot or should not be copied + +//////////////////////////////////////////////////////////////////////////////// +#include "containers_fixes.hpp" +#include "exceptions.hpp" +#include +#include + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // internals + + template class smart_ptr_holder; + + //////////////////////////////////////////////////////////////////////////////// + // Base class + //////////////////////////////////////////////////////////////////////////////// + + template + class smart_ptr_base + { + public: + ////////////////////////////////////////////////////////////////////////////// + // member type definitions + + typedef T value_type; + typedef T& reference; + typedef const T& const_reference; + typedef C value_copy; + + ////////////////////////////////////////////////////////////////////////////// + // constructors and destructors + + // create a null pointer + smart_ptr_base(void); + + // create a pointer containing a *copy* of the object using the template parameter C + // this copy is taken because the pointer class maintains a dynamically allocated object + // and the T& may not be (usually is not) dynamically allocated + explicit smart_ptr_base(const T& data) throw(illegal_copy); + + // create a pointer containing a dynamically created object + // Note: the object must be allocated *by the user* with new + // constructor form - must be called in the form smart_ptr_base x(new type(args)) + explicit smart_ptr_base(T* data); + + // copy constructor implements aliasing so no copy is made + explicit smart_ptr_base(const smart_ptr_base& r); + + // destructor decrements the reference count and delete only when the last reference is destroyed + ~smart_ptr_base(void); + + ////////////////////////////////////////////////////////////////////////////// + // logical tests to see if there is anything contained in the pointer since it can be null + + // there are two forms:explicit and implicit + // implicit: if(!r) or if(r) + // explicit: if(r.null()) or if(r.present()) + operator bool(void) const; + bool operator!(void) const; + bool present(void) const; + bool null(void) const; + + ////////////////////////////////////////////////////////////////////////////// + // dereference operators and functions + + // dereference the smart pointer to get the object - use in the form *p1 + T& operator*(void) throw(null_dereference); + const T& operator*(void) const throw(null_dereference); + + // used as a prefix to a member access to the contained object e.g. p1->print() calls T::print() + T* operator->(void) throw(null_dereference); + const T* operator->(void) const throw(null_dereference); + + ////////////////////////////////////////////////////////////////////////////// + // explicit function forms of the above assignment and dereference operators + + // set the value - note that this does a copy using the C template parameter + void set_value(const T& data) throw(illegal_copy); + // get the value + T& value(void) throw(null_dereference); + const T& value(void) const throw(null_dereference); + + // set the pointer + // deletes the previous pointer and adopts the passed pointer instead + // Note: the object must be allocated *by the user* with new + // Warning: it is very easy to break the memory management with this operation + void set(T* data = 0); + // get the pointer + T* pointer(void); + const T* pointer(void) const; + + ////////////////////////////////////////////////////////////////////////////// + // functions to manage aliases + + // make this an alias of the passed object + void alias(const smart_ptr_base&); + + // test whether two pointers point to the same object(known as aliasing the object) + // used in the form if(a.aliases(b)) + bool aliases(const smart_ptr_base&) const; + + // find the number of aliases - used when you need to know whether an + // object is still referred to from elsewhere (rare!) + unsigned alias_count(void) const; + + // delete the object and make the pointer null - does not make it unique + // first, so all other pointers to this will be null too + void clear(void); + + // make the pointer unique and null in one step - does not affect other + // pointers that were pointing to the same object + void clear_unique(void); + + ////////////////////////////////////////////////////////////////////////////// + // functions that involve copying + + // these functions use the copy functor passed as the template parameter C + // to copy the object with the right copy semantics. If the copy functor + // is no_copy, an exception will be thrown. + + // make this pointer unique with respect to any other references to the same object + // if this pointer is already unique, it does nothing - otherwise it copies the object + void make_unique(void) throw(illegal_copy); + + // make this pointer a unique copy of the parameter + // useful for expressions like p1.copy(p2) which makes p1 a pointer to a unique copy of the contents of p2 + void copy(const smart_ptr_base&) throw(illegal_copy); + + protected: + smart_ptr_holder* m_holder; + + public: + // internal use only - had to make them public because they need to be + // accessed by routines that could not be made friends + void* handle(void) const; + void make_alias(void* handle); + }; + + //////////////////////////////////////////////////////////////////////////////// + // copy functors implementing the three possible copy semantics + + // constructor_copy uses the copy constructor of the object - used for simple types + + template + class constructor_copy + { + public: + T* operator() (const T& from) throw() + { + return new T(from); + } + }; + + // clone_copy uses the clone method of the object - used for polymorphic types + + template + class clone_copy + { + public: + T* operator() (const T& from) throw() + { + return from.clone(); + } + }; + + // no_copy throws an exception - used for types that cannot be copied + + template + class no_copy + { + public: + T* operator() (const T& from) throw(illegal_copy) + { + throw illegal_copy("no_copy functor called"); + return 0; + } + }; + + //////////////////////////////////////////////////////////////////////////////// + // smart_ptr for simple types and classes which have copy constructors + + template + class smart_ptr : public smart_ptr_base > + { + public: + smart_ptr(void) {} + explicit smart_ptr(const T& data) : smart_ptr_base >(data) {} + explicit smart_ptr(T* data) : smart_ptr_base >(data) {} + smart_ptr& operator=(const T& data) {set_value(data); return *this;} + smart_ptr& operator=(const smart_ptr& r) {alias(r); return *this;} + ~smart_ptr(void) {} + }; + + //////////////////////////////////////////////////////////////////////////////// + // smart_ptr_clone for polymorphic class hierarchies which have a clone method + + template + class smart_ptr_clone : public smart_ptr_base > + { + public: + smart_ptr_clone(void) {} + explicit smart_ptr_clone(const T& data) : smart_ptr_base >(data) {} + explicit smart_ptr_clone(T* data) : smart_ptr_base >(data) {} + smart_ptr_clone& operator=(const T& data) {set_value(data); return *this;} + smart_ptr_clone& operator=(const smart_ptr_clone& r) {alias(r); return *this;} + ~smart_ptr_clone(void) {} + }; + + //////////////////////////////////////////////////////////////////////////////// + // smart_ptr_nocopy for any class that cannot or should not be copied + + template + class smart_ptr_nocopy : public smart_ptr_base > + { + public: + smart_ptr_nocopy(void) {} + explicit smart_ptr_nocopy(const T& data) : smart_ptr_base >(data) {} + explicit smart_ptr_nocopy(T* data) : smart_ptr_base >(data) {} + smart_ptr_nocopy& operator=(const T& data) {set_value(data); return *this;} + smart_ptr_nocopy& operator=(const smart_ptr_nocopy& r) {alias(r); return *this;} + ~smart_ptr_nocopy(void) {} + }; + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + +#include "smart_ptr.tpp" +#endif diff --git a/src/Moof/stlplus/smart_ptr.tpp b/src/Moof/stlplus/smart_ptr.tpp new file mode 100755 index 0000000..cb1b8bb --- /dev/null +++ b/src/Moof/stlplus/smart_ptr.tpp @@ -0,0 +1,343 @@ +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +//////////////////////////////////////////////////////////////////////////////// + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // internal holder data structure + //////////////////////////////////////////////////////////////////////////////// + + template + class smart_ptr_holder + { + private: + unsigned m_count; + T* m_data; + + // make these private to disallow copying because the holder doesn't know how to copy + smart_ptr_holder(const smart_ptr_holder& s) : + m_count(0), m_data(0) + { + } + + smart_ptr_holder& operator=(const smart_ptr_holder& s) + { + return *this; + } + + public: + smart_ptr_holder(T* p = 0) : + m_count(1), m_data(p) + { + } + + ~smart_ptr_holder(void) + { + clear(); + } + + unsigned count(void) const + { + return m_count; + } + + void increment(void) + { + ++m_count; + } + + bool decrement(void) + { + --m_count; + return m_count == 0; + } + + bool null(void) + { + return m_data == 0; + } + + void clear(void) + { + if(m_data) + delete m_data; + m_data = 0; + } + + void set(T* p = 0) + { + clear(); + m_data = p; + } + + T*& pointer(void) + { + return m_data; + } + + const T* pointer(void) const + { + return m_data; + } + + T& value(void) + { + return *m_data; + } + + const T& value(void) const + { + return *m_data; + } + }; + + //////////////////////////////////////////////////////////////////////////////// + // smart_ptr_base class + //////////////////////////////////////////////////////////////////////////////// + + //////////////////////////////////////////////////////////////////////////////// + // constructors, assignments and destructors + + // create a null pointer + template + smart_ptr_base::smart_ptr_base(void) : + m_holder(new smart_ptr_holder) + { + } + + // create a pointer containing a *copy* of the object pointer + template + smart_ptr_base::smart_ptr_base(const T& data) throw(illegal_copy) : + m_holder(new smart_ptr_holder) + { + m_holder->set(C()(data)); + } + + // create a pointer containing a dynamically created object + // Note: the object must be allocated *by the user* with new + // constructor form - must be called in the form smart_ptr x(new type(args)) + template + smart_ptr_base::smart_ptr_base(T* data) : + m_holder(new smart_ptr_holder) + { + m_holder->set(data); + } + + // copy constructor implements counted referencing - no copy is made + template + smart_ptr_base::smart_ptr_base(const smart_ptr_base& r) : + m_holder(0) + { + m_holder = r.m_holder; + m_holder->increment(); + } + + // destructor decrements the reference count and delete only when the last reference is destroyed + template + smart_ptr_base::~smart_ptr_base(void) + { + if(m_holder->decrement()) + delete m_holder; + } + + ////////////////////////////////////////////////////////////////////////////// + // logical tests to see if there is anything contained in the pointer since it can be null + + template + bool smart_ptr_base::null(void) const + { + return m_holder->null(); + } + + template + bool smart_ptr_base::present(void) const + { + return !m_holder->null(); + } + + template + bool smart_ptr_base::operator!(void) const + { + return m_holder->null(); + } + + template + smart_ptr_base::operator bool(void) const + { + return !m_holder->null(); + } + + ////////////////////////////////////////////////////////////////////////////// + // dereference operators and functions + + template + T& smart_ptr_base::operator*(void) throw(null_dereference) + { + if (m_holder->null()) throw null_dereference("null pointer dereferenced in smart_ptr::operator*"); + return m_holder->value(); + } + + template + const T& smart_ptr_base::operator*(void) const throw(null_dereference) + { + if (m_holder->null()) throw null_dereference("null pointer dereferenced in smart_ptr::operator*"); + return m_holder->value(); + } + + template + T* smart_ptr_base::operator->(void) throw(null_dereference) + { + if (m_holder->null()) throw null_dereference("null pointer dereferenced in smart_ptr::operator->"); + return m_holder->pointer(); + } + + template + const T* smart_ptr_base::operator->(void) const throw(null_dereference) + { + if (m_holder->null()) throw null_dereference("null pointer dereferenced in smart_ptr::operator->"); + return m_holder->pointer(); + } + + ////////////////////////////////////////////////////////////////////////////// + // explicit function forms of the above assignment dereference operators + + template + void smart_ptr_base::set_value(const T& data) throw(illegal_copy) + { + m_holder->set(C()(data)); + } + + template + T& smart_ptr_base::value(void) throw(null_dereference) + { + if (m_holder->null()) throw null_dereference("null pointer dereferenced in smart_ptr::value"); + return m_holder->value(); + } + + template + const T& smart_ptr_base::value(void) const throw(null_dereference) + { + if (m_holder->null()) throw null_dereference("null pointer dereferenced in smart_ptr::value"); + return m_holder->value(); + } + + template + void smart_ptr_base::set(T* data) + { + m_holder->set(data); + } + + template + T* smart_ptr_base::pointer(void) + { + return m_holder->pointer(); + } + + template + const T* smart_ptr_base::pointer(void) const + { + return m_holder->pointer(); + } + + //////////////////////////////////////////////////////////////////////////////// + // functions to manage counted referencing + + // make this an alias of the passed object + template + void smart_ptr_base::alias(const smart_ptr_base& r) + { + // make it alias-copy safe - this means that I don't try to do the + // assignment if r is either the same object or an alias of it + // if (m_holder == r.m_holder) return; + // if (m_holder->decrement()) + // delete m_holder; + // m_holder = r.m_holder; + // m_holder->increment(); + make_alias(r.m_holder); + } + + template + bool smart_ptr_base::aliases(const smart_ptr_base& r) const + { + return m_holder == r.m_holder; + } + + template + unsigned smart_ptr_base::alias_count(void) const + { + return m_holder->count(); + } + + template + void smart_ptr_base::clear(void) + { + m_holder->clear(); + } + + template + void smart_ptr_base::clear_unique(void) + { + if (m_holder->count() == 1) + m_holder->clear(); + else + { + m_holder->decrement(); + m_holder = 0; + m_holder = new smart_ptr_holder; + } + } + + template + void smart_ptr_base::make_unique(void) throw(illegal_copy) + { + if (m_holder->count() > 1) + { + smart_ptr_holder* old_holder = m_holder; + m_holder->decrement(); + m_holder = 0; + m_holder = new smart_ptr_holder; + if (old_holder->pointer()) + m_holder->set(C()(old_holder->value())); + } + } + + template + void smart_ptr_base::copy(const smart_ptr_base& data) throw(illegal_copy) + { + alias(data); + make_unique(); + } + + // internal function for distinguishing unique smart_ptr objects + // used for example in persistence routines + + template + void* smart_ptr_base::handle(void) const + { + return m_holder; + } + + template + void smart_ptr_base::make_alias(void* handle) + { + smart_ptr_holder* r_holder = (smart_ptr_holder*)handle; + if (m_holder != r_holder) + { + if (m_holder->decrement()) + delete m_holder; + m_holder = r_holder; + m_holder->increment(); + } + } + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + diff --git a/src/Moof/stlplus/triple.hpp b/src/Moof/stlplus/triple.hpp new file mode 100755 index 0000000..9546cce --- /dev/null +++ b/src/Moof/stlplus/triple.hpp @@ -0,0 +1,54 @@ +#ifndef STLPLUS_TRIPLE +#define STLPLUS_TRIPLE +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton, from an original by Dan Milton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +// Similar to the STL pair but with three elements + +//////////////////////////////////////////////////////////////////////////////// +#include "containers_fixes.hpp" + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // the triple class + + template + struct triple + { + typedef T1 first_type; + typedef T2 second_type; + typedef T3 third_type; + + T1 first; + T2 second; + T3 third; + + triple(void); + triple(const T1& p1, const T2& p2, const T3& p3); + triple(const triple& t2); + }; + + //////////////////////////////////////////////////////////////////////////////// + // creation + + template + triple make_triple(const T1& first, const T2& second, const T3& third); + + //////////////////////////////////////////////////////////////////////////////// + // comparison + + template + bool operator == (const triple& left, const triple& right); + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + +#include "triple.tpp" +#endif diff --git a/src/Moof/stlplus/triple.tpp b/src/Moof/stlplus/triple.tpp new file mode 100755 index 0000000..60e94aa --- /dev/null +++ b/src/Moof/stlplus/triple.tpp @@ -0,0 +1,56 @@ +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton, from an original by Dan Milton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004-2009 +// License: BSD License, see ../docs/license.html + +//////////////////////////////////////////////////////////////////////////////// + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // the triple class + + template + triple::triple(void) : + first(), second(), third() + { + } + + template + triple::triple(const T1& p1, const T2& p2, const T3& p3) : + first(p1), second(p2), third(p3) + { + } + + template + triple::triple(const triple& t2) : + first(t2.first), second(t2.second), third(t2.third) + { + } + + //////////////////////////////////////////////////////////////////////////////// + // creation + + template + triple make_triple(const T1& first, const T2& second, const T3& third) + { + return triple(first,second,third); + } + + //////////////////////////////////////////////////////////////////////////////// + // comparison + + template + bool operator == (const triple& left, const triple& right) + { + // triples are equal if all elements are equal + return left.first == right.first && left.second == right.second && left.third == right.third; + } + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + diff --git a/src/YoinkApp.cc b/src/YoinkApp.cc index 1b9fa03..43767d2 100644 --- a/src/YoinkApp.cc +++ b/src/YoinkApp.cc @@ -131,6 +131,7 @@ YoinkApp::~YoinkApp() { delete someChar; delete font; + delete testScene; Mf::Dispatcher::instance().removeHandler(this); } @@ -157,9 +158,13 @@ void YoinkApp::setupGL() glClearColor(1.0, 0.0, 0.0, 1.0); - glMatrixMode(GL_PROJECTION); - glLoadIdentity(); - gluPerspective(60.0, 1.33333, 1.0, 2500.0); + //glMatrixMode(GL_PROJECTION); + //glLoadIdentity(); + //gluPerspective(60.0, 1.33333, 1.0, 2500.0); + camera.setProjection(cml::rad(60.0), 1.33333, 32.0, 2500.0); + camera.uploadProjectionToGL(); + + //glMatrixMode(GL_MODELVIEW); //glLineWidth(10.0f); } @@ -208,10 +213,10 @@ void YoinkApp::draw(Mf::Scalar alpha) glBindTexture(GL_TEXTURE_2D, 0); //glRotatef(drawstate*15.0f, 0.0, 1.0, 0.0); //glTranslatef(x, y, z); - glLoadMatrix(camera.getTransformation().data()); + glLoadMatrix(camera.getModelviewMatrix().data()); // DRAW THE SCENE - testScene->draw(alpha); + testScene->draw(alpha, camera); /* @@ -394,19 +399,16 @@ void YoinkApp::handleEvent(const Mf::Event& event) case SDL_VIDEORESIZE: glViewport(0, 0, event.resize.w, event.resize.h); - - glMatrixMode(GL_PROJECTION); - glLoadIdentity(); - - - gluPerspective(60.0, double(event.resize.w / event.resize.h), 1.0, 2500.0); - - glMatrixMode(GL_MODELVIEW); + camera.setProjection(cml::rad(60.0), double(event.resize.w / event.resize.h), 32.0, 2500.0); + camera.uploadProjectionToGL(); break; } } +#include + + int main(int argc, char* argv[]) { std::cout << PACKAGE_STRING << std::endl @@ -416,6 +418,39 @@ int main(int argc, char* argv[]) int status = 0; + //Mf::Tree::Ptr rootNode; + //Mf::Tree::Ptr temp, temp2, temp3; + + //rootNode = Mf::Tree::Ptr(Mf::Tree::createNewNode(1)); + + //temp = Mf::Tree::Ptr(Mf::Tree::createNewNode(2)); + //temp3 = temp; + //rootNode->addChild(temp); + + //temp = Mf::Tree::Ptr(Mf::Tree::createNewNode(3)); + //temp2 = temp; + //rootNode->addChild(temp); + + //temp = Mf::Tree::Ptr(Mf::Tree::createNewNode(4)); + //rootNode->addChild(temp); + + //temp = Mf::Tree::Ptr(Mf::Tree::createNewNode(5)); + //temp2->addChild(temp); + + //temp = Mf::Tree::Ptr(Mf::Tree::createNewNode(6)); + //temp2->addChild(temp); + + //temp = Mf::Tree::Ptr(Mf::Tree::createNewNode(7)); + //temp3->addChild(temp); + + //temp = rootNode; + //while (temp) + //{ + //temp->print(); + //temp = temp->getNext(); + //} + //return 0; + try { YoinkApp app(argc, argv); -- 2.45.2