hb-iter.hh 7.5 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
  enum { is_iter = true };
59

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

  /* Operators. */
67 68 69
  iter_t iter () const { return *thiz(); }
  explicit_operator bool () const { return thiz()->__more__ (); }
  unsigned len () const { return thiz()->__len__ (); }
70 71 72 73
  /* TODO enable_if item_t is reference type only. */
  typename hb_remove_reference (item_t)* operator -> () const { return hb_addressof (*thiz()); }
  item_t operator * () const { return thiz()->__item__ (); }
  item_t operator [] (unsigned i) const { return thiz()->__item_at__ (i); }
74 75 76 77
  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 已提交
78 79
  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 已提交
80
  iter_t operator ++ (int) { iter_t c (*thiz()); ++*thiz(); return c; }
B
Behdad Esfahbod 已提交
81
  iter_t operator - (unsigned count) const { iter_t c (*thiz()); c -= count; return c; }
B
Behdad Esfahbod 已提交
82
  iter_t operator -- (int) { iter_t c (*thiz()); --*thiz(); return c; }
83
  constexpr bool is_random_access () const { return thiz()->__random_access__ (); }
84

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

91
#define HB_ITER_USING(Name) \
92 93 94 95
  using typename Name::iter_t; \
  using typename Name::item_t; \
  using Name::item_size; \
  using Name::is_iter; \
96 97 98 99 100 101 102 103 104 105
  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 已提交
106
  using Name::operator +; \
107 108 109 110
  using Name::operator -; \
  using Name::is_random_access; \
  static_assert (true, "")

B
Behdad Esfahbod 已提交
111 112 113 114 115 116 117
/* Base class for sorted iterators.  Does not enforce anything.
 * Just for class taxonomy and requirements. */
template <typename Iter, typename Item = typename Iter::__item_type__>
struct hb_sorted_iter_t : hb_iter_t<Iter, Item>
{
  protected:
  hb_sorted_iter_t () {}
B
Behdad Esfahbod 已提交
118 119
  hb_sorted_iter_t (const hb_sorted_iter_t &o) : hb_iter_t<Iter, Item> (o) {}
  void operator = (const hb_sorted_iter_t &o HB_UNUSED) {}
B
Behdad Esfahbod 已提交
120 121
};

122 123 124 125 126 127 128 129 130
/* 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:
131

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

136
  /* Termination: Implement __more__(), or __len__() if random-access. */
137
  bool __more__ () const { return thiz()->len (); }
138 139
  unsigned __len__ () const
  { iter_t c (*thiz()); unsigned l = 0; while (c) { c++; l++; }; return l; }
140 141

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

B
Behdad Esfahbod 已提交
145
  /* Rewinding: Implement __prev__() or __rewind__() if bidirectional. */
146 147
  void __prev__ () { *thiz() -= 1; }
  void __rewind__ (unsigned n) { while (n--) --*thiz(); }
B
Behdad Esfahbod 已提交
148

149
  /* Random access: Implement if __item_at__(), __len__(), __forward__() are. */
150
  constexpr bool __random_access__ () const { return false; }
B
Behdad Esfahbod 已提交
151 152 153 154 155

  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) {}
156 157
};

B
Behdad Esfahbod 已提交
158 159 160 161
/*
 * Meta-programming predicates.
 */

162 163 164
/* hb_is_iterable() */

template<typename T, typename B>
B
Behdad Esfahbod 已提交
165 166
struct _hb_is_iterable
{ enum { value = false }; };
167
template<typename T>
168
struct _hb_is_iterable<T, hb_bool_tt<true || sizeof (Null(T).iter ())> >
B
Behdad Esfahbod 已提交
169
{ enum { value = true }; };
B
Behdad Esfahbod 已提交
170

171
template<typename T>
B
Behdad Esfahbod 已提交
172 173
struct hb_is_iterable { enum { value = _hb_is_iterable<T, hb_true_t>::value }; };
#define hb_is_iterable(Iterable) hb_is_iterable<Iterable>::value
174

B
Behdad Esfahbod 已提交
175

176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204
/* hb_is_iterator() */

/* The following SFINAE fails to match template parameters to hb_iter_t<>.
 * As such, just check for member is_iter being there. */
# if 0
template<typename T = void> char
_hb_is_iterator (T *) {};
template<typename Iter, typename Item> int
_hb_is_iterator (hb_iter_t<Iter, Item> *) {};
static_assert (sizeof (char) != sizeof (int), "");

template<typename T>
struct hb_is_iterator { enum {
  value = sizeof (int) == sizeof (_hb_is_iterator (hb_declval<T*> ()))
}; };
#endif

template<typename T, typename B>
struct _hb_is_iterator
{ enum { value = false }; };
template<typename T>
struct _hb_is_iterator<T, hb_bool_tt<true || sizeof (T::is_iter)> >
{ enum { value = true }; };

template<typename T>
struct hb_is_iterator { enum { value = _hb_is_iterator<T, hb_true_t>::value }; };
#define hb_is_iterator(Iterator) hb_is_iterator<Iterator>::value


B
Behdad Esfahbod 已提交
205 206 207
/*
 * Algorithms operating on iterators or iteratables.
 */
208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224

template <typename C, typename V> inline void
hb_fill (const C& c, const V &v)
{
  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;
}


225
#endif /* HB_ITER_HH */