Chris@16: // Copyright 2005 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Distributed under the Boost Software License, Version 1.0.
Chris@16: // (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: //  Authors: Jeremiah Willcock
Chris@16: //           Douglas Gregor
Chris@16: //           Andrew Lumsdaine
Chris@16: 
Chris@16: // Indexed properties -- used for CSR and CSR-like graphs
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_INDEXED_PROPERTIES_HPP
Chris@16: #define BOOST_GRAPH_INDEXED_PROPERTIES_HPP
Chris@16: 
Chris@16: #include <vector>
Chris@16: #include <utility>
Chris@16: #include <algorithm>
Chris@16: #include <climits>
Chris@16: #include <iterator>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/properties.hpp>
Chris@16: #include <boost/iterator/counting_iterator.hpp>
Chris@16: #include <boost/integer.hpp>
Chris@16: #include <boost/iterator/iterator_facade.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace detail {
Chris@16: 
Chris@16: template<typename Derived, typename Property, typename Descriptor, typename IndexMap>
Chris@16: class indexed_vertex_properties
Chris@16: {
Chris@16: public:
Chris@16:   typedef no_property vertex_property_type;
Chris@16:   typedef Property vertex_bundled;
Chris@16:   typedef iterator_property_map<
Chris@16:             typename std::vector<Property>::iterator,
Chris@16:             IndexMap> vertex_map_type;
Chris@16:   typedef iterator_property_map<
Chris@16:             typename std::vector<Property>::const_iterator,
Chris@16:             IndexMap> const_vertex_map_type;
Chris@16: 
Chris@16:   // Directly access a vertex or edge bundle
Chris@16:   Property& operator[](Descriptor v)
Chris@16:   { return m_vertex_properties[get(vertex_index, derived(), v)]; }
Chris@16: 
Chris@16:   const Property& operator[](Descriptor v) const
Chris@16:   { return m_vertex_properties[get(vertex_index, derived(), v)]; }
Chris@16: 
Chris@16:   vertex_map_type get_vertex_bundle(const IndexMap& index_map = IndexMap()) {
Chris@16:     return vertex_map_type(m_vertex_properties.begin(), index_map);
Chris@16:   }
Chris@16: 
Chris@16:   const_vertex_map_type get_vertex_bundle(const IndexMap& index_map = IndexMap()) const {
Chris@16:     return const_vertex_map_type(m_vertex_properties.begin(), index_map);
Chris@16:   }
Chris@16: 
Chris@16: protected:
Chris@16:   // Default-construct with no property values
Chris@16:   indexed_vertex_properties() {}
Chris@16: 
Chris@16:   // Initialize with n default-constructed property values
Chris@16:   indexed_vertex_properties(std::size_t n) : m_vertex_properties(n) { }
Chris@16: 
Chris@16: public:
Chris@16:   // Clear the properties vector
Chris@16:   void clear()
Chris@16:   {
Chris@16:     m_vertex_properties.clear();
Chris@16:   }
Chris@16: 
Chris@16:   // Resize the properties vector
Chris@16:   void resize(std::size_t n)
Chris@16:   {
Chris@16:     m_vertex_properties.resize(n);
Chris@16:   }
Chris@16: 
Chris@16:   // Reserve space in the vector of properties
Chris@16:   void reserve(std::size_t n)
Chris@16:   {
Chris@16:     m_vertex_properties.reserve(n);
Chris@16:   }
Chris@16: 
Chris@16:   // Add a new property value to the back
Chris@16:   void push_back(const Property& prop)
Chris@16:   {
Chris@16:     m_vertex_properties.push_back(prop);
Chris@16:   }
Chris@16: 
Chris@16:   // Write an element by raw index
Chris@16:   void write_by_index(std::size_t idx, const Property& prop)
Chris@16:   {
Chris@16:     m_vertex_properties[idx] = prop;
Chris@16:   }
Chris@16: 
Chris@16:   // Access to the derived object
Chris@16:   Derived& derived() { return *static_cast<Derived*>(this); }
Chris@16: 
Chris@16:   const Derived& derived() const
Chris@16:   { return *static_cast<const Derived*>(this); }
Chris@16: 
Chris@16: public: // should be private, but friend templates not portable
Chris@16:   std::vector<Property> m_vertex_properties;
Chris@16: };
Chris@16: 
Chris@16: template<typename Derived, typename Descriptor, typename IndexMap>
Chris@16: class indexed_vertex_properties<Derived, void, Descriptor, IndexMap>
Chris@16: {
Chris@16:   struct secret {};
Chris@16: 
Chris@16:  public:
Chris@16:   typedef no_property vertex_property_type;
Chris@16:   typedef void vertex_bundled;
Chris@16:   typedef secret vertex_map_type;
Chris@16:   typedef secret const_vertex_map_type;
Chris@16: 
Chris@16:   secret operator[](secret) { return secret(); }
Chris@16: 
Chris@16:   vertex_map_type get_vertex_bundle() const {
Chris@16:     return vertex_map_type();
Chris@16:   }
Chris@16: 
Chris@16:  protected:
Chris@16:   // All operations do nothing.
Chris@16:   indexed_vertex_properties() { }
Chris@16:   indexed_vertex_properties(std::size_t) { }
Chris@16: 
Chris@16: public:
Chris@16:   void clear() { }
Chris@16:   void resize(std::size_t) { }
Chris@16:   void reserve(std::size_t) { }
Chris@16: };
Chris@16: 
Chris@16: template<typename Derived, typename Property, typename Descriptor, typename IndexMap>
Chris@16: class indexed_edge_properties
Chris@16: {
Chris@16: public:
Chris@16:   typedef no_property edge_property_type;
Chris@16:   typedef Property edge_bundled;
Chris@16:   typedef Property edge_push_back_type;
Chris@16:   typedef iterator_property_map<
Chris@16:             typename std::vector<Property>::iterator,
Chris@16:             IndexMap> edge_map_type;
Chris@16:   typedef iterator_property_map<
Chris@16:             typename std::vector<Property>::const_iterator,
Chris@16:             IndexMap> const_edge_map_type;
Chris@16: 
Chris@16:   // Directly access a edge or edge bundle
Chris@16:   Property& operator[](Descriptor v)
Chris@16:   { return m_edge_properties[get(edge_index, derived(), v)]; }
Chris@16: 
Chris@16:   const Property& operator[](Descriptor v) const
Chris@16:   { return m_edge_properties[get(edge_index, derived(), v)]; }
Chris@16: 
Chris@16:   edge_map_type get_edge_bundle(const IndexMap& index_map = IndexMap()) {
Chris@16:     return edge_map_type(m_edge_properties.begin(), index_map);
Chris@16:   }
Chris@16: 
Chris@16:   const_edge_map_type get_edge_bundle(const IndexMap& index_map = IndexMap()) const {
Chris@16:     return const_edge_map_type(m_edge_properties.begin(), index_map);
Chris@16:   }
Chris@16: 
Chris@16: protected:
Chris@16:   // Default-construct with no property values
Chris@16:   indexed_edge_properties() {}
Chris@16: 
Chris@16:   // Initialize with n default-constructed property values
Chris@16:   indexed_edge_properties(std::size_t n) : m_edge_properties(n) { }
Chris@16: 
Chris@16:   // Get the size of the properties vector
Chris@16:   std::size_t size() const
Chris@16:   {
Chris@16:     return m_edge_properties.size();
Chris@16:   }
Chris@16: 
Chris@16:   // Clear the properties vector
Chris@16:   void clear()
Chris@16:   {
Chris@16:     m_edge_properties.clear();
Chris@16:   }
Chris@16: 
Chris@16:   // Resize the properties vector
Chris@16:   void resize(std::size_t n)
Chris@16:   {
Chris@16:     m_edge_properties.resize(n);
Chris@16:   }
Chris@16: 
Chris@16:   // Reserve space in the vector of properties
Chris@16:   void reserve(std::size_t n)
Chris@16:   {
Chris@16:     m_edge_properties.reserve(n);
Chris@16:   }
Chris@16: 
Chris@16:   // Write an element by raw index
Chris@16:   void write_by_index(std::size_t idx, const Property& prop)
Chris@16:   {
Chris@16:     m_edge_properties[idx] = prop;
Chris@16:   }
Chris@16: 
Chris@16:  public:
Chris@16:   // Add a new property value to the back
Chris@16:   void push_back(const Property& prop)
Chris@16:   {
Chris@16:     m_edge_properties.push_back(prop);
Chris@16:   }
Chris@16: 
Chris@16:   // Move range of properties backwards
Chris@16:   void move_range(std::size_t src_begin, std::size_t src_end, std::size_t dest_begin) {
Chris@16:     std::copy_backward(
Chris@16:         m_edge_properties.begin() + src_begin,
Chris@16:         m_edge_properties.begin() + src_end,
Chris@16:         m_edge_properties.begin() + dest_begin + (src_end - src_begin));
Chris@16:   }
Chris@16: 
Chris@16:   typedef typename std::vector<Property>::iterator iterator;
Chris@16:   iterator begin() {return m_edge_properties.begin();}
Chris@16:   iterator end() {return m_edge_properties.end();}
Chris@16: 
Chris@16:  private:
Chris@16:   // Access to the derived object
Chris@16:   Derived& derived() { return *static_cast<Derived*>(this); }
Chris@16: 
Chris@16:   const Derived& derived() const
Chris@16:   { return *static_cast<const Derived*>(this); }
Chris@16: 
Chris@16: public: // should be private, but friend templates not portable
Chris@16:   std::vector<Property> m_edge_properties;
Chris@16: };
Chris@16: 
Chris@16: struct dummy_no_property_iterator
Chris@16: : public boost::iterator_facade<dummy_no_property_iterator, no_property, std::random_access_iterator_tag> {
Chris@16:   mutable no_property prop;
Chris@16:   no_property& dereference() const {return prop;}
Chris@16:   bool equal(const dummy_no_property_iterator&) const {return true;}
Chris@16:   void increment() {}
Chris@16:   void decrement() {}
Chris@16:   void advance(std::ptrdiff_t) {}
Chris@16:   std::ptrdiff_t distance_to(const dummy_no_property_iterator) const {return 0;}
Chris@16: };
Chris@16: 
Chris@16: template<typename Derived, typename Descriptor, typename IndexMap>
Chris@16: class indexed_edge_properties<Derived, void, Descriptor, IndexMap>
Chris@16: {
Chris@16:   struct secret {};
Chris@16: 
Chris@16:  public:
Chris@16:   typedef no_property edge_property_type;
Chris@16:   typedef void edge_bundled;
Chris@16:   typedef void* edge_push_back_type;
Chris@16:   typedef secret edge_map_type;
Chris@16:   typedef secret const_edge_map_type;
Chris@16: 
Chris@16:   secret operator[](secret) { return secret(); }
Chris@16:   void write_by_index(std::size_t /*idx*/, const no_property& /*prop*/) {}
Chris@16: 
Chris@16:   edge_map_type get_edge_bundle(const IndexMap& = IndexMap()) const {
Chris@16:     return edge_map_type();
Chris@16:   }
Chris@16: 
Chris@16:  protected:
Chris@16:   // All operations do nothing.
Chris@16:   indexed_edge_properties() { }
Chris@16:   indexed_edge_properties(std::size_t) { }
Chris@16:   std::size_t size() const {return 0;}
Chris@16:   void clear() { }
Chris@16:   void resize(std::size_t) { }
Chris@16:   void reserve(std::size_t) { }
Chris@16: 
Chris@16:  public:
Chris@16:   void push_back(const edge_push_back_type&) { }
Chris@16:   void move_range(std::size_t /*src_begin*/, std::size_t /*src_end*/, std::size_t /*dest_begin*/) {}
Chris@16: 
Chris@16:   typedef dummy_no_property_iterator iterator;
Chris@16:   iterator begin() {return dummy_no_property_iterator();}
Chris@16:   iterator end() {return dummy_no_property_iterator();}
Chris@16: 
Chris@16: };
Chris@16: 
Chris@16: }
Chris@16: }
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_INDEXED_PROPERTIES_HPP