gfx/harfbuzz/src/hb-iter.hh

   1 /*
   2  * Copyright © 2018  Google, Inc.
   3  * Copyright © 2019  Facebook, Inc.
   4  *
   5  *  This is part of HarfBuzz, a text shaping library.
   6  *
   7  * Permission is hereby granted, without written agreement and without
   8  * license or royalty fees, to use, copy, modify, and distribute this
   9  * software and its documentation for any purpose, provided that the
  10  * above copyright notice and the following two paragraphs appear in
  11  * all copies of this software.
  12  *
  13  * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
  14  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
  15  * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
  16  * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
  17  * DAMAGE.
  18  *
  19  * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
  20  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  21  * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
  22  * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
  23  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  24  *
  25  * Google Author(s): Behdad Esfahbod
  26  * Facebook Author(s): Behdad Esfahbod
  27  */
  28
  29 #ifndef HB_ITER_HH
  30 #define HB_ITER_HH
  31
  32 #include "hb.hh"
  33 #include "hb-algs.hh"
  34 #include "hb-meta.hh"
  35
  36
  37 /* Unified iterator object.
  38  *
  39  * The goal of this template is to make the same iterator interface
  40  * available to all types, and make it very easy and compact to use.
  41  * hb_iter_tator objects are small, light-weight, objects that can be
  42  * copied by value.  If the collection / object being iterated on
  43  * is writable, then the iterator returns lvalues, otherwise it
  44  * returns rvalues.
  45  *
  46  * If iterator implementation implements operator!=, then it can be
  47  * used in range-based for loop.  That already happens if the iterator
  48  * is random-access.  Otherwise, the range-based for loop incurs
  49  * one traversal to find end(), which can be avoided if written
  50  * as a while-style for loop, or if iterator implements a faster
  51  * __end__() method. */
  52
  53 /*
  54  * Base classes for iterators.
  55  */
  56
  57 /* Base class for all iterators. */
  58 template <typename iter_t, typename Item = typename iter_t::__item_t__>
  59 struct hb_iter_t
  60 {
  61   typedef Item item_t;
  62   constexpr unsigned get_item_size () const { return hb_static_size (Item); }
  63   static constexpr bool is_iterator = true;
  64   static constexpr bool is_random_access_iterator = false;
  65   static constexpr bool is_sorted_iterator = false;
  66   static constexpr bool has_fast_len = false; // Should be checked in combination with is_random_access_iterator.
  67
  68   private:
  69   /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */
  70   const iter_t* thiz () const { return static_cast<const iter_t *> (this); }
  71         iter_t* thiz ()       { return static_cast<      iter_t *> (this); }
  72   public:
  73
  74   /* Operators. */
  75   iter_t iter () const { return *thiz(); }
  76   iter_t operator + () const { return *thiz(); }
  77   iter_t _begin () const { return *thiz(); }
  78   iter_t begin () const { return _begin (); }
  79   iter_t _end () const { return thiz()->__end__ (); }
  80   iter_t end () const { return _end (); }
  81   explicit operator bool () const { return thiz()->__more__ (); }
  82   unsigned len () const { return thiz()->__len__ (); }
  83   /* The following can only be enabled if item_t is reference type.  Otherwise
  84    * it will be returning pointer to temporary rvalue. */
  85   template <typename T = item_t,
  86             hb_enable_if (std::is_reference<T>::value)>
  87   hb_remove_reference<item_t>* operator -> () const { return std::addressof (**thiz()); }
  88   item_t operator * () const { return thiz()->__item__ (); }
  89   item_t operator * () { return thiz()->__item__ (); }
  90   item_t operator [] (unsigned i) const { return thiz()->__item_at__ (i); }
  91   item_t operator [] (unsigned i) { return thiz()->__item_at__ (i); }
  92   iter_t& operator += (unsigned count) &  { thiz()->__forward__ (count); return *thiz(); }
  93   iter_t  operator += (unsigned count) && { thiz()->__forward__ (count); return *thiz(); }
  94   iter_t& operator ++ () &  { thiz()->__next__ (); return *thiz(); }
  95   iter_t  operator ++ () && { thiz()->__next__ (); return *thiz(); }
  96   iter_t& operator -= (unsigned count) &  { thiz()->__rewind__ (count); return *thiz(); }
  97   iter_t  operator -= (unsigned count) && { thiz()->__rewind__ (count); return *thiz(); }
  98   iter_t& operator -- () &  { thiz()->__prev__ (); return *thiz(); }
  99   iter_t  operator -- () && { thiz()->__prev__ (); return *thiz(); }
 100   iter_t operator + (unsigned count) const { auto c = thiz()->iter (); c += count; return c; }
 101   friend iter_t operator + (unsigned count, const iter_t &it) { return it + count; }
 102   iter_t operator ++ (int) { iter_t c (*thiz()); ++*thiz(); return c; }
 103   iter_t operator - (unsigned count) const { auto c = thiz()->iter (); c -= count; return c; }
 104   iter_t operator -- (int) { iter_t c (*thiz()); --*thiz(); return c; }
 105   template <typename T>
 106   iter_t& operator >> (T &v) &  { v = **thiz(); ++*thiz(); return *thiz(); }
 107   template <typename T>
 108   iter_t  operator >> (T &v) && { v = **thiz(); ++*thiz(); return *thiz(); }
 109   template <typename T>
 110   iter_t& operator << (const T v) &  { **thiz() = v; ++*thiz(); return *thiz(); }
 111   template <typename T>
 112   iter_t  operator << (const T v) && { **thiz() = v; ++*thiz(); return *thiz(); }
 113
 114   protected:
 115   hb_iter_t () = default;
 116   hb_iter_t (const hb_iter_t &o HB_UNUSED) = default;
 117   hb_iter_t (hb_iter_t &&o HB_UNUSED) = default;
 118   hb_iter_t& operator = (const hb_iter_t &o HB_UNUSED) = default;
 119   hb_iter_t& operator = (hb_iter_t &&o HB_UNUSED) = default;
 120 };
 121
 122 #define HB_ITER_USING(Name) \
 123   using item_t = typename Name::item_t; \
 124   using Name::_begin; \
 125   using Name::begin; \
 126   using Name::_end; \
 127   using Name::end; \
 128   using Name::get_item_size; \
 129   using Name::is_iterator; \
 130   using Name::iter; \
 131   using Name::operator bool; \
 132   using Name::len; \
 133   using Name::operator ->; \
 134   using Name::operator *; \
 135   using Name::operator []; \
 136   using Name::operator +=; \
 137   using Name::operator ++; \
 138   using Name::operator -=; \
 139   using Name::operator --; \
 140   using Name::operator +; \
 141   using Name::operator -; \
 142   using Name::operator >>; \
 143   using Name::operator <<; \
 144   static_assert (true, "")
 145
 146 /* Returns iterator / item type of a type. */
 147 template <typename Iterable>
 148 using hb_iter_type = decltype (hb_deref (hb_declval (Iterable)).iter ());
 149 template <typename Iterable>
 150 using hb_item_type = decltype (*hb_deref (hb_declval (Iterable)).iter ());
 151
 152
 153 template <typename> struct hb_array_t;
 154 template <typename> struct hb_sorted_array_t;
 155
 156 struct
 157 {
 158   template <typename T> hb_iter_type<T>
 159   operator () (T&& c) const
 160   { return hb_deref (std::forward<T> (c)).iter (); }
 161
 162   /* Specialization for C arrays. */
 163
 164   template <typename Type> inline hb_array_t<Type>
 165   operator () (Type *array, unsigned int length) const
 166   { return hb_array_t<Type> (array, length); }
 167
 168   template <typename Type, unsigned int length> hb_array_t<Type>
 169   operator () (Type (&array)[length]) const
 170   { return hb_array_t<Type> (array, length); }
 171
 172 }
 173 HB_FUNCOBJ (hb_iter);
 174 struct
 175 {
 176   template <typename T> auto
 177   impl (T&& c, hb_priority<1>) const HB_RETURN (unsigned, c.len ())
 178
 179   template <typename T> auto
 180   impl (T&& c, hb_priority<0>) const HB_RETURN (unsigned, c.len)
 181
 182   public:
 183
 184   template <typename T> auto
 185   operator () (T&& c) const HB_RETURN (unsigned, impl (std::forward<T> (c), hb_prioritize))
 186 }
 187 HB_FUNCOBJ (hb_len);
 188
 189 /* Mixin to fill in what the subclass doesn't provide. */
 190 template <typename iter_t, typename item_t = typename iter_t::__item_t__>
 191 struct hb_iter_fallback_mixin_t
 192 {
 193   private:
 194   /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */
 195   const iter_t* thiz () const { return static_cast<const iter_t *> (this); }
 196         iter_t* thiz ()       { return static_cast<      iter_t *> (this); }
 197   public:
 198
 199   /* Access: Implement __item__(), or __item_at__() if random-access. */
 200   item_t __item__ () const { return (*thiz())[0]; }
 201   item_t __item_at__ (unsigned i) const { return *(*thiz() + i); }
 202
 203   /* Termination: Implement __more__(), or __len__() if random-access. */
 204   bool __more__ () const { return bool (thiz()->len ()); }
 205   unsigned __len__ () const
 206   { iter_t c (*thiz()); unsigned l = 0; while (c) { c++; l++; } return l; }
 207
 208   /* Advancing: Implement __next__(), or __forward__() if random-access. */
 209   void __next__ () { *thiz() += 1; }
 210   void __forward__ (unsigned n) { while (*thiz() && n--) ++*thiz(); }
 211
 212   /* Rewinding: Implement __prev__() or __rewind__() if bidirectional. */
 213   void __prev__ () { *thiz() -= 1; }
 214   void __rewind__ (unsigned n) { while (*thiz() && n--) --*thiz(); }
 215
 216   /* Range-based for: Implement __end__() if can be done faster,
 217    * and operator!=. */
 218   iter_t __end__ () const
 219   {
 220     if (thiz()->is_random_access_iterator)
 221       return *thiz() + thiz()->len ();
 222     /* Above expression loops twice. Following loops once. */
 223     auto it = *thiz();
 224     while (it) ++it;
 225     return it;
 226   }
 227
 228   protected:
 229   hb_iter_fallback_mixin_t () = default;
 230   hb_iter_fallback_mixin_t (const hb_iter_fallback_mixin_t &o HB_UNUSED) = default;
 231   hb_iter_fallback_mixin_t (hb_iter_fallback_mixin_t &&o HB_UNUSED) = default;
 232   hb_iter_fallback_mixin_t& operator = (const hb_iter_fallback_mixin_t &o HB_UNUSED) = default;
 233   hb_iter_fallback_mixin_t& operator = (hb_iter_fallback_mixin_t &&o HB_UNUSED) = default;
 234 };
 235
 236 template <typename iter_t, typename item_t = typename iter_t::__item_t__>
 237 struct hb_iter_with_fallback_t :
 238   hb_iter_t<iter_t, item_t>,
 239   hb_iter_fallback_mixin_t<iter_t, item_t>
 240 {
 241   protected:
 242   hb_iter_with_fallback_t () = default;
 243   hb_iter_with_fallback_t (const hb_iter_with_fallback_t &o HB_UNUSED) = default;
 244   hb_iter_with_fallback_t (hb_iter_with_fallback_t &&o HB_UNUSED) = default;
 245   hb_iter_with_fallback_t& operator = (const hb_iter_with_fallback_t &o HB_UNUSED) = default;
 246   hb_iter_with_fallback_t& operator = (hb_iter_with_fallback_t &&o HB_UNUSED) = default;
 247 };
 248
 249 /*
 250  * Meta-programming predicates.
 251  */
 252
 253 /* hb_is_iterator() / hb_is_iterator_of() */
 254
 255 template<typename Iter, typename Item>
 256 struct hb_is_iterator_of
 257 {
 258   template <typename Item2 = Item>
 259   static hb_true_type impl (hb_priority<2>, hb_iter_t<Iter, hb_type_identity<Item2>> *);
 260   static hb_false_type impl (hb_priority<0>, const void *);
 261
 262   public:
 263   static constexpr bool value = decltype (impl (hb_prioritize, hb_declval (Iter*)))::value;
 264 };
 265 #define hb_is_iterator_of(Iter, Item) hb_is_iterator_of<Iter, Item>::value
 266 #define hb_is_iterator(Iter) hb_is_iterator_of (Iter, typename Iter::item_t)
 267 #define hb_is_sorted_iterator_of(Iter, Item) (hb_is_iterator_of<Iter, Item>::value && Iter::is_sorted_iterator)
 268 #define hb_is_sorted_iterator(Iter) hb_is_sorted_iterator_of (Iter, typename Iter::item_t)
 269
 270 /* hb_is_iterable() */
 271
 272 template <typename T>
 273 struct hb_is_iterable
 274 {
 275   private:
 276
 277   template <typename U>
 278   static auto impl (hb_priority<1>) -> decltype (hb_declval (U).iter (), hb_true_type ());
 279
 280   template <typename>
 281   static hb_false_type impl (hb_priority<0>);
 282
 283   public:
 284   static constexpr bool value = decltype (impl<T> (hb_prioritize))::value;
 285 };
 286 #define hb_is_iterable(Iterable) hb_is_iterable<Iterable>::value
 287
 288 /* hb_is_source_of() / hb_is_sink_of() */
 289
 290 template<typename Iter, typename Item>
 291 struct hb_is_source_of
 292 {
 293   private:
 294   template <typename Iter2 = Iter,
 295             hb_enable_if (hb_is_convertible (typename Iter2::item_t, hb_add_lvalue_reference<const Item>))>
 296   static hb_true_type impl (hb_priority<2>);
 297   template <typename Iter2 = Iter>
 298   static auto impl (hb_priority<1>) -> decltype (hb_declval (Iter2) >> hb_declval (Item &), hb_true_type ());
 299   static hb_false_type impl (hb_priority<0>);
 300
 301   public:
 302   static constexpr bool value = decltype (impl (hb_prioritize))::value;
 303 };
 304 #define hb_is_source_of(Iter, Item) hb_is_source_of<Iter, Item>::value
 305
 306 template<typename Iter, typename Item>
 307 struct hb_is_sink_of
 308 {
 309   private:
 310   template <typename Iter2 = Iter,
 311             hb_enable_if (hb_is_convertible (typename Iter2::item_t, hb_add_lvalue_reference<Item>))>
 312   static hb_true_type impl (hb_priority<2>);
 313   template <typename Iter2 = Iter>
 314   static auto impl (hb_priority<1>) -> decltype (hb_declval (Iter2) << hb_declval (Item), hb_true_type ());
 315   static hb_false_type impl (hb_priority<0>);
 316
 317   public:
 318   static constexpr bool value = decltype (impl (hb_prioritize))::value;
 319 };
 320 #define hb_is_sink_of(Iter, Item) hb_is_sink_of<Iter, Item>::value
 321
 322 /* This is commonly used, so define: */
 323 #define hb_is_sorted_source_of(Iter, Item) \
 324         (hb_is_source_of(Iter, Item) && Iter::is_sorted_iterator)
 325
 326
 327 /* Range-based 'for' for iterables. */
 328
 329 template <typename Iterable,
 330           hb_requires (hb_is_iterable (Iterable))>
 331 static inline auto begin (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).begin ())
 332
 333 template <typename Iterable,
 334           hb_requires (hb_is_iterable (Iterable))>
 335 static inline auto end (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).end ())
 336
 337 /* begin()/end() are NOT looked up non-ADL.  So each namespace must declare them.
 338  * Do it for namespace OT. */
 339 namespace OT {
 340
 341 template <typename Iterable,
 342           hb_requires (hb_is_iterable (Iterable))>
 343 static inline auto begin (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).begin ())
 344
 345 template <typename Iterable,
 346           hb_requires (hb_is_iterable (Iterable))>
 347 static inline auto end (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).end ())
 348
 349 }
 350
 351
 352 /*
 353  * Adaptors, combiners, etc.
 354  */
 355
 356 template <typename Lhs, typename Rhs,
 357           hb_requires (hb_is_iterator (Lhs))>
 358 static inline auto
 359 operator | (Lhs&& lhs, Rhs&& rhs) HB_AUTO_RETURN (std::forward<Rhs> (rhs) (std::forward<Lhs> (lhs)))
 360
 361 /* hb_map(), hb_filter(), hb_reduce() */
 362
 363 enum  class hb_function_sortedness_t {
 364   NOT_SORTED,
 365   RETAINS_SORTING,
 366   SORTED,
 367 };
 368
 369 template <typename Iter, typename Proj, hb_function_sortedness_t Sorted,
 370          hb_requires (hb_is_iterator (Iter))>
 371 struct hb_map_iter_t :
 372   hb_iter_t<hb_map_iter_t<Iter, Proj, Sorted>,
 373             decltype (hb_get (hb_declval (Proj), *hb_declval (Iter)))>
 374 {
 375   hb_map_iter_t (const Iter& it, Proj f_) : it (it), f (f_) {}
 376
 377   typedef decltype (hb_get (hb_declval (Proj), *hb_declval (Iter))) __item_t__;
 378   static constexpr bool is_random_access_iterator = Iter::is_random_access_iterator;
 379   static constexpr bool is_sorted_iterator =
 380     Sorted == hb_function_sortedness_t::SORTED ? true :
 381     Sorted == hb_function_sortedness_t::RETAINS_SORTING ? Iter::is_sorted_iterator :
 382     false;
 383   __item_t__ __item__ () const { return hb_get (f.get (), *it); }
 384   __item_t__ __item_at__ (unsigned i) const { return hb_get (f.get (), it[i]); }
 385   bool __more__ () const { return bool (it); }
 386   unsigned __len__ () const { return it.len (); }
 387   void __next__ () { ++it; }
 388   void __forward__ (unsigned n) { it += n; }
 389   void __prev__ () { --it; }
 390   void __rewind__ (unsigned n) { it -= n; }
 391   hb_map_iter_t __end__ () const { return hb_map_iter_t (it._end (), f); }
 392   bool operator != (const hb_map_iter_t& o) const
 393   { return it != o.it; }
 394
 395   private:
 396   Iter it;
 397   mutable hb_reference_wrapper<Proj> f;
 398 };
 399
 400 template <typename Proj, hb_function_sortedness_t Sorted>
 401 struct hb_map_iter_factory_t
 402 {
 403   hb_map_iter_factory_t (Proj f) : f (f) {}
 404
 405   template <typename Iter,
 406             hb_requires (hb_is_iterator (Iter))>
 407   hb_map_iter_t<Iter, Proj, Sorted>
 408   operator () (Iter it)
 409   { return hb_map_iter_t<Iter, Proj, Sorted> (it, f); }
 410
 411   private:
 412   Proj f;
 413 };
 414 struct
 415 {
 416   template <typename Proj>
 417   hb_map_iter_factory_t<Proj, hb_function_sortedness_t::NOT_SORTED>
 418   operator () (Proj&& f) const
 419   { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::NOT_SORTED> (f); }
 420 }
 421 HB_FUNCOBJ (hb_map);
 422 struct
 423 {
 424   template <typename Proj>
 425   hb_map_iter_factory_t<Proj, hb_function_sortedness_t::RETAINS_SORTING>
 426   operator () (Proj&& f) const
 427   { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::RETAINS_SORTING> (f); }
 428 }
 429 HB_FUNCOBJ (hb_map_retains_sorting);
 430 struct
 431 {
 432   template <typename Proj>
 433   hb_map_iter_factory_t<Proj, hb_function_sortedness_t::SORTED>
 434   operator () (Proj&& f) const
 435   { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::SORTED> (f); }
 436 }
 437 HB_FUNCOBJ (hb_map_sorted);
 438
 439 template <typename Iter, typename Pred, typename Proj,
 440          hb_requires (hb_is_iterator (Iter))>
 441 struct hb_filter_iter_t :
 442   hb_iter_with_fallback_t<hb_filter_iter_t<Iter, Pred, Proj>,
 443                           typename Iter::item_t>
 444 {
 445   hb_filter_iter_t (const Iter& it_, Pred p_, Proj f_) : it (it_), p (p_), f (f_)
 446   { while (it && !hb_has (p.get (), hb_get (f.get (), *it))) ++it; }
 447
 448   typedef typename Iter::item_t __item_t__;
 449   static constexpr bool is_sorted_iterator = Iter::is_sorted_iterator;
 450   __item_t__ __item__ () const { return *it; }
 451   bool __more__ () const { return bool (it); }
 452   void __next__ () { do ++it; while (it && !hb_has (p.get (), hb_get (f.get (), *it))); }
 453   void __prev__ () { do --it; while (it && !hb_has (p.get (), hb_get (f.get (), *it))); }
 454   hb_filter_iter_t __end__ () const { return hb_filter_iter_t (it._end (), p, f); }
 455   bool operator != (const hb_filter_iter_t& o) const
 456   { return it != o.it; }
 457
 458   private:
 459   Iter it;
 460   mutable hb_reference_wrapper<Pred> p;
 461   mutable hb_reference_wrapper<Proj> f;
 462 };
 463 template <typename Pred, typename Proj>
 464 struct hb_filter_iter_factory_t
 465 {
 466   hb_filter_iter_factory_t (Pred p, Proj f) : p (p), f (f) {}
 467
 468   template <typename Iter,
 469             hb_requires (hb_is_iterator (Iter))>
 470   hb_filter_iter_t<Iter, Pred, Proj>
 471   operator () (Iter it)
 472   { return hb_filter_iter_t<Iter, Pred, Proj> (it, p, f); }
 473
 474   private:
 475   Pred p;
 476   Proj f;
 477 };
 478 struct
 479 {
 480   template <typename Pred = decltype ((hb_identity)),
 481             typename Proj = decltype ((hb_identity))>
 482   hb_filter_iter_factory_t<Pred, Proj>
 483   operator () (Pred&& p = hb_identity, Proj&& f = hb_identity) const
 484   { return hb_filter_iter_factory_t<Pred, Proj> (p, f); }
 485 }
 486 HB_FUNCOBJ (hb_filter);
 487
 488 template <typename Redu, typename InitT>
 489 struct hb_reduce_t
 490 {
 491   hb_reduce_t (Redu r, InitT init_value) : r (r), init_value (init_value) {}
 492
 493   template <typename Iter,
 494             hb_requires (hb_is_iterator (Iter)),
 495             typename AccuT = hb_decay<decltype (hb_declval (Redu) (hb_declval (InitT), hb_declval (typename Iter::item_t)))>>
 496   AccuT
 497   operator () (Iter it)
 498   {
 499     AccuT value = init_value;
 500     for (; it; ++it)
 501       value = r (value, *it);
 502     return value;
 503   }
 504
 505   private:
 506   Redu r;
 507   InitT init_value;
 508 };
 509 struct
 510 {
 511   template <typename Redu, typename InitT>
 512   hb_reduce_t<Redu, InitT>
 513   operator () (Redu&& r, InitT init_value) const
 514   { return hb_reduce_t<Redu, InitT> (r, init_value); }
 515 }
 516 HB_FUNCOBJ (hb_reduce);
 517
 518
 519 /* hb_zip() */
 520
 521 template <typename A, typename B>
 522 struct hb_zip_iter_t :
 523   hb_iter_t<hb_zip_iter_t<A, B>,
 524             hb_pair_t<typename A::item_t, typename B::item_t>>
 525 {
 526   hb_zip_iter_t () {}
 527   hb_zip_iter_t (const A& a, const B& b) : a (a), b (b) {}
 528
 529   typedef hb_pair_t<typename A::item_t, typename B::item_t> __item_t__;
 530   static constexpr bool is_random_access_iterator =
 531     A::is_random_access_iterator &&
 532     B::is_random_access_iterator;
 533   /* Note.  The following categorization is only valid if A is strictly sorted,
 534    * ie. does NOT have duplicates.  Previously I tried to categorize sortedness
 535    * more granularly, see commits:
 536    *
 537    *   513762849a683914fc266a17ddf38f133cccf072
 538    *   4d3cf2adb669c345cc43832d11689271995e160a
 539    *
 540    * However, that was not enough, since hb_sorted_array_t, hb_sorted_vector_t,
 541    * SortedArrayOf, etc all needed to be updated to add more variants.  At that
 542    * point I saw it not worth the effort, and instead we now deem all sorted
 543    * collections as essentially strictly-sorted for the purposes of zip.
 544    *
 545    * The above assumption is not as bad as it sounds.  Our "sorted" comes with
 546    * no guarantees.  It's just a contract, put in place to help you remember,
 547    * and think about, whether an iterator you receive is expected to be
 548    * sorted or not.  As such, it's not perfect by definition, and should not
 549    * be treated so.  The inaccuracy here just errs in the direction of being
 550    * more permissive, so your code compiles instead of erring on the side of
 551    * marking your zipped iterator unsorted in which case your code won't
 552    * compile.
 553    *
 554    * This semantical limitation does NOT affect logic in any other place I
 555    * know of as of this writing.
 556    */
 557   static constexpr bool is_sorted_iterator = A::is_sorted_iterator;
 558
 559   __item_t__ __item__ () const { return __item_t__ (*a, *b); }
 560   __item_t__ __item_at__ (unsigned i) const { return __item_t__ (a[i], b[i]); }
 561   bool __more__ () const { return bool (a) && bool (b); }
 562   unsigned __len__ () const { return hb_min (a.len (), b.len ()); }
 563   void __next__ () { ++a; ++b; }
 564   void __forward__ (unsigned n) { a += n; b += n; }
 565   void __prev__ () { --a; --b; }
 566   void __rewind__ (unsigned n) { a -= n; b -= n; }
 567   hb_zip_iter_t __end__ () const { return hb_zip_iter_t (a._end (), b._end ()); }
 568   /* Note, we should stop if ANY of the iters reaches end.  As such two compare
 569    * unequal if both items are unequal, NOT if either is unequal. */
 570   bool operator != (const hb_zip_iter_t& o) const
 571   { return a != o.a && b != o.b; }
 572
 573   private:
 574   A a;
 575   B b;
 576 };
 577 struct
 578 { HB_PARTIALIZE(2);
 579   template <typename A, typename B,
 580             hb_requires (hb_is_iterable (A) && hb_is_iterable (B))>
 581   hb_zip_iter_t<hb_iter_type<A>, hb_iter_type<B>>
 582   operator () (A&& a, B&& b) const
 583   { return hb_zip_iter_t<hb_iter_type<A>, hb_iter_type<B>> (hb_iter (a), hb_iter (b)); }
 584 }
 585 HB_FUNCOBJ (hb_zip);
 586
 587 /* hb_concat() */
 588
 589 template <typename A, typename B>
 590 struct hb_concat_iter_t :
 591     hb_iter_t<hb_concat_iter_t<A, B>, typename A::item_t>
 592 {
 593   hb_concat_iter_t () {}
 594   hb_concat_iter_t (A& a, B& b) : a (a), b (b) {}
 595   hb_concat_iter_t (const A& a, const B& b) : a (a), b (b) {}
 596
 597
 598   typedef typename A::item_t __item_t__;
 599   static constexpr bool is_random_access_iterator =
 600     A::is_random_access_iterator &&
 601     B::is_random_access_iterator;
 602   static constexpr bool is_sorted_iterator = false;
 603
 604   __item_t__ __item__ () const
 605   {
 606     if (!a)
 607       return *b;
 608     return *a;
 609   }
 610
 611   __item_t__ __item_at__ (unsigned i) const
 612   {
 613     unsigned a_len = a.len ();
 614     if (i < a_len)
 615       return a[i];
 616     return b[i - a_len];
 617   }
 618
 619   bool __more__ () const { return bool (a) || bool (b); }
 620
 621   unsigned __len__ () const { return a.len () + b.len (); }
 622
 623   void __next__ ()
 624   {
 625     if (a)
 626       ++a;
 627     else
 628       ++b;
 629   }
 630
 631   void __forward__ (unsigned n)
 632   {
 633     if (!n) return;
 634     if (!is_random_access_iterator) {
 635       while (n-- && *this) {
 636         (*this)++;
 637       }
 638       return;
 639     }
 640
 641     unsigned a_len = a.len ();
 642     if (n > a_len) {
 643       n -= a_len;
 644       a.__forward__ (a_len);
 645       b.__forward__ (n);
 646     } else {
 647       a.__forward__ (n);
 648     }
 649   }
 650
 651   hb_concat_iter_t __end__ () const { return hb_concat_iter_t (a._end (), b._end ()); }
 652   bool operator != (const hb_concat_iter_t& o) const
 653   {
 654     return a != o.a
 655         || b != o.b;
 656   }
 657
 658   private:
 659   A a;
 660   B b;
 661 };
 662 struct
 663 { HB_PARTIALIZE(2);
 664   template <typename A, typename B,
 665             hb_requires (hb_is_iterable (A) && hb_is_iterable (B))>
 666   hb_concat_iter_t<hb_iter_type<A>, hb_iter_type<B>>
 667   operator () (A&& a, B&& b) const
 668   { return hb_concat_iter_t<hb_iter_type<A>, hb_iter_type<B>> (hb_iter (a), hb_iter (b)); }
 669 }
 670 HB_FUNCOBJ (hb_concat);
 671
 672 /* hb_apply() */
 673
 674 template <typename Appl>
 675 struct hb_apply_t
 676 {
 677   hb_apply_t (Appl a) : a (a) {}
 678
 679   template <typename Iter,
 680             hb_requires (hb_is_iterator (Iter))>
 681   void operator () (Iter it)
 682   {
 683     for (; it; ++it)
 684       (void) hb_invoke (a, *it);
 685   }
 686
 687   private:
 688   Appl a;
 689 };
 690 struct
 691 {
 692   template <typename Appl> hb_apply_t<Appl>
 693   operator () (Appl&& a) const
 694   { return hb_apply_t<Appl> (a); }
 695
 696   template <typename Appl> hb_apply_t<Appl&>
 697   operator () (Appl *a) const
 698   { return hb_apply_t<Appl&> (*a); }
 699 }
 700 HB_FUNCOBJ (hb_apply);
 701
 702 /* hb_range()/hb_iota()/hb_repeat() */
 703
 704 template <typename T, typename S>
 705 struct hb_range_iter_t :
 706   hb_iter_t<hb_range_iter_t<T, S>, T>
 707 {
 708   hb_range_iter_t (T start, T end_, S step) : v (start), end_ (end_for (start, end_, step)), step (step) {}
 709
 710   typedef T __item_t__;
 711   static constexpr bool is_random_access_iterator = true;
 712   static constexpr bool is_sorted_iterator = true;
 713   __item_t__ __item__ () const { return hb_ridentity (v); }
 714   __item_t__ __item_at__ (unsigned j) const { return v + j * step; }
 715   bool __more__ () const { return v != end_; }
 716   unsigned __len__ () const { return !step ? UINT_MAX : (end_ - v) / step; }
 717   void __next__ () { v += step; }
 718   void __forward__ (unsigned n) { v += n * step; }
 719   void __prev__ () { v -= step; }
 720   void __rewind__ (unsigned n) { v -= n * step; }
 721   hb_range_iter_t __end__ () const { return hb_range_iter_t (end_, end_, step); }
 722   bool operator != (const hb_range_iter_t& o) const
 723   { return v != o.v; }
 724
 725   private:
 726   static inline T end_for (T start, T end_, S step)
 727   {
 728     if (!step)
 729       return end_;
 730     auto res = (end_ - start) % step;
 731     if (!res)
 732       return end_;
 733     end_ += step - res;
 734     return end_;
 735   }
 736
 737   private:
 738   T v;
 739   T end_;
 740   S step;
 741 };
 742 struct
 743 {
 744   template <typename T = unsigned> hb_range_iter_t<T, unsigned>
 745   operator () (T end = (unsigned) -1) const
 746   { return hb_range_iter_t<T, unsigned> (0, end, 1u); }
 747
 748   template <typename T, typename S = unsigned> hb_range_iter_t<T, S>
 749   operator () (T start, T end, S step = 1u) const
 750   { return hb_range_iter_t<T, S> (start, end, step); }
 751 }
 752 HB_FUNCOBJ (hb_range);
 753
 754 template <typename T, typename S>
 755 struct hb_iota_iter_t :
 756   hb_iter_with_fallback_t<hb_iota_iter_t<T, S>, T>
 757 {
 758   hb_iota_iter_t (T start, S step) : v (start), step (step) {}
 759
 760   private:
 761
 762   template <typename S2 = S>
 763   auto
 764   inc (hb_type_identity<S2> s, hb_priority<1>)
 765     -> hb_void_t<decltype (hb_invoke (std::forward<S2> (s), hb_declval<T&> ()))>
 766   { v = hb_invoke (std::forward<S2> (s), v); }
 767
 768   void
 769   inc (S s, hb_priority<0>)
 770   { v += s; }
 771
 772   public:
 773
 774   typedef T __item_t__;
 775   static constexpr bool is_random_access_iterator = true;
 776   static constexpr bool is_sorted_iterator = true;
 777   __item_t__ __item__ () const { return hb_ridentity (v); }
 778   bool __more__ () const { return true; }
 779   unsigned __len__ () const { return UINT_MAX; }
 780   void __next__ () { inc (step, hb_prioritize); }
 781   void __prev__ () { v -= step; }
 782   hb_iota_iter_t __end__ () const { return *this; }
 783   bool operator != (const hb_iota_iter_t& o) const { return true; }
 784
 785   private:
 786   T v;
 787   S step;
 788 };
 789 struct
 790 {
 791   template <typename T = unsigned, typename S = unsigned> hb_iota_iter_t<T, S>
 792   operator () (T start = 0u, S step = 1u) const
 793   { return hb_iota_iter_t<T, S> (start, step); }
 794 }
 795 HB_FUNCOBJ (hb_iota);
 796
 797 template <typename T>
 798 struct hb_repeat_iter_t :
 799   hb_iter_t<hb_repeat_iter_t<T>, T>
 800 {
 801   hb_repeat_iter_t (T value) : v (value) {}
 802
 803   typedef T __item_t__;
 804   static constexpr bool is_random_access_iterator = true;
 805   static constexpr bool is_sorted_iterator = true;
 806   __item_t__ __item__ () const { return v; }
 807   __item_t__ __item_at__ (unsigned j) const { return v; }
 808   bool __more__ () const { return true; }
 809   unsigned __len__ () const { return UINT_MAX; }
 810   void __next__ () {}
 811   void __forward__ (unsigned) {}
 812   void __prev__ () {}
 813   void __rewind__ (unsigned) {}
 814   hb_repeat_iter_t __end__ () const { return *this; }
 815   bool operator != (const hb_repeat_iter_t& o) const { return true; }
 816
 817   private:
 818   T v;
 819 };
 820 struct
 821 {
 822   template <typename T> hb_repeat_iter_t<T>
 823   operator () (T value) const
 824   { return hb_repeat_iter_t<T> (value); }
 825 }
 826 HB_FUNCOBJ (hb_repeat);
 827
 828 /* hb_enumerate()/hb_take() */
 829
 830 struct
 831 {
 832   template <typename Iterable,
 833             typename Index = unsigned,
 834             hb_requires (hb_is_iterable (Iterable))>
 835   auto operator () (Iterable&& it, Index start = 0u) const HB_AUTO_RETURN
 836   ( hb_zip (hb_iota (start), it) )
 837 }
 838 HB_FUNCOBJ (hb_enumerate);
 839
 840 struct
 841 { HB_PARTIALIZE(2);
 842   template <typename Iterable,
 843             hb_requires (hb_is_iterable (Iterable))>
 844   auto operator () (Iterable&& it, unsigned count) const HB_AUTO_RETURN
 845   ( hb_zip (hb_range (count), it) | hb_map_retains_sorting (hb_second) )
 846
 847   /* Specialization arrays. */
 848
 849   template <typename Type> inline hb_array_t<Type>
 850   operator () (hb_array_t<Type> array, unsigned count) const
 851   { return array.sub_array (0, count); }
 852
 853   template <typename Type> inline hb_sorted_array_t<Type>
 854   operator () (hb_sorted_array_t<Type> array, unsigned count) const
 855   { return array.sub_array (0, count); }
 856 }
 857 HB_FUNCOBJ (hb_take);
 858
 859 struct
 860 { HB_PARTIALIZE(2);
 861   template <typename Iter,
 862             hb_requires (hb_is_iterator (Iter))>
 863   auto operator () (Iter it, unsigned count) const HB_AUTO_RETURN
 864   (
 865     + hb_iota (it, hb_add (count))
 866     | hb_map (hb_take (count))
 867     | hb_take ((hb_len (it) + count - 1) / count)
 868   )
 869 }
 870 HB_FUNCOBJ (hb_chop);
 871
 872 /* hb_sink() */
 873
 874 template <typename Sink>
 875 struct hb_sink_t
 876 {
 877   hb_sink_t (Sink s) : s (s) {}
 878
 879   template <typename Iter,
 880             hb_requires (hb_is_iterator (Iter))>
 881   void operator () (Iter it)
 882   {
 883     for (; it; ++it)
 884       s << *it;
 885   }
 886
 887   private:
 888   Sink s;
 889 };
 890 struct
 891 {
 892   template <typename Sink> hb_sink_t<Sink>
 893   operator () (Sink&& s) const
 894   { return hb_sink_t<Sink> (s); }
 895
 896   template <typename Sink> hb_sink_t<Sink&>
 897   operator () (Sink *s) const
 898   { return hb_sink_t<Sink&> (*s); }
 899 }
 900 HB_FUNCOBJ (hb_sink);
 901
 902 /* hb-drain: hb_sink to void / blackhole / /dev/null. */
 903
 904 struct
 905 {
 906   template <typename Iter,
 907             hb_requires (hb_is_iterator (Iter))>
 908   void operator () (Iter it) const
 909   {
 910     for (; it; ++it)
 911       (void) *it;
 912   }
 913 }
 914 HB_FUNCOBJ (hb_drain);
 915
 916 /* hb_unzip(): unzip and sink to two sinks. */
 917
 918 template <typename Sink1, typename Sink2>
 919 struct hb_unzip_t
 920 {
 921   hb_unzip_t (Sink1 s1, Sink2 s2) : s1 (s1), s2 (s2) {}
 922
 923   template <typename Iter,
 924             hb_requires (hb_is_iterator (Iter))>
 925   void operator () (Iter it)
 926   {
 927     for (; it; ++it)
 928     {
 929       const auto &v = *it;
 930       s1 << v.first;
 931       s2 << v.second;
 932     }
 933   }
 934
 935   private:
 936   Sink1 s1;
 937   Sink2 s2;
 938 };
 939 struct
 940 {
 941   template <typename Sink1, typename Sink2> hb_unzip_t<Sink1, Sink2>
 942   operator () (Sink1&& s1, Sink2&& s2) const
 943   { return hb_unzip_t<Sink1, Sink2> (s1, s2); }
 944
 945   template <typename Sink1, typename Sink2> hb_unzip_t<Sink1&, Sink2&>
 946   operator () (Sink1 *s1, Sink2 *s2) const
 947   { return hb_unzip_t<Sink1&, Sink2&> (*s1, *s2); }
 948 }
 949 HB_FUNCOBJ (hb_unzip);
 950
 951
 952 /* hb-all, hb-any, hb-none. */
 953
 954 struct
 955 {
 956   template <typename Iterable,
 957             typename Pred = decltype ((hb_identity)),
 958             typename Proj = decltype ((hb_identity)),
 959             hb_requires (hb_is_iterable (Iterable))>
 960   bool operator () (Iterable&& c,
 961                     Pred&& p = hb_identity,
 962                     Proj&& f = hb_identity) const
 963   {
 964     for (auto it = hb_iter (c); it; ++it)
 965       if (!hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it)))
 966         return false;
 967     return true;
 968   }
 969 }
 970 HB_FUNCOBJ (hb_all);
 971 struct
 972 {
 973   template <typename Iterable,
 974             typename Pred = decltype ((hb_identity)),
 975             typename Proj = decltype ((hb_identity)),
 976             hb_requires (hb_is_iterable (Iterable))>
 977   bool operator () (Iterable&& c,
 978                     Pred&& p = hb_identity,
 979                     Proj&& f = hb_identity) const
 980   {
 981     for (auto it = hb_iter (c); it; ++it)
 982       if (hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it)))
 983         return true;
 984     return false;
 985   }
 986 }
 987 HB_FUNCOBJ (hb_any);
 988 struct
 989 {
 990   template <typename Iterable,
 991             typename Pred = decltype ((hb_identity)),
 992             typename Proj = decltype ((hb_identity)),
 993             hb_requires (hb_is_iterable (Iterable))>
 994   bool operator () (Iterable&& c,
 995                     Pred&& p = hb_identity,
 996                     Proj&& f = hb_identity) const
 997   {
 998     for (auto it = hb_iter (c); it; ++it)
 999       if (hb_match (std::forward<Pred> (p), hb_get (std::forward<Proj> (f), *it)))
1000         return false;
1001     return true;
1002   }
1003 }
1004 HB_FUNCOBJ (hb_none);
1005
1006 /*
1007  * Algorithms operating on iterators.
1008  */
1009
1010 template <typename C, typename V,
1011           hb_requires (hb_is_iterable (C))>
1012 inline void
1013 hb_fill (C&& c, const V &v)
1014 {
1015   for (auto i = hb_iter (c); i; i++)
1016     *i = v;
1017 }
1018
1019 template <typename S, typename D>
1020 inline void
1021 hb_copy (S&& is, D&& id)
1022 {
1023   hb_iter (is) | hb_sink (id);
1024 }
1025
1026
1027 #endif /* HB_ITER_HH */