include/basix/iterator.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : iterator.hpp
* DESCRIPTION: Iterators
* COPYRIGHT  : (C) 2004  Joris van der Hoeven
*******************************************************************************
* This software falls under the GNU general public license and comes WITHOUT
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
* If you don't have this file, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
******************************************************************************/

#ifndef __MMX_ITERATOR_HPP
#define __MMX_ITERATOR_HPP
#include <basix/function.hpp>


namespace mmx {
#define TMPL_DEF template<typename C>
#define TMPL template<typename C>
#define Format format<C>
#define Iterator iterator<C>
#define Iterator_rep iterator_rep<C>
TMPL class iterator;
TMPL inline bool busy (const Iterator& it);
TMPL inline bool done (const Iterator& it);
TMPL inline bool init (const Iterator& it);
TMPL inline nat  hash (const Iterator& it);
TMPL inline nat  exact_hash (const Iterator& it);
TMPL inline Iterator copy (const Iterator& it);

/******************************************************************************
* The abstract iterator class
******************************************************************************/

TMPL_DEF
class iterator_rep REP_STRUCT_1(C) {
protected:
  virtual bool is_busy () = 0;
  virtual bool is_done () { return !is_busy (); }
  virtual bool is_init () {
    ERROR ("not implemented (is_init)"); return false; }
  virtual void advance () = 0;
  virtual void regress () {
    ERROR ("not implemented (regress)"); }
  virtual C current () = 0;
  virtual Iterator_rep* clone () {
    ERROR ("not implemented (clone)"); return NULL; }

public:
  inline iterator_rep () {}
  inline iterator_rep (const Format& fm): Format (fm) {}
  virtual ~iterator_rep () {}
  friend class Iterator;
  friend bool busy LESSGTR (const Iterator& it);
  friend bool done LESSGTR (const Iterator& it);
  friend bool init LESSGTR (const Iterator& it);
  friend nat  hash LESSGTR (const Iterator& it);
  friend nat  exact_hash LESSGTR (const Iterator& it);
  friend Iterator copy LESSGTR (const Iterator& it);
};

TMPL_DEF
class iterator {
INDIRECT_PROTO_1 (iterator, iterator_rep, C)
public:
  iterator ();
  iterator (const Format& fm);
  iterator (const C& c);
  inline C operator * () const { return rep->current(); }
  const Iterator& operator ++ () const {
    /*
    if (rep->ref_count>1) {
      rep->ref_count--;
      *(const_cast<Iterator_rep**> (&rep))= rep->clone ();
    }
    */
    rep->advance(); return *this; }
  const Iterator& operator -- () const {
    /*
    if (rep->ref_count>1) {
      rep->ref_count--;
      *(const_cast<Iterator_rep**> (&rep))= rep->clone ();
    }
    */
    rep->regress(); return *this; }
  friend bool busy LESSGTR (const Iterator& it);
  friend bool done LESSGTR (const Iterator& it);
  friend bool init LESSGTR (const Iterator& it);
  friend nat  hash LESSGTR (const Iterator& it);
  friend nat  exact_hash LESSGTR (const Iterator& it);
  friend Iterator copy LESSGTR (const Iterator& it);
};
INDIRECT_IMPL_1 (iterator, iterator_rep, typename C, C)

TMPL inline bool busy (const Iterator& it) { return it.rep->is_busy (); }
TMPL inline bool done (const Iterator& it) { return it.rep->is_done (); }
TMPL inline bool init (const Iterator& it) { return it.rep->is_init (); }
TMPL inline Iterator copy (const Iterator& it) { return it.rep->clone (); }
TMPL inline Format CF (const Iterator& it) { return it->tfm (); }

/******************************************************************************
* Formatting information
******************************************************************************/

TMPL
struct format<Iterator >: public Format {
  inline format () {}
  inline format (const Format& fm): Format (fm) {}
  inline format (const format<Iterator >& fm): Format ((Format) fm) {}
};

TMPL inline format<Iterator >
get_format (const Iterator& it) {
  return format<Iterator > (CF (it));
}

TMPL inline Iterator
get_sample (const format<Iterator >& fm) {
  return Iterator ((Format) fm);
}

/******************************************************************************
* Output and equality
******************************************************************************/

TMPL syntactic
flatten (const syntactic& fun, const Iterator& it) {
  vector<syntactic> v;
  for (; busy (it); ++it)
    v << flatten (*it);
  return apply (fun, v);
}

TMPL syntactic
flatten (const Iterator& it) {
  return flatten ("iterator", it);
  // NOTE: when C involves the generic type, then traversal of the iterator
  // is a non trivial operations which may cause trouble (like in 1..10)
  // Indeed, the traveral may require operations like < on generic which
  // are not defined in the output evaluator.
  // return flatten (generic ("iterator"), it);
  // (void) it; return "iterator";
}

TMPL
struct binary_helper<Iterator >: public void_binary_helper<Iterator > {
  static inline string short_type_name () {
    return "It" * Short_type_name (C); }
  static inline generic full_type_name () {
    return gen ("Iterator", Full_type_name (C)); }
};

template<typename Op, typename C> nat
unary_hash (const Iterator& it) {
  (void) it; return 20077002;
  /*
  Iterator it1= copy (it);
  register nat h= 20077002;
  while (busy (it1)) {
    h= (h<<3) ^ (h>>29) ^ Op::op (*it1);
    ++it1;
  }
  return h;
  */
}

template<typename Op, typename C> bool
binary_test (const Iterator& it1b, const Iterator& it2b) {
  (void) it1b; (void) it2b;
  ERROR ("invalid test on iterators");
  return false;
  /*
  Iterator it1= copy (it1b), it2= copy (it2b);
  while (busy (it1) && busy (it2)) {
    if (Op::not_op (*it1, *it2)) return false;
    ++it1; ++it2;
  }
  return done (it1) && done (it2);
  */
}

HARD_TO_EXACT_IDENTITY_SUGAR(TMPL,Iterator)
HARD_TO_TRUE_IDENTITY_SUGAR(TMPL,Iterator)

//TRUE_IDENTITY_OP_SUGAR(TMPL,Iterator)
//EXACT_IDENTITY_OP_SUGAR(TMPL,Iterator)

/******************************************************************************
* Converter iterator
******************************************************************************/

template<typename C, typename S>
class as_iterator_rep: public Iterator_rep {
  iterator<S> it_S;

public:
  as_iterator_rep (const iterator<S>& it, const Format& fm):
    Iterator_rep (fm), it_S (it) {}

protected:
  inline bool is_busy () { return busy (it_S); }
  inline bool is_init () { return init (it_S); }
  inline void advance () { ++ it_S; }
  inline void regress () { -- it_S; }
  C current () { return as<C> (* it_S); }
  Iterator_rep* clone () {
    return new as_iterator_rep (it_S, (Format) *this); }
};

template<typename C, typename S>
struct as_helper<iterator<C>, iterator<S> > {
  static inline iterator<C>
  cv (const iterator<S>& it) {
    format<C> fm= as<format<C> > (CF(it));
    return Iterator (new as_iterator_rep<C,S> (it, fm)); }
};

template<typename T,typename F> inline void
set_as (iterator<T>& r, const iterator<F>& x) {
  r= iterator<T> (new as_iterator_rep<T,F> (x, CF(r)));
}

/******************************************************************************
* Finite iterators
******************************************************************************/

TMPL_DEF
class finite_iterator_rep: public Iterator_rep {
  C*  a;      // the items
  nat n;      // the number of items
  nat i;      // how many items have been processed
  nat count;  // how many times do we share a

public:
  finite_iterator_rep (C* a2, nat n2, const Format& fm):
    Iterator_rep (fm), a(a2), n(n2), i(0), count(1) {}
  finite_iterator_rep (C* a2, nat n2, nat i2, nat count2, const Format& fm):
    Iterator_rep (fm), a(a2), n(n2), i(i2), count(count2) {}
  ~finite_iterator_rep () {
    if ((--count) == 0) mmx_delete<C> (a, n); }

protected:
  bool is_busy () { return i<n; }
  bool is_init () { return i==0; }
  void advance () { i++; }
  void regress () { i--; }
  C current () { return a[i]; }
  Iterator_rep* clone () {
    return new finite_iterator_rep (a, n, i, count+1, (Format) *this); }
};

TMPL
Iterator::iterator () {
  C* a= mmx_new<C> (0);
  rep= new finite_iterator_rep<C> (a, 0, Format (no_format ()));
}

TMPL
Iterator::iterator (const Format& fm) {
  C* a= mmx_new<C> (0);
  rep= new finite_iterator_rep<C> (a, 0, fm);
}

TMPL
Iterator::iterator (const C& c) {
  C* a= mmx_new<C> (1);
  a[0]= c;
  rep= new finite_iterator_rep<C> (a, 1, get_format (c));
}

TMPL Iterator
seq (const C& c1) {
  C* a= mmx_new<C> (1);
  a[0]= c1;
  return Iterator (new finite_iterator_rep<C> (a, 1, get_format (c1)));
}

TMPL Iterator
seq (const C& c1, const C& c2) {
  C* a= mmx_new<C> (2);
  a[0]= c1; a[1]= c2;
  return Iterator (new finite_iterator_rep<C> (a, 2, get_format (c1)));
}

TMPL Iterator
seq (const C& c1, const C& c2, const C& c3) {
  C* a= mmx_new<C> (3);
  a[0]= c1; a[1]= c2; a[2]= c3;
  return Iterator (new finite_iterator_rep<C> (a, 3, get_format (c1)));
}

TMPL Iterator
seq (const C& c1, const C& c2, const C& c3,
     const C& c4)
{
  C* a= mmx_new<C> (4);
  a[0]= c1; a[1]= c2; a[2]= c3; a[3]= c4;
  return Iterator (new finite_iterator_rep<C> (a, 4, get_format (c1)));
}

TMPL Iterator
seq (const C& c1, const C& c2, const C& c3,
     const C& c4, const C& c5)
{
  C* a= mmx_new<C> (5);
  a[0]= c1; a[1]= c2; a[2]= c3; a[3]= c4; a[4]= c5;
  return Iterator (new finite_iterator_rep<C> (a, 5, get_format (c1)));
}

TMPL Iterator
seq (const C& c1, const C& c2, const C& c3,
     const C& c4, const C& c5, const C& c6)
{
  C* a= mmx_new<C> (6);
  a[0]= c1; a[1]= c2; a[2]= c3; a[3]= c4; a[4]= c5; a[5]= c6;
  return Iterator (new finite_iterator_rep<C> (a, 6, get_format (c1)));
}

/******************************************************************************
* Ranges
******************************************************************************/

TMPL_DEF
class range_iterator_rep: public Iterator_rep {
  C start, end, step, now;
  bool back, strict;

public:
  range_iterator_rep (const C& start2, const C& end2, const C& step2, bool f):
    Iterator_rep (get_format (start2)),
    start (start2), end (end2), step (step2),
    now (start), back (sign (step) < 0), strict (f) {}
  ~range_iterator_rep () {}

protected:
  bool is_busy () {
    return strict? (back? now>end: now<end): (back? now>=end: now<=end); }
  bool is_init () { return now == start; }
  void advance () { now += step; }
  void regress () { now -= step; }
  C current () { return now; }
  Iterator_rep* clone () {
    range_iterator_rep* rep= new range_iterator_rep (start, end, step, strict);
    rep->now= now;
    return rep;
  }
};

TMPL Iterator
range_iterator (const C& start, const C& end,
                const C& step= outplace_set_as<C> (1), bool strict= true)
{
  return Iterator (new range_iterator_rep<C> (start, end, step, strict));
}

template<typename S, typename T> inline iterator<S>
strict_range (const S& start, const T& end) {
  return range_iterator (start, outplace_set_as<S> (end),
                         outplace_set_as<S> (1), true);
}

template<typename S, typename T> inline iterator<S>
natural_range (const S& start, const T& end) {
  return range_iterator (start, outplace_set_as<S> (end),
                         outplace_set_as<S> (1), false);
}

template<typename S, typename T> inline iterator<S>
downwards_range (const S& start, const T& end) {
  return range_iterator (start, outplace_set_as<S> (end),
                         outplace_set_as<S> (-1), false);
}

/******************************************************************************
* Joining iterators
******************************************************************************/

TMPL_DEF
class join_iterator_rep: public Iterator_rep {
  Iterator it1, it2;

public:
  join_iterator_rep (const Iterator it1b, const Iterator it2b):
    Iterator_rep (CF (it1b)), it1(it1b), it2(it2b) {}

protected:
  bool is_busy () { return busy (it1) || busy (it2); }
  void advance () { if (busy (it1)) ++it1; else ++it2; }
  bool is_init () { return init (it1) && init (it2); }
  void regress () { if (init (it2)) --it1; else --it2; }
  C current () { return busy (it1)? *it1: *it2; }
  Iterator_rep* clone () {
    return new join_iterator_rep (copy (it1), copy (it2)); }
};

TMPL Iterator
operator * (const Iterator& it1, const Iterator& it2) {
  return Iterator (new join_iterator_rep<C> (it1, it2));
}

/******************************************************************************
* Lazy iterators
******************************************************************************/

template<typename C, typename T>
class lazy_iterator_rep: public Iterator_rep {
  T x;
  bool initialized;
  iterator<C> it;

public:
  lazy_iterator_rep (const T& x2, const Format& fm):
    Iterator_rep (fm), x (x2), initialized (false) {}
  lazy_iterator_rep (const T& x2, bool init2, const iterator<C> it2,
                     const Format& fm):
    Iterator_rep (fm), x (x2), initialized (init2), it (it2) {}
  void initialize () {
    if (initialized) return;
    initialized= true;
    it= iterate (x);
  }

protected:
  bool is_busy () { initialize (); return busy (it); }
  void advance () { initialize (); ++it; }
  bool is_init () { return !initialized; }
  void regress () { initialize (); --it; }
  C current ()    { initialize (); return *it; }
  Iterator_rep* clone () {
    return new lazy_iterator_rep (x, initialized, copy (it), (Format) *this); }
};

template<typename C, typename T> Iterator
lazy_iterator (const T& x, const Format& fm) {
  return Iterator (new lazy_iterator_rep<C,T> (x, fm));
}

/******************************************************************************
* Big operators on iterators
******************************************************************************/

template<typename Op, typename C> C
big (const Iterator& it) {
  if (done (it)) {
    C r= get_sample (CF (it));
    Op::set_neutral (r);
    return r;
  }
  C r= *it;
  for (++it; busy (it); ++it)
    Op::set_op (r, *it);
  return r;
}

TMPL inline C big_add (const Iterator& it) { return big<add_op> (it); }
TMPL inline C big_mul (const Iterator& it) { return big<mul_op> (it); }
TMPL inline C big_or  (const Iterator& it) { return big<or_op > (it); }
TMPL inline C big_and (const Iterator& it) { return big<and_op> (it); }
TMPL inline C big_min (const Iterator& it) { return big<min_op> (it); }
TMPL inline C big_max (const Iterator& it) { return big<max_op> (it); }

#undef TMPL_DEF
#undef TMPL
#undef Format
#undef Iterator
#undef Iterator_rep
} // namespace mmx
#endif // __MMX_ITERATOR_HPP

---