author Alpar Juttner Tue, 02 Dec 2008 10:17:30 +0000 changeset 442 31d224a3c0af parent 441 4f7224faf3bd child 443 de16f1f2d228
Doc improvements and source unification in radix_sort (#72)
 lemon/radix_sort.h file | annotate | diff | comparison | revisions test/radix_sort_test.cc file | annotate | diff | comparison | revisions
1.1 --- a/lemon/radix_sort.h	Fri Oct 17 23:55:18 2008 +0200
1.2 +++ b/lemon/radix_sort.h	Tue Dec 02 10:17:30 2008 +0000
1.3 @@ -1,6 +1,6 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6   *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9   *
1.11   * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 @@ -37,93 +37,93 @@
1.13      template <typename Value>
1.14      struct Identity {
1.15        const Value& operator()(const Value& val) {
1.16 -	return val;
1.17 +        return val;
1.18        }
1.19      };
1.22      template <typename Value, typename Iterator, typename Functor>
1.23 -    Iterator radixSortPartition(Iterator first, Iterator last,
1.24 -				Functor functor, Value mask) {
1.25 +    Iterator radixSortPartition(Iterator first, Iterator last,
1.26 +                                Functor functor, Value mask) {
1.27        while (first != last && !(functor(*first) & mask)) {
1.28 -	++first;
1.29 +        ++first;
1.30        }
1.31        if (first == last) {
1.32 -	return first;
1.33 +        return first;
1.34        }
1.35        --last;
1.36        while (first != last && (functor(*last) & mask)) {
1.37 -	--last;
1.38 +        --last;
1.39        }
1.40        if (first == last) {
1.41 -	return first;
1.42 +        return first;
1.43        }
1.44        std::iter_swap(first, last);
1.45        ++first;
1.46        if (!(first < last)) {
1.47 -	return first;
1.48 +        return first;
1.49        }
1.50        while (true) {
1.51 -	while (!(functor(*first) & mask)) {
1.52 -	  ++first;
1.53 -	}
1.54 -	--last;
1.55 -	while (functor(*last) & mask) {
1.56 -	  --last;
1.57 -	}
1.58 -	if (!(first < last)) {
1.59 -	  return first;
1.60 -	}
1.61 -	std::iter_swap(first, last);
1.62 -	++first;
1.63 +        while (!(functor(*first) & mask)) {
1.64 +          ++first;
1.65 +        }
1.66 +        --last;
1.67 +        while (functor(*last) & mask) {
1.68 +          --last;
1.69 +        }
1.70 +        if (!(first < last)) {
1.71 +          return first;
1.72 +        }
1.73 +        std::iter_swap(first, last);
1.74 +        ++first;
1.75        }
1.76      }
1.78      template <typename Iterator, typename Functor>
1.79 -    Iterator radixSortSignPartition(Iterator first, Iterator last,
1.80 -				    Functor functor) {
1.81 +    Iterator radixSortSignPartition(Iterator first, Iterator last,
1.82 +                                    Functor functor) {
1.83        while (first != last && functor(*first) < 0) {
1.84 -	++first;
1.85 +        ++first;
1.86        }
1.87        if (first == last) {
1.88 -	return first;
1.89 +        return first;
1.90        }
1.91        --last;
1.92        while (first != last && functor(*last) >= 0) {
1.93 -	--last;
1.94 +        --last;
1.95        }
1.96        if (first == last) {
1.97 -	return first;
1.98 +        return first;
1.99        }
1.100        std::iter_swap(first, last);
1.101        ++first;
1.102        if (!(first < last)) {
1.103 -	return first;
1.104 +        return first;
1.106        while (true) {
1.107 -	while (functor(*first) < 0) {
1.108 -	  ++first;
1.109 -	}
1.110 -	--last;
1.111 -	while (functor(*last) >= 0) {
1.112 -	  --last;
1.113 -	}
1.114 -	if (!(first < last)) {
1.115 -	  return first;
1.116 -	}
1.117 -	std::iter_swap(first, last);
1.118 -	++first;
1.119 +        while (functor(*first) < 0) {
1.120 +          ++first;
1.121 +        }
1.122 +        --last;
1.123 +        while (functor(*last) >= 0) {
1.124 +          --last;
1.125 +        }
1.126 +        if (!(first < last)) {
1.127 +          return first;
1.128 +        }
1.129 +        std::iter_swap(first, last);
1.130 +        ++first;
1.134      template <typename Value, typename Iterator, typename Functor>
1.135 -    void radixIntroSort(Iterator first, Iterator last,
1.136 -			Functor functor, Value mask) {
1.137 +    void radixIntroSort(Iterator first, Iterator last,
1.138 +                        Functor functor, Value mask) {
1.139        while (mask != 0 && last - first > 1) {
1.143 -	first = cut;
1.147 +        first = cut;
1.151 @@ -138,19 +138,19 @@
1.153        mask = ~0; max_digit = 0;
1.154        for (it = first; it != cut; ++it) {
1.156 -	  ++max_digit;
1.158 -	}
1.160 +          ++max_digit;
1.162 +        }
1.164        radixIntroSort(first, cut, functor, 1 << max_digit);
1.166        mask = 0; max_digit = 0;
1.167        for (it = cut; it != last; ++it) {
1.169 -	  ++max_digit;
1.171 -	}
1.173 +          ++max_digit;
1.175 +        }
1.177        radixIntroSort(cut, last, functor, 1 << max_digit);
1.179 @@ -163,21 +163,21 @@
1.181        Iterator it;
1.182        for (it = first; it != last; ++it) {
1.184 -	  ++max_digit;
1.186 -	}
1.188 +          ++max_digit;
1.190 +        }
1.192        radixIntroSort(first, last, functor, 1 << max_digit);
1.196 -    template <typename Value,
1.197 -	      bool sign = std::numeric_limits<Value>::is_signed >
1.198 +    template <typename Value,
1.199 +              bool sign = std::numeric_limits<Value>::is_signed >
1.201        template <typename Iterator, typename Functor>
1.202        static void sort(Iterator first, Iterator last, Functor functor) {
1.206      };
1.208 @@ -185,7 +185,7 @@
1.210        template <typename Iterator, typename Functor>
1.211        static void sort(Iterator first, Iterator last, Functor functor) {
1.215      };
1.217 @@ -195,26 +195,29 @@
1.218    ///
1.219    /// \brief Sorts the STL compatible range into ascending order.
1.220    ///
1.221 -  /// The \c radixSort sorts the STL compatible range into ascending
1.222 -  /// order.  The radix sort algorithm can sort the items which mapped
1.223 -  /// to an integer with an adaptable unary function \c functor and the
1.224 -  /// order will be ascending by these mapped values. As function
1.225 -  /// specialization it is possible to use a normal function instead
1.226 -  /// of the functor object or if the functor is not given it will use
1.227 -  /// an identity function instead.
1.228 +  /// The \c radixSort sorts an STL compatible range into ascending
1.229 +  /// order.  The radix sort algorithm can sort items which are mapped
1.230 +  /// to integers with an adaptable unary function \c functor and the
1.231 +  /// order will be ascending according to these mapped values.
1.232    ///
1.233 -  /// This implemented radix sort is a special quick sort which pivot
1.234 -  /// value is choosen to partite the items on the next
1.235 -  /// bit. Therefore, let be \c c the maximal capacity and \c n the
1.236 -  /// number of the items in the container, the time complexity of the
1.237 -  /// algorithm is \f\$ O(\log(c)n) \f\$ and the additional space
1.238 -  /// complexity is \f\$ O(\log(c)) \f\$.
1.239 +  /// It is also possible to use a normal function instead
1.240 +  /// of the functor object. If the functor is not given it will use
1.241 +  /// the identity function instead.
1.242 +  ///
1.243 +  /// This is a special quick sort algorithm where the pivot
1.244 +  /// values to split the items are choosen to be \f\$ 2^k \f\$ for each \c k.
1.245 +  /// Therefore, the time complexity of the
1.246 +  /// algorithm is \f\$ O(\log(c)n) \f\$ and it uses \f\$ O(\log(c)) \f\$,
1.247 +  /// additional space, where \c c is the maximal value and \c n is the
1.248 +  /// number of the items in the container.
1.249    ///
1.250    /// \param first The begin of the given range.
1.251    /// \param last The end of the given range.
1.252    /// \param functor An adaptible unary function or a normal function
1.253    /// which maps the items to any integer type which can be either
1.254    /// signed or unsigned.
1.255 +  ///
1.256 +  /// \sa counterSort()
1.257    template <typename Iterator, typename Functor>
1.258    void radixSort(Iterator first, Iterator last, Functor functor) {
1.260 @@ -261,63 +264,63 @@
1.263      template <typename Functor, typename Key>
1.264 -    void counterIntroSort(Key *first, Key *last, Key *target,
1.265 -			  int byte, Functor functor) {
1.266 -      const int size =
1.267 -	unsigned(std::numeric_limits<unsigned char>::max()) + 1;
1.268 +    void counterIntroSort(Key *first, Key *last, Key *target,
1.269 +                          int byte, Functor functor) {
1.270 +      const int size =
1.271 +        unsigned(std::numeric_limits<unsigned char>::max()) + 1;
1.272        std::vector<int> counter(size);
1.273        for (int i = 0; i < size; ++i) {
1.274 -	counter[i] = 0;
1.275 +        counter[i] = 0;
1.277        Key *it = first;
1.278        while (first != last) {
1.279 -	++counter[valueByte(functor(*first), byte)];
1.280 -	++first;
1.281 +        ++counter[valueByte(functor(*first), byte)];
1.282 +        ++first;
1.284        int prev, num = 0;
1.285        for (int i = 0; i < size; ++i) {
1.286 -	prev = num;
1.287 -	num += counter[i];
1.288 -	counter[i] = prev;
1.289 +        prev = num;
1.290 +        num += counter[i];
1.291 +        counter[i] = prev;
1.293        while (it != last) {
1.294 -	target[counter[valueByte(functor(*it), byte)]++] = *it;
1.295 -	++it;
1.296 +        target[counter[valueByte(functor(*it), byte)]++] = *it;
1.297 +        ++it;
1.301      template <typename Functor, typename Key>
1.302 -    void signedCounterIntroSort(Key *first, Key *last, Key *target,
1.303 -				int byte, Functor functor) {
1.304 -      const int size =
1.305 -	unsigned(std::numeric_limits<unsigned char>::max()) + 1;
1.306 +    void signedCounterIntroSort(Key *first, Key *last, Key *target,
1.307 +                                int byte, Functor functor) {
1.308 +      const int size =
1.309 +        unsigned(std::numeric_limits<unsigned char>::max()) + 1;
1.310        std::vector<int> counter(size);
1.311        for (int i = 0; i < size; ++i) {
1.312 -	counter[i] = 0;
1.313 +        counter[i] = 0;
1.315        Key *it = first;
1.316        while (first != last) {
1.317 -	counter[valueByte(functor(*first), byte)]++;
1.318 -	++first;
1.319 +        counter[valueByte(functor(*first), byte)]++;
1.320 +        ++first;
1.322        int prev, num = 0;
1.323        for (int i = size / 2; i < size; ++i) {
1.324 -	prev = num;
1.325 -	num += counter[i];
1.326 -	counter[i] = prev;
1.327 +        prev = num;
1.328 +        num += counter[i];
1.329 +        counter[i] = prev;
1.331        for (int i = 0; i < size / 2; ++i) {
1.332 -	prev = num;
1.333 -	num += counter[i];
1.334 -	counter[i] = prev;
1.335 +        prev = num;
1.336 +        num += counter[i];
1.337 +        counter[i] = prev;
1.339        while (it != last) {
1.340 -	target[counter[valueByte(functor(*it), byte)]++] = *it;
1.341 -	++it;
1.342 +        target[counter[valueByte(functor(*it), byte)]++] = *it;
1.343 +        ++it;
1.349      template <typename Value, typename Iterator, typename Functor>
1.350      void counterSignedSort(Iterator first, Iterator last, Functor functor) {
1.351        if (first == last) return;
1.352 @@ -328,30 +331,30 @@
1.353        int length = std::distance(first, last);
1.354        Key* buffer = allocator.allocate(2 * length);
1.355        try {
1.356 -	bool dir = true;
1.357 -	std::copy(first, last, buffer);
1.358 -	for (int i = 0; i < int(sizeof(Value)) - 1; ++i) {
1.359 -	  if (dir) {
1.360 -	    counterIntroSort(buffer, buffer + length, buffer + length,
1.361 -			     i, functor);
1.362 -	  } else {
1.363 -	    counterIntroSort(buffer + length, buffer + 2 * length, buffer,
1.364 -			     i, functor);
1.365 -	  }
1.366 -	  dir = !dir;
1.367 -	}
1.368 -	if (dir) {
1.369 -	  signedCounterIntroSort(buffer, buffer + length, buffer + length,
1.370 -				 sizeof(Value) - 1, functor);
1.371 -	  std::copy(buffer + length, buffer + 2 * length, first);
1.372 -	}	else {
1.373 -	  signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer,
1.374 -				 sizeof(Value) - 1, functor);
1.375 -	  std::copy(buffer, buffer + length, first);
1.376 -	}
1.377 +        bool dir = true;
1.378 +        std::copy(first, last, buffer);
1.379 +        for (int i = 0; i < int(sizeof(Value)) - 1; ++i) {
1.380 +          if (dir) {
1.381 +            counterIntroSort(buffer, buffer + length, buffer + length,
1.382 +                             i, functor);
1.383 +          } else {
1.384 +            counterIntroSort(buffer + length, buffer + 2 * length, buffer,
1.385 +                             i, functor);
1.386 +          }
1.387 +          dir = !dir;
1.388 +        }
1.389 +        if (dir) {
1.390 +          signedCounterIntroSort(buffer, buffer + length, buffer + length,
1.391 +                                 sizeof(Value) - 1, functor);
1.392 +          std::copy(buffer + length, buffer + 2 * length, first);
1.393 +        }        else {
1.394 +          signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer,
1.395 +                                 sizeof(Value) - 1, functor);
1.396 +          std::copy(buffer, buffer + length, first);
1.397 +        }
1.398        } catch (...) {
1.399 -	allocator.deallocate(buffer, 2 * length);
1.400 -	throw;
1.401 +        allocator.deallocate(buffer, 2 * length);
1.402 +        throw;
1.404        allocator.deallocate(buffer, 2 * length);
1.406 @@ -366,38 +369,38 @@
1.407        int length = std::distance(first, last);
1.408        Key *buffer = allocator.allocate(2 * length);
1.409        try {
1.410 -	bool dir = true;
1.411 -	std::copy(first, last, buffer);
1.412 -	for (int i = 0; i < int(sizeof(Value)); ++i) {
1.413 -	  if (dir) {
1.414 -	    counterIntroSort(buffer, buffer + length,
1.415 -			     buffer + length, i, functor);
1.416 -	  } else {
1.417 -	    counterIntroSort(buffer + length, buffer + 2 * length,
1.418 -			     buffer, i, functor);
1.419 -	  }
1.420 -	  dir = !dir;
1.421 -	}
1.422 -	if (dir) {
1.423 -	  std::copy(buffer, buffer + length, first);
1.424 -	}	else {
1.425 -	  std::copy(buffer + length, buffer + 2 * length, first);
1.426 -	}
1.427 +        bool dir = true;
1.428 +        std::copy(first, last, buffer);
1.429 +        for (int i = 0; i < int(sizeof(Value)); ++i) {
1.430 +          if (dir) {
1.431 +            counterIntroSort(buffer, buffer + length,
1.432 +                             buffer + length, i, functor);
1.433 +          } else {
1.434 +            counterIntroSort(buffer + length, buffer + 2 * length,
1.435 +                             buffer, i, functor);
1.436 +          }
1.437 +          dir = !dir;
1.438 +        }
1.439 +        if (dir) {
1.440 +          std::copy(buffer, buffer + length, first);
1.441 +        }        else {
1.442 +          std::copy(buffer + length, buffer + 2 * length, first);
1.443 +        }
1.444        } catch (...) {
1.445 -	allocator.deallocate(buffer, 2 * length);
1.446 -	throw;
1.447 +        allocator.deallocate(buffer, 2 * length);
1.448 +        throw;
1.450        allocator.deallocate(buffer, 2 * length);
1.455 -    template <typename Value,
1.456 -	      bool sign = std::numeric_limits<Value>::is_signed >
1.457 +    template <typename Value,
1.458 +              bool sign = std::numeric_limits<Value>::is_signed >
1.459      struct CounterSortSelector {
1.460        template <typename Iterator, typename Functor>
1.461        static void sort(Iterator first, Iterator last, Functor functor) {
1.462 -	counterSignedSort<Value>(first, last, functor);
1.463 +        counterSignedSort<Value>(first, last, functor);
1.465      };
1.467 @@ -405,7 +408,7 @@
1.468      struct CounterSortSelector<Value, false> {
1.469        template <typename Iterator, typename Functor>
1.470        static void sort(Iterator first, Iterator last, Functor functor) {
1.471 -	counterUnsignedSort<Value>(first, last, functor);
1.472 +        counterUnsignedSort<Value>(first, last, functor);
1.474      };
1.476 @@ -413,34 +416,33 @@
1.478    /// \ingroup auxalg
1.479    ///
1.480 -  /// \brief Sorts stable the STL compatible range into ascending order.
1.481 +  /// \brief Sorts the STL compatible range into ascending order in a stable
1.482 +  /// way.
1.483    ///
1.484 -  /// The \c counterSort sorts the STL compatible range into ascending
1.485 -  /// order.  The counter sort algorithm can sort the items which
1.486 -  /// mapped to an integer with an adaptable unary function \c functor
1.487 -  /// and the order will be ascending by these mapped values. As
1.488 -  /// function specialization it is possible to use a normal function
1.489 -  /// instead of the functor object or if the functor is not given it
1.490 -  /// will use an identity function instead.
1.491 +  /// This function sorts an STL compatible range into ascending
1.492 +  /// order according to an integer mapping in the same as radixSort() does.
1.493    ///
1.494 -  /// The implemented counter sort use a radix forward sort on the
1.495 +  /// This sorting algorithm is stable, i.e. the order of two equal
1.496 +  /// element remains the same after the sorting.
1.497 +  ///
1.498 +  /// This sort algorithm  use a radix forward sort on the
1.499    /// bytes of the integer number. The algorithm sorts the items
1.500 -  /// byte-by-byte, first it counts how many times occurs a byte value
1.501 -  /// in the containerm, and with the occurence number the container
1.502 -  /// can be copied to an other in asceding order in \c O(n) time.
1.503 -  /// Let be \c c the maximal capacity of the integer type and \c n
1.504 -  /// the number of the items in the container, the time complexity of
1.505 -  /// the algorithm is \f\$ O(\log(c)n) \f\$ and the additional space
1.506 -  /// complexity is \f\$ O(n) \f\$.
1.507 +  /// byte-by-byte. First, it counts how many times a byte value occurs
1.508 +  /// in the container, then it copies the corresponding items to
1.509 +  /// another container in asceding order in \c O(n) time.
1.510    ///
1.511 -  /// The sorting algorithm is stable, i.e. the order of two equal
1.512 -  /// element remains the same.
1.513 +  /// The time complexity of the algorithm is \f\$ O(\log(c)n) \f\$ and
1.514 +  /// it uses \f\$ O(n) \f\$, additional space, where \c c is the
1.515 +  /// maximal value and \c n is the number of the items in the
1.516 +  /// container.
1.517    ///
1.519    /// \param first The begin of the given range.
1.520    /// \param last The end of the given range.
1.521    /// \param functor An adaptible unary function or a normal function
1.522    /// which maps the items to any integer type which can be either
1.523    /// signed or unsigned.
1.525    template <typename Iterator, typename Functor>
1.526    void counterSort(Iterator first, Iterator last, Functor functor) {
2.1 --- a/test/radix_sort_test.cc	Fri Oct 17 23:55:18 2008 +0200
2.2 +++ b/test/radix_sort_test.cc	Tue Dec 02 10:17:30 2008 +0000
2.3 @@ -1,6 +1,6 @@
2.4 -/* -*- C++ -*-
2.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.6   *
2.7 - * This file is a part of LEMON, a generic C++ optimization library
2.8 + * This file is a part of LEMON, a generic C++ optimization library.
2.9   *
2.11   * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.12 @@ -81,8 +81,8 @@
2.13        check(data1[i] == data2[n - 1 - i], "Test failed");
2.14      }
2.16 -  }
2.17 -
2.18 +  }
2.19 +
2.20    {
2.21      std::vector<unsigned char> data1(n);
2.22      generateCharSequence(n, data1);
2.23 @@ -121,7 +121,7 @@
2.24      for (int i = 0; i < n; ++i) {
2.25        check(data1[i] == data2[n - 1 - i], "Test failed");
2.26      }
2.27 -  }
2.28 +  }
2.30    {
2.31      std::vector<unsigned char> data1(n);
2.32 @@ -140,7 +140,7 @@
2.34  int main() {