← Back to branch summary

~ubuntu-branches/ubuntu/natty/inkscape/natty

« back to all changes in this revision

Viewing changes to src/util/longest-common-suffix.h

  • Committer: Bazaar Package Importer
  • Author(s): Alex Valavanis
  • Date: 2010-09-12 19:44:58 UTC
  • mfrom: (1.1.12 upstream) (45.1.3 maverick)
  • Revision ID: james.westby@ubuntu.com-20100912194458-4sjwmbl7dlsrk5dc
Tags: 0.48.0-1ubuntu1
https://launchpad.net/bugs/628048
https://launchpad.net/bugs/401567
https://launchpad.net/bugs/456248
https://launchpad.net/bugs/463602
https://launchpad.net/bugs/591986
https://launchpad.net/bugs/513319
* Merge with Debian unstable (LP: #628048, LP: #401567, LP: #456248, 
  LP: #463602, LP: #591986)
* debian/control: 
  - Ubuntu maintainers
  - Promote python-lxml, python-numpy, python-uniconvertor to Recommends.
  - Demote pstoedit to Suggests (universe package).
  - Suggests ttf-dejavu instead of ttf-bitstream-vera (LP: #513319)
* debian/rules:
  - Run intltool-update on build (Ubuntu-specific).
  - Add translation domain to .desktop files (Ubuntu-specific).
* debian/dirs:
  - Add usr/share/pixmaps.  Allow inkscape.xpm installation
* drop 50-poppler-API.dpatch (now upstream)
* drop 51-paste-in-unwritable-directory.dpatch (now upstream) 

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/util/longest-common-suffix.h
 
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
 */
 
11
 
 
12
#ifndef SEEN_INKSCAPE_ALGORITHMS_LONGEST_COMMON_SUFFIX_H
 
13
#define SEEN_INKSCAPE_ALGORITHMS_LONGEST_COMMON_SUFFIX_H
 
14
 
 
15
#include <iterator>
 
16
#include <functional>
 
17
#include "util/list.h"
 
18
 
 
19
namespace Inkscape {
 
20
 
 
21
namespace Algorithms {
 
22
 
 
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
 */
 
32
 
 
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
}
 
40
 
 
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
    }
 
48
 
 
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
        }
 
55
 
 
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
    }
 
63
 
 
64
    /* Build parallel lists of suffixes, ordered by increasing length. */
 
65
 
 
66
    using Inkscape::Util::List;
 
67
    using Inkscape::Util::cons;
 
68
    ForwardIterator lists[2] = { a, b };
 
69
    List<ForwardIterator> suffixes[2];
 
70
 
 
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
            }
 
77
 
 
78
            suffixes[i] = cons(iter, suffixes[i]);
 
79
        }
 
80
    }
 
81
 
 
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
     */
 
85
 
 
86
    ForwardIterator longest_common(end);
 
87
 
 
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
    }
 
95
 
 
96
    return longest_common;
 
97
}
 
98
 
 
99
}
 
100
 
 
101
}
 
102
 
 
103
#endif /* !SEEN_INKSCAPE_ALGORITHMS_LONGEST_COMMON_SUFFIX_H */
 
104
 
 
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 :