Partial Match string map
jul, 2008
problem:
Partial String Key Match
solution:
dependencies
DualPredicateMap, strlicmp, strlcmp, isShorter, predicatesNote that ANSI C++ requires that the entire template be available to every compilation unit (ODR rule). So: DO NOT put the functions in a separate .cpp file and expect the compiler to be able to find them. The best source code organisation is to include the whole template in a header file and include that everywhere that it is required. export is not supported for all compilers.
template<class ValueType> class StringMapCIL: public DualPredMap<const char*, ValueType, LessThanCI, LessThanCIL> {
public:
StringMapCIL(): DualPredMap<const char*, ValueType, LessThanCI, LessThanCIL>::DualPredMap() {}
typename StringMapCIL<ValueType>::iterator find(const char *haystack);
};
template<class ValueType> typename StringMapCIL<ValueType>::iterator StringMapCIL<ValueType>::find(const char *haystack) {
//length of the haystack *must* be more than the length of the needle
//the two strings are identical up to the first ending because of strlcmp
//the initial find will find *a* match
//because of the jump iteration that is used to tend towards a result
//there may be a longer match afterwards (always after if at all)
//the map is always ordered by length asc because of the sort predicate
int dir = 0, last;
typename StringMapCIL<ValueType>::iterator i,j;
if (!haystack || !(*haystack)) return end(); //searches for 0 or "" return end() in partial mapping
i = j = DualPredMap<const char*, ValueType, LessThanCI, LessThanCIL>::find(haystack);
if (i != end()) {
//found something
//look for a longer match after this initial one (ordered by length)
while (dir >= 0 && ++i != end()) { //continue when the haystack is more than or equal to the key
last = dir; //initial match = 0
dir = strlicmp(haystack, i->first);
}
if (!last) i--; else i = j; //return to origonal if did not find a better match
//the final match for the key must be longer than the haystack
if (isShorter(haystack, i->first)) i = end(); //length haystack < length needle
}
return i;
}
template<class ValueType> class StringMapL: public DualPredMap<const char*, ValueType, LessThan, LessThanL> {
public:
StringMapL(): DualPredMap<const char*, ValueType, LessThan, LessThanL>::DualPredMap() {}
typename StringMapL<ValueType>::iterator find(const char *haystack);
};
template<class ValueType> typename StringMapL<ValueType>::iterator StringMapL<ValueType>::find(const char *haystack) {
int dir = 0, last;
typename StringMapL<ValueType>::iterator i,j;
if (!haystack || !(*haystack)) return end(); //searches for 0 or "" return end() in partial mapping
i = j = DualPredMap<const char*, ValueType, LessThan, LessThanL>::find(haystack);
if (i != end()) {
//found something
//look for a longer match after this initial one (ordered by length)
while (dir >= 0 && ++i != end()) { //continue when the haystack is more than or equal to the key
last = dir; //initial match = 0
dir = strlcmp(haystack, i->first);
}
if (!last) i--; else i = j; //return to origonal if did not find a better match
//the final match for the key must be longer than the haystack
if (isShorter(haystack, i->first)) i = end(); //length haystack < length needle
}
return i;
}
StringMapCIL<int> dp;
StringMapCIL<int>::iterator i;
dp.insert(make_pair<const char*, int>("example", 3));
i = dp.find("example");
class LessThan {
public:
bool operator() (const char *str1, const char *str2) const {return strcmp(str1, str2) < 0;}
};
class LessThanCI {
public:
bool operator() (const char *str1, const char *str2) const {return strcasecmp(str1, str2) < 0;}
};
//variable length (test = testing)
//with normal compare test != testing
//the strlicmp returns 0 at the end of either string
//comparisons between a small string and huge data are efficient
class LessThanL {
public:
bool operator() (const char *str1, const char *str2) const {return strlcmp(str1, str2) < 0;}
};
class LessThanCIL {
public:
bool operator() (const char *str1, const char *str2) const {return strlicmp(str1, str2) < 0;}
};