ceph/src/boost/boost/polygon/isotropy.hpp

   1 /*
   2   Copyright 2008 Intel Corporation
   3
   4   Use, modification and distribution are subject to the Boost Software License,
   5   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6   http://www.boost.org/LICENSE_1_0.txt).
   7 */
   8
   9 #ifndef BOOST_POLYGON_ISOTROPY_HPP
  10 #define BOOST_POLYGON_ISOTROPY_HPP
  11
  12 //external
  13 #include <cmath>
  14 #include <cstddef>
  15 #include <cstdlib>
  16 #include <vector>
  17 #include <deque>
  18 #include <map>
  19 #include <set>
  20 #include <list>
  21 //#include <iostream>
  22 #include <algorithm>
  23 #include <limits>
  24 #include <iterator>
  25 #include <string>
  26
  27 #ifndef BOOST_POLYGON_NO_DEPS
  28
  29 #include <boost/config.hpp>
  30 #ifdef BOOST_MSVC
  31 #define BOOST_POLYGON_MSVC
  32 #endif
  33 #ifdef BOOST_INTEL
  34 #define BOOST_POLYGON_ICC
  35 #endif
  36 #ifdef BOOST_HAS_LONG_LONG
  37 #define BOOST_POLYGON_USE_LONG_LONG
  38 typedef boost::long_long_type polygon_long_long_type;
  39 typedef boost::ulong_long_type polygon_ulong_long_type;
  40 //typedef long long polygon_long_long_type;
  41 //typedef unsigned long long polygon_ulong_long_type;
  42 #endif
  43 #else
  44
  45 #ifdef _WIN32
  46 #define BOOST_POLYGON_MSVC
  47 #endif
  48 #ifdef __ICC
  49 #define BOOST_POLYGON_ICC
  50 #endif
  51 #define BOOST_POLYGON_USE_LONG_LONG
  52 typedef long long polygon_long_long_type;
  53 typedef unsigned long long polygon_ulong_long_type;
  54 #endif
  55
  56 namespace boost { namespace polygon{
  57
  58   enum GEOMETRY_CONCEPT_ID {
  59     COORDINATE_CONCEPT,
  60     INTERVAL_CONCEPT,
  61     POINT_CONCEPT,
  62     POINT_3D_CONCEPT,
  63     RECTANGLE_CONCEPT,
  64     POLYGON_90_CONCEPT,
  65     POLYGON_90_WITH_HOLES_CONCEPT,
  66     POLYGON_45_CONCEPT,
  67     POLYGON_45_WITH_HOLES_CONCEPT,
  68     POLYGON_CONCEPT,
  69     POLYGON_WITH_HOLES_CONCEPT,
  70     POLYGON_90_SET_CONCEPT,
  71     POLYGON_45_SET_CONCEPT,
  72     POLYGON_SET_CONCEPT
  73   };
  74
  75   struct undefined_concept {};
  76
  77   template <typename T>
  78   struct geometry_concept { typedef undefined_concept type; };
  79
  80   template <typename GCT, typename T>
  81   struct view_of {};
  82
  83   template <typename T1, typename T2>
  84   view_of<T1, T2> view_as(const T2& obj) { return view_of<T1, T2>(obj); }
  85
  86   template <typename T, bool /*enable*/ = true>
  87   struct coordinate_traits {};
  88
  89   //used to override long double with an infinite precision datatype
  90   template <typename T>
  91   struct high_precision_type {
  92     typedef long double type;
  93   };
  94
  95   template <typename T>
  96   T convert_high_precision_type(const typename high_precision_type<T>::type& v) {
  97     return T(v);
  98   }
  99
 100   //used to override std::sort with an alternative (parallel) algorithm
 101   template <typename iter_type>
 102   void polygon_sort(iter_type _b_, iter_type _e_);
 103
 104   template <typename iter_type, typename pred_type>
 105   void polygon_sort(iter_type _b_, iter_type _e_, const pred_type& _pred_);
 106
 107
 108   template <>
 109   struct coordinate_traits<int> {
 110     typedef int coordinate_type;
 111     typedef long double area_type;
 112 #ifdef BOOST_POLYGON_USE_LONG_LONG
 113     typedef polygon_long_long_type manhattan_area_type;
 114     typedef polygon_ulong_long_type unsigned_area_type;
 115     typedef polygon_long_long_type coordinate_difference;
 116 #else
 117     typedef long manhattan_area_type;
 118     typedef unsigned long unsigned_area_type;
 119     typedef long coordinate_difference;
 120 #endif
 121     typedef long double coordinate_distance;
 122   };
 123
 124   template<>
 125   struct coordinate_traits<long, sizeof(long) == sizeof(int)> {
 126     typedef coordinate_traits<int> cT_;
 127     typedef cT_::coordinate_type coordinate_type;
 128     typedef cT_::area_type area_type;
 129     typedef cT_::manhattan_area_type manhattan_area_type;
 130     typedef cT_::unsigned_area_type unsigned_area_type;
 131     typedef cT_::coordinate_difference coordinate_difference;
 132     typedef cT_::coordinate_distance coordinate_distance;
 133   };
 134
 135 #ifdef BOOST_POLYGON_USE_LONG_LONG
 136   template <>
 137   struct coordinate_traits<polygon_long_long_type> {
 138     typedef polygon_long_long_type coordinate_type;
 139     typedef long double area_type;
 140     typedef polygon_long_long_type manhattan_area_type;
 141     typedef polygon_ulong_long_type unsigned_area_type;
 142     typedef polygon_long_long_type coordinate_difference;
 143     typedef long double coordinate_distance;
 144   };
 145
 146   template<>
 147   struct coordinate_traits<long, sizeof(long) == sizeof(polygon_long_long_type)> {
 148     typedef coordinate_traits<polygon_long_long_type> cT_;
 149     typedef cT_::coordinate_type coordinate_type;
 150     typedef cT_::area_type area_type;
 151     typedef cT_::manhattan_area_type manhattan_area_type;
 152     typedef cT_::unsigned_area_type unsigned_area_type;
 153     typedef cT_::coordinate_difference coordinate_difference;
 154     typedef cT_::coordinate_distance coordinate_distance;
 155   };
 156 #endif
 157
 158   template <>
 159   struct coordinate_traits<float> {
 160     typedef float coordinate_type;
 161     typedef float area_type;
 162     typedef float manhattan_area_type;
 163     typedef float unsigned_area_type;
 164     typedef float coordinate_difference;
 165     typedef float coordinate_distance;
 166   };
 167
 168   template <>
 169   struct coordinate_traits<double> {
 170     typedef double coordinate_type;
 171     typedef double area_type;
 172     typedef double manhattan_area_type;
 173     typedef double unsigned_area_type;
 174     typedef double coordinate_difference;
 175     typedef double coordinate_distance;
 176   };
 177
 178   template <>
 179   struct coordinate_traits<long double> {
 180     typedef long double coordinate_type;
 181     typedef long double area_type;
 182     typedef long double manhattan_area_type;
 183     typedef long double unsigned_area_type;
 184     typedef long double coordinate_difference;
 185     typedef long double coordinate_distance;
 186   };
 187
 188   template <typename T>
 189   struct scaling_policy {
 190     template <typename T2>
 191     static inline T round(T2 t2) {
 192       return (T)std::floor(t2+0.5);
 193     }
 194
 195     static inline T round(T t2) {
 196       return t2;
 197     }
 198   };
 199
 200   struct coordinate_concept {};
 201
 202   template <>
 203   struct geometry_concept<int> { typedef coordinate_concept type; };
 204 #ifdef BOOST_POLYGON_USE_LONG_LONG
 205   template <>
 206   struct geometry_concept<polygon_long_long_type> { typedef coordinate_concept type; };
 207 #endif
 208   template <>
 209   struct geometry_concept<float> { typedef coordinate_concept type; };
 210   template <>
 211   struct geometry_concept<double> { typedef coordinate_concept type; };
 212   template <>
 213   struct geometry_concept<long double> { typedef coordinate_concept type; };
 214
 215   struct gtl_no { static const bool value = false; };
 216   struct gtl_yes { typedef gtl_yes type;
 217     static const bool value = true; };
 218
 219   template <bool T, bool T2>
 220   struct gtl_and_c { typedef gtl_no type; };
 221   template <>
 222   struct gtl_and_c<true, true> { typedef gtl_yes type; };
 223
 224   template <typename T, typename T2>
 225   struct gtl_and : gtl_and_c<T::value, T2::value> {};
 226   template <typename T, typename T2, typename T3>
 227   struct gtl_and_3 { typedef typename gtl_and<
 228                        T, typename gtl_and<T2, T3>::type>::type type; };
 229
 230   template <typename T, typename T2, typename T3, typename T4>
 231   struct gtl_and_4 { typedef typename gtl_and_3<
 232                        T, T2, typename gtl_and<T3, T4>::type>::type type; };
 233   template <typename T, typename T2>
 234   struct gtl_or { typedef gtl_yes type; };
 235   template <typename T>
 236   struct gtl_or<T, T> { typedef T type; };
 237
 238   template <typename T, typename T2, typename T3>
 239   struct gtl_or_3 { typedef typename gtl_or<
 240                       T, typename gtl_or<T2, T3>::type>::type type; };
 241
 242   template <typename T, typename T2, typename T3, typename T4>
 243   struct gtl_or_4 { typedef typename gtl_or<
 244                       T, typename gtl_or_3<T2, T3, T4>::type>::type type; };
 245
 246   template <typename T>
 247   struct gtl_not { typedef gtl_no type; };
 248   template <>
 249   struct gtl_not<gtl_no> { typedef gtl_yes type; };
 250
 251   template <typename T>
 252   struct gtl_if {
 253 #ifdef BOOST_POLYGON_MSVC
 254     typedef gtl_no type;
 255 #endif
 256   };
 257   template <>
 258   struct gtl_if<gtl_yes> { typedef gtl_yes type; };
 259
 260   template <typename T, typename T2>
 261   struct gtl_same_type { typedef gtl_no type; };
 262   template <typename T>
 263   struct gtl_same_type<T, T> { typedef gtl_yes type; };
 264   template <typename T, typename T2>
 265   struct gtl_different_type { typedef typename gtl_not<typename gtl_same_type<T, T2>::type>::type type; };
 266
 267   struct manhattan_domain {};
 268   struct forty_five_domain {};
 269   struct general_domain {};
 270
 271   template <typename T>
 272   struct geometry_domain { typedef general_domain type; };
 273
 274   template <typename domain_type, typename coordinate_type>
 275   struct area_type_by_domain { typedef typename coordinate_traits<coordinate_type>::area_type type; };
 276   template <typename coordinate_type>
 277   struct area_type_by_domain<manhattan_domain, coordinate_type> {
 278     typedef typename coordinate_traits<coordinate_type>::manhattan_area_type type; };
 279
 280   template<bool E, class R = void>
 281   struct enable_if_ {
 282       typedef R type;
 283   };
 284
 285   template<class R>
 286   struct enable_if_<false, R> { };
 287
 288   template<class E, class R = void>
 289   struct enable_if
 290       : enable_if_<E::value, R> { };
 291
 292   struct y_c_edist : gtl_yes {};
 293
 294   template <typename coordinate_type_1, typename coordinate_type_2>
 295     typename enable_if<
 296     typename gtl_and_3<y_c_edist, typename gtl_same_type<typename geometry_concept<coordinate_type_1>::type, coordinate_concept>::type,
 297                        typename gtl_same_type<typename geometry_concept<coordinate_type_1>::type, coordinate_concept>::type>::type,
 298     typename coordinate_traits<coordinate_type_1>::coordinate_difference>::type
 299   euclidean_distance(const coordinate_type_1& lvalue, const coordinate_type_2& rvalue) {
 300     typedef typename coordinate_traits<coordinate_type_1>::coordinate_difference Unit;
 301     return (lvalue < rvalue) ? (Unit)rvalue - (Unit)lvalue : (Unit)lvalue - (Unit)rvalue;
 302   }
 303
 304
 305
 306   // predicated_swap swaps a and b if pred is true
 307
 308   // predicated_swap is guarenteed to behave the same as
 309   // if(pred){
 310   //   T tmp = a;
 311   //   a = b;
 312   //   b = tmp;
 313   // }
 314   // but will not generate a branch instruction.
 315   // predicated_swap always creates a temp copy of a, but does not
 316   // create more than one temp copy of an input.
 317   // predicated_swap can be used to optimize away branch instructions in C++
 318   template <class T>
 319   inline bool predicated_swap(const bool& pred,
 320                               T& a,
 321                               T& b) {
 322     const T tmp = a;
 323     const T* input[2] = {&b, &tmp};
 324     a = *input[!pred];
 325     b = *input[pred];
 326     return pred;
 327   }
 328
 329   enum direction_1d_enum { LOW = 0, HIGH = 1,
 330                            LEFT = 0, RIGHT = 1,
 331                            CLOCKWISE = 0, COUNTERCLOCKWISE = 1,
 332                            REVERSE = 0, FORWARD = 1,
 333                            NEGATIVE = 0, POSITIVE = 1 };
 334   enum orientation_2d_enum { HORIZONTAL = 0, VERTICAL = 1 };
 335   enum direction_2d_enum { WEST = 0, EAST = 1, SOUTH = 2, NORTH = 3 };
 336   enum orientation_3d_enum { PROXIMAL = 2 };
 337   enum direction_3d_enum { DOWN = 4, UP = 5 };
 338   enum winding_direction {
 339     clockwise_winding = 0,
 340     counterclockwise_winding = 1,
 341     unknown_winding = 2
 342   };
 343
 344   class direction_2d;
 345   class direction_3d;
 346   class orientation_2d;
 347
 348   class direction_1d {
 349   private:
 350     unsigned int val_;
 351     explicit direction_1d(int d);
 352   public:
 353     inline direction_1d() : val_(LOW) {}
 354     inline direction_1d(const direction_1d& that) : val_(that.val_) {}
 355     inline direction_1d(const direction_1d_enum val) : val_(val) {}
 356     explicit inline direction_1d(const direction_2d& that);
 357     explicit inline direction_1d(const direction_3d& that);
 358     inline direction_1d& operator = (const direction_1d& d) {
 359       val_ = d.val_; return * this; }
 360     inline bool operator==(direction_1d d) const { return (val_ == d.val_); }
 361     inline bool operator!=(direction_1d d) const { return !((*this) == d); }
 362     inline unsigned int to_int(void) const { return val_; }
 363     inline direction_1d& backward() { val_ ^= 1; return *this; }
 364     inline int get_sign() const { return val_ * 2 - 1; }
 365   };
 366
 367   class direction_2d;
 368
 369   class orientation_2d {
 370   private:
 371     unsigned int val_;
 372     explicit inline orientation_2d(int o);
 373   public:
 374     inline orientation_2d() : val_(HORIZONTAL) {}
 375     inline orientation_2d(const orientation_2d& ori) : val_(ori.val_) {}
 376     inline orientation_2d(const orientation_2d_enum val) : val_(val) {}
 377     explicit inline orientation_2d(const direction_2d& that);
 378     inline orientation_2d& operator=(const orientation_2d& ori) {
 379       val_ = ori.val_; return * this; }
 380     inline bool operator==(orientation_2d that) const { return (val_ == that.val_); }
 381     inline bool operator!=(orientation_2d that) const { return (val_ != that.val_); }
 382     inline unsigned int to_int() const { return (val_); }
 383     inline void turn_90() { val_ = val_^ 1; }
 384     inline orientation_2d get_perpendicular() const {
 385       orientation_2d retval = *this;
 386       retval.turn_90();
 387       return retval;
 388     }
 389     inline direction_2d get_direction(direction_1d dir) const;
 390   };
 391
 392   class direction_2d {
 393   private:
 394     int val_;
 395
 396   public:
 397
 398     inline direction_2d() : val_(WEST) {}
 399
 400     inline direction_2d(const direction_2d& that) : val_(that.val_) {}
 401
 402     inline direction_2d(const direction_2d_enum val) : val_(val) {}
 403
 404     inline direction_2d& operator=(const direction_2d& d) {
 405       val_ = d.val_;
 406       return * this;
 407     }
 408
 409     inline ~direction_2d() { }
 410
 411     inline bool operator==(direction_2d d) const { return (val_ == d.val_); }
 412     inline bool operator!=(direction_2d d) const { return !((*this) == d); }
 413     inline bool operator< (direction_2d d) const { return (val_ < d.val_); }
 414     inline bool operator<=(direction_2d d) const { return (val_ <= d.val_); }
 415     inline bool operator> (direction_2d d) const { return (val_ > d.val_); }
 416     inline bool operator>=(direction_2d d) const { return (val_ >= d.val_); }
 417
 418     // Casting to int
 419     inline unsigned int to_int(void) const { return val_; }
 420
 421     inline direction_2d backward() const {
 422       // flip the LSB, toggles 0 - 1   and 2 - 3
 423       return direction_2d(direction_2d_enum(val_ ^ 1));
 424     }
 425
 426     // Returns a direction 90 degree left (LOW) or right(HIGH) to this one
 427     inline direction_2d turn(direction_1d t) const {
 428       return direction_2d(direction_2d_enum(val_ ^ 3 ^ (val_ >> 1) ^ t.to_int()));
 429     }
 430
 431     // Returns a direction 90 degree left to this one
 432     inline direction_2d left() const {return turn(HIGH);}
 433
 434     // Returns a direction 90 degree right to this one
 435     inline direction_2d right() const {return turn(LOW);}
 436
 437     // N, E are positive, S, W are negative
 438     inline bool is_positive() const {return (val_ & 1);}
 439     inline bool is_negative() const {return !is_positive();}
 440     inline int get_sign() const {return ((is_positive()) << 1) -1;}
 441
 442   };
 443
 444   direction_1d::direction_1d(const direction_2d& that) : val_(that.to_int() & 1) {}
 445
 446   orientation_2d::orientation_2d(const direction_2d& that) : val_(that.to_int() >> 1) {}
 447
 448   direction_2d orientation_2d::get_direction(direction_1d dir) const {
 449     return direction_2d(direction_2d_enum((val_ << 1) + dir.to_int()));
 450   }
 451
 452   class orientation_3d {
 453   private:
 454     unsigned int val_;
 455     explicit inline orientation_3d(int o);
 456   public:
 457     inline orientation_3d() : val_((int)HORIZONTAL) {}
 458     inline orientation_3d(const orientation_3d& ori) : val_(ori.val_) {}
 459     inline orientation_3d(orientation_2d ori) : val_(ori.to_int()) {}
 460     inline orientation_3d(const orientation_3d_enum val) : val_(val) {}
 461     explicit inline orientation_3d(const direction_2d& that);
 462     explicit inline orientation_3d(const direction_3d& that);
 463     inline ~orientation_3d() {  }
 464     inline orientation_3d& operator=(const orientation_3d& ori) {
 465       val_ = ori.val_; return * this; }
 466     inline bool operator==(orientation_3d that) const { return (val_ == that.val_); }
 467     inline bool operator!=(orientation_3d that) const { return (val_ != that.val_); }
 468     inline unsigned int to_int() const { return (val_); }
 469     inline direction_3d get_direction(direction_1d dir) const;
 470   };
 471
 472   class direction_3d {
 473   private:
 474     int val_;
 475
 476   public:
 477
 478     inline direction_3d() : val_(WEST) {}
 479
 480     inline direction_3d(direction_2d that) : val_(that.to_int()) {}
 481     inline direction_3d(const direction_3d& that) : val_(that.val_) {}
 482
 483     inline direction_3d(const direction_2d_enum val) : val_(val) {}
 484     inline direction_3d(const direction_3d_enum val) : val_(val) {}
 485
 486     inline direction_3d& operator=(direction_3d d) {
 487       val_ = d.val_;
 488       return * this;
 489     }
 490
 491     inline ~direction_3d() { }
 492
 493     inline bool operator==(direction_3d d) const { return (val_ == d.val_); }
 494     inline bool operator!=(direction_3d d) const { return !((*this) == d); }
 495     inline bool operator< (direction_3d d) const { return (val_ < d.val_); }
 496     inline bool operator<=(direction_3d d) const { return (val_ <= d.val_); }
 497     inline bool operator> (direction_3d d) const { return (val_ > d.val_); }
 498     inline bool operator>=(direction_3d d) const { return (val_ >= d.val_); }
 499
 500     // Casting to int
 501     inline unsigned int to_int(void) const { return val_; }
 502
 503     inline direction_3d backward() const {
 504       // flip the LSB, toggles 0 - 1   and 2 - 3 and 4 - 5
 505       return direction_2d(direction_2d_enum(val_ ^ 1));
 506     }
 507
 508     // N, E, U are positive, S, W, D are negative
 509     inline bool is_positive() const {return (val_ & 1);}
 510     inline bool is_negative() const {return !is_positive();}
 511     inline int get_sign() const {return ((is_positive()) << 1) -1;}
 512
 513   };
 514
 515   direction_1d::direction_1d(const direction_3d& that) : val_(that.to_int() & 1) {}
 516   orientation_3d::orientation_3d(const direction_3d& that) : val_(that.to_int() >> 1) {}
 517   orientation_3d::orientation_3d(const direction_2d& that) : val_(that.to_int() >> 1) {}
 518
 519   direction_3d orientation_3d::get_direction(direction_1d dir) const {
 520     return direction_3d(direction_3d_enum((val_ << 1) + dir.to_int()));
 521   }
 522
 523 }
 524 }
 525 #endif