[Boost-commit] svn:boost r47075 - in sandbox/SOC/2008/graphs/branches/descrip: . container descriptor structures

From: asutton_at_[hidden]
Date: 2008-07-04 11:05:55

Author: asutton
Date: 2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
New Revision: 47075
URL: http://svn.boost.org/trac/boost/changeset/47075

Log:
Committing changes. The sorted sequence is just a work in progress.

Added:
   sandbox/SOC/2008/graphs/branches/descrip/blob.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/descrip/container/map.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/descrip/container/multimap.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/descrip/container/multiset.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/descrip/des.cpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/descrip/descriptor/map.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/descrip/descriptor/multimap.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/descrip/descriptor/multiset.hpp   (contents, props changed)
   sandbox/SOC/2008/graphs/branches/descrip/structures/
   sandbox/SOC/2008/graphs/branches/descrip/structures/sorted_sequence.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/graphs/branches/descrip/container.hpp            |    69 ++++++++++----------------------------- 
   sandbox/SOC/2008/graphs/branches/descrip/container/functions.hpp  |    15 ++++++++                                
   sandbox/SOC/2008/graphs/branches/descrip/descriptor.hpp           |    16 ++++++++                                
   sandbox/SOC/2008/graphs/branches/descrip/descriptor/functions.hpp |     1                                         
   sandbox/SOC/2008/graphs/branches/descrip/descriptor/index.hpp     |     9 +++++                                   
   sandbox/SOC/2008/graphs/branches/descrip/descriptor/list.hpp      |    20 +----------                             
   sandbox/SOC/2008/graphs/branches/descrip/descriptor/node.hpp      |    27 +++++++++++----                         
   sandbox/SOC/2008/graphs/branches/descrip/descriptor/set.hpp       |    21 +-----------                            
   sandbox/SOC/2008/graphs/branches/descrip/descriptor/vector.hpp    |    20 +---------                              
   9 files changed, 84 insertions(+), 114 deletions(-)

Added: sandbox/SOC/2008/graphs/branches/descrip/blob.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/blob.cpp	2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,22 @@
+
+#include <iostream>
+
+#include "blob.hpp"
+
+using namespace std;
+
+int
+main()
+{
+    blob<sizeof(int)> x, y;
+    x.put(1);
+    y.put(2);
+
+    cout << "x < y == " << (x < y) << endl;
+    cout << "x > y == " << (x > y) << endl;
+    cout << "x <= y == " << (x <= y) << endl;
+    cout << "x >= y == " << (x >= y) << endl;
+
+    return 0;
+}
+

Modified: sandbox/SOC/2008/graphs/branches/descrip/container.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/container.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/descrip/container.hpp	2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -1,4 +1,5 @@
-//  (C) Copyright Jeremy Siek 2004 
+//  (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)
@@ -6,6 +7,19 @@
 #ifndef CONTAINER_HPP
 #define CONTAINER_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.
 
@@ -62,51 +76,17 @@
 #include "container/vector.hpp"
 #include "container/list.hpp"
 #include "container/set.hpp"
+#include "container/map.hpp"
+#include "container/multiset.hpp"
+#include "container/multimap.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>&)
@@ -117,19 +97,6 @@
   { 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>&)

Modified: sandbox/SOC/2008/graphs/branches/descrip/container/functions.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/container/functions.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/descrip/container/functions.hpp	2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -17,4 +17,19 @@
         >::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;
+};
+
 #endif

Added: sandbox/SOC/2008/graphs/branches/descrip/container/map.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/container/map.hpp	2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,18 @@
+
+#ifndef CONTAINER_MAP_HPP
+#define CONTAINER_MAP_HPP
+
+struct map_tag :
+    virtual public sorted_associative_container_tag,
+    virtual public pair_associative_container_tag,
+    virtual public 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;
+};
+
+#endif

Added: sandbox/SOC/2008/graphs/branches/descrip/container/multimap.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/container/multimap.hpp	2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,18 @@
+
+#ifndef CONTAINER_MULTIMAP_HPP
+#define CONTAINER_MULTIMAP_HPP
+
+struct multimap_tag :
+    virtual public sorted_associative_container_tag,
+    virtual public pair_associative_container_tag,
+    virtual public 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;
+};
+
+#endif

Added: sandbox/SOC/2008/graphs/branches/descrip/container/multiset.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/container/multiset.hpp	2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,18 @@
+
+#ifndef CONTAINER_MULTISET_HPP
+#define CONTAINER_MULTISET_HPP
+
+struct multiset_tag :
+    virtual public sorted_associative_container_tag,
+    virtual public simple_associative_container_tag,
+    virtual public 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;
+};
+
+#endif

Added: sandbox/SOC/2008/graphs/branches/descrip/des.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/des.cpp	2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,81 @@
+
+#include <iostream>
+#include <vector>
+#include <list>
+#include <set>
+#include <map>
+
+#include "descriptor.hpp"
+#include "demangle.hpp"
+
+using namespace std;
+
+namespace dispatch
+{
+    template <typename Container, typename Value>
+    void insert(Container& c, Value const& x, back_insertion_sequence_tag)
+    { c.push_back(x); }
+
+    template <typename Container, typename Value>
+    void insert(Container& c, Value const& x, simple_associative_container_tag)
+    { c.insert(x); }
+
+    template <typename Container, typename Value>
+    void insert(Container& c, Value const& x, pair_associative_container_tag)
+    { c.insert(make_pair(x, x)); }
+}
+
+// A little tag dispatch for the soul. So pretty.
+template <typename Container, typename Value>
+void insert(Container& c, Value const& x)
+{ dispatch::insert(c, x, container_category(c)); }
+
+template <typename T, typename U>
+ostream& operator<<(ostream& os, pair<T, U> const& x)
+{ return os << "(" << x.first << "," << x.second << ")"; }
+
+template <typename Container>
+void test()
+{
+    typedef typename container_traits<Container>::category Category;
+    typedef typename container_traits<Container>::iterator_stability IteratorStability;
+    typedef typename extended_container_traits<Container>::descriptor_type Descriptor;
+    typedef typename extended_container_traits<Container>::descriptor_stability DescriptorStability;
+
+    cout << "--- " << demangle<Container>() << " ---" << endl;
+    cout << "category: " << demangle<Category>() << endl;
+    cout << "iterator stability: " << demangle<IteratorStability>() << endl;
+    cout << "descriptor stabiltiy: " << demangle<DescriptorStability>() << endl;
+
+    cout << "allows insert: " << has_insert_mutator<Container>::value << endl;
+    cout << "allows remove: " << has_remove_mutator<Container>::value << endl;
+    cout << "unique elements: " << contains_unique_elements<Container>::value << endl;
+    cout << "mapped elements: " << contains_mapped_elements<Container>::value << endl;
+
+    Container c;
+    insert(c, 0.0);
+    insert(c, 6.28);
+    insert(c, 3.14);
+
+    Descriptor d1 = make_descriptor(c, c.begin());
+    Descriptor d2 = make_descriptor(c, next(c.begin(), 1));
+    Descriptor d3 = make_descriptor(c, next(c.begin(), 2));
+
+    cout << *make_iterator(c, d1) << endl;
+    cout << *make_iterator(c, d2) << endl;
+    cout << *make_iterator(c, d3) << endl;
+}
+
+int
+main()
+{
+    test<vector<double>>();
+    test<list<double>>();
+    test<set<double>>();
+    test<map<double, double>>();
+    test<multiset<double>>();
+    test<multimap<double, double>>();
+
+    return 0;
+}
+

Modified: sandbox/SOC/2008/graphs/branches/descrip/descriptor.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/descriptor.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor.hpp	2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -12,7 +12,6 @@
 #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
@@ -82,16 +81,31 @@
     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-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -19,7 +19,6 @@
         >::value;
 };
 
-
 /**
  * Returns true if the container supports remove operations that do not
  * invalidate outstanding descriptors.

Modified: sandbox/SOC/2008/graphs/branches/descrip/descriptor/index.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/descriptor/index.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/index.hpp	2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -21,6 +21,11 @@
         : value(d)
     { }
 
+    template <typename Container>
+    inline index_descriptor(Container& c, typename Container::iterator i)
+        : value(std::distance(c.begin(), i))
+    { }
+
     inline bool is_null() const
     { return value == descriptor_type(-1); }
 
@@ -48,6 +53,10 @@
     { return value >= x.value; }
     //@}
 
+    template <typename Container>
+    inline typename Container::iterator get(Container& c) const
+    { return std::next(c.begin(), value); }
+
     descriptor_type value;
 };
 

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-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -1,6 +1,6 @@
 
-#ifndef LIST_HPP
-#define LIST_HPP
+#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>>
@@ -10,22 +10,6 @@
     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.
  */

Added: sandbox/SOC/2008/graphs/branches/descrip/descriptor/map.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/map.hpp	2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,23 @@
+
+#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

Added: sandbox/SOC/2008/graphs/branches/descrip/descriptor/multimap.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/multimap.hpp	2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,23 @@
+
+#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

Added: sandbox/SOC/2008/graphs/branches/descrip/descriptor/multiset.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/multiset.hpp	2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,24 @@
+
+#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/node.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/branches/descrip/descriptor/node.hpp	(original)
+++ sandbox/SOC/2008/graphs/branches/descrip/descriptor/node.hpp	2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -12,14 +12,19 @@
 {
     typedef Blob descriptor_type;
 
-    node_descriptor()
+    inline node_descriptor()
         : value()
     { }
 
-    node_descriptor(descriptor_type const& x)
+    inline node_descriptor(descriptor_type const& x)
         : value(x)
     { }
 
+    template <typename Container>
+    inline node_descriptor(Container&, typename Container::iterator i)
+        : value(i)
+    { }
+
     inline bool is_null()
     { return value == descriptor_type(); }
 
@@ -36,14 +41,22 @@
     //@{
     inline bool operator<(node_descriptor const& x)
     { return value < x.value; }
+
+    inline bool operator>(node_descriptor const& x)
+    { return value > x.value; }
+
+    inline bool operator<=(node_descriptor const& x)
+    { return value <= x.value; }
+
+    inline bool operator>=(node_descriptor const& x)
+    { return value >= x.value; }
     //@}
 
+    template <typename Container>
+    inline typename Container::iterator get(Container& c) const
+    { return value.get<typename Container::iterator>(); }
+
     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

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-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -1,6 +1,6 @@
 
-#ifndef SET_HPP
-#define SET_HPP
+#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>>
@@ -10,22 +10,6 @@
     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.
  */
@@ -37,5 +21,4 @@
 };
 
 
-
 #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-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -1,6 +1,6 @@
 
-#ifndef VECTOR_HPP
-#define VECTOR_HPP
+#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>>
@@ -10,21 +10,6 @@
     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.
  */
@@ -35,4 +20,5 @@
     typedef unstable_remove_tag descriptor_stability;
 };
 
+
 #endif

Added: sandbox/SOC/2008/graphs/branches/descrip/structures/sorted_sequence.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/branches/descrip/structures/sorted_sequence.hpp	2008-07-04 11:05:54 EDT (Fri, 04 Jul 2008)
@@ -0,0 +1,129 @@
+
+#ifndef SORTED_SEQUENCE_HPP
+#define SORTED_SEQUENCE_HPP
+
+/**
+* A sorted sequence implements an ordering on elements inserted into the
+* sequence.
+*/
+template <
+    class Type,
+    class Sequence = std::deque<Type>,
+    class Compare = std::less<typename Sequence::value_type>
+>
+class insertion_queue
+{
+    typedef Sequence sequence_type;
+public:
+
+    // value, pointer and reference types
+    typedef typename sequence_type::value_type value_type;
+    typedef typename sequence_type::pointer				pointer;
+    typedef typename sequence_type::reference			reference;
+    typedef typename sequence_type::const_reference		const_reference;
+
+    // size type
+    typedef typename sequence_type::size_type			size_type;
+    typedef Compare										key_compare;
+
+    insertion_queue()
+        : m_comp()
+        , m_data()
+    {}
+
+    insertion_queue(key_compare const& comp)
+        : m_comp(comp)
+        , m_data()
+    {}
+
+    insertion_queue(insertion_queue const& q)
+        : m_comp()
+        , m_data(q)
+    {}
+
+    size_type size() const
+    { return m_data.size(); }
+
+    bool empty() const
+    { return m_data.empty(); }
+
+    sequence_type const& sequence() const
+    { return m_data; }
+
+    /**
+    * The front() method returns the first element in the
+    * insertion queue. Runs in Theta(1).
+    */
+    const_reference front() const
+    { return m_data.front(); }
+
+    /**
+    * The enqueue() method inserts the element into the
+    * correct position of the queue. The queue is sorted
+    * in descending order (highest first). Therefore, the
+    * highest element will always be returned first.
+    */
+    void enqueue(const_reference value)
+    {
+        for(typename sequence_type::iterator i = m_data.begin(); i != m_data.end(); ++i) {
+            const_reference elem = *i;
+            if(!m_comp(value, elem)) {
+                m_data.insert(i, value);
+                return;
+            }
+        }
+
+        // if we've made it this far, we actually just
+        // have to push the value.
+        m_data.push_back(value);
+    }
+
+    /**
+    * The dequeue() method removes the first element in the
+    * insertion_queue. Runs in Theta(1).
+    */
+    void dequeue()
+    { m_data.pop_front(); }
+
+private:
+    key_compare m_comp;
+    sequence_type m_data;
+};
+
+/**
+* The insertion sort algorithm uses a priority queue (specifically
+* an insertion queue in this case) to sort data. It runs in O(n^2)
+* time. There are two major phases to the algorithm. The first is
+* the construction of the priority queue and the second is the
+* removal and re-insertion to sort the list.
+*/
+template <class RandomAccessIterator>
+void insertion_sort(RandomAccessIterator first, RandomAccessIterator last)
+{
+    typedef RandomAccessIterator iterator;
+    typedef typename iterator::value_type value_type;
+
+    // use a selection queue to implement a selection sort
+    insertion_queue<value_type> iq;
+
+    // construct the queue by inserting all the elements\
+    // into the queue
+    for(iterator i = first; i != last; ++i) {
+        iq.enqueue(*i);
+    }
+
+    // dequeue all the elements to get the sorted sequence
+    // elements are re-assigned into the iterator's positions
+    iterator i = first;
+    while(!iq.empty()) {
+        // get the highest element
+        value_type elem = iq.front();
+        iq.dequeue();
+
+        // put it back into the original sequence
+        *i = elem;
+        ++i;
+    }
+}
+
+#endif