|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r49774 - in sandbox/SOC/2008/graphs/trunk: boost boost/graphs/adjacency_list libs/graphs/test
From: asutton_at_[hidden]
Date: 2008-11-15 14:10:41
Author: asutton
Date: 2008-11-15 14:10:40 EST (Sat, 15 Nov 2008)
New Revision: 49774
URL: http://svn.boost.org/trac/boost/changeset/49774
Log:
Revisiting the adjacency list implementation, trying to get rid
of numerous classes, and makingt the interfaces free functions.
Added:
sandbox/SOC/2008/graphs/trunk/boost/counted_list.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_store_traits.hpp (contents, props changed)
sandbox/SOC/2008/graphs/trunk/libs/graphs/test/opt.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_list.hpp | 16 +++++++++++++++-
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_vector.hpp | 15 +++++++++++++++
2 files changed, 30 insertions(+), 1 deletions(-)
Added: sandbox/SOC/2008/graphs/trunk/boost/counted_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/counted_list.hpp 2008-11-15 14:10:40 EST (Sat, 15 Nov 2008)
@@ -0,0 +1,139 @@
+
+#ifndef BOOST_COUNTED_LIST_HPP
+#define BOOST_COUNTED_LIST_HPP
+
+#include <list>
+#include <algorithm>
+
+namespace boost {
+
+/**
+ * The counted_list is a very simple wrapper around a std::list that maintains
+ * the size of the list. We can do this because graph operations don't require
+ * any notion of spliceability.
+ *
+ * The interface to this class is given by functions.
+ */
+template <typename T, typename Alloc, typename List = std::list<T, Alloc>>
+class counted_list
+{
+ typedef List base_type;
+public:
+ typedef typename base_type::value_type value_type;
+ typedef typename base-type::pointer pointer;
+ typedef typename base_type::reference reference;
+ typedef typename base-type::const_reference const_reference;
+ typedef typename base_type::iterator iterator;
+ typedef typename base_type::const_iterator const_iterator;
+ typedef typename base_type::reverse_iterator reverse_iterator;
+ typedef typename base_type::const_reverse_iterator const_reverse_iterator;
+ typedef typename base_type::size_type size_type;
+
+ counted_list()
+ : _list(), _size(0)
+ { }
+
+ counted_list(counted_list const& x)
+ : _list(x._list), _size(x._size)
+ { }
+
+ counted_list(counted_list&& x)
+ : _list(x._list), _size(x._size)
+ { }
+
+ counted_list(size_type n)
+ : _list(n), _size(n)
+ { }
+
+ counted_list(size_type n, T const& x)
+ : _list(n, x), _size(n)
+ { }
+
+ template <typename Iter>
+ counted_list(Iter f, Iter l)
+ : _list(f, l), _size(std::distance(f, l))
+ { }
+
+ iterator begin() { return _list.begin(); }
+ iterator end() { return _list.end(); }
+ const_iterator begin() const { return _list.begin(); }
+ const_iterator end() const { return _list.end(); }
+
+ reverse_iterator rbegin() { return _list.rbegin(); }
+ reverse_iterator rend() { return _list.rend(); }
+ const_reverse_iterator rbegin() const { return _list.rbegin(); }
+ const_reverse_iterator rend() const { return _list.rend(); }
+
+ size_type size() const { return _size; }
+ size_type max_size() const { return _list.max_size() }
+
+ bool empty() const { return _list.empty(); }
+
+ reference front() { return _list.front(); }
+ const_reference front() const { return _list.front(); }
+
+ reference back() { return _list.back(); }
+ const_reference back() const { return _list.back(); }
+
+ void push_front(T const& x) { _list.push_front(x); ++_size; }
+ void pop_front() { _list.pop_front(); --_size; }
+
+ void push_back(T const& x) { _list.push_back(x); ++_size; }
+ void pop_back() { _list.pop_back(); --_size; }
+
+ iterator insert(iterator i, T const& x)
+ {
+ iterator ret = _list.insert(i, x);
+ ++_size;
+ return ret;
+ }
+
+ template <typename Iter>
+ iterator insert(iterator pos, Iter f, Iter l)
+ {
+ _list.insert(pos, f, l);
+ _size += std::distance(f, l);
+ }
+
+ iterator erase(iterator pos)
+ {
+ iterator ret = _list.erase(pos);
+ --_size;
+ return ret;
+ }
+
+ iterator erase(iterator f, iterator l)
+ {
+ _size -= std::distance(f, l);
+ return _list.erase(f, l);
+ }
+
+ void resize(size_type n, T const& x = T())
+ { _list.resize(n, t); _size = n; }
+
+ void clear()
+ { _list.clear(); _size = 0; }
+
+ counted_list& swap(counted_list&& x)
+ { _list.swap(x); return* this; }
+
+ counted_list& operator=(counted_list const& x)
+ { return swap(counted_list(x)); }
+
+ counted_list& operator=(counted_list&& x)
+ { return swap(x); }
+
+ bool operator==(counted_list const& x) const
+ { return _list == x._list; }
+
+ bool operator<(counted_list const& x) const
+ { return _list < x._list; }
+
+private:
+ base_type _list;
+ size_type _size;
+};
+
+} /* namespace boost */
+
+#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_list.hpp 2008-11-15 14:10:40 EST (Sat, 15 Nov 2008)
@@ -31,6 +31,21 @@
};
};
+
+template <typename T, typename A>
+struct vertex_store_traits<counted_list<T,A>>
+{
+private:
+ typedef std::counted_list<T,A> base_type;
+public:
+ typedef typename base_type::iterator store_iterator;
+
+ typedef typename base_type::size_type vertices_size_type;
+ typedef typename descriptor_traits<base_type>::descriptor_type vertex_descriptor;
+ typedef basic_vertex_iterator<base_type> vertex_iterator;
+ typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
+};
+
/**
* The implementation of the vertex list.
*
@@ -44,7 +59,6 @@
typedef std::list<Vertex, Alloc> store_type;
typedef typename store_type::size_type size_type;
typedef typename store_type::iterator iterator;
- typedef typename store_type::const_iterator const_iterator;
typedef Vertex vertex_type;
typedef typename Vertex::vertex_label vertex_label;
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_store_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_store_traits.hpp 2008-11-15 14:10:40 EST (Sat, 15 Nov 2008)
@@ -0,0 +1,16 @@
+
+#ifndef BOOST_GRAPH_ADJLIST_VERTEX_STORE_TRAITS_HPP
+#define BOOST_GRAPH_ADJLIST_VERTEX_STORE_TRAITS_HPP
+
+namespace boost { namespace graphs { namespace adjacency_list {
+
+/**
+ * The vertex store traits defines the basic types associate with a vertex set.
+ */
+template <typename VertexStore>
+struct vertex_store_traits
+{ };
+
+} } } /* namespace boost::graphs::adjacency_list */
+
+#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_vector.hpp 2008-11-15 14:10:40 EST (Sat, 15 Nov 2008)
@@ -8,6 +8,7 @@
#include <boost/none.hpp>
#include <boost/descriptors.hpp>
#include <boost/graphs/utility.hpp>
+#include <boost/graphs/adjacency_list/vertex_store_traits.hpp>
#include <boost/graphs/adjacency_list/vertex_iterator.hpp>
namespace boost { namespace graphs { namespace adjacency_list {
@@ -44,6 +45,20 @@
};
};
+template <typename T, typename A>
+struct vertex_store_traits<std::vector<T,A>>
+{
+private:
+ typedef std::vector<T,A> base_type;
+public:
+ typedef typename base_type::iterator store_iterator;
+
+ typedef typename base_type::size_type vertices_size_type;
+ typedef typename descriptor_traits<base_type>::descriptor_type vertex_descriptor;
+ typedef basic_vertex_iterator<base_type> vertex_iterator;
+ typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
+};
+
/**
* The vertex_vector template implements veretex storage for adjacency lists
* as a vector. This essentially provides a heavily constrained interface
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/opt.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/opt.cpp 2008-11-15 14:10:40 EST (Sat, 15 Nov 2008)
@@ -0,0 +1,48 @@
+
+#include <iostream>
+
+#include <boost/assert.hpp>
+#include <boost/optional.hpp>
+#include <boost/optional_value.hpp>
+
+#include "typestr.hpp"
+
+using namespace std;
+using namespace boost;
+
+void test_opt()
+{
+ optional<int> x, y = 5;
+ BOOST_ASSERT(!x.valid());
+ BOOST_ASSERT(y.valid());
+ x = y;
+ BOOST_ASSERT(*x == 5);
+ BOOST_ASSERT(*y == 5);
+
+ int i = 20;
+ optional<int*> p, q = &i;
+ BOOST_ASSERT(!p.valid());
+ BOOST_ASSERT(q.valid() && *q == 20);
+}
+
+void test_opt_val()
+{
+ optional_value<unsigned> x, y = 5;
+ BOOST_ASSERT(!x.valid());
+ BOOST_ASSERT(y.valid());
+ x = y;
+ BOOST_ASSERT(x && *x == 5);
+
+ cout << typestr(optional_value<int*>::absent()) << " -> " << optional_value<int*>::absent() << endl;
+ cout << typestr(optional_value<int>::absent()) << " -> " << optional_value<int>::absent() << endl;
+ cout << typestr(optional_value<unsigned>::absent()) << " -> " << optional_value<unsigned>::absent() << endl;
+ cout << typestr(optional_value<double>::absent()) << " -> " << optional_value<double>::absent() << endl;
+ cout << typestr(optional_value<double, absent_neg_inf<double>>::absent())
+ << " -> " << optional_value<double, absent_neg_inf<double>>::absent() << endl;
+}
+
+int main()
+{
+ test_opt();
+ test_opt_val();
+}
\ No newline at end of file
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