[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"
{
"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":
[
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 \
Moof/Settings.cc \
Moof/Settings.hh \
Moof/Singleton.hh \
+ Moof/Sphere.cc \
+ Moof/Sphere.hh \
Moof/StringTools.cc \
Moof/StringTools.hh \
Moof/Texture.cc \
#include <Moof/Aabb.hh>
#include <Moof/Camera.hh>
+#include <Moof/OpenGL.hh>
+#include <Moof/Texture.hh>
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],
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);
}
#include <Moof/Cullable.hh>
#include <Moof/Drawable.hh>
#include <Moof/Math.hh>
+#include <Moof/Plane.hh>
namespace Mf {
(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;
};
#include <iostream>
#include <Moof/Camera.hh>
+#include <Moof/OpenGL.hh>
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);
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_);
}
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
private:
Vector3 position_;
Quaternion rotation_;
+ Matrix4 projection_;
- Matrix4 transformation_;
+ Matrix4 modelview_;
Frustum frustum_;
Lerpv3 pInterp_;
-
- Quaternion srcRotation_;
- Quaternion dstRotation_;
- Scalar tInterp_;
};
* 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()
nextStep += timestep;
}
+ if (ticksNow >= nextStep)
+ {
+ nextStep = ticksNow + timestep;
+ }
if (ticksNow >= nextDraw)
{
}
while (running);
- return 0;
+ return exitCode;
}
VideoPtr video;
bool running;
+ int exitCode;
Scalar timestep;
Scalar drawRate;
return impl_->run();
}
-void Engine::stop()
+void Engine::stop(int exitCode)
{
impl_->running = false;
+ impl_->exitCode = exitCode;
}
virtual ~Engine();
int run();
- void stop();
+ void stop(int exitCode = 0);
void setTimestep(Scalar ts);
Scalar getTimestep();
#include <Moof/Aabb.hh>
#include <Moof/Cullable.hh>
#include <Moof/Drawable.hh>
+#include <Moof/Sphere.hh>
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<Entity> EntityPtr;
--- /dev/null
+
+/*******************************************************************************
+
+ 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 <Moof/Aabb.hh>
+#include <Moof/Frustum.hh>
+#include <Moof/Sphere.hh>
+
+
+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: *************************************************/
+
#ifndef _MOOF_FRUSTUM_HH_
#define _MOOF_FRUSTUM_HH_
+#include <Moof/Math.hh>
#include <Moof/Plane.hh>
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
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;
};
--- /dev/null
+
+/*******************************************************************************
+
+ 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: *************************************************/
+
--- /dev/null
+
+/*******************************************************************************
+
+ 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 <string>
+
+#include <stlplus/hash.hpp>
+
+
+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: *************************************************/
+
* 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;
}
* after the last interested code releases its hold on the object.
*/
-#include <map>
+#include <Moof/Hash.hh>
#include <string>
-
namespace Mf {
template <class T>
class Mippleton
{
- typedef std::pair<unsigned,T*> ptr_value_t;
- typedef std::pair<std::string,ptr_value_t> ptr_map_pair_t;
- typedef std::map<std::string,ptr_value_t> ptr_map_t;
+ typedef std::pair<unsigned,T*> ptr_value_t;
+ typedef std::pair<std::string,ptr_value_t> ptr_map_pair_t;
+ typedef stlplus::hash<std::string,ptr_value_t,hash_string> ptr_map_t;
+ //typedef std::map<std::string,ptr_value_t> 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
{
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
{
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);
}
}
};
template <class T>
-std::map<std::string,std::pair<unsigned,T*> > Mippleton<T>::ptrs_;
+stlplus::hash< std::string,std::pair<unsigned,T*>,hash_string >
+//std::map< std::string,std::pair<unsigned,T*> >
+ Mippleton<T>::ptrs_;
} // namespace Mf
#include <boost/shared_ptr.hpp>
+#include <Moof/Aabb.hh>
+#include <Moof/Drawable.hh>
+#include <Moof/Entity.hh>
#include <Moof/Math.hh>
+#include <Moof/Sphere.hh>
#include <Moof/Tree.hh>
namespace Mf {
-class Entity;
+struct OctreeNode : public Entity
+{
+ std::list<EntityPtr> 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<EntityPtr>::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<EntityPtr>::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<Octree> OctreePtr;
+
+class Octree : public Tree<OctreeNode>
{
+
+ Octree() {}
+
+ explicit Octree(const OctreeNode& initNode) :
+ Tree<OctreeNode>(initNode) {}
+
public:
- class Node
+ inline static OctreePtr createNewNode(const OctreeNode& item)
+ {
+ OctreePtr newNode = OctreePtr(new Octree(item));
+ init(newNode);
+ return newNode;
+ }
+
+
+ static Tree<OctreeNode>::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<boost::shared_ptr<Entity> > 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<Node>()) {}
+ if (halfspace == Plane::POSITIVE)
+ {
+ Plane yz = node->node.getAabb().getPlaneYZ();
+ halfspace = yz.intersectsSphere(entity->getSphere());
- Octree(const Aabb& aabb) :
- root_(new Tree<Node>(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<Node>::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<Node>::Ptr root_;
};
+
} // namespace Mf
#endif // _MOOF_OCTREE_HH_
--- /dev/null
+
+/*******************************************************************************
+
+ 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: *************************************************/
+
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;
};
{
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)
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:
Quad* quad = new Quad(quadVertices, texture, indices[h][w]);
boost::shared_ptr<Quad> quadPtr(quad);
- objects.push_back(quadPtr);
+ //objects.push_back(quadPtr);
+ Octree::add(octree, quadPtr);
}
}
}
boost::shared_ptr<Quad> quadPtr(quad);
- objects.push_back(quadPtr);
+ //objects.push_back(quad_Ptr);
+ Octree::add(octree, quadPtr);
}
}
{
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);
}
- 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);
Aabb playfieldBounds;
Aabb maximumBounds;
- typedef std::vector< boost::shared_ptr<Quad> > QuadVector;
- QuadVector objects;
+ //typedef std::vector< boost::shared_ptr<Quad> > QuadVector;
+ //QuadVector objects;
+ OctreePtr octree;
};
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();
}
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);
--- /dev/null
+
+/*******************************************************************************
+
+ 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 <Moof/Camera.hh>
+#include <Moof/OpenGL.hh>
+#include <Moof/Sphere.hh>
+
+
+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: *************************************************/
+
--- /dev/null
+
+/*******************************************************************************
+
+ 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 <Moof/Cullable.hh>
+#include <Moof/Drawable.hh>
+#include <Moof/Math.hh>
+
+
+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: *************************************************/
+
}
+void Texture::resetBind()
+{
+ glBindTexture(GL_TEXTURE_2D, 0);
+ TextureImpl::globalObject_ = 0;
+}
+
+
unsigned Texture::getWidth() const
{
// pass through
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");
}
void bind() const;
GLuint getObject() const;
+ static void resetBind();
+
unsigned getWidth() const;
unsigned getHeight() const;
class Tree
{
public:
- typedef boost::shared_ptr<Tree> Ptr;
- typedef boost::weak_ptr<Tree> WeakPtr;
+ typedef boost::shared_ptr<Tree> Ptr;
+ typedef boost::weak_ptr<Tree> 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<T>());
+ }
- inline Ptr next() const
+ inline static Ptr createNewNode(const T& item)
+ {
+ Ptr newNode = Ptr(new Tree<T>(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_;
}
return Ptr();
}
- inline Ptr lastChild() const
+ inline Ptr getLastChild() const
{
- Ptr child = firstChild();
+ Ptr child = getFirstChild();
if (child)
{
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();
}
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();
}
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
{
};
- 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();
}
};
--- /dev/null
+#ifndef STLPLUS_CONTAINERS\r
+#define STLPLUS_CONTAINERS\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+// Allows all the STLplus containers to be included in one go\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+#include "digraph.hpp"\r
+#include "foursome.hpp"\r
+#include "hash.hpp"\r
+#include "matrix.hpp"\r
+#include "ntree.hpp"\r
+#include "smart_ptr.hpp"\r
+#include "triple.hpp"\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#endif\r
--- /dev/null
+#ifndef STLPLUS_CONTAINERS_FIXES\r
+#define STLPLUS_CONTAINERS_FIXES\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+// Contains work arounds for OS or Compiler specific problems with container\r
+// templates\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+// Unnecessary compiler warnings\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+#ifdef _MSC_VER\r
+// Microsoft Visual Studio\r
+// shut up the following irritating warnings\r
+// 4275 - VC6, exported class was derived from a class that was not exported\r
+// 4786 - VC6, identifier string exceeded maximum allowable length and was truncated (only affects debugger)\r
+// 4305 - VC6, identifier type was converted to a smaller type\r
+// 4503 - VC6, decorated name was longer than the maximum the compiler allows (only affects debugger)\r
+// 4309 - VC6, type conversion operation caused a constant to exceeded the space allocated for it\r
+// 4290 - VC6, C++ exception specification ignored\r
+// 4800 - VC6, forcing value to bool 'true' or 'false' (performance warning)\r
+// 4355 - VC6, 'this' : used in base member initializer list\r
+// 4675 - VC7.1, "change" in function overload resolution _might_ have altered program\r
+// 4996 - VC8, 'xxxx' was declared deprecated\r
+#pragma warning(disable: 4275 4786 4305 4503 4309 4290 4800 4355 4675 4996)\r
+#endif\r
+\r
+#ifdef __BORLANDC__\r
+// Borland\r
+// Shut up the following irritating warnings\r
+// 8008 - Condition is always true.\r
+// Whenever the compiler encounters a constant comparison that (due to\r
+// the nature of the value being compared) is always true or false, it\r
+// issues this warning and evaluates the condition at compile time.\r
+// 8026 - Functions with exception specifications are not expanded inline\r
+// 8027 - Functions with xxx are not expanded inline\r
+// 8060 - Possibly incorrect assignment.\r
+// This warning is generated when the compiler encounters an assignment\r
+// operator as the main operator of a conditional expression (part of\r
+// an if, while, or do-while statement). This is usually a\r
+// typographical error for the equality operator.\r
+// 8066 - Unreachable code.\r
+// A break, continue, goto, or return statement was not followed by a\r
+// label or the end of a loop or function. The compiler checks while,\r
+// do, and for loops with a constant test condition, and attempts to\r
+// recognize loops that can't fall through.\r
+#pragma warn -8008\r
+#pragma warn -8026\r
+#pragma warn -8027\r
+#pragma warn -8060\r
+#pragma warn -8066\r
+#endif\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+// Problems with the typename keyword\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// There are problems with using the 'typename' keyword. Technically, if you\r
+// use a type member of a template class (i.e. a type declared within the\r
+// template class by a local typedef), you need to tell the compiler that it\r
+// is a type name. This is because the compiler cannot work out whether a\r
+// member is a type, a method or a data field at compile time. However,\r
+// support for the typename keyword has traditionally been incomplete in both\r
+// gcc and Visual Studio. I have used macros to try to resolve this issue. The\r
+// macros add the keyword for compiler versions that require it and omit it\r
+// for compiler versions that do not support it\r
+\r
+// There are five places where typename keywords cause problems:\r
+//\r
+// 1) in a typedef where a template class's member type is being mapped onto\r
+// a type definition within another template class or function \r
+// e.g. template<typename T> fn () {\r
+// typedef typename someclass<T>::member_type local_type;\r
+// ^^^^^^^^\r
+// 2) in a function parameter declaration, with similar rules to the above\r
+// e.g. template<typename T> fn (typename someclass<T>::member_type)\r
+// ^^^^^^^^\r
+// 3) in instantiating a template, the parameter to the template, with similar rules to the above\r
+// e.g. template_class<typename someclass<T>::member_type>\r
+// ^^^^^^^^\r
+// 4) Return expressions\r
+// e.g. return typename ntree<T>::const_iterator(this,m_root);\r
+// ^^^^^^^^\r
+// 5) Creating temporary objects when passing arguments to a function or constructor\r
+// e.g. return typename ntree<T>::const_prefix_iterator(typename ntree<T>::const_iterator(this,m_root));\r
+// ^^^^^^^^\r
+// Note that the typename keyword is only required when the type being referred to is a member of a template class\r
+//\r
+// So far it *seems* as if all compilers either require all of them or none of\r
+// them, so this set of situations can be handled by a single macro\r
+\r
+// default values, overridden for individual problem cases below\r
+#define TYPENAME typename\r
+\r
+// GCC \r
+// - pre-version 3 didn't handle typename in any of these cases\r
+// - version 3 onwards, typename is required for all three cases as per default\r
+#ifdef __GNUC__\r
+#if __GNUC__ < 3\r
+#undef TYPENAME\r
+#define TYPENAME\r
+#endif\r
+#endif\r
+\r
+// Visual Studio\r
+// - version 6 (compiler v.12) cannot handle typename in any of these cases\r
+// - version 7 (.NET) (compiler v.13) requires a typename in a parameter specification but supports all\r
+// - version 8 (2005) (compiler v.14) requires parameters and templates, supports all\r
+#ifdef _MSC_VER\r
+#if _MSC_VER < 1300\r
+#undef TYPENAME\r
+#define TYPENAME\r
+#endif\r
+#endif\r
+\r
+// Borland \r
+// - doesn't handle typename in 5.5, does in 5.82, not sure about other cases\r
+#ifdef __BORLANDC__\r
+#if __BORLANDC__ <= 0x550\r
+#undef TYPENAME\r
+#define TYPENAME\r
+#endif\r
+#endif\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#endif\r
--- /dev/null
+#ifndef STLPLUS_DIGRAPH\r
+#define STLPLUS_DIGRAPH\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+// STL-style Directed graph template component\r
+// Digraph stands for directed-graph, i.e. all arcs have a direction\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include "containers_fixes.hpp"\r
+#include "safe_iterator.hpp"\r
+#include "exceptions.hpp"\r
+#include <vector>\r
+#include <map>\r
+#include <set>\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Internals\r
+\r
+ template<typename NT, typename AT> class digraph_node;\r
+ template<typename NT, typename AT> class digraph_arc;\r
+ template<typename NT, typename AT> class digraph;\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // The Digraph iterator classes\r
+ // a digraph_iterator points to a node whilst a digraph_arc_iterator points to an arc\r
+ // Note that these are redefined as:\r
+ // digraph<NT,AT>::iterator - points to a non-const node\r
+ // digraph<NT,AT>::const_iterator - points to a const node\r
+ // digraph<NT,AT>::arc_iterator - points to a non-const arc\r
+ // digraph<NT,AT>::const_arc_iterator - points to a const arc\r
+ // and this is the form in which they should be used\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ class digraph_iterator : public safe_iterator<digraph<NT,AT>, digraph_node<NT,AT> >\r
+ {\r
+ public:\r
+ friend class digraph<NT,AT>;\r
+\r
+ // local type definitions\r
+ // an iterator points to an object whilst a const_iterator points to a const object\r
+ typedef digraph_iterator<NT,AT,NT&,NT*> iterator;\r
+ typedef digraph_iterator<NT,AT,const NT&,const NT*> const_iterator;\r
+ typedef digraph_iterator<NT,AT,NRef,NPtr> this_iterator;\r
+ typedef NRef reference;\r
+ typedef NPtr pointer;\r
+\r
+ // constructor to create a null iterator - you must assign a valid value to this iterator before using it\r
+ digraph_iterator(void);\r
+ ~digraph_iterator(void);\r
+\r
+ // Type conversion methods allow const_iterator and iterator to be converted\r
+ // convert an iterator/const_iterator to a const_iterator\r
+ const_iterator constify(void) const;\r
+ // convert an iterator/const_iterator to an iterator\r
+ iterator deconstify(void) const;\r
+\r
+ // increment/decrement operators used to step through the set of all nodes in a graph\r
+ // it is only legal to increment a valid iterator\r
+ // pre-increment\r
+ this_iterator& operator ++ (void)\r
+ throw(null_dereference,end_dereference);\r
+ // post-increment\r
+ this_iterator operator ++ (int)\r
+ throw(null_dereference,end_dereference);\r
+ // pre-decrement\r
+ this_iterator& operator -- (void)\r
+ throw(null_dereference,end_dereference);\r
+ // post-decrement\r
+ this_iterator operator -- (int)\r
+ throw(null_dereference,end_dereference);\r
+\r
+ // test useful for testing whether iteration has completed and for inclusion in other containers\r
+ // Note: this class also inherits the safe_iterator methods: valid(), null(), end()\r
+ bool operator == (const this_iterator& r) const;\r
+ bool operator != (const this_iterator& r) const;\r
+ bool operator < (const this_iterator& r) const;\r
+\r
+ // access the node data - a const_iterator gives you a const element, an iterator a non-const element\r
+ // it is illegal to dereference an invalid (i.e. null or end) iterator\r
+ reference operator*(void) const\r
+ throw(null_dereference,end_dereference);\r
+ pointer operator->(void) const\r
+ throw(null_dereference,end_dereference);\r
+\r
+ public:\r
+ // constructor used by digraph to create a non-null iterator\r
+ explicit digraph_iterator(digraph_node<NT,AT>* node);\r
+ // constructor used by digraph to create an end iterator\r
+ explicit digraph_iterator(const digraph<NT,AT>* owner);\r
+ // used to create an alias of an iterator\r
+ explicit digraph_iterator(const safe_iterator<digraph<NT,AT>, digraph_node<NT,AT> >& iterator);\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename NT, typename AT, typename ARef, typename APtr>\r
+ class digraph_arc_iterator : public safe_iterator<digraph<NT,AT>, digraph_arc<NT,AT> >\r
+ {\r
+ public:\r
+ friend class digraph<NT,AT>;\r
+\r
+ // local type definitions\r
+ // an iterator points to an object whilst a const_iterator points to a const object\r
+ typedef digraph_arc_iterator<NT,AT,AT&,AT*> iterator;\r
+ typedef digraph_arc_iterator<NT,AT,const AT&,const AT*> const_iterator;\r
+ typedef digraph_arc_iterator<NT,AT,ARef,APtr> this_iterator;\r
+ typedef ARef reference;\r
+ typedef APtr pointer;\r
+\r
+ // constructor to create a null iterator - you must assign a valid value to this iterator before using it\r
+ digraph_arc_iterator(void);\r
+ ~digraph_arc_iterator(void);\r
+\r
+ // Type conversion methods allow const_iterator and iterator to be converted\r
+ // convert an iterator/const_iterator to a const_iterator\r
+ const_iterator constify(void) const;\r
+ // convert an iterator/const_iterator to an iterator\r
+ iterator deconstify(void) const;\r
+\r
+ // increment/decrement operators used to step through the set of all nodes in a graph\r
+ // it is only legal to increment a valid iterator\r
+ // pre-increment\r
+ this_iterator& operator ++ (void)\r
+ throw(null_dereference,end_dereference);\r
+ // post-increment\r
+ this_iterator operator ++ (int)\r
+ throw(null_dereference,end_dereference);\r
+ // pre-decrement\r
+ this_iterator& operator -- (void)\r
+ throw(null_dereference,end_dereference);\r
+ // post-decrement\r
+ this_iterator operator -- (int)\r
+ throw(null_dereference,end_dereference);\r
+\r
+ // test useful for testing whether iteration has completed and for inclusion in other containers\r
+ // Note: this class also inherits the safe_iterator methods: valid(), null(), end()\r
+ bool operator == (const this_iterator&) const;\r
+ bool operator != (const this_iterator&) const;\r
+ bool operator < (const this_iterator&) const;\r
+\r
+ // access the node data - a const_iterator gives you a const element, an iterator a non-const element\r
+ // it is illegal to dereference an invalid (i.e. null or end) iterator\r
+ reference operator*(void) const\r
+ throw(null_dereference,end_dereference);\r
+ pointer operator->(void) const\r
+ throw(null_dereference,end_dereference);\r
+\r
+ public:\r
+ // constructor used by digraph to create a non-null iterator\r
+ explicit digraph_arc_iterator(digraph_arc<NT,AT>* arc);\r
+ // constructor used by digraph to create an end iterator\r
+ explicit digraph_arc_iterator(const digraph<NT,AT>* owner);\r
+ // used to create an alias of an iterator\r
+ explicit digraph_arc_iterator(const safe_iterator<digraph<NT,AT>, digraph_arc<NT,AT> >& iterator);\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // The Graph class\r
+ // NT is the Node type and AT is the Arc type\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename NT, typename AT>\r
+ class digraph\r
+ {\r
+ public:\r
+ // STL-like typedefs for the types and iterators\r
+ typedef NT node_type;\r
+ typedef AT arc_type;\r
+ typedef digraph_iterator<NT,AT,NT&,NT*> iterator;\r
+ typedef digraph_iterator<NT,AT,const NT&,const NT*> const_iterator;\r
+ typedef digraph_arc_iterator<NT,AT,AT&,AT*> arc_iterator;\r
+ typedef digraph_arc_iterator<NT,AT,const AT&,const AT*> const_arc_iterator;\r
+\r
+ // supplementary types used throughout\r
+\r
+ // a path is represented as a vector of arcs so the forward traversal is\r
+ // done by going from begin() to end() or 0 to size-1 - of course a backward\r
+ // traversal can be done by traversing the vector backwards\r
+ typedef std::vector<arc_iterator> arc_vector;\r
+ typedef std::vector<const_arc_iterator> const_arc_vector;\r
+ const_arc_vector constify_arcs(const arc_vector&) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ arc_vector deconstify_arcs(const const_arc_vector&) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // a path vector is a vector of paths used to represent all the paths from one node to another\r
+ // there is no particular ordering to the paths in the vector\r
+ typedef std::vector<arc_vector> path_vector;\r
+ typedef std::vector<const_arc_vector> const_path_vector;\r
+ const_path_vector constify_paths(const path_vector&) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ path_vector deconstify_paths(const const_path_vector&) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // a node vector is a simple vector of nodes used to represent the reachable sets\r
+ // there is no particular ordering to the nodes in the vector\r
+ typedef std::vector<iterator> node_vector;\r
+ typedef std::vector<const_iterator> const_node_vector;\r
+ const_node_vector constify_nodes(const node_vector&) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ node_vector deconstify_nodes(const const_node_vector&) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // callback used in the path algorithms to select which arcs to consider\r
+ typedef bool (*arc_select_fn) (const digraph<NT,AT>&, const_arc_iterator);\r
+\r
+ // a value representing an unknown offset\r
+ // Note that it's static so use in the form digraph<NT,AT>::npos()\r
+ static unsigned npos(void);\r
+\r
+ //////////////////////////////////////////////////////////////////////////\r
+ // Constructors, destructors and copies\r
+\r
+ digraph(void);\r
+ ~digraph(void);\r
+\r
+ // copy constructor and assignment both copy the graph\r
+ digraph(const digraph<NT,AT>&);\r
+ digraph<NT,AT>& operator=(const digraph<NT,AT>&);\r
+\r
+ //////////////////////////////////////////////////////////////////////////\r
+ // Basic Node functions\r
+ // Nodes are referred to by iterators created when the node is inserted.\r
+ // Iterators remain valid unless the node is erased (they are list iterators, so no resize problems)\r
+ // It is also possible to walk through all the nodes using a list-like start() to end() loop\r
+ // Each node has a set of input arcs and output arcs. These are indexed by an unsigned i.e. they form a vector.\r
+ // The total number of inputs is the fanin and the total number of outputs is the fanout.\r
+ // The contents of the node (type NT) are accessed, of course, by dereferencing the node iterator.\r
+\r
+ // tests for the number of nodes and the special test for zero nodes\r
+ bool empty(void) const;\r
+ unsigned size(void) const;\r
+\r
+ // add a new node and return its iterator\r
+ iterator insert(const NT& node_data);\r
+\r
+ // remove a node and return the iterator to the next node\r
+ // erasing a node erases its arcs\r
+ iterator erase(iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // remove all nodes\r
+ void clear(void);\r
+\r
+ // traverse all the nodes in no particular order using STL-style iteration\r
+ const_iterator begin(void) const;\r
+ iterator begin(void);\r
+ const_iterator end(void) const;\r
+ iterator end(void);\r
+\r
+ // access the inputs of this node\r
+ // the fanin is the number of inputs and the inputs are accessed using an index from 0..fanin-1\r
+ unsigned fanin(const_iterator) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ unsigned fanin(iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ const_arc_iterator input(const_iterator, unsigned) const\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+ arc_iterator input(iterator, unsigned)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+\r
+ // access the outputs of this node\r
+ // the fanout is the number of outputs and the outputs are accessed using an index from 0..fanout-1\r
+ unsigned fanout(const_iterator) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ unsigned fanout(iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ const_arc_iterator output(const_iterator, unsigned) const\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+ arc_iterator output(iterator, unsigned)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+\r
+ // convenience routines for getting the set of all inputs or all outputs as vectors\r
+ const_arc_vector inputs(const_iterator) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ arc_vector inputs(iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ const_arc_vector outputs(const_iterator) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ arc_vector outputs(iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // find the output index of an arc which goes from this node\r
+ // returns digraph<NT,AT>::npos if the arc is not an output of from\r
+ unsigned output_offset(const_iterator from, const_arc_iterator arc) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ unsigned output_offset(iterator from, arc_iterator arc)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // ditto for an input arc\r
+ unsigned input_offset(const_iterator to, const_arc_iterator arc) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ unsigned input_offset(iterator to, arc_iterator arc)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ //////////////////////////////////////////////////////////////////////////\r
+ // Basic Arc functions\r
+ // to avoid name conflicts, arc functions have the arc_ prefix \r
+ // Arcs, like nodes, are referred to by a list iterator which is returned by the arc_insert function\r
+ // They may also be visited from arc_begin() to arc_end()\r
+ // Each arc has a from field and a to field which contain the node iterators of the endpoints of the arc\r
+ // Of course, the arc data can be accessed by simply dereferencing the iterator\r
+\r
+ // tests for the number of arcs and the special test for zero arcs\r
+ bool arc_empty (void) const;\r
+ unsigned arc_size(void) const;\r
+\r
+ // add a new arc and return its iterator\r
+ arc_iterator arc_insert(iterator from, iterator to, const AT& arc_data = AT())\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // remove an arc and return the iterator to the next arc\r
+ arc_iterator arc_erase(arc_iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // remove all arcs\r
+ void arc_clear(void);\r
+\r
+ // traverse all the arcs in no particular order using STL-style iteration\r
+ const_arc_iterator arc_begin(void) const;\r
+ arc_iterator arc_begin(void);\r
+ const_arc_iterator arc_end(void) const;\r
+ arc_iterator arc_end(void);\r
+\r
+ // find the node that an arc points from or to\r
+ const_iterator arc_from(const_arc_iterator) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ iterator arc_from(arc_iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ const_iterator arc_to(const_arc_iterator) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ iterator arc_to(arc_iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // reconnect an arc to a different from and to node\r
+ void arc_move(arc_iterator arc, iterator from, iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // reconnect just the from node\r
+ void arc_move_from(arc_iterator arc, iterator from)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // reconnect just the to node\r
+ void arc_move_to(arc_iterator arc, iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // reverse the arc direction so that to becomes from and vice-versa\r
+ void arc_flip(arc_iterator arc)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Adjacency algorithms\r
+\r
+ // test whether the nodes are adjacent i.e. whether there is an arc going from from to to\r
+ bool adjacent(const_iterator from, const_iterator to) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ bool adjacent(iterator from, iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // as above, but returns the arc that makes the nodes adjacent\r
+ // returns the first arc if there's more than one, returns arc_end() if there are none\r
+ const_arc_iterator adjacent_arc(const_iterator from, const_iterator to) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ arc_iterator adjacent_arc(iterator from, iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // as above, but returns the set of all arcs that make two nodes adjacent (there may be more than one)\r
+ // returns an empty vector if there are none\r
+ const_arc_vector adjacent_arcs(const_iterator from, const_iterator to) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ arc_vector adjacent_arcs(iterator from, iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // return the adjacency sets for the node inputs or outputs, i.e. the set of nodes adjacent to this node\r
+ // each adjacent node will only be entered once even if there are multiple arcs between the nodes\r
+ const_node_vector input_adjacencies(const_iterator to) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ node_vector input_adjacencies(iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ const_node_vector output_adjacencies(const_iterator from) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ node_vector output_adjacencies(iterator from)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Topographical Sort Algorithm\r
+ // This generates a node ordering such that each node is visited after its fanin nodes.\r
+\r
+ // This only generates a valid ordering for a DAG. \r
+\r
+ // The return value is a pair : \r
+ // - the node vector which is a set of iterators to the nodes in sorted order\r
+ // - the arc vector is the set of backward ards that were broken to achieve the sort\r
+ // If the arc vector is empty then the graph formed a DAG.\r
+\r
+ // The arc selection callback can be used to ignore arcs that are not part\r
+ // of the ordering, i.e. arcs that are meant to be backwards arcs\r
+\r
+ std::pair<const_node_vector,const_arc_vector> sort(arc_select_fn = 0) const;\r
+ std::pair<node_vector,arc_vector> sort(arc_select_fn = 0);\r
+\r
+ // Simplified variant of above for graphs that are known to be DAGs.\r
+ // If the sort fails due to backward arcs, the\r
+ // return vector is empty. Note that this will also be empty if the graph\r
+ // has no nodes in it, so use the empty() method to differentiate.\r
+\r
+ const_node_vector dag_sort(arc_select_fn = 0) const;\r
+ node_vector dag_sort(arc_select_fn = 0);\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Basic Path Algorithms\r
+ // A path is a series of arcs - you can use arc_from and arc_to to convert\r
+ // that into a series of nodes. All the path algorithms take an arc_select\r
+ // which allows arcs to be selected or rejected for consideration in a path.\r
+\r
+ // A selection callback function is applied to each arc in the traversal and\r
+ // returns true if the arc is to be selected and false if the arc is to be\r
+ // rejected. If no function is provided the arc is selected. If you want to\r
+ // use arc selection you should create a function with the type profile given\r
+ // by the arc_select_fn type. The select function is passed both the graph and\r
+ // the arc iterator so that it is possible to select an arc on the basis of\r
+ // the nodes it is connected to.\r
+\r
+ // Note: I used a callback because the STL-like predicate idea wasn't working for me...\r
+\r
+ // test for the existence of a path from from to to\r
+ bool path_exists(const_iterator from, const_iterator to, arc_select_fn = 0) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ bool path_exists(iterator from, iterator to, arc_select_fn = 0)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // get the set of all paths from from to to\r
+ const_path_vector all_paths(const_iterator from, const_iterator to, arc_select_fn = 0) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ path_vector all_paths(iterator from, iterator to, arc_select_fn = 0)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // get the set of all nodes that can be reached by any path from from\r
+ const_node_vector reachable_nodes(const_iterator from, arc_select_fn = 0) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ node_vector reachable_nodes(iterator from, arc_select_fn = 0)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // get the set of all nodes that can reach to to by any path\r
+ const_node_vector reaching_nodes(const_iterator to, arc_select_fn = 0) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ node_vector reaching_nodes(iterator to, arc_select_fn = 0)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Unweighted Shortest path algorithms\r
+\r
+ // find the shortest path from from to to\r
+ // This is an unweighted shortest path algorithm, i.e. the weight of each\r
+ // arc is assumed to be 1, so just counts the number of arcs\r
+ // if there is more than one shortest path it returns the first one\r
+ // If there are no paths, returns an empty path\r
+ const_arc_vector shortest_path(const_iterator from, const_iterator to, arc_select_fn = 0) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ arc_vector shortest_path(iterator from, iterator to, arc_select_fn = 0)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // find the set of shortest paths from from to any other node in the graph\r
+ // that is reachable (i.e. for which path_exists() is true)\r
+ // This is an unweighted shortest path, so just counts the number of arcs\r
+ // if there is more than one shortest path to a node it returns the first one\r
+ // If there are no paths, returns an empty list\r
+ const_path_vector shortest_paths(const_iterator from, arc_select_fn = 0) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ path_vector shortest_paths(iterator from, arc_select_fn = 0)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ private:\r
+ friend class digraph_iterator<NT,AT,NT&,NT*>;\r
+ friend class digraph_iterator<NT,AT,const NT&,const NT*>;\r
+ friend class digraph_arc_iterator<NT,AT,AT&,AT*>;\r
+ friend class digraph_arc_iterator<NT,AT,const AT&, const AT*>;\r
+\r
+ typedef std::set<const_iterator> const_iterator_set;\r
+ typedef TYPENAME const_iterator_set::iterator const_iterator_set_iterator;\r
+\r
+ bool path_exists_r(const_iterator from, const_iterator to, const_iterator_set& visited, arc_select_fn) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ void all_paths_r(const_iterator from, const_iterator to, const_arc_vector& so_far, const_path_vector& result, arc_select_fn) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ void reachable_nodes_r(const_iterator from, const_iterator_set& visited, arc_select_fn) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ void reaching_nodes_r(const_iterator to, const_iterator_set& visited, arc_select_fn) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ digraph_node<NT,AT>* m_nodes_begin;\r
+ digraph_node<NT,AT>* m_nodes_end;\r
+ digraph_arc<NT,AT>* m_arcs_begin;\r
+ digraph_arc<NT,AT>* m_arcs_end;\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
+#include "digraph.tpp"\r
+#endif\r
--- /dev/null
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+// Note: I tried to write this using STL lists for the node and arc lists, but\r
+// it got far too hairy. The specific problem is that I wanted a digraph\r
+// iterator to contain a list::iterator so I needed to be able to generate a\r
+// list::iterator from a node or arc and STL list iterators don't give you that\r
+// functionality. I tried burgling the data structures, but that was\r
+// non-portable between different STL implementations so needed lots of #ifdefs\r
+// and so was mind-bogglingly awful and unreadable - in other words a\r
+// maintenance nightmare. I gave up and impemented my own lists - not difficult.\r
+\r
+// I use circular double-linked lists. The circular design means that both\r
+// ends of the list are equally accessible in unit time. An empty list\r
+// contains no objects. There is no end node in the list - unlike the STL\r
+// lists which have a dummy node for end iterators to point to -\r
+// conceptually the end iterator points one element beyond the end of the\r
+// list. However, I implement the end iterator concept in the iterator\r
+// itself, so do not need the dummy end node.\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include <algorithm>\r
+#include <deque>\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+// Internals\r
+\r
+namespace stlplus\r
+{\r
+\r
+ template<typename NT, typename AT>\r
+ class digraph_node\r
+ {\r
+ public:\r
+ master_iterator<digraph<NT,AT>, digraph_node<NT,AT> > m_master;\r
+ NT m_data;\r
+ digraph_node<NT,AT>* m_prev;\r
+ digraph_node<NT,AT>* m_next;\r
+ std::vector<digraph_arc<NT,AT>*> m_inputs;\r
+ std::vector<digraph_arc<NT,AT>*> m_outputs;\r
+ public:\r
+ digraph_node(const digraph<NT,AT>* owner, const NT& d = NT()) :\r
+ m_master(owner,this), m_data(d), m_prev(0), m_next(0)\r
+ {\r
+ }\r
+ ~digraph_node(void)\r
+ {\r
+ }\r
+ };\r
+\r
+ template<typename NT, typename AT>\r
+ class digraph_arc\r
+ {\r
+ public:\r
+ master_iterator<digraph<NT,AT>, digraph_arc<NT,AT> > m_master;\r
+ AT m_data;\r
+ digraph_arc<NT,AT>* m_prev;\r
+ digraph_arc<NT,AT>* m_next;\r
+ digraph_node<NT,AT>* m_from;\r
+ digraph_node<NT,AT>* m_to;\r
+ digraph_arc(const digraph<NT,AT>* owner, digraph_node<NT,AT>* from = 0, digraph_node<NT,AT>* to = 0, const AT& d = AT()) : \r
+ m_master(owner,this), m_data(d), m_prev(0), m_next(0), m_from(from), m_to(to)\r
+ {\r
+ }\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Iterators\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Node iterator\r
+\r
+ // construct a null iterator\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(void)\r
+ {\r
+ }\r
+\r
+ // valid iterator\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(digraph_node<NT,AT>* node) :\r
+ safe_iterator<digraph<NT,AT>,digraph_node<NT,AT> >(node->m_master)\r
+ {\r
+ }\r
+\r
+ // end iterator\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(const digraph<NT,AT>* owner) :\r
+ safe_iterator<digraph<NT,AT>,digraph_node<NT,AT> >(owner)\r
+ {\r
+ }\r
+\r
+ // alias an iterator\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(const safe_iterator<digraph<NT,AT>, digraph_node<NT,AT> >& iterator) : \r
+ safe_iterator<digraph<NT,AT>,digraph_node<NT,AT> >(iterator)\r
+ {\r
+ }\r
+\r
+ // destructor\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ digraph_iterator<NT,AT,NRef,NPtr>::~digraph_iterator(void)\r
+ {\r
+ }\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::const_iterator digraph_iterator<NT,AT,NRef,NPtr>::constify (void) const\r
+ {\r
+ return digraph_iterator<NT,AT,const NT&,const NT*>(*this);\r
+ }\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::iterator digraph_iterator<NT,AT,NRef,NPtr>::deconstify (void) const\r
+ {\r
+ return digraph_iterator<NT,AT,NT&,NT*>(*this);\r
+ }\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& digraph_iterator<NT,AT,NRef,NPtr>::operator ++ (void)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ this->assert_valid();\r
+ if (this->node()->m_next)\r
+ this->set(this->node()->m_next->m_master);\r
+ else\r
+ this->set_end();\r
+ return *this;\r
+ }\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator digraph_iterator<NT,AT,NRef,NPtr>::operator ++ (int)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ // post-increment is defined in terms of the pre-increment\r
+ digraph_iterator<NT,AT,NRef,NPtr> result(*this);\r
+ ++(*this);\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& digraph_iterator<NT,AT,NRef,NPtr>::operator -- (void)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ this->assert_valid();\r
+ if (this->node()->m_prev)\r
+ this->set(this->node()->m_prev->m_master);\r
+ else\r
+ this->set_end();\r
+ return *this;\r
+ }\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator digraph_iterator<NT,AT,NRef,NPtr>::operator -- (int)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ // post-decrement is defined in terms of the pre-decrement\r
+ digraph_iterator<NT,AT,NRef,NPtr> result(*this);\r
+ --(*this);\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ bool digraph_iterator<NT,AT,NRef,NPtr>::operator == (const TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& r) const\r
+ {\r
+ return equal(r);\r
+ }\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ bool digraph_iterator<NT,AT,NRef,NPtr>::operator != (const TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& r) const\r
+ {\r
+ return !operator==(r);\r
+ }\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ bool digraph_iterator<NT,AT,NRef,NPtr>::operator < (const TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& r) const\r
+ {\r
+ return compare(r) < 0;\r
+ }\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::reference digraph_iterator<NT,AT,NRef,NPtr>::operator*(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ this->assert_valid();\r
+ return this->node()->m_data;\r
+ }\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::pointer digraph_iterator<NT,AT,NRef,NPtr>::operator->(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ return &(operator*());\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Arc Iterator\r
+\r
+ template<typename NT, typename AT, typename ARef, typename APtr>\r
+ digraph_arc_iterator<NT,AT,ARef,APtr>::digraph_arc_iterator(void)\r
+ {\r
+ }\r
+\r
+ // valid iterator\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ digraph_arc_iterator<NT,AT,NRef,NPtr>::digraph_arc_iterator(digraph_arc<NT,AT>* arc) :\r
+ safe_iterator<digraph<NT,AT>,digraph_arc<NT,AT> >(arc->m_master)\r
+ {\r
+ }\r
+\r
+ // end iterator\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ digraph_arc_iterator<NT,AT,NRef,NPtr>::digraph_arc_iterator(const digraph<NT,AT>* owner) :\r
+ safe_iterator<digraph<NT,AT>,digraph_arc<NT,AT> >(owner)\r
+ {\r
+ }\r
+\r
+ // alias an iterator\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ digraph_arc_iterator<NT,AT,NRef,NPtr>::digraph_arc_iterator(const safe_iterator<digraph<NT,AT>, digraph_arc<NT,AT> >& iterator) : \r
+ safe_iterator<digraph<NT,AT>,digraph_arc<NT,AT> >(iterator)\r
+ {\r
+ }\r
+\r
+ template<typename NT, typename AT, typename ARef, typename APtr>\r
+ digraph_arc_iterator<NT,AT,ARef,APtr>::~digraph_arc_iterator(void)\r
+ {\r
+ }\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ TYPENAME digraph_arc_iterator<NT,AT,NRef,NPtr>::const_iterator digraph_arc_iterator<NT,AT,NRef,NPtr>::constify (void) const\r
+ {\r
+ return digraph_arc_iterator<NT,AT,const AT&,const AT*>(*this);\r
+ }\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ TYPENAME digraph_arc_iterator<NT,AT,NRef,NPtr>::iterator digraph_arc_iterator<NT,AT,NRef,NPtr>::deconstify (void) const\r
+ {\r
+ return digraph_arc_iterator<NT,AT,AT&,AT*>(*this);\r
+ }\r
+\r
+ template<typename NT, typename AT, typename ARef, typename APtr>\r
+ TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& digraph_arc_iterator<NT,AT,ARef,APtr>::operator ++ (void)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ this->assert_valid();\r
+ if (this->node()->m_next)\r
+ this->set(this->node()->m_next->m_master);\r
+ else\r
+ this->set_end();\r
+ return *this;\r
+ }\r
+\r
+ template<typename NT, typename AT, typename ARef, typename APtr>\r
+ TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator digraph_arc_iterator<NT,AT,ARef,APtr>::operator ++ (int)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ // post-increment is defined in terms of the pre-increment\r
+ digraph_arc_iterator<NT,AT,ARef,APtr> result(*this);\r
+ ++(*this);\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT, typename ARef, typename APtr>\r
+ TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& digraph_arc_iterator<NT,AT,ARef,APtr>::operator -- (void)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ this->assert_valid();\r
+ if (this->node()->m_prev)\r
+ this->set(this->node()->m_prev->m_master);\r
+ else\r
+ this->set_end();\r
+ return *this;\r
+ }\r
+\r
+ template<typename NT, typename AT, typename ARef, typename APtr>\r
+ TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator digraph_arc_iterator<NT,AT,ARef,APtr>::operator -- (int)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ // post-decrement is defined in terms of the pre-decrement\r
+ digraph_arc_iterator<NT,AT,ARef,APtr> result(*this);\r
+ --(*this);\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT, typename ARef, typename APtr>\r
+ bool digraph_arc_iterator<NT,AT,ARef,APtr>::operator == (const TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& r) const\r
+ {\r
+ return equal(r);\r
+ }\r
+\r
+ template<typename NT, typename AT, typename ARef, typename APtr>\r
+ bool digraph_arc_iterator<NT,AT,ARef,APtr>::operator != (const TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& r) const\r
+ {\r
+ return !operator==(r);\r
+ }\r
+\r
+ template<typename NT, typename AT, typename ARef, typename APtr>\r
+ bool digraph_arc_iterator<NT,AT,ARef,APtr>::operator < (const TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& r) const\r
+ {\r
+ return compare(r) < 0;\r
+ }\r
+\r
+ template<typename NT, typename AT, typename ARef, typename APtr>\r
+ TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::reference digraph_arc_iterator<NT,AT,ARef,APtr>::operator*(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ this->assert_valid();\r
+ return this->node()->m_data;\r
+ }\r
+\r
+ template<typename NT, typename AT, typename ARef, typename APtr>\r
+ TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::pointer digraph_arc_iterator<NT,AT,ARef,APtr>::operator->(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ return &(operator*());\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // subtype utilities\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::constify_arcs(const TYPENAME digraph<NT,AT>::arc_vector& arcs) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > result;\r
+ for (unsigned i = 0; i < arcs.size(); i++)\r
+ {\r
+ arcs[i].assert_valid(this);\r
+ result.push_back(arcs[i].constify());\r
+ }\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::deconstify_arcs(const TYPENAME digraph<NT,AT>::const_arc_vector& arcs) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > result;\r
+ for (unsigned i = 0; i < arcs.size(); i++)\r
+ {\r
+ arcs[i].assert_valid(this);\r
+ result.push_back(arcs[i].deconstify());\r
+ }\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_path_vector digraph<NT,AT>::constify_paths(const TYPENAME digraph<NT,AT>::path_vector& paths) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result;\r
+ for (unsigned i = 0; i < paths.size(); i++)\r
+ result.push_back(constify_arcs(paths[i]));\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::path_vector digraph<NT,AT>::deconstify_paths(const TYPENAME digraph<NT,AT>::const_path_vector& paths) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ std::vector<std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > > result;\r
+ for (unsigned i = 0; i < paths.size(); i++)\r
+ result.push_back(deconstify_arcs(paths[i]));\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::constify_nodes(const TYPENAME digraph<NT,AT>::node_vector& nodes) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;\r
+ for (unsigned i = 0; i < nodes.size(); i++)\r
+ {\r
+ nodes[i].assert_valid(this);\r
+ result.push_back(nodes[i].constify());\r
+ }\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::deconstify_nodes(const TYPENAME digraph<NT,AT>::const_node_vector& nodes) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ std::vector<digraph_iterator<NT,AT,NT&,NT*> > result;\r
+ for (unsigned i = 0; i < nodes.size(); i++)\r
+ {\r
+ nodes[i].assert_valid(this);\r
+ result.push_back(nodes[i].deconstify());\r
+ }\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ unsigned digraph<NT,AT>::npos(void)\r
+ {\r
+ return(unsigned)-1;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Constructors etc.\r
+\r
+ template<typename NT, typename AT>\r
+ digraph<NT,AT>::digraph(void) :\r
+ m_nodes_begin(0), m_nodes_end(0), m_arcs_begin(0), m_arcs_end(0)\r
+ {\r
+ // node and arc lists are circular double-linked lists\r
+ // they start out empty (no dummy end node)\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ digraph<NT,AT>::~digraph(void)\r
+ {\r
+ clear();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ digraph<NT,AT>::digraph(const digraph<NT,AT>& r) :\r
+ m_nodes_begin(0), m_nodes_end(0), m_arcs_begin(0), m_arcs_end(0)\r
+ {\r
+ *this = r;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ digraph<NT,AT>& digraph<NT,AT>::operator=(const digraph<NT,AT>& r)\r
+ {\r
+ // make it self-copy safe i.e. a=a; is a valid instruction\r
+ if (this == &r) return *this;\r
+ clear();\r
+ // first phase is to copy the nodes, creating a map of cross references from the old nodes to their new equivalents\r
+ std::map<digraph_iterator<NT,AT,const NT&,const NT*>, digraph_iterator<NT,AT,NT&,NT*> > xref;\r
+ for (digraph_iterator<NT,AT,const NT&,const NT*> n = r.begin(); n != r.end(); n++)\r
+ xref[n] = insert(*n);\r
+ // second phase is to copy the arcs, using the map to convert the old to and from nodes to the new nodes\r
+ for (digraph_arc_iterator<NT,AT, const AT&,const AT*> a = r.arc_begin(); a != r.arc_end(); a++)\r
+ arc_insert(xref[r.arc_from(a)],xref[r.arc_to(a)],*a);\r
+ return *this;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Basic Node functions\r
+\r
+ template<typename NT, typename AT>\r
+ bool digraph<NT,AT>::empty(void) const\r
+ {\r
+ return m_nodes_begin == 0;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ unsigned digraph<NT,AT>::size(void) const\r
+ {\r
+ unsigned count = 0;\r
+ for (digraph_iterator<NT,AT,const NT&,const NT*> i = begin(); i != end(); i++)\r
+ count++;\r
+ return count;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::insert(const NT& node_data)\r
+ {\r
+ digraph_node<NT,AT>* new_node = new digraph_node<NT,AT>(this,node_data);\r
+ if (!m_nodes_end)\r
+ {\r
+ // insert into an empty list\r
+ m_nodes_begin = new_node;\r
+ m_nodes_end = new_node;\r
+ }\r
+ else\r
+ {\r
+ // insert at the end of the list\r
+ new_node->m_prev = m_nodes_end;\r
+ m_nodes_end->m_next = new_node;\r
+ m_nodes_end = new_node;\r
+ }\r
+ return digraph_iterator<NT,AT,NT&,NT*>(new_node);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::erase(TYPENAME digraph<NT,AT>::iterator iter)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ iter.assert_valid(this);\r
+ // remove all arcs connected to this node first\r
+ // use arc_erase rather than arcs.erase because that tidies up the node at the other end of the arc too\r
+ for (unsigned i = fanin(iter); i--; )\r
+ arc_erase(input(iter,i));\r
+ for (unsigned j = fanout(iter); j--; )\r
+ arc_erase(output(iter,j));\r
+ // now unlink the node from the list and delete it\r
+ if (iter.node()->m_next)\r
+ iter.node()->m_next->m_prev = iter.node()->m_prev;\r
+ if (iter.node()->m_prev)\r
+ iter.node()->m_prev->m_next = iter.node()->m_next;\r
+ digraph_node<NT,AT>* next = iter.node()->m_next;\r
+ delete iter.node();\r
+ // return the next node in the list\r
+ if (next)\r
+ return digraph_iterator<NT,AT,NT&,NT*>(next);\r
+ else\r
+ return digraph_iterator<NT,AT,NT&,NT*>(this);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ void digraph<NT,AT>::clear(void)\r
+ {\r
+ // clearing the nodes also clears the arcs\r
+ for (digraph_iterator<NT,AT,NT&,NT*> i = begin(); i != end(); )\r
+ i = erase(i);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::begin(void) const\r
+ {\r
+ if (m_nodes_begin)\r
+ return digraph_iterator<NT,AT,const NT&,const NT*>(m_nodes_begin);\r
+ else\r
+ return digraph_iterator<NT,AT,const NT&,const NT*>(this);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::begin(void)\r
+ {\r
+ if (m_nodes_begin)\r
+ return digraph_iterator<NT,AT,NT&,NT*>(m_nodes_begin);\r
+ else\r
+ return digraph_iterator<NT,AT,NT&,NT*>(this);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::end(void) const\r
+ {\r
+ return digraph_iterator<NT,AT,const NT&,const NT*>(this);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::end(void)\r
+ {\r
+ return digraph_iterator<NT,AT,NT&,NT*>(this);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ unsigned digraph<NT,AT>::fanin(TYPENAME digraph<NT,AT>::const_iterator iter) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ iter.assert_valid(this);\r
+ return iter.node()->m_inputs.size();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ unsigned digraph<NT,AT>::fanin(TYPENAME digraph<NT,AT>::iterator iter)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ iter.assert_valid(this);\r
+ return iter.node()->m_inputs.size();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::input(TYPENAME digraph<NT,AT>::const_iterator iter, unsigned i) const\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ iter.assert_valid(this);\r
+ if (i >= iter.node()->m_inputs.size()) throw std::out_of_range("digraph::input");\r
+ return digraph_arc_iterator<NT,AT, const AT&,const AT*>(iter.node()->m_inputs[i]);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::input(TYPENAME digraph<NT,AT>::iterator iter, unsigned i)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ iter.assert_valid(this);\r
+ if (i >= iter.node()->m_inputs.size()) throw std::out_of_range("digraph::input");\r
+ return digraph_arc_iterator<NT,AT,AT&,AT*>(iter.node()->m_inputs[i]);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ unsigned digraph<NT,AT>::fanout(TYPENAME digraph<NT,AT>::const_iterator iter) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ iter.assert_valid(this);\r
+ return iter.node()->m_outputs.size();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ unsigned digraph<NT,AT>::fanout(TYPENAME digraph<NT,AT>::iterator iter)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ iter.assert_valid(this);\r
+ return iter.node()->m_outputs.size();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::output(TYPENAME digraph<NT,AT>::const_iterator iter, unsigned i) const\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ iter.assert_valid(this);\r
+ if (i >= iter.node()->m_outputs.size()) throw std::out_of_range("digraph::output");\r
+ return digraph_arc_iterator<NT,AT, const AT&,const AT*>(iter.node()->m_outputs[i]);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::output(TYPENAME digraph<NT,AT>::iterator iter, unsigned i)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ iter.assert_valid(this);\r
+ if (i >= iter.node()->m_outputs.size()) throw std::out_of_range("digraph::output");\r
+ return digraph_arc_iterator<NT,AT,AT&,AT*>(iter.node()->m_outputs[i]);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::inputs(TYPENAME digraph<NT,AT>::const_iterator node) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ node.assert_valid(this);\r
+ std::vector<digraph_arc_iterator<NT,AT,const AT&, const AT*> > result;\r
+ for (unsigned i = 0; i < fanin(node); i++)\r
+ result.push_back(input(node,i));\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::inputs(TYPENAME digraph<NT,AT>::iterator node)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ node.assert_valid(this);\r
+ std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > result;\r
+ for (unsigned i = 0; i < fanin(node); i++)\r
+ result.push_back(input(node,i));\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::outputs(TYPENAME digraph<NT,AT>::const_iterator node) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ node.assert_valid(this);\r
+ std::vector<digraph_arc_iterator<NT,AT,const AT&, const AT*> > result;\r
+ for (unsigned i = 0; i < fanout(node); i++)\r
+ result.push_back(output(node,i));\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::outputs(TYPENAME digraph<NT,AT>::iterator node)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ node.assert_valid(this);\r
+ std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > result;\r
+ for (unsigned i = 0; i < fanout(node); i++)\r
+ result.push_back(output(node,i));\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ unsigned digraph<NT,AT>::output_offset(TYPENAME digraph<NT,AT>::const_iterator from,\r
+ TYPENAME digraph<NT,AT>::const_arc_iterator arc) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ from.assert_valid(this);\r
+ arc.assert_valid(this);\r
+ for (unsigned i = 0; i < fanout(from); i++)\r
+ {\r
+ if (output(from,i) == arc)\r
+ return i;\r
+ }\r
+ return digraph<NT,AT>::npos();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ unsigned digraph<NT,AT>::output_offset(TYPENAME digraph<NT,AT>::iterator from,\r
+ TYPENAME digraph<NT,AT>::arc_iterator arc)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ from.assert_valid(this);\r
+ arc.assert_valid(this);\r
+ for (unsigned i = 0; i < fanout(from); i++)\r
+ {\r
+ if (output(from,i) == arc)\r
+ return i;\r
+ }\r
+ return digraph<NT,AT>::npos();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ unsigned digraph<NT,AT>::input_offset(TYPENAME digraph<NT,AT>::const_iterator to,\r
+ TYPENAME digraph<NT,AT>::const_arc_iterator arc) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ to.assert_valid(this);\r
+ arc.assert_valid(this);\r
+ for (unsigned i = 0; i < fanin(to); i++)\r
+ {\r
+ if (input(to,i) == arc)\r
+ return i;\r
+ }\r
+ return digraph<NT,AT>::npos();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ unsigned digraph<NT,AT>::input_offset(TYPENAME digraph<NT,AT>::iterator to,\r
+ TYPENAME digraph<NT,AT>::arc_iterator arc)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ to.assert_valid(this);\r
+ arc.assert_valid(this);\r
+ for (unsigned i = 0; i < fanin(to); i++)\r
+ {\r
+ if (input(to,i) == arc)\r
+ return i;\r
+ }\r
+ return digraph<NT,AT>::npos();\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Basic Arc functions\r
+\r
+ template<typename NT, typename AT>\r
+ bool digraph<NT,AT>::arc_empty(void) const\r
+ {\r
+ return m_arcs_end == 0;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ unsigned digraph<NT,AT>::arc_size(void) const\r
+ {\r
+ unsigned count = 0;\r
+ for (digraph_arc_iterator<NT,AT, const AT&,const AT*> i = arc_begin(); i != arc_end(); i++)\r
+ count++;\r
+ return count;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_insert(TYPENAME digraph<NT,AT>::iterator from,\r
+ TYPENAME digraph<NT,AT>::iterator to,\r
+ const AT& arc_data)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ from.assert_valid(this);\r
+ to.assert_valid(this);\r
+ // create the new arc and link it in to the arc list\r
+ digraph_arc<NT,AT>* new_arc = new digraph_arc<NT,AT>(this, from.node(), to.node(), arc_data);\r
+ if (!m_arcs_end)\r
+ {\r
+ // insert into an empty list\r
+ m_arcs_begin = new_arc;\r
+ m_arcs_end = new_arc;\r
+ }\r
+ else\r
+ {\r
+ // insert at the end of the list\r
+ new_arc->m_prev = m_arcs_end;\r
+ m_arcs_end->m_next = new_arc;\r
+ m_arcs_end = new_arc;\r
+ }\r
+ // add this arc to the inputs and outputs of the end nodes\r
+ from.node()->m_outputs.push_back(new_arc);\r
+ to.node()->m_inputs.push_back(new_arc);\r
+ return digraph_arc_iterator<NT,AT,AT&,AT*>(new_arc);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_erase(TYPENAME digraph<NT,AT>::arc_iterator iter)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ iter.assert_valid(this);\r
+ // first remove this arc's pointers from the from/to nodes\r
+ for (TYPENAME std::vector<digraph_arc<NT,AT>*>::iterator i = iter.node()->m_to->m_inputs.begin(); i != iter.node()->m_to->m_inputs.end(); )\r
+ {\r
+ if (*i == iter.node())\r
+ i = iter.node()->m_to->m_inputs.erase(i);\r
+ else\r
+ i++;\r
+ }\r
+ for (TYPENAME std::vector<digraph_arc<NT,AT>*>::iterator o = iter.node()->m_from->m_outputs.begin(); o != iter.node()->m_from->m_outputs.end(); )\r
+ {\r
+ if (*o == iter.node())\r
+ o = iter.node()->m_from->m_outputs.erase(o);\r
+ else\r
+ o++;\r
+ }\r
+ // now unlink the arc from the list and delete it\r
+ if (iter.node()->m_next)\r
+ iter.node()->m_next->m_prev = iter.node()->m_prev;\r
+ if (iter.node()->m_prev)\r
+ iter.node()->m_prev->m_next = iter.node()->m_next;\r
+ digraph_arc<NT,AT>* next = iter.node()->m_next;\r
+ delete iter.node();\r
+ if (next)\r
+ return digraph_arc_iterator<NT,AT,AT&,AT*>(next);\r
+ else\r
+ return digraph_arc_iterator<NT,AT,AT&,AT*>(this);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ void digraph<NT,AT>::arc_clear(void)\r
+ {\r
+ for (digraph_arc_iterator<NT,AT,AT&,AT*> a = arc_begin(); a != arc_end(); )\r
+ a = arc_erase(a);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::arc_begin(void) const\r
+ {\r
+ if (m_arcs_begin)\r
+ return digraph_arc_iterator<NT,AT, const AT&,const AT*>(m_arcs_begin);\r
+ else\r
+ return digraph_arc_iterator<NT,AT, const AT&,const AT*>(this);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_begin(void)\r
+ {\r
+ if (m_arcs_begin)\r
+ return digraph_arc_iterator<NT,AT,AT&,AT*>(m_arcs_begin);\r
+ else\r
+ return digraph_arc_iterator<NT,AT,AT&,AT*>(this);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::arc_end(void) const\r
+ {\r
+ return digraph_arc_iterator<NT,AT, const AT&,const AT*>(this);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_end(void)\r
+ {\r
+ return digraph_arc_iterator<NT,AT,AT&,AT*>(this);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::arc_from(TYPENAME digraph<NT,AT>::const_arc_iterator iter) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ iter.assert_valid(this);\r
+ return digraph_iterator<NT,AT,const NT&,const NT*>(iter.node()->m_from);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::arc_from(TYPENAME digraph<NT,AT>::arc_iterator iter)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ iter.assert_valid(this);\r
+ return digraph_iterator<NT,AT,NT&,NT*>(iter.node()->m_from);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::arc_to(TYPENAME digraph<NT,AT>::const_arc_iterator iter) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ iter.assert_valid(this);\r
+ return digraph_iterator<NT,AT,const NT&,const NT*>(iter.node()->m_to);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::arc_to(TYPENAME digraph<NT,AT>::arc_iterator iter)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ iter.assert_valid(this);\r
+ return digraph_iterator<NT,AT,NT&,NT*>(iter.node()->m_to);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ void digraph<NT,AT>::arc_move(TYPENAME digraph<NT,AT>::arc_iterator arc,\r
+ TYPENAME digraph<NT,AT>::iterator from,\r
+ TYPENAME digraph<NT,AT>::iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ arc_move_to(arc,to);\r
+ arc_move_from(arc,from);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ void digraph<NT,AT>::arc_move_from(TYPENAME digraph<NT,AT>::arc_iterator arc,\r
+ TYPENAME digraph<NT,AT>::iterator from)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ arc.assert_valid(this);\r
+ from.assert_valid(this);\r
+ for (TYPENAME std::vector<digraph_arc<NT,AT>*>::iterator o = arc.node()->m_from->m_outputs.begin(); o != arc.node()->m_from->m_outputs.end(); )\r
+ {\r
+ if (*o == arc.node())\r
+ o = arc.node()->m_from->m_outputs.erase(o);\r
+ else\r
+ o++;\r
+ }\r
+ from.node()->m_outputs.push_back(arc.node());\r
+ arc.node()->m_from = from.node();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ void digraph<NT,AT>::arc_move_to(TYPENAME digraph<NT,AT>::arc_iterator arc,\r
+ TYPENAME digraph<NT,AT>::iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ arc.assert_valid(this);\r
+ to.assert_valid(this);\r
+ for (TYPENAME std::vector<digraph_arc<NT,AT>*>::iterator i = arc.node()->m_to->m_inputs.begin(); i != arc.node()->m_to->m_inputs.end(); )\r
+ {\r
+ if (*i == arc.node())\r
+ i = arc.node()->m_to->m_inputs.erase(i);\r
+ else\r
+ i++;\r
+ }\r
+ to.node()->m_inputs.push_back(arc.node());\r
+ arc.node()->m_to = to.node();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ void digraph<NT,AT>::arc_flip(TYPENAME digraph<NT,AT>::arc_iterator arc)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ arc_move(arc,arc_to(arc),arc_from(arc));\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Adjacency Algorithms\r
+\r
+ template<typename NT, typename AT>\r
+ bool digraph<NT,AT>::adjacent(TYPENAME digraph<NT,AT>::const_iterator from,\r
+ TYPENAME digraph<NT,AT>::const_iterator to) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return adjacent_arc(from,to) != arc_end();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ bool digraph<NT,AT>::adjacent(TYPENAME digraph<NT,AT>::iterator from,\r
+ TYPENAME digraph<NT,AT>::iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return adjacent_arc(from,to) != arc_end();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::adjacent_arc(TYPENAME digraph<NT,AT>::const_iterator from,\r
+ TYPENAME digraph<NT,AT>::const_iterator to) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ from.assert_valid(this);\r
+ to.assert_valid(this);\r
+ for (unsigned arc = 0; arc < fanout(from); arc++)\r
+ {\r
+ if (arc_to(output(from, arc)) == to)\r
+ return output(from,arc);\r
+ }\r
+ return arc_end();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::adjacent_arc(TYPENAME digraph<NT,AT>::iterator from,\r
+ TYPENAME digraph<NT,AT>::iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return adjacent_arc(from.constify(), to.constify()).deconstify();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::adjacent_arcs(TYPENAME digraph<NT,AT>::const_iterator from,\r
+ TYPENAME digraph<NT,AT>::const_iterator to) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ from.assert_valid(this);\r
+ to.assert_valid(this);\r
+ std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > result;\r
+ for (unsigned arc = 0; arc < fanout(from); arc++)\r
+ {\r
+ if (arc_to(output(from, arc)) == to)\r
+ result.push_back(output(from,arc));\r
+ }\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::adjacent_arcs(TYPENAME digraph<NT,AT>::iterator from,\r
+ TYPENAME digraph<NT,AT>::iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return deconstify_arcs(adjacent_arcs(from.constify(), to.constify()));\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::input_adjacencies(TYPENAME digraph<NT,AT>::const_iterator to) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;\r
+ for (unsigned arc = 0; arc < fanin(to); arc++)\r
+ {\r
+ digraph_iterator<NT,AT,const NT&,const NT*> from = arc_from(input(to, arc));\r
+ if (std::find(result.begin(), result.end(), from) == result.end())\r
+ result.push_back(from);\r
+ }\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::input_adjacencies(TYPENAME digraph<NT,AT>::iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return deconstify_nodes(input_adjacencies(to.constify()));\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::output_adjacencies(TYPENAME digraph<NT,AT>::const_iterator from) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;\r
+ for (unsigned arc = 0; arc < fanout(from); arc++)\r
+ {\r
+ digraph_iterator<NT,AT,const NT&,const NT*> to = arc_to(output(from, arc));\r
+ if (find(result.begin(), result.end(), to) == result.end())\r
+ result.push_back(to);\r
+ }\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::output_adjacencies(TYPENAME digraph<NT,AT>::iterator from)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return deconstify_nodes(output_adjacencies(from.constify()));\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Topographical Sort Algorithms\r
+\r
+ template<typename NT, typename AT>\r
+ std::pair<TYPENAME digraph<NT,AT>::const_node_vector, TYPENAME digraph<NT,AT>::const_arc_vector>\r
+ digraph<NT,AT>::sort(TYPENAME digraph<NT,AT>::arc_select_fn select) const\r
+ {\r
+ std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;\r
+ std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > errors;\r
+ // build a map containing the number of fanins to each node that must be visited before this one\r
+ std::map<digraph_iterator<NT,AT,const NT&,const NT*>,unsigned> fanin_map;\r
+ for (digraph_iterator<NT,AT,const NT&,const NT*> n = begin(); n != end(); n++)\r
+ {\r
+ unsigned predecessors = 0;\r
+ // only count predecessors connected by selected arcs\r
+ for (unsigned f = 0; f < fanin(n); f++)\r
+ {\r
+ digraph_arc_iterator<NT,AT, const AT&,const AT*> input_arc = input(n,f);\r
+ digraph_iterator<NT,AT,const NT&,const NT*> predecessor = arc_from(input_arc);\r
+ if (!select || select(*this,input_arc))\r
+ predecessors++;\r
+ }\r
+ if (predecessors == 0)\r
+ {\r
+ result.push_back(n);\r
+ }\r
+ else\r
+ {\r
+ fanin_map[n] = predecessors;\r
+ }\r
+ }\r
+ // main algorithm applies the topographical sort repeatedly. For a DAG, it\r
+ // will complete first time. However, with backward arcs, the first\r
+ // iteration will fail. The algorithm then tries breaking random arcs to try\r
+ // to get an ordering.\r
+ for(unsigned i = 0; !fanin_map.empty(); )\r
+ {\r
+ // now visit each node in traversal order, decrementing the fanin count of\r
+ // all successors. As each successor's fanin count goes to zero, it is\r
+ // appended to the result.\r
+ for (; i < result.size(); i++)\r
+ {\r
+ // Note: dereferencing gives us a node iterator\r
+ digraph_iterator<NT,AT,const NT&,const NT*> current = result[i];\r
+ for (unsigned f = 0; f < fanout(current); f++)\r
+ {\r
+ // only consider successors connected by selected arcs\r
+ digraph_arc_iterator<NT,AT, const AT&,const AT*> output_arc = output(current, f);\r
+ digraph_iterator<NT,AT,const NT&,const NT*> successor = arc_to(output_arc);\r
+ if (!select || select(*this,output_arc))\r
+ {\r
+ // don't consider arcs that have been eliminated to break a loop\r
+ if (fanin_map.find(successor) != fanin_map.end())\r
+ {\r
+ --fanin_map[successor];\r
+ if ((fanin_map[successor]) == 0)\r
+ {\r
+ result.push_back(successor);\r
+ fanin_map.erase(fanin_map.find(successor));\r
+ }\r
+ }\r
+ }\r
+ }\r
+ }\r
+ if (!fanin_map.empty())\r
+ {\r
+ // there must be backward arcs preventing completion\r
+ // try removing arcs from the sort to get a partial ordering containing all the nodes\r
+\r
+ // select an arc that is still relevant to the sort and break it\r
+ // first select a node that has non-zero fanin and its predecessor that has non-zero fanin\r
+ digraph_iterator<NT,AT,const NT&,const NT*> stuck_node = fanin_map.begin()->first;\r
+ for (unsigned f = 0; f < fanin(stuck_node); f++)\r
+ {\r
+ // now successively remove input arcs that are still part of the sort until the fanin reduces to zero\r
+ // first find a relevant arc - this must be a selected arc that has not yet been traversed by the first half of the algorithm\r
+ digraph_arc_iterator<NT,AT, const AT&,const AT*> input_arc = input(stuck_node, f);\r
+ if (!select || select(*this,input_arc))\r
+ {\r
+ digraph_iterator<NT,AT,const NT&,const NT*> predecessor = arc_from(input_arc);\r
+ if (fanin_map.find(predecessor) != fanin_map.end())\r
+ {\r
+ // found the right combination - remove this arc and then drop out of the fanin loop to restart the outer sort loop\r
+ errors.push_back(input_arc);\r
+ --fanin_map[stuck_node];\r
+ if ((fanin_map[stuck_node]) == 0)\r
+ {\r
+ result.push_back(stuck_node);\r
+ fanin_map.erase(fanin_map.find(stuck_node));\r
+ break;\r
+ }\r
+ }\r
+ }\r
+ }\r
+ }\r
+ }\r
+ return std::make_pair(result,errors);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ std::pair<TYPENAME digraph<NT,AT>::node_vector, TYPENAME digraph<NT,AT>::arc_vector>\r
+ digraph<NT,AT>::sort(TYPENAME digraph<NT,AT>::arc_select_fn select)\r
+ {\r
+ std::pair<std::vector<digraph_iterator<NT,AT,const NT&,const NT*> >,\r
+ std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > const_result =\r
+ const_cast<const digraph<NT,AT>*>(this)->sort(select);\r
+\r
+ std::pair<std::vector<digraph_iterator<NT,AT,NT&,NT*> >,\r
+ std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > > result =\r
+ std::make_pair(deconstify_nodes(const_result.first),deconstify_arcs(const_result.second));\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::dag_sort(TYPENAME digraph<NT,AT>::arc_select_fn select) const\r
+ {\r
+ std::pair<std::vector<digraph_iterator<NT,AT,const NT&,const NT*> >,\r
+ std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result = sort(select);\r
+ if (result.second.empty()) return result.first;\r
+ return std::vector<digraph_iterator<NT,AT,const NT&,const NT*> >();\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::dag_sort(TYPENAME digraph<NT,AT>::arc_select_fn select)\r
+ {\r
+ return deconstify_nodes(const_cast<const digraph<NT,AT>*>(this)->dag_sort(select));\r
+ }\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Path Algorithms\r
+\r
+ template<typename NT, typename AT>\r
+ bool digraph<NT,AT>::path_exists_r(TYPENAME digraph<NT,AT>::const_iterator from,\r
+ TYPENAME digraph<NT,AT>::const_iterator to,\r
+ TYPENAME digraph<NT,AT>::const_iterator_set& visited,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ // Recursive part of the digraph::path_exists function. This is based on a\r
+ // depth first search algorithm and stops the moment it finds a path\r
+ // regardless of its length. Simply traverse every output and recurse on that\r
+ // node until we find the to node or run out of things to recurse on. However,\r
+ // to avoid infinite recursion due to cycles in the graph, I need to maintain\r
+ // a set of visited nodes. The visited set is updated when a candidate is\r
+ // found but tested before the recursion on the candidate so that the number of\r
+ // function calls is minimised.\r
+ for (unsigned i = 0; i < fanout(from); i++)\r
+ {\r
+ digraph_arc_iterator<NT,AT, const AT&,const AT*> arc = output(from,i);\r
+ if (!select || select(*this, arc))\r
+ {\r
+ digraph_iterator<NT,AT,const NT&,const NT*> node = arc_to(arc);\r
+ // if the node is the target, return immediately\r
+ if (node == to) return true;\r
+ // update the visited set and give up if the insert fails, which indicates that the node has already been visited\r
+ if (!(visited.insert(node).second)) return false;\r
+ // now recurse - a path exists from from to to if a path exists from an adjacent node to to\r
+ if (path_exists_r(node,to,visited,select)) return true;\r
+ }\r
+ }\r
+ return false;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ bool digraph<NT,AT>::path_exists(TYPENAME digraph<NT,AT>::const_iterator from,\r
+ TYPENAME digraph<NT,AT>::const_iterator to, \r
+ TYPENAME digraph<NT,AT>::arc_select_fn select) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ // set up the recursion with its initial visited set and then recurse\r
+ std::set<digraph_iterator<NT,AT,const NT&,const NT*> > visited;\r
+ visited.insert(from);\r
+ return path_exists_r(from, to, visited, select);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ bool digraph<NT,AT>::path_exists(TYPENAME digraph<NT,AT>::iterator from,\r
+ TYPENAME digraph<NT,AT>::iterator to,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return path_exists(from.constify(), to.constify(), select);\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ void digraph<NT,AT>::all_paths_r(TYPENAME digraph<NT,AT>::const_iterator from,\r
+ TYPENAME digraph<NT,AT>::const_iterator to,\r
+ TYPENAME digraph<NT,AT>::const_arc_vector& so_far,\r
+ TYPENAME digraph<NT,AT>::const_path_vector& result,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ // This is the recursive part of the all_paths function. The field so_far\r
+ // contains the path so far so that when 'to' is reached, the path is\r
+ // complete. It serves the same purpose as the visited set in the path_exists\r
+ // function except that it also preserves the path order. It also serves the\r
+ // purpose of detecting cycles and thus stopping infinite recursion. Every\r
+ // time the recursion reaches the to node, a copy of so_far is appended to the\r
+ // path set.\r
+ for (unsigned i = 0; i < fanout(from); i++)\r
+ {\r
+ digraph_arc_iterator<NT,AT, const AT&,const AT*> candidate = output(from,i);\r
+ // assert_valid that the arc is selected and then assert_valid that the candidate has not\r
+ // been visited on this path and only allow further recursion if it hasn't\r
+ if ((!select || select(*this, candidate)) && std::find(so_far.begin(), so_far.end(), candidate) == so_far.end())\r
+ {\r
+ // extend the path tracing the route to this arc\r
+ so_far.push_back(candidate);\r
+ // if the candidate arc points to the target, update the result set and prevent further recursion, otherwise recurse\r
+ if (arc_to(candidate) == to)\r
+ result.push_back(so_far);\r
+ else\r
+ all_paths_r(arc_to(candidate),to,so_far,result,select);\r
+ so_far.pop_back();\r
+ }\r
+ }\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_path_vector \r
+ digraph<NT,AT>::all_paths(TYPENAME digraph<NT,AT>::const_iterator from, \r
+ TYPENAME digraph<NT,AT>::const_iterator to,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ // set up the recursion with empty data fields and then recurse\r
+ std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result;\r
+ std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > so_far;\r
+ all_paths_r(from, to, so_far, result, select);\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::path_vector\r
+ digraph<NT,AT>::all_paths(TYPENAME digraph<NT,AT>::iterator from, \r
+ TYPENAME digraph<NT,AT>::iterator to,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return deconstify_paths(all_paths(from.constify(), to.constify(), select));\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ void digraph<NT,AT>::reachable_nodes_r(TYPENAME digraph<NT,AT>::const_iterator from,\r
+ TYPENAME digraph<NT,AT>::const_iterator_set& visited,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ // The recursive part of the reachable_nodes function.\r
+ // This is a depth-first traversal again but this time it carries on to find all the reachable nodes\r
+ // Just keep recursing on all the adjacent nodes of each node, skipping already visited nodes to avoid cycles\r
+ for (unsigned i = 0; i < fanout(from); i++)\r
+ {\r
+ digraph_arc_iterator<NT,AT, const AT&,const AT*> arc = output(from,i);\r
+ if (!select || select(*this,arc))\r
+ {\r
+ digraph_iterator<NT,AT,const NT&,const NT*> candidate = arc_to(arc);\r
+ if (visited.insert(candidate).second)\r
+ reachable_nodes_r(candidate,visited,select);\r
+ }\r
+ }\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_node_vector\r
+ digraph<NT,AT>::reachable_nodes(TYPENAME digraph<NT,AT>::const_iterator from,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ // seed the recursion, marking the starting node as already visited\r
+ std::set<digraph_iterator<NT,AT,const NT&,const NT*> > visited;\r
+ visited.insert(from);\r
+ reachable_nodes_r(from, visited, select);\r
+ // convert the visited set into the required output form\r
+ // exclude the starting node\r
+ std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;\r
+ for (TYPENAME std::set<digraph_iterator<NT,AT,const NT&,const NT*> >::iterator i = visited.begin(); i != visited.end(); i++)\r
+ if (*i != from)\r
+ result.push_back(*i);\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::node_vector\r
+ digraph<NT,AT>::reachable_nodes(TYPENAME digraph<NT,AT>::iterator from,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return deconstify_nodes(reachable_nodes(from.constify(), select));\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ void digraph<NT,AT>::reaching_nodes_r(TYPENAME digraph<NT,AT>::const_iterator to,\r
+ TYPENAME digraph<NT,AT>::const_iterator_set& visited,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ // The recursive part of the reaching_nodes function.\r
+ // Just like the reachable_nodes_r function but it goes backwards\r
+ for (unsigned i = 0; i < fanin(to); i++)\r
+ {\r
+ digraph_arc_iterator<NT,AT, const AT&,const AT*> arc = input(to,i);\r
+ if (!select || select(*this,arc))\r
+ {\r
+ digraph_iterator<NT,AT,const NT&,const NT*> candidate = arc_from(input(to,i));\r
+ if (visited.insert(candidate).second)\r
+ reaching_nodes_r(candidate,visited,select);\r
+ }\r
+ }\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_node_vector\r
+ digraph<NT,AT>::reaching_nodes(TYPENAME digraph<NT,AT>::const_iterator to,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ // seed the recursion, marking the starting node as already visited\r
+ std::set<digraph_iterator<NT,AT,const NT&,const NT*> > visited;\r
+ visited.insert(to);\r
+ reaching_nodes_r(to,visited,select);\r
+ // convert the visited set into the required output form\r
+ // exclude the end node\r
+ std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;\r
+ for (TYPENAME std::set<digraph_iterator<NT,AT,const NT&,const NT*> >::iterator i = visited.begin(); i != visited.end(); i++)\r
+ if (*i != to)\r
+ result.push_back(*i);\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::node_vector\r
+ digraph<NT,AT>::reaching_nodes(TYPENAME digraph<NT,AT>::iterator to,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return deconstify_nodes(reaching_nodes(to.constify(),select));\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Shortest Path Algorithms\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_arc_vector\r
+ digraph<NT,AT>::shortest_path(TYPENAME digraph<NT,AT>::const_iterator from,\r
+ TYPENAME digraph<NT,AT>::const_iterator to,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > paths = all_paths(from,to,select);\r
+ std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > shortest;\r
+ for (TYPENAME std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > >::iterator i = paths.begin(); i != paths.end(); i++)\r
+ if (shortest.empty() || i->size() < shortest.size())\r
+ shortest = *i;\r
+ return shortest;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::arc_vector\r
+ digraph<NT,AT>::shortest_path(TYPENAME digraph<NT,AT>::iterator from, \r
+ TYPENAME digraph<NT,AT>::iterator to,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return deconstify_arcs(shortest_path(from.constify(),to.constify(),select));\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::const_path_vector\r
+ digraph<NT,AT>::shortest_paths(TYPENAME digraph<NT,AT>::const_iterator from,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ from.assert_valid(this);\r
+ // This is an unweighted shortest path algorithm based on the algorithm from\r
+ // Weiss's book. This is essentially a breadth-first traversal or graph\r
+ // colouring algorithm. It is an iterative algorithm, so no recursion here! It\r
+ // works by creating a node queue initialised with the starting node. It then\r
+ // consumes the queue from front to back. For each node, it finds the\r
+ // successors and appends them to the queue. If a node is already 'known' it\r
+ // is not added - this avoids cycles. Thus the queue insert ordering\r
+ // represents the breadth-first ordering. On the way it creates a map of\r
+ // visited nodes. This is a map not a set because it also stores the arc that\r
+ // nominated this node as a shortest path. The full path can then be recreated\r
+ // from the map by just walking back through the predecessors. The depth (or\r
+ // colour) can be determined by the path length.\r
+ std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result;\r
+ // initialise the iteration by creating a queue and adding the start node\r
+ std::deque<digraph_iterator<NT,AT,const NT&,const NT*> > nodes;\r
+ nodes.push_back(from);\r
+ // Create a map to store the set of known nodes mapped to their predecessor\r
+ // arcs. Initialise it with the current node, which has no predecessor. Note\r
+ // that the algorithm uses the feature of digraph iterators that they can be\r
+ // null iterators and that all null iterators are equal.\r
+ typedef std::map<digraph_iterator<NT,AT,const NT&,const NT*>,\r
+ digraph_arc_iterator<NT,AT,const AT&,const AT*> > known_map;\r
+ known_map known;\r
+ known.insert(std::make_pair(from,digraph_arc_iterator<NT,AT, const AT&,const AT*>()));\r
+ // now the iterative part of the algorithm\r
+ while(!nodes.empty())\r
+ {\r
+ // pop the queue to get the next node to process - unfortunately the STL\r
+ // deque::pop does not return the popped value\r
+ digraph_iterator<NT,AT,const NT&,const NT*> current = nodes.front();\r
+ nodes.pop_front();\r
+ // now visit all the successors\r
+ for (unsigned i = 0; i < fanout(current); i++)\r
+ {\r
+ digraph_arc_iterator<NT,AT, const AT&,const AT*> next_arc = output(current,i);\r
+ // assert_valid whether the successor arc is a selected arc and can be part of a path\r
+ if (!select || select(*this,next_arc))\r
+ {\r
+ digraph_iterator<NT,AT,const NT&,const NT*> next = arc_to(next_arc);\r
+ // Discard any successors that are known because to be known already they\r
+ // must have another shorter path. Otherwise add the successor node to the\r
+ // queue to be visited later. To minimise the overhead of map lookup I use\r
+ // the usual trick of trying to insert the node and determining whether\r
+ // the node was known by the success or failure of the insertion - this is\r
+ // a Good STL Trick (TM).\r
+ if (known.insert(std::make_pair(next,next_arc)).second)\r
+ nodes.push_back(next);\r
+ }\r
+ }\r
+ }\r
+ // The map contains the results as an unordered set of nodes, mapped to their\r
+ // predecessor arcs and weight. This now needs to be converted into a set of\r
+ // paths. This is done by starting with a node from the map, finding its\r
+ // predecessor arc and therefore its predecessor node, looking that up in the\r
+ // map to find its predecessor and so on until the start node is reached (it\r
+ // has a null predecessor). Note that the known set includes the from node\r
+ // which does not generate a path.\r
+ for (TYPENAME known_map::iterator i = known.begin(); i != known.end(); i++)\r
+ {\r
+ if (i->first != from)\r
+ {\r
+ const_arc_vector this_path;\r
+ for (TYPENAME known_map::iterator node = i; \r
+ node->second.valid(); \r
+ node = known.find(arc_from(node->second)))\r
+ this_path.insert(this_path.begin(),node->second);\r
+ result.push_back(this_path);\r
+ }\r
+ }\r
+ return result;\r
+ }\r
+\r
+ template<typename NT, typename AT>\r
+ TYPENAME digraph<NT,AT>::path_vector\r
+ digraph<NT,AT>::shortest_paths(TYPENAME digraph<NT,AT>::iterator from,\r
+ TYPENAME digraph<NT,AT>::arc_select_fn select)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return deconstify_paths(shortest_paths(from.constify(),select));\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
--- /dev/null
+#ifndef STLPLUS_EXCEPTIONS\r
+#define STLPLUS_EXCEPTIONS\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+// The set of general exceptions thrown by STLplus components\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include "containers_fixes.hpp"\r
+#include <stdexcept>\r
+#include <string>\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Thrown if a pointer or an iterator is dereferenced when it is null\r
+\r
+ class null_dereference : public std::logic_error\r
+ {\r
+ public:\r
+ null_dereference(const std::string& description) throw() :\r
+ std::logic_error(std::string("stlplus::null_dereference: ") + description) {}\r
+ ~null_dereference(void) throw() {}\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Thrown if an iterator is dereferenced when it is pointing to the end element\r
+\r
+ class end_dereference : public std::logic_error\r
+ {\r
+ public:\r
+ end_dereference(const std::string& description) throw() :\r
+ std::logic_error("stlplus::end_dereference: " + description) {}\r
+ ~end_dereference(void) throw() {}\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Thrown if an iterator is used with the wrong container. In other words, an\r
+ // iterator is created as a pointer to a sub-object within a container. If\r
+ // that iterator is then used with a different container, this exception is\r
+ // thrown.\r
+\r
+ class wrong_object : public std::logic_error\r
+ {\r
+ public:\r
+ wrong_object(const std::string& description) throw() :\r
+ std::logic_error("stlplus::wrong_object: " + description) {}\r
+ ~wrong_object(void) throw() {}\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Thrown if an attempt is made to copy an object that is uncopyable\r
+\r
+ class illegal_copy : public std::logic_error\r
+ {\r
+ public:\r
+ illegal_copy(const std::string& description) throw() :\r
+ std::logic_error("stlplus::illegal_copy: " + description) {}\r
+ ~illegal_copy(void) throw() {}\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
+#endif\r
--- /dev/null
+#ifndef STLPLUS_FOURSOME\r
+#define STLPLUS_FOURSOME\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton, from an original by Dan Milton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+// The next in the series pair->triple->foursome\r
+\r
+// Originally called quadruple but that clashed (as did quad) with system\r
+// libraries on some operating systems\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include "containers_fixes.hpp"\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // the foursome class\r
+\r
+ template<typename T1, typename T2, typename T3, typename T4>\r
+ struct foursome\r
+ {\r
+ typedef T1 first_type;\r
+ typedef T2 second_type;\r
+ typedef T3 third_type;\r
+ typedef T4 fourth_type;\r
+\r
+ T1 first;\r
+ T2 second;\r
+ T3 third;\r
+ T4 fourth;\r
+\r
+ foursome(void);\r
+ foursome(const T1& p1, const T2& p2, const T3& p3, const T4& p4);\r
+ foursome(const foursome<T1,T2,T3,T4>& t2);\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // creation\r
+\r
+ template<typename T1, typename T2, typename T3, typename T4>\r
+ foursome<T1,T2,T3,T4> make_foursome(const T1& first, const T2& second, const T3& third, const T4& fourth);\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // comparison\r
+\r
+ template<typename T1, typename T2, typename T3, typename T4>\r
+ bool operator == (const foursome<T1,T2,T3,T4>& left, const foursome<T1,T2,T3,T4>& right);\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
+#include "foursome.tpp"\r
+#endif\r
--- /dev/null
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton, from an original by Dan Milton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // the foursome class\r
+\r
+ template<typename T1, typename T2, typename T3, typename T4>\r
+ foursome<T1,T2,T3,T4>::foursome(void) :\r
+ first(), second(), third(), fourth()\r
+ {\r
+ }\r
+\r
+ template<typename T1, typename T2, typename T3, typename T4>\r
+ foursome<T1,T2,T3,T4>::foursome(const T1& p1, const T2& p2, const T3& p3, const T4& p4) :\r
+ first(p1), second(p2), third(p3), fourth(p4)\r
+ {\r
+ }\r
+\r
+ template<typename T1, typename T2, typename T3, typename T4>\r
+ foursome<T1,T2,T3,T4>::foursome(const foursome<T1,T2,T3,T4>& t2) :\r
+ first(t2.first), second(t2.second), third(t2.third), fourth(t2.fourth)\r
+ {\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // creation\r
+\r
+ template<typename T1, typename T2, typename T3, typename T4>\r
+ foursome<T1,T2,T3,T4> make_foursome(const T1& first, const T2& second, const T3& third, const T4& fourth)\r
+ {\r
+ return foursome<T1,T2,T3,T4>(first,second,third,fourth);\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // comparison\r
+\r
+ template<typename T1, typename T2, typename T3, typename T4>\r
+ bool operator == (const foursome<T1,T2,T3,T4>& left, const foursome<T1,T2,T3,T4>& right)\r
+ {\r
+ // foursomes are equal if all elements are equal\r
+ return \r
+ left.first == right.first && \r
+ left.second == right.second && \r
+ left.third == right.third &&\r
+ left.fourth == right.fourth;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
--- /dev/null
+#ifndef STLPLUS_HASH\r
+#define STLPLUS_HASH\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+// A chained hash table using STL semantics\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include "containers_fixes.hpp"\r
+#include "exceptions.hpp"\r
+#include "safe_iterator.hpp"\r
+#include <map>\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // internals\r
+\r
+ template<typename K, typename T, class H, class E> class hash;\r
+ template<typename K, typename T, class H, class E> class hash_element;\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // iterator class\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ class hash_iterator : public safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >\r
+ {\r
+ public:\r
+ friend class hash<K,T,H,E>;\r
+\r
+ // local type definitions\r
+ // an iterator points to a value whilst a const_iterator points to a const value\r
+ typedef V value_type;\r
+ typedef hash_iterator<K,T,H,E,std::pair<const K,T> > iterator;\r
+ typedef hash_iterator<K,T,H,E,const std::pair<const K,T> > const_iterator;\r
+ typedef hash_iterator<K,T,H,E,V> this_iterator;\r
+ typedef V& reference;\r
+ typedef V* pointer;\r
+\r
+ // constructor to create a null iterator - you must assign a valid value to this iterator before using it\r
+ // any attempt to dereference or use a null iterator is an error\r
+ // the only valid thing you can do is assign an iterator to it\r
+ hash_iterator(void);\r
+ ~hash_iterator(void);\r
+\r
+ // Type conversion methods allow const_iterator and iterator to be converted\r
+ // convert an iterator/const_iterator to a const_iterator\r
+ const_iterator constify(void) const;\r
+ // convert an iterator/const_iterator to an iterator\r
+ iterator deconstify(void) const;\r
+\r
+ // increment operators used to step through the set of all values in a hash\r
+ // it is only legal to increment a valid iterator\r
+ // there's no decrement - I've only implemented this as a unidirectional iterator\r
+ // pre-increment\r
+ this_iterator& operator ++ (void)\r
+ throw(null_dereference,end_dereference);\r
+ // post-increment\r
+ this_iterator operator ++ (int)\r
+ throw(null_dereference,end_dereference);\r
+\r
+ // test useful for testing whether iteration has completed\r
+ bool operator == (const this_iterator& r) const;\r
+ bool operator != (const this_iterator& r) const;\r
+ bool operator < (const this_iterator& r) const;\r
+\r
+ // access the value - a const_iterator gives you a const value, an iterator a non-const value\r
+ // it is illegal to dereference an invalid (i.e. null or end) iterator\r
+ reference operator*(void) const\r
+ throw(null_dereference,end_dereference);\r
+ pointer operator->(void) const\r
+ throw(null_dereference,end_dereference);\r
+\r
+ private:\r
+ friend class hash_element<K,T,H,E>;\r
+\r
+ // constructor used by hash to create a non-null iterator\r
+ // you cannot create a valid iterator except by calling a hash method that returns one\r
+ explicit hash_iterator(hash_element<K,T,H,E>* element);\r
+ // constructor used to create an end iterator\r
+ explicit hash_iterator(const hash<K,T,H,E>* owner);\r
+ // used to create an alias of an iterator\r
+ explicit hash_iterator(const safe_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> >& iterator);\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Hash class\r
+ // K = key type\r
+ // T = value type\r
+ // H = hash function object with the profile 'unsigned H(const K&)'\r
+ // E = equal function object with profile 'bool E(const K&, const K&)' defaults to equal_to which in turn calls '=='\r
+\r
+ template<typename K, typename T, class H, class E = std::equal_to<K> >\r
+ class hash\r
+ {\r
+ public:\r
+ typedef unsigned size_type;\r
+ typedef K key_type;\r
+ typedef T data_type;\r
+ typedef T mapped_type;\r
+ typedef std::pair<const K, T> value_type;\r
+ typedef hash_iterator<K,T,H,E,value_type> iterator;\r
+ typedef hash_iterator<K,T,H,E,const value_type> const_iterator;\r
+\r
+ // construct a hash table with specified number of bins\r
+ // the default 0 bins means leave it to the table to decide\r
+ // specifying 0 bins also enables auto-rehashing, otherwise auto-rehashing defaults off\r
+ hash(unsigned bins = 0);\r
+ ~hash(void);\r
+\r
+ // copy and equality copy the data elements but not the size of the copied table\r
+ hash(const hash&);\r
+ hash& operator = (const hash&);\r
+\r
+ // test for an empty table and for the size of a table\r
+ // efficient because the size is stored separately from the table contents\r
+ bool empty(void) const;\r
+ unsigned size(void) const;\r
+\r
+ // test for equality - two hashes are equal if they contain equal values\r
+ bool operator == (const hash&) const;\r
+ bool operator != (const hash&) const;\r
+\r
+ // switch auto-rehash on\r
+ void auto_rehash(void);\r
+ // switch auto-rehash off\r
+ void manual_rehash(void);\r
+ // force a rehash now\r
+ // default of 0 means implement built-in size calculation for rehashing (recommended - it doubles the number of bins)\r
+ void rehash(unsigned bins = 0);\r
+ // test the loading ratio, which is the size divided by the number of bins\r
+ // use this if you are doing your own rehashing\r
+ // the recommendation is to double the bins when the loading exceeds 0.5 which is what auto-rehashing does\r
+ float loading(void) const;\r
+\r
+ // test for the presence of a key\r
+ bool present(const K& key) const;\r
+ // provide map equivalent key count function (0 or 1, as not a multimap)\r
+ size_type count(const K& key) const;\r
+\r
+ // insert a new key/data pair - replaces any previous value for this key\r
+ iterator insert(const K& key, const T& data);\r
+ // insert a copy of the pair into the table (std::map compatible)\r
+ std::pair<iterator, bool> insert(const value_type& value);\r
+ // insert a new key and return the iterator so that the data can be filled in\r
+ iterator insert(const K& key);\r
+\r
+ // remove a key/data pair from the hash table\r
+ bool erase(const K& key);\r
+ // remove all elements from the hash table\r
+ void erase(void);\r
+ // provide the std::map equivalent clear function\r
+ void clear(void);\r
+\r
+ // find a key and return an iterator to it\r
+ // The iterator is like a pointer to a pair<const K,T>\r
+ // end() is returned if the find fails\r
+ const_iterator find(const K& key) const;\r
+ iterator find(const K& key);\r
+\r
+ // returns the data corresponding to the key\r
+ // const version is used for const hashes and cannot change the hash, so failure causes an exception\r
+ // non-const version is for non-const hashes and is like map - it creates a new key/data pair if find fails\r
+ const T& operator[] (const K& key) const throw(std::out_of_range);\r
+ T& operator[] (const K& key);\r
+\r
+ // iterators allow the hash table to be traversed\r
+ // iterators remain valid unless an item is removed or unless a rehash happens\r
+ const_iterator begin(void) const;\r
+ iterator begin(void);\r
+ const_iterator end(void) const;\r
+ iterator end(void);\r
+\r
+ // internals\r
+ private:\r
+ friend class hash_element<K,T,H,E>;\r
+ friend class hash_iterator<K,T,H,E,std::pair<const K,T> >;\r
+ friend class hash_iterator<K,T,H,E,const std::pair<const K,T> >;\r
+\r
+ unsigned m_rehash;\r
+ unsigned m_bins;\r
+ unsigned m_size;\r
+ hash_element<K,T,H,E>** m_values;\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
+#include "hash.tpp"\r
+#endif\r
--- /dev/null
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // the element stored in the hash\r
+\r
+ template<typename K, typename T, typename H, typename E>\r
+ class hash_element\r
+ {\r
+ public:\r
+ master_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> > m_master;\r
+ std::pair<const K, T> m_value;\r
+ hash_element<K,T,H,E>* m_next;\r
+ unsigned m_hash;\r
+\r
+ hash_element(const hash<K,T,H,E>* owner, const K& key, const T& data, unsigned hash) : \r
+ m_master(owner,this), m_value(key,data), m_next(0), m_hash(hash) \r
+ {\r
+ }\r
+\r
+ hash_element(const hash<K,T,H,E>* owner, const std::pair<const K,T>& value, unsigned hash) : \r
+ m_master(owner,this), m_value(value), m_next(0), m_hash(hash) \r
+ {\r
+ }\r
+\r
+ ~hash_element(void)\r
+ {\r
+ m_next = 0;\r
+ m_hash = 0;\r
+ }\r
+\r
+ const hash<K,T,H,E>* owner(void) const\r
+ {\r
+ return m_master.owner();\r
+ }\r
+\r
+ // generate the bin number from the hash value and the owner's number of bins\r
+ unsigned bin(void) const\r
+ {\r
+ return m_hash % (owner()->m_bins);\r
+ }\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // iterator\r
+\r
+ // null constructor\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ hash_iterator<K,T,H,E,V>::hash_iterator(void)\r
+ {\r
+ }\r
+\r
+ // non-null constructor used from within the hash to construct a valid iterator\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ hash_iterator<K,T,H,E,V>::hash_iterator(hash_element<K,T,H,E>* element) :\r
+ safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(element->m_master)\r
+ {\r
+ }\r
+\r
+ // constructor used to create an end iterator\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ hash_iterator<K,T,H,E,V>::hash_iterator(const hash<K,T,H,E>* owner) :\r
+ safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(owner)\r
+ {\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ hash_iterator<K,T,H,E,V>::hash_iterator(const safe_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> >& iterator) :\r
+ safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(iterator)\r
+ {\r
+ }\r
+\r
+ // destructor\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ hash_iterator<K,T,H,E,V>::~hash_iterator(void)\r
+ {\r
+ }\r
+\r
+ // mode conversions\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ TYPENAME hash_iterator<K,T,H,E,V>::const_iterator hash_iterator<K,T,H,E,V>::constify(void) const\r
+ {\r
+ return hash_iterator<K,T,H,E,const std::pair<const K,T> >(*this);\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ TYPENAME hash_iterator<K,T,H,E,V>::iterator hash_iterator<K,T,H,E,V>::deconstify(void) const\r
+ {\r
+ return hash_iterator<K,T,H,E,std::pair<const K,T> >(*this);\r
+ }\r
+\r
+ // increment operator looks for the next element in the table\r
+ // if there isn't one, then this becomes an end() iterator with m_bin = m_bins\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ TYPENAME hash_iterator<K,T,H,E,V>::this_iterator& hash_iterator<K,T,H,E,V>::operator ++ (void)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ this->assert_valid();\r
+ if (this->node()->m_next)\r
+ set(this->node()->m_next->m_master);\r
+ else\r
+ {\r
+ // failing that, subsequent hash values are tried until either an element is found or there are no more bins\r
+ // in which case it becomes an end() iterator\r
+ hash_element<K,T,H,E>* element = 0;\r
+ unsigned current_bin = this->node()->bin();\r
+ for(current_bin++; !element && (current_bin < this->owner()->m_bins); current_bin++)\r
+ element = this->owner()->m_values[current_bin];\r
+ if (element)\r
+ set(element->m_master);\r
+ else\r
+ this->set_end();\r
+ }\r
+ return *this;\r
+ }\r
+\r
+ // post-increment is defined in terms of pre-increment\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ TYPENAME hash_iterator<K,T,H,E,V>::this_iterator hash_iterator<K,T,H,E,V>::operator ++ (int)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ hash_iterator<K,T,H,E,V> old(*this);\r
+ ++(*this);\r
+ return old;\r
+ }\r
+\r
+ // two iterators are equal if they point to the same element\r
+ // both iterators must be non-null and belong to the same table\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ bool hash_iterator<K,T,H,E,V>::operator == (const hash_iterator<K,T,H,E,V>& r) const\r
+ {\r
+ return equal(r);\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ bool hash_iterator<K,T,H,E,V>::operator != (const hash_iterator<K,T,H,E,V>& r) const\r
+ {\r
+ return !operator==(r);\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ bool hash_iterator<K,T,H,E,V>::operator < (const hash_iterator<K,T,H,E,V>& r) const\r
+ {\r
+ return compare(r) < 0;\r
+ }\r
+\r
+ // iterator dereferencing is only legal on a non-null iterator\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ V& hash_iterator<K,T,H,E,V>::operator*(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ this->assert_valid();\r
+ return this->node()->m_value;\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E, typename V>\r
+ V* hash_iterator<K,T,H,E,V>::operator->(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ return &(operator*());\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // hash\r
+\r
+ // totally arbitrary initial size used for auto-rehashed tables\r
+ static unsigned hash_default_bins = 127;\r
+\r
+ // constructor\r
+ // tests whether the user wants auto-rehash\r
+ // sets the rehash point to be a loading of 1.0 by setting it to the number of bins\r
+ // uses the user's size unless this is zero, in which case implement the default\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ hash<K,T,H,E>::hash(unsigned bins) :\r
+ m_rehash(bins), m_bins(bins > 0 ? bins : hash_default_bins), m_size(0), m_values(0)\r
+ {\r
+ m_values = new hash_element<K,T,H,E>*[m_bins];\r
+ for (unsigned i = 0; i < m_bins; i++)\r
+ m_values[i] = 0;\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ hash<K,T,H,E>::~hash(void)\r
+ {\r
+ // delete all the elements\r
+ clear();\r
+ // and delete the data structure\r
+ delete[] m_values;\r
+ m_values = 0;\r
+ }\r
+\r
+ // as usual, implement the copy constructor i.t.o. the assignment operator\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ hash<K,T,H,E>::hash(const hash<K,T,H,E>& right) :\r
+ m_rehash(right.m_rehash), m_bins(right.m_bins), m_size(0), m_values(0)\r
+ {\r
+ m_values = new hash_element<K,T,H,E>*[right.m_bins];\r
+ // copy the rehash behaviour as well as the size\r
+ for (unsigned i = 0; i < m_bins; i++)\r
+ m_values[i] = 0;\r
+ *this = right;\r
+ }\r
+\r
+ // assignment operator\r
+ // this is done by copying the elements\r
+ // the source and target hashes can be different sizes\r
+ // the hash is self-copy safe, i.e. it is legal to say x = x;\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ hash<K,T,H,E>& hash<K,T,H,E>::operator = (const hash<K,T,H,E>& r)\r
+ {\r
+ // make self-copy safe\r
+ if (&r == this) return *this;\r
+ // remove all the existing elements\r
+ clear();\r
+ // copy the elements across - remember that this is rehashing because the two\r
+ // tables can be different sizes so there is no quick way of doing this by\r
+ // copying the lists\r
+ for (hash_iterator<K,T,H,E,const std::pair<const K,T> > i = r.begin(); i != r.end(); ++i)\r
+ insert(i->first, i->second);\r
+ return *this;\r
+ }\r
+\r
+ // number of values in the hash\r
+ template<typename K, typename T, class H, class E>\r
+ bool hash<K,T,H,E>::empty(void) const\r
+ {\r
+ return m_size == 0;\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ unsigned hash<K,T,H,E>::size(void) const\r
+ {\r
+ return m_size;\r
+ }\r
+\r
+ // equality\r
+ template<typename K, typename T, class H, class E>\r
+ bool hash<K,T,H,E>::operator == (const hash<K,T,H,E>& right) const\r
+ {\r
+ // this table is the same as the right table if they are the same table!\r
+ if (&right == this) return true;\r
+ // they must be the same size to be equal\r
+ if (m_size != right.m_size) return false;\r
+ // now every key in this must be in right and have the same data\r
+ for (hash_iterator<K,T,H,E,const std::pair<const K,T> > i = begin(); i != end(); i++)\r
+ {\r
+ hash_iterator<K,T,H,E,const std::pair<const K,T> > found = right.find(i->first);\r
+ if (found == right.end()) return false;\r
+ if (!(i->second == found->second)) return false;\r
+ }\r
+ return true;\r
+ }\r
+\r
+ // set up the hash to auto-rehash at a specific size\r
+ // setting the rehash size to 0 forces manual rehashing\r
+ template<typename K, typename T, class H, class E>\r
+ void hash<K,T,H,E>::auto_rehash(void)\r
+ {\r
+ m_rehash = m_bins;\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ void hash<K,T,H,E>::manual_rehash(void)\r
+ {\r
+ m_rehash = 0;\r
+ }\r
+\r
+ // the rehash function\r
+ // builds a new hash table and moves the elements (without copying) from the old to the new\r
+ // I store the un-modulused hash value in the element for more efficient rehashing\r
+ // passing 0 to the bins parameter does auto-rehashing\r
+ // passing any other value forces the number of bins\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ void hash<K,T,H,E>::rehash(unsigned bins)\r
+ {\r
+ // user specified size: just take the user's value\r
+ // auto calculate: if the load is high, increase the size; else do nothing\r
+ unsigned new_bins = bins ? bins : m_bins;\r
+ if (bins == 0 && m_size > 0)\r
+ {\r
+ // these numbers are pretty arbitrary\r
+ // TODO - make them user-customisable?\r
+ float load = loading();\r
+ if (load > 2.0)\r
+ new_bins = (unsigned)(m_bins * load);\r
+ else if (load > 1.0)\r
+ new_bins = m_bins * 2;\r
+ }\r
+ if (new_bins == m_bins) return;\r
+ // set the new rehashing point if auto-rehashing is on\r
+ if (m_rehash) m_rehash = new_bins;\r
+ // move aside the old structure\r
+ hash_element<K,T,H,E>** old_values = m_values;\r
+ unsigned old_bins = m_bins;\r
+ // create a replacement structure\r
+ m_values = new hash_element<K,T,H,E>*[new_bins];\r
+ for (unsigned i = 0; i < new_bins; i++)\r
+ m_values[i] = 0;\r
+ m_bins = new_bins;\r
+ // move all the old elements across, rehashing each one\r
+ for (unsigned j = 0; j < old_bins; j++)\r
+ {\r
+ while(old_values[j])\r
+ {\r
+ // unhook from the old structure\r
+ hash_element<K,T,H,E>* current = old_values[j];\r
+ old_values[j] = current->m_next;\r
+ // rehash using the stored hash value\r
+ unsigned bin = current->bin();\r
+ // hook it into the new structure\r
+ current->m_next = m_values[bin];\r
+ m_values[bin] = current;\r
+ }\r
+ }\r
+ // now delete the old structure\r
+ delete[] old_values;\r
+ }\r
+\r
+ // the loading is the average number of elements per bin\r
+ // this simplifies to the total elements divided by the number of bins\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ float hash<K,T,H,E>::loading(void) const\r
+ {\r
+ return (float)m_size / (float)m_bins;\r
+ }\r
+\r
+ // remove all elements from the table\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ void hash<K,T,H,E>::erase(void)\r
+ {\r
+ // unhook the list elements and destroy them\r
+ for (unsigned i = 0; i < m_bins; i++)\r
+ {\r
+ hash_element<K,T,H,E>* current = m_values[i];\r
+ while(current)\r
+ {\r
+ hash_element<K,T,H,E>* next = current->m_next;\r
+ delete current;\r
+ current = next;\r
+ }\r
+ m_values[i] = 0;\r
+ }\r
+ m_size = 0;\r
+ }\r
+\r
+ // test for whether a key is present in the table\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ bool hash<K,T,H,E>::present(const K& key) const\r
+ {\r
+ return find(key) != end();\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::size_type hash<K,T,H,E>::count(const K& key) const\r
+ {\r
+ return present() ? 1 : 0;\r
+ }\r
+\r
+ // add a key and data element to the table - defined in terms of the general-purpose pair insert function\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::insert(const K& key, const T& data)\r
+ {\r
+ return insert(std::pair<const K,T>(key,data)).first;\r
+ }\r
+\r
+ // insert a key/data pair into the table\r
+ // this removes any old value with the same key since there is no multihash functionality\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ std::pair<TYPENAME hash<K,T,H,E>::iterator, bool> hash<K,T,H,E>::insert(const std::pair<const K,T>& value)\r
+ {\r
+ // if auto-rehash is enabled, implement the auto-rehash before inserting the new value\r
+ // the table is rehashed if this insertion makes the loading exceed 1.0\r
+ if (m_rehash && (m_size >= m_rehash)) rehash();\r
+ // calculate the new hash value\r
+ unsigned hash_value_full = H()(value.first);\r
+ unsigned bin = hash_value_full % m_bins;\r
+ bool inserted = true;\r
+ // unhook any previous value with this key\r
+ // this has been inlined from erase(key) so that the hash value is not calculated twice\r
+ hash_element<K,T,H,E>* previous = 0;\r
+ for (hash_element<K,T,H,E>* current = m_values[bin]; current; previous = current, current = current->m_next)\r
+ {\r
+ // first check the full stored hash value\r
+ if (current->m_hash != hash_value_full) continue;\r
+\r
+ // next try the equality operator\r
+ if (!E()(current->m_value.first, value.first)) continue;\r
+\r
+ // unhook this value and destroy it\r
+ if (previous)\r
+ previous->m_next = current->m_next;\r
+ else\r
+ m_values[bin] = current->m_next;\r
+ delete current;\r
+ m_size--;\r
+\r
+ // we've overwritten a previous value\r
+ inserted = false;\r
+\r
+ // assume there can only be one match so we can give up now\r
+ break;\r
+ }\r
+ // now hook in a new list element at the start of the list for this hash value\r
+ hash_element<K,T,H,E>* new_item = new hash_element<K,T,H,E>(this, value, hash_value_full);\r
+ new_item->m_next = m_values[bin];\r
+ m_values[bin] = new_item;\r
+ // increment the size count\r
+ m_size++;\r
+ // construct an iterator from the list node, and return whether inserted\r
+ return std::make_pair(hash_iterator<K,T,H,E,std::pair<const K,T> >(new_item), inserted);\r
+ }\r
+\r
+ // insert a key with an empty data field ready to be filled in later\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::insert(const K& key)\r
+ {\r
+ return insert(key,T());\r
+ }\r
+\r
+ // remove a key from the table - return true if the key was found and removed, false if it wasn't present\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ bool hash<K,T,H,E>::erase(const K& key)\r
+ {\r
+ unsigned hash_value_full = H()(key);\r
+ unsigned bin = hash_value_full % m_bins;\r
+ // scan the list for an element with this key\r
+ // need to keep a previous pointer because the lists are single-linked\r
+ hash_element<K,T,H,E>* previous = 0;\r
+ for (hash_element<K,T,H,E>* current = m_values[bin]; current; previous = current, current = current->m_next)\r
+ {\r
+ // first check the full stored hash value\r
+ if (current->m_hash != hash_value_full) continue;\r
+\r
+ // next try the equality operator\r
+ if (!E()(current->m_value.first, key)) continue;\r
+\r
+ // found this key, so unhook the element from the list\r
+ if (previous)\r
+ previous->m_next = current->m_next;\r
+ else\r
+ m_values[bin] = current->m_next;\r
+ // destroy it\r
+ delete current;\r
+ // remember to maintain the size count\r
+ m_size--;\r
+ return true;\r
+ }\r
+ return false;\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ void hash<K,T,H,E>::clear(void)\r
+ {\r
+ erase();\r
+ }\r
+\r
+ // search for a key in the table and return an iterator to it\r
+ // if the search fails, returns an end() iterator\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::const_iterator hash<K,T,H,E>::find(const K& key) const\r
+ {\r
+ // scan the list for this key's hash value for the element with a matching key\r
+ unsigned hash_value_full = H()(key);\r
+ unsigned bin = hash_value_full % m_bins;\r
+ for (hash_element<K,T,H,E>* current = m_values[bin]; current; current = current->m_next)\r
+ {\r
+ if (current->m_hash == hash_value_full && E()(current->m_value.first, key))\r
+ return hash_iterator<K,T,H,E,const std::pair<const K,T> >(current);\r
+ }\r
+ return end();\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::find(const K& key)\r
+ {\r
+ // scan the list for this key's hash value for the element with a matching key\r
+ unsigned hash_value_full = H()(key);\r
+ unsigned bin = hash_value_full % m_bins;\r
+ for (hash_element<K,T,H,E>* current = m_values[bin]; current; current = current->m_next)\r
+ {\r
+ if (current->m_hash == hash_value_full && E()(current->m_value.first, key))\r
+ return hash_iterator<K,T,H,E,std::pair<const K,T> >(current);\r
+ }\r
+ return end();\r
+ }\r
+\r
+ // table lookup by key using the index operator[], returning a reference to the data field, not an iterator\r
+ // this is rather like the std::map's [] operator\r
+ // the difference is that I have a const and non-const version\r
+ // the const version will not create the element if not present already, but the non-const version will\r
+ // the non-const version is compatible with the behaviour of the map\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ const T& hash<K,T,H,E>::operator[] (const K& key) const throw(std::out_of_range)\r
+ {\r
+ // this const version cannot change the hash, so has to raise an exception if the key is missing\r
+ hash_iterator<K,T,H,E,const std::pair<const K,T> > found = find(key);\r
+ if (found == end())\r
+ throw std::out_of_range("key not found in stlplus::hash::operator[]");\r
+ return found->second;\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ T& hash<K,T,H,E>::operator[] (const K& key)\r
+ {\r
+ // this non-const version can change the hash, so creates a new element if the key is missing\r
+ hash_iterator<K,T,H,E,std::pair<const K,T> > found = find(key);\r
+ if (found == end())\r
+ found = insert(key);\r
+ return found->second;\r
+ }\r
+\r
+ // iterators\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::const_iterator hash<K,T,H,E>::begin(void) const\r
+ {\r
+ // find the first element\r
+ for (unsigned bin = 0; bin < m_bins; bin++)\r
+ if (m_values[bin])\r
+ return hash_iterator<K,T,H,E,const std::pair<const K,T> >(m_values[bin]);\r
+ // if the hash is empty, return the end iterator\r
+ return end();\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::begin(void)\r
+ {\r
+ // find the first element\r
+ for (unsigned bin = 0; bin < m_bins; bin++)\r
+ if (m_values[bin])\r
+ return hash_iterator<K,T,H,E,std::pair<const K,T> >(m_values[bin]);\r
+ // if the hash is empty, return the end iterator\r
+ return end();\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::const_iterator hash<K,T,H,E>::end(void) const\r
+ {\r
+ return hash_iterator<K,T,H,E,const std::pair<const K,T> >(this);\r
+ }\r
+\r
+ template<typename K, typename T, class H, class E>\r
+ TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::end(void)\r
+ {\r
+ return hash_iterator<K,T,H,E,std::pair<const K,T> >(this);\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
--- /dev/null
+#ifndef STLPLUS_MATRIX\r
+#define STLPLUS_MATRIX\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+// General-purpose 2D matrix data structure \r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include "containers_fixes.hpp"\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename T> class matrix\r
+ {\r
+ public:\r
+ matrix(unsigned rows = 0, unsigned cols = 0, const T& fill = T()) throw();\r
+ ~matrix(void) throw();\r
+\r
+ matrix(const matrix&) throw();\r
+ matrix& operator =(const matrix&) throw();\r
+\r
+ void resize(unsigned rows, unsigned cols, const T& fill = T()) throw();\r
+\r
+ unsigned rows(void) const throw();\r
+ unsigned columns(void) const throw();\r
+\r
+ void erase(const T& fill = T()) throw();\r
+ void erase(unsigned row, unsigned col, const T& fill = T()) throw(std::out_of_range);\r
+ void insert(unsigned row, unsigned col, const T&) throw(std::out_of_range);\r
+ const T& item(unsigned row, unsigned col) const throw(std::out_of_range);\r
+ T& item(unsigned row, unsigned col) throw(std::out_of_range);\r
+ const T& operator()(unsigned row, unsigned col) const throw(std::out_of_range);\r
+ T& operator()(unsigned row, unsigned col) throw(std::out_of_range);\r
+\r
+ void fill(const T& item = T()) throw();\r
+ void fill_column(unsigned col, const T& item = T()) throw(std::out_of_range);\r
+ void fill_row(unsigned row, const T& item = T()) throw(std::out_of_range);\r
+ void fill_leading_diagonal(const T& item = T()) throw();\r
+ void fill_trailing_diagonal(const T& item = T()) throw();\r
+ void make_identity(const T& one, const T& zero = T()) throw();\r
+\r
+ void transpose(void) throw();\r
+\r
+ private:\r
+ unsigned m_rows;\r
+ unsigned m_cols;\r
+ T** m_data;\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
+#include "matrix.tpp"\r
+#endif\r
--- /dev/null
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename T>\r
+ matrix<T>::matrix(unsigned rows, unsigned cols, const T& fill) throw()\r
+ {\r
+ m_rows = 0;\r
+ m_cols = 0;\r
+ m_data = 0;\r
+ resize(rows,cols,fill);\r
+ }\r
+\r
+ template<typename T>\r
+ matrix<T>::~matrix(void) throw()\r
+ {\r
+ for (unsigned row = 0; row < m_rows; row++)\r
+ delete[] m_data[row];\r
+ delete[] m_data;\r
+ }\r
+\r
+ template<typename T>\r
+ matrix<T>::matrix(const matrix<T>& r) throw()\r
+ {\r
+ m_rows = 0;\r
+ m_cols = 0;\r
+ m_data = 0;\r
+ *this = r;\r
+ }\r
+\r
+ template<typename T>\r
+ matrix<T>& matrix<T>::operator =(const matrix<T>& right) throw()\r
+ {\r
+ // clear the old values\r
+ for (unsigned row = 0; row < m_rows; row++)\r
+ delete[] m_data[row];\r
+ delete[] m_data;\r
+ m_rows = 0;\r
+ m_cols = 0;\r
+ m_data = 0;\r
+ // now reconstruct with the new\r
+ resize(right.m_rows, right.m_cols);\r
+ for (unsigned row = 0; row < m_rows; row++)\r
+ for (unsigned col = 0; col < m_cols; col++)\r
+ m_data[row][col] = right.m_data[row][col];\r
+ return *this;\r
+ }\r
+\r
+ template<typename T>\r
+ void matrix<T>::resize(unsigned rows, unsigned cols, const T& fill) throw()\r
+ {\r
+ // a grid is an array of rows, where each row is an array of T\r
+ // a zero-row or zero-column matrix has a null grid\r
+ // TODO - make this exception-safe - new could throw here and that would cause a memory leak\r
+ T** new_grid = 0;\r
+ if (rows && cols)\r
+ {\r
+ new_grid = new T*[rows];\r
+ for (unsigned row = 0; row < rows; row++)\r
+ {\r
+ new_grid[row] = new T[cols];\r
+ // copy old items to the new grid but only within the bounds of the intersection of the old and new grids\r
+ // fill the rest of the grid with the initial value\r
+ for (unsigned col = 0; col < cols; col++)\r
+ if (row < m_rows && col < m_cols)\r
+ new_grid[row][col] = m_data[row][col];\r
+ else\r
+ new_grid[row][col] = fill;\r
+ }\r
+ }\r
+ // destroy the old grid\r
+ for (unsigned row = 0; row < m_rows; row++)\r
+ delete[] m_data[row];\r
+ delete[] m_data;\r
+ // move the new data into the matrix\r
+ m_data = new_grid;\r
+ m_rows = rows;\r
+ m_cols = cols;\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned matrix<T>::rows(void) const throw()\r
+ {\r
+ return m_rows;\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned matrix<T>::columns(void) const throw()\r
+ {\r
+ return m_cols;\r
+ }\r
+\r
+ template<typename T>\r
+ void matrix<T>::erase(const T& fill) throw()\r
+ {\r
+ for (unsigned row = 0; row < m_rows; row++)\r
+ for (unsigned col = 0; col < m_cols; col++)\r
+ insert(row,col,fill);\r
+ }\r
+\r
+ template<typename T>\r
+ void matrix<T>::erase(unsigned row, unsigned col, const T& fill) throw(std::out_of_range)\r
+ {\r
+ insert(row,col,fill);\r
+ }\r
+\r
+ template<typename T>\r
+ void matrix<T>::insert(unsigned row, unsigned col, const T& element) throw(std::out_of_range)\r
+ {\r
+ if (row >= m_rows) throw std::out_of_range("matrix::insert row");\r
+ if (col >= m_cols) throw std::out_of_range("matrix::insert col");\r
+ m_data[row][col] = element;\r
+ }\r
+\r
+ template<typename T>\r
+ const T& matrix<T>::item(unsigned row, unsigned col) const throw(std::out_of_range)\r
+ {\r
+ if (row >= m_rows) throw std::out_of_range("matrix::item row");\r
+ if (col >= m_cols) throw std::out_of_range("matrix::item col");\r
+ return m_data[row][col];\r
+ }\r
+\r
+ template<typename T>\r
+ T& matrix<T>::item(unsigned row, unsigned col) throw(std::out_of_range)\r
+ {\r
+ if (row >= m_rows) throw std::out_of_range("matrix::item row");\r
+ if (col >= m_cols) throw std::out_of_range("matrix::item col");\r
+ return m_data[row][col];\r
+ }\r
+\r
+ template<typename T>\r
+ const T& matrix<T>::operator()(unsigned row, unsigned col) const throw(std::out_of_range)\r
+ {\r
+ if (row >= m_rows) throw std::out_of_range("matrix::operator() row");\r
+ if (col >= m_cols) throw std::out_of_range("matrix::operator() col");\r
+ return m_data[row][col];\r
+ }\r
+\r
+ template<typename T>\r
+ T& matrix<T>::operator()(unsigned row, unsigned col) throw(std::out_of_range)\r
+ {\r
+ if (row >= m_rows) throw std::out_of_range("matrix::operator() row");\r
+ if (col >= m_cols) throw std::out_of_range("matrix::operator() col");\r
+ return m_data[row][col];\r
+ }\r
+\r
+ template<typename T>\r
+ void matrix<T>::fill(const T& item) throw()\r
+ {\r
+ erase(item);\r
+ }\r
+\r
+ template<typename T>\r
+ void matrix<T>::fill_column(unsigned col, const T& item) throw (std::out_of_range)\r
+ {\r
+ if (col >= m_cols) throw std::out_of_range("matrix::fill_column");\r
+ for (unsigned row = 0; row < m_rows; row++)\r
+ insert(row, col, item);\r
+ }\r
+\r
+ template<typename T>\r
+ void matrix<T>::fill_row(unsigned row, const T& item) throw (std::out_of_range)\r
+ {\r
+ if (row >= m_rows) throw std::out_of_range("matrix::fill_row");\r
+ for (unsigned col = 0; col < m_cols; col++)\r
+ insert(row, col, item);\r
+ }\r
+\r
+ template<typename T>\r
+ void matrix<T>::fill_leading_diagonal(const T& item) throw()\r
+ {\r
+ for (unsigned i = 0; i < m_cols && i < m_rows; i++)\r
+ insert(i, i, item);\r
+ }\r
+\r
+ template<typename T>\r
+ void matrix<T>::fill_trailing_diagonal(const T& item) throw()\r
+ {\r
+ for (unsigned i = 0; i < m_cols && i < m_rows; i++)\r
+ insert(i, m_cols-i-1, item);\r
+ }\r
+\r
+ template<typename T>\r
+ void matrix<T>::make_identity(const T& one, const T& zero) throw()\r
+ {\r
+ fill(zero);\r
+ fill_leading_diagonal(one);\r
+ }\r
+\r
+ template<typename T>\r
+ void matrix<T>::transpose(void) throw()\r
+ {\r
+ // no gain in manipulating this, since building a new matrix is no less efficient\r
+ matrix<T> transposed(columns(), rows());\r
+ for (unsigned row = 0; row < rows(); row++)\r
+ for (unsigned col = 0; col < columns(); col++)\r
+ transposed.insert(col,row,item(row,col));\r
+ // TODO - avoid an extra copy by swapping the member data here\r
+ *this = transposed;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
--- /dev/null
+#ifndef STLPLUS_NTREE\r
+#define STLPLUS_NTREE\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+// A templated n-ary tree data structure. STL-like but the definition of\r
+// iterators is really only applicable to one-dimensional structures. I use\r
+// iterators to access tree nodes, but there is no increment or decrement\r
+// operators for them. I also define prefix and postfix traversal iterators\r
+// which do have increment.\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include "containers_fixes.hpp"\r
+#include "exceptions.hpp"\r
+#include "safe_iterator.hpp"\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Internals\r
+\r
+ template<typename T> class ntree_node;\r
+ template<typename T> class ntree;\r
+ template<typename T, typename TRef, typename TPtr> class ntree_iterator;\r
+ template<typename T, typename TRef, typename TPtr> class ntree_prefix_iterator;\r
+ template<typename T, typename TRef, typename TPtr> class ntree_postfix_iterator;\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Iterators\r
+\r
+ // Simple iterators which are just used as pointers to tree nodes. These have\r
+ // no increment or decrement operations defined. An uninitialised iterator is\r
+ // null - similarly, if you ask for the root of an empty tree or the parent of\r
+ // the root node then you get a null iterator.\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ class ntree_iterator : public safe_iterator<ntree<T>,ntree_node<T> >\r
+ {\r
+ public:\r
+ // local type definitions\r
+ // an iterator points to an object whilst a const_iterator points to a const object\r
+ typedef ntree_iterator<T,T&,T*> iterator;\r
+ typedef ntree_iterator<T,const T&,const T*> const_iterator;\r
+ typedef ntree_iterator<T,TRef,TPtr> this_iterator;\r
+ typedef TRef reference;\r
+ typedef TPtr pointer;\r
+\r
+ // constructor to create a null iterator - you must assign a valid value to this iterator before using it\r
+ ntree_iterator(void);\r
+ ~ntree_iterator(void);\r
+\r
+ // Type conversion methods allow const_iterator and iterator to be converted\r
+ const_iterator constify(void) const;\r
+ iterator deconstify(void) const;\r
+\r
+ // tests useful for putting iterators into other STL structures and for testing whether iteration has completed\r
+ bool operator == (const this_iterator& r) const;\r
+ bool operator != (const this_iterator& r) const;\r
+ bool operator < (const this_iterator& r) const;\r
+\r
+ // access the node data - a const_iterator gives you a const element, an iterator a non-const element\r
+ // it is illegal to dereference an invalid (i.e. null or end) iterator\r
+ reference operator*(void) const\r
+ throw(null_dereference,end_dereference);\r
+ pointer operator->(void) const\r
+ throw(null_dereference,end_dereference);\r
+\r
+ friend class ntree<T>;\r
+ friend class ntree_prefix_iterator<T,TRef,TPtr>;\r
+ friend class ntree_postfix_iterator<T,TRef,TPtr>;\r
+\r
+ public:\r
+ // Note: I had to make this public to get round a compiler problem - it should be private\r
+ // you cannot create a valid iterator except by calling an ntree method that returns one\r
+ // constructor used by ntree to create a non-null iterator\r
+ explicit ntree_iterator(ntree_node<T>* node);\r
+ // constructor used by ntree to create an end iterator\r
+ explicit ntree_iterator(const ntree<T>* owner);\r
+ // used to create an alias of an iterator\r
+ explicit ntree_iterator(const safe_iterator<ntree<T>, ntree_node<T> >& iterator);\r
+ };\r
+\r
+ // Traversal iterators are like iterators but they have increment operators (++)\r
+ // - prefix_iterator visits the nodes of the tree in prefix order\r
+ // - postfix_iterator visits the nodes of the tree in postfix order.\r
+ // There is no such thing as infix order for an n-ary tree and you cannot\r
+ // traverse backwards with these iterators. These follow the STL convention in\r
+ // that you iterate from a begin to an end - in this case ntree exports\r
+ // prefix_begin()/prefix_end() and postfix_begin()/postfix_end(). You can\r
+ // simplify these iterators to the basic iterator above for functions that\r
+ // require a simple iterator.\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ class ntree_prefix_iterator\r
+ {\r
+ public:\r
+ typedef ntree_prefix_iterator<T,T&,T*> iterator;\r
+ typedef ntree_prefix_iterator<T,const T&,const T*> const_iterator;\r
+ typedef ntree_prefix_iterator<T,TRef,TPtr> this_iterator;\r
+ typedef ntree_iterator<T,TRef,TPtr> simple_iterator;\r
+ typedef TRef reference;\r
+ typedef TPtr pointer;\r
+\r
+ // constructor to create a null iterator - you must assign a valid value to this iterator before using it\r
+ ntree_prefix_iterator(void);\r
+ ~ntree_prefix_iterator(void);\r
+\r
+ // tests\r
+ // a null iterator is one that has not been initialised with a value yet\r
+ // i.e. you just declared it but didn't assign to it\r
+ bool null(void) const;\r
+ // an end iterator is one that points to the end element of the list of nodes\r
+ // in STL conventions this is one past the last valid element and must not be dereferenced\r
+ bool end(void) const;\r
+ // a valid iterator is one that can be dereferenced\r
+ // i.e. non-null and non-end\r
+ bool valid(void) const;\r
+\r
+ // Type conversion methods allow const_iterator and iterator to be converted\r
+ // convert an iterator/const_iterator to a const_iterator\r
+ const_iterator constify(void) const;\r
+ iterator deconstify(void) const;\r
+\r
+ // generate a simple iterator from a traversal iterator\r
+ ntree_iterator<T,TRef,TPtr> simplify(void) const;\r
+\r
+ // tests useful for putting iterators into other STL structures and for testing whether iteration has completed\r
+ bool operator == (const this_iterator& r) const;\r
+ bool operator != (const this_iterator& r) const;\r
+ bool operator < (const this_iterator& r) const;\r
+\r
+ // increment/decrement operators used to step through the set of all nodes in a graph\r
+ // it is only legal to increment a valid iterator\r
+ // pre-increment\r
+ this_iterator& operator ++ (void)\r
+ throw(null_dereference,end_dereference);\r
+ // post-increment\r
+ this_iterator operator ++ (int)\r
+ throw(null_dereference,end_dereference);\r
+\r
+ // access the node data - a const_iterator gives you a const element, an iterator a non-const element\r
+ // it is illegal to dereference an invalid (i.e. null or end) iterator\r
+ reference operator*(void) const\r
+ throw(null_dereference,end_dereference);\r
+ pointer operator->(void) const\r
+ throw(null_dereference,end_dereference);\r
+\r
+ friend class ntree<T>;\r
+ friend class ntree_iterator<T,TRef,TPtr>;\r
+\r
+ private:\r
+ ntree_iterator<T,TRef,TPtr> m_iterator;\r
+\r
+ explicit ntree_prefix_iterator(const ntree_iterator<T,TRef,TPtr>& i);\r
+ const ntree_iterator<T,TRef,TPtr>& get_iterator(void) const;\r
+ ntree_iterator<T,TRef,TPtr>& get_iterator(void);\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ class ntree_postfix_iterator\r
+ {\r
+ public:\r
+ typedef ntree_postfix_iterator<T,T&,T*> iterator;\r
+ typedef ntree_postfix_iterator<T,const T&,const T*> const_iterator;\r
+ typedef ntree_postfix_iterator<T,TRef,TPtr> this_iterator;\r
+ typedef ntree_iterator<T,TRef,TPtr> simple_iterator;\r
+ typedef TRef reference;\r
+ typedef TPtr pointer;\r
+\r
+ // constructor to create a null iterator - you must assign a valid value to this iterator before using it\r
+ ntree_postfix_iterator(void);\r
+ ~ntree_postfix_iterator(void);\r
+\r
+ // tests\r
+ // a null iterator is one that has not been initialised with a value yet\r
+ // i.e. you just declared it but didn't assign to it\r
+ bool null(void) const;\r
+ // an end iterator is one that points to the end element of the list of nodes\r
+ // in STL conventions this is one past the last valid element and must not be dereferenced\r
+ bool end(void) const;\r
+ // a valid iterator is one that can be dereferenced\r
+ // i.e. non-null and non-end\r
+ bool valid(void) const;\r
+\r
+ // Type conversion methods allow const_iterator and iterator to be converted\r
+ // convert an iterator/const_iterator to a const_iterator\r
+ const_iterator constify(void) const;\r
+ iterator deconstify(void) const;\r
+\r
+ // generate a simple iterator from a traversal iterator\r
+ ntree_iterator<T,TRef,TPtr> simplify(void) const;\r
+\r
+ // tests useful for putting iterators into other STL structures and for testing whether iteration has completed\r
+ bool operator == (const this_iterator& r) const;\r
+ bool operator != (const this_iterator& r) const;\r
+ bool operator < (const this_iterator& r) const;\r
+\r
+ // increment/decrement operators used to step through the set of all nodes in a graph\r
+ // it is only legal to increment a valid iterator\r
+ // pre-increment\r
+ this_iterator& operator ++ (void)\r
+ throw(null_dereference,end_dereference);\r
+ // post-increment\r
+ this_iterator operator ++ (int)\r
+ throw(null_dereference,end_dereference);\r
+\r
+ // access the node data - a const_iterator gives you a const element, an iterator a non-const element\r
+ // it is illegal to dereference an invalid (i.e. null or end) iterator\r
+ reference operator*(void) const\r
+ throw(null_dereference,end_dereference);\r
+ pointer operator->(void) const\r
+ throw(null_dereference,end_dereference);\r
+\r
+ friend class ntree<T>;\r
+ friend class ntree_iterator<T,TRef,TPtr>;\r
+\r
+ private:\r
+ ntree_iterator<T,TRef,TPtr> m_iterator;\r
+\r
+ explicit ntree_postfix_iterator(const ntree_iterator<T,TRef,TPtr>& i);\r
+ const ntree_iterator<T,TRef,TPtr>& get_iterator(void) const;\r
+ ntree_iterator<T,TRef,TPtr>& get_iterator(void);\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // The Ntree class\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename T>\r
+ class ntree\r
+ {\r
+ public:\r
+ // STL-like typedefs for the types and iterators\r
+ typedef T value_type;\r
+\r
+ typedef ntree_iterator<T,T&,T*> iterator;\r
+ typedef ntree_iterator<T,const T&,const T*> const_iterator;\r
+\r
+ typedef ntree_prefix_iterator<T,T&,T*> prefix_iterator;\r
+ typedef ntree_prefix_iterator<T,const T&,const T*> const_prefix_iterator;\r
+\r
+ typedef ntree_postfix_iterator<T,T&,T*> postfix_iterator;\r
+ typedef ntree_postfix_iterator<T,const T&,const T*> const_postfix_iterator;\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // Constructors, destructors and copies\r
+\r
+ ntree(void);\r
+ ~ntree(void);\r
+\r
+ // copy constructor and assignment both copy the tree\r
+ ntree(const ntree<T>&);\r
+ ntree<T>& operator=(const ntree<T>&);\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // size tests\r
+\r
+ // tests on whole tree\r
+ bool empty(void) const;\r
+ unsigned size(void) const;\r
+\r
+ // tests for number of nodes in subtree starting at node\r
+ unsigned size(const const_iterator& node) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ unsigned size(const iterator& node)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // test for depth of tree from root to node\r
+ unsigned depth(const const_iterator& node) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ unsigned depth(const iterator& node)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // direct traversal\r
+\r
+ const_iterator root(void) const;\r
+ iterator root(void);\r
+\r
+ unsigned children(const const_iterator& node) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ unsigned children(const iterator& node)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ const_iterator child(const const_iterator& node, unsigned child) const\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+ iterator child(const iterator& node, unsigned child)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+\r
+ const_iterator parent(const const_iterator& node) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ iterator parent(const iterator& node)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // iterator traversal\r
+\r
+ const_prefix_iterator prefix_begin(void) const;\r
+ prefix_iterator prefix_begin(void);\r
+ const_prefix_iterator prefix_end(void) const;\r
+ prefix_iterator prefix_end(void);\r
+\r
+ const_postfix_iterator postfix_begin(void) const;\r
+ postfix_iterator postfix_begin(void);\r
+ const_postfix_iterator postfix_end(void) const;\r
+ postfix_iterator postfix_end(void);\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // modification\r
+\r
+ iterator insert(const T&);\r
+\r
+ iterator insert(const iterator& node, unsigned child, const T&)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+ iterator append(const iterator& node, const T&) \r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ iterator insert(const iterator& node, unsigned child, const ntree<T>&)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+ iterator append(const iterator& node, const ntree<T>&)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ iterator push(const iterator& node, const T&) \r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ void pop(const iterator& node, unsigned child) \r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ void erase(void);\r
+ void erase(const iterator& node)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ void erase(const iterator& node, unsigned child)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+\r
+ ntree<T> subtree(void);\r
+ ntree<T> subtree(const iterator& node)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ ntree<T> subtree(const iterator& node, unsigned child)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+\r
+ ntree<T> cut(void);\r
+ ntree<T> cut(const iterator& node)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ ntree<T> cut(const iterator& node, unsigned child)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+\r
+ private:\r
+ ntree_node<T>* m_root;\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
+#include "ntree.tpp"\r
+#endif\r
--- /dev/null
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include <vector>\r
+#include <algorithm>\r
+\r
+namespace stlplus \r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // ntree_node\r
+\r
+ template<typename T>\r
+ class ntree_node\r
+ {\r
+ public:\r
+ master_iterator<ntree<T>, ntree_node<T> > m_master;\r
+ T m_data;\r
+ ntree_node<T>* m_parent;\r
+ std::vector<ntree_node<T>*> m_children;\r
+\r
+ public:\r
+ ntree_node(const ntree<T>* owner, const T& data = T()) :\r
+ m_master(owner,this), m_data(data), m_parent(0)\r
+ {\r
+ }\r
+\r
+ void change_owner(const ntree<T>* owner)\r
+ {\r
+ m_master.change_owner(owner);\r
+ for (TYPENAME std::vector<ntree_node<T>*>::iterator i = m_children.begin(); i != m_children.end(); i++)\r
+ (*i)->change_owner(owner);\r
+ }\r
+\r
+ ~ntree_node(void)\r
+ {\r
+ m_parent = 0;\r
+ for (TYPENAME std::vector<ntree_node<T>*>::iterator i = m_children.begin(); i != m_children.end(); i++)\r
+ delete *i;\r
+ }\r
+\r
+ };\r
+\r
+ template<typename T>\r
+ static ntree_node<T>* ntree_copy(const ntree<T>* new_owner, ntree_node<T>* root)\r
+ {\r
+ if (!root) return 0;\r
+ ntree_node<T>* new_tree = new ntree_node<T>(new_owner, root->m_data);\r
+ for (TYPENAME std::vector<ntree_node<T>*>::iterator i = root->m_children.begin(); i != root->m_children.end(); i++)\r
+ {\r
+ ntree_node<T>* new_child = ntree_copy(new_owner, *i);\r
+ new_tree->m_children.push_back(new_child);\r
+ new_child->m_parent = new_tree;\r
+ }\r
+ return new_tree;\r
+ }\r
+\r
+ template<typename T>\r
+ static unsigned ntree_size(ntree_node<T>* root)\r
+ {\r
+ if (!root) return 0;\r
+ unsigned result = 1;\r
+ for (TYPENAME std::vector<ntree_node<T>*>::iterator i = root->m_children.begin(); i != root->m_children.end(); i++)\r
+ result += ntree_size(*i);\r
+ return result;\r
+ }\r
+\r
+ template<typename T>\r
+ static unsigned ntree_depth(ntree_node<T>* root)\r
+ {\r
+ unsigned depth = 0;\r
+ for (ntree_node<T>* i = root; i; i = i->m_parent)\r
+ depth++;\r
+ return depth;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // ntree_iterator\r
+\r
+ // constructor to create a null iterator - you must assign a valid value to this iterator before using it\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr>::ntree_iterator(void)\r
+ {\r
+ }\r
+\r
+ // used to create an alias of an iterator\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr>::ntree_iterator(const safe_iterator<ntree<T>, ntree_node<T> >& iterator) :\r
+ safe_iterator<ntree<T>,ntree_node<T> >(iterator)\r
+ {\r
+ }\r
+\r
+ // constructor used by ntree to create a non-null iterator\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr>::ntree_iterator(ntree_node<T>* node) :\r
+ safe_iterator<ntree<T>,ntree_node<T> >(node->m_master)\r
+ {\r
+ }\r
+\r
+ // constructor used by ntree to create an end iterator\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr>::ntree_iterator(const ntree<T>* owner) :\r
+ safe_iterator<ntree<T>,ntree_node<T> >(owner)\r
+ {\r
+ }\r
+\r
+ // destructor\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr>::~ntree_iterator(void)\r
+ {\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_iterator<T,TRef,TPtr>::const_iterator ntree_iterator<T,TRef,TPtr>::constify(void) const\r
+ {\r
+ return ntree_iterator<T,const T&,const T*>(*this);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_iterator<T,TRef,TPtr>::iterator ntree_iterator<T,TRef,TPtr>::deconstify(void) const\r
+ {\r
+ return ntree_iterator<T,T&,T*>(*this);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return equal(r);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return !operator==(r);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return compare(r) < 0;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_iterator<T,TRef,TPtr>::reference ntree_iterator<T,TRef,TPtr>::operator*(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ this->assert_valid();\r
+ return this->node()->m_data;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_iterator<T,TRef,TPtr>::pointer ntree_iterator<T,TRef,TPtr>::operator->(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ return &(operator*());\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // ntree_prefix_iterator\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_prefix_iterator<T,TRef,TPtr>::ntree_prefix_iterator(void)\r
+ {\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_prefix_iterator<T,TRef,TPtr>::~ntree_prefix_iterator(void)\r
+ {\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_prefix_iterator<T,TRef,TPtr>::ntree_prefix_iterator(const ntree_iterator<T,TRef,TPtr>& i) :\r
+ m_iterator(i)\r
+ {\r
+ // this is initialised with the root node\r
+ // which is also the first node in prefix traversal order\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_prefix_iterator<T,TRef,TPtr>::null(void) const\r
+ {\r
+ return m_iterator.null();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_prefix_iterator<T,TRef,TPtr>::end(void) const\r
+ {\r
+ return m_iterator.end();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_prefix_iterator<T,TRef,TPtr>::valid(void) const\r
+ {\r
+ return m_iterator.valid();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::const_iterator ntree_prefix_iterator<T,TRef,TPtr>::constify(void) const\r
+ {\r
+ return ntree_prefix_iterator<T,const T&,const T*>(m_iterator);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::iterator ntree_prefix_iterator<T,TRef,TPtr>::deconstify(void) const\r
+ {\r
+ return ntree_prefix_iterator<T,T&,T*>(m_iterator);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr> ntree_prefix_iterator<T,TRef,TPtr>::simplify(void) const\r
+ {\r
+ return m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_prefix_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return m_iterator == r.m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_prefix_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return m_iterator != r.m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_prefix_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return m_iterator < r.m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& ntree_prefix_iterator<T,TRef,TPtr>::operator ++ (void)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ // pre-increment operator\r
+ // algorithm: if there are any children, visit child 0, otherwise, go to\r
+ // parent and deduce which child the start node was of that parent - if\r
+ // there are further children, go into the next one. Otherwise, go up the\r
+ // tree and test again for further children. Return null if there are no\r
+ // further nodes\r
+ m_iterator.assert_valid();\r
+ ntree_node<T>* old_node = m_iterator.node();\r
+ if (!old_node->m_children.empty())\r
+ {\r
+ // simply take the first child of this node\r
+ m_iterator.set(old_node->m_children[0]->m_master);\r
+ }\r
+ else\r
+ {\r
+ // this loop walks up the parent pointers\r
+ // either it will walk off the top and exit or a new node will be found and the loop will exit\r
+ for (;;)\r
+ {\r
+ // go up a level\r
+ ntree_node<T>* parent = old_node->m_parent;\r
+ if (!parent)\r
+ {\r
+ // we've walked off the top of the tree, so return end\r
+ m_iterator.set_end();\r
+ break;\r
+ }\r
+ else\r
+ {\r
+ // otherwise walk down the next child - if there is one\r
+ // find which index the old node was relative to this node\r
+ TYPENAME std::vector<ntree_node<T>*>::iterator found = \r
+ std::find(parent->m_children.begin(), parent->m_children.end(), old_node);\r
+ // if this was found, then see if there is another and if so return that\r
+ found++;\r
+ if (found != parent->m_children.end())\r
+ {\r
+ // visit the next child\r
+ m_iterator.set((*found)->m_master);\r
+ break;\r
+ }\r
+ else\r
+ {\r
+ // keep going up\r
+ old_node = parent;\r
+ }\r
+ }\r
+ }\r
+ }\r
+ return *this;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator ntree_prefix_iterator<T,TRef,TPtr>::operator ++ (int)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ // post-increment is defined in terms of the pre-increment\r
+ ntree_prefix_iterator<T,TRef,TPtr> result(*this);\r
+ ++(*this);\r
+ return result;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::reference ntree_prefix_iterator<T,TRef,TPtr>::operator*(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ return m_iterator.operator*();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::pointer ntree_prefix_iterator<T,TRef,TPtr>::operator->(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ return m_iterator.operator->();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ const ntree_iterator<T,TRef,TPtr>& ntree_prefix_iterator<T,TRef,TPtr>::get_iterator(void) const\r
+ {\r
+ return m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr>& ntree_prefix_iterator<T,TRef,TPtr>::get_iterator(void)\r
+ {\r
+ return m_iterator;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // ntree_postfix_iterator\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_postfix_iterator<T,TRef,TPtr>::ntree_postfix_iterator(void)\r
+ {\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_postfix_iterator<T,TRef,TPtr>::~ntree_postfix_iterator(void)\r
+ {\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_postfix_iterator<T,TRef,TPtr>::ntree_postfix_iterator(const ntree_iterator<T,TRef,TPtr>& i) :\r
+ m_iterator(i)\r
+ {\r
+ // this is initialised with the root node\r
+ // initially traverse to the first node to be visited\r
+ if (m_iterator.valid())\r
+ {\r
+ ntree_node<T>* node = m_iterator.node();\r
+ while (!node->m_children.empty())\r
+ node = node->m_children[0];\r
+ m_iterator.set(node->m_master);\r
+ }\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_postfix_iterator<T,TRef,TPtr>::null(void) const\r
+ {\r
+ return m_iterator.null();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_postfix_iterator<T,TRef,TPtr>::end(void) const\r
+ {\r
+ return m_iterator.end();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_postfix_iterator<T,TRef,TPtr>::valid(void) const\r
+ {\r
+ return m_iterator.valid();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::const_iterator ntree_postfix_iterator<T,TRef,TPtr>::constify(void) const\r
+ {\r
+ return ntree_postfix_iterator<T,const T&,const T*>(m_iterator);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::iterator ntree_postfix_iterator<T,TRef,TPtr>::deconstify(void) const\r
+ {\r
+ return ntree_postfix_iterator<T,T&,T*>(m_iterator);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr> ntree_postfix_iterator<T,TRef,TPtr>::simplify(void) const\r
+ {\r
+ return m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_postfix_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return m_iterator == r.m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_postfix_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return m_iterator != r.m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_postfix_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return m_iterator < r.m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& ntree_postfix_iterator<T,TRef,TPtr>::operator ++ (void)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ // pre-increment operator\r
+ // algorithm: this node has been visited, therefore all children must have\r
+ // already been visited. So go to parent. Return null if the parent is null.\r
+ // Otherwise deduce which child the start node was of that parent - if there\r
+ // are further children, go into the next one and then walk down any\r
+ // subsequent first-child pointers to the bottom. Otherwise, if there are no\r
+ // children then the parent node is the next in the traversal.\r
+ m_iterator.assert_valid();\r
+ // go up a level\r
+ ntree_node<T>* old_node = m_iterator.node();\r
+ ntree_node<T>* parent = old_node->m_parent;\r
+ if (!parent)\r
+ {\r
+ // we've walked off the top of the tree, so return end\r
+ m_iterator.set_end();\r
+ }\r
+ else\r
+ {\r
+ // otherwise find which index the old node was relative to this node\r
+ TYPENAME std::vector<ntree_node<T>*>::iterator found =\r
+ std::find(parent->m_children.begin(), parent->m_children.end(), old_node);\r
+ // if this was found, then see if there is another\r
+ found++;\r
+ if (found != parent->m_children.end())\r
+ {\r
+ // if so traverse to it and walk down the leftmost child pointers to the bottom of the new sub-tree\r
+ ntree_node<T>* new_node = *found;\r
+ while (!new_node->m_children.empty())\r
+ new_node = new_node->m_children[0];\r
+ m_iterator.set(new_node->m_master);\r
+ }\r
+ else\r
+ {\r
+ // the parent's children have all been visited - so the parent is visited\r
+ m_iterator.set(parent->m_master);\r
+ }\r
+ }\r
+ return *this;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator ntree_postfix_iterator<T,TRef,TPtr>::operator ++ (int)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ // post-increment is defined in terms of the pre-increment\r
+ ntree_postfix_iterator<T,TRef,TPtr> result(*this);\r
+ ++(*this);\r
+ return result;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::reference ntree_postfix_iterator<T,TRef,TPtr>::operator*(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ return m_iterator.operator*();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::pointer ntree_postfix_iterator<T,TRef,TPtr>::operator->(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ return m_iterator.operator->();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ const ntree_iterator<T,TRef,TPtr>& ntree_postfix_iterator<T,TRef,TPtr>::get_iterator(void) const\r
+ {\r
+ return m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr>& ntree_postfix_iterator<T,TRef,TPtr>::get_iterator(void)\r
+ {\r
+ return m_iterator;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // ntree\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename T>\r
+ ntree<T>::ntree(void) : m_root(0)\r
+ {\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T>::~ntree(void)\r
+ {\r
+ if (m_root) delete m_root;\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T>::ntree(const ntree<T>& r) : m_root(0)\r
+ {\r
+ *this = r;\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T>& ntree<T>::operator=(const ntree<T>& r)\r
+ {\r
+ if (m_root) delete m_root;\r
+ m_root = ntree_copy(this, r.m_root);\r
+ return *this;\r
+ }\r
+\r
+ template<typename T>\r
+ bool ntree<T>::empty(void) const\r
+ {\r
+ return m_root == 0;\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned ntree<T>::size(void) const\r
+ {\r
+ return ntree_size(m_root);\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned ntree<T>::size(const TYPENAME ntree<T>::const_iterator& i) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ return ntree_size(i.node());\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned ntree<T>::size(const TYPENAME ntree<T>::iterator& i)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ return ntree_size(i.node());\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned ntree<T>::depth(const TYPENAME ntree<T>::const_iterator& i) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ return ntree_depth(i.node());\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned ntree<T>::depth(const TYPENAME ntree<T>::iterator& i)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ return ntree_depth(i.node());\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::const_iterator ntree<T>::root(void) const\r
+ {\r
+ if (!m_root) return ntree_iterator<T,const T&,const T*>(this);\r
+ return ntree_iterator<T,const T&,const T*>(m_root);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::root(void)\r
+ {\r
+ if (!m_root) return ntree_iterator<T,T&,T*>(this);\r
+ return ntree_iterator<T,T&,T*>(m_root);\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned ntree<T>::children(const TYPENAME ntree<T>::const_iterator& i) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ return i.node()->m_children.size();\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned ntree<T>::children(const ntree_iterator<T,T&,T*>& i)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ return i.node()->m_children.size();\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::const_iterator ntree<T>::child(const TYPENAME ntree<T>::const_iterator& i, unsigned child) const\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ i.assert_valid(this);\r
+ if (child >= children(i)) throw std::out_of_range("stlplus::ntree");\r
+ return ntree_iterator<T,const T&,const T*>(i.node()->m_children[child]);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::child(const TYPENAME ntree<T>::iterator& i, unsigned child)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ i.assert_valid(this);\r
+ if (child >= children(i)) throw std::out_of_range("stlplus::ntree");\r
+ return ntree_iterator<T,T&,T*>(i.node()->m_children[child]);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::const_iterator ntree<T>::parent(const TYPENAME ntree<T>::const_iterator& i) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ ntree_node<T>* parent = i.node()->m_parent;\r
+ if (!parent) return ntree_iterator<T,const T&,const T*>(this);\r
+ return ntree_iterator<T,const T&,const T*>(parent);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::parent(const TYPENAME ntree<T>::iterator& i)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ ntree_node<T>* parent = i.node()->m_parent;\r
+ if (!parent) return ntree_iterator<T,T&,T*>(this);\r
+ return ntree_iterator<T,T&,T*>(parent);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::const_prefix_iterator ntree<T>::prefix_begin(void) const\r
+ {\r
+ return ntree_prefix_iterator<T,const T&,const T*>(root());\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::prefix_iterator ntree<T>::prefix_begin(void)\r
+ {\r
+ return ntree_prefix_iterator<T,T&,T*>(root());\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::const_prefix_iterator ntree<T>::prefix_end(void) const\r
+ {\r
+ return ntree_prefix_iterator<T,const T&,const T*>(ntree_iterator<T,const T&,const T*>(this));\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::prefix_iterator ntree<T>::prefix_end(void)\r
+ {\r
+ return ntree_prefix_iterator<T,T&,T*>(ntree_iterator<T,T&,T*>(this));\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::const_postfix_iterator ntree<T>::postfix_begin(void) const\r
+ {\r
+ return ntree_postfix_iterator<T,const T&,const T*>(root());\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::postfix_iterator ntree<T>::postfix_begin(void)\r
+ {\r
+ return ntree_postfix_iterator<T,T&,T*>(root());\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::const_postfix_iterator ntree<T>::postfix_end(void) const\r
+ {\r
+ return ntree_postfix_iterator<T,const T&,const T*>(ntree_iterator<T,const T&,const T*>(this));\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::postfix_iterator ntree<T>::postfix_end(void)\r
+ {\r
+ return ntree_postfix_iterator<T,T&,T*>(ntree_iterator<T,T&,T*>(this));\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::insert(const T& data)\r
+ {\r
+ // insert a new node as the root\r
+ return insert(ntree_iterator<T,T&,T*>(this), 0, data);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, unsigned offset, const T& data)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ // if i is the end iterator, this means insert a new root\r
+ if (i.end())\r
+ erase();\r
+ else\r
+ {\r
+ i.assert_valid(this);\r
+ if (offset > children(i)) throw std::out_of_range("stlplus::ntree");\r
+ }\r
+ ntree_node<T>* new_node = new ntree_node<T>(this,data);\r
+ if (i.end())\r
+ {\r
+ m_root = new_node;\r
+ }\r
+ else\r
+ {\r
+ i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node);\r
+ new_node->m_parent = i.node();\r
+ }\r
+ return ntree_iterator<T,T&,T*>(new_node);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::append(const TYPENAME ntree<T>::iterator& i, const T& data)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return insert(i, i.node()->m_children.size(), data);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, unsigned offset, const ntree<T>& tree)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ // insert a whole tree as a child of i\r
+ i.assert_valid(this);\r
+ if (offset > children(i)) throw std::out_of_range("stlplus::ntree");\r
+ ntree_node<T>* new_node = ntree_copy(this, tree.m_root);\r
+ i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node);\r
+ new_node->m_parent = i.node();\r
+ return ntree_iterator<T,T&,T*>(new_node);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::append(const TYPENAME ntree<T>::iterator& i, const ntree<T>& tree)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return insert(i, children(i), tree);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::push(const TYPENAME ntree<T>::iterator& node, const T& data)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ // insert a new node to replace the existing node in the tree\r
+ // making the original node the child of the new node\r
+ // i.e. (node) becomes (new)->(node)\r
+ // afterwards, the iterator still points to the old node, now the child\r
+ // returns the iterator to the new node\r
+ node.assert_valid(this);\r
+ ntree_node<T>* new_node = new ntree_node<T>(this,data);\r
+ if (node.node() == m_root)\r
+ {\r
+ // pushing the root node\r
+ m_root = new_node;\r
+ new_node->m_parent = 0;\r
+ }\r
+ else\r
+ {\r
+ // pushing a sub-node\r
+ *(std::find(node.node()->m_parent->m_children.begin(), node.node()->m_parent->m_children.end(), node.node())) = new_node;\r
+ new_node->m_parent = node.node()->m_parent;\r
+ }\r
+ // link up the old node as the child of the new node\r
+ new_node->m_children.insert(new_node->m_children.begin(),node.node());\r
+ node.node()->m_parent = new_node;\r
+ return ntree_iterator<T,T&,T*>(new_node);\r
+ }\r
+\r
+ template<typename T>\r
+ void ntree<T>::pop(const TYPENAME ntree<T>::iterator& parent, unsigned offset)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ // inverse of push\r
+ // removes the specified child of the parent node, adding its children to the parent node at the same offset\r
+ parent.assert_valid(this);\r
+ ntree_node<T>* node = parent.node();\r
+ if (offset >= node->m_children.size()) throw std::out_of_range("stlplus::ntree");\r
+ // move the grandchildren first\r
+ ntree_node<T>* child = parent.node()->m_children[offset];\r
+ while (!child->m_children.empty())\r
+ {\r
+ // remove the last grandchild and insert into node just after the child to be removed\r
+ ntree_node<T>* grandchild = child->m_children[child->m_children.size()-1];\r
+ child->m_children.pop_back();\r
+ node->m_children.insert(node->m_children.begin()+offset+1, grandchild);\r
+ grandchild->m_parent = node;\r
+ }\r
+ // now remove the child\r
+ node->m_children.erase(node->m_children.begin()+offset);\r
+ delete child;\r
+ }\r
+\r
+ template<typename T>\r
+ void ntree<T>::erase(void)\r
+ {\r
+ // erase the whole tree\r
+ erase(root());\r
+ }\r
+\r
+ template<typename T>\r
+ void ntree<T>::erase(const TYPENAME ntree<T>::iterator& i)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ if (!i.end())\r
+ {\r
+ // erase this node and its subtree\r
+ // do this by erasing this child of its parent\r
+ // handle the case of erasing the root\r
+ i.assert_valid(this);\r
+ ntree_node<T>* node = i.node();\r
+ if (node == m_root)\r
+ {\r
+ delete m_root;\r
+ m_root = 0;\r
+ }\r
+ else\r
+ {\r
+ ntree_node<T>* parent = node->m_parent;\r
+ // impossible for parent to be null - should assert this\r
+ TYPENAME std::vector<ntree_node<T>*>::iterator found = \r
+ std::find(parent->m_children.begin(), parent->m_children.end(), node);\r
+ // impossible for find to fail - should assert this\r
+ parent->m_children.erase(found);\r
+ delete node;\r
+ }\r
+ }\r
+ }\r
+\r
+ template<typename T>\r
+ void ntree<T>::erase(const TYPENAME ntree<T>::iterator& i, unsigned offset)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ erase(child(i, offset));\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T> ntree<T>::subtree(void)\r
+ {\r
+ return subtree(root());\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T> ntree<T>::subtree(const TYPENAME ntree<T>::iterator& i)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ ntree<T> result;\r
+ if (!i.end())\r
+ {\r
+ i.assert_valid(this);\r
+ result.m_root = ntree_copy(&result, i.node());\r
+ }\r
+ return result;\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T> ntree<T>::subtree(const TYPENAME ntree<T>::iterator& i, unsigned offset)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ return subtree(child(i, offset));\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T> ntree<T>::cut(void)\r
+ {\r
+ return cut(root());\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T> ntree<T>::cut(const TYPENAME ntree<T>::iterator& i)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ ntree<T> result;\r
+ if (!i.end())\r
+ {\r
+ i.assert_valid(this);\r
+ ntree_node<T>* node = i.node();\r
+ if (node == m_root)\r
+ {\r
+ result.m_root = m_root;\r
+ m_root = 0;\r
+ }\r
+ else\r
+ {\r
+ ntree_node<T>* parent = node->m_parent;\r
+ // impossible for parent to be null - should assert this\r
+ TYPENAME std::vector<ntree_node<T>*>::iterator found = \r
+ std::find(parent->m_children.begin(), parent->m_children.end(), node);\r
+ // impossible for find to fail - should assert this\r
+ result.m_root = *found;\r
+ parent->m_children.erase(found);\r
+ }\r
+ if (result.m_root)\r
+ {\r
+ result.m_root->m_parent = 0;\r
+ result.m_root->set_new_owner(&result);\r
+ }\r
+ }\r
+ return result;\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T> ntree<T>::cut(const TYPENAME ntree<T>::iterator& i, unsigned offset)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ return cut(child(i, offset));\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
--- /dev/null
+#ifndef STLPLUS_SAFE_ITERATOR\r
+#define STLPLUS_SAFE_ITERATOR\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+// The STLplus safe_iterator superclasses. This implements the STLplus safe\r
+// iterator principles. Data structures can then be built using subclasses\r
+// of safe_iterator for their iterator objects and they will inherit the\r
+// safe iterator behaviour.\r
+\r
+// The data structure must contain a master iterator for each node in the\r
+// structure. When an iterator is returned to the user, it must be created\r
+// by the master iterator. When a node is removed from the data structure,\r
+// its master iterator is destroyed. This sets all iterators pointing to the\r
+// master iterator to end iterators.\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include "containers_fixes.hpp"\r
+#include "exceptions.hpp"\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // internals\r
+\r
+ template<typename O, typename N>\r
+ class safe_iterator_body;\r
+\r
+ template<typename O, typename N>\r
+ class safe_iterator;\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Master Iterator\r
+ // Create one of these in each node in the data structure\r
+ // Generate iterators by obtaining a safe-iterator object from the master iterator\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename O, typename N>\r
+ class master_iterator\r
+ {\r
+ public:\r
+\r
+ // construct a valid master iterator connected to the node\r
+ master_iterator(const O* owner, N* node) throw();\r
+\r
+ // destructor - disconnects all iterators from the node\r
+ ~master_iterator(void) throw();\r
+\r
+ // dereference\r
+ N* node(void) const throw();\r
+ const O* owner(void) const throw();\r
+\r
+ // when you move a node from one owner to another, call this on the node's master iterator\r
+ // this effectively moves all other iterators to the node so that they are owned by the new owner too\r
+ void change_owner(const O* owner) throw();\r
+\r
+ friend class safe_iterator<O,N>;\r
+ private:\r
+ master_iterator(const master_iterator&) throw();\r
+ master_iterator& operator=(const master_iterator&) throw();\r
+ safe_iterator_body<O,N>* m_body;\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Safe Iterator\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename O, typename N>\r
+ class safe_iterator\r
+ {\r
+ public:\r
+\r
+ // construct a null iterator\r
+ safe_iterator(void) throw();\r
+\r
+ // construct a valid iterator by aliasing from the owner node's master iterator\r
+ safe_iterator(const master_iterator<O,N>&) throw();\r
+\r
+ // copy constructor does aliasing\r
+ safe_iterator(const safe_iterator<O,N>&) throw();\r
+\r
+ // alias an iterator by assignment\r
+ safe_iterator<O,N>& operator=(const safe_iterator<O,N>&) throw();\r
+\r
+ // destructor\r
+ ~safe_iterator(void) throw();\r
+\r
+ // reassignment to another node used in increment/decrement operation\r
+ void set(const master_iterator<O,N>&) throw();\r
+\r
+ // dereference\r
+ N* node(void) const throw();\r
+ const O* owner(void) const throw();\r
+\r
+ // change to a null iterator - i.e. one that does not belong to any object\r
+ // this does not affect any other iterators pointing to the same node\r
+ void set_null(void) throw();\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // operations for clients that do not have a master end iterator\r
+ // alternatively, have a master end iterator as part of the container\r
+ // and call constructor(master_end) or set(master_end)\r
+\r
+ // construct an end iterator\r
+ safe_iterator(const O* owner) throw();\r
+\r
+ // change to an end iterator - e.g. as a result of incrementing off the end\r
+ void set_end(void) throw();\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // tests\r
+\r
+ // comparison\r
+ bool equal(const safe_iterator<O,N>& right) const throw();\r
+ int compare(const safe_iterator<O,N>& right) const throw();\r
+\r
+ // a null iterator is one that has not been initialised with a value yet\r
+ // i.e. you just declared it but didn't assign to it\r
+ bool null(void) const throw();\r
+\r
+ // an end iterator is one that points to the end element of the list of nodes\r
+ // in STL conventions this is one past the last valid element and must not be dereferenced\r
+ bool end(void) const throw();\r
+\r
+ // a valid iterator is one that can be dereferenced\r
+ // i.e. non-null and non-end\r
+ bool valid(void) const throw();\r
+\r
+ // check the rules for a valid iterator that can be dereferenced\r
+ // optionally also check that the iterator is owned by the owner\r
+ void assert_valid(void) const throw(null_dereference,end_dereference);\r
+ void assert_valid(const O* owner) const throw(wrong_object,null_dereference,end_dereference);\r
+ // assert the rules for a non-null iterator - i.e. valid or end, values that occur in increment operations\r
+ void assert_non_null(void) const throw(null_dereference);\r
+ // assert that this iterator is owned by this container\r
+ void assert_owner(const O* owner) const throw(wrong_object);\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ friend class master_iterator<O,N>;\r
+ private:\r
+ safe_iterator_body<O,N>* m_body;\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
+#include "safe_iterator.tpp"\r
+#endif\r
--- /dev/null
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // body class implements the aliasing behaviour\r
+\r
+ template<typename O, typename N>\r
+ class safe_iterator_body\r
+ {\r
+ private:\r
+ const O* m_owner;\r
+ N* m_node;\r
+ unsigned m_count;\r
+\r
+ public:\r
+\r
+ safe_iterator_body(const O* owner, N* node) throw() : \r
+ m_owner(owner), m_node(node), m_count(1)\r
+ {\r
+// std::cerr << "constructing " \r
+// << std::hex << ((unsigned long)this) \r
+// << " => " << ((unsigned long)m_owner) << ":" << ((unsigned long)m_node)\r
+// << ":" << std::dec << m_count << std::endl;\r
+ }\r
+\r
+ ~safe_iterator_body(void) throw()\r
+ {\r
+// std::cerr << "destroying " \r
+// << std::hex << ((unsigned long)this) \r
+// << " => " << ((unsigned long)m_owner) << ":" << ((unsigned long)m_node)\r
+// << ":" << std::dec << m_count << std::endl;\r
+ m_owner = 0;\r
+ m_node = 0;\r
+ }\r
+\r
+ unsigned count(void) const\r
+ {\r
+ return m_count;\r
+ }\r
+\r
+ void increment(void)\r
+ {\r
+ ++m_count;\r
+// std::cerr << "incremented " \r
+// << std::hex << ((unsigned long)this) \r
+// << " => " << ((unsigned long)m_owner) << ":" << ((unsigned long)m_node)\r
+// << ":" << std::dec << m_count << std::endl;\r
+ }\r
+\r
+ bool decrement(void)\r
+ {\r
+ --m_count;\r
+// std::cerr << "decremented " \r
+// << std::hex << ((unsigned long)this) \r
+// << " => " << ((unsigned long)m_owner) << ":" << ((unsigned long)m_node)\r
+// << ":" << std::dec << m_count << std::endl;\r
+ return m_count == 0;\r
+ }\r
+\r
+ N* node(void) const throw()\r
+ {\r
+ return m_node;\r
+ }\r
+\r
+ const O* owner(void) const throw()\r
+ {\r
+ return m_owner;\r
+ }\r
+\r
+ void change_owner(const O* owner)\r
+ {\r
+ m_owner = owner;\r
+ }\r
+\r
+ bool equal(const safe_iterator_body<O,N>* right) const throw()\r
+ {\r
+// return m_node == right->m_node;\r
+ return compare(right) == 0;\r
+ }\r
+\r
+ int compare(const safe_iterator_body<O,N>* right) const throw()\r
+ {\r
+ return ((long)m_node) - ((long)right->m_node);\r
+ }\r
+\r
+ bool null(void) const throw()\r
+ {\r
+ return m_owner == 0;\r
+ }\r
+\r
+ bool end(void) const throw()\r
+ {\r
+ return m_owner != 0 && m_node == 0;\r
+ }\r
+\r
+ bool valid(void) const throw()\r
+ {\r
+ return m_owner != 0 && m_node != 0;\r
+ }\r
+\r
+ void set_end(void) throw()\r
+ {\r
+ m_node = 0;\r
+ }\r
+\r
+ void set_null(void) throw()\r
+ {\r
+ m_owner = 0;\r
+ m_node = 0;\r
+ }\r
+\r
+ void assert_valid(void) const throw(null_dereference,end_dereference)\r
+ {\r
+ if (null())\r
+ throw null_dereference("stlplus::safe_iterator");\r
+ if (end())\r
+ throw end_dereference("stlplus::safe_iterator");\r
+ }\r
+\r
+ void assert_non_null(void) const throw(null_dereference)\r
+ {\r
+ if (null())\r
+ throw null_dereference("stlplus::safe_iterator");\r
+ }\r
+\r
+ void assert_owner(const O* owner) const throw(wrong_object)\r
+ {\r
+ if (owner != m_owner)\r
+ throw wrong_object("stlplus::safe_iterator");\r
+ }\r
+ };\r
+\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Master Iterator\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ // construct a valid iterator\r
+ template<typename O, typename N>\r
+ master_iterator<O,N>::master_iterator(const O* owner, N* node) throw() :\r
+ m_body(new safe_iterator_body<O,N>(owner,node))\r
+ {\r
+ }\r
+\r
+ // destructor - disconnect all iterators from the node\r
+ // this usually happens when the node is deleted and must invalidate all aliases\r
+ template<typename O, typename N>\r
+ master_iterator<O,N>::~master_iterator(void) throw()\r
+ {\r
+ m_body->set_end();\r
+ if(m_body->decrement())\r
+ {\r
+ delete m_body;\r
+ m_body = 0;\r
+ }\r
+ }\r
+\r
+ // dereference\r
+ template<typename O, typename N>\r
+ N* master_iterator<O,N>::node(void) const throw()\r
+ {\r
+ return m_body->node();\r
+ }\r
+\r
+ template<typename O, typename N>\r
+ const O* master_iterator<O,N>::owner(void) const throw()\r
+ {\r
+ return m_body->owner();\r
+ }\r
+\r
+ // when you move a node from one owner to another, call this on the node's iterator\r
+ // this effectively moves all iterators to the node so that they are owned by the new owner too\r
+ template<typename O, typename N>\r
+ void master_iterator<O,N>::change_owner(const O* owner) throw()\r
+ {\r
+ m_body->change_owner(owner);\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Safe Iterator\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ // construct a null iterator\r
+ // later assignment of a valid iterator to this is done by using step\r
+ template<typename O, typename N>\r
+ safe_iterator<O,N>::safe_iterator(void) throw() : \r
+ m_body(new safe_iterator_body<O,N>(0,0))\r
+ {\r
+ }\r
+\r
+ // construct a valid iterator by aliasing from the owner node's master iterator\r
+ template<typename O, typename N>\r
+ safe_iterator<O,N>::safe_iterator(const master_iterator<O,N>& r) throw() :\r
+ m_body(0)\r
+ {\r
+ m_body = r.m_body;\r
+ m_body->increment();\r
+ }\r
+\r
+ // construct a valid iterator by aliasing from the owner node's master iterator\r
+ template<typename O, typename N>\r
+ safe_iterator<O,N>::safe_iterator(const safe_iterator<O,N>& r) throw() :\r
+ m_body(0)\r
+ {\r
+ m_body = r.m_body;\r
+ m_body->increment();\r
+ }\r
+\r
+ // assignment implements dealiasing followed by aliasing\r
+ template<typename O, typename N>\r
+ safe_iterator<O,N>& safe_iterator<O,N>::operator=(const safe_iterator<O,N>& r) throw()\r
+ {\r
+ if (m_body != r.m_body)\r
+ {\r
+ if (m_body->decrement())\r
+ delete m_body;\r
+ m_body = r.m_body;\r
+ m_body->increment();\r
+ }\r
+ return *this;\r
+ }\r
+\r
+ // destructor - implements dealiasing\r
+ template<typename O, typename N>\r
+ safe_iterator<O,N>::~safe_iterator(void) throw()\r
+ {\r
+ if(m_body->decrement())\r
+ {\r
+ delete m_body;\r
+ m_body = 0;\r
+ }\r
+ }\r
+\r
+\r
+ // increment/decrement operation\r
+ // implements dealiasing followed by aliasing\r
+ template<typename O, typename N>\r
+ void safe_iterator<O,N>::set(const master_iterator<O,N>& r) throw()\r
+ {\r
+ if (m_body != r.m_body)\r
+ {\r
+ if (m_body->decrement())\r
+ delete m_body;\r
+ m_body = r.m_body;\r
+ m_body->increment();\r
+ }\r
+ }\r
+\r
+ // dereference\r
+ template<typename O, typename N>\r
+ N* safe_iterator<O,N>::node(void) const throw()\r
+ {\r
+ return m_body->node();\r
+ }\r
+\r
+ template<typename O, typename N>\r
+ const O* safe_iterator<O,N>::owner(void) const throw()\r
+ {\r
+ return m_body->owner();\r
+ }\r
+\r
+ // change to a null iterator - i.e. one that doees not belong to any object\r
+ // this does not affect any other iterators pointing to the same node\r
+ template<typename O, typename N>\r
+ void safe_iterator<O,N>::set_null(void) throw()\r
+ {\r
+ if (m_body->count() == 1)\r
+ {\r
+ // no aliases, so just make this null\r
+ m_body->set_null();\r
+ }\r
+ else\r
+ {\r
+ // create a new body which is null so as not to affect any other aliases\r
+ m_body->decrement();\r
+ m_body = new safe_iterator_body<O,N>(0,0);\r
+ }\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // operations for clients that do not have a master end iterator\r
+ // alternatively, have a master end iterator as part of the container\r
+ // and call constructor(master_end) or step(master_end)\r
+\r
+ // construct an end iterator\r
+ template<typename O, typename N>\r
+ safe_iterator<O,N>::safe_iterator(const O* owner) throw() :\r
+ m_body(new safe_iterator_body<O,N>(owner,0))\r
+ {\r
+ }\r
+\r
+ // change to an end iterator - e.g. as a result of incrementing off the end\r
+ template<typename O, typename N>\r
+ void safe_iterator<O,N>::set_end(void) throw()\r
+ {\r
+ if (m_body->count() == 1)\r
+ {\r
+ // no aliases, so just make this an end iterator\r
+ m_body->set_end();\r
+ }\r
+ else\r
+ {\r
+ // create a new body which is null so as not to affect any other aliases\r
+ m_body->decrement();\r
+ m_body = new safe_iterator_body<O,N>(owner(),0);\r
+ }\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // tests\r
+\r
+ // comparison\r
+ template<typename O, typename N>\r
+ bool safe_iterator<O,N>::equal(const safe_iterator<O,N>& right) const throw()\r
+ {\r
+ return compare(right) == 0;\r
+ }\r
+\r
+ template<typename O, typename N>\r
+ int safe_iterator<O,N>::compare(const safe_iterator<O,N>& right) const throw()\r
+ {\r
+ if (m_body == right.m_body) return 0;\r
+ return m_body->compare(right.m_body);\r
+ }\r
+\r
+ // a null iterator is one that has not been initialised with a value yet\r
+ template<typename O, typename N>\r
+ bool safe_iterator<O,N>::null(void) const throw()\r
+ {\r
+ return m_body->null();\r
+ }\r
+\r
+ // an end iterator is one that points to the end element of the list of nodes\r
+ template<typename O, typename N>\r
+ bool safe_iterator<O,N>::end(void) const throw()\r
+ {\r
+ return m_body->end();\r
+ }\r
+\r
+ // a valid iterator is one that can be dereferenced\r
+ template<typename O, typename N>\r
+ bool safe_iterator<O,N>::valid(void) const throw()\r
+ {\r
+ return m_body->valid();\r
+ }\r
+\r
+ // check the rules for a valid iterator that can be dereferenced\r
+ template<typename O, typename N>\r
+ void safe_iterator<O,N>::assert_valid(void) const throw(null_dereference,end_dereference)\r
+ {\r
+ m_body->assert_valid();\r
+ }\r
+\r
+ template<typename O, typename N>\r
+ void safe_iterator<O,N>::assert_valid(const O* owner) const throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ m_body->assert_valid();\r
+ m_body->assert_owner(owner);\r
+ }\r
+\r
+ template<typename O, typename N>\r
+ void safe_iterator<O,N>::assert_non_null(void) const throw(null_dereference)\r
+ {\r
+ m_body->assert_non_null();\r
+ }\r
+\r
+ template<typename O, typename N>\r
+ void safe_iterator<O,N>::assert_owner(const O* owner) const throw(wrong_object)\r
+ {\r
+ m_body->assert_owner(owner);\r
+ }\r
+\r
+} // end namespace stlplus\r
--- /dev/null
+#ifndef STLPLUS_SMART_PTR\r
+#define STLPLUS_SMART_PTR\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+// A smart pointer is a memory-managing pointer to an object. If you like, it\r
+// is a zero-dimensional container. \r
+\r
+// Assignment of smart pointers result in multiple aliases of the same object.\r
+// The term alias is used to differentiate from conventional pointers because\r
+// the semantics are different.\r
+\r
+// Aliases can be turned into copies if the pointed-to class supports copying.\r
+\r
+// The base class is smart_ptr_base which defines the common interface. Then\r
+// there are three subclasses which have the same interface but different copy\r
+// semantics:\r
+\r
+// - smart_ptr for simple types and classes which have copy constructors\r
+// - smart_ptr_clone for polymorphic class hierarchies which are copied using a clone method\r
+// - smart_ptr_nocopy for any class that cannot or should not be copied\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include "containers_fixes.hpp"\r
+#include "exceptions.hpp"\r
+#include <map>\r
+#include <string>\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // internals\r
+\r
+ template<typename T> class smart_ptr_holder;\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Base class\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename T, typename C>\r
+ class smart_ptr_base\r
+ {\r
+ public:\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // member type definitions\r
+\r
+ typedef T value_type;\r
+ typedef T& reference;\r
+ typedef const T& const_reference;\r
+ typedef C value_copy;\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // constructors and destructors\r
+\r
+ // create a null pointer\r
+ smart_ptr_base(void);\r
+\r
+ // create a pointer containing a *copy* of the object using the template parameter C\r
+ // this copy is taken because the pointer class maintains a dynamically allocated object \r
+ // and the T& may not be (usually is not) dynamically allocated\r
+ explicit smart_ptr_base(const T& data) throw(illegal_copy);\r
+\r
+ // create a pointer containing a dynamically created object\r
+ // Note: the object must be allocated *by the user* with new\r
+ // constructor form - must be called in the form smart_ptr_base<type> x(new type(args))\r
+ explicit smart_ptr_base(T* data);\r
+\r
+ // copy constructor implements aliasing so no copy is made\r
+ explicit smart_ptr_base(const smart_ptr_base<T,C>& r);\r
+\r
+ // destructor decrements the reference count and delete only when the last reference is destroyed\r
+ ~smart_ptr_base(void);\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // logical tests to see if there is anything contained in the pointer since it can be null\r
+\r
+ // there are two forms:explicit and implicit\r
+ // implicit: if(!r) or if(r)\r
+ // explicit: if(r.null()) or if(r.present())\r
+ operator bool(void) const;\r
+ bool operator!(void) const;\r
+ bool present(void) const;\r
+ bool null(void) const;\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // dereference operators and functions\r
+\r
+ // dereference the smart pointer to get the object - use in the form *p1\r
+ T& operator*(void) throw(null_dereference);\r
+ const T& operator*(void) const throw(null_dereference);\r
+\r
+ // used as a prefix to a member access to the contained object e.g. p1->print() calls T::print()\r
+ T* operator->(void) throw(null_dereference);\r
+ const T* operator->(void) const throw(null_dereference);\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // explicit function forms of the above assignment and dereference operators\r
+\r
+ // set the value - note that this does a copy using the C template parameter\r
+ void set_value(const T& data) throw(illegal_copy);\r
+ // get the value\r
+ T& value(void) throw(null_dereference);\r
+ const T& value(void) const throw(null_dereference);\r
+\r
+ // set the pointer\r
+ // deletes the previous pointer and adopts the passed pointer instead\r
+ // Note: the object must be allocated *by the user* with new\r
+ // Warning: it is very easy to break the memory management with this operation\r
+ void set(T* data = 0);\r
+ // get the pointer\r
+ T* pointer(void);\r
+ const T* pointer(void) const;\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // functions to manage aliases\r
+\r
+ // make this an alias of the passed object\r
+ void alias(const smart_ptr_base<T,C>&);\r
+\r
+ // test whether two pointers point to the same object(known as aliasing the object)\r
+ // used in the form if(a.aliases(b))\r
+ bool aliases(const smart_ptr_base<T,C>&) const;\r
+\r
+ // find the number of aliases - used when you need to know whether an\r
+ // object is still referred to from elsewhere (rare!)\r
+ unsigned alias_count(void) const;\r
+\r
+ // delete the object and make the pointer null - does not make it unique\r
+ // first, so all other pointers to this will be null too\r
+ void clear(void);\r
+\r
+ // make the pointer unique and null in one step - does not affect other\r
+ // pointers that were pointing to the same object\r
+ void clear_unique(void);\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // functions that involve copying\r
+\r
+ // these functions use the copy functor passed as the template parameter C\r
+ // to copy the object with the right copy semantics. If the copy functor\r
+ // is no_copy, an exception will be thrown.\r
+\r
+ // make this pointer unique with respect to any other references to the same object\r
+ // if this pointer is already unique, it does nothing - otherwise it copies the object\r
+ void make_unique(void) throw(illegal_copy);\r
+\r
+ // make this pointer a unique copy of the parameter\r
+ // useful for expressions like p1.copy(p2) which makes p1 a pointer to a unique copy of the contents of p2\r
+ void copy(const smart_ptr_base<T,C>&) throw(illegal_copy);\r
+\r
+ protected:\r
+ smart_ptr_holder<T>* m_holder;\r
+\r
+ public:\r
+ // internal use only - had to make them public because they need to be\r
+ // accessed by routines that could not be made friends\r
+ void* handle(void) const;\r
+ void make_alias(void* handle);\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // copy functors implementing the three possible copy semantics\r
+\r
+ // constructor_copy uses the copy constructor of the object - used for simple types\r
+\r
+ template <typename T>\r
+ class constructor_copy\r
+ {\r
+ public:\r
+ T* operator() (const T& from) throw()\r
+ {\r
+ return new T(from);\r
+ }\r
+ };\r
+\r
+ // clone_copy uses the clone method of the object - used for polymorphic types\r
+\r
+ template <typename T>\r
+ class clone_copy\r
+ {\r
+ public:\r
+ T* operator() (const T& from) throw()\r
+ {\r
+ return from.clone();\r
+ }\r
+ };\r
+\r
+ // no_copy throws an exception - used for types that cannot be copied\r
+\r
+ template <typename T>\r
+ class no_copy\r
+ {\r
+ public:\r
+ T* operator() (const T& from) throw(illegal_copy)\r
+ {\r
+ throw illegal_copy("no_copy functor called");\r
+ return 0;\r
+ }\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // smart_ptr for simple types and classes which have copy constructors\r
+\r
+ template <typename T>\r
+ class smart_ptr : public smart_ptr_base<T, constructor_copy<T> >\r
+ {\r
+ public:\r
+ smart_ptr(void) {}\r
+ explicit smart_ptr(const T& data) : smart_ptr_base<T, constructor_copy<T> >(data) {}\r
+ explicit smart_ptr(T* data) : smart_ptr_base<T, constructor_copy<T> >(data) {}\r
+ smart_ptr<T>& operator=(const T& data) {set_value(data); return *this;}\r
+ smart_ptr<T>& operator=(const smart_ptr<T>& r) {alias(r); return *this;}\r
+ ~smart_ptr(void) {}\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // smart_ptr_clone for polymorphic class hierarchies which have a clone method\r
+\r
+ template <typename T>\r
+ class smart_ptr_clone : public smart_ptr_base<T, clone_copy<T> >\r
+ {\r
+ public:\r
+ smart_ptr_clone(void) {}\r
+ explicit smart_ptr_clone(const T& data) : smart_ptr_base<T, clone_copy<T> >(data) {}\r
+ explicit smart_ptr_clone(T* data) : smart_ptr_base<T, clone_copy<T> >(data) {}\r
+ smart_ptr_clone<T>& operator=(const T& data) {set_value(data); return *this;}\r
+ smart_ptr_clone<T>& operator=(const smart_ptr_clone<T>& r) {alias(r); return *this;}\r
+ ~smart_ptr_clone(void) {}\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // smart_ptr_nocopy for any class that cannot or should not be copied\r
+\r
+ template <typename T>\r
+ class smart_ptr_nocopy : public smart_ptr_base<T, no_copy<T> >\r
+ {\r
+ public:\r
+ smart_ptr_nocopy(void) {}\r
+ explicit smart_ptr_nocopy(const T& data) : smart_ptr_base<T, no_copy<T> >(data) {}\r
+ explicit smart_ptr_nocopy(T* data) : smart_ptr_base<T, no_copy<T> >(data) {}\r
+ smart_ptr_nocopy<T>& operator=(const T& data) {set_value(data); return *this;}\r
+ smart_ptr_nocopy<T>& operator=(const smart_ptr_nocopy<T>& r) {alias(r); return *this;}\r
+ ~smart_ptr_nocopy(void) {}\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
+#include "smart_ptr.tpp"\r
+#endif\r
--- /dev/null
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // internal holder data structure\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename T>\r
+ class smart_ptr_holder\r
+ {\r
+ private:\r
+ unsigned m_count;\r
+ T* m_data;\r
+\r
+ // make these private to disallow copying because the holder doesn't know how to copy\r
+ smart_ptr_holder(const smart_ptr_holder& s) :\r
+ m_count(0), m_data(0)\r
+ {\r
+ }\r
+\r
+ smart_ptr_holder& operator=(const smart_ptr_holder& s)\r
+ {\r
+ return *this;\r
+ }\r
+\r
+ public:\r
+ smart_ptr_holder(T* p = 0) : \r
+ m_count(1), m_data(p)\r
+ {\r
+ }\r
+\r
+ ~smart_ptr_holder(void)\r
+ {\r
+ clear();\r
+ }\r
+\r
+ unsigned count(void) const\r
+ {\r
+ return m_count;\r
+ }\r
+\r
+ void increment(void)\r
+ {\r
+ ++m_count;\r
+ }\r
+\r
+ bool decrement(void)\r
+ {\r
+ --m_count;\r
+ return m_count == 0;\r
+ }\r
+\r
+ bool null(void)\r
+ {\r
+ return m_data == 0;\r
+ }\r
+\r
+ void clear(void)\r
+ {\r
+ if(m_data)\r
+ delete m_data;\r
+ m_data = 0;\r
+ }\r
+\r
+ void set(T* p = 0)\r
+ {\r
+ clear();\r
+ m_data = p;\r
+ }\r
+\r
+ T*& pointer(void)\r
+ {\r
+ return m_data;\r
+ }\r
+\r
+ const T* pointer(void) const\r
+ {\r
+ return m_data;\r
+ }\r
+\r
+ T& value(void)\r
+ {\r
+ return *m_data;\r
+ }\r
+\r
+ const T& value(void) const\r
+ {\r
+ return *m_data;\r
+ }\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // smart_ptr_base class\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // constructors, assignments and destructors\r
+\r
+ // create a null pointer\r
+ template <typename T, typename C>\r
+ smart_ptr_base<T,C>::smart_ptr_base(void) :\r
+ m_holder(new smart_ptr_holder<T>)\r
+ {\r
+ }\r
+\r
+ // create a pointer containing a *copy* of the object pointer\r
+ template <typename T, typename C>\r
+ smart_ptr_base<T,C>::smart_ptr_base(const T& data) throw(illegal_copy) :\r
+ m_holder(new smart_ptr_holder<T>)\r
+ {\r
+ m_holder->set(C()(data));\r
+ }\r
+\r
+ // create a pointer containing a dynamically created object\r
+ // Note: the object must be allocated *by the user* with new\r
+ // constructor form - must be called in the form smart_ptr<type> x(new type(args))\r
+ template <typename T, typename C>\r
+ smart_ptr_base<T,C>::smart_ptr_base(T* data) :\r
+ m_holder(new smart_ptr_holder<T>)\r
+ {\r
+ m_holder->set(data);\r
+ }\r
+\r
+ // copy constructor implements counted referencing - no copy is made\r
+ template <typename T, typename C>\r
+ smart_ptr_base<T,C>::smart_ptr_base(const smart_ptr_base<T,C>& r) :\r
+ m_holder(0)\r
+ {\r
+ m_holder = r.m_holder;\r
+ m_holder->increment();\r
+ }\r
+\r
+ // destructor decrements the reference count and delete only when the last reference is destroyed\r
+ template <typename T, typename C>\r
+ smart_ptr_base<T,C>::~smart_ptr_base(void)\r
+ {\r
+ if(m_holder->decrement())\r
+ delete m_holder;\r
+ }\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // logical tests to see if there is anything contained in the pointer since it can be null\r
+\r
+ template <typename T, typename C>\r
+ bool smart_ptr_base<T,C>::null(void) const\r
+ {\r
+ return m_holder->null();\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ bool smart_ptr_base<T,C>::present(void) const\r
+ {\r
+ return !m_holder->null();\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ bool smart_ptr_base<T,C>::operator!(void) const\r
+ {\r
+ return m_holder->null();\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ smart_ptr_base<T,C>::operator bool(void) const\r
+ {\r
+ return !m_holder->null();\r
+ }\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // dereference operators and functions\r
+\r
+ template <typename T, typename C>\r
+ T& smart_ptr_base<T,C>::operator*(void) throw(null_dereference)\r
+ {\r
+ if (m_holder->null()) throw null_dereference("null pointer dereferenced in smart_ptr::operator*");\r
+ return m_holder->value();\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ const T& smart_ptr_base<T,C>::operator*(void) const throw(null_dereference)\r
+ {\r
+ if (m_holder->null()) throw null_dereference("null pointer dereferenced in smart_ptr::operator*");\r
+ return m_holder->value();\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ T* smart_ptr_base<T,C>::operator->(void) throw(null_dereference)\r
+ {\r
+ if (m_holder->null()) throw null_dereference("null pointer dereferenced in smart_ptr::operator->");\r
+ return m_holder->pointer();\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ const T* smart_ptr_base<T,C>::operator->(void) const throw(null_dereference)\r
+ {\r
+ if (m_holder->null()) throw null_dereference("null pointer dereferenced in smart_ptr::operator->");\r
+ return m_holder->pointer();\r
+ }\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // explicit function forms of the above assignment dereference operators\r
+\r
+ template <typename T, typename C>\r
+ void smart_ptr_base<T,C>::set_value(const T& data) throw(illegal_copy)\r
+ {\r
+ m_holder->set(C()(data));\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ T& smart_ptr_base<T,C>::value(void) throw(null_dereference)\r
+ {\r
+ if (m_holder->null()) throw null_dereference("null pointer dereferenced in smart_ptr::value");\r
+ return m_holder->value();\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ const T& smart_ptr_base<T,C>::value(void) const throw(null_dereference)\r
+ {\r
+ if (m_holder->null()) throw null_dereference("null pointer dereferenced in smart_ptr::value");\r
+ return m_holder->value();\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ void smart_ptr_base<T,C>::set(T* data)\r
+ {\r
+ m_holder->set(data);\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ T* smart_ptr_base<T,C>::pointer(void)\r
+ {\r
+ return m_holder->pointer();\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ const T* smart_ptr_base<T,C>::pointer(void) const\r
+ {\r
+ return m_holder->pointer();\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // functions to manage counted referencing\r
+\r
+ // make this an alias of the passed object\r
+ template <typename T, typename C>\r
+ void smart_ptr_base<T,C>::alias(const smart_ptr_base<T,C>& r)\r
+ {\r
+ // make it alias-copy safe - this means that I don't try to do the\r
+ // assignment if r is either the same object or an alias of it\r
+ // if (m_holder == r.m_holder) return;\r
+ // if (m_holder->decrement())\r
+ // delete m_holder;\r
+ // m_holder = r.m_holder;\r
+ // m_holder->increment();\r
+ make_alias(r.m_holder);\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ bool smart_ptr_base<T,C>::aliases(const smart_ptr_base<T,C>& r) const\r
+ {\r
+ return m_holder == r.m_holder;\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ unsigned smart_ptr_base<T,C>::alias_count(void) const\r
+ {\r
+ return m_holder->count();\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ void smart_ptr_base<T,C>::clear(void)\r
+ {\r
+ m_holder->clear();\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ void smart_ptr_base<T,C>::clear_unique(void)\r
+ {\r
+ if (m_holder->count() == 1)\r
+ m_holder->clear();\r
+ else\r
+ {\r
+ m_holder->decrement();\r
+ m_holder = 0;\r
+ m_holder = new smart_ptr_holder<T>;\r
+ }\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ void smart_ptr_base<T,C>::make_unique(void) throw(illegal_copy)\r
+ {\r
+ if (m_holder->count() > 1)\r
+ {\r
+ smart_ptr_holder<T>* old_holder = m_holder;\r
+ m_holder->decrement();\r
+ m_holder = 0;\r
+ m_holder = new smart_ptr_holder<T>;\r
+ if (old_holder->pointer())\r
+ m_holder->set(C()(old_holder->value()));\r
+ }\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ void smart_ptr_base<T,C>::copy(const smart_ptr_base<T,C>& data) throw(illegal_copy)\r
+ {\r
+ alias(data);\r
+ make_unique();\r
+ }\r
+\r
+ // internal function for distinguishing unique smart_ptr objects\r
+ // used for example in persistence routines\r
+\r
+ template <typename T, typename C>\r
+ void* smart_ptr_base<T,C>::handle(void) const\r
+ {\r
+ return m_holder;\r
+ }\r
+\r
+ template <typename T, typename C>\r
+ void smart_ptr_base<T,C>::make_alias(void* handle)\r
+ {\r
+ smart_ptr_holder<T>* r_holder = (smart_ptr_holder<T>*)handle;\r
+ if (m_holder != r_holder)\r
+ {\r
+ if (m_holder->decrement())\r
+ delete m_holder;\r
+ m_holder = r_holder;\r
+ m_holder->increment();\r
+ }\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
--- /dev/null
+#ifndef STLPLUS_TRIPLE\r
+#define STLPLUS_TRIPLE\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton, from an original by Dan Milton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+// Similar to the STL pair but with three elements\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include "containers_fixes.hpp"\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // the triple class\r
+\r
+ template<typename T1, typename T2, typename T3>\r
+ struct triple\r
+ {\r
+ typedef T1 first_type;\r
+ typedef T2 second_type;\r
+ typedef T3 third_type;\r
+\r
+ T1 first;\r
+ T2 second;\r
+ T3 third;\r
+\r
+ triple(void);\r
+ triple(const T1& p1, const T2& p2, const T3& p3);\r
+ triple(const triple<T1,T2,T3>& t2);\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // creation\r
+\r
+ template<typename T1, typename T2, typename T3>\r
+ triple<T1,T2,T3> make_triple(const T1& first, const T2& second, const T3& third);\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // comparison\r
+\r
+ template<typename T1, typename T2, typename T3>\r
+ bool operator == (const triple<T1,T2,T3>& left, const triple<T1,T2,T3>& right);\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
+#include "triple.tpp"\r
+#endif\r
--- /dev/null
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton, from an original by Dan Milton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // the triple class\r
+\r
+ template<typename T1, typename T2, typename T3>\r
+ triple<T1,T2,T3>::triple(void) :\r
+ first(), second(), third()\r
+ {\r
+ }\r
+\r
+ template<typename T1, typename T2, typename T3>\r
+ triple<T1,T2,T3>::triple(const T1& p1, const T2& p2, const T3& p3) :\r
+ first(p1), second(p2), third(p3)\r
+ {\r
+ }\r
+\r
+ template<typename T1, typename T2, typename T3>\r
+ triple<T1,T2,T3>::triple(const triple<T1,T2,T3>& t2) :\r
+ first(t2.first), second(t2.second), third(t2.third)\r
+ {\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // creation\r
+\r
+ template<typename T1, typename T2, typename T3>\r
+ triple<T1,T2,T3> make_triple(const T1& first, const T2& second, const T3& third)\r
+ {\r
+ return triple<T1,T2,T3>(first,second,third);\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // comparison\r
+\r
+ template<typename T1, typename T2, typename T3>\r
+ bool operator == (const triple<T1,T2,T3>& left, const triple<T1,T2,T3>& right)\r
+ {\r
+ // triples are equal if all elements are equal\r
+ return left.first == right.first && left.second == right.second && left.third == right.third;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
{
delete someChar;
delete font;
+ delete testScene;
Mf::Dispatcher::instance().removeHandler(this);
}
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);
}
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);
/*
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 <Moof/Tree.hh>
+
+
int main(int argc, char* argv[])
{
std::cout << PACKAGE_STRING << std::endl
int status = 0;
+ //Mf::Tree<int>::Ptr rootNode;
+ //Mf::Tree<int>::Ptr temp, temp2, temp3;
+
+ //rootNode = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(1));
+
+ //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(2));
+ //temp3 = temp;
+ //rootNode->addChild(temp);
+
+ //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(3));
+ //temp2 = temp;
+ //rootNode->addChild(temp);
+
+ //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(4));
+ //rootNode->addChild(temp);
+
+ //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(5));
+ //temp2->addChild(temp);
+
+ //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(6));
+ //temp2->addChild(temp);
+
+ //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(7));
+ //temp3->addChild(temp);
+
+ //temp = rootNode;
+ //while (temp)
+ //{
+ //temp->print();
+ //temp = temp->getNext();
+ //}
+ //return 0;
+
try
{
YoinkApp app(argc, argv);
projects / chaz / yoink / commitdiff
