// 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 &current; }
    
    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