|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-07-04 09:55:01
Author: asutton
Date: 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
New Revision: 47074
URL: http://svn.boost.org/trac/boost/changeset/47074
Log:
Experimenting with rebuilding the descriptor library and pulling the older
container traits in to help out (which is also getting a facelift).
Added:
sandbox/SOC/2008/graphs/branches/descrip/blob.hpp (contents, props changed)
sandbox/SOC/2008/graphs/branches/descrip/container/
sandbox/SOC/2008/graphs/branches/descrip/container.hpp (contents, props changed)
sandbox/SOC/2008/graphs/branches/descrip/container/functions.hpp (contents, props changed)
sandbox/SOC/2008/graphs/branches/descrip/container/list.hpp (contents, props changed)
sandbox/SOC/2008/graphs/branches/descrip/container/set.hpp (contents, props changed)
sandbox/SOC/2008/graphs/branches/descrip/container/vector.hpp (contents, props changed)
sandbox/SOC/2008/graphs/branches/descrip/demangle.hpp (contents, props changed)
sandbox/SOC/2008/graphs/branches/descrip/descriptor/
sandbox/SOC/2008/graphs/branches/descrip/descriptor.hpp (contents, props changed)
sandbox/SOC/2008/graphs/branches/descrip/descriptor/functions.hpp (contents, props changed)
sandbox/SOC/2008/graphs/branches/descrip/descriptor/index.hpp (contents, props changed)
sandbox/SOC/2008/graphs/branches/descrip/descriptor/list.hpp (contents, props changed)
sandbox/SOC/2008/graphs/branches/descrip/descriptor/node.hpp (contents, props changed)
sandbox/SOC/2008/graphs/branches/descrip/descriptor/set.hpp (contents, props changed)
sandbox/SOC/2008/graphs/branches/descrip/descriptor/vector.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/branches/descrip/Jamfile | 7 ++++++-
1 files changed, 6 insertions(+), 1 deletions(-)
Modified: sandbox/SOC/2008/graphs/branches/descrip/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/Jamfile (original)
+++ sandbox/SOC/2008/graphs/branches/descrip/Jamfile 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -1,2 +1,7 @@
-exe decoup : decoup.cpp : <include>../../trunk ;
+# NOTE... only compiles with experimental compiler (oops).
+
+using gcc : 4.4 : g++-4.4 : <cxxflags>-std=c++0x ;
+
+exe des : des.cpp : <include>../../trunk : <toolset>gcc-4.4 ;
+exe blob : blob.cpp : <include>../../trunk : <toolset>gcc-4.4 ;
Added: sandbox/SOC/2008/graphs/branches/descrip/blob.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/blob.hpp 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,103 @@
+
+#ifndef BLOB_HPP
+#define BLOB_HPP
+
+#include <cstring>
+
+#include <boost/functional/hash.hpp>
+
+/**
+ * The blob type is used to allocate a small buffer of memory that can be
+ * reinterpreted as a type of the same size. This is used solely as a means
+ * of deferring the immediate need for the type of an object if you can guess
+ * its size.
+ *
+ * One can imagine this stands for "Binary Little OBject". Little because you
+ * probably don't want to copy these around all over the place.
+ *
+ * If you're going to write something hacky, you may as well try to make it a
+ * little bit pretty.
+ */
+template <unsigned int N>
+struct blob
+{
+ inline blob()
+ : mem()
+ { std::memset(mem, 0, N); }
+
+ inline blob(blob const& x)
+ : mem()
+ { std::memcpy(mem, x.mem, N); }
+
+ template <typename T>
+ inline blob(const T& x)
+ : mem()
+ { put(x); }
+
+ /** Put the value of x into the blob object. */
+ template <typename T>
+ inline void put(T const& x)
+ {
+ static_assert(sizeof(T) == N, "Putting value of wrong size");
+ char const* p = reinterpret_cast<char const*>(&x);
+ std::memcpy(mem, p, N);
+ }
+
+ /** Get the value of the blob object, returning it as an object of type T. */
+ template <typename T>
+ inline T& get() const
+ {
+ static_assert(sizeof(T) == N, "Getting value of wrong size");
+ return *reinterpret_cast<T*>(mem);
+ }
+
+ /** @name Equality Comparable
+ * Two blob objects (of the same size) are equal iff their memory contents
+ * are the same.
+ */
+ //@{
+ inline bool operator==(const blob& x) const
+ { return std::memcmp(mem, x.mem, N) == 0; }
+
+ inline bool operator!=(const blob& x) const
+ { return !operator==(x); }
+ //@}
+
+ /** @name Less Than Comparable
+ * A blob is less than another (of the same size) iff its memory contents
+ * are byte-wise less than those of the other. This comparison does not
+ * guarantee that the stored object is less than the other, only that its
+ * bit representation is bite-wise less, which is the same as numerically
+ * less on little (or is it big) endian systems. The big thing is that you
+ * shouldn't attach any real meaning on the ordering.
+ */
+ //@{
+ inline bool operator<(const blob& x) const
+ { return std::memcmp(mem, x.mem, N) < 0; }
+
+ inline bool operator>(const blob& x) const
+ { return std::memcmp(mem, x.mem, N) > 0; }
+
+ inline bool operator<=(const blob& x) const
+ { return std::memcmp(mem, x.mem, N) <= 0; }
+
+ inline bool operator>=(const blob& x) const
+ { return std::memcmp(mem, x.mem, N) >= 0; }
+ //@}
+
+ mutable char mem[N];
+};
+
+template <unsigned int N>
+std::size_t
+hash_value(blob<N> const& x)
+{
+ using boost::hash_value;
+ std::size_t seed = 0;
+ for(int i = 0; i < N; ++i) {
+ boost::hash_combine(seed, x.mem[i]);
+ }
+ return seed;
+}
+
+#endif
Added: sandbox/SOC/2008/graphs/branches/descrip/container.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/container.hpp 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,290 @@
+// (C) Copyright Jeremy Siek 2004
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef CONTAINER_HPP
+#define CONTAINER_HPP
+
+// TODO: This probably all goes away with concepts. Seeing as how concepts
+// aren't in C++ just yet, we'll still do things this way.
+
+// Container Category Tags
+// These define the basic concepts of STL containers. Note the use of
+// virtual inheritance because there are lots of inheritance diamonds.
+struct container_tag { };
+struct forward_container_tag : virtual public container_tag { };
+struct reversible_container_tag : virtual public forward_container_tag { };
+struct random_access_container_tag : virtual public reversible_container_tag { };
+struct sequence_tag : virtual public forward_container_tag { };
+struct associative_container_tag : virtual public forward_container_tag { };
+struct sorted_associative_container_tag : virtual public associative_container_tag , virtual public reversible_container_tag { };
+struct front_insertion_sequence_tag : virtual public sequence_tag { };
+struct back_insertion_sequence_tag : virtual public sequence_tag { };
+struct unique_associative_container_tag : virtual public associative_container_tag { };
+struct multiple_associative_container_tag : virtual public associative_container_tag { };
+struct simple_associative_container_tag : virtual public associative_container_tag { };
+struct pair_associative_container_tag : virtual public associative_container_tag { };
+
+// Iterator Stability Tags
+// These tags determine the "stability" of iterators. Do mutating operations
+// such as insert/erase/resize invalidate all outstanding iterators, or just
+// those being removed. Most node-based implementations have stable iteraors,
+// while vectors are generally unstable.
+struct stable_iterator_tag { };
+struct unstable_iterator_tag { };
+
+/**
+ * The container traits class defines the basic container concepts and iterator
+ * stability properties of the given container.
+ */
+template <class Container>
+struct container_traits
+{
+ typedef typename Container::category category;
+ typedef typename Container::iterator_stability iterator_stability;
+};
+
+/** Return the container category tag of the given container. */
+template <typename Container>
+inline typename container_traits<Container>::category
+container_category(Container const&)
+{ return typename container_traits<Container>::category(); }
+
+/** Return the iterator stability tag of the given container. */
+template <class Container>
+inline typename container_traits<Container>::iterator_stability
+iterator_stability(Container const&)
+{ return typename container_traits<Container>::iterator_stability(); }
+
+// Pull specializtions and metafunctions.
+#include "container/functions.hpp"
+#include "container/vector.hpp"
+#include "container/list.hpp"
+#include "container/set.hpp"
+
+// Use this as a compile-time assertion that X is stable
+// inline void require_stable(stable_tag) { }
+
+#if 0
+
+ // std::multiset
+ struct multiset_tag :
+ virtual public sorted_associative_container_tag,
+ virtual public simple_associative_container_tag,
+ virtual public multiple_associative_container_tag
+ { };
+
+ template <class Key, class Cmp, class Alloc>
+ multiset_tag container_category(const std::multiset<Key,Cmp,Alloc>&)
+ { return multiset_tag(); }
+
+ template <class Key, class Cmp, class Alloc>
+ stable_tag iterator_stability(const std::multiset<Key,Cmp,Alloc>&)
+ { return stable_tag(); }
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ template <class Key, class Cmp, class Alloc>
+ struct container_traits< std::multiset<Key,Cmp,Alloc> > {
+ typedef multiset_tag category;
+ typedef stable_tag iterator_stability;
+ };
+#endif
+
+ // deque
+
+ // std::map
+ struct map_tag :
+ virtual public sorted_associative_container_tag,
+ virtual public pair_associative_container_tag,
+ virtual public unique_associative_container_tag
+ { };
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ template <class Key, class T, class Cmp, class Alloc>
+ struct container_traits< std::map<Key,T,Cmp,Alloc> > {
+ typedef map_tag category;
+ typedef stable_tag iterator_stability;
+ };
+#endif
+
+ template <class Key, class T, class Cmp, class Alloc>
+ map_tag container_category(const std::map<Key,T,Cmp,Alloc>&)
+ { return map_tag(); }
+
+ template <class Key, class T, class Cmp, class Alloc>
+ stable_tag iterator_stability(const std::map<Key,T,Cmp,Alloc>&)
+ { return stable_tag(); }
+
+ // std::multimap
+ struct multimap_tag :
+ virtual public sorted_associative_container_tag,
+ virtual public pair_associative_container_tag,
+ virtual public multiple_associative_container_tag
+ { };
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ template <class Key, class T, class Cmp, class Alloc>
+ struct container_traits< std::multimap<Key,T,Cmp,Alloc> > {
+ typedef multimap_tag category;
+ typedef stable_tag iterator_stability;
+ };
+#endif
+
+ template <class Key, class T, class Cmp, class Alloc>
+ multimap_tag container_category(const std::multimap<Key,T,Cmp,Alloc>&)
+ { return multimap_tag(); }
+
+ template <class Key, class T, class Cmp, class Alloc>
+ stable_tag iterator_stability(const std::multimap<Key,T,Cmp,Alloc>&)
+ { return stable_tag(); }
+
+
+ // hash_set, hash_map
+
+#ifndef BOOST_NO_HASH
+#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ template <class Key, class Eq, class Hash, class Alloc>
+ struct container_traits< BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc> > {
+ typedef set_tag category;
+ typedef stable_tag iterator_stability; // is this right?
+ };
+ template <class Key, class T, class Eq, class Hash, class Alloc>
+ struct container_traits< BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc> > {
+ typedef map_tag category;
+ typedef stable_tag iterator_stability; // is this right?
+ };
+#endif
+ template <class Key, class Eq, class Hash, class Alloc>
+ set_tag container_category(const BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc>&)
+ { return set_tag(); }
+
+ template <class Key, class T, class Eq, class Hash, class Alloc>
+ map_tag container_category(const BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc>&)
+ { return map_tag(); }
+
+ template <class Key, class Eq, class Hash, class Alloc>
+ stable_tag iterator_stability(const BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc>&)
+ { return stable_tag(); }
+
+ template <class Key, class T, class Eq, class Hash, class Alloc>
+ stable_tag iterator_stability(const BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc>&)
+ { return stable_tag(); }
+#endif
+
+
+
+ //===========================================================================
+ // Generalized Container Functions
+
+
+ // Erase
+ template <class Sequence, class T>
+ void erase_dispatch(Sequence& c, const T& x,
+ sequence_tag)
+ {
+ c.erase(std::remove(c.begin(), c.end(), x), c.end());
+ }
+
+ template <class AssociativeContainer, class T>
+ void erase_dispatch(AssociativeContainer& c, const T& x,
+ associative_container_tag)
+ {
+ c.erase(x);
+ }
+ template <class Container, class T>
+ void erase(Container& c, const T& x)
+ {
+ erase_dispatch(c, x, container_category(c));
+ }
+
+ // Erase If
+ template <class Sequence, class Predicate, class IteratorStability>
+ void erase_if_dispatch(Sequence& c, Predicate p,
+ sequence_tag, IteratorStability)
+ {
+#if 0
+ c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
+#else
+ if (! c.empty())
+ c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
+#endif
+ }
+ template <class AssociativeContainer, class Predicate>
+ void erase_if_dispatch(AssociativeContainer& c, Predicate p,
+ associative_container_tag, stable_tag)
+ {
+ typename AssociativeContainer::iterator i, next;
+ for (i = next = c.begin(); next != c.end(); i = next) {
+ ++next;
+ if (p(*i))
+ c.erase(i);
+ }
+ }
+ template <class AssociativeContainer, class Predicate>
+ void erase_if_dispatch(AssociativeContainer& c, Predicate p,
+ associative_container_tag, unstable_tag)
+ {
+ // This method is really slow, so hopefully we won't have any
+ // associative containers with unstable iterators!
+ // Is there a better way to do this?
+ typename AssociativeContainer::iterator i;
+ typename AssociativeContainer::size_type n = c.size();
+ while (n--)
+ for (i = c.begin(); i != c.end(); ++i)
+ if (p(*i)) {
+ c.erase(i);
+ break;
+ }
+ }
+ template <class Container, class Predicate>
+ void erase_if(Container& c, Predicate p)
+ {
+ erase_if_dispatch(c, p, container_category(c), iterator_stability(c));
+ }
+
+ // Push
+ template <class Container, class T>
+ std::pair<typename Container::iterator, bool>
+ push_dispatch(Container& c, const T& v, back_insertion_sequence_tag)
+ {
+ c.push_back(v);
+ return std::make_pair(boost::prior(c.end()), true);
+ }
+
+ template <class Container, class T>
+ std::pair<typename Container::iterator, bool>
+ push_dispatch(Container& c, const T& v, front_insertion_sequence_tag)
+ {
+ c.push_front(v);
+ return std::make_pair(c.begin(), true);
+ }
+
+ template <class AssociativeContainer, class T>
+ std::pair<typename AssociativeContainer::iterator, bool>
+ push_dispatch(AssociativeContainer& c, const T& v,
+ unique_associative_container_tag)
+ {
+ return c.insert(v);
+ }
+
+ template <class AssociativeContainer, class T>
+ std::pair<typename AssociativeContainer::iterator, bool>
+ push_dispatch(AssociativeContainer& c, const T& v,
+ multiple_associative_container_tag)
+ {
+ return std::make_pair(c.insert(v), true);
+ }
+
+ template <class Container, class T>
+ std::pair<typename Container::iterator,bool>
+ push(Container& c, const T& v)
+ {
+ return push_dispatch(c, v, container_category(c));
+ }
+
+}} // namespace boost::graph_detail
+
+#endif
+
+#endif
Added: sandbox/SOC/2008/graphs/branches/descrip/container/functions.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/container/functions.hpp 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,20 @@
+
+#ifndef CONTAINER_FUNCTIONS_HPP
+#define CONTAINER_FUNCTIONS_HPP
+
+#include <boost/type_traits.hpp>
+
+/**
+ * Evaluates to true if the container contains unique elements.
+ */
+template <typename Container>
+struct contains_unique_elements
+{
+ static bool const value =
+ boost::is_convertible<
+ typename container_traits<Container>::category,
+ unique_associative_container_tag
+ >::value;
+};
+
+#endif
Added: sandbox/SOC/2008/graphs/branches/descrip/container/list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/container/list.hpp 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,18 @@
+
+#ifndef CONTAINER_LIST_HPP
+#define CONTAINER_LIST_HPP
+
+struct list_tag :
+ virtual public reversible_container_tag,
+ virtual public back_insertion_sequence_tag,
+ virtual public front_insertion_sequence_tag
+{ };
+
+template <class T, class Alloc>
+struct container_traits<std::list<T,Alloc>>
+{
+ typedef list_tag category;
+ typedef stable_iterator_tag iterator_stability;
+};
+
+#endif
Added: sandbox/SOC/2008/graphs/branches/descrip/container/set.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/container/set.hpp 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,19 @@
+
+#ifndef CONTAINER_SET_HPP
+#define CONTAINER_SET_HPP
+
+struct set_tag :
+ virtual public sorted_associative_container_tag,
+ virtual public simple_associative_container_tag,
+ virtual public unique_associative_container_tag
+{ };
+
+
+template <class Key, class Cmp, class Alloc>
+struct container_traits<std::set<Key,Cmp,Alloc>>
+{
+ typedef set_tag category;
+ typedef stable_iterator_tag iterator_stability;
+};
+
+#endif
Added: sandbox/SOC/2008/graphs/branches/descrip/container/vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/container/vector.hpp 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,17 @@
+
+#ifndef CONTAINER_VECTOR_HPP
+#define CONTAINER_VECTOR_HPP
+
+struct vector_tag :
+ virtual public random_access_container_tag,
+ virtual public back_insertion_sequence_tag
+{ };
+
+template <class T, class Alloc>
+struct container_traits<std::vector<T,Alloc>>
+{
+ typedef vector_tag category;
+ typedef unstable_iterator_tag iterator_stability;
+};
+
+#endif
Added: sandbox/SOC/2008/graphs/branches/descrip/demangle.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/demangle.hpp 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,22 @@
+
+#ifndef DEMANGLE_HPP
+#define DEMANGLE_HPP
+
+#include <string>
+#include <typeinfo>
+#include <cxxabi.h>
+
+inline std::string
+demangle(std::string const& name)
+{
+ return std::string(abi::__cxa_demangle(name.c_str(), 0, 0, 0));
+}
+
+template <typename T>
+inline std::string
+demangle()
+{
+ return demangle(typeid(T).name());
+}
+
+#endif
Added: sandbox/SOC/2008/graphs/branches/descrip/descriptor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor.hpp 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,97 @@
+
+#ifndef DESCRIPTOR_HPP
+#define DESCRIPTOR_HPP
+
+// Pull the container traits.
+#include "container.hpp"
+
+// Some descriptors are built on blobs.
+#include "blob.hpp"
+
+// Descriptor implementations.
+#include "descriptor/node.hpp"
+#include "descriptor/index.hpp"
+
+
+// Descriptors Take 2 (or 3 or 4).
+//
+// Note that we can't build descriptors on template names alone becaue we can't
+// guarantee that arbitrary template parameters won't change the size of the
+// iterator (e.g., comparators, allocators, or other policies). We should be
+// able to say that the size of the iterator must NOT change with respect to
+// the contained type.
+//
+// Basically, what I'm trying to say is that a descriptor type can be applied
+// to every vector for which its value type is compatible - which is a really
+// odd thing to think about.
+
+// Operations on descriptors:
+// This is the minimum interface supported by all containers that support
+// descriptors. These operators are all constant (or at least constant with
+// respect to the size of the container).
+//
+// --- get_descriptor(container, iterator) ---
+// Given a container and a valid iterator, generate a descriptor to the value
+// pointed at by the iterator.
+//
+// --- get_iterator(container, descriptor) ---
+// Given a container and valid descriptor, return an iterator to the described
+// value.
+
+// Various Notes...
+// What's the real tradeoff for using template template parameters versus just
+// template parameters. For example:
+// template <typename T, template <typename> class Alloc = std::allocator>
+// template <typename T, typename Alloc = std::allocator<T>
+//
+// The first version decouples the specification of the allocator from the type
+// that it will eventually be applied to. The downside is that it restricts the
+// allocator to being parameterized over a single parameter. It's possible that
+// the allocator is actually parameterized over several different policies or
+// strategies. Of course, these policies can be reduced to a single template
+// using inheritance and/or template aliases.
+
+// Operator Stability Tags
+// These tags define the stability of container's descriptors under insert and
+// remove operations. Note that unstable operations should not be used in
+// relational data structures (like graphs) since these operations will
+// invalidate all outstanding descriptors. There are only two mutating
+// operations worth describing: insert and remove. A container that is unstable
+// for both operations has unstable mutators.
+//
+// Note that it is certainly possible for a container to be unstable for both
+// insertions and removals. These data structures are generally constructed over
+// a known set of objects and are generally immutable afterwards.
+struct stable_descriptor_tag { };
+struct unstable_insert_tag { };
+struct unstable_remove_tag { };
+struct unstable_mutators_tag : unstable_insert_tag, unstable_remove_tag { };
+
+/**
+ * This metafunction contains some basic traits related to descriptors of
+ * containers. This structure must be specialized by each container. By default
+ * the types and properties of this class reference nested types of the
+ * container, which are basically doomed to fail.
+ *
+ * This inherits a specialized version of container traits from boost/pending.
+ */
+template <typename Container>
+struct extended_container_traits
+{
+ typedef typename Container::descriptor_type descriptor_type;
+ typedef typename Container::descriptor_stability descriptor_stability;
+};
+
+/** Return the descriptor stability tag for the given container. */
+template <typename Container>
+inline typename extended_container_traits<Container>::descriptor_stability
+descriptor_stability(Container const&)
+{ return typename extended_container_traits<Container>::descriptor_stability(); }
+
+// Pull specializations and metafunctions.
+#include "descriptor/functions.hpp"
+#include "descriptor/vector.hpp"
+#include "descriptor/list.hpp"
+#include "descriptor/set.hpp"
+
+#endif
Added: sandbox/SOC/2008/graphs/branches/descrip/descriptor/functions.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/functions.hpp 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,38 @@
+
+#ifndef DESCRIPTOR_FUNCTIONS_HPP
+#define DESCRIPTOR_FUNCTIONS_HPP
+
+#include <boost/type_traits.hpp>
+
+/**
+ * Returns true if the cotnainer supports insert operations that do not
+ * invalidate outstanding descriptors.
+ */
+template <typename Container>
+struct has_insert_mutator
+{
+ // True if not convertible to unstable_insert_tag.
+ static bool const value =
+ !boost::is_convertible<
+ typename extended_container_traits<Container>::descriptor_stability,
+ unstable_insert_tag
+ >::value;
+};
+
+
+/**
+ * Returns true if the container supports remove operations that do not
+ * invalidate outstanding descriptors.
+ */
+template <typename Container>
+struct has_remove_mutator
+{
+ // True if not convertible to unstable_remove_tag.
+ static bool const value =
+ !boost::is_convertible<
+ typename extended_container_traits<Container>::descriptor_stability,
+ unstable_remove_tag
+ >::value;
+};
+
+#endif
Added: sandbox/SOC/2008/graphs/branches/descrip/descriptor/index.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/index.hpp 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,62 @@
+
+#ifndef INDEX_DESCRIPTOR_HPP
+#define INDEX_DESCRIPTOR_HPP
+
+#include <boost/functional/hash.hpp>
+
+/**
+ * The index_descriptor simply maintains the descriptor as an index into the
+ * given offset.
+ */
+template <typename Index>
+struct index_descriptor
+{
+ typedef Index descriptor_type;
+
+ inline index_descriptor()
+ : value(-1)
+ { }
+
+ inline index_descriptor(descriptor_type d)
+ : value(d)
+ { }
+
+ inline bool is_null() const
+ { return value == descriptor_type(-1); }
+
+ /** @name Equality Comparable */
+ //@{
+ inline bool operator==(index_descriptor const& x)
+ { return value == x.value; }
+
+ inline bool operator!=(index_descriptor const& x)
+ { return value != x.value; }
+ //@}
+
+ /** @name Less Than Comparable */
+ //@{
+ inline bool operator<(index_descriptor const& x)
+ { return value < x.value; }
+
+ inline bool operator>(index_descriptor const& x)
+ { return value > x.value; }
+
+ inline bool operator<=(index_descriptor const& x)
+ { return value <= x.value; }
+
+ inline bool operator>=(index_descriptor const& x)
+ { return value >= x.value; }
+ //@}
+
+ descriptor_type value;
+};
+
+// A hash function for indexed descriptors.
+template <typename Index>
+std::size_t hash_value(index_descriptor<Index> const& x)
+{
+ using boost::hash_value;
+ return hash_value(x.value);
+}
+
+#endif
Added: sandbox/SOC/2008/graphs/branches/descrip/descriptor/list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/list.hpp 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,40 @@
+
+#ifndef LIST_HPP
+#define LIST_HPP
+
+/** Generate a descriptor for a list wtih the given properties. */
+template <typename T, typename Alloc = std::allocator<T>>
+struct list_descriptor
+{
+ typedef blob<sizeof(typename std::list<T, Alloc>::iterator)> blob_type;
+ typedef node_descriptor<blob_type> type;
+};
+
+template <typename T, typename Alloc>
+inline typename list_descriptor<T, Alloc>::type
+get_descriptor(std::list<T, Alloc>& c, typename std::list<T, Alloc>::iterator i)
+{
+ typedef typename list_descriptor<T, Alloc>::type result_type;
+ return result_type(i);
+}
+
+template <typename T, typename Alloc>
+inline typename std::list<T, Alloc>::iterator
+get_iterator(std::list<T, Alloc>& c, typename list_descriptor<T, Alloc>::type d)
+{
+ typedef typename std::list<T, Alloc>::iterator result_type;
+ return d.value.template get<result_type>();
+}
+
+/**
+ * Extended container traits for lists.
+ */
+template <typename T, typename Alloc>
+struct extended_container_traits<std::list<T, Alloc>>
+{
+ typedef typename list_descriptor<T, Alloc>::type descriptor_type;
+ typedef stable_descriptor_tag descriptor_stability;
+};
+
+
+#endif
Added: sandbox/SOC/2008/graphs/branches/descrip/descriptor/node.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/node.hpp 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,49 @@
+
+#ifndef VECTOR_DESCRIPTOR_HPP
+#define VECTOR_DESCRIPTOR_HPP
+
+/**
+ * The node descriptor contains an iterator into the target container. The
+ * container iterator is just a pattern for the actual iterator and has no
+ * real type (it's opaque).
+ */
+template <typename Blob>
+struct node_descriptor
+{
+ typedef Blob descriptor_type;
+
+ node_descriptor()
+ : value()
+ { }
+
+ node_descriptor(descriptor_type const& x)
+ : value(x)
+ { }
+
+ inline bool is_null()
+ { return value == descriptor_type(); }
+
+ /** @name Equality Comparable */
+ //@{
+ inline bool operator==(node_descriptor const& x)
+ { return value == x.value; }
+
+ inline bool operator!=(node_descriptor const& x)
+ { return value != x.value; }
+ //@}
+
+ /** @name Less Than Comparable */
+ //@{
+ inline bool operator<(node_descriptor const& x)
+ { return value < x.value; }
+ //@}
+
+ descriptor_type value;
+};
+
+template <typename Container>
+inline bool
+is_null(node_descriptor<Container> const d)
+{ return d.value == typename node_descriptor<Container>::descriptor_type(); }
+
+#endif
Added: sandbox/SOC/2008/graphs/branches/descrip/descriptor/set.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/set.hpp 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,41 @@
+
+#ifndef SET_HPP
+#define SET_HPP
+
+/** Generate a set descriptor for a set with the given parameters. */
+template <typename T, typename Compare = std::less<T>, typename Alloc = std::allocator<T>>
+struct set_descriptor
+{
+ typedef blob<sizeof(typename std::set<T, Compare, Alloc>::iterator)> blob_type;
+ typedef node_descriptor<blob_type> type;
+};
+
+template <typename T, typename Compare, typename Alloc>
+inline typename set_descriptor<T, Compare, Alloc>::type
+get_descriptor(std::set<T, Compare, Alloc>& c, typename std::set<T, Compare, Alloc>::iterator i)
+{
+ typedef typename set_descriptor<T, Compare, Alloc>::type result_type;
+ return result_type(i);
+}
+
+template <typename T, typename Compare, typename Alloc>
+inline typename std::set<T, Compare, Alloc>::iterator
+get_iterator(std::set<T, Compare, Alloc>& c, typename set_descriptor<T, Compare, Alloc>::type d)
+{
+ typedef typename std::set<T, Compare, Alloc>::iterator result_type;
+ return d.value.template get<result_type>();
+}
+
+/**
+ * Extended container traits for sets.
+ */
+template <typename T, typename Compare, typename Alloc>
+struct extended_container_traits<std::set<T, Compare, Alloc>>
+{
+ typedef typename set_descriptor<T, Compare, Alloc>::type descriptor_type;
+ typedef stable_descriptor_tag descriptor_stability;
+};
+
+
+
+#endif
Added: sandbox/SOC/2008/graphs/branches/descrip/descriptor/vector.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/vector.hpp 2008-07-04 09:54:59 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,38 @@
+
+#ifndef VECTOR_HPP
+#define VECTOR_HPP
+
+/** Generate a descriptor for any vector with the given properties. */
+template <typename T, typename Alloc = std::allocator<T>>
+struct vector_descriptor
+{
+ typedef typename std::vector<T, Alloc>::size_type index_type;
+ typedef index_descriptor<index_type> type;
+};
+
+template <typename T, typename Alloc>
+inline typename vector_descriptor<T, Alloc>::type
+get_descriptor(std::vector<T, Alloc>& c, typename std::vector<T, Alloc>::iterator i)
+{
+ typedef typename vector_descriptor<T, Alloc>::type result_type;
+ return result_type(std::distance(c.begin(), i));
+}
+
+template <typename T, typename Alloc>
+inline typename std::vector<T, Alloc>::iterator
+get_iterator(std::vector<T, Alloc>& c, typename vector_descriptor<T, Alloc>::type d)
+{
+ return std::next(c.begin(), d.value);
+}
+
+/**
+ * Extended container traits for vectors.
+ */
+template <typename T, typename Alloc>
+struct extended_container_traits<std::vector<T, Alloc>>
+{
+ typedef typename vector_descriptor<T, Alloc>::type descriptor_type;
+ typedef unstable_remove_tag descriptor_stability;
+};
+
+#endif
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk