include/basix/new_table.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : new_table.hpp
* DESCRIPTION: New implementation of hash tables
* COPYRIGHT  : (C) 2012  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_NEW_TABLE_HPP
#define __MMX_NEW_TABLE_HPP
#include <basix/list.hpp>
#include <basix/pair.hpp>
#include <basix/vector.hpp>
#include <basix/triple.hpp>
#include <basix/table.hpp>


namespace mmx {
#define table new_table
#define table_rep new_table_rep
#define entries_iterator_rep new_entries_iterator_rep
#define table_iterator_rep new_table_iterator_rep
#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>
#define Triple triple<nat,T,C>
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);

/******************************************************************************
* Utilities
******************************************************************************/

const nat hibit_mask= ((nat) 1) << 31;

template<typename T> inline T*
mmx_new_uninitialized (nat i) {
  return (T*) ((void*) mmx_new<char> (i * sizeof (T)));
}

template<typename T> inline void
mmx_delete_uninitialized (T* mem, nat i) {
  mmx_delete<char> ((char*) ((void*) mem), i * sizeof (T));
}

template<typename T> inline T*
mmx_new_at (T* pos) {
  return new ((void*) pos) T;
}

template<typename T> inline void
mmx_delete_at (T* pos) {
  pos -> ~T ();
}

/******************************************************************************
* 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)
  nat     mask;             // n - 1
  C*      init;             // default entry
  Triple* 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), mask (n2-1),
    init (NULL),
    a (mmx_new_uninitialized<Triple > (n))
  {
    for (nat i=0; i<n; i++) a[i].x1= 0;
    //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), mask (n2-1),
    init (mmx_new_one<C> (init2)),
    a (mmx_new_uninitialized<Triple > (n))
  {
    for (nat i=0; i<n; i++) a[i].x1= 0;
    //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);
    for (nat i=0; i<n; i++) {
      Triple* cur= a+i;
      if (cur->x1 != 0) mmx_delete_at (cur);
    }
    mmx_delete_uninitialized<Triple > (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;
    }
  }
  nat find (const T& x) const;
  void remove (nat addr) const;
  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 (2, Format1 (no_format ()), Format2 (no_format ()))) {}
  inline table (const Format1& fm1, const Format2& fm2):
    rep (new Table_rep (2, fm1, fm2)) {}
  template<typename K> inline table (const K& i, nat n=2):
    rep (new Table_rep (as<C> (i), n, Format2 ())) {}
  template<typename K> inline table (const K& i, const Format2& fm2, nat n=2):
    rep (new Table_rep (as<C> (i), n, fm2)) {}
  inline table (const iterator<pair<T,C> >& it):
    rep (new Table_rep (2, 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, 2, 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 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     old_n= n;
  Triple* old_a= a;

  n   = n2;
  mask= n-1;
  a   = mmx_new_uninitialized<Triple > (n);

  for (nat i=0; i<old_n; i++) {
    Triple* cur= old_a + i;
    if (cur->x1 != 0) {
      set (cur->x2)= cur->x3;
      mmx_delete_at (cur);
    }
  }

  mmx_delete_uninitialized<Triple > (old_a, old_n);
}

TMPL inline nat
Table_rep::find (const T& x) const {
  nat code= V::key_op::hash_op (x) | hibit_mask;
  nat addr= code & mask;
  while (true) {
    Triple* cur= a + addr;
    nat stamp= cur->x1;
    if (stamp == 0) return n;
    if (stamp == code && cur->x2 == x) return addr;
    addr= (addr + 1) & mask;
  }
}

TMPL inline void
Table_rep::remove (nat addr) const {
  Triple* cur= a + addr;
  nat old_addr= addr;
  Triple* old_cur= cur;
  while (true) {
    addr= (addr + 1) & mask;
    cur= a + addr;
    nat stamp= cur->x1;
    if (stamp == 0) break;
    nat item_addr= stamp & mask;
    if (((item_addr - old_addr - 1) % mask) > ((addr - old_addr) % mask)) {
      *old_cur= *cur;
      old_cur = cur;
      old_addr= addr;
    }
  }
  mmx_delete_at (old_cur);
  old_cur->x1= 0;
}

TMPL bool
Table_rep::contains (const T& x) const {
  return find (x) < n;
  /*
  nat code= V::key_op::hash_op (x) | hibit_mask;
  nat addr= code & mask;
  while (true) {
    Triple* cur= a + addr;
    nat stamp= cur->x1;
    if (stamp == 0) return false;
    if (stamp == code && cur->x2 == x) return true;
    addr= (addr + 1) & mask;
  }
  */
}

TMPL bool
Table_rep::get (const T& x, C& y) const {
  nat addr= find (x);
  if (addr >= n) return false;
  y= (a + addr)->x3;
  return true;
  /*
  nat code= V::key_op::hash_op (x) | hibit_mask;
  nat addr= code & mask;
  while (true) {
    Triple* cur= a + addr;
    nat stamp= cur->x1;
    if (stamp == 0) return false;
    if (stamp == code && cur->x2 == x) {
      y= cur->x3;
      return true;
    }
    addr= (addr + 1) & mask;
  }
  */
}

TMPL const C&
Table_rep::get (const T& x) const {
  nat addr= find (x);
  if (addr < n) return (a + addr)->x3;
  lazy_initialize ();
  return *init;
  /*
  nat code= V::key_op::hash_op (x) | hibit_mask;
  nat addr= code & mask;
  while (true) {
    Triple* cur= a + addr;
    nat stamp= cur->x1;
    if (stamp == 0) {
      lazy_initialize ();
      return *init;
    }
    if (stamp == code && cur->x2 == x) return cur->x3;
    addr= (addr + 1) & mask;
  }
  */
}

TMPL C&
Table_rep::set (const T& x) {
  if ((size<<1) >= n) {
    //mmout << "size= " << size << ", n= " << n << "\n";
    resize (n<<1);
    //mmout << "Resized\n";
  }

  nat code= V::key_op::hash_op (x) | hibit_mask;
  nat addr= code & mask;
  Triple* cur;
  nat stamp;
  while (true) {
    cur= a + addr;
    stamp= cur->x1;
    if (stamp == 0) break;
    if (stamp == code && cur->x2 == x) return cur->x3;
    addr= (addr + 1) & mask;
  }

  lazy_initialize ();
  mmx_new_at (cur);
  cur->x1= code;
  cur->x2= x;
  cur->x3= *init;
  size++;
  return cur->x3;
}

TMPL void
Table_rep::reset (const T& x) {
  nat addr= find (x);
  if (addr >= n) return;
  remove (addr);
  if ((size << 3) < n) resize (n>>1);
}

TMPL void
Table_rep::simplify () {
  lazy_initialize ();
  for (nat i=0; i<n; i++)
    if ((a + i)->x3 == *init)
      remove (i);
  while ((size << 3) < n) resize (n>>1);
}

TMPL double
Table_rep::complexity () const {
  double sum= 0.0;
  //mmout << "{";
  for (nat i=0; i<n; i++) {
    for (nat j=0; j<n; j++)
      if ((a + ((i+j) & mask))->x1 == 0) {
        sum += ((double) j) * ((double) j);
        break;
      }
    //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

protected:
  entries_iterator_rep (const Table& t2, nat i2):
    iterator_rep<T> (CF2(t2)), t(t2), i(i2) {}
  void spool () {
    while (i < t->n) {
      if ((t->a + i)->x1 != 0) break;
      i++;
    }
  }
  bool is_busy () { return i<t->n; }
  void advance () { i++; spool (); }
  T current () { return (t->a + i)->x2; }
  iterator_rep<T>* clone () { return new entries_iterator_rep (t, i); }

public:
  entries_iterator_rep (const Table& t2):
    iterator_rep<T> (CF2(t2)), t(t2), i(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

protected:
  table_iterator_rep (const Table& t2, nat i2):
    iterator_rep<pair<T,C> > (format<pair<T,C> > (CF2 (t2), CF1 (t2))),
    t(t2), i(i2) {}
  void spool () {
    while (i < t->n) {
      if ((t->a + i)->x1 != 0) break;
      i++;
    }
  }
  bool is_busy () { return i<t->n; }
  void advance () { i++; spool (); }
  pair<T,C> current () { return pair<T,C> ((t->a + i)->x2, (t->a + i)->x3); }
  iterator_rep<pair<T,C> >* clone () {
    return new table_iterator_rep (t, i); }

public:
  table_iterator_rep (const Table& t2):
    iterator_rep<pair<T,C> > (format<pair<T,C> > (CF2 (t2), CF1 (t2))),
    t(t2), i(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_new_table(T,C) table<C,T >

template<typename T, typename C> inline table<C,T>
make_mmx_new_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_new_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_new_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_new_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
#undef Triple
#undef table
#undef table_rep
#undef entries_iterator_rep
#undef table_iterator_rep
} // namespace mmx
#endif // __MMX_NEW_TABLE_HPP

---