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