dcover/stringsort.hpp

   1 /*
   2  * stringsort.hpp
   3  *
   4  * Copyright 2003 Max-Planck-Institut fuer Informatik
   5  *
   6  */
   7
   8 //======================================================================
   9 // Multikey quicksort for suffixes
  10 //======================================================================
  11
  12 #ifndef STRINGSORT_HPP
  13 #define STRINGSORT_HPP
  14
  15 #include "partition.hpp"
  16
  17 #include <algorithm>
  18 #include <iterator>
  19 #include <functional>
  20 #include <vector>
  21
  22
  23 //----------------------------------------------------------------------
  24 // function string_compare
  25 //
  26 // Compare two strings until a mismatch but no longer than limit
  27 // characters.  The sign of the result indicates the order of the
  28 // strings and the absolute value the distance of the mismatch from
  29 // the limit. Zero means that no mismatch was found within limit
  30 // characters.
  31 //
  32 // WARNING: A check for the end of a string is user's responsibility.
  33 //----------------------------------------------------------------------
  34 template <typename StringIterator, typename DifferenceType,
  35           typename CharCompare>
  36 DifferenceType
  37 string_compare(StringIterator s1, StringIterator s2,
  38                DifferenceType limit, CharCompare less) {
  39   for ( ; limit > 0; --limit, ++s1, ++s2) {
  40     if (less(*s1,*s2)) return -limit;
  41     if (less(*s2,*s1)) return limit;
  42   }
  43   return 0;
  44 }
  45 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  46 template <typename StringIterator, typename DifferenceType>
  47 inline DifferenceType
  48 string_compare(StringIterator s1, StringIterator s2, DifferenceType limit)
  49 {
  50   typedef typename std::iterator_traits<StringIterator>::value_type
  51     char_type;
  52   return string_compare(s1, s2, limit, std::less<char_type>());
  53 }
  54
  55
  56 //----------------------------------------------------------------------
  57 // const int suffix_insertion_sort_threshold_
  58 //
  59 // Groups of suffixes with size less or equal to this value are
  60 // sorted by insertion sort.
  61 //----------------------------------------------------------------------
  62 static const int suffix_insertion_sort_threshold_ = 15;
  63
  64 //----------------------------------------------------------------------
  65 // function suffix_insertion_sort
  66 //
  67 // Sort suffixes using insertion sort.
  68 // A difference from a straightforward insertion sort is that
  69 // the lengths of longest common prefixes of the already sorted
  70 // suffixes are stored and used in later insertions.
  71 //----------------------------------------------------------------------
  72 template <typename StringIterator, typename SArrayIterator,
  73           typename GroupHandler, typename CharCompare>
  74 void
  75 suffix_insertion_sort(StringIterator str, StringIterator str_end,
  76                       SArrayIterator sa, SArrayIterator sa_end,
  77      typename std::iterator_traits<StringIterator>::difference_type limit,
  78                       GroupHandler handle_unsorted_group,
  79                       CharCompare less)
  80 {
  81   typedef typename std::iterator_traits<StringIterator>::difference_type
  82     str_diff_type;
  83   typedef typename std::iterator_traits<SArrayIterator>::difference_type
  84     sa_diff_type;
  85   typedef typename std::iterator_traits<SArrayIterator>::value_type
  86     pos_type;
  87
  88   static std::vector<str_diff_type> lcp(suffix_insertion_sort_threshold_);
  89   lcp.resize(sa_end-sa);
  90   lcp.back() = -1;
  91
  92   for (sa_diff_type i = sa_end-sa-2; i >= 0; --i) {
  93     pos_type i_pos = sa[i];
  94     StringIterator i_str = str + i_pos;
  95     StringIterator j_str = str + sa[i+1];
  96     str_diff_type i_limit = std::min(limit, str_end - i_str);
  97     str_diff_type ij_limit = std::min(i_limit, str_end - j_str);
  98     str_diff_type dist = string_compare(i_str, j_str, ij_limit, less);
  99     if (dist < 0 || (dist == 0 && i_limit == ij_limit)) {
 100       lcp[i] = ij_limit + dist;
 101     } else {
 102       sa[i] = sa[i+1];
 103       str_diff_type i_lcp = ij_limit - dist;
 104
 105       sa_diff_type j = i+1;
 106       for ( ; lcp[j] >= i_lcp; ++j) {
 107         if (lcp[j] == i_lcp) {
 108           j_str = str+sa[j+1];
 109           ij_limit = std::min(i_limit, str_end-j_str);
 110           dist = string_compare(i_str+i_lcp, j_str+i_lcp,
 111                                 ij_limit-i_lcp, less);
 112           if (dist < 0 || (dist == 0 && i_limit == ij_limit)) {
 113             lcp[j] = ij_limit + dist;
 114             break;
 115           } else {
 116             i_lcp = ij_limit - dist;
 117           }
 118         }
 119         sa[j] = sa[j+1];
 120         lcp[j-1] = lcp[j];
 121       }
 122
 123       sa[j] = i_pos;
 124       lcp[j-1] = i_lcp;
 125     }
 126   }
 127
 128   // find and process unsorted groups
 129   typename std::vector<pos_type>::iterator beg, end, last = lcp.end()-1;
 130   for (beg = lcp.begin(); beg < last; ++beg) {
 131     if (*beg == limit) {
 132       end = beg;
 133       do { ++end; } while (*end == limit);
 134       handle_unsorted_group(sa+(beg-lcp.begin()), sa+(end-lcp.begin())+1);
 135       beg = end;
 136     }
 137   }
 138 }
 139 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 140 template <typename StringIterator, typename SArrayIterator,
 141           typename GroupHandler>
 142 void
 143 suffix_insertion_sort(StringIterator str, StringIterator str_end,
 144                       SArrayIterator sa, SArrayIterator sa_end,
 145     typename std::iterator_traits<StringIterator>::difference_type limit,
 146                       GroupHandler handle_unsorted_group)
 147 {
 148   typedef typename std::iterator_traits<StringIterator>::value_type
 149     char_type;
 150   suffix_insertion_sort(str, str_end, sa, sa_end, limit,
 151                         handle_unsorted_group, std::less<char_type>());
 152 }
 153
 154
 155 //----------------------------------------------------------------------
 156 // functor char_access
 157 //
 158 // Compute the character that represents a suffix in comparisons.
 159 //----------------------------------------------------------------------
 160 template <typename StringIterator, typename SArrayIterator>
 161 class char_access
 162   : public std::unary_function<SArrayIterator,
 163            typename std::iterator_traits<StringIterator>::value_type>
 164 {
 165 private:
 166   const StringIterator str;
 167 public:
 168   char_access(StringIterator s) : str(s) {}
 169
 170   typename std::iterator_traits<StringIterator>::value_type
 171   operator() (SArrayIterator i) const {
 172     return str[*i];
 173   }
 174 };
 175
 176
 177 //======================================================================
 178 // function suffix_mkqsort
 179 // function suffix_mkqsort_noempty
 180 //
 181 // Sort suffixes using multikey quicksort.
 182 // These two functions call each other to implement multikey quicksort.
 183 // Either can be used as the initial call. suffix_mkqsort_noempty
 184 // places more restrictions on the input but can be slightly faster.
 185 //======================================================================
 186
 187 //----------------------------------------------------------------------
 188 // function suffix_mkqsort
 189 //
 190 // Sort suffixes using multikey quicksort.
 191 // This is the more general form.
 192 //----------------------------------------------------------------------
 193 template <typename StringIterator, typename SArrayIterator,
 194           typename GroupHandler, typename CharCompare>
 195 void
 196 suffix_mkqsort(StringIterator str, StringIterator str_end,
 197                SArrayIterator sa, SArrayIterator sa_end,
 198     typename std::iterator_traits<StringIterator>::difference_type limit,
 199                GroupHandler handle_unsorted_group,
 200                CharCompare less)
 201 {
 202   typedef typename std::iterator_traits<SArrayIterator>::value_type pos_type;
 203
 204   while (sa_end-sa > suffix_insertion_sort_threshold_ && limit > 0) {
 205
 206     // check for empty suffix(es)
 207     pos_type length = static_cast<pos_type>(str_end-str);
 208     sa = std::partition(sa, sa_end,
 209                         std::bind2nd(std::equal_to<pos_type>(), length));
 210
 211     // this would check only for one empty suffix
 212     //SArrayIterator empty = std::find(sa, sa_end, length);
 213     //if (empty != sa_end) {
 214     //  std::swap(*sa, *empty);
 215     //  ++sa;
 216     //}
 217
 218     // partition
 219     char_access<StringIterator, SArrayIterator> key(str);
 220     SArrayIterator pivot = random_pivot(sa, sa_end, less, key);
 221     std::pair<SArrayIterator,SArrayIterator> midrange;
 222     midrange = ternary_partition(sa, sa_end, pivot, less, key);
 223
 224     // recurse on <-part
 225     if (midrange.first - sa > 1) {
 226       suffix_mkqsort_noempty(str, str_end, sa, midrange.first,
 227                              limit, handle_unsorted_group, less);
 228     }
 229
 230     // recurse on >-part
 231     if (sa_end - midrange.second > 1) {
 232       suffix_mkqsort_noempty(str, str_end, midrange.second, sa_end,
 233                              limit, handle_unsorted_group, less);
 234     }
 235
 236     // loop on =-part
 237     sa = midrange.first;
 238     sa_end = midrange.second;
 239
 240     // move to the next position in the suffixes
 241     ++str;
 242     --limit;
 243
 244   }
 245
 246   if (sa_end-sa > 1) {
 247     if (limit == 0) {
 248       handle_unsorted_group(sa, sa_end);
 249     } else {
 250       suffix_insertion_sort(str, str_end, sa, sa_end, limit,
 251                             handle_unsorted_group, less);
 252     }
 253   }
 254 }
 255 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 256 template <typename StringIterator, typename SArrayIterator,
 257           typename GroupHandler>
 258 void
 259 suffix_mkqsort(StringIterator str, StringIterator str_end,
 260                SArrayIterator sa, SArrayIterator sa_end,
 261      typename std::iterator_traits<StringIterator>::difference_type limit,
 262                GroupHandler handle_unsorted_group)
 263 {
 264   typedef typename std::iterator_traits<StringIterator>::value_type
 265     char_type;
 266   suffix_mkqsort(str, str_end, sa, sa_end, limit,
 267                  handle_unsorted_group, std::less<char_type>());
 268 }
 269
 270
 271 //----------------------------------------------------------------------
 272 // function suffix_mkqsort_noempty
 273 //
 274 // Sort suffixes using multikey quicksort.
 275 // Used as a subroutine of suffix_mkqsort but can also be called
 276 // directly.  Places more restrictions on input (see below) but
 277 // can be slightly faster than suffix_mkqsort.
 278 //
 279 // The additional restrictions:
 280 // PRECONDITION: limit>0 and there are no empty suffixes
 281 //----------------------------------------------------------------------
 282 template <typename StringIterator, typename SArrayIterator,
 283           typename GroupHandler, typename CharCompare>
 284 void
 285 suffix_mkqsort_noempty(StringIterator str, StringIterator str_end,
 286                        SArrayIterator sa, SArrayIterator sa_end,
 287     typename std::iterator_traits<StringIterator>::difference_type limit,
 288                        GroupHandler handle_unsorted_group,
 289                        CharCompare less)
 290 {
 291   typedef typename std::iterator_traits<SArrayIterator>::value_type pos_type;
 292
 293   while (sa_end-sa > suffix_insertion_sort_threshold_) {
 294
 295     // partition
 296     char_access<StringIterator, SArrayIterator> key(str);
 297     SArrayIterator pivot = random_pivot(sa, sa_end, less, key);
 298     std::pair<SArrayIterator,SArrayIterator> midrange;
 299     midrange = ternary_partition(sa, sa_end, pivot, less, key);
 300
 301     // recurse on <-part
 302     if (midrange.first - sa > 1) {
 303       suffix_mkqsort_noempty(str, str_end, sa, midrange.first,
 304                              limit, handle_unsorted_group, less);
 305     }
 306
 307     // recurse on =-part
 308     if (midrange.second - midrange.first > 1) {
 309       suffix_mkqsort(str+1, str_end, midrange.first, midrange.second,
 310                      limit-1, handle_unsorted_group, less);
 311     }
 312
 313     // loop on >-part
 314     sa = midrange.second;
 315   }
 316
 317   if (sa_end-sa > 1) {
 318     suffix_insertion_sort(str, str_end, sa, sa_end, limit,
 319                           handle_unsorted_group, less);
 320   }
 321 }
 322 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 323 template <typename StringIterator, typename SArrayIterator,
 324           typename GroupHandler>
 325 void
 326 suffix_mkqsort_noempty(StringIterator str, StringIterator str_end,
 327                        SArrayIterator sa, SArrayIterator sa_end,
 328       typename std::iterator_traits<StringIterator>::difference_type limit,
 329                        GroupHandler handle_unsorted_group)
 330 {
 331   typedef typename std::iterator_traits<StringIterator>::value_type
 332     char_type;
 333   suffix_mkqsort_noempty(str, str_end, sa, sa_end, limit,
 334                          handle_unsorted_group, std::less<char_type>());
 335 }
 336
 337 #endif // STRINGSORT_HPP