ExactCompare.h

Go to the documentation of this file.

 
#pragma once
 
#include <string/LinearString.h>
#include <string/CyclicString.h>
 
namespace string {
 
namespace naive {
 
class ExactCompare {
public:
    template < class SymbolType >
    static int compare(const string::LinearString < SymbolType >& u, const string::LinearString < SymbolType >& v);
 
    template < class SymbolType >
    static int compare(const string::CyclicString < SymbolType >& u, const string::CyclicString < SymbolType >& v);
};
 
template < class SymbolType >
int ExactCompare::compare ( const string::LinearString < SymbolType > & u, const string::LinearString < SymbolType > & v ) {
    size_t n = u.getContent ( ).size ( );
    size_t m = v.getContent ( ).size ( );
    size_t k = 0;
 
    while ( k < n && k < m && u.getContent ( )[k] == v.getContent ( )[k] ) k++;
 
    if ( ( k == m ) && ( k == n ) )
        return 0;
    else if ( k == m )
        return -1;
    else if ( k == n )
        return 1;
    else if ( u.getContent ( )[k] < v.getContent ( )[k] )
        return -1;
    else
        return 1;
}
 
template < class SymbolType >
int ExactCompare::compare ( const string::CyclicString < SymbolType > & u, const string::CyclicString < SymbolType > & v ) {
    size_t n = u.getContent ( ).size ( );
    size_t m = v.getContent ( ).size ( );
    size_t i = 0;
    size_t j = 0;
 
    bool last = false;
 
    while ( i < n && j < m ) {
        size_t k = 0;
 
        while ( k < n && u.getContent ( )[( i + k ) % n] == v.getContent ( )[( j + k ) % m] ) k++;
 
        if ( k >= n ) return 0;
 
        last = u.getContent ( )[( i + k ) % n] > v.getContent ( )[( j + k ) % m];
 
        if ( last )
            i += k + 1;
        else
            j += k + 1;
    }
 
    return last ? 1 : -1;
}
 
} /* namespace naive */
 
} /* namespace string */