123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158 |
- // 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 <boost/assert.hpp>
- #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)
- { BOOST_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
|