cleanup stlplus files
authorCharles McGarvey <chazmcgarvey@brokenzipper.com>
Mon, 14 Jun 2010 22:13:37 +0000 (16:13 -0600)
committerCharles McGarvey <chazmcgarvey@brokenzipper.com>
Mon, 14 Jun 2010 22:13:37 +0000 (16:13 -0600)
245 files changed:
src/stlplus/README.txt [deleted file]
src/stlplus/containers/containers.hpp
src/stlplus/containers/containers_fixes.hpp
src/stlplus/containers/copy_functors.hpp
src/stlplus/containers/digraph.hpp
src/stlplus/containers/digraph.tpp
src/stlplus/containers/exceptions.hpp
src/stlplus/containers/foursome.hpp
src/stlplus/containers/foursome.tpp
src/stlplus/containers/hash.hpp
src/stlplus/containers/hash.tpp
src/stlplus/containers/matrix.hpp
src/stlplus/containers/matrix.tpp
src/stlplus/containers/ntree.hpp
src/stlplus/containers/ntree.tpp
src/stlplus/containers/safe_iterator.hpp
src/stlplus/containers/safe_iterator.tpp
src/stlplus/containers/simple_ptr.hpp
src/stlplus/containers/simple_ptr.tpp
src/stlplus/containers/smart_ptr.hpp
src/stlplus/containers/smart_ptr.tpp
src/stlplus/containers/triple.hpp
src/stlplus/containers/triple.tpp
src/stlplus/messages/stlplus_messages.txt [deleted file]
src/stlplus/persistence/persistence.hpp [deleted file]
src/stlplus/persistence/persistence_fixes.hpp [deleted file]
src/stlplus/persistence/persistent.hpp [deleted file]
src/stlplus/persistence/persistent_basic.hpp [deleted file]
src/stlplus/persistence/persistent_bitset.hpp [deleted file]
src/stlplus/persistence/persistent_bitset.tpp [deleted file]
src/stlplus/persistence/persistent_bool.cpp [deleted file]
src/stlplus/persistence/persistent_bool.hpp [deleted file]
src/stlplus/persistence/persistent_callback.hpp [deleted file]
src/stlplus/persistence/persistent_callback.tpp [deleted file]
src/stlplus/persistence/persistent_complex.hpp [deleted file]
src/stlplus/persistence/persistent_complex.tpp [deleted file]
src/stlplus/persistence/persistent_contexts.cpp [deleted file]
src/stlplus/persistence/persistent_contexts.hpp [deleted file]
src/stlplus/persistence/persistent_cstring.cpp [deleted file]
src/stlplus/persistence/persistent_cstring.hpp [deleted file]
src/stlplus/persistence/persistent_deque.hpp [deleted file]
src/stlplus/persistence/persistent_deque.tpp [deleted file]
src/stlplus/persistence/persistent_digraph.hpp [deleted file]
src/stlplus/persistence/persistent_digraph.tpp [deleted file]
src/stlplus/persistence/persistent_enum.hpp [deleted file]
src/stlplus/persistence/persistent_enum.tpp [deleted file]
src/stlplus/persistence/persistent_exceptions.cpp [deleted file]
src/stlplus/persistence/persistent_exceptions.hpp [deleted file]
src/stlplus/persistence/persistent_float.cpp [deleted file]
src/stlplus/persistence/persistent_float.hpp [deleted file]
src/stlplus/persistence/persistent_foursome.hpp [deleted file]
src/stlplus/persistence/persistent_foursome.tpp [deleted file]
src/stlplus/persistence/persistent_hash.hpp [deleted file]
src/stlplus/persistence/persistent_hash.tpp [deleted file]
src/stlplus/persistence/persistent_inf.cpp [deleted file]
src/stlplus/persistence/persistent_inf.hpp [deleted file]
src/stlplus/persistence/persistent_int.cpp [deleted file]
src/stlplus/persistence/persistent_int.hpp [deleted file]
src/stlplus/persistence/persistent_interface.hpp [deleted file]
src/stlplus/persistence/persistent_interface.tpp [deleted file]
src/stlplus/persistence/persistent_list.hpp [deleted file]
src/stlplus/persistence/persistent_list.tpp [deleted file]
src/stlplus/persistence/persistent_map.hpp [deleted file]
src/stlplus/persistence/persistent_map.tpp [deleted file]
src/stlplus/persistence/persistent_matrix.hpp [deleted file]
src/stlplus/persistence/persistent_matrix.tpp [deleted file]
src/stlplus/persistence/persistent_multimap.hpp [deleted file]
src/stlplus/persistence/persistent_multimap.tpp [deleted file]
src/stlplus/persistence/persistent_multiset.hpp [deleted file]
src/stlplus/persistence/persistent_multiset.tpp [deleted file]
src/stlplus/persistence/persistent_ntree.hpp [deleted file]
src/stlplus/persistence/persistent_ntree.tpp [deleted file]
src/stlplus/persistence/persistent_pair.hpp [deleted file]
src/stlplus/persistence/persistent_pair.tpp [deleted file]
src/stlplus/persistence/persistent_pointer.hpp [deleted file]
src/stlplus/persistence/persistent_pointer.tpp [deleted file]
src/stlplus/persistence/persistent_pointers.hpp [deleted file]
src/stlplus/persistence/persistent_set.hpp [deleted file]
src/stlplus/persistence/persistent_set.tpp [deleted file]
src/stlplus/persistence/persistent_shortcuts.hpp [deleted file]
src/stlplus/persistence/persistent_shortcuts.tpp [deleted file]
src/stlplus/persistence/persistent_simple_ptr.hpp [deleted file]
src/stlplus/persistence/persistent_simple_ptr.tpp [deleted file]
src/stlplus/persistence/persistent_smart_ptr.hpp [deleted file]
src/stlplus/persistence/persistent_smart_ptr.tpp [deleted file]
src/stlplus/persistence/persistent_stl.hpp [deleted file]
src/stlplus/persistence/persistent_stlplus.hpp [deleted file]
src/stlplus/persistence/persistent_string.cpp [deleted file]
src/stlplus/persistence/persistent_string.hpp [deleted file]
src/stlplus/persistence/persistent_string.tpp [deleted file]
src/stlplus/persistence/persistent_triple.hpp [deleted file]
src/stlplus/persistence/persistent_triple.tpp [deleted file]
src/stlplus/persistence/persistent_vector.cpp [deleted file]
src/stlplus/persistence/persistent_vector.hpp [deleted file]
src/stlplus/persistence/persistent_vector.tpp [deleted file]
src/stlplus/persistence/persistent_xref.hpp [deleted file]
src/stlplus/persistence/persistent_xref.tpp [deleted file]
src/stlplus/portability/build.cpp
src/stlplus/portability/build.hpp
src/stlplus/portability/debug.cpp
src/stlplus/portability/debug.hpp
src/stlplus/portability/dprintf.cpp
src/stlplus/portability/dprintf.hpp
src/stlplus/portability/dynaload.cpp
src/stlplus/portability/dynaload.hpp
src/stlplus/portability/file_system.cpp
src/stlplus/portability/file_system.hpp
src/stlplus/portability/inf.cpp
src/stlplus/portability/inf.hpp
src/stlplus/portability/ip_sockets.cpp
src/stlplus/portability/ip_sockets.hpp
src/stlplus/portability/portability.hpp
src/stlplus/portability/portability_exceptions.hpp
src/stlplus/portability/portability_fixes.cpp
src/stlplus/portability/portability_fixes.hpp
src/stlplus/portability/subprocesses.cpp
src/stlplus/portability/subprocesses.hpp
src/stlplus/portability/tcp.hpp
src/stlplus/portability/tcp_sockets.cpp
src/stlplus/portability/tcp_sockets.hpp
src/stlplus/portability/time.cpp
src/stlplus/portability/time.hpp
src/stlplus/portability/udp_sockets.cpp
src/stlplus/portability/udp_sockets.hpp
src/stlplus/portability/version.cpp
src/stlplus/portability/version.hpp
src/stlplus/portability/wildcard.cpp
src/stlplus/portability/wildcard.hpp
src/stlplus/strings/format_types.hpp
src/stlplus/strings/print_address.cpp
src/stlplus/strings/print_address.hpp
src/stlplus/strings/print_basic.hpp
src/stlplus/strings/print_bitset.hpp
src/stlplus/strings/print_bitset.tpp
src/stlplus/strings/print_bool.cpp
src/stlplus/strings/print_bool.hpp
src/stlplus/strings/print_cstring.cpp
src/stlplus/strings/print_cstring.hpp
src/stlplus/strings/print_digraph.hpp
src/stlplus/strings/print_digraph.tpp
src/stlplus/strings/print_float.cpp
src/stlplus/strings/print_float.hpp
src/stlplus/strings/print_foursome.hpp
src/stlplus/strings/print_foursome.tpp
src/stlplus/strings/print_hash.hpp
src/stlplus/strings/print_hash.tpp
src/stlplus/strings/print_inf.cpp
src/stlplus/strings/print_inf.hpp
src/stlplus/strings/print_int.cpp
src/stlplus/strings/print_int.hpp
src/stlplus/strings/print_list.hpp
src/stlplus/strings/print_list.tpp
src/stlplus/strings/print_map.hpp
src/stlplus/strings/print_map.tpp
src/stlplus/strings/print_matrix.hpp
src/stlplus/strings/print_matrix.tpp
src/stlplus/strings/print_ntree.hpp
src/stlplus/strings/print_ntree.tpp
src/stlplus/strings/print_pair.hpp
src/stlplus/strings/print_pair.tpp
src/stlplus/strings/print_pointer.hpp
src/stlplus/strings/print_pointer.tpp
src/stlplus/strings/print_sequence.hpp
src/stlplus/strings/print_sequence.tpp
src/stlplus/strings/print_set.hpp
src/stlplus/strings/print_set.tpp
src/stlplus/strings/print_simple_ptr.hpp
src/stlplus/strings/print_simple_ptr.tpp
src/stlplus/strings/print_smart_ptr.hpp
src/stlplus/strings/print_smart_ptr.tpp
src/stlplus/strings/print_stl.hpp
src/stlplus/strings/print_stlplus.hpp
src/stlplus/strings/print_string.cpp
src/stlplus/strings/print_string.hpp
src/stlplus/strings/print_triple.hpp
src/stlplus/strings/print_triple.tpp
src/stlplus/strings/print_vector.cpp
src/stlplus/strings/print_vector.hpp
src/stlplus/strings/print_vector.tpp
src/stlplus/strings/string_address.cpp
src/stlplus/strings/string_address.hpp
src/stlplus/strings/string_basic.hpp
src/stlplus/strings/string_bitset.hpp
src/stlplus/strings/string_bitset.tpp
src/stlplus/strings/string_bool.cpp
src/stlplus/strings/string_bool.hpp
src/stlplus/strings/string_cstring.cpp
src/stlplus/strings/string_cstring.hpp
src/stlplus/strings/string_digraph.hpp
src/stlplus/strings/string_digraph.tpp
src/stlplus/strings/string_float.cpp
src/stlplus/strings/string_float.hpp
src/stlplus/strings/string_foursome.hpp
src/stlplus/strings/string_foursome.tpp
src/stlplus/strings/string_hash.hpp
src/stlplus/strings/string_hash.tpp
src/stlplus/strings/string_inf.cpp
src/stlplus/strings/string_inf.hpp
src/stlplus/strings/string_int.cpp
src/stlplus/strings/string_int.hpp
src/stlplus/strings/string_list.hpp
src/stlplus/strings/string_list.tpp
src/stlplus/strings/string_map.hpp
src/stlplus/strings/string_map.tpp
src/stlplus/strings/string_matrix.hpp
src/stlplus/strings/string_matrix.tpp
src/stlplus/strings/string_ntree.hpp
src/stlplus/strings/string_ntree.tpp
src/stlplus/strings/string_pair.hpp
src/stlplus/strings/string_pair.tpp
src/stlplus/strings/string_pointer.hpp
src/stlplus/strings/string_pointer.tpp
src/stlplus/strings/string_sequence.hpp
src/stlplus/strings/string_sequence.tpp
src/stlplus/strings/string_set.hpp
src/stlplus/strings/string_set.tpp
src/stlplus/strings/string_simple_ptr.hpp
src/stlplus/strings/string_simple_ptr.tpp
src/stlplus/strings/string_smart_ptr.hpp
src/stlplus/strings/string_smart_ptr.tpp
src/stlplus/strings/string_stl.hpp
src/stlplus/strings/string_stlplus.hpp
src/stlplus/strings/string_string.cpp
src/stlplus/strings/string_string.hpp
src/stlplus/strings/string_triple.hpp
src/stlplus/strings/string_triple.tpp
src/stlplus/strings/string_utilities.cpp
src/stlplus/strings/string_utilities.hpp
src/stlplus/strings/string_vector.cpp
src/stlplus/strings/string_vector.hpp
src/stlplus/strings/string_vector.tpp
src/stlplus/strings/strings.hpp
src/stlplus/strings/strings_fixes.hpp
src/stlplus/subsystems/cli_parser.cpp [deleted file]
src/stlplus/subsystems/cli_parser.hpp [deleted file]
src/stlplus/subsystems/ini_manager.cpp [deleted file]
src/stlplus/subsystems/ini_manager.hpp [deleted file]
src/stlplus/subsystems/library_manager.cpp [deleted file]
src/stlplus/subsystems/library_manager.hpp [deleted file]
src/stlplus/subsystems/message_handler.cpp [deleted file]
src/stlplus/subsystems/message_handler.hpp [deleted file]
src/stlplus/subsystems/subsystems.hpp [deleted file]
src/stlplus/subsystems/subsystems_fixes.hpp [deleted file]
src/stlplus/subsystems/timer.cpp [deleted file]
src/stlplus/subsystems/timer.hpp [deleted file]

diff --git a/src/stlplus/README.txt b/src/stlplus/README.txt
deleted file mode 100644 (file)
index dad518e..0000000
+++ /dev/null
@@ -1,19 +0,0 @@
-This directory is for implementing STLplus as a library collection. The\r
-libraries are to be found in the directories:\r
-\r
-          containers\r
-          persistence\r
-          portability\r
-          strings\r
-          subsystems\r
-\r
-The documentation is in the 'docs' directory and starts with index.html.\r
-\r
-To build the STLplus3 library collection, use the project files supplied at\r
-this level - 'Makefile' for gcc, 'stlplus3.sln' for Visual Studio 9 (2008),\r
-'stlplus3.dsw' for Visual Studio 6 (and 7 or 8).\r
-\r
-The 'source' directory is provided with script files that allow the library\r
-collection to be merged into one large library - termed the monolithic build.\r
-See source/README.txt for instructions.\r
-\r
index 58637581643849b2d657bd0abde6b4e034a06b02..e99d31382f5586b185d2fc755486d1544177c800 100644 (file)
@@ -1,23 +1,23 @@
-#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
+#ifndef STLPLUS_CONTAINERS
+#define STLPLUS_CONTAINERS
+////////////////////////////////////////////////////////////////////////////////
+
+//   Author:    Andy Rushton
+//   Copyright: (c) Southampton University 1999-2004
+//              (c) Andy Rushton           2004-2009
+//   License:   BSD License, see ../docs/license.html
+
+//   Allows all the STLplus containers to be included in one go
+
+////////////////////////////////////////////////////////////////////////////////
+
+#include "digraph.hpp"
+#include "foursome.hpp"
+#include "hash.hpp"
+#include "matrix.hpp"
+#include "ntree.hpp"
+#include "smart_ptr.hpp"
+#include "triple.hpp"
+
+////////////////////////////////////////////////////////////////////////////////
+#endif
index ad29f99e2ed5908afe8b73a1d2ca74a3c23f3fa3..f244323d279427e2094be08fb88702451276f641 100644 (file)
-#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
-//   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: 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
-//   8026 - Functions with exception specifications are not expanded inline\r
-//   8027 - Functions with xxx are not expanded inline\r
-#pragma warn -8026\r
-#pragma warn -8027\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 <= 1200\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
-// Member templates\r
-// e.g. a template function in a template class\r
-\r
-// Not all compilers support them - this fix can be used to disable member\r
-// templates for compilers that don't. Unfortunately that means that some\r
-// functionality will be missing for those compilers.\r
-\r
-#define STLPLUS_MEMBER_TEMPLATES\r
-\r
-// Visual Studio v6 (compiler version 12) does not support them\r
-#ifdef _MSC_VER\r
-#if _MSC_VER <= 1200\r
-#undef STLPLUS_MEMBER_TEMPLATES\r
-#endif\r
-#endif\r
-\r
-////////////////////////////////////////////////////////////////////////////////\r
-#endif\r
+#ifndef STLPLUS_CONTAINERS_FIXES
+#define STLPLUS_CONTAINERS_FIXES
+////////////////////////////////////////////////////////////////////////////////
+
+//   Author:    Andy Rushton
+//   Copyright: (c) Southampton University 1999-2004
+//              (c) Andy Rushton           2004-2009
+//   License:   BSD License, see ../docs/license.html
+
+//   Contains work arounds for OS or Compiler specific problems with container
+//   templates
+
+////////////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////////////
+// Unnecessary compiler warnings
+////////////////////////////////////////////////////////////////////////////////
+
+#ifdef _MSC_VER
+// Microsoft Visual Studio
+// shut up the following irritating warnings
+//   4786 - VC6, identifier string exceeded maximum allowable length and was truncated (only affects debugger)
+//   4305 - VC6, identifier type was converted to a smaller type
+//   4503 - VC6, decorated name was longer than the maximum the compiler allows (only affects debugger)
+//   4309 - VC6, type conversion operation caused a constant to exceeded the space allocated for it
+//   4290 - VC6, C++ exception specification ignored
+//   4800 - VC6, forcing value to bool 'true' or 'false' (performance warning)
+//   4355 - VC6, 'this' : used in base member initializer list
+//   4675 - VC7.1, "change" in function overload resolution _might_ have altered program
+//   4996 - VC8, 'xxxx' was declared deprecated
+#pragma warning(disable: 4786 4305 4503 4309 4290 4800 4355 4675 4996)
+#endif
+
+#ifdef __BORLANDC__
+// Borland
+// Shut up the following irritating warnings
+//   8026 - Functions with exception specifications are not expanded inline
+//   8027 - Functions with xxx are not expanded inline
+#pragma warn -8026
+#pragma warn -8027
+#endif
+
+////////////////////////////////////////////////////////////////////////////////
+// Problems with the typename keyword
+////////////////////////////////////////////////////////////////////////////////
+
+// There are problems with using the 'typename' keyword. Technically, if you
+// use a type member of a template class (i.e. a type declared within the
+// template class by a local typedef), you need to tell the compiler that it
+// is a type name. This is because the compiler cannot work out whether a
+// member is a type, a method or a data field at compile time. However,
+// support for the typename keyword has traditionally been incomplete in both
+// gcc and Visual Studio. I have used macros to try to resolve this issue. The
+// macros add the keyword for compiler versions that require it and omit it
+// for compiler versions that do not support it
+
+// There are five places where typename keywords cause problems:
+//
+//   1) in a typedef where a template class's member type is being mapped onto
+//      a type definition within another template class or function 
+//      e.g. template<typename T> fn () {
+//             typedef typename someclass<T>::member_type local_type;
+//                     ^^^^^^^^
+//   2) in a function parameter declaration, with similar rules to the above
+//      e.g. template<typename T> fn (typename someclass<T>::member_type)
+//                                    ^^^^^^^^
+//   3) in instantiating a template, the parameter to the template, with similar rules to the above
+//      e.g. template_class<typename someclass<T>::member_type>
+//                          ^^^^^^^^
+//   4) Return expressions
+//      e.g. return typename ntree<T>::const_iterator(this,m_root);
+//                  ^^^^^^^^
+//   5) Creating temporary objects when passing arguments to a function or constructor
+//      e.g. return typename ntree<T>::const_prefix_iterator(typename ntree<T>::const_iterator(this,m_root));
+//                                                           ^^^^^^^^
+// Note that the typename keyword is only required when the type being referred to is a member of a template class
+//
+// So far it *seems* as if all compilers either require all of them or none of
+// them, so this set of situations can be handled by a single macro
+
+// default values, overridden for individual problem cases below
+#define TYPENAME typename
+
+// GCC 
+//   - pre-version 3 didn't handle typename in any of these cases
+//   - version 3 onwards, typename is required for all three cases as per default
+#ifdef __GNUC__
+#if __GNUC__ < 3
+#undef TYPENAME
+#define TYPENAME
+#endif
+#endif
+
+// Visual Studio
+//   - version 6 (compiler v.12) cannot handle typename in any of these cases
+//   - version 7 (.NET) (compiler v.13) requires a typename in a parameter specification but supports all
+//   - version 8 (2005) (compiler v.14) requires parameters and templates, supports all
+#ifdef _MSC_VER
+#if _MSC_VER <= 1200
+#undef TYPENAME
+#define TYPENAME
+#endif
+#endif
+
+// Borland 
+//   - doesn't handle typename in 5.5, does in 5.82, not sure about other cases
+#ifdef __BORLANDC__
+#if __BORLANDC__ <= 0x550
+#undef TYPENAME
+#define TYPENAME
+#endif
+#endif
+
+////////////////////////////////////////////////////////////////////////////////
+// Member templates
+// e.g. a template function in a template class
+
+// Not all compilers support them - this fix can be used to disable member
+// templates for compilers that don't. Unfortunately that means that some
+// functionality will be missing for those compilers.
+
+#define STLPLUS_MEMBER_TEMPLATES
+
+// Visual Studio v6 (compiler version 12) does not support them
+#ifdef _MSC_VER
+#if _MSC_VER <= 1200
+#undef STLPLUS_MEMBER_TEMPLATES
+#endif
+#endif
+
+////////////////////////////////////////////////////////////////////////////////
+#endif
index c82ee9f0c0f920ab05a280b2f53a3d34925e2566..68f2b21b226a0d382c324552d853859bfe697f2b 100644 (file)
@@ -1,66 +1,66 @@
-#ifndef STLPLUS_COPY_FUNCTORS\r
-#define STLPLUS_COPY_FUNCTORS\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 function constructor classes below are used by the smart_ptr and the\r
-//   simple_ptr classes. They provide three (well ok, two) copying mechanisms.\r
-//   These classes have been separated from the smart_ptr header by DJDM, as\r
-//   the simple_ptr classes now also use them.\r
-\r
-////////////////////////////////////////////////////////////////////////////////\r
-#include "containers_fixes.hpp"\r
-#include "exceptions.hpp"\r
-\r
-namespace stlplus\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
-\r
-} // end namespace stlplus\r
-\r
-#endif\r
+#ifndef STLPLUS_COPY_FUNCTORS
+#define STLPLUS_COPY_FUNCTORS
+////////////////////////////////////////////////////////////////////////////////
+
+//   Author:    Andy Rushton
+//   Copyright: (c) Southampton University 1999-2004
+//              (c) Andy Rushton           2004-2009
+//   License:   BSD License, see ../docs/license.html
+
+//   The function constructor classes below are used by the smart_ptr and the
+//   simple_ptr classes. They provide three (well ok, two) copying mechanisms.
+//   These classes have been separated from the smart_ptr header by DJDM, as
+//   the simple_ptr classes now also use them.
+
+////////////////////////////////////////////////////////////////////////////////
+#include "containers_fixes.hpp"
+#include "exceptions.hpp"
+
+namespace stlplus
+{
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // copy functors implementing the three possible copy semantics
+
+  // constructor_copy uses the copy constructor of the object - used for simple types
+
+  template <typename T>
+  class constructor_copy
+  {
+  public:
+    T* operator() (const T& from) throw()
+      {
+        return new T(from);
+      }
+  };
+
+  // clone_copy uses the clone method of the object - used for polymorphic types
+
+  template <typename T>
+  class clone_copy
+  {
+  public:
+    T* operator() (const T& from) throw()
+      {
+        return from.clone();
+      }
+  };
+
+  // no_copy throws an exception - used for types that cannot be copied
+
+  template <typename T>
+  class no_copy
+  {
+  public:
+    T* operator() (const T& from) throw(illegal_copy)
+      {
+        throw illegal_copy("no_copy functor called");
+        return 0;
+      }
+  };
+
+  ////////////////////////////////////////////////////////////////////////////////
+
+} // end namespace stlplus
+
+#endif
index 8281998d24640512b3b1ddfe94fadcd4b3f9fd1e..7b603c11d0f7c5b87bc8e65fb4552d75b29c9e59 100644 (file)
-#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
+#ifndef STLPLUS_DIGRAPH
+#define STLPLUS_DIGRAPH
+////////////////////////////////////////////////////////////////////////////////
+
+//   Author:    Andy Rushton
+//   Copyright: (c) Southampton University 1999-2004
+//              (c) Andy Rushton           2004-2009
+//   License:   BSD License, see ../docs/license.html
+
+//   STL-style Directed graph template component
+//   Digraph stands for directed-graph, i.e. all arcs have a direction
+
+////////////////////////////////////////////////////////////////////////////////
+#include "containers_fixes.hpp"
+#include "safe_iterator.hpp"
+#include "exceptions.hpp"
+#include <vector>
+#include <map>
+#include <set>
+
+namespace stlplus
+{
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Internals
+
+  template<typename NT, typename AT> class digraph_node;
+  template<typename NT, typename AT> class digraph_arc;
+  template<typename NT, typename AT> class digraph;
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // The Digraph iterator classes
+  // a digraph_iterator points to a node whilst a digraph_arc_iterator points to an arc
+  // Note that these are redefined as:
+  //   digraph<NT,AT>::iterator           - points to a non-const node
+  //   digraph<NT,AT>::const_iterator     - points to a const node
+  //   digraph<NT,AT>::arc_iterator       - points to a non-const arc
+  //   digraph<NT,AT>::const_arc_iterator - points to a const arc
+  // and this is the form in which they should be used
+
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  class digraph_iterator : public safe_iterator<digraph<NT,AT>, digraph_node<NT,AT> >
+  {
+  public:
+    friend class digraph<NT,AT>;
+
+    // local type definitions
+    // an iterator points to an object whilst a const_iterator points to a const object
+    typedef digraph_iterator<NT,AT,NT&,NT*> iterator;
+    typedef digraph_iterator<NT,AT,const NT&,const NT*> const_iterator;
+    typedef digraph_iterator<NT,AT,NRef,NPtr> this_iterator;
+    typedef NRef reference;
+    typedef NPtr pointer;
+
+    // constructor to create a null iterator - you must assign a valid value to this iterator before using it
+    digraph_iterator(void);
+    ~digraph_iterator(void);
+
+    // Type conversion methods allow const_iterator and iterator to be converted
+    // convert an iterator/const_iterator to a const_iterator
+    const_iterator constify(void) const;
+    // convert an iterator/const_iterator to an iterator
+    iterator deconstify(void) const;
+
+    // increment/decrement operators used to step through the set of all nodes in a graph
+    // it is only legal to increment a valid iterator
+    // pre-increment
+    this_iterator& operator ++ (void)
+      throw(null_dereference,end_dereference);
+    // post-increment
+    this_iterator operator ++ (int)
+      throw(null_dereference,end_dereference);
+    // pre-decrement
+    this_iterator& operator -- (void)
+      throw(null_dereference,end_dereference);
+    // post-decrement
+    this_iterator operator -- (int)
+      throw(null_dereference,end_dereference);
+
+    // test useful for testing whether iteration has completed and for inclusion in other containers
+    // Note: this class also inherits the safe_iterator methods: valid(), null(), end()
+    bool operator == (const this_iterator& r) const;
+    bool operator != (const this_iterator& r) const;
+    bool operator < (const this_iterator& r) const;
+
+    // access the node data - a const_iterator gives you a const element, an iterator a non-const element
+    // it is illegal to dereference an invalid (i.e. null or end) iterator
+    reference operator*(void) const
+      throw(null_dereference,end_dereference);
+    pointer operator->(void) const
+      throw(null_dereference,end_dereference);
+
+  public:
+    // constructor used by digraph to create a non-null iterator
+    explicit digraph_iterator(digraph_node<NT,AT>* node);
+    // constructor used by digraph to create an end iterator
+    explicit digraph_iterator(const digraph<NT,AT>* owner);
+    // used to create an alias of an iterator
+    explicit digraph_iterator(const safe_iterator<digraph<NT,AT>, digraph_node<NT,AT> >& iterator);
+  };
+
+  ////////////////////////////////////////////////////////////////////////////////
+
+  template<typename NT, typename AT, typename ARef, typename APtr>
+  class digraph_arc_iterator : public safe_iterator<digraph<NT,AT>, digraph_arc<NT,AT> >
+  {
+  public:
+    friend class digraph<NT,AT>;
+
+    // local type definitions
+    // an iterator points to an object whilst a const_iterator points to a const object
+    typedef digraph_arc_iterator<NT,AT,AT&,AT*> iterator;
+    typedef digraph_arc_iterator<NT,AT,const AT&,const AT*> const_iterator;
+    typedef digraph_arc_iterator<NT,AT,ARef,APtr> this_iterator;
+    typedef ARef reference;
+    typedef APtr pointer;
+
+    // constructor to create a null iterator - you must assign a valid value to this iterator before using it
+    digraph_arc_iterator(void);
+    ~digraph_arc_iterator(void);
+
+    // Type conversion methods allow const_iterator and iterator to be converted
+    // convert an iterator/const_iterator to a const_iterator
+    const_iterator constify(void) const;
+    // convert an iterator/const_iterator to an iterator
+    iterator deconstify(void) const;
+
+    // increment/decrement operators used to step through the set of all nodes in a graph
+    // it is only legal to increment a valid iterator
+    // pre-increment
+    this_iterator& operator ++ (void)
+      throw(null_dereference,end_dereference);
+    // post-increment
+    this_iterator operator ++ (int)
+      throw(null_dereference,end_dereference);
+    // pre-decrement
+    this_iterator& operator -- (void)
+      throw(null_dereference,end_dereference);
+    // post-decrement
+    this_iterator operator -- (int)
+      throw(null_dereference,end_dereference);
+
+    // test useful for testing whether iteration has completed and for inclusion in other containers
+    // Note: this class also inherits the safe_iterator methods: valid(), null(), end()
+    bool operator == (const this_iterator&) const;
+    bool operator != (const this_iterator&) const;
+    bool operator < (const this_iterator&) const;
+
+    // access the node data - a const_iterator gives you a const element, an iterator a non-const element
+    // it is illegal to dereference an invalid (i.e. null or end) iterator
+    reference operator*(void) const
+      throw(null_dereference,end_dereference);
+    pointer operator->(void) const
+      throw(null_dereference,end_dereference);
+
+  public:
+    // constructor used by digraph to create a non-null iterator
+    explicit digraph_arc_iterator(digraph_arc<NT,AT>* arc);
+    // constructor used by digraph to create an end iterator
+    explicit digraph_arc_iterator(const digraph<NT,AT>* owner);
+    // used to create an alias of an iterator
+    explicit digraph_arc_iterator(const safe_iterator<digraph<NT,AT>, digraph_arc<NT,AT> >& iterator);
+  };
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // The Graph class
+  // NT is the Node type and AT is the Arc type
+  ////////////////////////////////////////////////////////////////////////////////
+
+  template<typename NT, typename AT>
+  class digraph
+  {
+  public:
+    // STL-like typedefs for the types and iterators
+    typedef NT node_type;
+    typedef AT arc_type;
+    typedef digraph_iterator<NT,AT,NT&,NT*> iterator;
+    typedef digraph_iterator<NT,AT,const NT&,const NT*> const_iterator;
+    typedef digraph_arc_iterator<NT,AT,AT&,AT*> arc_iterator;
+    typedef digraph_arc_iterator<NT,AT,const AT&,const AT*> const_arc_iterator;
+
+    // supplementary types used throughout
+
+    // a path is represented as a vector of arcs so the forward traversal is
+    // done by going from begin() to end() or 0 to size-1 - of course a backward
+    // traversal can be done by traversing the vector backwards
+    typedef std::vector<arc_iterator> arc_vector;
+    typedef std::vector<const_arc_iterator> const_arc_vector;
+    const_arc_vector constify_arcs(const arc_vector&) const
+      throw(wrong_object,null_dereference,end_dereference);
+    arc_vector deconstify_arcs(const const_arc_vector&) const
+      throw(wrong_object,null_dereference,end_dereference);
+
+    // a path vector is a vector of paths used to represent all the paths from one node to another
+    // there is no particular ordering to the paths in the vector
+    typedef std::vector<arc_vector> path_vector;
+    typedef std::vector<const_arc_vector> const_path_vector;
+    const_path_vector constify_paths(const path_vector&) const
+      throw(wrong_object,null_dereference,end_dereference);
+    path_vector deconstify_paths(const const_path_vector&) const
+      throw(wrong_object,null_dereference,end_dereference);
+
+    // a node vector is a simple vector of nodes used to represent the reachable sets
+    // there is no particular ordering to the nodes in the vector
+    typedef std::vector<iterator> node_vector;
+    typedef std::vector<const_iterator> const_node_vector;
+    const_node_vector constify_nodes(const node_vector&) const
+      throw(wrong_object,null_dereference,end_dereference);
+    node_vector deconstify_nodes(const const_node_vector&) const
+      throw(wrong_object,null_dereference,end_dereference);
+
+    // callback used in the path algorithms to select which arcs to consider
+    typedef bool (*arc_select_fn) (const digraph<NT,AT>&, const_arc_iterator);
+
+    // a value representing an unknown offset
+    // Note that it's static so use in the form digraph<NT,AT>::npos()
+    static unsigned npos(void);
+
+    //////////////////////////////////////////////////////////////////////////
+    // Constructors, destructors and copies
+
+    digraph(void);
+    ~digraph(void);
+
+    // copy constructor and assignment both copy the graph
+    digraph(const digraph<NT,AT>&);
+    digraph<NT,AT>& operator=(const digraph<NT,AT>&);
+
+    //////////////////////////////////////////////////////////////////////////
+    // Basic Node functions
+    // Nodes are referred to by iterators created when the node is inserted.
+    // Iterators remain valid unless the node is erased (they are list iterators, so no resize problems)
+    // It is also possible to walk through all the nodes using a list-like start() to end() loop
+    // Each node has a set of input arcs and output arcs. These are indexed by an unsigned i.e. they form a vector.
+    // The total number of inputs is the fanin and the total number of outputs is the fanout.
+    // The contents of the node (type NT) are accessed, of course, by dereferencing the node iterator.
+
+    // tests for the number of nodes and the special test for zero nodes
+    bool empty(void) const;
+    unsigned size(void) const;
+
+    // add a new node and return its iterator
+    iterator insert(const NT& node_data);
+
+    // remove a node and return the iterator to the next node
+    // erasing a node erases its arcs
+    iterator erase(iterator)
+      throw(wrong_object,null_dereference,end_dereference);
+    // remove all nodes
+    void clear(void);
+
+    // traverse all the nodes in no particular order using STL-style iteration
+    const_iterator begin(void) const;
+    iterator begin(void);
+    const_iterator end(void) const;
+    iterator end(void);
+
+    // access the inputs of this node
+    // the fanin is the number of inputs and the inputs are accessed using an index from 0..fanin-1
+    unsigned fanin(const_iterator) const
+      throw(wrong_object,null_dereference,end_dereference);
+    unsigned fanin(iterator)
+      throw(wrong_object,null_dereference,end_dereference);
+    const_arc_iterator input(const_iterator, unsigned) const
+      throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
+    arc_iterator input(iterator, unsigned)
+      throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
+
+    // access the outputs of this node
+    // the fanout is the number of outputs and the outputs are accessed using an index from 0..fanout-1
+    unsigned fanout(const_iterator) const
+      throw(wrong_object,null_dereference,end_dereference);
+    unsigned fanout(iterator)
+      throw(wrong_object,null_dereference,end_dereference);
+    const_arc_iterator output(const_iterator, unsigned) const
+      throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
+    arc_iterator output(iterator, unsigned)
+      throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
+
+    // convenience routines for getting the set of all inputs or all outputs as vectors
+    const_arc_vector inputs(const_iterator) const
+      throw(wrong_object,null_dereference,end_dereference);
+    arc_vector inputs(iterator)
+      throw(wrong_object,null_dereference,end_dereference);
+    const_arc_vector outputs(const_iterator) const
+      throw(wrong_object,null_dereference,end_dereference);
+    arc_vector outputs(iterator)
+      throw(wrong_object,null_dereference,end_dereference);
+
+    // find the output index of an arc which goes from this node
+    // returns digraph<NT,AT>::npos if the arc is not an output of from
+    unsigned output_offset(const_iterator from, const_arc_iterator arc) const
+      throw(wrong_object,null_dereference,end_dereference);
+    unsigned output_offset(iterator from, arc_iterator arc)
+      throw(wrong_object,null_dereference,end_dereference);
+    // ditto for an input arc
+    unsigned input_offset(const_iterator to, const_arc_iterator arc) const
+      throw(wrong_object,null_dereference,end_dereference);
+    unsigned input_offset(iterator to, arc_iterator arc)
+      throw(wrong_object,null_dereference,end_dereference);
+
+    //////////////////////////////////////////////////////////////////////////
+    // Basic Arc functions
+    // to avoid name conflicts, arc functions have the arc_ prefix 
+    // Arcs, like nodes, are referred to by a list iterator which is returned by the arc_insert function
+    // They may also be visited from arc_begin() to arc_end()
+    // Each arc has a from field and a to field which contain the node iterators of the endpoints of the arc
+    // Of course, the arc data can be accessed by simply dereferencing the iterator
+
+    // tests for the number of arcs and the special test for zero arcs
+    bool arc_empty (void) const;
+    unsigned arc_size(void) const;
+
+    // add a new arc and return its iterator
+    arc_iterator arc_insert(iterator from, iterator to, const AT& arc_data = AT())
+      throw(wrong_object,null_dereference,end_dereference);
+
+    // remove an arc and return the iterator to the next arc
+    arc_iterator arc_erase(arc_iterator)
+      throw(wrong_object,null_dereference,end_dereference);
+    // remove all arcs
+    void arc_clear(void);
+
+    // traverse all the arcs in no particular order using STL-style iteration
+    const_arc_iterator arc_begin(void) const;
+    arc_iterator arc_begin(void);
+    const_arc_iterator arc_end(void) const;
+    arc_iterator arc_end(void);
+
+    // find the node that an arc points from or to
+    const_iterator arc_from(const_arc_iterator) const
+      throw(wrong_object,null_dereference,end_dereference);
+    iterator arc_from(arc_iterator)
+      throw(wrong_object,null_dereference,end_dereference);
+    const_iterator arc_to(const_arc_iterator) const
+      throw(wrong_object,null_dereference,end_dereference);
+    iterator arc_to(arc_iterator)
+      throw(wrong_object,null_dereference,end_dereference);
+
+    // reconnect an arc to a different from and to node
+    void arc_move(arc_iterator arc, iterator from, iterator to)
+      throw(wrong_object,null_dereference,end_dereference);
+    // reconnect just the from node
+    void arc_move_from(arc_iterator arc, iterator from)
+      throw(wrong_object,null_dereference,end_dereference);
+    // reconnect just the to node
+    void arc_move_to(arc_iterator arc, iterator to)
+      throw(wrong_object,null_dereference,end_dereference);
+    // reverse the arc direction so that to becomes from and vice-versa
+    void arc_flip(arc_iterator arc)
+      throw(wrong_object,null_dereference,end_dereference);
+
+    ////////////////////////////////////////////////////////////////////////////////
+    // Adjacency algorithms
+
+    // test whether the nodes are adjacent i.e. whether there is an arc going from from to to
+    bool adjacent(const_iterator from, const_iterator to) const
+      throw(wrong_object,null_dereference,end_dereference);
+    bool adjacent(iterator from, iterator to)
+      throw(wrong_object,null_dereference,end_dereference);
+
+    // as above, but returns the arc that makes the nodes adjacent
+    // returns the first arc if there's more than one, returns arc_end() if there are none
+    const_arc_iterator adjacent_arc(const_iterator from, const_iterator to) const
+      throw(wrong_object,null_dereference,end_dereference);
+    arc_iterator adjacent_arc(iterator from, iterator to)
+      throw(wrong_object,null_dereference,end_dereference);
+
+    // as above, but returns the set of all arcs that make two nodes adjacent (there may be more than one)
+    // returns an empty vector if there are none
+    const_arc_vector adjacent_arcs(const_iterator from, const_iterator to) const
+      throw(wrong_object,null_dereference,end_dereference);
+    arc_vector adjacent_arcs(iterator from, iterator to)
+      throw(wrong_object,null_dereference,end_dereference);
+
+    // return the adjacency sets for the node inputs or outputs, i.e. the set of nodes adjacent to this node
+    // each adjacent node will only be entered once even if there are multiple arcs between the nodes
+    const_node_vector input_adjacencies(const_iterator to) const
+      throw(wrong_object,null_dereference,end_dereference);
+    node_vector input_adjacencies(iterator to)
+      throw(wrong_object,null_dereference,end_dereference);
+    const_node_vector output_adjacencies(const_iterator from) const
+      throw(wrong_object,null_dereference,end_dereference);
+    node_vector output_adjacencies(iterator from)
+      throw(wrong_object,null_dereference,end_dereference);
+
+    ////////////////////////////////////////////////////////////////////////////////
+    // Topographical Sort Algorithm
+    // This generates a node ordering such that each node is visited after its fanin nodes.
+
+    // This only generates a valid ordering for a DAG. 
+
+    // The return value is a pair : 
+    //  - the node vector which is a set of iterators to the nodes in sorted order
+    //  - the arc vector is the set of backward ards that were broken to achieve the sort
+    // If the arc vector is empty then the graph formed a DAG.
+
+    // The arc selection callback can be used to ignore arcs that are not part
+    // of the ordering, i.e. arcs that are meant to be backwards arcs
+
+    std::pair<const_node_vector,const_arc_vector> sort(arc_select_fn = 0) const;
+    std::pair<node_vector,arc_vector> sort(arc_select_fn = 0);
+
+    // Simplified variant of above for graphs that are known to be DAGs.
+    // If the sort fails due to backward arcs, the
+    // return vector is empty. Note that this will also be empty if the graph
+    // has no nodes in it, so use the empty() method to differentiate.
+
+    const_node_vector dag_sort(arc_select_fn = 0) const;
+    node_vector dag_sort(arc_select_fn = 0);
+
+    ////////////////////////////////////////////////////////////////////////////////
+    // Basic Path Algorithms
+    // A path is a series of arcs - you can use arc_from and arc_to to convert
+    // that into a series of nodes. All the path algorithms take an arc_select
+    // which allows arcs to be selected or rejected for consideration in a path.
+
+    // A selection callback function is applied to each arc in the traversal and
+    // returns true if the arc is to be selected and false if the arc is to be
+    // rejected. If no function is provided the arc is selected. If you want to
+    // use arc selection you should create a function with the type profile given
+    // by the arc_select_fn type. The select function is passed both the graph and
+    // the arc iterator so that it is possible to select an arc on the basis of
+    // the nodes it is connected to.
+
+    // Note: I used a callback because the STL-like predicate idea wasn't working for me...
+
+    // test for the existence of a path from from to to
+    bool path_exists(const_iterator from, const_iterator to, arc_select_fn = 0) const
+      throw(wrong_object,null_dereference,end_dereference);
+    bool path_exists(iterator from, iterator to, arc_select_fn = 0)
+      throw(wrong_object,null_dereference,end_dereference);
+
+    // get the set of all paths from from to to
+    const_path_vector all_paths(const_iterator from, const_iterator to, arc_select_fn = 0) const
+      throw(wrong_object,null_dereference,end_dereference);
+    path_vector all_paths(iterator from, iterator to, arc_select_fn = 0)
+      throw(wrong_object,null_dereference,end_dereference);
+
+    // get the set of all nodes that can be reached by any path from from
+    const_node_vector reachable_nodes(const_iterator from, arc_select_fn = 0) const
+      throw(wrong_object,null_dereference,end_dereference);
+    node_vector reachable_nodes(iterator from, arc_select_fn = 0)
+      throw(wrong_object,null_dereference,end_dereference);
+
+    // get the set of all nodes that can reach to to by any path
+    const_node_vector reaching_nodes(const_iterator to, arc_select_fn = 0) const
+      throw(wrong_object,null_dereference,end_dereference);
+    node_vector reaching_nodes(iterator to, arc_select_fn = 0)
+      throw(wrong_object,null_dereference,end_dereference);
+
+    ////////////////////////////////////////////////////////////////////////////////
+    // Unweighted Shortest path algorithms
+
+    // find the shortest path from from to to
+    // This is an unweighted shortest path algorithm, i.e. the weight of each
+    // arc is assumed to be 1, so just counts the number of arcs
+    // if there is more than one shortest path it returns the first one
+    // If there are no paths, returns an empty path
+    const_arc_vector shortest_path(const_iterator from, const_iterator to, arc_select_fn = 0) const
+      throw(wrong_object,null_dereference,end_dereference);
+    arc_vector shortest_path(iterator from, iterator to, arc_select_fn = 0)
+      throw(wrong_object,null_dereference,end_dereference);
+
+    // find the set of shortest paths from from to any other node in the graph
+    // that is reachable (i.e. for which path_exists() is true)
+    // This is an unweighted shortest path, so just counts the number of arcs
+    // if there is more than one shortest path to a node it returns the first one
+    // If there are no paths, returns an empty list
+    const_path_vector shortest_paths(const_iterator from, arc_select_fn = 0) const
+      throw(wrong_object,null_dereference,end_dereference);
+    path_vector shortest_paths(iterator from, arc_select_fn = 0)
+      throw(wrong_object,null_dereference,end_dereference);
+
+  private:
+    friend class digraph_iterator<NT,AT,NT&,NT*>;
+    friend class digraph_iterator<NT,AT,const NT&,const NT*>;
+    friend class digraph_arc_iterator<NT,AT,AT&,AT*>;
+    friend class digraph_arc_iterator<NT,AT,const AT&, const AT*>;
+
+    typedef std::set<const_iterator> const_iterator_set;
+    typedef TYPENAME const_iterator_set::iterator const_iterator_set_iterator;
+
+    bool path_exists_r(const_iterator from, const_iterator to, const_iterator_set& visited, arc_select_fn) const
+      throw(wrong_object,null_dereference,end_dereference);
+
+    void all_paths_r(const_iterator from, const_iterator to, const_arc_vector& so_far, const_path_vector& result, arc_select_fn) const
+      throw(wrong_object,null_dereference,end_dereference);
+
+    void reachable_nodes_r(const_iterator from, const_iterator_set& visited, arc_select_fn) const
+      throw(wrong_object,null_dereference,end_dereference);
+
+    void reaching_nodes_r(const_iterator to, const_iterator_set& visited, arc_select_fn) const
+      throw(wrong_object,null_dereference,end_dereference);
+
+    digraph_node<NT,AT>* m_nodes_begin;
+    digraph_node<NT,AT>* m_nodes_end;
+    digraph_arc<NT,AT>* m_arcs_begin;
+    digraph_arc<NT,AT>* m_arcs_end;
+  };
+
+  ////////////////////////////////////////////////////////////////////////////////
+
+} // end namespace stlplus
+
+#include "digraph.tpp"
+#endif
index c10586b011e354782d713787b0f106fdef6c73f3..804954a0db72e70bd33d2c36cd32986736e1aaf6 100644 (file)
-////////////////////////////////////////////////////////////////////////////////\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
+////////////////////////////////////////////////////////////////////////////////
+
+//   Author:    Andy Rushton
+//   Copyright: (c) Southampton University 1999-2004
+//              (c) Andy Rushton           2004-2009
+//   License:   BSD License, see ../docs/license.html
+
+//   Note: I tried to write this using STL lists for the node and arc lists, but
+//   it got far too hairy. The specific problem is that I wanted a digraph
+//   iterator to contain a list::iterator so I needed to be able to generate a
+//   list::iterator from a node or arc and STL list iterators don't give you that
+//   functionality. I tried burgling the data structures, but that was
+//   non-portable between different STL implementations so needed lots of #ifdefs
+//   and so was mind-bogglingly awful and unreadable - in other words a
+//   maintenance nightmare. I gave up and impemented my own lists - not difficult.
+
+//   I use circular double-linked lists. The circular design means that both
+//   ends of the list are equally accessible in unit time. An empty list
+//   contains no objects. There is no end node in the list - unlike the STL
+//   lists which have a dummy node for end iterators to point to -
+//   conceptually the end iterator points one element beyond the end of the
+//   list. However, I implement the end iterator concept in the iterator
+//   itself, so do not need the dummy end node.
+
+////////////////////////////////////////////////////////////////////////////////
+#include <algorithm>
+#include <deque>
+
+////////////////////////////////////////////////////////////////////////////////
+// Internals
+
+namespace stlplus
+{
+
+  template<typename NT, typename AT>
+  class digraph_node
+  {
+  public:
+    master_iterator<digraph<NT,AT>, digraph_node<NT,AT> > m_master;
+    NT m_data;
+    digraph_node<NT,AT>* m_prev;
+    digraph_node<NT,AT>* m_next;
+    std::vector<digraph_arc<NT,AT>*> m_inputs;
+    std::vector<digraph_arc<NT,AT>*> m_outputs;
+  public:
+    digraph_node(const digraph<NT,AT>* owner, const NT& d = NT()) :
+      m_master(owner,this), m_data(d), m_prev(0), m_next(0)
+      {
+      }
+    ~digraph_node(void)
+      {
+      }
+  };
+
+  template<typename NT, typename AT>
+  class digraph_arc
+  {
+  public:
+    master_iterator<digraph<NT,AT>, digraph_arc<NT,AT> > m_master;
+    AT m_data;
+    digraph_arc<NT,AT>* m_prev;
+    digraph_arc<NT,AT>* m_next;
+    digraph_node<NT,AT>* m_from;
+    digraph_node<NT,AT>* m_to;
+    digraph_arc(const digraph<NT,AT>* owner, digraph_node<NT,AT>* from = 0, digraph_node<NT,AT>* to = 0, const AT& d = AT()) : 
+      m_master(owner,this), m_data(d), m_prev(0), m_next(0), m_from(from), m_to(to)
+      {
+      }
+  };
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Iterators
+  ////////////////////////////////////////////////////////////////////////////////
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Node iterator
+
+  // construct a null iterator
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(void)
+  {
+  }
+
+  // valid iterator
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(digraph_node<NT,AT>* node) :
+    safe_iterator<digraph<NT,AT>,digraph_node<NT,AT> >(node->m_master)
+  {
+  }
+
+  // end iterator
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(const digraph<NT,AT>* owner) :
+    safe_iterator<digraph<NT,AT>,digraph_node<NT,AT> >(owner)
+  {
+  }
+
+  // alias an iterator
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(const safe_iterator<digraph<NT,AT>, digraph_node<NT,AT> >& iterator) : 
+    safe_iterator<digraph<NT,AT>,digraph_node<NT,AT> >(iterator)
+  {
+  }
+
+  // destructor
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  digraph_iterator<NT,AT,NRef,NPtr>::~digraph_iterator(void)
+  {
+  }
+
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::const_iterator digraph_iterator<NT,AT,NRef,NPtr>::constify (void) const
+  {
+    return digraph_iterator<NT,AT,const NT&,const NT*>(*this);
+  }
+
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::iterator digraph_iterator<NT,AT,NRef,NPtr>::deconstify (void) const
+  {
+    return digraph_iterator<NT,AT,NT&,NT*>(*this);
+  }
+
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& digraph_iterator<NT,AT,NRef,NPtr>::operator ++ (void)
+    throw(null_dereference,end_dereference)
+  {
+    this->assert_valid();
+    if (this->node()->m_next)
+      this->set(this->node()->m_next->m_master);
+    else
+      this->set_end();
+    return *this;
+  }
+
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator digraph_iterator<NT,AT,NRef,NPtr>::operator ++ (int)
+    throw(null_dereference,end_dereference)
+  {
+    // post-increment is defined in terms of the pre-increment
+    digraph_iterator<NT,AT,NRef,NPtr> result(*this);
+    ++(*this);
+    return result;
+  }
+
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& digraph_iterator<NT,AT,NRef,NPtr>::operator -- (void)
+    throw(null_dereference,end_dereference)
+  {
+    this->assert_valid();
+    if (this->node()->m_prev)
+      this->set(this->node()->m_prev->m_master);
+    else
+      this->set_end();
+    return *this;
+  }
+
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator digraph_iterator<NT,AT,NRef,NPtr>::operator -- (int)
+    throw(null_dereference,end_dereference)
+  {
+    // post-decrement is defined in terms of the pre-decrement
+    digraph_iterator<NT,AT,NRef,NPtr> result(*this);
+    --(*this);
+    return result;
+  }
+
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  bool digraph_iterator<NT,AT,NRef,NPtr>::operator == (const TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& r) const
+  {
+    return equal(r);
+  }
+
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  bool digraph_iterator<NT,AT,NRef,NPtr>::operator != (const TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& r) const
+  {
+    return !operator==(r);
+  }
+
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  bool digraph_iterator<NT,AT,NRef,NPtr>::operator < (const TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& r) const
+  {
+    return compare(r) < 0;
+  }
+
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::reference digraph_iterator<NT,AT,NRef,NPtr>::operator*(void) const
+    throw(null_dereference,end_dereference)
+  {
+    this->assert_valid();
+    return this->node()->m_data;
+  }
+
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::pointer digraph_iterator<NT,AT,NRef,NPtr>::operator->(void) const
+    throw(null_dereference,end_dereference)
+  {
+    return &(operator*());
+  }
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Arc Iterator
+
+  template<typename NT, typename AT, typename ARef, typename APtr>
+  digraph_arc_iterator<NT,AT,ARef,APtr>::digraph_arc_iterator(void)
+  {
+  }
+
+  // valid iterator
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  digraph_arc_iterator<NT,AT,NRef,NPtr>::digraph_arc_iterator(digraph_arc<NT,AT>* arc) :
+    safe_iterator<digraph<NT,AT>,digraph_arc<NT,AT> >(arc->m_master)
+  {
+  }
+
+  // end iterator
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  digraph_arc_iterator<NT,AT,NRef,NPtr>::digraph_arc_iterator(const digraph<NT,AT>* owner) :
+    safe_iterator<digraph<NT,AT>,digraph_arc<NT,AT> >(owner)
+  {
+  }
+
+  // alias an iterator
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  digraph_arc_iterator<NT,AT,NRef,NPtr>::digraph_arc_iterator(const safe_iterator<digraph<NT,AT>, digraph_arc<NT,AT> >& iterator) : 
+    safe_iterator<digraph<NT,AT>,digraph_arc<NT,AT> >(iterator)
+  {
+  }
+
+  template<typename NT, typename AT, typename ARef, typename APtr>
+  digraph_arc_iterator<NT,AT,ARef,APtr>::~digraph_arc_iterator(void)
+  {
+  }
+
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  TYPENAME digraph_arc_iterator<NT,AT,NRef,NPtr>::const_iterator digraph_arc_iterator<NT,AT,NRef,NPtr>::constify (void) const
+  {
+    return digraph_arc_iterator<NT,AT,const AT&,const AT*>(*this);
+  }
+
+  template<typename NT, typename AT, typename NRef, typename NPtr>
+  TYPENAME digraph_arc_iterator<NT,AT,NRef,NPtr>::iterator digraph_arc_iterator<NT,AT,NRef,NPtr>::deconstify (void) const
+  {
+    return digraph_arc_iterator<NT,AT,AT&,AT*>(*this);
+  }
+
+  template<typename NT, typename AT, typename ARef, typename APtr>
+  TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& digraph_arc_iterator<NT,AT,ARef,APtr>::operator ++ (void)
+    throw(null_dereference,end_dereference)
+  {
+    this->assert_valid();
+    if (this->node()->m_next)
+      this->set(this->node()->m_next->m_master);
+    else
+      this->set_end();
+    return *this;
+  }
+
+  template<typename NT, typename AT, typename ARef, typename APtr>
+  TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator digraph_arc_iterator<NT,AT,ARef,APtr>::operator ++ (int)
+    throw(null_dereference,end_dereference)
+  {
+    // post-increment is defined in terms of the pre-increment
+    digraph_arc_iterator<NT,AT,ARef,APtr> result(*this);
+    ++(*this);
+    return result;
+  }
+
+  template<typename NT, typename AT, typename ARef, typename APtr>
+  TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& digraph_arc_iterator<NT,AT,ARef,APtr>::operator -- (void)
+    throw(null_dereference,end_dereference)
+  {
+    this->assert_valid();
+    if (this->node()->m_prev)
+      this->set(this->node()->m_prev->m_master);
+    else
+      this->set_end();
+    return *this;
+  }
+
+  template<typename NT, typename AT, typename ARef, typename APtr>
+  TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator digraph_arc_iterator<NT,AT,ARef,APtr>::operator -- (int)
+    throw(null_dereference,end_dereference)
+  {
+    // post-decrement is defined in terms of the pre-decrement
+    digraph_arc_iterator<NT,AT,ARef,APtr> result(*this);
+    --(*this);
+    return result;
+  }
+
+  template<typename NT, typename AT, typename ARef, typename APtr>
+  bool digraph_arc_iterator<NT,AT,ARef,APtr>::operator == (const TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& r) const
+  {
+    return equal(r);
+  }
+
+  template<typename NT, typename AT, typename ARef, typename APtr>
+  bool digraph_arc_iterator<NT,AT,ARef,APtr>::operator != (const TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& r) const
+  {
+    return !operator==(r);
+  }
+
+  template<typename NT, typename AT, typename ARef, typename APtr>
+  bool digraph_arc_iterator<NT,AT,ARef,APtr>::operator < (const TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& r) const
+  {
+    return compare(r) < 0;
+  }
+
+  template<typename NT, typename AT, typename ARef, typename APtr>
+  TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::reference digraph_arc_iterator<NT,AT,ARef,APtr>::operator*(void) const
+    throw(null_dereference,end_dereference)
+  {
+    this->assert_valid();
+    return this->node()->m_data;
+  }
+
+  template<typename NT, typename AT, typename ARef, typename APtr>
+  TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::pointer digraph_arc_iterator<NT,AT,ARef,APtr>::operator->(void) const
+    throw(null_dereference,end_dereference)
+  {
+    return &(operator*());
+  }
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // subtype utilities
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::constify_arcs(const TYPENAME digraph<NT,AT>::arc_vector& arcs) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > result;
+    for (unsigned i = 0; i < arcs.size(); i++)
+    {
+      arcs[i].assert_valid(this);
+      result.push_back(arcs[i].constify());
+    }
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::deconstify_arcs(const TYPENAME digraph<NT,AT>::const_arc_vector& arcs) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > result;
+    for (unsigned i = 0; i < arcs.size(); i++)
+    {
+      arcs[i].assert_valid(this);
+      result.push_back(arcs[i].deconstify());
+    }
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_path_vector digraph<NT,AT>::constify_paths(const TYPENAME digraph<NT,AT>::path_vector& paths) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result;
+    for (unsigned i = 0; i < paths.size(); i++)
+      result.push_back(constify_arcs(paths[i]));
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::path_vector digraph<NT,AT>::deconstify_paths(const TYPENAME digraph<NT,AT>::const_path_vector& paths) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    std::vector<std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > > result;
+    for (unsigned i = 0; i < paths.size(); i++)
+      result.push_back(deconstify_arcs(paths[i]));
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::constify_nodes(const TYPENAME digraph<NT,AT>::node_vector& nodes) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
+    for (unsigned i = 0; i < nodes.size(); i++)
+    {
+      nodes[i].assert_valid(this);
+      result.push_back(nodes[i].constify());
+    }
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::deconstify_nodes(const TYPENAME digraph<NT,AT>::const_node_vector& nodes) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    std::vector<digraph_iterator<NT,AT,NT&,NT*> > result;
+    for (unsigned i = 0; i < nodes.size(); i++)
+    {
+      nodes[i].assert_valid(this);
+      result.push_back(nodes[i].deconstify());
+    }
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  unsigned digraph<NT,AT>::npos(void)
+  {
+    return(unsigned)-1;
+  }
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Constructors etc.
+
+  template<typename NT, typename AT>
+  digraph<NT,AT>::digraph(void) :
+    m_nodes_begin(0), m_nodes_end(0), m_arcs_begin(0), m_arcs_end(0)
+  {
+    // node and arc lists are circular double-linked lists
+    // they start out empty (no dummy end node)
+  }
+
+  template<typename NT, typename AT>
+  digraph<NT,AT>::~digraph(void)
+  {
+    clear();
+  }
+
+  template<typename NT, typename AT>
+  digraph<NT,AT>::digraph(const digraph<NT,AT>& r) :
+    m_nodes_begin(0), m_nodes_end(0), m_arcs_begin(0), m_arcs_end(0)
+  {
+    *this = r;
+  }
+
+  template<typename NT, typename AT>
+  digraph<NT,AT>& digraph<NT,AT>::operator=(const digraph<NT,AT>& r)
+  {
+    // make it self-copy safe i.e. a=a; is a valid instruction
+    if (this == &r) return *this;
+    clear();
+    // first phase is to copy the nodes, creating a map of cross references from the old nodes to their new equivalents
+    std::map<digraph_iterator<NT,AT,const NT&,const NT*>, digraph_iterator<NT,AT,NT&,NT*> > xref;
+    for (digraph_iterator<NT,AT,const NT&,const NT*> n = r.begin(); n != r.end(); n++)
+      xref[n] = insert(*n);
+    // second phase is to copy the arcs, using the map to convert the old to and from nodes to the new nodes
+    for (digraph_arc_iterator<NT,AT, const AT&,const AT*> a = r.arc_begin(); a != r.arc_end(); a++)
+      arc_insert(xref[r.arc_from(a)],xref[r.arc_to(a)],*a);
+    return *this;
+  }
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Basic Node functions
+
+  template<typename NT, typename AT>
+  bool digraph<NT,AT>::empty(void) const
+  {
+    return m_nodes_begin == 0;
+  }
+
+  template<typename NT, typename AT>
+  unsigned digraph<NT,AT>::size(void) const
+  {
+    unsigned count = 0;
+    for (digraph_iterator<NT,AT,const NT&,const NT*> i = begin(); i != end(); i++)
+      count++;
+    return count;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::insert(const NT& node_data)
+  {
+    digraph_node<NT,AT>* new_node = new digraph_node<NT,AT>(this,node_data);
+    if (!m_nodes_end)
+    {
+      // insert into an empty list
+      m_nodes_begin = new_node;
+      m_nodes_end = new_node;
+    }
+    else
+    {
+      // insert at the end of the list
+      new_node->m_prev = m_nodes_end;
+      m_nodes_end->m_next = new_node;
+      m_nodes_end = new_node;
+    }
+    return digraph_iterator<NT,AT,NT&,NT*>(new_node);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::erase(TYPENAME digraph<NT,AT>::iterator iter)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    iter.assert_valid(this);
+    // remove all arcs connected to this node first
+    // use arc_erase rather than arcs.erase because that tidies up the node at the other end of the arc too
+    for (unsigned i = fanin(iter); i--; )
+      arc_erase(input(iter,i));
+    for (unsigned j = fanout(iter); j--; )
+      arc_erase(output(iter,j));
+    // now unlink the node from the list and delete it
+    if (iter.node()->m_next)
+      iter.node()->m_next->m_prev = iter.node()->m_prev;
+    if (iter.node()->m_prev)
+      iter.node()->m_prev->m_next = iter.node()->m_next;
+    digraph_node<NT,AT>* next = iter.node()->m_next;
+    delete iter.node();
+    // return the next node in the list
+    if (next)
+      return digraph_iterator<NT,AT,NT&,NT*>(next);
+    else
+      return digraph_iterator<NT,AT,NT&,NT*>(this);
+  }
+
+  template<typename NT, typename AT>
+  void digraph<NT,AT>::clear(void)
+  {
+    // clearing the nodes also clears the arcs
+    for (digraph_iterator<NT,AT,NT&,NT*> i = begin(); i != end(); )
+      i = erase(i);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::begin(void) const
+  {
+    if (m_nodes_begin)
+      return digraph_iterator<NT,AT,const NT&,const NT*>(m_nodes_begin);
+    else
+      return digraph_iterator<NT,AT,const NT&,const NT*>(this);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::begin(void)
+  {
+    if (m_nodes_begin)
+      return digraph_iterator<NT,AT,NT&,NT*>(m_nodes_begin);
+    else
+      return digraph_iterator<NT,AT,NT&,NT*>(this);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::end(void) const
+  {
+    return digraph_iterator<NT,AT,const NT&,const NT*>(this);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::end(void)
+  {
+    return digraph_iterator<NT,AT,NT&,NT*>(this);
+  }
+
+  template<typename NT, typename AT>
+  unsigned digraph<NT,AT>::fanin(TYPENAME digraph<NT,AT>::const_iterator iter) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    iter.assert_valid(this);
+    return iter.node()->m_inputs.size();
+  }
+
+  template<typename NT, typename AT>
+  unsigned digraph<NT,AT>::fanin(TYPENAME digraph<NT,AT>::iterator iter)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    iter.assert_valid(this);
+    return iter.node()->m_inputs.size();
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::input(TYPENAME digraph<NT,AT>::const_iterator iter, unsigned i) const
+    throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
+  {
+    iter.assert_valid(this);
+    if (i >= iter.node()->m_inputs.size()) throw std::out_of_range("digraph::input");
+    return digraph_arc_iterator<NT,AT, const AT&,const AT*>(iter.node()->m_inputs[i]);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::input(TYPENAME digraph<NT,AT>::iterator iter, unsigned i)
+    throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
+  {
+    iter.assert_valid(this);
+    if (i >= iter.node()->m_inputs.size()) throw std::out_of_range("digraph::input");
+    return digraph_arc_iterator<NT,AT,AT&,AT*>(iter.node()->m_inputs[i]);
+  }
+
+  template<typename NT, typename AT>
+  unsigned digraph<NT,AT>::fanout(TYPENAME digraph<NT,AT>::const_iterator iter) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    iter.assert_valid(this);
+    return iter.node()->m_outputs.size();
+  }
+
+  template<typename NT, typename AT>
+  unsigned digraph<NT,AT>::fanout(TYPENAME digraph<NT,AT>::iterator iter)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    iter.assert_valid(this);
+    return iter.node()->m_outputs.size();
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::output(TYPENAME digraph<NT,AT>::const_iterator iter, unsigned i) const
+    throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
+  {
+    iter.assert_valid(this);
+    if (i >= iter.node()->m_outputs.size()) throw std::out_of_range("digraph::output");
+    return digraph_arc_iterator<NT,AT, const AT&,const AT*>(iter.node()->m_outputs[i]);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::output(TYPENAME digraph<NT,AT>::iterator iter, unsigned i)
+    throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
+  {
+    iter.assert_valid(this);
+    if (i >= iter.node()->m_outputs.size()) throw std::out_of_range("digraph::output");
+    return digraph_arc_iterator<NT,AT,AT&,AT*>(iter.node()->m_outputs[i]);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::inputs(TYPENAME digraph<NT,AT>::const_iterator node) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    node.assert_valid(this);
+    std::vector<digraph_arc_iterator<NT,AT,const AT&, const AT*> > result;
+    for (unsigned i = 0; i < fanin(node); i++)
+      result.push_back(input(node,i));
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::inputs(TYPENAME digraph<NT,AT>::iterator node)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    node.assert_valid(this);
+    std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > result;
+    for (unsigned i = 0; i < fanin(node); i++)
+      result.push_back(input(node,i));
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::outputs(TYPENAME digraph<NT,AT>::const_iterator node) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    node.assert_valid(this);
+    std::vector<digraph_arc_iterator<NT,AT,const AT&, const AT*> > result;
+    for (unsigned i = 0; i < fanout(node); i++)
+      result.push_back(output(node,i));
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::outputs(TYPENAME digraph<NT,AT>::iterator node)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    node.assert_valid(this);
+    std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > result;
+    for (unsigned i = 0; i < fanout(node); i++)
+      result.push_back(output(node,i));
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  unsigned digraph<NT,AT>::output_offset(TYPENAME digraph<NT,AT>::const_iterator from,
+                                         TYPENAME digraph<NT,AT>::const_arc_iterator arc) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    from.assert_valid(this);
+    arc.assert_valid(this);
+    for (unsigned i = 0; i < fanout(from); i++)
+    {
+      if (output(from,i) == arc)
+        return i;
+    }
+    return digraph<NT,AT>::npos();
+  }
+
+  template<typename NT, typename AT>
+  unsigned digraph<NT,AT>::output_offset(TYPENAME digraph<NT,AT>::iterator from,
+                                         TYPENAME digraph<NT,AT>::arc_iterator arc)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    from.assert_valid(this);
+    arc.assert_valid(this);
+    for (unsigned i = 0; i < fanout(from); i++)
+    {
+      if (output(from,i) == arc)
+        return i;
+    }
+    return digraph<NT,AT>::npos();
+  }
+
+  template<typename NT, typename AT>
+  unsigned digraph<NT,AT>::input_offset(TYPENAME digraph<NT,AT>::const_iterator to,
+                                        TYPENAME digraph<NT,AT>::const_arc_iterator arc) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    to.assert_valid(this);
+    arc.assert_valid(this);
+    for (unsigned i = 0; i < fanin(to); i++)
+    {
+      if (input(to,i) == arc)
+        return i;
+    }
+    return digraph<NT,AT>::npos();
+  }
+
+  template<typename NT, typename AT>
+  unsigned digraph<NT,AT>::input_offset(TYPENAME digraph<NT,AT>::iterator to,
+                                        TYPENAME digraph<NT,AT>::arc_iterator arc)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    to.assert_valid(this);
+    arc.assert_valid(this);
+    for (unsigned i = 0; i < fanin(to); i++)
+    {
+      if (input(to,i) == arc)
+        return i;
+    }
+    return digraph<NT,AT>::npos();
+  }
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Basic Arc functions
+
+  template<typename NT, typename AT>
+  bool digraph<NT,AT>::arc_empty(void) const
+  {
+    return m_arcs_end == 0;
+  }
+
+  template<typename NT, typename AT>
+  unsigned digraph<NT,AT>::arc_size(void) const
+  {
+    unsigned count = 0;
+    for (digraph_arc_iterator<NT,AT, const AT&,const AT*> i = arc_begin(); i != arc_end(); i++)
+      count++;
+    return count;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_insert(TYPENAME digraph<NT,AT>::iterator from,
+                                                                   TYPENAME digraph<NT,AT>::iterator to,
+                                                                   const AT& arc_data)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    from.assert_valid(this);
+    to.assert_valid(this);
+    // create the new arc and link it in to the arc list
+    digraph_arc<NT,AT>* new_arc = new digraph_arc<NT,AT>(this, from.node(), to.node(), arc_data);
+    if (!m_arcs_end)
+    {
+      // insert into an empty list
+      m_arcs_begin = new_arc;
+      m_arcs_end = new_arc;
+    }
+    else
+    {
+      // insert at the end of the list
+      new_arc->m_prev = m_arcs_end;
+      m_arcs_end->m_next = new_arc;
+      m_arcs_end = new_arc;
+    }
+    // add this arc to the inputs and outputs of the end nodes
+    from.node()->m_outputs.push_back(new_arc);
+    to.node()->m_inputs.push_back(new_arc);
+    return digraph_arc_iterator<NT,AT,AT&,AT*>(new_arc);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_erase(TYPENAME digraph<NT,AT>::arc_iterator iter)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    iter.assert_valid(this);
+    // first remove this arc's pointers from the from/to nodes
+    for (TYPENAME std::vector<digraph_arc<NT,AT>*>::iterator i = iter.node()->m_to->m_inputs.begin(); i != iter.node()->m_to->m_inputs.end(); )
+    {
+      if (*i == iter.node())
+        i = iter.node()->m_to->m_inputs.erase(i);
+      else
+        i++;
+    }
+    for (TYPENAME std::vector<digraph_arc<NT,AT>*>::iterator o = iter.node()->m_from->m_outputs.begin(); o != iter.node()->m_from->m_outputs.end(); )
+    {
+      if (*o == iter.node())
+        o = iter.node()->m_from->m_outputs.erase(o);
+      else
+        o++;
+    }
+    // now unlink the arc from the list and delete it
+    if (iter.node()->m_next)
+      iter.node()->m_next->m_prev = iter.node()->m_prev;
+    if (iter.node()->m_prev)
+      iter.node()->m_prev->m_next = iter.node()->m_next;
+    digraph_arc<NT,AT>* next = iter.node()->m_next;
+    delete iter.node();
+    if (next)
+      return digraph_arc_iterator<NT,AT,AT&,AT*>(next);
+    else
+      return digraph_arc_iterator<NT,AT,AT&,AT*>(this);
+  }
+
+  template<typename NT, typename AT>
+  void digraph<NT,AT>::arc_clear(void)
+  {
+    for (digraph_arc_iterator<NT,AT,AT&,AT*> a = arc_begin(); a != arc_end(); )
+      a = arc_erase(a);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::arc_begin(void) const
+  {
+    if (m_arcs_begin)
+      return digraph_arc_iterator<NT,AT, const AT&,const AT*>(m_arcs_begin);
+    else
+      return digraph_arc_iterator<NT,AT, const AT&,const AT*>(this);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_begin(void)
+  {
+    if (m_arcs_begin)
+      return digraph_arc_iterator<NT,AT,AT&,AT*>(m_arcs_begin);
+    else
+      return digraph_arc_iterator<NT,AT,AT&,AT*>(this);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::arc_end(void) const
+  {
+    return digraph_arc_iterator<NT,AT, const AT&,const AT*>(this);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_end(void)
+  {
+    return digraph_arc_iterator<NT,AT,AT&,AT*>(this);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::arc_from(TYPENAME digraph<NT,AT>::const_arc_iterator iter) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    iter.assert_valid(this);
+    return digraph_iterator<NT,AT,const NT&,const NT*>(iter.node()->m_from);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::arc_from(TYPENAME digraph<NT,AT>::arc_iterator iter)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    iter.assert_valid(this);
+    return digraph_iterator<NT,AT,NT&,NT*>(iter.node()->m_from);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::arc_to(TYPENAME digraph<NT,AT>::const_arc_iterator iter) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    iter.assert_valid(this);
+    return digraph_iterator<NT,AT,const NT&,const NT*>(iter.node()->m_to);
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::arc_to(TYPENAME digraph<NT,AT>::arc_iterator iter)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    iter.assert_valid(this);
+    return digraph_iterator<NT,AT,NT&,NT*>(iter.node()->m_to);
+  }
+
+  template<typename NT, typename AT>
+  void digraph<NT,AT>::arc_move(TYPENAME digraph<NT,AT>::arc_iterator arc,
+                                TYPENAME digraph<NT,AT>::iterator from,
+                                TYPENAME digraph<NT,AT>::iterator to)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    arc_move_to(arc,to);
+    arc_move_from(arc,from);
+  }
+
+  template<typename NT, typename AT>
+  void digraph<NT,AT>::arc_move_from(TYPENAME digraph<NT,AT>::arc_iterator arc,
+                                     TYPENAME digraph<NT,AT>::iterator from)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    arc.assert_valid(this);
+    from.assert_valid(this);
+    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(); )
+    {
+      if (*o == arc.node())
+        o = arc.node()->m_from->m_outputs.erase(o);
+      else
+        o++;
+    }
+    from.node()->m_outputs.push_back(arc.node());
+    arc.node()->m_from = from.node();
+  }
+
+  template<typename NT, typename AT>
+  void digraph<NT,AT>::arc_move_to(TYPENAME digraph<NT,AT>::arc_iterator arc,
+                                   TYPENAME digraph<NT,AT>::iterator to)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    arc.assert_valid(this);
+    to.assert_valid(this);
+    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(); )
+    {
+      if (*i == arc.node())
+        i = arc.node()->m_to->m_inputs.erase(i);
+      else
+        i++;
+    }
+    to.node()->m_inputs.push_back(arc.node());
+    arc.node()->m_to = to.node();
+  }
+
+  template<typename NT, typename AT>
+  void digraph<NT,AT>::arc_flip(TYPENAME digraph<NT,AT>::arc_iterator arc)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    arc_move(arc,arc_to(arc),arc_from(arc));
+  }
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Adjacency Algorithms
+
+  template<typename NT, typename AT>
+  bool digraph<NT,AT>::adjacent(TYPENAME digraph<NT,AT>::const_iterator from,
+                                TYPENAME digraph<NT,AT>::const_iterator to) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    return adjacent_arc(from,to) != arc_end();
+  }
+
+  template<typename NT, typename AT>
+  bool digraph<NT,AT>::adjacent(TYPENAME digraph<NT,AT>::iterator from,
+                                TYPENAME digraph<NT,AT>::iterator to)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    return adjacent_arc(from,to) != arc_end();
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::adjacent_arc(TYPENAME digraph<NT,AT>::const_iterator from,
+                                                                           TYPENAME digraph<NT,AT>::const_iterator to) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    from.assert_valid(this);
+    to.assert_valid(this);
+    for (unsigned arc = 0; arc < fanout(from); arc++)
+    {
+      if (arc_to(output(from, arc)) == to)
+        return output(from,arc);
+    }
+    return arc_end();
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::adjacent_arc(TYPENAME digraph<NT,AT>::iterator from,
+                                                                     TYPENAME digraph<NT,AT>::iterator to)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    return adjacent_arc(from.constify(), to.constify()).deconstify();
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::adjacent_arcs(TYPENAME digraph<NT,AT>::const_iterator from,
+                                                                          TYPENAME digraph<NT,AT>::const_iterator to) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    from.assert_valid(this);
+    to.assert_valid(this);
+    std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > result;
+    for (unsigned arc = 0; arc < fanout(from); arc++)
+    {
+      if (arc_to(output(from, arc)) == to)
+        result.push_back(output(from,arc));
+    }
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::adjacent_arcs(TYPENAME digraph<NT,AT>::iterator from,
+                                                                    TYPENAME digraph<NT,AT>::iterator to)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    return deconstify_arcs(adjacent_arcs(from.constify(), to.constify()));
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::input_adjacencies(TYPENAME digraph<NT,AT>::const_iterator to) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
+    for (unsigned arc = 0; arc < fanin(to); arc++)
+    {
+      digraph_iterator<NT,AT,const NT&,const NT*> from = arc_from(input(to, arc));
+      if (std::find(result.begin(), result.end(), from) == result.end())
+        result.push_back(from);
+    }
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::input_adjacencies(TYPENAME digraph<NT,AT>::iterator to)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    return deconstify_nodes(input_adjacencies(to.constify()));
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::output_adjacencies(TYPENAME digraph<NT,AT>::const_iterator from) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
+    for (unsigned arc = 0; arc < fanout(from); arc++)
+    {
+      digraph_iterator<NT,AT,const NT&,const NT*> to = arc_to(output(from, arc));
+      if (find(result.begin(), result.end(), to) == result.end())
+        result.push_back(to);
+    }
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::output_adjacencies(TYPENAME digraph<NT,AT>::iterator from)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    return deconstify_nodes(output_adjacencies(from.constify()));
+  }
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Topographical Sort Algorithms
+
+  template<typename NT, typename AT>
+  std::pair<TYPENAME digraph<NT,AT>::const_node_vector, TYPENAME digraph<NT,AT>::const_arc_vector>
+  digraph<NT,AT>::sort(TYPENAME digraph<NT,AT>::arc_select_fn select) const
+  {
+    std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
+    std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > errors;
+    // build a map containing the number of fanins to each node that must be visited before this one
+    std::map<digraph_iterator<NT,AT,const NT&,const NT*>,unsigned> fanin_map;
+    for (digraph_iterator<NT,AT,const NT&,const NT*> n = begin(); n != end(); n++)
+    {
+      unsigned predecessors = 0;
+      // only count predecessors connected by selected arcs
+      for (unsigned f = 0; f < fanin(n); f++)
+      {
+        digraph_arc_iterator<NT,AT, const AT&,const AT*> input_arc = input(n,f);
+        digraph_iterator<NT,AT,const NT&,const NT*> predecessor = arc_from(input_arc);
+        if (!select || select(*this,input_arc))
+          predecessors++;
+      }
+      if (predecessors == 0)
+      {
+        result.push_back(n);
+      }
+      else
+      {
+        fanin_map[n] = predecessors;
+      }
+    }
+    // main algorithm applies the topographical sort repeatedly. For a DAG, it
+    // will complete first time. However, with backward arcs, the first
+    // iteration will fail. The algorithm then tries breaking random arcs to try
+    // to get an ordering.
+    for(unsigned i = 0; !fanin_map.empty(); )
+    {
+      // now visit each node in traversal order, decrementing the fanin count of
+      // all successors. As each successor's fanin count goes to zero, it is
+      // appended to the result.
+      for (; i < result.size(); i++)
+      {
+        // Note: dereferencing gives us a node iterator
+        digraph_iterator<NT,AT,const NT&,const NT*> current = result[i];
+        for (unsigned f = 0; f < fanout(current); f++)
+        {
+          // only consider successors connected by selected arcs
+          digraph_arc_iterator<NT,AT, const AT&,const AT*> output_arc = output(current, f);
+          digraph_iterator<NT,AT,const NT&,const NT*> successor = arc_to(output_arc);
+          if (!select || select(*this,output_arc))
+          {
+            // don't consider arcs that have been eliminated to break a loop
+            if (fanin_map.find(successor) != fanin_map.end())
+            {
+              --fanin_map[successor];
+              if ((fanin_map[successor]) == 0)
+              {
+                result.push_back(successor);
+                fanin_map.erase(fanin_map.find(successor));
+              }
+            }
+          }
+        }
+      }
+      if (!fanin_map.empty())
+      {
+        // there must be backward arcs preventing completion
+        // try removing arcs from the sort to get a partial ordering containing all the nodes
+
+        // select an arc that is still relevant to the sort and break it
+        // first select a node that has non-zero fanin and its predecessor that has non-zero fanin
+        digraph_iterator<NT,AT,const NT&,const NT*> stuck_node = fanin_map.begin()->first;
+        for (unsigned f = 0; f < fanin(stuck_node); f++)
+        {
+          // now successively remove input arcs that are still part of the sort until the fanin reduces to zero
+          // first find a relevant arc - this must be a selected arc that has not yet been traversed by the first half of the algorithm
+          digraph_arc_iterator<NT,AT, const AT&,const AT*> input_arc = input(stuck_node, f);
+          if (!select || select(*this,input_arc))
+          {
+            digraph_iterator<NT,AT,const NT&,const NT*> predecessor = arc_from(input_arc);
+            if (fanin_map.find(predecessor) != fanin_map.end())
+            {
+              // found the right combination - remove this arc and then drop out of the fanin loop to restart the outer sort loop
+              errors.push_back(input_arc);
+              --fanin_map[stuck_node];
+              if ((fanin_map[stuck_node]) == 0)
+              {
+                result.push_back(stuck_node);
+                fanin_map.erase(fanin_map.find(stuck_node));
+                break;
+              }
+            }
+          }
+        }
+      }
+    }
+    return std::make_pair(result,errors);
+  }
+
+  template<typename NT, typename AT>
+  std::pair<TYPENAME digraph<NT,AT>::node_vector, TYPENAME digraph<NT,AT>::arc_vector>
+  digraph<NT,AT>::sort(TYPENAME digraph<NT,AT>::arc_select_fn select)
+  {
+    std::pair<std::vector<digraph_iterator<NT,AT,const NT&,const NT*> >,
+              std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > const_result =
+      const_cast<const digraph<NT,AT>*>(this)->sort(select);
+
+    std::pair<std::vector<digraph_iterator<NT,AT,NT&,NT*> >,
+              std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > > result =
+      std::make_pair(deconstify_nodes(const_result.first),deconstify_arcs(const_result.second));
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::dag_sort(TYPENAME digraph<NT,AT>::arc_select_fn select) const
+  {
+    std::pair<std::vector<digraph_iterator<NT,AT,const NT&,const NT*> >,
+              std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result = sort(select);
+    if (result.second.empty()) return result.first;
+    return std::vector<digraph_iterator<NT,AT,const NT&,const NT*> >();
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::dag_sort(TYPENAME digraph<NT,AT>::arc_select_fn select)
+  {
+    return deconstify_nodes(const_cast<const digraph<NT,AT>*>(this)->dag_sort(select));
+  }
+  ////////////////////////////////////////////////////////////////////////////////
+  // Path Algorithms
+
+  template<typename NT, typename AT>
+  bool digraph<NT,AT>::path_exists_r(TYPENAME digraph<NT,AT>::const_iterator from,
+                                     TYPENAME digraph<NT,AT>::const_iterator to,
+                                     TYPENAME digraph<NT,AT>::const_iterator_set& visited,
+                                     TYPENAME digraph<NT,AT>::arc_select_fn select) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    // Recursive part of the digraph::path_exists function. This is based on a
+    // depth first search algorithm and stops the moment it finds a path
+    // regardless of its length. Simply traverse every output and recurse on that
+    // node until we find the to node or run out of things to recurse on. However,
+    // to avoid infinite recursion due to cycles in the graph, I need to maintain
+    // a set of visited nodes. The visited set is updated when a candidate is
+    // found but tested before the recursion on the candidate so that the number of
+    // function calls is minimised.
+    for (unsigned i = 0; i < fanout(from); i++)
+    {
+      digraph_arc_iterator<NT,AT, const AT&,const AT*> arc = output(from,i);
+      if (!select || select(*this, arc))
+      {
+        digraph_iterator<NT,AT,const NT&,const NT*> node = arc_to(arc);
+        // if the node is the target, return immediately
+        if (node == to) return true;
+        // update the visited set and give up if the insert fails, which indicates that the node has already been visited
+        if (!(visited.insert(node).second)) return false;
+        // now recurse - a path exists from from to to if a path exists from an adjacent node to to
+        if (path_exists_r(node,to,visited,select)) return true;
+      }
+    }
+    return false;
+  }
+
+  template<typename NT, typename AT>
+  bool digraph<NT,AT>::path_exists(TYPENAME digraph<NT,AT>::const_iterator from,
+                                   TYPENAME digraph<NT,AT>::const_iterator to, 
+                                   TYPENAME digraph<NT,AT>::arc_select_fn select) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    // set up the recursion with its initial visited set and then recurse
+    std::set<digraph_iterator<NT,AT,const NT&,const NT*> > visited;
+    visited.insert(from);
+    return path_exists_r(from, to, visited, select);
+  }
+
+  template<typename NT, typename AT>
+  bool digraph<NT,AT>::path_exists(TYPENAME digraph<NT,AT>::iterator from,
+                                   TYPENAME digraph<NT,AT>::iterator to,
+                                   TYPENAME digraph<NT,AT>::arc_select_fn select)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    return path_exists(from.constify(), to.constify(), select);
+  }
+
+  template<typename NT, typename AT>
+  void digraph<NT,AT>::all_paths_r(TYPENAME digraph<NT,AT>::const_iterator from,
+                                   TYPENAME digraph<NT,AT>::const_iterator to,
+                                   TYPENAME digraph<NT,AT>::const_arc_vector& so_far,
+                                   TYPENAME digraph<NT,AT>::const_path_vector& result,
+                                   TYPENAME digraph<NT,AT>::arc_select_fn select) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    // This is the recursive part of the all_paths function. The field so_far
+    // contains the path so far so that when 'to' is reached, the path is
+    // complete. It serves the same purpose as the visited set in the path_exists
+    // function except that it also preserves the path order. It also serves the
+    // purpose of detecting cycles and thus stopping infinite recursion. Every
+    // time the recursion reaches the to node, a copy of so_far is appended to the
+    // path set.
+    for (unsigned i = 0; i < fanout(from); i++)
+    {
+      digraph_arc_iterator<NT,AT, const AT&,const AT*> candidate = output(from,i);
+      // assert_valid that the arc is selected and then assert_valid that the candidate has not
+      // been visited on this path and only allow further recursion if it hasn't
+      if ((!select || select(*this, candidate)) && std::find(so_far.begin(), so_far.end(), candidate) == so_far.end())
+      {
+        // extend the path tracing the route to this arc
+        so_far.push_back(candidate);
+        // if the candidate arc points to the target, update the result set and prevent further recursion, otherwise recurse
+        if (arc_to(candidate) == to)
+          result.push_back(so_far);
+        else
+          all_paths_r(arc_to(candidate),to,so_far,result,select);
+        so_far.pop_back();
+      }
+    }
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_path_vector 
+  digraph<NT,AT>::all_paths(TYPENAME digraph<NT,AT>::const_iterator from, 
+                            TYPENAME digraph<NT,AT>::const_iterator to,
+                            TYPENAME digraph<NT,AT>::arc_select_fn select) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    // set up the recursion with empty data fields and then recurse
+    std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result;
+    std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > so_far;
+    all_paths_r(from, to, so_far, result, select);
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::path_vector
+  digraph<NT,AT>::all_paths(TYPENAME digraph<NT,AT>::iterator from, 
+                            TYPENAME digraph<NT,AT>::iterator to,
+                            TYPENAME digraph<NT,AT>::arc_select_fn select)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    return deconstify_paths(all_paths(from.constify(), to.constify(), select));
+  }
+
+  template<typename NT, typename AT>
+  void digraph<NT,AT>::reachable_nodes_r(TYPENAME digraph<NT,AT>::const_iterator from,
+                                         TYPENAME digraph<NT,AT>::const_iterator_set& visited,
+                                         TYPENAME digraph<NT,AT>::arc_select_fn select) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    // The recursive part of the reachable_nodes function.
+    // This is a depth-first traversal again but this time it carries on to find all the reachable nodes
+    // Just keep recursing on all the adjacent nodes of each node, skipping already visited nodes to avoid cycles
+    for (unsigned i = 0; i < fanout(from); i++)
+    {
+      digraph_arc_iterator<NT,AT, const AT&,const AT*> arc = output(from,i);
+      if (!select || select(*this,arc))
+      {
+        digraph_iterator<NT,AT,const NT&,const NT*> candidate = arc_to(arc);
+        if (visited.insert(candidate).second)
+          reachable_nodes_r(candidate,visited,select);
+      }
+    }
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_node_vector
+  digraph<NT,AT>::reachable_nodes(TYPENAME digraph<NT,AT>::const_iterator from,
+                                  TYPENAME digraph<NT,AT>::arc_select_fn select) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    // seed the recursion, marking the starting node as already visited
+    std::set<digraph_iterator<NT,AT,const NT&,const NT*> > visited;
+    visited.insert(from);
+    reachable_nodes_r(from, visited, select);
+    // convert the visited set into the required output form
+    // exclude the starting node
+    std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
+    for (TYPENAME std::set<digraph_iterator<NT,AT,const NT&,const NT*> >::iterator i = visited.begin(); i != visited.end(); i++)
+      if (*i != from)
+        result.push_back(*i);
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::node_vector
+  digraph<NT,AT>::reachable_nodes(TYPENAME digraph<NT,AT>::iterator from,
+                                  TYPENAME digraph<NT,AT>::arc_select_fn select)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    return deconstify_nodes(reachable_nodes(from.constify(), select));
+  }
+
+  template<typename NT, typename AT>
+  void digraph<NT,AT>::reaching_nodes_r(TYPENAME digraph<NT,AT>::const_iterator to,
+                                        TYPENAME digraph<NT,AT>::const_iterator_set& visited,
+                                        TYPENAME digraph<NT,AT>::arc_select_fn select) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    // The recursive part of the reaching_nodes function.
+    // Just like the reachable_nodes_r function but it goes backwards
+    for (unsigned i = 0; i < fanin(to); i++)
+    {
+      digraph_arc_iterator<NT,AT, const AT&,const AT*> arc = input(to,i);
+      if (!select || select(*this,arc))
+      {
+        digraph_iterator<NT,AT,const NT&,const NT*> candidate = arc_from(input(to,i));
+        if (visited.insert(candidate).second)
+          reaching_nodes_r(candidate,visited,select);
+      }
+    }
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_node_vector
+  digraph<NT,AT>::reaching_nodes(TYPENAME digraph<NT,AT>::const_iterator to,
+                                 TYPENAME digraph<NT,AT>::arc_select_fn select) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    // seed the recursion, marking the starting node as already visited
+    std::set<digraph_iterator<NT,AT,const NT&,const NT*> > visited;
+    visited.insert(to);
+    reaching_nodes_r(to,visited,select);
+    // convert the visited set into the required output form
+    // exclude the end node
+    std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
+    for (TYPENAME std::set<digraph_iterator<NT,AT,const NT&,const NT*> >::iterator i = visited.begin(); i != visited.end(); i++)
+      if (*i != to)
+        result.push_back(*i);
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::node_vector
+  digraph<NT,AT>::reaching_nodes(TYPENAME digraph<NT,AT>::iterator to,
+                                 TYPENAME digraph<NT,AT>::arc_select_fn select)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    return deconstify_nodes(reaching_nodes(to.constify(),select));
+  }
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Shortest Path Algorithms
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_arc_vector
+  digraph<NT,AT>::shortest_path(TYPENAME digraph<NT,AT>::const_iterator from,
+                                TYPENAME digraph<NT,AT>::const_iterator to,
+                                TYPENAME digraph<NT,AT>::arc_select_fn select) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > paths = all_paths(from,to,select);
+    std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > shortest;
+    for (TYPENAME std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > >::iterator i = paths.begin(); i != paths.end(); i++)
+      if (shortest.empty() || i->size() < shortest.size())
+        shortest = *i;
+    return shortest;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::arc_vector
+  digraph<NT,AT>::shortest_path(TYPENAME digraph<NT,AT>::iterator from, 
+                                TYPENAME digraph<NT,AT>::iterator to,
+                                TYPENAME digraph<NT,AT>::arc_select_fn select)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    return deconstify_arcs(shortest_path(from.constify(),to.constify(),select));
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::const_path_vector
+  digraph<NT,AT>::shortest_paths(TYPENAME digraph<NT,AT>::const_iterator from,
+                                 TYPENAME digraph<NT,AT>::arc_select_fn select) const
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    from.assert_valid(this);
+    // This is an unweighted shortest path algorithm based on the algorithm from
+    // Weiss's book. This is essentially a breadth-first traversal or graph
+    // colouring algorithm. It is an iterative algorithm, so no recursion here! It
+    // works by creating a node queue initialised with the starting node. It then
+    // consumes the queue from front to back. For each node, it finds the
+    // successors and appends them to the queue. If a node is already 'known' it
+    // is not added - this avoids cycles. Thus the queue insert ordering
+    // represents the breadth-first ordering. On the way it creates a map of
+    // visited nodes. This is a map not a set because it also stores the arc that
+    // nominated this node as a shortest path. The full path can then be recreated
+    // from the map by just walking back through the predecessors. The depth (or
+    // colour) can be determined by the path length.
+    std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result;
+    // initialise the iteration by creating a queue and adding the start node
+    std::deque<digraph_iterator<NT,AT,const NT&,const NT*> > nodes;
+    nodes.push_back(from);
+    // Create a map to store the set of known nodes mapped to their predecessor
+    // arcs. Initialise it with the current node, which has no predecessor. Note
+    // that the algorithm uses the feature of digraph iterators that they can be
+    // null iterators and that all null iterators are equal.
+    typedef std::map<digraph_iterator<NT,AT,const NT&,const NT*>,
+                     digraph_arc_iterator<NT,AT,const AT&,const AT*> > known_map;
+    known_map known;
+    known.insert(std::make_pair(from,digraph_arc_iterator<NT,AT, const AT&,const AT*>()));
+    // now the iterative part of the algorithm
+    while(!nodes.empty())
+    {
+      // pop the queue to get the next node to process - unfortunately the STL
+      // deque::pop does not return the popped value
+      digraph_iterator<NT,AT,const NT&,const NT*> current = nodes.front();
+      nodes.pop_front();
+      // now visit all the successors
+      for (unsigned i = 0; i < fanout(current); i++)
+      {
+        digraph_arc_iterator<NT,AT, const AT&,const AT*> next_arc = output(current,i);
+        // assert_valid whether the successor arc is a selected arc and can be part of a path
+        if (!select || select(*this,next_arc))
+        {
+          digraph_iterator<NT,AT,const NT&,const NT*> next = arc_to(next_arc);
+          // Discard any successors that are known because to be known already they
+          // must have another shorter path. Otherwise add the successor node to the
+          // queue to be visited later. To minimise the overhead of map lookup I use
+          // the usual trick of trying to insert the node and determining whether
+          // the node was known by the success or failure of the insertion - this is
+          // a Good STL Trick (TM).
+          if (known.insert(std::make_pair(next,next_arc)).second)
+            nodes.push_back(next);
+        }
+      }
+    }
+    // The map contains the results as an unordered set of nodes, mapped to their
+    // predecessor arcs and weight. This now needs to be converted into a set of
+    // paths. This is done by starting with a node from the map, finding its
+    // predecessor arc and therefore its predecessor node, looking that up in the
+    // map to find its predecessor and so on until the start node is reached (it
+    // has a null predecessor). Note that the known set includes the from node
+    // which does not generate a path.
+    for (TYPENAME known_map::iterator i = known.begin(); i != known.end(); i++)
+    {
+      if (i->first != from)
+      {
+        const_arc_vector this_path;
+        for (TYPENAME known_map::iterator node = i; 
+             node->second.valid(); 
+             node = known.find(arc_from(node->second)))
+          this_path.insert(this_path.begin(),node->second);
+        result.push_back(this_path);
+      }
+    }
+    return result;
+  }
+
+  template<typename NT, typename AT>
+  TYPENAME digraph<NT,AT>::path_vector
+  digraph<NT,AT>::shortest_paths(TYPENAME digraph<NT,AT>::iterator from,
+                                 TYPENAME digraph<NT,AT>::arc_select_fn select)
+    throw(wrong_object,null_dereference,end_dereference)
+  {
+    return deconstify_paths(shortest_paths(from.constify(),select));
+  }
+
+  ////////////////////////////////////////////////////////////////////////////////
+
+} // end namespace stlplus
index 3549ff4c9022e98b570a975bd52bf18fb544cca0..19110137c5aeb8cf06e9828b2f21129db07bc270 100644 (file)
@@ -1,71 +1,71 @@
-#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
+#ifndef STLPLUS_EXCEPTIONS
+#define STLPLUS_EXCEPTIONS
+////////////////////////////////////////////////////////////////////////////////
+
+//   Author: Andy Rushton
+//   Copyright: (c) Southampton University 1999-2004
+//              (c) Andy Rushton           2004-2009
+//   License:   BSD License, see ../docs/license.html
+
+//   The set of general exceptions thrown by STLplus components
+
+////////////////////////////////////////////////////////////////////////////////
+#include "containers_fixes.hpp"
+#include <stdexcept>
+#include <string>
+
+namespace stlplus
+{
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Thrown if a pointer or an iterator is dereferenced when it is null
+
+  class null_dereference : public std::logic_error
+  {
+  public:
+    null_dereference(const std::string& description) throw() :
+      std::logic_error(std::string("stlplus::null_dereference: ") + description) {}
+    ~null_dereference(void) throw() {}
+  };
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Thrown if an iterator is dereferenced when it is pointing to the end element
+
+  class end_dereference : public std::logic_error
+  {
+  public:
+    end_dereference(const std::string& description) throw() :
+      std::logic_error("stlplus::end_dereference: " + description) {}
+    ~end_dereference(void) throw() {}
+  };
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Thrown if an iterator is used with the wrong container. In other words, an
+  // iterator is created as a pointer to a sub-object within a container. If
+  // that iterator is then used with a different container, this exception is
+  // thrown.
+
+  class wrong_object : public std::logic_error
+  {
+  public:
+    wrong_object(const std::string& description) throw() :
+      std::logic_error("stlplus::wrong_object: " + description) {}
+    ~wrong_object(void) throw() {}
+  };
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Thrown if an attempt is made to copy an object that is uncopyable
+
+  class illegal_copy : public std::logic_error
+  {
+  public:
+    illegal_copy(const std::string& description) throw() :
+      std::logic_error("stlplus::illegal_copy: " + description) {}
+    ~illegal_copy(void) throw() {}
+  };
+
+  ////////////////////////////////////////////////////////////////////////////////
+
+} // end namespace stlplus
+
+#endif
index 36437f1671b287ffef593797dbc967e12ebd504c..46dc46ddc5c6e00da2028bc26c6e3f94ced0c9e8 100644 (file)
@@ -1,59 +1,59 @@
-#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
+#ifndef STLPLUS_FOURSOME
+#define STLPLUS_FOURSOME
+////////////////////////////////////////////////////////////////////////////////
+
+//   Author:    Andy Rushton, from an original by Dan Milton
+//   Copyright: (c) Southampton University 1999-2004
+//              (c) Andy Rushton           2004-2009
+//   License:   BSD License, see ../docs/license.html
+
+//   The next in the series pair->triple->foursome
+
+//   Originally called quadruple but that clashed (as did quad) with system
+//   libraries on some operating systems
+
+////////////////////////////////////////////////////////////////////////////////
+#include "containers_fixes.hpp"
+
+namespace stlplus
+{
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // the foursome class
+
+  template<typename T1, typename T2, typename T3, typename T4>
+  struct foursome
+  {
+    typedef T1 first_type;
+    typedef T2 second_type;
+    typedef T3 third_type;
+    typedef T4 fourth_type;
+
+    T1 first;
+    T2 second;
+    T3 third;
+    T4 fourth;
+
+    foursome(void);
+    foursome(const T1& p1, const T2& p2, const T3& p3, const T4& p4);
+    foursome(const foursome<T1,T2,T3,T4>& t2);
+  };
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // creation
+
+  template<typename T1, typename T2, typename T3, typename T4>
+  foursome<T1,T2,T3,T4> make_foursome(const T1& first, const T2& second, const T3& third, const T4& fourth);
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // comparison
+
+  template<typename T1, typename T2, typename T3, typename T4>
+  bool operator == (const foursome<T1,T2,T3,T4>& left, const foursome<T1,T2,T3,T4>& right);
+
+  ////////////////////////////////////////////////////////////////////////////////
+
+} // end namespace stlplus
+
+#include "foursome.tpp"
+#endif
index f1dd9b39c66b2352352371e17e12f7474c2d8213..b2bfe08d4679e6bc39d3122429fd9b678a7ef6a0 100644 (file)
@@ -1,59 +1,59 @@
-////////////////////////////////////////////////////////////////////////////////\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
+////////////////////////////////////////////////////////////////////////////////
+
+//   Author:    Andy Rushton, from an original by Dan Milton
+//   Copyright: (c) Southampton University 1999-2004
+//              (c) Andy Rushton           2004-2009
+//   License:   BSD License, see ../docs/license.html
+
+////////////////////////////////////////////////////////////////////////////////
+
+namespace stlplus
+{
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // the foursome class
+
+  template<typename T1, typename T2, typename T3, typename T4>
+  foursome<T1,T2,T3,T4>::foursome(void) :
+    first(), second(), third(), fourth()
+  {
+  }
+
+  template<typename T1, typename T2, typename T3, typename T4>
+  foursome<T1,T2,T3,T4>::foursome(const T1& p1, const T2& p2, const T3& p3, const T4& p4) :
+    first(p1), second(p2), third(p3), fourth(p4)
+  {
+  }
+
+  template<typename T1, typename T2, typename T3, typename T4>
+  foursome<T1,T2,T3,T4>::foursome(const foursome<T1,T2,T3,T4>& t2) :
+    first(t2.first), second(t2.second), third(t2.third), fourth(t2.fourth)
+  {
+  }
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // creation
+
+  template<typename T1, typename T2, typename T3, typename T4>
+  foursome<T1,T2,T3,T4> make_foursome(const T1& first, const T2& second, const T3& third, const T4& fourth)
+  {
+    return foursome<T1,T2,T3,T4>(first,second,third,fourth);
+  }
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // comparison
+
+  template<typename T1, typename T2, typename T3, typename T4>
+  bool operator == (const foursome<T1,T2,T3,T4>& left, const foursome<T1,T2,T3,T4>& right)
+  {
+    // foursomes are equal if all elements are equal
+    return 
+      left.first == right.first && 
+      left.second == right.second && 
+      left.third == right.third &&
+      left.fourth == right.fourth;
+  }
+
+  ////////////////////////////////////////////////////////////////////////////////
+
+} // end namespace stlplus
index 19624812850a1fc0d1355f983f3972b475e2d747..13e9541f81d0cc2ff31320b60ae0f592eef590d6 100644 (file)
-#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
-#include <iostream>\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
-    // as in map, this returns the number of elements erased\r
-    size_type erase(const K& key);\r
-    // remove an element from the hash table using an iterator\r
-    // as in map, returns an iterator to the next element\r
-    iterator erase(iterator it);\r
-    // remove all elements from the hash table\r
-    void erase(void);\r
-    // map equivalent of above\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
-    // diagnostic report shows the number of items in each bin so can be used\r
-    // to diagnose effectiveness of hash functions\r
-    void debug_report(std::ostream&) const;\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
+#ifndef STLPLUS_HASH
+#define STLPLUS_HASH
+////////////////////////////////////////////////////////////////////////////////
+
+//   Author:    Andy Rushton
+//   Copyright: (c) Southampton University 1999-2004
+//              (c) Andy Rushton           2004-2009
+//   License:   BSD License, see ../docs/license.html
+
+//   A chained hash table using STL semantics
+
+////////////////////////////////////////////////////////////////////////////////
+#include "containers_fixes.hpp"
+#include "exceptions.hpp"
+#include "safe_iterator.hpp"
+#include <map>
+#include <iostream>
+
+namespace stlplus
+{
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // internals
+
+  template<typename K, typename T, class H, class E> class hash;
+  template<typename K, typename T, class H, class E> class hash_element;
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // iterator class
+
+  template<typename K, typename T, class H, class E, typename V>
+  class hash_iterator : public safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >
+  {
+  public:
+    friend class hash<K,T,H,E>;
+
+    // local type definitions
+    // an iterator points to a value whilst a const_iterator points to a const value
+    typedef V                                                  value_type;
+    typedef hash_iterator<K,T,H,E,std::pair<const K,T> >       iterator;
+    typedef hash_iterator<K,T,H,E,const std::pair<const K,T> > const_iterator;
+    typedef hash_iterator<K,T,H,E,V>                           this_iterator;
+    typedef V&                                                 reference;
+    typedef V*                                                 pointer;
+
+    // constructor to create a null iterator - you must assign a valid value to this iterator before using it
+    // any attempt to dereference or use a null iterator is an error
+    // the only valid thing you can do is assign an iterator to it
+    hash_iterator(void);
+    ~hash_iterator(void);
+
+    // Type conversion methods allow const_iterator and iterator to be converted
+    // convert an iterator/const_iterator to a const_iterator
+    const_iterator constify(void) const;
+    // convert an iterator/const_iterator to an iterator
+    iterator deconstify(void) const;
+
+    // increment operators used to step through the set of all values in a hash
+    // it is only legal to increment a valid iterator
+    // there's no decrement - I've only implemented this as a unidirectional iterator
+    // pre-increment
+    this_iterator& operator ++ (void)
+      throw(null_dereference,end_dereference);
+    // post-increment
+    this_iterator operator ++ (int)
+      throw(null_dereference,end_dereference);
+
+    // test useful for testing whether iteration has completed
+    bool operator == (const this_iterator& r) const;
+    bool operator != (const this_iterator& r) const;
+    bool operator < (const this_iterator& r) const;
+
+    // access the value - a const_iterator gives you a const value, an iterator a non-const value
+    // it is illegal to dereference an invalid (i.e. null or end) iterator
+    reference operator*(void) const
+      throw(null_dereference,end_dereference);
+    pointer operator->(void) const
+      throw(null_dereference,end_dereference);
+
+  private:
+    friend class hash_element<K,T,H,E>;
+
+    // constructor used by hash to create a non-null iterator
+    // you cannot create a valid iterator except by calling a hash method that returns one
+    explicit hash_iterator(hash_element<K,T,H,E>* element);
+    // constructor used to create an end iterator
+    explicit hash_iterator(const hash<K,T,H,E>* owner);
+    // used to create an alias of an iterator
+    explicit hash_iterator(const safe_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> >& iterator);
+  };
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // Hash class
+  // K = key type
+  // T = value type
+  // H = hash function object with the profile 'unsigned H(const K&)'
+  // E = equal function object with profile 'bool E(const K&, const K&)' defaults to equal_to which in turn calls '=='
+
+  template<typename K, typename T, class H, class E = std::equal_to<K> >
+  class hash
+  {
+  public:
+    typedef unsigned                                size_type;
+    typedef K                                       key_type;
+    typedef T                                       data_type;
+    typedef T                                       mapped_type;
+    typedef std::pair<const K, T>                   value_type;
+    typedef hash_iterator<K,T,H,E,value_type>       iterator;
+    typedef hash_iterator<K,T,H,E,const value_type> const_iterator;
+
+    // construct a hash table with specified number of bins
+    // the default 0 bins means leave it to the table to decide
+    // specifying 0 bins also enables auto-rehashing, otherwise auto-rehashing defaults off
+    hash(unsigned bins = 0);
+    ~hash(void);
+
+    // copy and equality copy the data elements but not the size of the copied table
+    hash(const hash&);
+    hash& operator = (const hash&);
+
+    // test for an empty table and for the size of a table
+    // efficient because the size is stored separately from the table contents
+    bool empty(void) const;
+    unsigned size(void) const;
+
+    // test for equality - two hashes are equal if they contain equal values
+    bool operator == (const hash&) const;
+    bool operator != (const hash&) const;
+
+    // switch auto-rehash on
+    void auto_rehash(void);
+    // switch auto-rehash off
+    void manual_rehash(void);
+    // force a rehash now
+    // default of 0 means implement built-in size calculation for rehashing (recommended - it doubles the number of bins)
+    void rehash(unsigned bins = 0);
+    // test the loading ratio, which is the size divided by the number of bins
+    // use this if you are doing your own rehashing
+    // the recommendation is to double the bins when the loading exceeds 0.5 which is what auto-rehashing does
+    float loading(void) const;
+
+    // test for the presence of a key
+    bool present(const K& key) const;
+    // provide map equivalent key count function (0 or 1, as not a multimap)
+    size_type count(const K& key) const;
+
+    // insert a new key/data pair - replaces any previous value for this key
+    iterator insert(const K& key, const T& data);
+    // insert a copy of the pair into the table (std::map compatible)
+    std::pair<iterator, bool> insert(const value_type& value);
+    // insert a new key and return the iterator so that the data can be filled in
+    iterator insert(const K& key);
+
+    // remove a key/data pair from the hash table
+    // as in map, this returns the number of elements erased
+    size_type erase(const K& key);
+    // remove an element from the hash table using an iterator
+    // as in map, returns an iterator to the next element
+    iterator erase(iterator it);
+    // remove all elements from the hash table
+    void erase(void);
+    // map equivalent of above
+    void clear(void);
+
+    // find a key and return an iterator to it
+    // The iterator is like a pointer to a pair<const K,T>
+    // end() is returned if the find fails
+    const_iterator find(const K& key) const;
+    iterator find(const K& key);
+
+    // returns the data corresponding to the key
+    // const version is used for const hashes and cannot change the hash, so failure causes an exception
+    // non-const version is for non-const hashes and is like map - it creates a new key/data pair if find fails
+    const T& operator[] (const K& key) const throw(std::out_of_range);
+    T& operator[] (const K& key);
+
+    // iterators allow the hash table to be traversed
+    // iterators remain valid unless an item is removed or unless a rehash happens
+    const_iterator begin(void) const;
+    iterator begin(void);
+    const_iterator end(void) const;
+    iterator end(void);
+
+    // diagnostic report shows the number of items in each bin so can be used
+    // to diagnose effectiveness of hash functions
+    void debug_report(std::ostream&) const;
+
+    // internals
+  private:
+    friend class hash_element<K,T,H,E>;
+    friend class hash_iterator<K,T,H,E,std::pair<const K,T> >;
+    friend class hash_iterator<K,T,H,E,const std::pair<const K,T> >;
+
+    unsigned m_rehash;
+    unsigned m_bins;
+    unsigned m_size;
+    hash_element<K,T,H,E>** m_values;
+  };
+
+  ////////////////////////////////////////////////////////////////////////////////
+
+} // end namespace stlplus
+
+#include "hash.tpp"
+#endif
index 9a1e4e93728c477f7d13961c678592508786ce7b..da2e39df5f5beebbb1d3908b95897aa20fc765c6 100644 (file)
-////////////////////////////////////////////////////////////////////////////////\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 <iomanip>\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
-  unsigned 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 1;\r
-    }\r
-    return 0;\r
-  }\r
-\r
-  // remove an element from the hash table using an iterator (std::map equivalent)\r
-  template<typename K, typename T, class H, class E>\r
-  TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::erase(TYPENAME hash<K,T,H,E>::iterator it)\r
-  {\r
-    // work out what the next iterator is in order to return it later\r
-    TYPENAME hash<K,T,H,E>::iterator next(it);\r
-    ++next;\r
-    // we now need to find where this item is - made difficult by the use of\r
-    // single-linked lists which means I have to search through the bin from\r
-    // the top in order to unlink from the list.\r
-    unsigned hash_value_full = it.node()->m_hash;\r
-    unsigned bin = hash_value_full % m_bins;\r
-    // scan the list for this element\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
-      // direct test on the address of the element\r
-      if (current != it.node()) continue;\r
-      // found this iterator, 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
-      current = 0;\r
-      // remember to maintain the size count\r
-      m_size--;\r
-      break;\r
-    }\r
-    return next;\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
-  template<typename K, typename T, class H, class E>\r
-  void hash<K,T,H,E>::debug_report(std::ostream& str) const\r
-  {\r
-    // calculate some stats first\r
-    unsigned occupied = 0;\r
-    unsigned min_in_bin = m_size;\r
-    unsigned max_in_bin = 0;\r
-    for (unsigned i = 0; i < m_bins; i++)\r
-    {\r
-      if (m_values[i]) occupied++;\r
-      unsigned count = 0;\r
-      for (hash_element<K,T,H,E>* item = m_values[i]; item; item = item->m_next) count++;\r
-      if (count > max_in_bin) max_in_bin = count;\r
-      if (count < min_in_bin) min_in_bin = count;\r
-    }\r
-    // now print the table\r
-    str << "------------------------------------------------------------------------" << std::endl;\r
-    str << "| size:     " << m_size << std::endl;\r
-    str << "| bins:     " << m_bins << std::endl;\r
-    str << "| loading:  " << loading() << " ";\r
-    if (m_rehash)\r
-      str << "auto-rehash at " << m_rehash << std::endl;\r
-    else\r
-      str << "manual rehash" << std::endl;\r
-    str << "| occupied: " << occupied \r
-        << std::fixed << " (" << (100.0*(float)occupied/(float)m_bins) << "%)" << std::scientific\r
-        << ", min = " << min_in_bin << ", max = " << max_in_bin << std::endl;\r
-    str << "|-----------------------------------------------------------------------" << std::endl;\r
-    str << "|  bin         0     1     2     3     4     5     6     7     8     9" << std::endl;\r
-    str << "|        ---------------------------------------------------------------";\r
-    for (unsigned j = 0; j < m_bins; j++)\r
-    {\r
-      if (j % 10 == 0)\r
-      {\r
-        str << std::endl;\r
-        str << "| " << std::setw(6) << std::right << (j/10*10) << std::left << " |";\r
-      }\r
-      unsigned count = 0;\r
-      for (hash_element<K,T,H,E>* item = m_values[j]; item; item = item->m_next) count++;\r
-      if (!count)\r
-        str << "     .";\r
-      else\r
-        str << std::setw(6) << std::right << count << std::left;\r
-    }\r
-    str << std::endl;\r
-    str << "------------------------------------------------------------------------" << std::endl;\r
-  }\r
-\r
-  ////////////////////////////////////////////////////////////////////////////////\r
-\r
-} // end namespace stlplus\r
-\r
+////////////////////////////////////////////////////////////////////////////////
+
+//   Author:    Andy Rushton
+//   Copyright: (c) Southampton University 1999-2004
+//              (c) Andy Rushton           2004-2009
+//   License:   BSD License, see ../docs/license.html
+
+////////////////////////////////////////////////////////////////////////////////
+#include <iomanip>
+
+namespace stlplus
+{
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // the element stored in the hash
+
+  template<typename K, typename T, typename H, typename E>
+  class hash_element
+  {
+  public:
+    master_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> > m_master;
+    std::pair<const K, T> m_value;
+    hash_element<K,T,H,E>* m_next;
+    unsigned m_hash;
+
+    hash_element(const hash<K,T,H,E>* owner, const K& key, const T& data, unsigned hash) :
+      m_master(owner,this), m_value(key,data), m_next(0), m_hash(hash)
+      {
+      }
+
+    hash_element(const hash<K,T,H,E>* owner, const std::pair<const K,T>& value, unsigned hash) :
+      m_master(owner,this), m_value(value), m_next(0), m_hash(hash)
+      {
+      }
+
+    ~hash_element(void)
+      {
+        m_next = 0;
+        m_hash = 0;
+      }
+
+    const hash<K,T,H,E>* owner(void) const
+      {
+        return m_master.owner();
+      }
+
+    // generate the bin number from the hash value and the owner's number of bins
+    unsigned bin(void) const
+      {
+        return m_hash % (owner()->m_bins);
+      }
+  };
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // iterator
+
+  // null constructor
+  template<typename K, typename T, class H, class E, typename V>
+  hash_iterator<K,T,H,E,V>::hash_iterator(void)
+  {
+  }
+
+  // non-null constructor used from within the hash to construct a valid iterator
+  template<typename K, typename T, class H, class E, typename V>
+  hash_iterator<K,T,H,E,V>::hash_iterator(hash_element<K,T,H,E>* element) :
+    safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(element->m_master)
+  {
+  }
+
+  // constructor used to create an end iterator
+  template<typename K, typename T, class H, class E, typename V>
+  hash_iterator<K,T,H,E,V>::hash_iterator(const hash<K,T,H,E>* owner) :
+    safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(owner)
+  {
+  }
+
+  template<typename K, typename T, class H, class E, typename V>
+  hash_iterator<K,T,H,E,V>::hash_iterator(const safe_iterator<hash<K,T,H,E>, hash_element<K,T,H,E> >& iterator) :
+    safe_iterator<hash<K,T,H,E>,hash_element<K,T,H,E> >(iterator)
+  {
+  }
+
+  // destructor
+
+  template<typename K, typename T, class H, class E, typename V>
+  hash_iterator<K,T,H,E,V>::~hash_iterator(void)
+  {
+  }
+
+  // mode conversions
+
+  template<typename K, typename T, class H, class E, typename V>
+  TYPENAME hash_iterator<K,T,H,E,V>::const_iterator hash_iterator<K,T,H,E,V>::constify(void) const
+  {
+    return hash_iterator<K,T,H,E,const std::pair<const K,T> >(*this);
+  }
+
+  template<typename K, typename T, class H, class E, typename V>
+  TYPENAME hash_iterator<K,T,H,E,V>::iterator hash_iterator<K,T,H,E,V>::deconstify(void) const
+  {
+    return hash_iterator<K,T,H,E,std::pair<const K,T> >(*this);
+  }
+
+  // increment operator looks for the next element in the table
+  // if there isn't one, then this becomes an end() iterator with m_bin = m_bins
+  template<typename K, typename T, class H, class E, typename V>
+  TYPENAME hash_iterator<K,T,H,E,V>::this_iterator& hash_iterator<K,T,H,E,V>::operator ++ (void)
+    throw(null_dereference,end_dereference)
+  {
+    this->assert_valid();
+    if (this->node()->m_next)
+      set(this->node()->m_next->m_master);
+    else
+    {
+      // failing that, subsequent hash values are tried until either an element is found or there are no more bins
+      // in which case it becomes an end() iterator
+      hash_element<K,T,H,E>* element = 0;
+      unsigned current_bin = this->node()->bin();
+      for(current_bin++; !element && (current_bin < this->owner()->m_bins); current_bin++)
+        element = this->owner()->m_values[current_bin];
+      if (element)
+        set(element->m_master);
+      else
+        this->set_end();
+    }
+    return *this;
+  }
+
+  // post-increment is defined in terms of pre-increment
+  template<typename K, typename T, class H, class E, typename V>
+  TYPENAME hash_iterator<K,T,H,E,V>::this_iterator hash_iterator<K,T,H,E,V>::operator ++ (int)
+    throw(null_dereference,end_dereference)
+  {
+    hash_iterator<K,T,H,E,V> old(*this);
+    ++(*this);
+    return old;
+  }
+
+  // two iterators are equal if they point to the same element
+  // both iterators must be non-null and belong to the same table
+  template<typename K, typename T, class H, class E, typename V>
+  bool hash_iterator<K,T,H,E,V>::operator == (const hash_iterator<K,T,H,E,V>& r) const
+  {
+    return equal(r);
+  }
+
+  template<typename K, typename T, class H, class E, typename V>
+  bool hash_iterator<K,T,H,E,V>::operator != (const hash_iterator<K,T,H,E,V>& r) const
+  {
+    return !operator==(r);
+  }
+
+  template<typename K, typename T, class H, class E, typename V>
+  bool hash_iterator<K,T,H,E,V>::operator < (const hash_iterator<K,T,H,E,V>& r) const
+  {
+    return compare(r) < 0;
+  }
+
+  // iterator dereferencing is only legal on a non-null iterator
+  template<typename K, typename T, class H, class E, typename V>
+  V& hash_iterator<K,T,H,E,V>::operator*(void) const
+    throw(null_dereference,end_dereference)
+  {
+    this->assert_valid();
+    return this->node()->m_value;
+  }
+
+  template<typename K, typename T, class H, class E, typename V>
+  V* hash_iterator<K,T,H,E,V>::operator->(void) const
+    throw(null_dereference,end_dereference)
+  {
+    return &(operator*());
+  }
+
+  ////////////////////////////////////////////////////////////////////////////////
+  // hash
+
+  // totally arbitrary initial size used for auto-rehashed tables
+  static unsigned hash_default_bins = 127;
+
+  // constructor
+  // tests whether the user wants auto-rehash
+  // sets the rehash point to be a loading of 1.0 by setting it to the number of bins
+  // uses the user's size unless this is zero, in which case implement the default
+
+  template<typename K, typename T, class H, class E>
+  hash<K,T,H,E>::hash(unsigned bins) :
+    m_rehash(bins), m_bins(bins > 0 ? bins : hash_default_bins), m_size(0), m_values(0)
+  {
+    m_values = new hash_element<K,T,H,E>*[m_bins];
+    for (unsigned i = 0; i < m_bins; i++)
+      m_values[i] = 0;
+  }
+
+  template<typename K, typename T, class H, class E>
+  hash<K,T,H,E>::~hash(void)
+  {
+    // delete all the elements
+    clear();
+    // and delete the data structure
+    delete[] m_values;
+    m_values = 0;
+  }
+
+  // as usual, implement the copy constructor i.t.o. the assignment operator
+
+  template<typename K, typename T, class H, class E>
+  hash<K,T,H,E>::hash(const hash<K,T,H,E>& right) :
+    m_rehash(right.m_rehash), m_bins(right.m_bins), m_size(0), m_values(0)
+  {
+    m_values = new hash_element<K,T,H,E>*[right.m_bins];
+    // copy the rehash behaviour as well as the size
+    for (unsigned i = 0; i < m_bins; i++)
+      m_values[i] = 0;
+    *this = right;
+  }
+
+  // assignment operator
+  // this is done by copying the elements
+  // the source and target hashes can be different sizes
+  // the hash is self-copy safe, i.e. it is legal to say x = x;
+
+  template<typename K, typename T, class H, class E>
+  hash<K,T,H,E>& hash<K,T,H,E>::operator = (const hash<K,T,H,E>& r)
+  {
+    // make self-copy safe
+    if (&r == this) return *this;
+    // remove all the existing elements
+    clear();
+    // copy the elements across - remember that this is rehashing because the two
+    // tables can be different sizes so there is no quick way of doing this by
+    // copying the lists
+    for (hash_iterator<K,T,H,E,const std::pair<const K,T> > i = r.begin(); i != r.end(); ++i)
+      insert(i->first, i->second);
+    return *this;
+  }
+
+  // number of values in the hash
+  template<typename K, typename T, class H, class E>
+  bool hash<K,T,H,E>::empty(void) const
+  {
+    return m_size == 0;
+  }
+
+  template<typename K, typename T, class H, class E>
+  unsigned hash<K,T,H,E>::size(void) const
+  {
+    return m_size;
+  }
+
+  // equality
+  template<typename K, typename T, class H, class E>
+  bool hash<K,T,H,E>::operator == (const hash<K,T,H,E>& right) const
+  {
+    // this table is the same as the right table if they are the same table!
+    if (&right == this) return true;
+    // they must be the same size to be equal
+    if (m_size != right.m_size) return false;
+    // now every key in this must be in right and have the same data
+    for (hash_iterator<K,T,H,E,const std::pair<const K,T> > i = begin(); i != end(); i++)
+    {
+      hash_iterator<K,T,H,E,const std::pair<const K,T> > found = right.find(i->first);
+      if (found == right.end()) return false;
+      if (!(i->second == found->second)) return false;
+    }
+    return true;
+  }
+
+  // set up the hash to auto-rehash at a specific size
+  // setting the rehash size to 0 forces manual rehashing
+  template<typename K, typename T, class H, class E>
+  void hash<K,T,H,E>::auto_rehash(void)
+  {
+    m_rehash = m_bins;
+  }
+
+  template<typename K, typename T, class H, class E>
+  void hash<K,T,H,E>::manual_rehash(void)
+  {
+    m_rehash = 0;
+  }
+
+  // the rehash function
+  // builds a new hash table and moves the elements (without copying) from the old to the new
+  // I store the un-modulused hash value in the element for more efficient rehashing
+  // passing 0 to the bins parameter does auto-rehashing
+  // passing any other value forces the number of bins
+
+  template<typename K, typename T, class H, class E>
+  void hash<K,T,H,E>::rehash(unsigned bins)
+  {
+    // user specified size: just take the user's value
+    // auto calculate: if the load is high, increase the size; else do nothing
+    unsigned new_bins = bins ? bins : m_bins;
+    if (bins == 0 && m_size > 0)
+    {
+      // these numbers are pretty arbitrary
+      // TODO - make them user-customisable?
+      float load = loading();
+      if (load > 2.0)
+        new_bins = (unsigned)(m_bins * load);
+      else if (load > 1.0)
+        new_bins = m_bins * 2;
+    }
+    if (new_bins == m_bins) return;
+    // set the new rehashing point if auto-rehashing is on
+    if (m_rehash) m_rehash = new_bins;
+    // move aside the old structure
+    hash_element<K,T,H,E>** old_values = m_values;
+    unsigned old_bins = m_bins;
+    // create a replacement structure
+    m_values = new hash_element<K,T,H,E>*[new_bins];
+    for (unsigned i = 0; i < new_bins; i++)
+      m_values[i] = 0;
+    m_bins = new_bins;
+    // move all the old elements across, rehashing each one
+    for (unsigned j = 0; j < old_bins; j++)
+    {
+      while(old_values[j])
+      {
+        // unhook from the old structure
+        hash_element<K,T,H,E>* current = old_values[j];
+        old_values[j] = current->m_next;
+        // rehash using the stored hash value
+        unsigned bin = current->bin();
+        // hook it into the new structure
+        current->m_next = m_values[bin];
+        m_values[bin] = current;
+      }
+    }
+    // now delete the old structure
+    delete[] old_values;
+  }
+
+  // the loading is the average number of elements per bin
+  // this simplifies to the total elements divided by the number of bins
+
+  template<typename K, typename T, class H, class E>
+  float hash<K,T,H,E>::loading(void) const
+  {
+    return (float)m_size / (float)m_bins;
+  }
+
+  // remove all elements from the table
+
+  template<typename K, typename T, class H, class E>
+  void hash<K,T,H,E>::erase(void)
+  {
+    // unhook the list elements and destroy them
+    for (unsigned i = 0; i < m_bins; i++)
+    {
+      hash_element<K,T,H,E>* current = m_values[i];
+      while(current)
+      {
+        hash_element<K,T,H,E>* next = current->m_next;
+        delete current;
+        current = next;
+      }
+      m_values[i] = 0;
+    }
+    m_size = 0;
+  }
+
+  // test for whether a key is present in the table
+
+  template<typename K, typename T, class H, class E>
+  bool hash<K,T,H,E>::present(const K& key) const
+  {
+    return find(key) != end();
+  }
+
+  template<typename K, typename T, class H, class E>
+  TYPENAME hash<K,T,H,E>::size_type hash<K,T,H,E>::count(const K& key) const
+  {
+    return present() ? 1 : 0;
+  }
+
+  // add a key and data element to the table - defined in terms of the general-purpose pair insert function
+
+  template<typename K, typename T, class H, class E>
+  TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::insert(const K& key, const T& data)
+  {
+    return insert(std::pair<const K,T>(key,data)).first;
+  }
+
+  // insert a key/data pair into the table
+  // this removes any old value with the same key since there is no multihash functionality
+
+  template<typename K, typename T, class H, class E>
+  std::pair<TYPENAME hash<K,T,H,E>::iterator, bool> hash<K,T,H,E>::insert(const std::pair<const K,T>& value)
+  {
+    // if auto-rehash is enabled, implement the auto-rehash before inserting the new value
+    // the table is rehashed if this insertion makes the loading exceed 1.0
+    if (m_rehash && (m_size >= m_rehash)) rehash();
+    // calculate the new hash value
+    unsigned hash_value_full = H()(value.first);
+    unsigned bin = hash_value_full % m_bins;
+    bool inserted = true;
+    // unhook any previous value with this key
+    // this has been inlined from erase(key) so that the hash value is not calculated twice
+    hash_element<K,T,H,E>* previous = 0;
+    for (hash_element<K,T,H,E>* current = m_values[bin]; current; previous = current, current = current->m_next)
+    {
+      // first check the full stored hash value
+      if (current->m_hash != hash_value_full) continue;
+
+      // next try the equality operator
+      if (!E()(current->m_value.first, value.first)) continue;
+
+      // unhook this value and destroy it
+      if (previous)
+        previous->m_next = current->m_next;
+      else
+        m_values[bin] = current->m_next;
+      delete current;
+      m_size--;
+
+      // we've overwritten a previous value
+      inserted = false;
+
+      // assume there can only be one match so we can give up now
+      break;
+    }
+    // now hook in a new list element at the start of the list for this hash value
+    hash_element<K,T,H,E>* new_item = new hash_element<K,T,H,E>(this, value, hash_value_full);
+    new_item->m_next = m_values[bin];
+    m_values[bin] = new_item;
+    // increment the size count
+    m_size++;
+    // construct an iterator from the list node, and return whether inserted
+    return std::make_pair(hash_iterator<K,T,H,E,std::pair<const K,T> >(new_item), inserted);
+  }
+
+  // insert a key with an empty data field ready to be filled in later
+
+  template<typename K, typename T, class H, class E>
+  TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::insert(const K& key)