Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
strings::search::RollingHash< BaseType > Class Template Reference

#include <rolling_hash.h>

List of all members.

Public Member Functions

 RollingHash (SizeType length, BaseType modulus_, BaseType c_)
template<typename ValueType >
BaseType roll (ValueType new_element, ValueType discarded_element)
BaseType getHash () const

Private Types

typedef size_t SizeType

Private Attributes

BaseType modulus
BaseType c
BaseType hash
BaseType c_len
SizeType length

Detailed Description

template<typename BaseType>
class strings::search::RollingHash< BaseType >

Rolling hash implementation -- can efficiently compute hash of sequence of fixed length.


Member Typedef Documentation

template<typename BaseType>
typedef size_t strings::search::RollingHash< BaseType >::SizeType [private]

Constructor & Destructor Documentation

template<typename BaseType>
strings::search::RollingHash< BaseType >::RollingHash ( SizeType  length,
BaseType  modulus_,
BaseType  c_ 
) [inline]

Create rolling hash and initialize it to zero sequence.

The rolling hash value is defined as hash = sum_{i=0}^{length-1} seq[i] * c_^(length-1-i) mod modulus_

Parameters:
lengthlength of the sequence
modulus_modulus is best to be a prime
c_

Member Function Documentation

template<typename BaseType>
BaseType strings::search::RollingHash< BaseType >::getHash ( ) const [inline]
Returns:
current hash value
template<typename BaseType>
template<typename ValueType >
BaseType strings::search::RollingHash< BaseType >::roll ( ValueType  new_element,
ValueType  discarded_element 
) [inline]

Moves the hashing function window by one character

Note: This implementation is very conservative in considering overflows. If you know about your data limitations, it can be probably optimized to two multiplications and one modular division.

Precondition:
  • discarded elements should be consistent with the #new_elements when rolling length times
Parameters:
new_elementnew element of the sequence
discarded_elementelement of the sequence which "fell out"
Returns:
new hash value

Member Data Documentation

template<typename BaseType>
BaseType strings::search::RollingHash< BaseType >::c [private]

TODO

template<typename BaseType>
BaseType strings::search::RollingHash< BaseType >::c_len [private]

value $ c^{length - 1} $

template<typename BaseType>
BaseType strings::search::RollingHash< BaseType >::hash [private]

current value of the hash

template<typename BaseType>
SizeType strings::search::RollingHash< BaseType >::length [private]

TODO: potrebne?

template<typename BaseType>
BaseType strings::search::RollingHash< BaseType >::modulus [private]

modulus of the hash function


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines