#include <vector>
#include <iostream>

enum orientation_2d_enum { HORIZONTAL = 0, VERTICAL = 1 };
enum direction_1d_enum { LOW = 0, HIGH = 1 };
enum orientation_3d_enum { PROXIMAL = 2 };

class orientation_2d {
private:
  unsigned int val_;
  explicit orientation_2d(int o);
public:
  orientation_2d() : val_(HORIZONTAL) {}
  orientation_2d(const orientation_2d& ori) : val_(ori.val_) {}
  orientation_2d(const orientation_2d_enum val) : val_(val) {}
  const orientation_2d& operator=(const orientation_2d& ori) {
    val_ = ori.val_; return * this; }
  bool operator==(orientation_2d that) const { return (val_ == that.val_); }
  bool operator!=(orientation_2d that) const { return (val_ != that.val_); }
  unsigned int to_int() const { return (val_); }
  void turn_90() { val_ = val_^ 1; }
};

class direction_1d {
private:
  unsigned int val_;
  explicit direction_1d(int d);
public:
  direction_1d() { val_ = LOW; }
  direction_1d(const direction_1d& that) : val_(that.val_) {}
  direction_1d(const direction_1d_enum val) : val_(val) {}
  const direction_1d& operator = (const direction_1d& d) { 
    val_ = d.val_; return * this; }
  bool operator==(direction_1d d) const { return (val_ == d.val_); }
  bool operator!=(direction_1d d) const { return !((*this) == d); }
  unsigned int to_int(void) const { return val_; }
};

class orientation_3d {
private:
  unsigned int val_;
  explicit orientation_3d(int o);
public:
  orientation_3d() : val_((int)HORIZONTAL) {}
  orientation_3d(const orientation_3d& ori) : val_(ori.val_) {}
  orientation_3d(const orientation_2d& ori) { val_ = ori.to_int(); }
  orientation_3d(const orientation_2d_enum val) : val_(val) {}
  orientation_3d(const orientation_3d_enum val) : val_(val) {}
  ~orientation_3d() {  }
  const orientation_3d& operator=(const orientation_3d& ori) { 
    val_ = ori.val_; return * this; }
  bool operator==(orientation_3d that) const { return (val_ == that.val_); }
  bool operator!=(orientation_3d that) const { return (val_ != that.val_); }
  unsigned int to_int() const { return (val_); }
};


template <typename T>
class point_data {
public:
  typedef T coordinate_type;
  inline point_data(){} 
  inline point_data(coordinate_type x, coordinate_type y) {
    coords_[HORIZONTAL] = x; coords_[VERTICAL] = y; 
  }
  inline point_data(const point_data& that) { (*this) = that; }
  inline point_data& operator=(const point_data& that) {
    coords_[0] = that.coords_[0]; coords_[1] = that.coords_[1]; return *this; 
  }
  template <typename T2>
  inline point_data& operator=(const T2& that);
  inline coordinate_type get(orientation_2d orient) const {
    return coords_[orient.to_int()]; 
  }
  inline void set(orientation_2d orient, coordinate_type value) {
    coords_[orient.to_int()] = value; 
  }
private:
  coordinate_type coords_[2]; 
};

template <typename T>
struct point_traits {
  typedef typename T::coordinate_type coordinate_type;
  
  static inline coordinate_type get(const T& point, orientation_2d orient) {
    return point.get(orient); 
  }
  static inline void set(T& point, orientation_2d orient, coordinate_type value) {
    point.set(orient, value); 
  }
  static inline T construct(coordinate_type x_value, coordinate_type y_value) {
    return T(x_value, y_value); 
  }
};

struct point_concept {
  template <typename T>
  static inline typename point_traits<T>::coordinate_type get(const T& point, orientation_2d orient) {
    return point_traits<T>::get(point, orient);
  }
  
  template <orientation_2d_enum orient, typename T>
  static inline typename point_traits<T>::coordinate_type get(const T& point) {
    return get(point, orient); 
  }
  
  template <typename T, typename coordinate_type>
  static inline void set(T& point, orientation_2d orient, coordinate_type value) {
    point_traits<T>::set(point, orient, value);
  }
  
  template <orientation_2d_enum orient, typename T, typename coordinate_type>
  static inline void set(T& point, coordinate_type value) {
    set(point, orient, value);
  }

  template <typename T, typename coordinate_type1, typename coordinate_type2>
  static inline T construct(coordinate_type1 x_value, coordinate_type2 y_value) {
    return point_traits<T>::construct(x_value, y_value); 
  }

  template <typename T, typename T2>
  static inline bool equivilence(const T& point1, const T2& point2) {
    typename point_traits<T>::coordinate_type x1 = get<HORIZONTAL>(point1);
    typename point_traits<T2>::coordinate_type x2 = get(point2, HORIZONTAL);
    typename point_traits<T>::coordinate_type y1 = get(point1, VERTICAL);
    typename point_traits<T2>::coordinate_type y2 = get<VERTICAL>(point2);
    return x1 == x2 && y1 == y2;
  }

  template <typename point_type_1, typename point_type_2>
  static typename point_traits<point_type_1>::coordinate_type
  manhattan_distance(const point_type_1& point1, const point_type_2& point2) {
    return distance(point1, point2, HORIZONTAL) + distance(point1, point2, VERTICAL);
  }

  template <typename point_type_1, typename point_type_2>
  static typename point_traits<point_type_1>::coordinate_type
  distance(const point_type_1& point1, const point_type_2& point2, orientation_2d orient) {
    typename point_traits<point_type_1>::coordinate_type return_value =
      get(point1, orient) - get(point2, orient);
    return return_value < 0 ? -return_value : return_value;
  }

};

template<>
int point_concept::get(const point_data<int>& point, orientation_2d orient) {
  return point.get(orient);
}
template<>
long long point_concept::get(const point_data<long long>& point, orientation_2d orient) {
  return point.get(orient);
}

template <typename T>
class interval_data {
public:
  typedef T coordinate_type;
  inline interval_data(){} 
  inline interval_data(coordinate_type low, coordinate_type high) {
    coords_[LOW] = low; coords_[HIGH] = high; 
  }
  inline interval_data(const interval_data& that) {
    (*this) = that; 
  }
  inline interval_data& operator=(const interval_data& that) {
    coords_[0] = that.coords_[0]; coords_[1] = that.coords_[1]; return *this; 
  }
  inline coordinate_type get(direction_1d dir) const {
    return coords_[dir.to_int()]; 
  }
  inline void set(direction_1d dir, coordinate_type value) {
    coords_[dir.to_int()] = value; 
  }
private:
  coordinate_type coords_[2]; 
};

template <typename T>
struct interval_traits {
  typedef typename T::coordinate_type coordinate_type;

  static inline coordinate_type get(const T& interval, direction_1d dir) {
    return interval.get(dir); 
  }

  static inline void set(T& interval, direction_1d dir, coordinate_type value) {
    interval.set(dir, value); 
  }

  static inline T construct(coordinate_type low_value, coordinate_type high_value) {
    return T(low_value, high_value); 
  }
};

struct interval_concept {
  template <direction_1d_enum dir, typename T>
  static inline typename interval_traits<T>::coordinate_type 
  get(const T& interval) {
    return interval_traits<T>::get(interval, dir);
  }
  
  template <typename T>
  static inline typename interval_traits<T>::coordinate_type 
  get(const T& interval, direction_1d dir) {
    return interval_traits<T>::get(interval, dir); 
  }

  template <direction_1d_enum dir, typename T, typename coordinate_type>
  static inline void set(T& interval, coordinate_type value) {
    interval_traits<T>::set(interval, dir, value); 
  }
  
  template <typename T, typename coordinate_type>
  static inline void set(T& interval, direction_1d dir, coordinate_type value) {
    interval_traits<T>::set(interval, dir, value); 
  }
  
  template <typename T, typename coordinate_type1, typename coordinate_type2>
  static inline T construct(coordinate_type1 low_value, coordinate_type2 high_value) {
    if(low_value > high_value) std::swap(low_value, high_value);
    return interval_traits<T>::construct(low_value, high_value); 
  }
  
  template <typename T, typename T2>
  static T copy_construct(const T2& interval) {
    return construct<T>
      (get(interval, LOW ),
       get(interval, HIGH));
  }

  template <typename T, typename T2>
  static bool equivilence(const T& interval1, const T2& interval2) {
    return get(interval1, LOW) ==
      get(interval2, LOW) &&
      get(interval1, HIGH) ==
      get(interval2, HIGH); 
  }

  template <typename interval_type, typename coordinate_type>
  static bool contains_coordinate(const interval_type& interval,
                                   coordinate_type value, bool consider_touch) {
    if(consider_touch) {
      return value <= get<HIGH>(interval) && value >= get<LOW>(interval);
    } else {
      return value < get<HIGH>(interval) && value > get<LOW>(interval);
    }
  }

};

template <typename T>
class rectangle_data {
public:
  typedef T coordinate_type;
  inline rectangle_data() {}
  template <typename interval_type_1, typename interval_type_2>
  inline rectangle_data(const interval_type_1& hrange,
                        const interval_type_2& vrange) {
    set(HORIZONTAL, hrange); set(VERTICAL, hrange); }

  inline rectangle_data(const rectangle_data& that) { (*this) = that; }

  inline rectangle_data& operator=(const rectangle_data& that) {
    ranges_[0] = that.ranges_[0]; ranges_[1] = that.ranges_[1]; return *this;
  }

  inline interval_data<coordinate_type> get(orientation_2d orient) const {
    return ranges_[orient.to_int()]; }
  template <typename interval_type>
  inline void set(orientation_2d orient, const interval_type& interval) {
    ranges_[orient.to_int()].set(LOW, interval_concept::get(interval, LOW));
    ranges_[orient.to_int()].set(HIGH, interval_concept::get(interval, HIGH));
  }
private:
  interval_data<coordinate_type> ranges_[2]; 
};

template <typename T>
struct rectangle_traits {
  typedef typename T::coordinate_type coordinate_type;
  typedef interval_data<coordinate_type> interval_type;
  
  static inline interval_type get(const T& rectangle, orientation_2d orient) {
    return rectangle.get(orient); }

  template <typename T2>
  static inline void set(T& rectangle, orientation_2d orient, const T2& interval) {
    rectangle.set(orient, interval); }
  
  template <typename T2, typename T3>
  static inline T construct(const T2& interval_horizontal,
                            const T3& interval_vertical) {
    return T(interval_horizontal, interval_vertical); }
};
  
struct rectangle_concept {
  template <orientation_2d_enum orient, typename T>
  static inline typename rectangle_traits<T>::interval_type 
  get(const T& rectangle) {
    return rectangle_traits<T>::get(rectangle, orient); 
  }
  
  template <typename T>
  static inline typename rectangle_traits<T>::interval_type 
  get(const T& rectangle, orientation_2d orient) {
    return rectangle_traits<T>::get(rectangle, orient); 
  }

  template <orientation_2d_enum orient, typename T, typename T2>
  static inline void set(T& rectangle, const T2& interval) {
    rectangle_traits<T>::set(rectangle, orient, interval); 
  }

  template <typename T, typename T2>
  static inline void set(T& rectangle, orientation_2d orient, const T2& interval) {
    rectangle_traits<T>::set(rectangle, orient, interval); 
  }

  template <typename T, typename T2, typename T3>
  static inline T construct(const T2& interval_horizontal,
                            const T3& interval_vertical) {
    return rectangle_traits<T>::construct(interval_horizontal, interval_vertical); }

  template <typename T, typename coordinate_type>
  static inline T construct(coordinate_type xl, coordinate_type yl, coordinate_type xh, coordinate_type yh) {
    return rectangle_traits<T>::construct(interval_data<coordinate_type>(xl, xh), 
                                          interval_data<coordinate_type>(yl, yh)); 
  }

  template <typename T, typename T2>
  static T copy_construct(const T2& rectangle) {
    return construct<T>
      (get(rectangle, HORIZONTAL),
       get(rectangle, VERTICAL));
  }
  
  template <typename T, typename T2>
  static bool equivilence(const T& rect1, const T2& rect2) {
    return interval_concept::equivilence(get(rect1, HORIZONTAL),
                                         get(rect2, HORIZONTAL)) &&
      interval_concept::equivilence(get(rect1, VERTICAL),
                                    get(rect2, VERTICAL));
  }

  template <typename rectangle_type>
  static typename rectangle_traits<rectangle_type>::coordinate_type
  xl(const rectangle_type& rectangle) {
    return interval_concept::get<LOW>(get<HORIZONTAL>(rectangle));
  }

  template <typename rectangle_type>
  static typename rectangle_traits<rectangle_type>::coordinate_type
  xh(const rectangle_type& rectangle) {
    return interval_concept::get<HIGH>(get<HORIZONTAL>(rectangle));
  }

  template <typename rectangle_type>
  static typename rectangle_traits<rectangle_type>::coordinate_type
  yl(const rectangle_type& rectangle) {
    return interval_concept::get<LOW>(get<VERTICAL>(rectangle));
  }

  template <typename rectangle_type>
  static typename rectangle_traits<rectangle_type>::coordinate_type
  yh(const rectangle_type& rectangle) {
    return interval_concept::get<HIGH>(get<VERTICAL>(rectangle));
  }


};

template <typename T>
class point_3d_data {
public:
  typedef T coordinate_type;
  inline point_3d_data(){} 
  inline point_3d_data(coordinate_type x, coordinate_type y) {
    coords_[HORIZONTAL] = x; coords_[VERTICAL] = y; coords_[PROXIMAL] = 0; }
  inline point_3d_data(coordinate_type x, coordinate_type y, coordinate_type z) {
    coords_[HORIZONTAL] = x; coords_[VERTICAL] = y; coords_[PROXIMAL] = z; }
  inline point_3d_data(const point_3d_data& that) { (*this) = that; }
  inline point_3d_data& operator=(const point_3d_data& that) {
    coords_[0] = that.coords_[0]; coords_[1] = that.coords_[1]; 
    coords_[2] = that.coords_[2]; return *this; }
  template <typename T2>
  inline point_3d_data& operator=(const T2& that);
  inline coordinate_type get(orientation_3d orient) const {
    return coords_[orient.to_int()]; }
  inline void set(orientation_3d orient, coordinate_type value) {
    coords_[orient.to_int()] = value; }
private:
  coordinate_type coords_[3]; 
};
  
template <typename T>
struct point_3d_traits {
  typedef typename T::coordinate_type coordinate_type;

  static inline coordinate_type get(const T& point, orientation_3d orient) {
    return point.get(orient); }

  static inline void set(T& point, orientation_3d orient, coordinate_type value) {
    point.set(orient, value); }
  
  static inline T construct(coordinate_type x_value, 
                            coordinate_type y_value, 
                            coordinate_type z_value) {
    return T(x_value, y_value, z_value); }
};
  
struct point_3d_concept {
  template <orientation_2d_enum orient, typename T> 
  static inline typename point_traits<T>::coordinate_type get(const T& point) {
    return point_traits<T>::get(point, orient); }

  template <orientation_3d_enum orient, typename T>
  static inline typename point_3d_traits<T>::coordinate_type get(const T& point) {
    return point_3d_traits<T>::get(point, orient); }

  template <typename T>
  static inline typename point_3d_traits<T>::coordinate_type get(const T& point, orientation_3d orient) {
    return point_3d_traits<T>::get(point, orient); }
  
  template <orientation_2d_enum orient, typename T, typename coordinate_type>
  static inline void set(T& point, coordinate_type value) {
    point_traits<T>::set(point, orient, value); }
  template <orientation_3d_enum orient, typename T, typename coordinate_type>
  static inline void set(T& point, coordinate_type value) {
    point_traits<T>::set(point, orient, value); }
  template <typename T, typename coordinate_type>
  static inline void set(T& point, orientation_3d orient, coordinate_type value) {
    point_traits<T>::set(point, orient, value); }

  template <typename T, typename coordinate_type1, typename coordinate_type2, typename coordinate_type3>
  static inline T construct(coordinate_type1 x_value, 
                            coordinate_type2 y_value, 
                            coordinate_type3 z_value) {
    return point_3d_traits<T>::construct(x_value, y_value, z_value); }
};

template <class T>
template <class T2>
point_data<T>& point_data<T>::operator=(const T2& r_point) {
  set(HORIZONTAL, point_concept::get(r_point, HORIZONTAL));
  set(VERTICAL, point_concept::get(r_point, VERTICAL));
  return *this;
}

template <class T>
template <class T2>
point_3d_data<T>& point_3d_data<T>::operator=(const T2& r_point) {
  set(HORIZONTAL, point_3d_concept::get(r_point, HORIZONTAL));
  set(VERTICAL, point_3d_concept::get(r_point, VERTICAL));
  set(PROXIMAL, point_3d_concept::get(r_point, PROXIMAL));
  return *this;
}

inline bool testPattern() {
  point_data<int> pt(10, 20);
  point_data<long long> pt2(10, 90);
  pt = pt2;
  std::cout << (point_concept::equivilence(pt, pt2)) << std::endl;
  rectangle_data<int> rect1(interval_data<int>(10, 20), interval_data<int>(30, 40));
  rectangle_data<long long> rect2(interval_data<long long>(10, 20),
                                  interval_data<long long>(30, 40));
  rectangle_data<int> rect3 = rectangle_concept::copy_construct<rectangle_data<int>, 
    rectangle_data<long long> >(rect2);
  point_3d_data<long long> pt3d(40, 50, 30);
  pt = pt3d;
  pt3d = pt3d;
  return point_concept::equivilence(pt, pt3d);
}

struct LayoutObject {
public:
  std::string netname;
  int xl, yl, xh, yh, layer, id;
  LayoutObject() {}
  LayoutObject(std::string name, int xl_val, int yl_val, int xh_val, int yh_val, int layer_val, int id_val) :
    netname(name), xl(xl_val), yl(yl_val), xh(xh_val), yh(yh_val), layer(layer_val), id(id_val) {}
  LayoutObject& operator=(const LayoutObject& that) {
    netname = that.netname;
    xl = that.xl;
    xh = that.xh;
    yl = that.yl;
    yh = that.yh;
    layer = that.layer;
    id = that.id;
    return *this;
  }
};

template <>
struct rectangle_traits<LayoutObject> {
  typedef int coordinate_type;
  typedef interval_data<coordinate_type> interval_type;

  static interval_type get(const LayoutObject& rectangle, orientation_2d orient) {
    if(orient == HORIZONTAL)
      return rectangle_traits<LayoutObject>::interval_type(rectangle.xl, rectangle.xh);
    return rectangle_traits<LayoutObject>::interval_type(rectangle.yl, rectangle.yh);
  }

  template <typename T2>
  static inline void set(LayoutObject& rectangle, orientation_2d orient, const T2& interval) {
    if(orient == HORIZONTAL) {
      rectangle.xl = interval_concept::get<LOW>(interval);
      rectangle.xh = interval_concept::get<HIGH>(interval);
    } else {
      rectangle.yl = interval_concept::get<LOW>(interval);
      rectangle.yh = interval_concept::get<HIGH>(interval);
    }
  }
  
  template <typename T2, typename T3>
  static inline LayoutObject construct(const T2& interval_horizontal,
                                                   const T3& interval_vertical) {
    return LayoutObject("", interval_concept::get(interval_horizontal, LOW),
                        interval_concept::get(interval_vertical, LOW),
                        interval_concept::get(interval_horizontal, HIGH),
                        interval_concept::get(interval_vertical, HIGH), 0, 0);
  }
};


template <typename T>
class polygon_data {
public:
  typedef T coordinate_type;
  typedef typename std::vector<coordinate_type>::const_iterator iterator_type;

  inline polygon_data(){;} //do nothing default constructor

  /// initialize a polygon from x,y values, it is assumed that the first is an x
  /// and that the input is a well behaved polygon
  template<class iT>
  inline polygon_data& set(iT input_begin, iT input_end) {
    coords_.clear();  //just in case there was some old data there
    while(input_begin != input_end) {
       coords_.insert(coords_.end(), *input_begin);
       ++input_begin;
    }
    return *this;
  }

  /// copy constructor (since we have dynamic memory)
  inline polygon_data(const polygon_data& that) : coords_(that.coords_) {}
  
  /// assignment operator (since we have dynamic memory do a deep copy)
  inline polygon_data& operator=(const polygon_data& that) {
    coords_ = that.coords_;
    return *this;
  }

  /// get begin iterator, returns a pointer to a const Unit
  inline iterator_type begin() const { return coords_.begin(); }

  /// get end iterator, returns a pointer to a const Unit
  inline iterator_type end() const { return coords_.end(); }

  inline std::size_t size() const { return coords_.size(); }

private:
  std::vector<coordinate_type> coords_; 
};

enum winding_direction {
  counterclockwise_winding = 0,
  clockwise_winding = 1,
  unknown_winding = 2
};

template <class T>
struct polygon_traits {
  typedef typename T::coordinate_type coordinate_type;
  typedef typename T::iterator_type iterator_type;

  /// Get the begin iterator
  static inline iterator_type begin(const T& t) {
    return t.begin();
  }
  
  /// Get the end iterator
  static inline iterator_type end(const T& t) {
    return t.end();
  }
  
  /// Set the data of a polygon with the unique coordinates in an iterator, starting with an x
  template <class iT>
  static inline T& set(T& t, iT input_begin, iT input_end) {
    t.set(input_begin, input_end);
    return t;
  }
  
  /// Get the number of sides of the polygon
  static inline unsigned int size(const T& t) {
    return t.size();
  }
  
  /// Get the winding direction of the polygon
  static inline winding_direction winding(const T& t) {
    return unknown_winding;
  }
};

struct polygon_concept {
  template <class iterator_type, class point_type>
  class iterator_points {
  private:
    iterator_type iter_;
    iterator_type iter_end_;
    point_type pt_;
    typename point_traits<point_type>::coordinate_type firstX_;
    orientation_2d orient_;
  public:
    inline iterator_points() {}
    inline iterator_points(iterator_type iter, iterator_type iter_end) : 
      iter_(iter), iter_end_(iter_end), orient_(HORIZONTAL) {
      if(iter_ != iter_end_) {
        firstX_ = *iter_;
        point_concept::set<HORIZONTAL>(pt_, firstX_);
        ++iter_;
        if(iter_ != iter_end_) {
          point_concept::set<VERTICAL>(pt_, *iter_);
        }
      }
    }
    //use bitwise copy and assign provided by the compiler
    inline iterator_points& operator++() {
      ++iter_;
      if(iter_ == iter_end_) {
        if(point_concept::get<HORIZONTAL>(pt_) != firstX_) {
              --iter_;
              point_concept::set<HORIZONTAL>(pt_, firstX_);
        }
      } else {
        point_concept::set(pt_, orient_, *iter_);
        orient_.turn_90();
      }
      return *this;
    }
    inline iterator_points operator++(int) {
      iterator_points tmp(*this);
      ++(*this);
      return tmp;
    }
    inline bool operator==(const iterator_points& that) const {
      return (iter_ == that.iter_);
    }
    inline bool operator!=(const iterator_points& that) const {
      return (iter_ != that.iter_);
    }
    inline const point_type& operator*() const { return pt_; }
  };

  template <class iT, typename coordinate_type>
  class iterator_points_to_coords {
  private:
     iT iter_;
     orientation_2d orient_;
  public:
     inline iterator_points_to_coords() {}
     inline iterator_points_to_coords(iT iter) : iter_(iter), orient_(HORIZONTAL) {}
     inline iterator_points_to_coords(const iterator_points_to_coords& that) : 
       iter_(that.iter_), orient_(that.orient_) {}
     //use bitwise copy and assign provided by the compiler
     inline iterator_points_to_coords& operator++() {
        ++iter_;
        orient_.turn_90();
        return *this;
     }
     inline iterator_points_to_coords operator++(int) {
        iT tmp(*this);
        ++(*this);
        return tmp;
     }
     inline bool operator==(const iterator_points_to_coords& that) const {
        return (iter_ == that.iter_);
     }
     inline bool operator!=(const iterator_points_to_coords& that) const {
        return (iter_ != that.iter_);
     }
     inline coordinate_type operator*() { return (*iter_).get(orient_); }
  };

  template<typename polygon_type, typename iterator_type>
  static void set(polygon_type& polygon, iterator_type input_begin, iterator_type input_end) {
    polygon_traits<polygon_type>::set(polygon, input_begin, input_end);
  }

  template<typename polygon_type, typename rectangle_type>
  static void set(polygon_type& polygon, const rectangle_type& rect) {
    typename polygon_traits<polygon_type>::coordinate_type coords[4] = 
      {rectangle_concept::xl(rect), rectangle_concept::yl(rect),
       rectangle_concept::xh(rect), rectangle_concept::yh(rect)};
    set(polygon, coords, coords+4);
  }
   
  template<typename polygon_type, typename point_iterator_type>
  static void set_points(polygon_type& polygon, point_iterator_type begin_point, point_iterator_type end_point) {
    return set(iterator_points_to_coords<point_iterator_type, 
        typename polygon_traits<polygon_type>::coordinate_type>(begin_point),
        iterator_points_to_coords<point_iterator_type, 
        typename polygon_traits<polygon_type>::coordinate_type>(end_point));
  }

  template <typename polygon_type>
  static typename polygon_traits<polygon_type>::iterator_type begin(const polygon_type& polygon) {
    return polygon_traits<polygon_type>::begin(polygon);
  }
  
  template <typename polygon_type>
  static typename polygon_traits<polygon_type>::iterator_type end(const polygon_type& polygon) {
    return polygon_traits<polygon_type>::end(polygon);
  }
  
  template <typename polygon_type>
  static iterator_points<typename polygon_traits<polygon_type>::iterator_type,
                         point_data<typename polygon_traits<polygon_type>::coordinate_type> > 
  begin_points(const polygon_type& polygon) {
    return iterator_points<typename polygon_traits<polygon_type>::iterator_type,
      point_data<typename polygon_traits<polygon_type>::coordinate_type> > (begin(polygon), end(polygon));
  }

  template <typename polygon_type>
  static iterator_points<typename polygon_traits<polygon_type>::iterator_type,
                         point_data<typename polygon_traits<polygon_type>::coordinate_type> > 
  end_points(const polygon_type& polygon) {
    return iterator_points<typename polygon_traits<polygon_type>::iterator_type,
      point_data<typename polygon_traits<polygon_type>::coordinate_type> > (end(polygon), end(polygon));
  }

  template<typename T, class iT>
  static T construct(iT inputBegin, iT inputEnd) { return polygon_traits<T>::construct(inputBegin, inputEnd); }

  template<typename polygon_type, typename rectangle_type>
  static polygon_type construct_from_rectangle(const rectangle_type& rect) {
    polygon_type poly;
    set(poly, rect);
    return poly;
  }

  template <typename polygon_type, typename polygon_type2>
  static polygon_type copy_construct(const polygon_type2& polygon) { 
    return construct(polygon_concept::begin(polygon), polygon_concept::end(polygon)); 
  }

  template <typename polygon_type>
  static std::size_t size(const polygon_type& polygon) {
    return polygon_traits<polygon_type>::size(polygon);
  }

  template <typename polygon_type>
  static direction_1d winding(const polygon_type& polygon){
    winding_direction wd = polygon_traits<polygon_type>::winding(polygon);
    if(wd != unknown_winding) {
      return wd == clockwise_winding ? LOW: HIGH;
    }
    direction_1d dir = HIGH;
    typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
    typedef typename polygon_traits<polygon_type>::iterator iterator;
    iterator itr = begin(polygon);
    coordinate_type firstx = *itr;
    coordinate_type minX = firstx;
    ++itr;
    iterator end_itr = end(polygon);
    if(itr == end_itr) return dir; 
    coordinate_type prevy = *itr;
    coordinate_type firsty = *itr;
    ++itr;
    for( ; itr != end_itr; ++itr) {
      coordinate_type x = *itr;
      ++itr;
      if(itr == end_itr) break;
      coordinate_type y = *itr;
      if(x <= minX) {
        minX = x;
        //edge directed downward on left side of figure is counterclockwise
        dir = y < prevy ? HIGH : LOW;
      }
      prevy = y;
    }
    if(firstx <= minX) {
      dir = firsty < prevy ? HIGH : LOW;
    }
    return dir;
  }

  template <typename polygon_type>
  static rectangle_data<typename polygon_traits<polygon_type>::coordinate_type> 
  bounding_box(const polygon_type& polygon) {
    typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
    typedef typename polygon_traits<polygon_type>::iterator_type iterator;
    coordinate_type xmin = 0;
    coordinate_type ymin = 0;
    coordinate_type xmax = 0;
    coordinate_type ymax = 0;
    bool first_iteration = true;
    iterator itr_end = end(polygon);
    for(iterator itr = begin(polygon); itr != itr_end; ++itr) {
      coordinate_type x = *itr;
      ++itr;
      if(itr == itr_end) break;
      coordinate_type y = *itr;
      if(first_iteration) {
        xmin = xmax = x;
        ymin = ymax = x;
        first_iteration = false;
      }
      xmin = std::min(xmin, x);
      xmax = std::max(xmax, x);
      ymin = std::min(ymin, y);
      ymax = std::max(ymax, y);
    }
    typedef rectangle_data<coordinate_type> rectangle_type;
    rectangle_type return_value = rectangle_concept::construct<rectangle_type>(xmin, ymin, xmax, ymax);
    return return_value;
  }

  template <typename polygon_type>
  static typename polygon_traits<polygon_type>::coordinate_type 
  area(const polygon_type& polygon) {
    //for (long i = 2; i < _size; i += 2) res += ((double)_vertex[i-1])*((double)(_vertex[i-2] - _vertex[i]));
    typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
    typedef typename polygon_traits<polygon_type>::iterator_type iterator;
    coordinate_type retval = 0;
    iterator itr = begin(polygon);
    iterator end_itr = end(polygon);
    coordinate_type firstx = *itr;
    coordinate_type prevx = *itr;
    ++itr;
    if(itr == end_itr) return 0;
    coordinate_type prevy = *itr;
    ++itr;
    for( ; itr != end_itr; ++itr) {
      coordinate_type x = *itr;
      ++itr;
      if(itr == end_itr) break;
      coordinate_type y = *itr;
      retval += (prevy * (prevx - x));
      prevy = y;
      prevx = x;
    }
    retval += (prevy * (prevx - firstx));
    return retval >= 0 ? retval : -retval;
  }

  /// get the perimeter of the rectangle
  template <typename polygon_type>
  static typename polygon_traits<polygon_type>::coordinate_type
  perimeter(const polygon_type& polygon) {
    typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
    typedef typename polygon_traits<polygon_type>::iterator_type iterator_type;
    typedef iterator_points<iterator_type, point_data<coordinate_type> > iterator;
    coordinate_type return_value = 0;
    point_data<coordinate_type> previous_point, first_point;
    iterator itr = begin_points(polygon);
    iterator itr_end = end_points(polygon);
    if(itr == itr_end) return return_value;
    previous_point = first_point = *itr;
    ++itr;
    for( ; itr != itr_end; ++itr) {
      ++itr;
      if(itr == itr_end) break;
      point_data<coordinate_type> current_point = *itr;
      return_value += point_concept::manhattan_distance(current_point, previous_point);
      previous_point = current_point;
    }
    return_value += point_concept::manhattan_distance(previous_point, first_point);
    return return_value;
  }

  /// check if point is inside polygon 
  template <typename polygon_type, typename point_type>
  static bool contains_point(const polygon_type& polygon, const point_type& point, 
                             bool consider_touch = true) {
    typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
    typedef typename polygon_traits<polygon_type>::iterator_type iterator_type;
    typedef iterator_points<iterator_type, point_data<coordinate_type> > iterator;
    iterator iter, iter_end;
    iter_end = end_points(polygon);
    iter = begin_points(polygon);
    point_data<coordinate_type> prev_pt = *iter;
    unsigned int num = size(polygon);
    unsigned int counts[2] = {0, 0};
    for(unsigned int i = 0; i < num; ++i) {
      if(i == num-1) iter = begin_points(polygon);
      else ++iter;
      point_data<coordinate_type> current_pt = *iter;
      if(point_concept::get<HORIZONTAL>(current_pt) == 
         point_concept::get<HORIZONTAL>(prev_pt)) {
        unsigned int index = point_concept::get<HORIZONTAL>(current_pt) > 
          point_concept::get<HORIZONTAL>(point);
        unsigned int increment = 0;
        interval_data<coordinate_type> ivl = 
          interval_concept::construct<interval_data<coordinate_type> >(point_concept::get<VERTICAL>(current_pt), 
                                                                       point_concept::get<VERTICAL>(prev_pt));
        if(interval_concept::contains_coordinate(ivl, point_concept::get<VERTICAL>(point), true)) {
          if(point_concept::get<HORIZONTAL>(current_pt) == 
             point_concept::get<HORIZONTAL>(point)) return consider_touch;
          ++increment;
          if(point_concept::get<VERTICAL>(current_pt) != 
              point_concept::get<VERTICAL>(point) &&
              point_concept::get<VERTICAL>(prev_pt) != 
              point_concept::get<VERTICAL>(point)) {
            ++increment;
          } 
          counts[index] += increment;
        }
      }
      prev_pt = current_pt;
    }
    //odd count implies boundary condition
    if(counts[0] % 2 || counts[1] % 2) return consider_touch;
    //an odd number of edges to the left implies interior pt
    return counts[0] % 4; 
  }

//   //awaiting re-implementation of iterator_edges and edge concept
//   template <typename polygon_type, typename point_type>
//   static point_type project(const polygon_type& polygon, const point_type& point) const {
//     point_type return_value;
//     typedef iterator_edges<typename polygon_traits<polygon_type>::iterator_type,
//       edge_data<typename polygon_traits<polygon_type>::coordinate_type> > iterator;
//     iterator iter = begin_edges();
//     iterator iter_end = end_edges();
//     double dist = 0;
//     bool first_segment = true;
//     for( ; iter != iter_end; ++iter) {
//       point_type segement_point = segment_concept::project_point(*iter, point);
//       double seg_dist = point_concept::euclidian_distance(point, segment_point);
//       if(first_segment || seg_dist < dist) {
//         dist = seg_dist;
//         return_value = segment_point;
//       }
//     }
//     return return_value;
//   }
  
//   //awaiting re-implementation of iterator_edges and edge concept
//   template <typename polygon_type, typename point_type>
//   static point_type project(point_type& result, const polygon_type& polygon, 
//                             const point_type& point, direction_2d dir) {
//     typedef iterator_edges<typename polygon_traits<polygon_type>::iterator_type,
//       edge_data<typename polygon_traits<polygon_type>::coordinate_type> > iterator;
//     iterator iter = begin_edges();
//     iterator iter_end = end_edges();
//     double dist = 0;
//     bool found = false;
//     bool first_segment = true;
//     for( ; iter != iter_end; ++iter) {
//       point_type segement_point;
//       if(segment_concept::project_point(segment_point, *iter, point, dir)) {
//            found = true;
//            double seg_dist = point_concept::euclidian_distance(point, segment_point);
//            if(first_segment || seg_dist < dist) {
//              dist = seg_dist;
//              result = segment_point;
//       }
//     }
//     return found;
//   }

  template <typename polygon_type, typename coordinate_type_1, typename coordinate_type_2>
  static void move(polygon_type& polygon, coordinate_type_1 x_displacement, coordinate_type_2 y_displacement) {
    std::vector<typename polygon_traits<polygon_type>::coordinate_type> coords;
    coords.reserve(size(polygon));
    bool pingpong = true;
    for(typename polygon_traits<polygon_type>::iterator_type iter = begin(polygon); 
        iter != end(polygon); ++iter) {
      coords.push_back((*iter) + predicated_value(pingpong, x_displacement, y_displacement));
      pingpong = !pingpong;
    }
    set(polygon, coords.begin(), coords.end());
  }
  
  /// move polygon by delta in orient
  template <typename polygon_type, typename coordinate_type_1>
  static void move(polygon_type& polygon, orientation_2d orient, coordinate_type_1 displacement) {
    if(orient == HORIZONTAL) {
      move(displacement, 0);
    } else {
      move(0, displacement);
    }
  }
};

int main() {
  std::cout << testPattern() << std::endl;
  rectangle_data<long long> rect(interval_data<long long>(10, 20),
                                 interval_data<long long>(30, 40));
  LayoutObject lobj = rectangle_concept::copy_construct<LayoutObject, rectangle_data<long long> >(rect);
  std::cout << (rectangle_concept::equivilence(rect, lobj)) << std::endl;
  std::cout << (interval_concept::equivilence(rectangle_concept::get(lobj, HORIZONTAL),
                                               rect.get(HORIZONTAL))) << std::endl;

  rectangle_data<long long> rectangle1 = rectangle_concept::construct<rectangle_data<long long> >(10, 20, 30, 40);
  polygon_data<int> polygon1 = polygon_concept::construct_from_rectangle<polygon_data<int> >(rectangle1);
  polygon_data<long long> polygon2 = polygon_concept::construct_from_rectangle<polygon_data<long long> >(rectangle1);
  rectangle_data<int> rectangle2 = rectangle_concept::copy_construct<rectangle_data<int> >(polygon_concept::bounding_box(polygon2));
  rectangle_data<long long> rectangle3 = rectangle_concept::copy_construct<rectangle_data<long long> >(polygon_concept::bounding_box(polygon1));
  bool result = rectangle_concept::equivilence(rectangle2, rectangle3);
  std::cout << result << std::endl;
  std::cout << (polygon_concept::perimeter(polygon1)) << std::endl;
  point_data<long long> pt(10, 20);
  std::cout << (polygon_concept::contains_point(polygon1, pt)) << std::endl;
  return 0;
}