/Users/mourrain/Devel/mmx/basix/include/basix/chain.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : chain.hpp
* DESCRIPTION: Chains (balanced trees considered as lists)
* COPYRIGHT  : (C) 2006  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_CHAIN_HPP
#define __MMX_CHAIN_HPP
#include <basix/vector.hpp>


namespace mmx {
#define TMPL_DEF template<typename C>
#define TMPL template<typename C>
#define Format format<C>
#define Chain chain<C>
#define Chain_rep chain_rep<C>
TMPL class chain_rep;
TMPL class chain;
TMPL inline Chain left (const Chain& c);
TMPL inline C middle (const Chain& c);
TMPL inline Chain right (const Chain& c);
TMPL inline bool is_nil (const Chain& c);
TMPL inline nat N (const Chain& c);
TMPL Chain balance_left (const Chain& c);
TMPL Chain balance_right (const Chain& c);
TMPL Chain operator * (const Chain& l, const Chain& r);

/******************************************************************************
* Chain class and its representation class
******************************************************************************/

TMPL_DEF
class chain_rep REP_STRUCT {
  nat   size;
  Chain l;
  C     m;
  Chain r;
  // Invariant: #l < 2 (#r + 1) and #r < 2 (#l + 1)

public:
  inline Chain_rep (const Chain& l2, const C& m2, const Chain& r2);
  friend class Chain;
  friend Chain left LESSGTR (const Chain& c);
  friend C middle LESSGTR (const Chain& c);
  friend Chain right LESSGTR (const Chain& c);
  friend nat N LESSGTR (const Chain& c);
};

TMPL_DEF
class chain: public format<C> {
INDIRECT_PROTO_1 (chain, chain_rep, C)
public:
  inline chain ():
    Format (no_format ()),
    rep (NULL) {}
  inline chain (const C& c1):
    Format (get_format (c1)),
    rep (new Chain_rep (Chain (), c1, Chain ())) {}
  inline chain (const C& c1, const C& c2):
    Format (get_format (c1)),
    rep (new Chain_rep (Chain (c1), c2, Chain ())) {}
  inline chain (const C& c1, const C& c2, const C& c3):
    Format (get_format (c1)),
    rep (new Chain_rep (Chain (c1), c2, Chain (c3))) {}
  inline chain (const Chain& l, const C& m, const Chain& r):
    Format (get_format (m)),
    rep (new Chain_rep (l, m, r)) {}
  chain (const iterator<C>& it):
    Format (CF(it)) {
    rep= NULL;
    for (; busy (it); ++it) *this= (*this) * Chain (*it); }
  C operator [] (nat i) const {
    ASSERT (rep != NULL, "non-empty chain expected");
    if (i < N (rep->l)) return rep->l[i];
    if (i > N (rep->l)) return rep->r[i-N(rep->l)];
    return rep->m; }
  friend Chain left LESSGTR (const Chain& c);
  friend C middle LESSGTR (const Chain& c);
  friend Chain right LESSGTR (const Chain& c);
  friend bool is_nil LESSGTR (const Chain& c);
  friend nat N LESSGTR (const Chain& c);
};
DEFINE_UNARY_FORMAT_1 (chain)

TMPL inline Format CF (const Chain& l) {
  return (Format) l; }
TMPL inline Chain::chain (Chain_rep* rep2):
  Format (no_format ()), rep(rep2) {}
TMPL inline Chain::chain (const Chain_rep* rep2, bool with_inc):
  Format (no_format ()), rep((Chain_rep*) (void*) rep2) {
  (void) with_inc; INC_NULL_COUNT (rep); }
TMPL inline Chain::chain (const Chain& x):
  Format (CF(x)), rep(x.rep) {
  INC_NULL_COUNT (rep); }
TMPL inline Chain::~chain () {
  DEC_NULL_COUNT (rep); }
TMPL inline const Chain_rep* Chain::operator -> () const {
  return rep; }
TMPL inline Chain_rep* Chain::operator -> () {
  return rep; }
TMPL inline Chain& Chain::operator = (const Chain& x) {
  INC_NULL_COUNT (x.rep); DEC_NULL_COUNT (rep);
  rep=x.rep; return *this; }
TMPL inline void Chain::secure () {
  if (rep->ref_count>1) *this= copy (*this); }
TMPL Chain_rep* inside (const Chain& x) {
  return const_cast<Chain_rep*> (x.operator -> ()); }
TMPL inline nat hard_hash (const Chain& x) {
  return as_hash (x.operator -> ()); }
TMPL inline bool hard_eq (const Chain& x, const Chain& y) {
  return (x.operator -> ()) == (y.operator -> ()); }
TMPL inline bool hard_neq (const Chain& x, const Chain& y) {
  return (x.operator -> ()) != (y.operator -> ()); }

/******************************************************************************
* Basic constructors and accessors
******************************************************************************/

TMPL inline
Chain_rep::chain_rep (const Chain& l2, const C& m2, const Chain& r2):
  size (N (l2) + N (r2) + 1), l (l2), m (m2), r (r2) {}

TMPL inline Chain left (const Chain& c) { return c.rep->l; }
TMPL inline C middle (const Chain& c) { return c.rep->m; }
TMPL inline Chain right (const Chain& c) { return c.rep->r; }
TMPL inline bool is_nil (const Chain& c) { return c.rep == NULL; }
TMPL inline nat N (const Chain& c) { return (c.rep == NULL? 0: c.rep->size); }

/******************************************************************************
* Chain iteration and output
******************************************************************************/

TMPL iterator<C>
iterate (const Chain& c) {
  if (is_nil (c)) return iterator<C> ();
  return
    lazy_iterator<C,Chain > (left (c), get_format (middle (c))) *
    iterator<C> (middle (c)) *
    lazy_iterator<C,Chain > (right (c), get_format (middle (c)));
}

TMPL syntactic
flatten (const Chain& c) {
  return flatten (syntactic ("chain"), iterate (c));
}

TMPL
struct binary_helper<Chain >: public void_binary_helper<Chain > {
  static inline string short_type_name () {
    return "Ch" * Short_type_name (C); }
  static inline generic full_type_name () {
    return gen ("Chain", Full_type_name (C)); }
  static generic disassemble (const Chain& c) {
    if (N(c) == 0) return gen_vec ();
    else if (N(c) == 1) return gen_vec (as<generic> (middle (c)));
    else return gen_vec (as<generic> (left (c)),
                         as<generic> (middle (c)),
                         as<generic> (right (c))); }
  static Chain assemble (const generic& g) {
    vector<generic> v= as<vector<generic> > (g);
    if (N(v) == 0) return Chain ();
    else if (N(v) == 1) return Chain (as<C> (v[0]));
    else return Chain (as<Chain > (v[0]), as<C> (v[1]), as<Chain > (v[2])); }
  static void write_bis (const port& out, const Chain& c) {
    write_bis (out, left (c));
    binary_write<C> (out, middle (c));
    write_bis (out, right (c)); }
  static inline void write (const port& out, const Chain& c) {
    binary_write<nat> (out, N(c));
    write_bis (out, c); }
  static Chain read (const port& in, nat n) {
    if (n == 0) return Chain ();
    else if (n == 1) return Chain (binary_read<C> (in));
    else return Chain (binary_read<Chain > (in, n >> 1),
                       binary_read<C> (in),
                       binary_read<Chain > (in, (n-1) >> 1)); }
  static inline Chain read (const port& in) {
    nat n = binary_read<nat> (in);
    return read (in, n); }
};

/******************************************************************************
* Operations on chains
******************************************************************************/

TMPL Chain
copy (const Chain& c) {
  if (is_nil (c)) return c;
  return Chain (left (c), middle (c), right (c));
}

TMPL Chain
reverse (const Chain& c) {
  if (is_nil (c)) return c;
  return Chain (reverse (right (c)), middle (c), reverse (left (c)));
}

TMPL C
car (const Chain& c) {
  ASSERT (!is_nil (c), "non-empty chain expected");
  if (is_nil (left (c))) return middle (c);
  return car (left (c));
}

TMPL C
cAr (const Chain& c) {
  ASSERT (!is_nil (c), "non-empty chain expected");
  if (is_nil (right (c))) return middle (c);
  return cAr (right (c));
}

template<typename Op, typename C> nat
unary_hash (const Chain& c) {
  if (is_nil (c)) return 1928;
  nat h1= Op::op (left (c));
  nat h2= Op::op (middle (c));
  nat h3= Op::op (right (c));
  return h1 ^ (h2>>1) ^ (h2<<31) ^ (h3>>3) ^ (h3>>29);
}

template<typename Op, typename C> bool
binary_test (const Chain& c1, const Chain& c2) {
  if (N (c1) != N (c2)) return false;
  if (N (c1) == 0) return true;
  return binary_test<Op> (left (c1), left(c2)) &&
    Op::op (middle (c1), middle (c2)) &&
    binary_test<Op> (right (c1), right(c2));
}

TRUE_IDENTITY_OP_SUGAR(TMPL,Chain)
EXACT_IDENTITY_OP_SUGAR(TMPL,Chain)

/******************************************************************************
* Operations that need balancing
******************************************************************************/

TMPL Chain
shift_left (const Chain& c) {
  return Chain (Chain (left (c), middle (c), left (right (c))),
                middle (right (c)),
                right (right (c)));
}

TMPL Chain
shift_right (const Chain& c) {
  return Chain (left (left (c)),
                middle (left (c)),
                Chain (right (left (c)), middle (c), right (c)));
}

TMPL Chain
balance_left (const Chain& c) {
  // Ensure that #left(c) >= #right(c)
  switch (N(c)) {
  case 0:
  case 1:
    return c;
  case 2:
    if (is_nil (right (c))) return c;
    return Chain (Chain (middle (c)), middle (right (c)), Chain ());
  case 3:
    return c;
  default:
    if (N (left (c)) >= N (right (c))) return c;
    else {
      Chain aux= balance_right (right (c));
      return shift_left (Chain (left (c), middle (c), aux));
    }
  }
}

TMPL Chain
balance_right (const Chain& c) {
  // Ensure that #left(c) <= #right(c)
  switch (N(c)) {
  case 0:
  case 1:
    return c;
  case 2:
    if (is_nil (left (c))) return c;
    return Chain (Chain (), middle (left (c)), Chain (middle (c)));
  case 3:
    return c;
  default:
    if (N (left (c)) <= N (right (c))) return c;
    else {
      Chain aux= balance_left (left (c));
      return shift_right (Chain (aux, middle (c), right (c)));
    }
  }
}

TMPL Chain
cdr (const Chain& c) {
  ASSERT (!is_nil (c), "non-empty chain expected");
  if (N (c) == 1) return Chain ();
  if (2 * N (left (c)) <= N (right (c))) return cdr (balance_left (c));
  return Chain (cdr (left (c)), middle (c), right (c));
}

TMPL Chain
cDr (const Chain& c) {
  ASSERT (!is_nil (c), "non-empty chain expected");
  if (N (c) == 1) return Chain ();
  if (2 * N (right (c)) <= N (left (c))) return cDr (balance_right (c));
  return Chain (left (c), middle (c), cDr (right (c)));
}

TMPL Chain
operator * (const Chain& l, const Chain& r) {
  nat nl= N (l), nr= N (r);
  if (nl < nr) {
    if (nl == 0) return r;
    if (nr < 2*nl + 3) return Chain (l, car (r), cdr (r));
    Chain br= balance_right (r);
    return Chain (l * left (br), middle (br), right (br));
  }
  else {
    if (nr == 0) return l;
    if (nl < 2*nr + 3) return Chain (cDr (l), cAr (l), r);
    Chain bl= balance_left (l);
    return Chain (left (bl), middle (bl), right (bl) * r);
  }
}

TMPL Chain
range (const Chain& c, nat start, nat end) {
  if (start >= end) return Chain ();
  ASSERT (!is_nil (c), "non-empty chain expected");
  nat n= N (left (c));
  if (end <= n) return range (left (c), start, end);
  if (start > n) return range (right (c), start-n-1, end-n-1);
  Chain l= range (left (c), start, n);
  C     m= middle (c);
  Chain r= range (right (c), 0, end-n-1);
  if (N(l) < 2*(N(r) + 1) && N(r) < 2*(N(l) + 1)) return Chain (l, m, r);
  return l * Chain (m) * r;
}

/******************************************************************************
* Dynamic mappers
******************************************************************************/

template<typename S1, typename D> chain<D>
map (const function_1<D,Argument(S1) >& fun,
     const chain<S1>& c1, const format<D>& fm)
{
  if (is_nil (c1)) return chain<D> (fm);
  return chain<D> (map (fun, left (c1), fm),
                   fun (middle (c1)),
                   map (fun, right (c1), fm));
}

template<typename S1, typename D> inline chain<D>
map (D (*fun) (const S1&), const chain<S1>& x1, const format<D>& fm) {
  return map (function_1<D,Argument(S1) > (fun), x1, fm);
}

#undef TMPL_DEF
#undef TMPL
#undef Format
#undef Chain
#undef Chain_rep
} // namespace mmx
#endif // __MMX_CHAIN_HPP