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