00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
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
00033
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
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;
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
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
00152
00153
00154
00155
00156
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
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;
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;
00225 }
00226
00227
00228
00229
00230
00231
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;
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 }
00251
00252 #endif // ASTL_HASH_H
00253