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