hash.h

00001 /*
00002  * ASTL - the Automaton Standard Template Library.
00003  * C++ generic components for Finite State Automata handling.
00004  * Copyright (C) 2000-2003 Vincent Le Maout (vincent.lemaout@chello.fr).
00005  * 
00006  * This library is free software; you can redistribute it and/or
00007  * modify it under the terms of the GNU Lesser General Public
00008  * License as published by the Free Software Foundation; either
00009  * version 2.1 of the License, or (at your option) any later version.
00010  * 
00011  * This library is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  * Lesser General Public License for more details.
00015  * 
00016  * You should have received a copy of the GNU Lesser General Public
00017  * License along with this library; if not, write to the Free Software
00018  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00019  *
00020  */
00021 
00022 #ifndef ASTL_HASH_H
00023 #define ASTL_HASH_H
00024 
00025 #include <astl.h>
00026 #include <iostream>
00027 
00028 using namespace std;
00029 
00030 namespace astl {
00031 
00032 // Requirements (see the algorithm make_hash)
00033 // 1. DFA::Tag::wc()
00034 template <typename ForwardCursor>
00035 class hash_cursor : public ForwardCursor
00036 {
00037 protected:
00038   int hashv;
00039 
00040 public:
00041   typedef hash_cursor                 self;
00042   typedef ForwardCursor               super;
00043   typedef typename super::state_type  state_type;
00044   typedef typename super::char_type   char_type;
00045   typedef typename super::tag_type    tag_type;
00046   typedef typename super::char_traits char_traits;
00047   typedef typename super::concept     concept;
00048 
00049   // Backward compatibility typedefs:
00050   typedef state_type  State;
00051   typedef tag_type    Tag;
00052   typedef char_type   Alphabet;
00053   typedef char_traits Sigma;
00054 
00055   hash_cursor()
00056     : super()
00057   { }
00058 
00059   hash_cursor(const ForwardCursor &c)
00060     : super(c), hashv(0)
00061   { }
00062 
00063   self& operator=(state_type p) {
00064     super::operator=(p);
00065     hashv = 0;       // warning: might get into troubles if p != dfa->initial()
00066     return *this;
00067   }
00068 
00069   bool first() {
00070     if (super::first()) {
00071       if (super::aim_final()) ++hashv;
00072       return true;
00073     }
00074     return false;
00075   }
00076 
00077   bool next() {
00078     hashv += super::aim_tag().wc();
00079     if (super::next()) {
00080       if (super::aim_final()) ++hashv;
00081       return true;
00082     }
00083     return false;
00084   }
00085 
00086   bool forward(const char_type &a) {
00087     if (first()) {
00088       while (super::letter() != a)
00089         if (!next()) {
00090           *this = super::sink_state();
00091           return false;
00092         }
00093       forward();
00094       return true;
00095     }
00096     return false;
00097   }
00098 
00099   void forward() {
00100     super::forward();
00101   }
00102 
00103   int hash_value() const {
00104     return hashv;
00105   }
00106 };
00107 
00108 template <typename DFA>
00109 inline
00110 hash_cursor<forward_cursor<DFA> > hashc(const DFA &a) {
00111   return hashc(forwardc(a, a.initial()));
00112 }
00113 
00114 template <typename DFA>
00115 inline
00116 hash_cursor<forward_cursor<DFA> > 
00117 hashc(const DFA &a, const typename DFA::state_type &q) {
00118   return hash_cursor<forward_cursor<DFA> >(forwardc(a, q));
00119 }
00120 
00121 struct hash_tag
00122 {
00123   int wc_;
00124 
00125   hash_tag(int i = 0)
00126     : wc_(i)
00127   { }
00128 
00129   // needed by stream input with clone_cursor & clone:
00130   hash_tag& operator=(const empty&) { return *this; }
00131   int& wc()       { return wc_; }
00132   int  wc() const { return wc_; }
00133 };
00134 
00135 inline bool operator<(const hash_tag &x, const hash_tag &y) {
00136   return x.wc() < y.wc();
00137 }
00138 
00139 inline bool operator==(const hash_tag &x, const hash_tag &y) {
00140   return x.wc() == y.wc();
00141 }
00142 
00143 inline ostream& operator<<(ostream& out, const hash_tag& h) {
00144   return out << h.wc();
00145 }
00146 
00147 inline istream& operator>>(istream& in, hash_tag& h) {
00148   return in >> h.wc();
00149 }
00150 
00151 // make_hash computes the size of each state language (recognized words count)
00152 // it stores the result in the state tag which must at least have the same
00153 // interface as struct hash_tag above, that is:
00154 // type requirements:
00155 // int DFA::Tag::wc() const;
00156 // int& DFA::Tag::wc(); 
00157 template <typename DFA>
00158 inline
00159 void make_hash(DFA& a) 
00160 {
00161 #ifndef _MSC_VER
00162   make_hash_(a, dfirst_markc(a));
00163 #else
00164   make_hash_(a, dfirst_markc(forwardc(a)));
00165 #endif
00166 }
00167 
00168 template <typename DFA, typename DFirstCursor>
00169 void make_hash_(DFA& a, DFirstCursor first, DFirstCursor last = DFirstCursor())
00170 {
00171   while (first != last) {
00172     while (first.forward());
00173     do {
00174       if (first.aim_final()) a.tag(first.src()).wc() += 1;
00175       a.tag(first.src()).wc() += a.tag(first.aim()).wc();
00176     } while (!first.forward());
00177   }
00178 }
00179 
00182 // Requirements: c points to the initial state
00183 template <typename ForwardCursorOrDFA, typename InputIterator>
00184 inline
00185 int hash_value(const ForwardCursorOrDFA &x, InputIterator first, 
00186                InputIterator last) {
00187   return hash_value(x, first, last, x);
00188 }
00189 
00190 template <typename ForwardCursor, typename InputIterator>
00191 inline
00192 int hash_value(const ForwardCursor &c, InputIterator first, 
00193                InputIterator last, const cursor_concept&)
00194 {
00195   if (!c.sink()) {
00196     hash_cursor<ForwardCursor> h(c);
00197     while (first != last && h.forward(*first)) 
00198       ++first;
00199     if (first == last && h.src_final()) 
00200       return h.hash_value();
00201   }
00202   return 0;  // word not found
00203 }
00204 
00205 template <typename DFA, typename InputIterator>
00206 inline
00207 int hash_value(const DFA &x, InputIterator first, 
00208                InputIterator last, const DFA_concept&) {
00209   return hash_value(forwardc(x), first, last);
00210 }
00211 
00212 template <typename ForwardCursor, typename Container>
00213 inline
00214 int hash_value(const ForwardCursor &c, const Container &C)
00215 {
00216   if (!c.sink()) {
00217     hash_cursor<ForwardCursor> h(c);
00218     typename Container::const_iterator first = C.begin();
00219     while (first != C.end() && h.forward(*first)) 
00220       ++first;
00221     if (first == C.end() && h.src_final()) 
00222       return h.hash_value();
00223   }
00224   return 0;  // word not found
00225 }
00226 
00227 // Write the word corresponding to the id into x
00228 // Requirements: 
00229 // - c is a forward cursor pointing to a hashing DFA
00230 // - id > 0
00231 // - int ForwardCursor::tag_type::wc() const;
00232 template <typename ForwardCursor, typename OutputIterator>
00233 inline
00234 int value_hash(ForwardCursor c, int id, OutputIterator x)
00235 {
00236   int how_far = 0;
00237   while(id > 0 && c.first()) {
00238     if (c.aim_final()) --id;
00239     while (id - c.aim_tag().wc() > 0) {
00240       id -= c.aim_tag().wc();
00241       if (!c.next()) return 0;  // id does not match any word
00242       if (c.aim_final()) --id;
00243     }
00244     *x = c.letter(); ++x; 
00245     c.forward(); ++how_far;  
00246   }
00247   return how_far;
00248 }
00249 
00250 } // namespace astl
00251 
00252 #endif // ASTL_HASH_H
00253 

Generated on Sun Mar 8 02:41:34 2009 for ASTL by  doxygen 1.5.7.1