hb-iter.hh 7.4 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
/*
 * Copyright © 2018  Google, Inc.
 *
 *  This is part of HarfBuzz, a text shaping library.
 *
 * Permission is hereby granted, without written agreement and without
 * license or royalty fees, to use, copy, modify, and distribute this
 * software and its documentation for any purpose, provided that the
 * above copyright notice and the following two paragraphs appear in
 * all copies of this software.
 *
 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGE.
 *
 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
 *
 * Google Author(s): Behdad Esfahbod
 */

#ifndef HB_ITER_HH
#define HB_ITER_HH

#include "hb.hh"
B
Behdad Esfahbod 已提交
31
#include "hb-dsalgs.hh" // for hb_addressof
32
#include "hb-meta.hh"
33
#include "hb-null.hh"
34 35 36 37 38 39


/* Unified iterator object.
 *
 * The goal of this template is to make the same iterator interface
 * available to all types, and make it very easy and compact to use.
40
 * hb_iter_tator objects are small, light-weight, objects that can be
41
 * copied by value.  If the collection / object being iterated on
42
 * is writable, then the iterator returns lvalues, otherwise it
43 44 45
 * returns rvalues.
 */

B
Behdad Esfahbod 已提交
46 47 48 49 50

/*
 * Base classes for iterators.
 */

51
/* Base class for all iterators. */
B
Behdad Esfahbod 已提交
52
template <typename Iter, typename Item = typename Iter::__item_type__>
53
struct hb_iter_t
54
{
B
Behdad Esfahbod 已提交
55 56
  typedef Iter iter_t;
  typedef Item item_t;
B
Behdad Esfahbod 已提交
57
  enum { item_size = hb_static_size (Item) };
58 59
  enum { is_iterator = true };
  enum { is_random_access_iterator = false };
B
Behdad Esfahbod 已提交
60
  enum { is_sorted_iterator = false };
61

62 63
  private:
  /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */
B
Behdad Esfahbod 已提交
64 65
  const iter_t* thiz () const { return static_cast<const iter_t *> (this); }
        iter_t* thiz ()       { return static_cast<      iter_t *> (this); }
66
  public:
67 68

  /* Operators. */
69 70 71
  iter_t iter () const { return *thiz(); }
  explicit_operator bool () const { return thiz()->__more__ (); }
  unsigned len () const { return thiz()->__len__ (); }
B
Behdad Esfahbod 已提交
72 73
  template <typename U = item_t, hb_enable_if (hb_is_reference (U))>
  hb_remove_reference (item_t)* operator -> () const { return hb_addressof (**thiz()); }
74 75
  item_t operator * () const { return thiz()->__item__ (); }
  item_t operator [] (unsigned i) const { return thiz()->__item_at__ (i); }
76 77 78 79
  iter_t& operator += (unsigned count) { thiz()->__forward__ (count); return *thiz(); }
  iter_t& operator ++ () { thiz()->__next__ (); return *thiz(); }
  iter_t& operator -= (unsigned count) { thiz()->__rewind__ (count); return *thiz(); }
  iter_t& operator -- () { thiz()->__prev__ (); return *thiz(); }
B
Behdad Esfahbod 已提交
80 81
  iter_t operator + (unsigned count) const { iter_t c (*thiz()); c += count; return c; }
  friend iter_t operator + (unsigned count, const iter_t &it) { return it + count; }
B
Behdad Esfahbod 已提交
82
  iter_t operator ++ (int) { iter_t c (*thiz()); ++*thiz(); return c; }
B
Behdad Esfahbod 已提交
83
  iter_t operator - (unsigned count) const { iter_t c (*thiz()); c -= count; return c; }
B
Behdad Esfahbod 已提交
84
  iter_t operator -- (int) { iter_t c (*thiz()); --*thiz(); return c; }
85

86 87
  protected:
  hb_iter_t () {}
B
Behdad Esfahbod 已提交
88 89
  hb_iter_t (const hb_iter_t &o HB_UNUSED) {}
  void operator = (const hb_iter_t &o HB_UNUSED) {}
90 91
};

92
#define HB_ITER_USING(Name) \
93 94 95
  using typename Name::iter_t; \
  using typename Name::item_t; \
  using Name::item_size; \
96
  using Name::is_iterator; \
97 98 99 100 101 102 103 104 105 106
  using Name::iter; \
  using Name::operator bool; \
  using Name::len; \
  using Name::operator ->; \
  using Name::operator *; \
  using Name::operator []; \
  using Name::operator +=; \
  using Name::operator ++; \
  using Name::operator -=; \
  using Name::operator --; \
B
Behdad Esfahbod 已提交
107
  using Name::operator +; \
108 109 110
  using Name::operator -; \
  static_assert (true, "")

111 112 113 114 115 116 117 118 119
/* Mixin to fill in what the subclass doesn't provide. */
template <typename iter_t, typename item_t = typename iter_t::__item_type__>
struct hb_iter_mixin_t
{
  private:
  /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */
  const iter_t* thiz () const { return static_cast<const iter_t *> (this); }
        iter_t* thiz ()       { return static_cast<      iter_t *> (this); }
  public:
120

B
Behdad Esfahbod 已提交
121
  /* Access: Implement __item__(), or __item_at__() if random-access. */
122 123
  item_t __item__ () const { return (*thiz())[0]; }
  item_t __item_at__ (unsigned i) const { return *(*thiz() + i); }
124

125
  /* Termination: Implement __more__(), or __len__() if random-access. */
126
  bool __more__ () const { return thiz()->len (); }
127 128
  unsigned __len__ () const
  { iter_t c (*thiz()); unsigned l = 0; while (c) { c++; l++; }; return l; }
129 130

  /* Advancing: Implement __next__(), or __forward__() if random-access. */
131 132
  void __next__ () { *thiz() += 1; }
  void __forward__ (unsigned n) { while (n--) ++*thiz(); }
133

B
Behdad Esfahbod 已提交
134
  /* Rewinding: Implement __prev__() or __rewind__() if bidirectional. */
135 136
  void __prev__ () { *thiz() -= 1; }
  void __rewind__ (unsigned n) { while (n--) --*thiz(); }
B
Behdad Esfahbod 已提交
137

B
Behdad Esfahbod 已提交
138 139 140 141
  protected:
  hb_iter_mixin_t () {}
  hb_iter_mixin_t (const hb_iter_mixin_t &o HB_UNUSED) {}
  void operator = (const hb_iter_mixin_t &o HB_UNUSED) {}
142 143
};

B
Behdad Esfahbod 已提交
144 145 146 147
/*
 * Meta-programming predicates.
 */

148 149 150
/* hb_is_iterable() */

template<typename T, typename B>
B
Behdad Esfahbod 已提交
151 152
struct _hb_is_iterable
{ enum { value = false }; };
153
template<typename T>
154
struct _hb_is_iterable<T, hb_bool_tt<true || sizeof (Null(T).iter ())> >
B
Behdad Esfahbod 已提交
155
{ enum { value = true }; };
B
Behdad Esfahbod 已提交
156

157
template<typename T>
B
Behdad Esfahbod 已提交
158 159
struct hb_is_iterable { enum { value = _hb_is_iterable<T, hb_true_t>::value }; };
#define hb_is_iterable(Iterable) hb_is_iterable<Iterable>::value
160

B
Behdad Esfahbod 已提交
161

162
/* hb_is_iterator() / hb_is_random_access_iterator() / hb_is_sorted_iterator() */
163

164
template <typename Iter>
165
struct _hb_is_iterator_of
166 167 168 169 170 171 172 173
{
  char operator () (...) { return 0; };
  template<typename Item> int operator () (hb_iter_t<Iter, Item> *) { return 0; };
  template<typename Item> int operator () (hb_iter_t<Iter, const Item> *) { return 0; };
  template<typename Item> int operator () (hb_iter_t<Iter, Item&> *) { return 0; };
  template<typename Item> int operator () (hb_iter_t<Iter, const Item&> *) { return 0; };
  static_assert (sizeof (char) != sizeof (int), "");
};
174
template<typename Iter, typename Item>
175 176 177 178
struct hb_is_iterator_of { enum {
  value = sizeof (int) == sizeof (hb_declval (_hb_is_iterator_of<Iter>) (hb_declval (Iter*))) }; };
#define hb_is_iterator_of(Iter, Item) hb_is_iterator_of<Iter, Item>::value
#define hb_is_iterator(Iter) hb_is_iterator_of (Iter, typename Iter::item_t)
179

180 181 182 183 184
#define hb_is_random_access_iterator_of(Iter, Item) \
  hb_is_iterator_of (Iter, Item) && Iter::is_random_access_iterator
#define hb_is_random_access_iterator(Iter) \
  hb_is_random_access_iterator_of (Iter, typename Iter::item_t)

185
#define hb_is_sorted_iterator_of(Iter, Item) \
186
  hb_is_iterator_of (Iter, Item) && Iter::is_sorted_iterator
187 188
#define hb_is_sorted_iterator(Iter) \
  hb_is_sorted_iterator_of (Iter, typename Iter::item_t)
189

B
Behdad Esfahbod 已提交
190 191 192
/*
 * Algorithms operating on iterators or iteratables.
 */
193 194

template <typename C, typename V> inline void
B
Behdad Esfahbod 已提交
195
hb_fill (C& c, const V &v)
196 197 198 199 200 201 202 203 204 205 206 207 208 209
{
  for (typename C::iter_t i (c); i; i++)
    hb_assign (*i, v);
}

template <typename S, typename D> inline bool
hb_copy (hb_iter_t<D> &id, hb_iter_t<S> &is)
{
  for (; id && is; ++id, ++is)
    *id = *is;
  return !is;
}


210
#endif /* HB_ITER_HH */