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