Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
strings::suffix_array::SuffixArrayChecker< T > Class Template Reference

#include <suffix_array_check.h>

List of all members.

Static Public Member Functions

static bool isValidSuffixArray (const T s[], const int SA[], int length)
static bool isValidSuffixArrayInverses (const T s[], const int SA[], int length)

Static Protected Member Functions

static bool checkCondition1Holds (const int SA[], int length)
static bool checkCondition2Holds (const T s[], const int SA[], int length)
static bool checkCondition3HoldsKarkkainen (const T s[], const int SA[], int length)
static bool checkCondition3HoldsInverses (const T s[], const int SA[], int length)

Private Member Functions

 FRIEND_TEST (SuffixArrayCheck, condition1)

Detailed Description

template<typename T>
class strings::suffix_array::SuffixArrayChecker< T >

Class that can check validity of suffix array conditions.


Member Function Documentation

template<typename T >
static bool strings::suffix_array::SuffixArrayChecker< T >::checkCondition1Holds ( const int  SA[],
int  length 
) [inline, static, protected]

Checks that: For all i [0,length), SA[i] [0,length).

Returns:
true if condition holds
template<typename T >
static bool strings::suffix_array::SuffixArrayChecker< T >::checkCondition2Holds ( const T  s[],
const int  SA[],
int  length 
) [inline, static, protected]

Checks that: For all i [1,length), s[SA[i - 1]] <= s[SA[i]]. Warning: there is no out-of bounds checking in this function, so be sure to call checkCondition1Holds() first!

Returns:
true if condition holds
template<typename T >
static bool strings::suffix_array::SuffixArrayChecker< T >::checkCondition3HoldsInverses ( const T  s[],
const int  SA[],
int  length 
) [inline, static, protected]

Check that: For all i [1,length) such that s[SA[i - 1]] = s[SA[i]] and SA[i - 1] != n - 1, there exists j, k [0,n) such that SA[j] = SA[i - 1]+1, SA[k] = SA[i]+1 and j<k.

This algorithm requires linear memory becouse it needs inverse array to suffix array.

Warning: this function does not check for out-of-bounds, check condition 1 first.

Returns:
true if condition holds
template<typename T >
static bool strings::suffix_array::SuffixArrayChecker< T >::checkCondition3HoldsKarkkainen ( const T  s[],
const int  SA[],
int  length 
) [inline, static, protected]

Checks following reformulation of 3. condition: For all characters c alphabet: If SA[a, b] contains the suffixes starting with the character c, then SA[a]+1, SA[a+1]+1,... , SA[b]+1 occur in SA in this order (but not consecutively in general), except that the first entry SA[a] + 1 is missing when c = s[n - 1].

Warning: this function does not check for out-of-the bounds, so you should check condition 1 first!

Note that memory O(sigma) where sigma is size of the alphabet. If your alphabet is positive-indexed and not sparse, you may change std::map to array in this implementation to gain speed and less memory storage.

Note: reformulation of 3rd condition is equal to the 3rd condition itself only when the first two conditions hold. The results of checkCondition3HoldsKarkkainen may be therefore different from checkCondition3HoldsInverses unless you assert the condition 1,2.

Based on pseudocode from the paper.

Returns:
true if condition holds
template<typename T >
strings::suffix_array::SuffixArrayChecker< T >::FRIEND_TEST ( SuffixArrayCheck  ,
condition1   
) [private]
template<typename T >
static bool strings::suffix_array::SuffixArrayChecker< T >::isValidSuffixArray ( const T  s[],
const int  SA[],
int  length 
) [inline, static]

Liner-time check of suffix-array invariant. Uses O(alphabet) memory.

Parameters:
soriginal sequence
sasuffix array to be checked
lengthlength of the sequence (and suffix array)
Returns:
true if the suffix array is correct for the sequence
template<typename T >
static bool strings::suffix_array::SuffixArrayChecker< T >::isValidSuffixArrayInverses ( const T  s[],
const int  SA[],
int  length 
) [inline, static]

Liner-time check of suffix-array invariant. Uses O(n) memory.

Parameters:
soriginal sequence
sasuffix array to be checked
lengthlength of the sequence (and suffix array)
Returns:
true if the suffix array is correct for the sequence

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