Doc improvements and source unification in radix_sort (#72)
authorAlpar Juttner <alpar@cs.elte.hu>
Tue, 02 Dec 2008 10:17:30 +0000
changeset 46531d224a3c0af
parent 464 4f7224faf3bd
child 466 de16f1f2d228
Doc improvements and source unification in radix_sort (#72)
lemon/radix_sort.h
test/radix_sort_test.cc
     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.10   * Copyright (C) 2003-2008
    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.20  
    1.21  
    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.77  
    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.105        }
   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.131        }
   1.132      }
   1.133  
   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.140 -	Iterator cut = radixSortPartition(first, last, functor, mask);
   1.141 -	mask >>= 1;
   1.142 -	radixIntroSort(first, cut, functor, mask);
   1.143 -	first = cut;
   1.144 +        Iterator cut = radixSortPartition(first, last, functor, mask);
   1.145 +        mask >>= 1;
   1.146 +        radixIntroSort(first, cut, functor, mask);
   1.147 +        first = cut;
   1.148        }
   1.149      }
   1.150  
   1.151 @@ -138,19 +138,19 @@
   1.152  
   1.153        mask = ~0; max_digit = 0;
   1.154        for (it = first; it != cut; ++it) {
   1.155 -	while ((mask & functor(*it)) != mask) {
   1.156 -	  ++max_digit;
   1.157 -	  mask <<= 1;
   1.158 -	}
   1.159 +        while ((mask & functor(*it)) != mask) {
   1.160 +          ++max_digit;
   1.161 +          mask <<= 1;
   1.162 +        }
   1.163        }
   1.164        radixIntroSort(first, cut, functor, 1 << max_digit);
   1.165  
   1.166        mask = 0; max_digit = 0;
   1.167        for (it = cut; it != last; ++it) {
   1.168 -	while ((mask | functor(*it)) != mask) {
   1.169 -	  ++max_digit;
   1.170 -	  mask <<= 1; mask |= 1;
   1.171 -	}
   1.172 +        while ((mask | functor(*it)) != mask) {
   1.173 +          ++max_digit;
   1.174 +          mask <<= 1; mask |= 1;
   1.175 +        }
   1.176        }
   1.177        radixIntroSort(cut, last, functor, 1 << max_digit);
   1.178      }
   1.179 @@ -163,21 +163,21 @@
   1.180  
   1.181        Iterator it;
   1.182        for (it = first; it != last; ++it) {
   1.183 -	while ((mask | functor(*it)) != mask) {
   1.184 -	  ++max_digit;
   1.185 -	  mask <<= 1; mask |= 1;
   1.186 -	}
   1.187 +        while ((mask | functor(*it)) != mask) {
   1.188 +          ++max_digit;
   1.189 +          mask <<= 1; mask |= 1;
   1.190 +        }
   1.191        }
   1.192        radixIntroSort(first, last, functor, 1 << max_digit);
   1.193      }
   1.194  
   1.195  
   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.200      struct RadixSortSelector {
   1.201        template <typename Iterator, typename Functor>
   1.202        static void sort(Iterator first, Iterator last, Functor functor) {
   1.203 -	radixSignedSort<Value>(first, last, functor);
   1.204 +        radixSignedSort<Value>(first, last, functor);
   1.205        }
   1.206      };
   1.207  
   1.208 @@ -185,7 +185,7 @@
   1.209      struct RadixSortSelector<Value, false> {
   1.210        template <typename Iterator, typename Functor>
   1.211        static void sort(Iterator first, Iterator last, Functor functor) {
   1.212 -	radixUnsignedSort<Value>(first, last, functor);
   1.213 +        radixUnsignedSort<Value>(first, last, functor);
   1.214        }
   1.215      };
   1.216  
   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.259      using namespace _radix_sort_bits;
   1.260 @@ -261,63 +264,63 @@
   1.261      }
   1.262  
   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.276        }
   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.283        }
   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.292        }
   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.298        }
   1.299      }
   1.300  
   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.314        }
   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.321        }
   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.330        }
   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.338        }
   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.344        }
   1.345      }
   1.346  
   1.347 -  
   1.348 +
   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.403        }
   1.404        allocator.deallocate(buffer, 2 * length);
   1.405      }
   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.449        }
   1.450        allocator.deallocate(buffer, 2 * length);
   1.451      }
   1.452  
   1.453  
   1.454  
   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.464        }
   1.465      };
   1.466  
   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.473        }
   1.474      };
   1.475  
   1.476 @@ -413,34 +416,33 @@
   1.477  
   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.518 +
   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.524 +  /// \sa radixSort()
   1.525    template <typename Iterator, typename Functor>
   1.526    void counterSort(Iterator first, Iterator last, Functor functor) {
   1.527      using namespace _radix_sort_bits;
     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.10   * Copyright (C) 2003-2008
    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.15  
    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.29  
    2.30    {
    2.31      std::vector<unsigned char> data1(n);
    2.32 @@ -140,7 +140,7 @@
    2.33  
    2.34  int main() {
    2.35  
    2.36 -  checkRadixSort();  
    2.37 +  checkRadixSort();
    2.38    checkCounterSort();
    2.39  
    2.40    return 0;