Back to index

texmacs  1.0.7.15
hashmap.hpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : hashmap.hpp
00004 * DESCRIPTION: fixed size hashmaps with reference counting
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_H
00013 #define HASHMAP_H
00014 #include "list.hpp"
00015 
00016 class tree;
00017 template<class T> class list;
00018 template<class T,class U> class hashmap;
00019 template<class T,class U> class rel_hashmap;
00020 template<class T,class U> class rel_hashmap_rep;
00021 template<class T,class U> class hashmap_iterator_rep;
00022 
00023 template<class T,class U> int N (hashmap<T,U> a);
00024 template<class T,class U> tm_ostream& operator << (tm_ostream& out, hashmap<T,U> h);
00025 template<class T,class U> hashmap<T,U> copy (hashmap<T,U> h);
00026 template<class T,class U> hashmap<T,U> changes (hashmap<T,U> p,hashmap<T,U> b);
00027 template<class T,class U> hashmap<T,U> invert (hashmap<T,U> p, hashmap<T,U> b);
00028 template<class T,class U> bool operator == (hashmap<T,U> h1, hashmap<T,U> h2);
00029 template<class T,class U> bool operator != (hashmap<T,U> h1, hashmap<T,U> h2);
00030 
00031 template<class T, class U> struct hashentry {
00032   int code;
00033   T key;
00034   U im;
00035   hashentry<T,U> () { }
00036   hashentry<T,U> (int code, T key2, U im2);
00037   operator tree ();
00038 };
00039 
00040 template<class T, class U> class hashmap_rep: concrete_struct {
00041   int size;                  // size of hashmap (nr of entries)
00042   int n;                     // nr of keys (a power of two)
00043   int max;                   // mean number of entries per key
00044   U   init;                  // default entry
00045   list<hashentry<T,U> >* a;  // the array of entries
00046 
00047 public:
00048   inline hashmap_rep<T,U>(U init2, int n2=1, int max2=1):
00049     size(0), n(n2), max(max2), init(init2), a(tm_new_array<list<hashentry<T,U> > > (n)) {}
00050   inline ~hashmap_rep<T,U> () { tm_delete_array (a); }
00051   void resize (int n);
00052   void reset (T x);
00053   void generate (void (*routine) (T));
00054   bool contains (T x);
00055   bool empty ();
00056   U    bracket_ro (T x);
00057   U&   bracket_rw (T x);
00058   U&   bracket_rw_debug (T x);
00059   void join (hashmap<T,U> H);
00060 
00061   friend class hashmap<T,U>;
00062   friend class rel_hashmap<T,U>;
00063   friend class rel_hashmap_rep<T,U>;
00064   friend class hashmap_iterator_rep<T,U>;
00065   friend int N LESSGTR (hashmap<T,U> h);
00066   friend tm_ostream& operator << LESSGTR (tm_ostream& out, hashmap<T,U> h);
00067 
00068   // only for hashmap<string,tree>
00069   void write_back (T x, hashmap<T,U> base);
00070   void pre_patch (hashmap<T,U> patch, hashmap<T,U> base);
00071   void post_patch (hashmap<T,U> patch, hashmap<T,U> base);
00072   friend hashmap<T,U> copy LESSGTR (hashmap<T,U> h);
00073   friend hashmap<T,U> changes LESSGTR (hashmap<T,U> patch, hashmap<T,U> base);
00074   friend hashmap<T,U> invert LESSGTR (hashmap<T,U> patch, hashmap<T,U> base);
00075   friend class edit_env_rep; // FIXME: broken encapsulation
00076   // end only for hashmap<string,tree>
00077 
00078   friend bool operator == LESSGTR (hashmap<T,U> h1, hashmap<T,U> h2);
00079   friend bool operator != LESSGTR (hashmap<T,U> h1, hashmap<T,U> h2);
00080 };
00081 
00082 template<class T, class U> class hashmap {
00083 CONCRETE_TEMPLATE_2(hashmap,T,U);
00084   static hashmap<T,U> init;
00085   inline hashmap ():
00086     rep (tm_new<hashmap_rep<T,U> > (type_helper<U>::init, 1, 1)) {}
00087   inline hashmap (U init, int n=1, int max=1):
00088     rep (tm_new<hashmap_rep<T,U> > (init, n, max)) {}
00089   // only for hashmap<string,tree>
00090   hashmap (U init, tree t);
00091   // end only for hashmap<string,tree>
00092   inline U  operator [] (T x) { return rep->bracket_ro (x); }
00093   inline U& operator () (T x) { return rep->bracket_rw (x); }
00094   operator tree ();
00095 };
00096 CONCRETE_TEMPLATE_2_CODE(hashmap,class,T,class,U);
00097 
00098 #define TMPL template<class T, class U>
00099 TMPL inline int N (hashmap<T,U> h) { return h->size; }
00100 TMPL hashmap<T,U> changes (hashmap<T,U> patch, hashmap<T,U> base);
00101 TMPL hashmap<T,U> invert (hashmap<T,U> patch, hashmap<T,U> base);
00102 #undef TMPL
00103 
00104 #include "hashmap.cpp"
00105 #include "hashmap_extra.cpp"
00106 
00107 #endif // defined HASHMAP_H