|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-07-05 07:58:42
Author: asutton
Date: 2008-07-05 07:58:41 EDT (Sat, 05 Jul 2008)
New Revision: 47098
URL: http://svn.boost.org/trac/boost/changeset/47098
Log:
Restructuring into something a little more library-ish.
Added:
sandbox/SOC/2008/graphs/branches/descrip/containers.hpp
- copied, changed from r47097, /sandbox/SOC/2008/graphs/branches/descrip/container.hpp
sandbox/SOC/2008/graphs/branches/descrip/descriptors.hpp
- copied, changed from r47097, /sandbox/SOC/2008/graphs/branches/descrip/descriptor.hpp
Removed:
sandbox/SOC/2008/graphs/branches/descrip/container.hpp
sandbox/SOC/2008/graphs/branches/descrip/descriptor.hpp
Text files modified:
sandbox/SOC/2008/graphs/branches/descrip/containers.hpp | 4
sandbox/SOC/2008/graphs/branches/descrip/descriptor/functions.hpp | 30 ----------
sandbox/SOC/2008/graphs/branches/descrip/descriptor/list.hpp | 18 ------
sandbox/SOC/2008/graphs/branches/descrip/descriptor/map.hpp | 17 -----
sandbox/SOC/2008/graphs/branches/descrip/descriptor/multimap.hpp | 17 -----
sandbox/SOC/2008/graphs/branches/descrip/descriptor/multiset.hpp | 17 -----
sandbox/SOC/2008/graphs/branches/descrip/descriptor/set.hpp | 17 -----
sandbox/SOC/2008/graphs/branches/descrip/descriptor/vector.hpp | 18 ------
sandbox/SOC/2008/graphs/branches/descrip/descriptors.hpp | 116 +++++++++++++++++++++++++++++++++++----
9 files changed, 105 insertions(+), 149 deletions(-)
Deleted: sandbox/SOC/2008/graphs/branches/descrip/container.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/container.hpp 2008-07-05 07:58:41 EDT (Sat, 05 Jul 2008)
+++ (empty file)
@@ -1,351 +0,0 @@
-// (C) Copyright 2004 Jeremy Siek
-// (C) Copyright 2008 Andrew Sutton
-// 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
-
-#include <boost/type_traits.hpp>
-
-// Forward declarations of stdandard types. Jeremy's right! There does need
-// to be an <stlfwd> header since there's no guarantee that these are the
-// correct signatures for these types.
-namespace std
-{
- template <typename, typename> class vector;
- template <typename, typename> class list;
- template <typename, typename, typename> class set;
- template <typename, typename, typename> class multiset;
- template <typename, typename, typename, typename> class map;
- template <typename, typename, typename, typename> class multimap;
-}
-
-// 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 container_tag { };
-struct reversible_container_tag : virtual forward_container_tag { };
-struct random_access_container_tag : virtual reversible_container_tag { };
-
-// Sequential containers
-struct sequence_tag : virtual forward_container_tag { };
-struct front_insertion_sequence_tag : virtual sequence_tag { };
-struct back_insertion_sequence_tag : virtual sequence_tag { };
-
-// Associative containers
-struct associative_container_tag : virtual forward_container_tag { };
-struct sorted_associative_container_tag : virtual associative_container_tag, virtual reversible_container_tag { };
-struct unique_associative_container_tag : virtual associative_container_tag { };
-struct multiple_associative_container_tag : virtual associative_container_tag { };
-struct simple_associative_container_tag : virtual associative_container_tag { };
-struct pair_associative_container_tag : virtual associative_container_tag { };
-
-// These aren't real concepts, just combinations of others.
-struct set_container_tag : virtual simple_associative_container_tag, virtual unique_associative_container_tag { };
-struct map_container_tag : virtual pair_associative_container_tag, virtual unique_associative_container_tag { };
-struct multiset_container_tag : virtual simple_associative_container_tag, virtual multiple_associative_container_tag { };
-struct multimap_container_tag : virtual pair_associative_container_tag, virtual multiple_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;
-};
-
-// Trait accessors
-
-/** 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(); }
-
-// Metafunctions
-
-/**
- * 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;
-};
-
-/**
- * Evaluates to true if the container's elements are mapped to a key. This is
- * only true for pair associative containers, not sets (which are a little
- * different).
- */
-template <typename Container>
-struct contains_mapped_elements
-{
- static bool const value =
- boost::is_convertible<
- typename container_traits<Container>::category,
- pair_associative_container_tag
- >::value;
-};
-
-// Specializations
-
-// Vector
-struct vector_tag :
- virtual random_access_container_tag,
- virtual 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;
-};
-
-// List
-struct list_tag :
- virtual reversible_container_tag,
- virtual back_insertion_sequence_tag,
- virtual 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;
-};
-
-// TODO: Dequeue
-
-// Set
-struct set_tag :
- virtual sorted_associative_container_tag,
- virtual simple_associative_container_tag,
- virtual 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;
-};
-
-// Multiset
-struct multiset_tag :
- virtual sorted_associative_container_tag,
- virtual simple_associative_container_tag,
- virtual multiple_associative_container_tag
-{ };
-
-template <class T, class Compare, class Alloc>
-struct container_traits<std::multiset<T, Compare, Alloc>>
-{
- typedef multiset_tag category;
- typedef stable_iterator_tag iterator_stability;
-};
-
-// Map
-struct map_tag :
- virtual sorted_associative_container_tag,
- virtual pair_associative_container_tag,
- virtual unique_associative_container_tag
-{ };
-
-template <class Key, class T, class Compare, class Alloc>
-struct container_traits<std::map<Key, T, Compare, Alloc>>
-{
- typedef map_tag category;
- typedef stable_iterator_tag iterator_stability;
-};
-
-// Multimap
-struct multimap_tag :
- virtual sorted_associative_container_tag,
- virtual pair_associative_container_tag,
- virtual multiple_associative_container_tag
-{ };
-
-template <class Key, class T, class Compare, class Alloc>
-struct container_traits<std::multimap<Key, T, Compare, Alloc>>
-{
- typedef multimap_tag category;
- typedef stable_iterator_tag iterator_stability;
-};
-
-// TODO: Unordered Set
-// TODO: Unordered Multiset
-// TODO: Unordered Map
-// TODO: Unordered Multimap
-
-// Generic insert/remove functions
-
-namespace dispatch
-{
- template <typename Container, typename Value>
- inline typename Container::iterator
- insert(Container& c, Value const& x, back_insertion_sequence_tag)
- { return c.insert(c.end(), x); }
-
- template <typename Container, typename Value>
- inline typename Container::iterator
- insert(Container& c, Value const& x, unique_associative_container_tag)
- { return c.insert(x).first; }
-
- template <typename Container, typename Value>
- inline typename Container::iterator
- insert(Container& c, Value const& x, multiple_associative_container_tag)
- { return c.insert(x); }
-}
-
-template <typename Container, typename T>
-inline typename Container::iterator
-insert(Container& c, T const& x)
-{ return dispatch::insert(c, x, container_category(c)); }
-
-#if 0
-
- //===========================================================================
- // 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
Copied: sandbox/SOC/2008/graphs/branches/descrip/containers.hpp (from r47097, /sandbox/SOC/2008/graphs/branches/descrip/container.hpp)
==============================================================================
--- /sandbox/SOC/2008/graphs/branches/descrip/container.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/descrip/containers.hpp 2008-07-05 07:58:41 EDT (Sat, 05 Jul 2008)
@@ -4,8 +4,8 @@
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef CONTAINER_HPP
-#define CONTAINER_HPP
+#ifndef CONTAINERS_HPP
+#define CONTAINERS_HPP
#include <boost/type_traits.hpp>
Deleted: sandbox/SOC/2008/graphs/branches/descrip/descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/descriptor.hpp 2008-07-05 07:58:41 EDT (Sat, 05 Jul 2008)
+++ (empty file)
@@ -1,111 +0,0 @@
-
-#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_descriptor.hpp"
-#include "descriptor/index_descriptor.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;
-};
-
-
-template <typename Container>
-inline typename extended_container_traits<Container>::descriptor_type
-make_descriptor(Container& c, typename Container::iterator i)
-{ return typename extended_container_traits<Container>::descriptor_type(c, i); }
-
-template <typename Container>
-inline typename Container::iterator
-make_iterator(Container& c, typename extended_container_traits<Container>::descriptor_type d)
-{ return d.get(c); }
-
-/** 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"
-#include "descriptor/multiset.hpp"
-#include "descriptor/map.hpp"
-#include "descriptor/multimap.hpp"
-
-#endif
Modified: sandbox/SOC/2008/graphs/branches/descrip/descriptor/functions.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/descriptor/functions.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/functions.hpp 2008-07-05 07:58:41 EDT (Sat, 05 Jul 2008)
@@ -4,34 +4,4 @@
#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
Modified: sandbox/SOC/2008/graphs/branches/descrip/descriptor/list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/descriptor/list.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/list.hpp 2008-07-05 07:58:41 EDT (Sat, 05 Jul 2008)
@@ -2,23 +2,5 @@
#ifndef DESCRIPTOR_LIST_HPP
#define DESCRIPTOR_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;
-};
-
-/**
- * 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
Modified: sandbox/SOC/2008/graphs/branches/descrip/descriptor/map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/descriptor/map.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/map.hpp 2008-07-05 07:58:41 EDT (Sat, 05 Jul 2008)
@@ -2,22 +2,5 @@
#ifndef DESCRIPTOR_MAP_HPP
#define DESCRIPTOR_MAP_HPP
-/** Generate a map descriptor for a map with the given parameters. */
-template <typename K, typename T, typename Compare = std::less<T>, typename Alloc = std::allocator<T>>
-struct map_descriptor
-{
- typedef blob<sizeof(typename std::map<T, K, Compare, Alloc>::iterator)> blob_type;
- typedef node_descriptor<blob_type> type;
-};
-
-/**
- * Extended container traits for maps.
- */
-template <typename K, typename T, typename Compare, typename Alloc>
-struct extended_container_traits<std::map<K, T, Compare, Alloc>>
-{
- typedef typename map_descriptor<K, T, Compare, Alloc>::type descriptor_type;
- typedef stable_descriptor_tag descriptor_stability;
-};
#endif
Modified: sandbox/SOC/2008/graphs/branches/descrip/descriptor/multimap.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/descriptor/multimap.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/multimap.hpp 2008-07-05 07:58:41 EDT (Sat, 05 Jul 2008)
@@ -2,22 +2,5 @@
#ifndef DESCRIPTOR_MULTIMAP_HPP
#define DESCRIPTOR_MULTIMAP_HPP
-/** Generate a multimap descriptor for a multimap with the given parameters. */
-template <typename K, typename T, typename Compare = std::less<T>, typename Alloc = std::allocator<T>>
-struct multimap_descriptor
-{
- typedef blob<sizeof(typename std::multimap<T, K, Compare, Alloc>::iterator)> blob_type;
- typedef node_descriptor<blob_type> type;
-};
-
-/**
- * Extended container traits for multimaps.
- */
-template <typename K, typename T, typename Compare, typename Alloc>
-struct extended_container_traits<std::multimap<K, T, Compare, Alloc>>
-{
- typedef typename multimap_descriptor<K, T, Compare, Alloc>::type descriptor_type;
- typedef stable_descriptor_tag descriptor_stability;
-};
#endif
Modified: sandbox/SOC/2008/graphs/branches/descrip/descriptor/multiset.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/descriptor/multiset.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/multiset.hpp 2008-07-05 07:58:41 EDT (Sat, 05 Jul 2008)
@@ -2,23 +2,6 @@
#ifndef DESCRIPTOR_MULTISET_HPP
#define DESCRIPTOR_MULTISET_HPP
-/** Generate a multiset descriptor for a multiset with the given parameters. */
-template <typename T, typename Compare = std::less<T>, typename Alloc = std::allocator<T>>
-struct multiset_descriptor
-{
- typedef blob<sizeof(typename std::multiset<T, Compare, Alloc>::iterator)> blob_type;
- typedef node_descriptor<blob_type> type;
-};
-
-/**
- * Extended container traits for multisets.
- */
-template <typename T, typename Compare, typename Alloc>
-struct extended_container_traits<std::multiset<T, Compare, Alloc>>
-{
- typedef typename multiset_descriptor<T, Compare, Alloc>::type descriptor_type;
- typedef stable_descriptor_tag descriptor_stability;
-};
#endif
Modified: sandbox/SOC/2008/graphs/branches/descrip/descriptor/set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/descriptor/set.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/set.hpp 2008-07-05 07:58:41 EDT (Sat, 05 Jul 2008)
@@ -2,23 +2,6 @@
#ifndef DESCRIPTOR_SET_HPP
#define DESCRIPTOR_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;
-};
-
-/**
- * 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
Modified: sandbox/SOC/2008/graphs/branches/descrip/descriptor/vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/descriptor/vector.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/vector.hpp 2008-07-05 07:58:41 EDT (Sat, 05 Jul 2008)
@@ -2,23 +2,5 @@
#ifndef DESCRIPTOR_VECTOR_HPP
#define DESCRIPTOR_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;
-};
-
-/**
- * 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
Copied: sandbox/SOC/2008/graphs/branches/descrip/descriptors.hpp (from r47097, /sandbox/SOC/2008/graphs/branches/descrip/descriptor.hpp)
==============================================================================
--- /sandbox/SOC/2008/graphs/branches/descrip/descriptor.hpp (original)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptors.hpp 2008-07-05 07:58:41 EDT (Sat, 05 Jul 2008)
@@ -1,9 +1,9 @@
-#ifndef DESCRIPTOR_HPP
-#define DESCRIPTOR_HPP
+#ifndef DESCRIPTORS_HPP
+#define DESCRIPTORS_HPP
// Pull the container traits.
-#include "container.hpp"
+#include "containers.hpp"
// Some descriptors are built on blobs.
#include "blob.hpp"
@@ -75,37 +75,127 @@
* This inherits a specialized version of container traits from boost/pending.
*/
template <typename Container>
-struct extended_container_traits
+struct descriptor_traits
{
typedef typename Container::descriptor_type descriptor_type;
typedef typename Container::descriptor_stability descriptor_stability;
};
-
+/**
+ * Given a container and a valid iterator into the container, return a
+ * descriptor to the object being pointed at. The descriptor is guaranteed to
+ * be at least as long as the iterator, generally longer.
+ */
template <typename Container>
inline typename extended_container_traits<Container>::descriptor_type
make_descriptor(Container& c, typename Container::iterator i)
{ return typename extended_container_traits<Container>::descriptor_type(c, i); }
+/**
+ * Given a container and a valid descriptor, return an iterator pointing to the
+ * described object. The iterator will be valid as long as the descriptor has
+ * not been invalidated (e.g., removing an item from a vector).
+ */
template <typename Container>
inline typename Container::iterator
make_iterator(Container& c, typename extended_container_traits<Container>::descriptor_type d)
{ return d.get(c); }
+
/** 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(); }
+// Metafunctions
+
+/**
+ * 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;
+};
+
+// Specializations
+
+// Vector
+template <typename T, typename Alloc>
+struct descriptor_traits<std::vector<T, Alloc>>
+{
+ typedef index_descriptor<std::vector<T, Alloc>> descriptor_type;
+ typedef unstable_remove_tag descriptor_stability;
+};
+
+// List
+template <typename T, typename Alloc>
+struct descriptor_traits<std::list<T, Alloc>>
+{
+ typedef blob<sizeof(typename std::list<T, Alloc>::iterator)> descriptor_type;
+ typedef stable_descriptor_tag descriptor_stability;
+};
+
+// TODO: Dequeue
+
+// Set
+template <typename T, typename Compare, typename Alloc>
+struct extended_container_traits<std::set<T, Compare, Alloc>>
+{
+ typedef blob<sizeof(typename std::set<T, Compare, Alloc>::iterator)> descriptor_type;
+ typedef stable_descriptor_tag descriptor_stability;
+};
+
+// Multiset
+template <typename T, typename Compare, typename Alloc>
+struct extended_container_traits<std::multiset<T, Compare, Alloc>>
+{
+ typedef typename blob<sizeof(typename std::multiset<T, Compare, Alloc>::iterator)> descriptor_type;
+ typedef stable_descriptor_tag descriptor_stability;
+};
+
+// Map
+template <typename K, typename T, typename Compare, typename Alloc>
+struct extended_container_traits<std::map<K, T, Compare, Alloc>>
+{
+ typedef blob<sizeof(typename std::map<T, K, Compare, Alloc>::iterator)> descriptor_type;
+ typedef stable_descriptor_tag descriptor_stability;
+};
+
+// Multimap
+template <typename K, typename T, typename Compare, typename Alloc>
+struct extended_container_traits<std::multimap<K, T, Compare, Alloc>>
+{
+ typedef blob<sizeof(typename std::multimap<T, K, Compare, Alloc>::iterator)> descriptor_type;
+ typedef stable_descriptor_tag descriptor_stability;
+};
+
+// TODO: Unordered Set
+// TODO: Unordered Multiset
+// TODO: Unordered Map
+// TODO: Unordered Multimap
-// Pull specializations and metafunctions.
-#include "descriptor/functions.hpp"
-#include "descriptor/vector.hpp"
-#include "descriptor/list.hpp"
-#include "descriptor/set.hpp"
-#include "descriptor/multiset.hpp"
-#include "descriptor/map.hpp"
-#include "descriptor/multimap.hpp"
#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