2
* Inkscape::Algorithms::longest_common_suffix
5
* MenTaLguY <mental@rydia.net>
7
* Copyright (C) 2004 MenTaLguY
9
* Released under GNU GPL, read the file 'COPYING' for more information
12
#ifndef SEEN_INKSCAPE_ALGORITHMS_LONGEST_COMMON_SUFFIX_H
13
#define SEEN_INKSCAPE_ALGORITHMS_LONGEST_COMMON_SUFFIX_H
17
#include "util/list.h"
21
namespace Algorithms {
26
* The case of sharing a common successor is handled in O(1) time.
28
* If \a a is the longest common suffix, then runs in O(len(rest of b)) time.
30
* Otherwise, runs in O(len(a) + len(b)) time.
33
template <typename ForwardIterator>
34
ForwardIterator longest_common_suffix(ForwardIterator a, ForwardIterator b,
37
typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;
38
return longest_common_suffix(a, b, end, std::equal_to<value_type>());
41
template <typename ForwardIterator, typename BinaryPredicate>
42
ForwardIterator longest_common_suffix(ForwardIterator a, ForwardIterator b,
43
ForwardIterator end, BinaryPredicate pred)
45
if ( a == end || b == end ) {
49
/* Handle in O(1) time the common cases of identical lists or tails. */
51
/* identical lists? */
56
/* identical tails? */
57
ForwardIterator tail_a(a);
58
ForwardIterator tail_b(b);
59
if ( ++tail_a == ++tail_b ) {
64
/* Build parallel lists of suffixes, ordered by increasing length. */
66
using Inkscape::Util::List;
67
using Inkscape::Util::cons;
68
ForwardIterator lists[2] = { a, b };
69
List<ForwardIterator> suffixes[2];
71
for ( int i=0 ; i < 2 ; i++ ) {
72
for ( ForwardIterator iter(lists[i]) ; iter != end ; ++iter ) {
73
if ( iter == lists[1-i] ) {
74
// the other list is a suffix of this one
78
suffixes[i] = cons(iter, suffixes[i]);
82
/* Iterate in parallel through the lists of suffix lists from shortest to
83
* longest, stopping before the first pair of suffixes that differs
86
ForwardIterator longest_common(end);
88
while ( suffixes[0] && suffixes[1] &&
89
pred(**suffixes[0], **suffixes[1]) )
91
longest_common = *suffixes[0];
96
return longest_common;
103
#endif /* !SEEN_INKSCAPE_ALGORITHMS_LONGEST_COMMON_SUFFIX_H */
108
c-file-style:"stroustrup"
109
c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
114
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :