lemon/radix_sort.h
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 08 May 2009 16:21:06 +0100
changeset 655 c706534d4740
parent 444 ba49101c9b07
child 1042 d450a02728d0
permissions -rw-r--r--
Fix the faulty merge of unify-sources.sh in [586b65073025]
alpar@442
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@441
     2
 *
alpar@442
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@441
     4
 *
alpar@444
     5
 * Copyright (C) 2003-2009
deba@441
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@441
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@441
     8
 *
deba@441
     9
 * Permission to use, modify and distribute this software is granted
deba@441
    10
 * provided that this copyright notice appears in all copies. For
deba@441
    11
 * precise terms see the accompanying LICENSE file.
deba@441
    12
 *
deba@441
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@441
    14
 * express or implied, and with no claim as to its suitability for any
deba@441
    15
 * purpose.
deba@441
    16
 *
deba@441
    17
 */
deba@441
    18
deba@441
    19
#ifndef RADIX_SORT_H
deba@441
    20
#define RADIX_SORT_H
deba@441
    21
deba@441
    22
/// \ingroup auxalg
deba@441
    23
/// \file
deba@441
    24
/// \brief Radix sort
deba@441
    25
///
deba@441
    26
/// Linear time sorting algorithms
deba@441
    27
deba@441
    28
#include <vector>
deba@441
    29
#include <limits>
deba@441
    30
#include <iterator>
deba@441
    31
#include <algorithm>
deba@441
    32
deba@441
    33
namespace lemon {
deba@441
    34
deba@441
    35
  namespace _radix_sort_bits {
deba@441
    36
deba@441
    37
    template <typename Value>
deba@441
    38
    struct Identity {
deba@441
    39
      const Value& operator()(const Value& val) {
alpar@442
    40
        return val;
deba@441
    41
      }
deba@441
    42
    };
deba@441
    43
deba@441
    44
deba@441
    45
    template <typename Value, typename Iterator, typename Functor>
alpar@442
    46
    Iterator radixSortPartition(Iterator first, Iterator last,
alpar@442
    47
                                Functor functor, Value mask) {
deba@441
    48
      while (first != last && !(functor(*first) & mask)) {
alpar@442
    49
        ++first;
deba@441
    50
      }
deba@441
    51
      if (first == last) {
alpar@442
    52
        return first;
deba@441
    53
      }
deba@441
    54
      --last;
deba@441
    55
      while (first != last && (functor(*last) & mask)) {
alpar@442
    56
        --last;
deba@441
    57
      }
deba@441
    58
      if (first == last) {
alpar@442
    59
        return first;
deba@441
    60
      }
deba@441
    61
      std::iter_swap(first, last);
deba@441
    62
      ++first;
deba@441
    63
      if (!(first < last)) {
alpar@442
    64
        return first;
deba@441
    65
      }
deba@441
    66
      while (true) {
alpar@442
    67
        while (!(functor(*first) & mask)) {
alpar@442
    68
          ++first;
alpar@442
    69
        }
alpar@442
    70
        --last;
alpar@442
    71
        while (functor(*last) & mask) {
alpar@442
    72
          --last;
alpar@442
    73
        }
alpar@442
    74
        if (!(first < last)) {
alpar@442
    75
          return first;
alpar@442
    76
        }
alpar@442
    77
        std::iter_swap(first, last);
alpar@442
    78
        ++first;
deba@441
    79
      }
deba@441
    80
    }
deba@441
    81
deba@441
    82
    template <typename Iterator, typename Functor>
alpar@442
    83
    Iterator radixSortSignPartition(Iterator first, Iterator last,
alpar@442
    84
                                    Functor functor) {
deba@441
    85
      while (first != last && functor(*first) < 0) {
alpar@442
    86
        ++first;
deba@441
    87
      }
deba@441
    88
      if (first == last) {
alpar@442
    89
        return first;
deba@441
    90
      }
deba@441
    91
      --last;
deba@441
    92
      while (first != last && functor(*last) >= 0) {
alpar@442
    93
        --last;
deba@441
    94
      }
deba@441
    95
      if (first == last) {
alpar@442
    96
        return first;
deba@441
    97
      }
deba@441
    98
      std::iter_swap(first, last);
deba@441
    99
      ++first;
deba@441
   100
      if (!(first < last)) {
alpar@442
   101
        return first;
deba@441
   102
      }
deba@441
   103
      while (true) {
alpar@442
   104
        while (functor(*first) < 0) {
alpar@442
   105
          ++first;
alpar@442
   106
        }
alpar@442
   107
        --last;
alpar@442
   108
        while (functor(*last) >= 0) {
alpar@442
   109
          --last;
alpar@442
   110
        }
alpar@442
   111
        if (!(first < last)) {
alpar@442
   112
          return first;
alpar@442
   113
        }
alpar@442
   114
        std::iter_swap(first, last);
alpar@442
   115
        ++first;
deba@441
   116
      }
deba@441
   117
    }
deba@441
   118
deba@441
   119
    template <typename Value, typename Iterator, typename Functor>
alpar@442
   120
    void radixIntroSort(Iterator first, Iterator last,
alpar@442
   121
                        Functor functor, Value mask) {
deba@441
   122
      while (mask != 0 && last - first > 1) {
alpar@442
   123
        Iterator cut = radixSortPartition(first, last, functor, mask);
alpar@442
   124
        mask >>= 1;
alpar@442
   125
        radixIntroSort(first, cut, functor, mask);
alpar@442
   126
        first = cut;
deba@441
   127
      }
deba@441
   128
    }
deba@441
   129
deba@441
   130
    template <typename Value, typename Iterator, typename Functor>
deba@441
   131
    void radixSignedSort(Iterator first, Iterator last, Functor functor) {
deba@441
   132
deba@441
   133
      Iterator cut = radixSortSignPartition(first, last, functor);
deba@441
   134
deba@441
   135
      Value mask;
deba@441
   136
      int max_digit;
deba@441
   137
      Iterator it;
deba@441
   138
deba@441
   139
      mask = ~0; max_digit = 0;
deba@441
   140
      for (it = first; it != cut; ++it) {
alpar@442
   141
        while ((mask & functor(*it)) != mask) {
alpar@442
   142
          ++max_digit;
alpar@442
   143
          mask <<= 1;
alpar@442
   144
        }
deba@441
   145
      }
deba@441
   146
      radixIntroSort(first, cut, functor, 1 << max_digit);
deba@441
   147
deba@441
   148
      mask = 0; max_digit = 0;
deba@441
   149
      for (it = cut; it != last; ++it) {
alpar@442
   150
        while ((mask | functor(*it)) != mask) {
alpar@442
   151
          ++max_digit;
alpar@442
   152
          mask <<= 1; mask |= 1;
alpar@442
   153
        }
deba@441
   154
      }
deba@441
   155
      radixIntroSort(cut, last, functor, 1 << max_digit);
deba@441
   156
    }
deba@441
   157
deba@441
   158
    template <typename Value, typename Iterator, typename Functor>
deba@441
   159
    void radixUnsignedSort(Iterator first, Iterator last, Functor functor) {
deba@441
   160
deba@441
   161
      Value mask = 0;
deba@441
   162
      int max_digit = 0;
deba@441
   163
deba@441
   164
      Iterator it;
deba@441
   165
      for (it = first; it != last; ++it) {
alpar@442
   166
        while ((mask | functor(*it)) != mask) {
alpar@442
   167
          ++max_digit;
alpar@442
   168
          mask <<= 1; mask |= 1;
alpar@442
   169
        }
deba@441
   170
      }
deba@441
   171
      radixIntroSort(first, last, functor, 1 << max_digit);
deba@441
   172
    }
deba@441
   173
deba@441
   174
alpar@442
   175
    template <typename Value,
alpar@442
   176
              bool sign = std::numeric_limits<Value>::is_signed >
deba@441
   177
    struct RadixSortSelector {
deba@441
   178
      template <typename Iterator, typename Functor>
deba@441
   179
      static void sort(Iterator first, Iterator last, Functor functor) {
alpar@442
   180
        radixSignedSort<Value>(first, last, functor);
deba@441
   181
      }
deba@441
   182
    };
deba@441
   183
deba@441
   184
    template <typename Value>
deba@441
   185
    struct RadixSortSelector<Value, false> {
deba@441
   186
      template <typename Iterator, typename Functor>
deba@441
   187
      static void sort(Iterator first, Iterator last, Functor functor) {
alpar@442
   188
        radixUnsignedSort<Value>(first, last, functor);
deba@441
   189
      }
deba@441
   190
    };
deba@441
   191
deba@441
   192
  }
deba@441
   193
deba@441
   194
  /// \ingroup auxalg
deba@441
   195
  ///
deba@441
   196
  /// \brief Sorts the STL compatible range into ascending order.
deba@441
   197
  ///
alpar@442
   198
  /// The \c radixSort sorts an STL compatible range into ascending
alpar@442
   199
  /// order.  The radix sort algorithm can sort items which are mapped
alpar@442
   200
  /// to integers with an adaptable unary function \c functor and the
alpar@442
   201
  /// order will be ascending according to these mapped values.
deba@441
   202
  ///
alpar@442
   203
  /// It is also possible to use a normal function instead
alpar@442
   204
  /// of the functor object. If the functor is not given it will use
alpar@442
   205
  /// the identity function instead.
alpar@442
   206
  ///
alpar@442
   207
  /// This is a special quick sort algorithm where the pivot
kpeter@559
   208
  /// values to split the items are choosen to be 2<sup>k</sup>
kpeter@559
   209
  /// for each \c k.
kpeter@559
   210
  /// Therefore, the time complexity of the algorithm is O(log(c)*n) and
kpeter@559
   211
  /// it uses O(log(c)) additional space, where \c c is the maximal value
kpeter@559
   212
  /// and \c n is the number of the items in the container.
deba@441
   213
  ///
deba@441
   214
  /// \param first The begin of the given range.
deba@441
   215
  /// \param last The end of the given range.
deba@441
   216
  /// \param functor An adaptible unary function or a normal function
deba@441
   217
  /// which maps the items to any integer type which can be either
deba@441
   218
  /// signed or unsigned.
alpar@442
   219
  ///
deba@443
   220
  /// \sa stableRadixSort()
deba@441
   221
  template <typename Iterator, typename Functor>
deba@441
   222
  void radixSort(Iterator first, Iterator last, Functor functor) {
deba@441
   223
    using namespace _radix_sort_bits;
deba@441
   224
    typedef typename Functor::result_type Value;
deba@441
   225
    RadixSortSelector<Value>::sort(first, last, functor);
deba@441
   226
  }
deba@441
   227
deba@441
   228
  template <typename Iterator, typename Value, typename Key>
deba@441
   229
  void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
deba@441
   230
    using namespace _radix_sort_bits;
deba@441
   231
    RadixSortSelector<Value>::sort(first, last, functor);
deba@441
   232
  }
deba@441
   233
deba@441
   234
  template <typename Iterator, typename Value, typename Key>
deba@441
   235
  void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
deba@441
   236
    using namespace _radix_sort_bits;
deba@441
   237
    RadixSortSelector<Value>::sort(first, last, functor);
deba@441
   238
  }
deba@441
   239
deba@441
   240
  template <typename Iterator, typename Value, typename Key>
deba@441
   241
  void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
deba@441
   242
    using namespace _radix_sort_bits;
deba@441
   243
    RadixSortSelector<Value>::sort(first, last, functor);
deba@441
   244
  }
deba@441
   245
deba@441
   246
  template <typename Iterator, typename Value, typename Key>
deba@441
   247
  void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
deba@441
   248
    using namespace _radix_sort_bits;
deba@441
   249
    RadixSortSelector<Value>::sort(first, last, functor);
deba@441
   250
  }
deba@441
   251
deba@441
   252
  template <typename Iterator>
deba@441
   253
  void radixSort(Iterator first, Iterator last) {
deba@441
   254
    using namespace _radix_sort_bits;
deba@441
   255
    typedef typename std::iterator_traits<Iterator>::value_type Value;
deba@441
   256
    RadixSortSelector<Value>::sort(first, last, Identity<Value>());
deba@441
   257
  }
deba@441
   258
deba@441
   259
  namespace _radix_sort_bits {
deba@441
   260
deba@441
   261
    template <typename Value>
deba@441
   262
    unsigned char valueByte(Value value, int byte) {
deba@441
   263
      return value >> (std::numeric_limits<unsigned char>::digits * byte);
deba@441
   264
    }
deba@441
   265
deba@441
   266
    template <typename Functor, typename Key>
deba@443
   267
    void stableRadixIntroSort(Key *first, Key *last, Key *target,
deba@443
   268
                              int byte, Functor functor) {
alpar@442
   269
      const int size =
alpar@442
   270
        unsigned(std::numeric_limits<unsigned char>::max()) + 1;
deba@441
   271
      std::vector<int> counter(size);
deba@441
   272
      for (int i = 0; i < size; ++i) {
alpar@442
   273
        counter[i] = 0;
deba@441
   274
      }
deba@441
   275
      Key *it = first;
deba@441
   276
      while (first != last) {
alpar@442
   277
        ++counter[valueByte(functor(*first), byte)];
alpar@442
   278
        ++first;
deba@441
   279
      }
deba@441
   280
      int prev, num = 0;
deba@441
   281
      for (int i = 0; i < size; ++i) {
alpar@442
   282
        prev = num;
alpar@442
   283
        num += counter[i];
alpar@442
   284
        counter[i] = prev;
deba@441
   285
      }
deba@441
   286
      while (it != last) {
alpar@442
   287
        target[counter[valueByte(functor(*it), byte)]++] = *it;
alpar@442
   288
        ++it;
deba@441
   289
      }
deba@441
   290
    }
deba@441
   291
deba@441
   292
    template <typename Functor, typename Key>
deba@443
   293
    void signedStableRadixIntroSort(Key *first, Key *last, Key *target,
deba@443
   294
                                    int byte, Functor functor) {
alpar@442
   295
      const int size =
alpar@442
   296
        unsigned(std::numeric_limits<unsigned char>::max()) + 1;
deba@441
   297
      std::vector<int> counter(size);
deba@441
   298
      for (int i = 0; i < size; ++i) {
alpar@442
   299
        counter[i] = 0;
deba@441
   300
      }
deba@441
   301
      Key *it = first;
deba@441
   302
      while (first != last) {
alpar@442
   303
        counter[valueByte(functor(*first), byte)]++;
alpar@442
   304
        ++first;
deba@441
   305
      }
deba@441
   306
      int prev, num = 0;
deba@441
   307
      for (int i = size / 2; i < size; ++i) {
alpar@442
   308
        prev = num;
alpar@442
   309
        num += counter[i];
alpar@442
   310
        counter[i] = prev;
deba@441
   311
      }
deba@441
   312
      for (int i = 0; i < size / 2; ++i) {
alpar@442
   313
        prev = num;
alpar@442
   314
        num += counter[i];
alpar@442
   315
        counter[i] = prev;
deba@441
   316
      }
deba@441
   317
      while (it != last) {
alpar@442
   318
        target[counter[valueByte(functor(*it), byte)]++] = *it;
alpar@442
   319
        ++it;
deba@441
   320
      }
deba@441
   321
    }
deba@441
   322
alpar@442
   323
deba@441
   324
    template <typename Value, typename Iterator, typename Functor>
deba@443
   325
    void stableRadixSignedSort(Iterator first, Iterator last, Functor functor) {
deba@441
   326
      if (first == last) return;
deba@441
   327
      typedef typename std::iterator_traits<Iterator>::value_type Key;
deba@441
   328
      typedef std::allocator<Key> Allocator;
deba@441
   329
      Allocator allocator;
deba@441
   330
deba@441
   331
      int length = std::distance(first, last);
deba@441
   332
      Key* buffer = allocator.allocate(2 * length);
deba@441
   333
      try {
alpar@442
   334
        bool dir = true;
alpar@442
   335
        std::copy(first, last, buffer);
alpar@442
   336
        for (int i = 0; i < int(sizeof(Value)) - 1; ++i) {
alpar@442
   337
          if (dir) {
deba@443
   338
            stableRadixIntroSort(buffer, buffer + length, buffer + length,
deba@443
   339
                                 i, functor);
alpar@442
   340
          } else {
deba@443
   341
            stableRadixIntroSort(buffer + length, buffer + 2 * length, buffer,
deba@443
   342
                                 i, functor);
alpar@442
   343
          }
alpar@442
   344
          dir = !dir;
alpar@442
   345
        }
alpar@442
   346
        if (dir) {
deba@443
   347
          signedStableRadixIntroSort(buffer, buffer + length, buffer + length,
deba@443
   348
                                     sizeof(Value) - 1, functor);
alpar@442
   349
          std::copy(buffer + length, buffer + 2 * length, first);
alpar@442
   350
        }        else {
alpar@444
   351
          signedStableRadixIntroSort(buffer + length, buffer + 2 * length,
deba@443
   352
                                     buffer, sizeof(Value) - 1, functor);
alpar@442
   353
          std::copy(buffer, buffer + length, first);
alpar@442
   354
        }
deba@441
   355
      } catch (...) {
alpar@442
   356
        allocator.deallocate(buffer, 2 * length);
alpar@442
   357
        throw;
deba@441
   358
      }
deba@441
   359
      allocator.deallocate(buffer, 2 * length);
deba@441
   360
    }
deba@441
   361
deba@441
   362
    template <typename Value, typename Iterator, typename Functor>
alpar@444
   363
    void stableRadixUnsignedSort(Iterator first, Iterator last,
deba@443
   364
                                 Functor functor) {
deba@441
   365
      if (first == last) return;
deba@441
   366
      typedef typename std::iterator_traits<Iterator>::value_type Key;
deba@441
   367
      typedef std::allocator<Key> Allocator;
deba@441
   368
      Allocator allocator;
deba@441
   369
deba@441
   370
      int length = std::distance(first, last);
deba@441
   371
      Key *buffer = allocator.allocate(2 * length);
deba@441
   372
      try {
alpar@442
   373
        bool dir = true;
alpar@442
   374
        std::copy(first, last, buffer);
alpar@442
   375
        for (int i = 0; i < int(sizeof(Value)); ++i) {
alpar@442
   376
          if (dir) {
deba@443
   377
            stableRadixIntroSort(buffer, buffer + length,
deba@443
   378
                                 buffer + length, i, functor);
alpar@442
   379
          } else {
deba@443
   380
            stableRadixIntroSort(buffer + length, buffer + 2 * length,
deba@443
   381
                                 buffer, i, functor);
alpar@442
   382
          }
alpar@442
   383
          dir = !dir;
alpar@442
   384
        }
alpar@442
   385
        if (dir) {
alpar@442
   386
          std::copy(buffer, buffer + length, first);
alpar@442
   387
        }        else {
alpar@442
   388
          std::copy(buffer + length, buffer + 2 * length, first);
alpar@442
   389
        }
deba@441
   390
      } catch (...) {
alpar@442
   391
        allocator.deallocate(buffer, 2 * length);
alpar@442
   392
        throw;
deba@441
   393
      }
deba@441
   394
      allocator.deallocate(buffer, 2 * length);
deba@441
   395
    }
deba@441
   396
deba@441
   397
deba@441
   398
alpar@442
   399
    template <typename Value,
alpar@442
   400
              bool sign = std::numeric_limits<Value>::is_signed >
deba@443
   401
    struct StableRadixSortSelector {
deba@441
   402
      template <typename Iterator, typename Functor>
deba@441
   403
      static void sort(Iterator first, Iterator last, Functor functor) {
deba@443
   404
        stableRadixSignedSort<Value>(first, last, functor);
deba@441
   405
      }
deba@441
   406
    };
deba@441
   407
deba@441
   408
    template <typename Value>
deba@443
   409
    struct StableRadixSortSelector<Value, false> {
deba@441
   410
      template <typename Iterator, typename Functor>
deba@441
   411
      static void sort(Iterator first, Iterator last, Functor functor) {
deba@443
   412
        stableRadixUnsignedSort<Value>(first, last, functor);
deba@441
   413
      }
deba@441
   414
    };
deba@441
   415
deba@441
   416
  }
deba@441
   417
deba@441
   418
  /// \ingroup auxalg
deba@441
   419
  ///
alpar@442
   420
  /// \brief Sorts the STL compatible range into ascending order in a stable
alpar@442
   421
  /// way.
deba@441
   422
  ///
alpar@442
   423
  /// This function sorts an STL compatible range into ascending
alpar@442
   424
  /// order according to an integer mapping in the same as radixSort() does.
deba@441
   425
  ///
alpar@442
   426
  /// This sorting algorithm is stable, i.e. the order of two equal
deba@443
   427
  /// elements remains the same after the sorting.
alpar@442
   428
  ///
alpar@442
   429
  /// This sort algorithm  use a radix forward sort on the
deba@441
   430
  /// bytes of the integer number. The algorithm sorts the items
alpar@442
   431
  /// byte-by-byte. First, it counts how many times a byte value occurs
alpar@442
   432
  /// in the container, then it copies the corresponding items to
kpeter@559
   433
  /// another container in asceding order in O(n) time.
deba@441
   434
  ///
kpeter@559
   435
  /// The time complexity of the algorithm is O(log(c)*n) and
kpeter@559
   436
  /// it uses O(n) additional space, where \c c is the
alpar@442
   437
  /// maximal value and \c n is the number of the items in the
alpar@442
   438
  /// container.
deba@441
   439
  ///
alpar@442
   440
deba@441
   441
  /// \param first The begin of the given range.
deba@441
   442
  /// \param last The end of the given range.
deba@441
   443
  /// \param functor An adaptible unary function or a normal function
deba@441
   444
  /// which maps the items to any integer type which can be either
deba@441
   445
  /// signed or unsigned.
alpar@442
   446
  /// \sa radixSort()
deba@441
   447
  template <typename Iterator, typename Functor>
deba@443
   448
  void stableRadixSort(Iterator first, Iterator last, Functor functor) {
deba@441
   449
    using namespace _radix_sort_bits;
deba@441
   450
    typedef typename Functor::result_type Value;
deba@443
   451
    StableRadixSortSelector<Value>::sort(first, last, functor);
deba@441
   452
  }
deba@441
   453
deba@441
   454
  template <typename Iterator, typename Value, typename Key>
deba@443
   455
  void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
deba@441
   456
    using namespace _radix_sort_bits;
deba@443
   457
    StableRadixSortSelector<Value>::sort(first, last, functor);
deba@441
   458
  }
deba@441
   459
deba@441
   460
  template <typename Iterator, typename Value, typename Key>
deba@443
   461
  void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
deba@441
   462
    using namespace _radix_sort_bits;
deba@443
   463
    StableRadixSortSelector<Value>::sort(first, last, functor);
deba@441
   464
  }
deba@441
   465
deba@441
   466
  template <typename Iterator, typename Value, typename Key>
deba@443
   467
  void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
deba@441
   468
    using namespace _radix_sort_bits;
deba@443
   469
    StableRadixSortSelector<Value>::sort(first, last, functor);
deba@441
   470
  }
deba@441
   471
deba@441
   472
  template <typename Iterator, typename Value, typename Key>
deba@443
   473
  void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
deba@441
   474
    using namespace _radix_sort_bits;
deba@443
   475
    StableRadixSortSelector<Value>::sort(first, last, functor);
deba@441
   476
  }
deba@441
   477
deba@441
   478
  template <typename Iterator>
deba@443
   479
  void stableRadixSort(Iterator first, Iterator last) {
deba@441
   480
    using namespace _radix_sort_bits;
deba@441
   481
    typedef typename std::iterator_traits<Iterator>::value_type Value;
deba@443
   482
    StableRadixSortSelector<Value>::sort(first, last, Identity<Value>());
deba@441
   483
  }
deba@441
   484
deba@441
   485
}
deba@441
   486
deba@441
   487
#endif