// 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 |