williamr@2: // Copyright 2005 The Trustees of Indiana University.
williamr@2: 
williamr@2: // Distributed under the Boost Software License, Version 1.0.
williamr@2: // (See accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: 
williamr@2: //  Authors: Jeremiah Willcock
williamr@2: //           Douglas Gregor
williamr@2: //           Andrew Lumsdaine
williamr@2: 
williamr@2: // Indexed properties -- used for CSR and CSR-like graphs
williamr@2: 
williamr@2: #ifndef BOOST_GRAPH_INDEXED_PROPERTIES_HPP
williamr@2: #define BOOST_GRAPH_INDEXED_PROPERTIES_HPP
williamr@2: 
williamr@2: #include <vector>
williamr@2: #include <utility>
williamr@2: #include <algorithm>
williamr@2: #include <climits>
williamr@2: #include <iterator>
williamr@2: #include <boost/graph/graph_traits.hpp>
williamr@2: #include <boost/graph/properties.hpp>
williamr@2: #include <boost/iterator/counting_iterator.hpp>
williamr@2: #include <boost/integer.hpp>
williamr@2: #include <boost/iterator/iterator_facade.hpp>
williamr@2: #include <boost/mpl/if.hpp>
williamr@2: 
williamr@2: namespace boost {
williamr@2: namespace detail {
williamr@2: 
williamr@2: template<typename Derived, typename Property, typename Descriptor>
williamr@2: class indexed_vertex_properties
williamr@2: {
williamr@2: public:
williamr@2:   typedef no_property vertex_property_type;
williamr@2:   typedef Property vertex_bundled;
williamr@2: 
williamr@2:   // Directly access a vertex or edge bundle
williamr@2:   Property& operator[](Descriptor v)
williamr@2:   { return m_vertex_properties[get(vertex_index, derived(), v)]; }
williamr@2: 
williamr@2:   const Property& operator[](Descriptor v) const
williamr@2:   { return m_vertex_properties[get(vertex_index, derived(), v)]; }
williamr@2: 
williamr@2: protected:
williamr@2:   // Default-construct with no property values
williamr@2:   indexed_vertex_properties() {}
williamr@2: 
williamr@2:   // Initialize with n default-constructed property values
williamr@2:   indexed_vertex_properties(std::size_t n) : m_vertex_properties(n) { }
williamr@2: 
williamr@2:   // Resize the properties vector
williamr@2:   void resize(std::size_t n)
williamr@2:   {
williamr@2:     m_vertex_properties.resize(n);
williamr@2:   }
williamr@2: 
williamr@2:   // Reserve space in the vector of properties
williamr@2:   void reserve(std::size_t n)
williamr@2:   {
williamr@2:     m_vertex_properties.reserve(n);
williamr@2:   }
williamr@2: 
williamr@2:   // Add a new property value to the back
williamr@2:   void push_back(const Property& prop)
williamr@2:   {
williamr@2:     m_vertex_properties.push_back(prop);
williamr@2:   }
williamr@2: 
williamr@2:   // Access to the derived object
williamr@2:   Derived& derived() { return *static_cast<Derived*>(this); }
williamr@2: 
williamr@2:   const Derived& derived() const
williamr@2:   { return *static_cast<const Derived*>(this); }
williamr@2: 
williamr@2: public: // should be private, but friend templates not portable
williamr@2:   std::vector<Property> m_vertex_properties;
williamr@2: };
williamr@2: 
williamr@2: template<typename Derived, typename Descriptor>
williamr@2: class indexed_vertex_properties<Derived, void, Descriptor>
williamr@2: {
williamr@2:   struct secret {};
williamr@2: 
williamr@2:  public:
williamr@2:   typedef no_property vertex_property_type;
williamr@2:   typedef void vertex_bundled;
williamr@2: 
williamr@2:   secret operator[](secret) { return secret(); }
williamr@2: 
williamr@2:  protected:
williamr@2:   // All operations do nothing.
williamr@2:   indexed_vertex_properties() { }
williamr@2:   indexed_vertex_properties(std::size_t) { }
williamr@2:   void resize(std::size_t) { }
williamr@2:   void reserve(std::size_t) { }
williamr@2: };
williamr@2: 
williamr@2: template<typename Derived, typename Property, typename Descriptor>
williamr@2: class indexed_edge_properties
williamr@2: {
williamr@2: public:
williamr@2:   typedef no_property edge_property_type;
williamr@2:   typedef Property edge_bundled;
williamr@2:   typedef Property edge_push_back_type;
williamr@2: 
williamr@2:   // Directly access a edge or edge bundle
williamr@2:   Property& operator[](Descriptor v)
williamr@2:   { return m_edge_properties[get(edge_index, derived(), v)]; }
williamr@2: 
williamr@2:   const Property& operator[](Descriptor v) const
williamr@2:   { return m_edge_properties[get(edge_index, derived(), v)]; }
williamr@2: 
williamr@2: protected:
williamr@2:   // Default-construct with no property values
williamr@2:   indexed_edge_properties() {}
williamr@2: 
williamr@2:   // Initialize with n default-constructed property values
williamr@2:   indexed_edge_properties(std::size_t n) : m_edge_properties(n) { }
williamr@2: 
williamr@2:   // Resize the properties vector
williamr@2:   void resize(std::size_t n)
williamr@2:   {
williamr@2:     m_edge_properties.resize(n);
williamr@2:   }
williamr@2: 
williamr@2:   // Reserve space in the vector of properties
williamr@2:   void reserve(std::size_t n)
williamr@2:   {
williamr@2:     m_edge_properties.reserve(n);
williamr@2:   }
williamr@2: 
williamr@2:  public:
williamr@2:   // Add a new property value to the back
williamr@2:   void push_back(const Property& prop)
williamr@2:   {
williamr@2:     m_edge_properties.push_back(prop);
williamr@2:   }
williamr@2: 
williamr@2:  private:
williamr@2:   // Access to the derived object
williamr@2:   Derived& derived() { return *static_cast<Derived*>(this); }
williamr@2: 
williamr@2:   const Derived& derived() const
williamr@2:   { return *static_cast<const Derived*>(this); }
williamr@2: 
williamr@2: public: // should be private, but friend templates not portable
williamr@2:   std::vector<Property> m_edge_properties;
williamr@2: };
williamr@2: 
williamr@2: template<typename Derived, typename Descriptor>
williamr@2: class indexed_edge_properties<Derived, void, Descriptor>
williamr@2: {
williamr@2:   struct secret {};
williamr@2: 
williamr@2:  public:
williamr@2:   typedef no_property edge_property_type;
williamr@2:   typedef void edge_bundled;
williamr@2:   typedef void* edge_push_back_type;
williamr@2: 
williamr@2:   secret operator[](secret) { return secret(); }
williamr@2: 
williamr@2:  protected:
williamr@2:   // All operations do nothing.
williamr@2:   indexed_edge_properties() { }
williamr@2:   indexed_edge_properties(std::size_t) { }
williamr@2:   void resize(std::size_t) { }
williamr@2:   void reserve(std::size_t) { }
williamr@2: 
williamr@2:  public:
williamr@2:   void push_back(const edge_push_back_type&) { }
williamr@2: };
williamr@2: 
williamr@2: }
williamr@2: }
williamr@2: 
williamr@2: #endif // BOOST_GRAPH_INDEXED_PROPERTIES_HPP