1 /*
2 * Inkscape::Algorithms::longest_common_suffix
3 *
4 * Authors:
5 * MenTaLguY <mental@rydia.net>
6 *
7 * Copyright (C) 2004 MenTaLguY
8 *
9 * Released under GNU GPL, read the file 'COPYING' for more information
10 */
12 #ifndef SEEN_INKSCAPE_ALGORITHMS_LONGEST_COMMON_SUFFIX_H
13 #define SEEN_INKSCAPE_ALGORITHMS_LONGEST_COMMON_SUFFIX_H
15 #include <iterator>
16 #include <functional>
17 #include "util/list.h"
19 namespace Inkscape {
21 namespace Algorithms {
23 /**
24 * Time costs:
25 *
26 * The case of sharing a common successor is handled in O(1) time.
27 *
28 * If \a a is the longest common suffix, then runs in O(len(rest of b)) time.
29 *
30 * Otherwise, runs in O(len(a) + len(b)) time.
31 */
33 template <typename ForwardIterator>
34 ForwardIterator longest_common_suffix(ForwardIterator a, ForwardIterator b,
35 ForwardIterator end)
36 {
37 typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;
38 return longest_common_suffix(a, b, end, std::equal_to<value_type>());
39 }
41 template <typename ForwardIterator, typename BinaryPredicate>
42 ForwardIterator longest_common_suffix(ForwardIterator a, ForwardIterator b,
43 ForwardIterator end, BinaryPredicate pred)
44 {
45 if ( a == end || b == end ) {
46 return end;
47 }
49 /* Handle in O(1) time the common cases of identical lists or tails. */
50 {
51 /* identical lists? */
52 if ( a == b ) {
53 return a;
54 }
56 /* identical tails? */
57 ForwardIterator tail_a(a);
58 ForwardIterator tail_b(b);
59 if ( ++tail_a == ++tail_b ) {
60 return tail_a;
61 }
62 }
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
75 return lists[1-i];
76 }
78 suffixes[i] = cons(iter, suffixes[i]);
79 }
80 }
82 /* Iterate in parallel through the lists of suffix lists from shortest to
83 * longest, stopping before the first pair of suffixes that differs
84 */
86 ForwardIterator longest_common(end);
88 while ( suffixes[0] && suffixes[1] &&
89 pred(**suffixes[0], **suffixes[1]) )
90 {
91 longest_common = *suffixes[0];
92 ++suffixes[0];
93 ++suffixes[1];
94 }
96 return longest_common;
97 }
99 }
101 }
103 #endif /* !SEEN_INKSCAPE_ALGORITHMS_LONGEST_COMMON_SUFFIX_H */
105 /*
106 Local Variables:
107 mode:c++
108 c-file-style:"stroustrup"
109 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
110 indent-tabs-mode:nil
111 fill-column:99
112 End:
113 */
114 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :