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 :