Back to index

texmacs  1.0.7.15
hashmap_extra.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : hashmap_extra.cpp
00004 * DESCRIPTION: extra routines for hashmap<string,tree>
00005 * COPYRIGHT  : (C) 1999  Joris van der Hoeven
00006 *******************************************************************************
00007 * This software falls under the GNU general public license version 3 or later.
00008 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
00009 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
00010 ******************************************************************************/
00011 
00012 #ifndef HASHMAP_EXTRA_CC
00013 #define HASHMAP_EXTRA_CC
00014 #include "hashmap.hpp"
00015 #define TMPL template<class T, class U>
00016 #define H hashentry<T,U>
00017 
00018 TMPL void
00019 hashmap_rep<T,U>::write_back (T x, hashmap<T,U> base) {
00020   register int hv= hash (x);
00021   list<hashentry<T,U> > l (a [hv & (n-1)]);
00022   while (!is_nil (l)) {
00023     if (l->item.code == hv && l->item.key == x)
00024       return;
00025     l= l->next;
00026   }
00027   if (size >= n*max) resize (n<<1);
00028   list<hashentry<T,U> >& rl= a[hv & (n-1)];
00029   rl= list<hashentry<T,U> > (H (hv, x, init), rl);
00030   size ++;
00031 
00032   list<hashentry<T,U> > bl (base->a [hv & (base->n-1)]);
00033   while (!is_nil (bl)) {
00034     if (bl->item.code == hv && bl->item.key == x) {
00035       rl->item.im= bl->item.im;
00036       return;
00037     }
00038     bl= bl->next;
00039   }
00040   rl->item.im= base->init;
00041 }
00042 
00043 TMPL void
00044 hashmap_rep<T,U>::pre_patch (hashmap<T,U> patch, hashmap<T,U> base) {
00045   int i= 0, n= patch->n;
00046   for (; i<n; i++) {
00047     list<hashentry<T,U> > l= patch->a[i];
00048     for (; !is_nil (l); l= l->next) {
00049       T x= l->item.key;
00050       U y= contains (x)? bracket_ro (x): l->item.im;
00051       if (base[x] == y) reset (x);
00052       else bracket_rw (x)= y;
00053     }
00054   }
00055 }
00056 
00057 TMPL void
00058 hashmap_rep<T,U>::post_patch (hashmap<T,U> patch, hashmap<T,U> base) {
00059   int i= 0, n= patch->n;
00060   for (; i<n; i++) {
00061     list<hashentry<T,U> > l= patch->a[i];
00062     for (; !is_nil (l); l= l->next) {
00063       T x= l->item.key;
00064       U y= l->item.im;
00065       if (base[x] == y) reset (x);
00066       else bracket_rw (x)= y;
00067     }
00068   }
00069 }
00070 
00071 TMPL list<hashentry<T,U> >
00072 copy_list (list<hashentry<T,U> > l) {
00073   if (is_nil (l)) return l;
00074   else return list<hashentry<T,U> >
00075                (hashentry<T,U> (l->item.code, l->item.key, l->item.im),
00076                copy_list (l->next));
00077 }
00078 
00079 TMPL hashmap<T,U>
00080 copy (hashmap<T,U> h) {
00081   int i, n= h->n;
00082   hashmap<T,U> h2 (h->init, n, h->max);
00083   h2->size= h->size;
00084   for (i=0; i<n; i++)
00085     h2->a[i]= copy_list (h->a[i]);
00086   return h2;
00087 }
00088 
00089 TMPL hashmap<T,U>
00090 changes (hashmap<T,U> patch, hashmap<T,U> base) {
00091   int i;
00092   hashmap<T,U> h (base->init);
00093   for (i=0; i<patch->n; i++) {
00094     list<hashentry<T,U> > l (patch->a[i]);
00095     while (!is_nil (l)) {
00096       if (l->item.im != base [l->item.key])
00097        h (l->item.key)= l->item.im;
00098       l=l->next;
00099     }
00100   }
00101   return h;
00102 }
00103 
00104 TMPL hashmap<T,U>
00105 invert (hashmap<T,U> patch, hashmap<T,U> base) {
00106   int i;
00107   hashmap<T,U> h (base->init);
00108   for (i=0; i<patch->n; i++) {
00109     list<hashentry<T,U> > l (patch->a[i]);
00110     while (!is_nil (l)) {
00111       if (l->item.im != base [l->item.key])
00112        h (l->item.key)= base [l->item.key];
00113       l=l->next;
00114     }
00115   }
00116   return h;
00117 }
00118 
00119 TMPL hashmap<T,U>::hashmap (U init, tree t):
00120   rep (tm_new<hashmap_rep<T,U> > (init, 1, 1))
00121 {
00122   int i, n= arity (t);
00123   for (i=0; i<n; i++)
00124     if (is_func (t[i], ASSOCIATE, 2))
00125       rep->bracket_rw (get_label (t[i][0]))= copy (t[i][1]);
00126 }
00127 
00128 #undef H
00129 #undef TMPL
00130 #endif // defined HASHMAP_EXTRA_CC