- Main Page
- Namespaces
- Classes
- Files

# proto/Source/hash_vector.h

Go to the documentation of this file.

    00001
    00014 #ifndef _HASH_H
    00015 #define _HASH_H
    00016
    00017 #include <algorithm>
    00018 #include <functional>
    00019 #include <vector>
    00020
    00021 namespace ace {
    00022
    00023 // NOTE: Class is designed with above-lying structure in mind,
    00024 // which is generally (very) bad idea. But performace is... performance.
    00025
    00030 template<class _StType, class _HashFunc>
    00031 class HashVector {
    00032 public:
    00035     typedef _StType type;
    00036
    00037 private:
    00040     typedef typename std::vector<_StType> _store_t;
    00043     typedef typename std::vector<_store_t> _buckets_t;
    00044
    00047     size_t _init_size;
    00050     size_t _bucket_size;
    00053     std::vector<_store_t> _buckets;
    00056     _HashFunc _h;
    00059     size_t _items;
    00062     size_t _crop_ratio;
    00063
    00069     class items_compare: public std::unary_function<_StType, bool> {
    00072         const _StType _look_for;
    00073     public:
    00076         items_compare(_StType look_for): _look_for(look_for) {}
    00081         bool operator()(_StType ptr) const {
    00082             return *ptr == *_look_for;
    00083         }
    00084     };
    00085
    00089     class items_sort: public std::binary_function<_StType, _StType, bool> {
    00090     public:
    00096         bool operator()(_StType lhs, _StType rhs) const {
    00097             // > -> we want descending order!
    00098             return lhs->frequency() > rhs->frequency();
    00099         }
    00100     };
    00101
    00104     void _expand(void) {
    00105         //
    00106         size_t _recent_buckets_size = _buckets.size();
    00107
    00108         // Double size buckets table.
    00109         _buckets.resize(_recent_buckets_size * 2);
    00110
    00111         bool any_empty = false;
    00112         size_t bucket_index = 0, index_of_empty = 0;
    00113         // Process each bucket (except newly added of course).
    00114         for ( size_t i = 0; i < _recent_buckets_size; ++i ) {
    00115             any_empty = false; // !
    00116             for ( size_t j = 0; j < _buckets[i].size(); ++j ) {
    00117                 // Get bucket no.
    00118                 bucket_index = _h(_buckets[i][j]) % _buckets.size();
    00119                 if ( bucket_index != i ) {
    00120                     // Copy to new bucket.
    00121                     _buckets[bucket_index].push_back(_buckets[i][j]);
    00122                     if ( !any_empty ) {
    00123                         any_empty = true; index_of_empty = j;
    00124                     }
    00125                 } else if ( any_empty ) {
    00126                     // Any empty before?
    00127                     _buckets[i][index_of_empty] = _buckets[i][j];
    00128                     ++index_of_empty;
    00129                     // We get rid of tail empty elements later...
    00130                 }
    00131             }
    00132
    00133             // Really remove "removed" elements (we have to count number of elements added into new bucket,
    00134             // to know how much elements to erase (from end).
    00135             _buckets[i].erase(_buckets[i].end() - _buckets[i + _recent_buckets_size].size(), _buckets[i].end());
    00136
    00137             // STD way.
    00138             // The two calls below does exactly the same, as the loop and erase command above.
    00139             // It's a pity, remove_copy_if doesn't really "remove" elements (even in remove_if way!).
    00140             //std::remove_copy_if(_buckets[i].begin(), _buckets[i].end(), std::back_inserter(_buckets[i+_recent_buckets_size]), std::not1(hash_compare(i, _buckets.size())));
    00141             // Two calls are more expensive then one hand written loop.
    00142             //_buckets[i].erase(std::remove_if(_buckets[i].begin(), _buckets[i].end(), hash_compare(i, _buckets.size())), _buckets[i].end());
    00143
    00144             // Too much unused space in bucket?
    00145             if ( _crop_ratio ) {
    00146                 if ( (_buckets[i].size() * _crop_ratio) < _buckets[i].capacity() ) {
    00147                     // So do crop!
    00148                     std::vector<_StType>(_buckets[i]).swap(_buckets[i]);
    00149                 }
    00150             }
    00151         }
    00152     }
    00153
    00154 public:
    00157     class iterator {
    00160         typedef HashVector<_StType, _HashFunc> _hash_t;
    00163         typename _hash_t::_buckets_t::const_iterator _end_of_buckets;
    00166         typename _hash_t::_buckets_t::const_iterator _i_bucket;
    00169         typename _hash_t::_store_t::const_iterator _i_item;
    00172         inline bool _end(void) const { return _i_bucket == _end_of_buckets; }
    00175         void _init_item(void) {
    00176             if ( _end() ) {
    00177                 return;
    00178             }
    00179             if ( _i_bucket->empty() ) {
    00180                 // Find first non empty bucket.
    00181                 _next();
    00182             } else {
    00183                 _i_item = _i_bucket->begin();
    00184             }
    00185         }
    00188         void _next(void) {
    00189             // Go to next non empty bucket.
    00190             while ( (++_i_bucket != _end_of_buckets) && _i_bucket->empty() );
    00191             if ( _i_bucket != _end_of_buckets ) {
    00192                 //
    00193                 _i_item = _i_bucket->begin();
    00194             }
    00195         }
    00196
    00197     public:
    00201         explicit iterator(const typename _hash_t::_buckets_t& hash_buckets): _end_of_buckets(hash_buckets.end()), _i_bucket(hash_buckets.begin()), _i_item() {
    00202             _init_item();
    00203         }
    00209         explicit iterator(const typename _hash_t::_buckets_t& hash_buckets, typename _hash_t::_buckets_t::const_iterator i_bucket): _end_of_buckets(hash_buckets.end()), _i_bucket(i_bucket), _i_item() {
    00210             _init_item();
    00211         }
    00217         explicit iterator(const typename _hash_t::_buckets_t& hash_buckets, typename _hash_t::_buckets_t::const_iterator i_bucket, typename _hash_t::_store_t::const_iterator i_item): _end_of_buckets(hash_buckets.end()), _i_bucket(i_bucket), _i_item(i_item) {}
    00218
    00219         // Following operators are needed to satisfy NGramStore functionality.
    00220
    00223         iterator& operator++(void) {
    00224             if ( _end() ) {
    00225                 // Do nothing.
    00226                 return *this;
    00227             }
    00228             if ( ++_i_item == _i_bucket->end() ) {
    00229                 // Find next non empty bucket and set item iterator to its beginning.
    00230                 _next();
    00231             }
    00232             return *this;
    00233         }
    00234
    00238         const typename _hash_t::type& operator*(void) const {
    00239             // If invalid, would fall as it should.
    00240             return *_i_item;
    00241         }
    00242
    00247         bool operator==(const iterator& rhs) const {
    00248
    00249             if ( _i_bucket != rhs._i_bucket ) {
    00250                 // Different buckets.
    00251                 return false;
    00252             }
    00253             if ( _end() && rhs._end() ) {
    00254                 // Both at end.
    00255                 return true;
    00256             }
    00257             if ( _end() || rhs._end() ) {
    00258                 // Only one at its end, so:
    00259                 return false;
    00260             }
    00261             if ( _i_item == rhs._i_item ) {
    00262                 // Both the same!
    00263                 return true;
    00264             }
    00265             return false;
    00266         }
    00267
    00272         bool operator!=(const iterator& rhs) const {
    00273             return !operator==(rhs);
    00274         }
    00275
    00276     };
    00277
    00278     // Following typedefs are needed to meet in hashset interface used by
    00279     // overlying N-grams storing structure.
    00280
    00283     typedef iterator const_iterator;
    00286     typedef std::pair<iterator, bool> pair_ib;
    00289     typedef std::pair<iterator, iterator> pair_ii;
    00290
    00296     HashVector(size_t init_size, size_t bucket_size, size_t crop_ratio): _init_size(1 << init_size), _bucket_size(1 << bucket_size), _buckets(_init_size), _items(0), _crop_ratio(crop_ratio) {}
    00297
    00300     HashVector& operator=(const HashVector& rhs) {
    00301         if ( this != &rhs ) {
    00302             _init_size = rhs._init_size;
    00303             _bucket_size = rhs._bucket_size;
    00304             _buckets = rhs._buckets;
    00305             _items = rhs._items;
    00306             _h = rhs._h;
    00307             _crop_ratio = rhs._crop_ratio;
    00308         }
    00309         return *this;
    00310     }
    00311
    00314     const_iterator begin(void) const {
    00315         return const_iterator(_buckets);
    00316     }
    00317
    00320     const_iterator end(void) const {
    00321         return const_iterator(_buckets, _buckets.end());
    00322     }
    00323
    00328     pair_ib insert(_StType value) {
    00329         // Update items counter and do check...
    00330         if ( ++_items > (_buckets.size() * _bucket_size) ) {
    00331             // Expansion needed!
    00332             _expand();
    00333         }
    00334         // Find bucket.
    00335         typename _buckets_t::iterator bucket = _buckets.begin() + (_h(value) % _buckets.size());
    00336         // Insert...
    00337         bucket->push_back(value);
    00338         // ...and return.
    00339         return pair_ib(iterator(_buckets, bucket, bucket->end() - 1), true);
    00340     }
    00341
    00346     pair_ii equal_range(const _StType value) const {
    00347
    00348         typename _buckets_t::const_iterator bucket = _buckets.begin() + (_h(value) % _buckets.size());
    00349         // Look into recent.
    00350         typename _store_t::const_iterator searched = std::find_if(bucket->begin(), bucket->end(), items_compare(value));
    00351
    00352         if ( searched != bucket->end() ) {
    00353             // Founded!
    00354             return pair_ii(iterator(_buckets, bucket, searched), iterator(_buckets, bucket, searched + 1));
    00355         } else {
    00356             // Sorry, not found.
    00357             return pair_ii(iterator(_buckets, bucket, bucket->end()), iterator(_buckets, bucket, bucket->end()));
    00358         }
    00359     }
    00360
    00363     inline size_t size(void) const { return _items; }
    00364
    00367     void sort(void) {
    00368         for ( typename _buckets_t::iterator i_bucket = _buckets.begin(); i_bucket != _buckets.end(); ++i_bucket ) {
    00369             std::sort(i_bucket->begin(), i_bucket->end(), items_sort());
    00370         }
    00371     }
    00372
    00373 };
    00374
    00375 } // namespace ace
    00376
    00377 #endif