Chris@16: // Copyright 2004, 2005 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (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: Nick Edmonds
Chris@16: //           Andrew Lumsdaine
Chris@16: #ifndef BOOST_GRAPH_MESH_GENERATOR_HPP
Chris@16: #define BOOST_GRAPH_MESH_GENERATOR_HPP
Chris@16: 
Chris@16: #include <iterator>
Chris@16: #include <utility>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/type_traits/is_base_and_derived.hpp>
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   template<typename Graph>
Chris@16:   class mesh_iterator
Chris@16:   {
Chris@16:     typedef typename graph_traits<Graph>::directed_category directed_category;
Chris@16:     typedef typename graph_traits<Graph>::vertices_size_type 
Chris@16:       vertices_size_type;
Chris@16: 
Chris@16:     BOOST_STATIC_CONSTANT
Chris@16:       (bool,
Chris@16:        is_undirected = (is_base_and_derived<undirected_tag,
Chris@16:                                             directed_category>::value
Chris@16:                         || is_same<undirected_tag, directed_category>::value));
Chris@16: 
Chris@16:   public:
Chris@16:     typedef std::input_iterator_tag iterator_category;
Chris@16:     typedef std::pair<vertices_size_type, vertices_size_type> value_type;
Chris@16:     typedef const value_type& reference;
Chris@16:     typedef const value_type* pointer;
Chris@16:     typedef void difference_type;
Chris@16: 
Chris@16:     mesh_iterator()
Chris@16:       : x(0), y(0), done(true) { }
Chris@16: 
Chris@16:     // Vertices are numbered in row-major order
Chris@16:     // Assumes directed
Chris@16:     mesh_iterator(vertices_size_type x, vertices_size_type y, 
Chris@16:                   bool toroidal = true)
Chris@16:       : x(x), y(y), n(x*y), source(0), target(1), current(0,1), 
Chris@16:         toroidal(toroidal), done(false)
Chris@16:     { BOOST_ASSERT(x > 1 && y > 1); }
Chris@16: 
Chris@16:     reference operator*() const { return current; }
Chris@16:     pointer operator->() const { return &current; }
Chris@16:     
Chris@16:     mesh_iterator& operator++()
Chris@16:     {
Chris@16:       if (is_undirected) {
Chris@16:         if (!toroidal) {
Chris@16:           if (target == source + 1)
Chris@16:             if (source < x * (y - 1))
Chris@16:               target = source + x;
Chris@16:             else {
Chris@16:               source++;
Chris@16:               target = (source % x) < x - 1 ? source + 1 : source + x;
Chris@16:               if (target > n) 
Chris@16:                 done = true;
Chris@16:             }
Chris@16:           else if (target == source + x) {
Chris@16:             source++;
Chris@16:             target = (source % x) < x - 1 ? source + 1 : source + x;
Chris@16:           }
Chris@16:         } else {
Chris@16:           if (target == source + 1 || target == source - (source % x))
Chris@16:             target = (source + x) % n;
Chris@16:           else if (target == (source + x) % n) {
Chris@16:             if (source == n - 1)
Chris@16:               done = true;
Chris@16:             else {
Chris@16:               source++;
Chris@16:               target = (source % x) < (x - 1) ? source + 1 : source - (source % x);
Chris@16:             }
Chris@16:           }
Chris@16:         }
Chris@16:       } else { // Directed
Chris@16:         if ( !toroidal ) {
Chris@16:           if (target == source - x) 
Chris@16:             target = source % x > 0 ? source - 1 : source + 1;
Chris@16:           else if (target == source - 1)
Chris@16:             if ((source % x) < (x - 1))
Chris@16:               target = source + 1;
Chris@16:             else if (source < x * (y - 1))
Chris@16:               target = source + x;
Chris@16:             else {
Chris@16:               done = true;
Chris@16:             }
Chris@16:           else if (target == source + 1)
Chris@16:             if (source < x * (y - 1))
Chris@16:               target = source + x;
Chris@16:             else {
Chris@16:               source++;
Chris@16:               target = source - x;
Chris@16:             }
Chris@16:           else if (target == source + x) {
Chris@16:             source++;
Chris@16:             target = (source >= x) ? source - x : source - 1;
Chris@16:           }
Chris@16:         } else {
Chris@16:           if (source == n - 1 && target == (source + x) % n)
Chris@16:             done = true;
Chris@16:           else if (target == source - 1 || target == source + x - 1)
Chris@16:             target = (source + x) % n;
Chris@16:           else if (target == source + 1 || target == source - (source % x))
Chris@16:             target = (source - x + n) % n;
Chris@16:           else if (target == (source - x + n) % n)
Chris@16:             target = (source % x > 0) ? source - 1 : source + x - 1;
Chris@16:           else if (target == (source + x) % n) {
Chris@16:             source++;
Chris@16:             target = (source % x) < (x - 1) ? source + 1 : source - (source % x);
Chris@16:           }
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       current.first = source;
Chris@16:       current.second = target;
Chris@16: 
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     mesh_iterator operator++(int)
Chris@16:     {
Chris@16:       mesh_iterator temp(*this);
Chris@16:       ++(*this);
Chris@16:       return temp;
Chris@16:     }
Chris@16: 
Chris@16:     bool operator==(const mesh_iterator& other) const
Chris@16:     {
Chris@16:       return done == other.done;
Chris@16:     }
Chris@16: 
Chris@16:     bool operator!=(const mesh_iterator& other) const
Chris@16:     { return !(*this == other); }
Chris@16: 
Chris@16:   private: 
Chris@16: 
Chris@16:     vertices_size_type x,y;
Chris@16:     vertices_size_type n;
Chris@16:     vertices_size_type source;
Chris@16:     vertices_size_type target;
Chris@16:     value_type current;
Chris@16:     bool toroidal;
Chris@16:     bool done;
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16: } // end namespace boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_MESH_GENERATOR_HPP