← Back to branch summary

~ubuntu-branches/debian/sid/boost1.49/sid

« back to all changes in this revision

Viewing changes to boost/graph/mesh_graph_generator.hpp

  • Committer: Package Import Robot
  • Author(s): Steve M. Robbins
  • Date: 2012-02-26 00:31:44 UTC
  • Revision ID: package-import@ubuntu.com-20120226003144-eaytp12cbf6ubpms
Tags: upstream-1.49.0
Import upstream version 1.49.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
boost/graph/mesh_graph_generator.hpp
 
1
// Copyright 2004, 2005 The Trustees of Indiana University.
 
2
 
 
3
// Use, modification and distribution is subject to the Boost Software
 
4
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
 
5
// http://www.boost.org/LICENSE_1_0.txt)
 
6
 
 
7
//  Authors: Nick Edmonds
 
8
//           Andrew Lumsdaine
 
9
#ifndef BOOST_GRAPH_MESH_GENERATOR_HPP
 
10
#define BOOST_GRAPH_MESH_GENERATOR_HPP
 
11
 
 
12
#include <iterator>
 
13
#include <utility>
 
14
#include <boost/assert.hpp>
 
15
#include <boost/graph/graph_traits.hpp>
 
16
#include <boost/type_traits/is_base_and_derived.hpp>
 
17
#include <boost/type_traits/is_same.hpp>
 
18
 
 
19
namespace boost {
 
20
 
 
21
  template<typename Graph>
 
22
  class mesh_iterator
 
23
  {
 
24
    typedef typename graph_traits<Graph>::directed_category directed_category;
 
25
    typedef typename graph_traits<Graph>::vertices_size_type 
 
26
      vertices_size_type;
 
27
 
 
28
    BOOST_STATIC_CONSTANT
 
29
      (bool,
 
30
       is_undirected = (is_base_and_derived<undirected_tag,
 
31
                                            directed_category>::value
 
32
                        || is_same<undirected_tag, directed_category>::value));
 
33
 
 
34
  public:
 
35
    typedef std::input_iterator_tag iterator_category;
 
36
    typedef std::pair<vertices_size_type, vertices_size_type> value_type;
 
37
    typedef const value_type& reference;
 
38
    typedef const value_type* pointer;
 
39
    typedef void difference_type;
 
40
 
 
41
    mesh_iterator()
 
42
      : x(0), y(0), done(true) { }
 
43
 
 
44
    // Vertices are numbered in row-major order
 
45
    // Assumes directed
 
46
    mesh_iterator(vertices_size_type x, vertices_size_type y, 
 
47
                  bool toroidal = true)
 
48
      : x(x), y(y), n(x*y), source(0), target(1), current(0,1), 
 
49
        toroidal(toroidal), done(false)
 
50
    { BOOST_ASSERT(x > 1 && y > 1); }
 
51
 
 
52
    reference operator*() const { return current; }
 
53
    pointer operator->() const { return &current; }
 
54
    
 
55
    mesh_iterator& operator++()
 
56
    {
 
57
      if (is_undirected) {
 
58
        if (!toroidal) {
 
59
          if (target == source + 1)
 
60
            if (source < x * (y - 1))
 
61
              target = source + x;
 
62
            else {
 
63
              source++;
 
64
              target = (source % x) < x - 1 ? source + 1 : source + x;
 
65
              if (target > n) 
 
66
                done = true;
 
67
            }
 
68
          else if (target == source + x) {
 
69
            source++;
 
70
            target = (source % x) < x - 1 ? source + 1 : source + x;
 
71
          }
 
72
        } else {
 
73
          if (target == source + 1 || target == source - (source % x))
 
74
            target = (source + x) % n;
 
75
          else if (target == (source + x) % n) {
 
76
            if (source == n - 1)
 
77
              done = true;
 
78
            else {
 
79
              source++;
 
80
              target = (source % x) < (x - 1) ? source + 1 : source - (source % x);
 
81
            }
 
82
          }
 
83
        }
 
84
      } else { // Directed
 
85
        if ( !toroidal ) {
 
86
          if (target == source - x) 
 
87
            target = source % x > 0 ? source - 1 : source + 1;
 
88
          else if (target == source - 1)
 
89
            if ((source % x) < (x - 1))
 
90
              target = source + 1;
 
91
            else if (source < x * (y - 1))
 
92
              target = source + x;
 
93
            else {
 
94
              done = true;
 
95
            }
 
96
          else if (target == source + 1)
 
97
            if (source < x * (y - 1))
 
98
              target = source + x;
 
99
            else {
 
100
              source++;
 
101
              target = source - x;
 
102
            }
 
103
          else if (target == source + x) {
 
104
            source++;
 
105
            target = (source >= x) ? source - x : source - 1;
 
106
          }
 
107
        } else {
 
108
          if (source == n - 1 && target == (source + x) % n)
 
109
            done = true;
 
110
          else if (target == source - 1 || target == source + x - 1)
 
111
            target = (source + x) % n;
 
112
          else if (target == source + 1 || target == source - (source % x))
 
113
            target = (source - x + n) % n;
 
114
          else if (target == (source - x + n) % n)
 
115
            target = (source % x > 0) ? source - 1 : source + x - 1;
 
116
          else if (target == (source + x) % n) {
 
117
            source++;
 
118
            target = (source % x) < (x - 1) ? source + 1 : source - (source % x);
 
119
          }
 
120
        }
 
121
      }
 
122
 
 
123
      current.first = source;
 
124
      current.second = target;
 
125
 
 
126
      return *this;
 
127
    }
 
128
 
 
129
    mesh_iterator operator++(int)
 
130
    {
 
131
      mesh_iterator temp(*this);
 
132
      ++(*this);
 
133
      return temp;
 
134
    }
 
135
 
 
136
    bool operator==(const mesh_iterator& other) const
 
137
    {
 
138
      return done == other.done;
 
139
    }
 
140
 
 
141
    bool operator!=(const mesh_iterator& other) const
 
142
    { return !(*this == other); }
 
143
 
 
144
  private: 
 
145
 
 
146
    vertices_size_type x,y;
 
147
    vertices_size_type n;
 
148
    vertices_size_type source;
 
149
    vertices_size_type target;
 
150
    value_type current;
 
151
    bool toroidal;
 
152
    bool done;
 
153
  };
 
154
 
 
155
 
 
156
} // end namespace boost
 
157
 
 
158
#endif // BOOST_GRAPH_MESH_GENERATOR_HPP