include/basix/table.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : table.hpp
* DESCRIPTION: Hash tables
* 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_TABLE_HPP
#define __MMX_TABLE_HPP
#include <basix/list.hpp>
#include <basix/pair.hpp>
#include <basix/vector.hpp>


namespace mmx {
struct exact_eq_table;
#define TMPL_DEF template<typename C, typename T, typename V= exact_eq_table>
#define TMPL template<typename C, typename T, typename V>
#define TMPLK template<typename C, typename T, typename V, typename K>
#define Format1 format<C>
#define Format2 format<T>
#define Table table<C,T,V>
#define Table_rep table_rep<C,T,V>
#define GEN generic
#define VEC vector<generic>
#define GTAB table<C,generic>
TMPL class table_rep;
TMPL class table;
TMPL class entries_iterator_rep;
TMPL class table_iterator_rep;
TMPL inline C& I (Table& t);
TMPL inline const C& I (const Table& t);
TMPL inline const C& read_I (const Table& t);
TMPL inline nat N (const Table& t);
TMPL inline void simplify (Table& t);
TMPL bool operator == (const Table& t1, const Table& t2);

/******************************************************************************
* Different kinds of tables
******************************************************************************/

struct hard_eq_table {
  typedef hard_eq_op key_op;
  typedef equal_op val_op;
};

struct exact_eq_table {
  typedef exact_eq_op key_op;
  typedef equal_op val_op;
};

struct equal_table {
  typedef equal_op key_op;
  typedef equal_op val_op;
};

/******************************************************************************
* Table class and its representation class
******************************************************************************/

TMPL_DEF
class table_rep REP_STRUCT_2(C,T) {
  nat size;             // size of table (nr of entries)
  nat n;                // nr of keys (a power of two)
  C*  init;             // default entry
  list<pair<T,C> >* a;  // the array of entries

public:
  Table_rep (nat n2, const Format1& fm1, const Format2& fm2):
    encapsulate1<Format1 > (fm1),
    encapsulate2<Format2 > (fm2),
    size (0), n (n2),
    init (NULL),
    a (mmx_new<list<pair<T,C> > > (n))
  {
    //mmout << "[+init=" << init << "," << this
    //<< "]" << flush_now;
  }
  Table_rep (const C& init2, nat n2, const Format2& fm2):
    encapsulate1<Format1 > (get_format (init2)),
    encapsulate2<Format2 > (fm2),
    size (0), n (n2),
    init (mmx_new_one<C> (init2)),
    a (mmx_new<list<pair<T,C> > > (n))
  {
    //mmout << "[+init=" << init << "," << this
    //<< ";" << ((int*) ((void*) init))[-1]
    //<< "]" << flush_now;
  }
  ~Table_rep () {
    //mmout << "[-init=" << init << "," << this;
    //if (init != NULL)
    //mmout << ";" << ((int*) ((void*) init))[-1];
    //mmout << "]" << flush_now;
    if (init != NULL) mmx_delete_one<C> (init);
    mmx_delete<list<pair<T,C> > > (a, n); }
  inline void lazy_initialize () const {
    if (init == NULL) {
      *((C**) ((void*) &init))= mmx_new_one<C> ();
      //mmout << "[:init=" << init << "," << this
      //<< ";" << ((int*) ((void*) init))[-1]
      //<< "]" << flush_now;
    }
  }
  void resize (nat n);
  void reset (const T& x);
  bool contains (const T& x) const;
  bool get (const T& x, C& y) const;
  const C& get (const T& x) const;
  C& set (const T& x);
  void simplify ();
  double complexity () const;

  friend class Table;
  friend class entries_iterator_rep<C,T,V>;
  friend class table_iterator_rep<C,T,V>;
  friend C& I LESSGTR (Table& t);
  friend const C& I LESSGTR (const Table& t);
  friend const C& read_I LESSGTR (const Table& t);
  friend nat N LESSGTR (const Table& t);
  friend bool operator == LESSGTR (const Table& t1, const Table& t2);
};

TMPL_DEF
class table {
INDIRECT_PROTO_3 (table, table_rep, C, T, V)
  inline table ():
    rep (new Table_rep (1, Format1 (no_format ()), Format2 (no_format ()))) {}
  inline table (const Format1& fm1, const Format2& fm2):
    rep (new Table_rep (1, fm1, fm2)) {}
  template<typename K> inline table (const K& i, nat n=1):
    rep (new Table_rep (as<C> (i), n, Format2 ())) {}
  template<typename K> inline table (const K& i, const Format2& fm2, nat n=1):
    rep (new Table_rep (as<C> (i), n, fm2)) {}
  inline table (const iterator<pair<T,C> >& it):
    rep (new Table_rep (1, CF(it).format1 (), CF(it).format2 ())) {
      for (; busy (it); ++it) rep->set ((*it).x1)= (*it).x2; }
  inline table (const C& i, const iterator<pair<T,C> >& it):
    rep (new Table_rep (i, 1, CF(it).format2 ())) {
      for (; busy (it); ++it) rep->set ((*it).x1)= (*it).x2; }
  template<typename K> inline const C& operator [] (const K& x) const {
    return rep->get (as<T> (x)); }
  inline const C& operator [] (const T& x) const {
    return rep->get (x); }
  template<typename K> inline C& operator [] (const K& x) {
    secure (); return rep->set (as<T> (x)); }
  inline C& operator [] (const T& x) {
    secure (); return rep->set (x); }
  friend void simplify LESSGTR (Table& t);
};
INDIRECT_IMPL_3 (table, table_rep, typename C, C, typename T, T, typename V, V)
DEFINE_BINARY_FORMAT_3 (table)

STYPE_TO_TYPE(TMPL,scalar_type,Table,C);

TMPL inline Format1 CF1 (const Table& t) { return t->tfm1 (); }
TMPL inline Format2 CF2 (const Table& t) { return t->tfm2 (); }

TMPLK inline const C& read (const Table& t, const K& x) {
  return t[as<T> (x)]; }
TMPLK inline void reset (Table& t, const K& x) {
  t.secure(); inside (t) -> reset (as<T> (x)); }
TMPLK inline bool contains (const Table& t, const K& x) {
  return t->contains (as<T> (x)); }
TMPLK inline void inside_set (const Table& t, const K& x, const C& v) {
  inside (t) -> set (as<T> (x)) = v; }

TMPL inline void simplify (Table& t) {
  t.secure(); t.rep->simplify (); }
TMPL inline const C& read (const Table& t, const T& x) {
  return t[x]; }
TMPL inline void reset (Table& t, const T& x) {
  t.secure(); inside (t) -> reset (x); }
TMPL inline bool contains (const Table& t, const T& x) {
  return t->contains (x); }
TMPL inline void inside_set (const Table& t, const T& x, const C& v) {
  inside (t) -> set (x) = v; }

TMPL inline double complexity (const Table& t) {
  return t->complexity (); }
TMPL inline nat discrete_complexity (const Table& t) {
  return (nat) t->complexity (); }

TMPL struct species_type_information<Table > {
  static const nat id= SPECIES_TABLE; };

template<typename D, typename C, typename T>
struct as_helper<table<D,T>,table<C,T> > {
  static inline table<D,T>
  cv (const table<C,T>& t) {
    table<D,T> r (as<D> (I (t)), CF2(t));
    for (iterator<T> it= entries (t); busy (it); ++it)
      r[*it]= as<D> (t[*it]);
    return r;
  }
};

/******************************************************************************
* Basic access routines for tables
******************************************************************************/

TMPL inline C&
I (Table& t) {
  t->lazy_initialize ();
  return *t->init;
}

TMPL inline const C&
I (const Table& t) {
  t->lazy_initialize ();
  return *t->init;
}

TMPL inline const C&
read_I (const Table& t) {
  t->lazy_initialize ();
  return *t->init;
}

TMPL inline nat
N (const Table& t) {
  return t->size;
}

TMPL void
Table_rep::resize (nat n2) {
  nat i, oldn= n;
  list<pair<T,C> >* olda= a;
  n= n2;
  a= mmx_new<list<pair<T,C> > > (n);
  for (i=0; i<oldn; i++) {
    list<pair<T,C> > l (olda [i]);
    while (!is_nil (l)) {
      nat code= V::key_op::hash_op (read_car(l).x1);
      list<pair<T,C> >& newl= a [code & (n-1)];
      newl= cons (read_car (l), newl);
      l= read_cdr (l);
    }
  }
  mmx_delete<list<pair<T,C> > > (olda, oldn);
  //double acc= 0.0;
  //for (i=0; i<n; i++)
  //acc += N(a[i]) * N(a[i]);
  //mmout << "Access ratio: " << (acc/n) << " out of " << n << "\n";
}

TMPL bool
Table_rep::contains (const T& x) const {
  list<pair<T,C> >  l (a [V::key_op::hash_op (x) & (n-1)]);
  while (!is_nil (l)) {
    if (V::key_op::op (read_car (l).x1, x)) return true;
    l= read_cdr (l);
  }
  return false;
}

TMPL bool
Table_rep::get (const T& x, C& y) const {
  list<pair<T,C> >  l (a [V::key_op::hash_op (x) & (n-1)]);
  while (!is_nil (l)) {
    if (V::key_op::op (read_car (l).x1, x)) {
      y= read_car (l).x2;
      return true;
    }
    l= read_cdr (l);
  }
  return false;
}

TMPL C&
Table_rep::set (const T& x) {
  register nat hv= V::key_op::hash_op (x);
  list<pair<T,C> >* l= &(a [hv & (n-1)]);
  while (!is_nil (*l)) {
    if (V::key_op::op (read_car (*l).x1, x))
      return car (*l).x2;
    l= &cdr (*l);
  }
  //mmout << "size= " << size << ", n= " << n << "\n";
  if (size>=n) resize (n<<1);
  //mmout << "Resized\n";
  lazy_initialize ();
  l= &a [hv & (n-1)];
  *l= cons (pair<T,C> (x, *init), *l);
  size ++;
  return car (*l).x2;
}

TMPL const C&
Table_rep::get (const T& x) const {
  list<pair<T,C> > l (a [V::key_op::hash_op (x) & (n-1)]);
  while (!is_nil (l)) {
    if (V::key_op::op (read_car (l).x1, x)) return read_car (l).x2;
    l= read_cdr (l);
  }
  lazy_initialize ();
  return *init;
}

TMPL void
Table_rep::reset (const T& x) {
  list<pair<T,C> > *l= &(a [V::key_op::hash_op (x) & (n-1)]);
  while (!is_nil (*l)) {
    if (V::key_op::op (read_car (*l).x1, x)) {
      *l= read_cdr (*l);
      size --;
      if (size < (n>>1)) resize (n>>1);
      return;
    }
    l= &cdr (*l);
  }
}

TMPL void
Table_rep::simplify () {
  lazy_initialize ();
  for (nat i=0; i<n; i++) {
    list<pair<T,C> > *l= &(a[i]);
    while (!is_nil (*l)) {
      if (V::val_op::op (read_car (*l).x2, *init)) {
        *l= read_cdr (*l);
        size --;
      }
      else l= &cdr (*l);
    }
  }
  while (size < (n>>1)) resize (n>>1);
}

TMPL double
Table_rep::complexity () const {
  double sum= 0.0;
  //mmout << "{";
  for (nat i=0; i<n; i++) {
    nat l= N(a[i]);
    sum += l*l;
    //mmout << " " << l;
  }
  //mmout << " }";
  return sum / n;
}

/******************************************************************************
* Iterators
******************************************************************************/

TMPL_DEF
class entries_iterator_rep: public iterator_rep<T> {
  Table t;             // the table to traverse
  nat i;               // current entry in table
  list<pair<T,C> > l;  // current list

protected:
  entries_iterator_rep (const Table& t2, nat i2, const list<pair<T,C> >& l2):
    iterator_rep<T> (CF2(t2)), t(t2), i(i2), l(l2) {}
  void spool () {
    while (is_nil (l)) {
      i++;
      if (i >= t->n) break;
      l= t->a[i];
    }
  }
  bool is_busy () { return i<t->n; }
  void advance () { l= read_cdr (l); spool (); }
  T current () { return read_car (l).x1; }
  iterator_rep<T>* clone () { return new entries_iterator_rep (t, i, l); }

public:
  entries_iterator_rep (const Table& t2):
    iterator_rep<T> (CF2(t2)), t(t2), i(0), l(t->a[0]) { spool (); }
};

TMPL iterator<T>
entries (const Table& t) {
  return iterator<T> (new entries_iterator_rep<C,T,V> (t));
}

TMPL_DEF
class table_iterator_rep: public iterator_rep<pair<T,C> > {
  Table t;             // the table to traverse
  nat i;               // current entry in table
  list<pair<T,C> > l;  // current list

protected:
  table_iterator_rep (const Table& t2, nat i2, const list<pair<T,C> >& l2):
    iterator_rep<pair<T,C> > (format<pair<T,C> > (CF2 (t2), CF1 (t2))),
    t(t2), i(i2), l(l2) {}
  void spool () {
    while (is_nil (l)) {
      i++;
      if (i >= t->n) break;
      l= t->a[i];
    }
  }
  bool is_busy () { return i<t->n; }
  void advance () { l= read_cdr (l); spool (); }
  pair<T,C> current () { return read_car (l); }
  iterator_rep<pair<T,C> >* clone () {
    return new table_iterator_rep (t, i, l); }

public:
  table_iterator_rep (const Table& t2):
    iterator_rep<pair<T,C> > (format<pair<T,C> > (CF2 (t2), CF1 (t2))),
    t(t2), i(0), l(t->a[0]) { spool (); }
};

TMPL iterator<pair<T,C> >
iterate (const Table& t) {
  return iterator<pair<T,C> > (new table_iterator_rep<C,T,V> (t));
}

/******************************************************************************
* Printing tables
******************************************************************************/

TMPL syntactic
flatten (const Table& t) {
  vector<syntactic> v;
  for (iterator<pair<T,C> > it= iterate (t); busy (it); ++it)
    v << apply ("~>", flatten ((*it).x1), flatten ((*it).x2));
  return apply ("table", v);
}

TMPL
struct binary_helper<Table >: public void_binary_helper<Table > {
  static inline string short_type_name () {
    return "T" * Short_type_name (C) * Short_type_name (T); }
  static inline generic full_type_name () {
    return gen ("Table", Full_type_name (T), Full_type_name (C)); }
  static inline generic disassemble (const Table& t) {
    vector<generic> v;
    v << as<generic> (I(t));
    for (iterator<pair<T,C> > it= iterate (t); busy (it); ++it)
      v << as<generic> (*it);
    return as<generic> (v); }
  static inline Table assemble (const generic& x) {
    vector<generic> v= as<vector<generic> > (x);
    Table t (as<C> (v[0]));
    for (nat i=1; i<N(v); i++) {
      pair<T,C> p= as<pair<T,C> > (v[i]);
      t[p.x1]= p.x2;
    }
    return t; }
  static inline void write (const port& out, const Table& t) {
    binary_write<C> (out, I (t));
    binary_write<Format2 > (out, CF2(t));
    binary_write<nat> (out, N (t));
    for (iterator<T> it= entries (t); busy (it); ++it) {
      binary_write<T> (out, *it);
      binary_write<C> (out, t[*it]); } }
  static inline Table read (const port& in) {
    C init= binary_read<C> (in);
    Format2 fm2= binary_read<Format2 > (in);
    Table t (init, fm2);
    nat n= binary_read<nat> (in);
    for (nat i=0; i<n; i++) {
      T key= binary_read<T> (in);
      t[key]= binary_read<C> (in);
    }
    return t; }
};

/******************************************************************************
* Abstract operations on tables
******************************************************************************/

template<typename Op, typename C, typename T, typename V> nat
unary_hash (const Table& t) {
  // we add all hash codes of the element pairs; don't "cycle",
  // because the order of the element pairs is not uniquely determined
  nat h=54321;
  for (iterator<pair<T,C> > it= iterate (t); busy (it); ++it) {
    pair<T,C> p= *it;
    nat key_h= V::key_op::hash_op (p.x1);
    nat val_h= Op::op (p.x2);
    h += (key_h << 5) ^ (key_h >> 27) ^ val_h;
  }
  return h;
}

TMPL Table
copy (const Table& t) {
  Table r (I(t), CF2(t));
  for (iterator<T> it= entries (t); busy (it); ++it)
    r[*it]= t[*it];
  return r;
}

template<typename Op, typename C, typename T, typename V> Table
unary_map (const Table& t) {
  Table r (Op::op (I(t)), CF2(t));
  for (iterator<T> it= entries (t); busy (it); ++it)
    r[*it]= Op::op (t[*it]);
  simplify (r);
  return r;
}

template<typename Op, typename C, typename T, typename V> Table
binary_map (const Table& t, const Table& u) {
  Table r (Op::op (I(t), I(u)), CF2(t));
  for (iterator<T> it= entries (t); busy (it); ++it)
    r[*it]= Op::op (t[*it], u[*it]);
  for (iterator<T> it= entries (u); busy (it); ++it)
    if (!(t->contains (*it)))
      r[*it]= Op::op (t[*it], u[*it]);
  simplify (r);
  return r;
}

template<typename Op, typename C, typename T, typename V, typename X> Table
binary_map_scalar (const Table& t, const X& x) {
  Table r (Op::op (I(t), x), CF2(t));
  for (iterator<T> it= entries (t); busy (it); ++it)
    r[*it]= Op::op (t[*it], x);
  simplify (r);
  return r;
}

template<typename Op, typename C, typename T, typename V> Table&
unary_set (Table& t, const Table& u) {
  Op::set_op (I(t), I(u));
  for (iterator<T> it= entries (u); busy (it); ++it) {
    Op::set_op (t[*it], u[*it]);
    if (V::val_op::op (read (t, *it), read_I (t))) reset (t, *it);
  }
  return t;
}

template<typename Op, typename C, typename T, typename V, typename X> Table&
unary_set_scalar (Table& t, const X& x) {
  Op::set_op (I (t), x);
  for (iterator<T> it= entries (t); busy (it); ++it)
    Op::set_op (t[*it], x);
  simplify (t);
  return t;
}

template<typename Op, typename C, typename T, typename V> bool
binary_test (const Table& t, const Table& u) {
  if (Op::not_op (I(t), I(u))) return false;
  for (iterator<T> it= entries (t); busy (it); ++it)
    if (Op::not_op (t[*it], u[*it])) return false;
  for (iterator<T> it= entries (u); busy (it); ++it)
    if (!t->contains (*it) && Op::not_op (t[*it], u[*it])) return false;
  return true;
}

template<typename Op, typename C, typename T, typename V, typename X> bool
binary_test_scalar (const Table& t, const X& c) {
  if (Op::not_op (I(t), c)) return false;
  for (iterator<T> it= entries (t); busy (it); ++it)
    if (Op::not_op (t[*it], c)) return false;
  return true;
}

template<typename Op, typename C, typename T, typename V> inline C
big (const Table& t) {
  iterator<T> it= entries (t);
  if (done (it)) return Op::template neutral<C> ();
  C r= t[*it];
  for (++it; busy (it); ++it)
    Op::set_op (r, t[*it]);
  return r;
}

template<typename Op, typename C, typename T, typename V> Table
binary_combine (const Table& t, const Table& u) {
  Table r (Op::template neutral<C> ());
  for (iterator<T> it1= entries (t); busy (it1); ++it1)
    for (iterator<T> it2= entries (u); busy (it2); ++it2)
      Op::set_op (r[Op::rhs_op::op (*it1, *it2)], t[*it1], u[*it2]);
  simplify (r);
  return r;
}

template<typename Op, typename C, typename T, typename V> Table
unary_filter (const Table& t) {
  Table r (I(t));
  for (iterator<T> it= entries (t); busy (it); ++it)
    if (Op::op (*it)) r[*it]= t[*it];
  return r;
}

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

template<typename T1, typename C1, typename T2, typename C2,
         typename Fun1, typename Fun2> table<C2,T2>
map (const Fun1& funT, const Fun2& funC,
     const table<C1,T1>& t,
     const format<T2>& fmT, const format<C2>& fmC)
{
  table<C2,T2> r (funC (I(t)), fmT);
  for (iterator<T1> it= entries (t); busy (it); ++it)
    r[funT(*it)]= funC (t[*it]);
  simplify (r);
  return r;
}

/******************************************************************************
* Instantiations of the abstract routines
******************************************************************************/

TMPL inline Table duplicate (const Table& t) {
  return unary_map<duplicate_op,C,T,V> (t); }
TMPL inline Table operator - (const Table& t) {
  return unary_map<neg_op,C,T,V> (t); }
TMPL inline Table operator + (const Table& t, const Table& u) {
  return binary_map<add_op,C,T,V> (t, u); }
TMPL inline Table operator + (const Table& t, const C& u) {
  return binary_map<add_op,C,T,V> (t, Table (u)); }
TMPL inline Table operator + (const C& t, const Table& u) {
  return binary_map<add_op,C,T,V> (Table (t), u); }
TMPL inline Table operator - (const Table& t, const Table& u) {
  return binary_map<sub_op,C,T,V> (t, u); }
TMPL inline Table operator - (const Table& t, const C& u) {
  return binary_map<sub_op,C,T,V> (t, Table (u)); }
TMPL inline Table operator - (const C& t, const Table& u) {
  return binary_map<sub_op,C,T,V> (Table (t), u); }
TMPL inline Table operator * (const Table& t, const Table& u) {
  return binary_map<mul_op,C,T,V> (t, u); }
TMPL inline Table operator / (const Table& t, const Table& u) {
  return binary_map<div_op,C,T,V> (t, u); }
TMPL inline Table quo (const Table& t, const Table& u) {
  return binary_map<quo_op,C,T,V> (t, u); }
TMPL inline Table rem (const Table& t, const Table& u) {
  return binary_map<rem_op,C,T,V> (t, u); }
TMPL inline Table operator | (const Table& t, const Table& u) {
  return binary_map<or_op,C,T,V> (t, u); }
TMPL inline Table operator & (const Table& t, const Table& u) {
  return binary_map<and_op,C,T,V> (t, u); }
TMPL inline Table inf (const Table& t, const Table& u) {
  return binary_map<inf_op,C,T,V> (t, u); }
TMPL inline Table sup (const Table& t, const Table& u) {
  return binary_map<sup_op,C,T,V> (t, u); }
template<typename C, typename T, typename V, typename K> inline Table
operator * (const Table& t, const K& sc) {
  return binary_map_scalar<rmul_op> (t, sc); }
template<typename C, typename T, typename V, typename K> inline Table
operator * (const K& sc, const Table& t) {
  return binary_map_scalar<lmul_op> (t, sc); }
template<typename C, typename T, typename V, typename K> inline Table
operator / (const Table& t, const K& sc) {
  return binary_map_scalar<rdiv_op> (t, sc); }
template<typename C, typename T, typename V, typename K> inline Table
operator / (const K& sc, const Table& t) {
  return binary_map_scalar<ldiv_op> (t, sc); }
template<typename C, typename T, typename V, typename K> inline Table
quo (const Table& t, const K& sc) {
  return binary_map_scalar<rquo_op> (t, sc); }
template<typename C, typename T, typename V, typename K> inline Table
rem (const Table& t, const K& sc) {
  return binary_map_scalar<rrem_op> (t, sc); }
TMPL inline Table operator += (Table& t, const Table& u) {
  return unary_set<add_op,C,T,V> (t, u); }
TMPL inline Table operator -= (Table& t, const Table& u) {
  return unary_set<sub_op,C,T,V> (t, u); }
TMPL inline Table operator *= (Table& t, const Table& u) {
  return unary_set<mul_op,C,T,V> (t, u); }
TMPL inline Table operator /= (Table& t, const Table& u) {
  return unary_set<div_op,C,T,V> (t, u); }
TMPL inline Table operator |= (Table& t, const Table& u) {
  return unary_set<or_op,C,T,V> (t, u); }
TMPL inline Table operator &= (Table& t, const Table& u) {
  return unary_set<and_op,C,T,V> (t, u); }
template<typename C, typename T, typename V, typename K> inline Table&
operator *= (Table& t, const K& sc) {
  return unary_set_scalar<rmul_op> (t, sc); }
template<typename C, typename T, typename V, typename K> inline Table&
operator /= (Table& t, const K& sc) {
  return unary_set_scalar<rdiv_op> (t, sc); }
TMPL inline bool operator <= (const Table& t, const Table& u) {
  return binary_test<lesseq_op> (t, u); }
TMPL inline bool operator >= (const Table& t, const Table& u) {
  return binary_test<gtreq_op,C,T,V> (t, u); }
template<typename C, typename T, typename V, typename K> inline bool
operator == (const Table& t, const K& c) {
  return binary_test_scalar<equal_op> (t, c); }
template<typename C, typename T, typename V, typename K> inline bool
operator <= (const Table& t, const K& c) {
  return binary_test_scalar<lesseq_op> (t, c); }
template<typename C, typename T, typename V, typename K> inline bool
operator >= (const Table& t, const K& c) {
  return binary_test_scalar<gtreq_op> (t, c); }

TRUE_IDENTITY_OP_SUGAR(TMPL,Table)
EXACT_IDENTITY_OP_SUGAR(TMPL,Table)
ADDITIVE_SCALAR_INT_SUGAR(TMPL,Table)
STRICT_COMPARE_SUGAR(TMPL,Table)

TMPL Table sqrt (const Table& t) { return unary_map<sqrt_op> (t); }
TMPL Table exp (const Table& t) { return unary_map<exp_op> (t); }
TMPL Table log (const Table& t) { return unary_map<log_op> (t); }
TMPL Table cos (const Table& t) { return unary_map<cos_op> (t); }
TMPL Table sin (const Table& t) { return unary_map<sin_op> (t); }
TMPL Table tan (const Table& t) { return unary_map<tan_op> (t); }
TMPL Table acos (const Table& t) { return unary_map<acos_op> (t); }
TMPL Table asin (const Table& t) { return unary_map<asin_op> (t); }
TMPL Table atan (const Table& t) { return unary_map<atan_op> (t); }

TMPL Table pow (const Table& t, const Table& u) {
  return binary_map<pow_op> (t, u); }
TMPL Table pow (const Table& t, const int& u) {
  return binary_map_scalar<rpow_op> (t, u); }
TMPL Table pow (const int& u, const Table& t) {
  return binary_map_scalar<lpow_op> (t, u); }

TMPL inline C big_add (const Table& t) { return big<add_op> (t); }
TMPL inline C big_mul (const Table& t) { return big<mul_op> (t); }
TMPL inline C big_or  (const Table& t) { return big< or_op> (t); }
TMPL inline C big_and (const Table& t) { return big<and_op> (t); }
TMPL inline C big_min (const Table& t) { return big<min_op> (t); }
TMPL inline C big_max (const Table& t) { return big<max_op> (t); }
TMPL inline C big_inf (const Table& t) { return big<inf_op> (t); }
TMPL inline C big_sup (const Table& t) { return big<sup_op> (t); }

/******************************************************************************
* Floating point related operations
******************************************************************************/

TMPL inline bool is_finite (const Table& t) {
  return big<and_is_finite_op> (t); }
TMPL inline bool is_nan (const Table& t) {
  return big<or_is_nan_op> (t); }
TMPL inline bool is_infinite (const Table& t) {
  return !is_nan (t) && big<or_is_infinite_op> (t); }
TMPL inline bool is_fuzz (const Table& t) {
  return !is_nan (t) && big<or_is_fuzz_op> (t); }
TMPL inline bool is_reliable (const Table& t) {
  return is_reliable (C (0)); }

TMPL inline Table sharpen (const Table& t) {
  return unary_map<sharpen_op> (t); }
TMPLK inline Table blur (const Table& t, const K& x) {
  return binary_map_scalar<blur_op> (t, x); }

/******************************************************************************
* Set-like operations
******************************************************************************/

TMPL table<T,C,V>
reverse (const Table& t) {
  table<T,C,V> r (CF2 (t), CF1 (t));
  for (iterator<T> it= entries (t); busy (it); ++it)
    r[t[*it]]= *it;
  simplify (r);
  return r;
}

TMPL Table&
operator << (Table& t, const Table& u) {
  for (iterator<T> it= entries (u); busy (it); ++it)
    t[*it]= u[*it];
  return t;
}

TMPL Table
append (const Table& t, const Table& u) {
  Table r (I (u), CF2(t));
  for (iterator<T> it= entries (t); busy (it); ++it)
    r[*it]= t[*it];
  for (iterator<T> it= entries (u); busy (it); ++it)
    r[*it]= u[*it];
  return r;
}

TMPL Table
common (const Table& t, const Table& u) {
  Table r (I (t), CF2(t));
  for (iterator<T> it= entries (t); busy (it); ++it)
    if (V::val_op::op (u[*it], t[*it]))
      r[*it]= t[*it];
  return r;
}

TMPL Table
difference (const Table& t, const Table& u) {
  Table r (I (t), CF2(t));
  for (iterator<T> it= entries (t); busy (it); ++it)
    if (!V::val_op::op (u[*it], t[*it]))
      r[*it]= t[*it];
  return r;
}

/******************************************************************************
* Extras for glue
******************************************************************************/

#define mmx_table(T,C) table<C,T >

template<typename T, typename C> inline table<C,T>
make_mmx_table (const format<T>& fm1, const format<C>& fm2) {
  return table<C,T> (default_cst (fm2), fm1);
}

template<typename T, typename C> inline table<C,T>
make_mmx_table (const C& init, const format<T>& fm) {
  return table<C,T> (init, fm);
}

template<typename T, typename C> inline table<C,T>
make_mmx_table (const vector<pair<T,C> >& v) {
  return table<C,T> (default_cst (get_format2 (CF(v))), iterate (v));
}

template<typename T, typename C> inline table<C,T>
make_mmx_table (const C& init, const vector<pair<T,C> >& v) {
  return table<C,T> (init, iterate (v));
}

template<typename T, typename C> inline T
get_key (const pair<T,C>& p) { return p.x1; }

template<typename T, typename C> inline C
get_value (const pair<T,C>& p) { return p.x2; }

template<typename C> inline bool
ttable_contains (const GTAB& t, const GEN& a, const GEN& b, const VEC& c) {
  return contains (t, cons (a, cons (b, c)));
}

template<typename C> inline C
ttable_access (const GTAB& t, const GEN& a, const GEN& b, const VEC& c) {
  return t[cons (a, cons (b, c))];
}

template<typename C> inline C&
ttable_access (GTAB& t, const GEN& a, const GEN& b, const VEC& c) {
  return t[cons (a, cons (b, c))];
}

template<typename C> inline void
ttable_reset (GTAB& t, const GEN& a, const GEN& b, const VEC& c) {
  reset (t, cons (a, cons (b, c)));
}

#undef TMPL_DEF
#undef TMPL
#undef TMPLK
#undef Format1
#undef Format2
#undef Table
#undef Table_rep
#undef GEN
#undef VEC
#undef GTAB
} // namespace mmx
#endif // __MMX_TABLE_HPP

---