LEMON/LEMON-main Changeset - r442:31d224a3c0af

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r442:31d224a3c0af

« 441:4f7224

443:de16f1 »

r442:31d224a3c0af

Tue, 02 Dec 2008 11:17:30

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Doc improvements and source unification in radix_sort (#72)

0 2 0

default

2 files changed with 37 insertions and 35 deletions:

lemon/radix_sort.h

test/radix_sort_test.cc

↑ Collapse diff ↑

lemon/radix_sort.h

Show inline comments

 		/* -*- C++ -*-
+		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef RADIX_SORT_H
 		#define RADIX_SORT_H
 		/// \ingroup auxalg
 		/// \file
 		/// \brief Radix sort
 		///
 		/// Linear time sorting algorithms
 		#include <vector>
 		#include <limits>
 		#include <iterator>
 		#include <algorithm>
 		namespace lemon {
 		  namespace _radix_sort_bits {
@@ -166,84 +166,87 @@
 			while ((mask | functor(*it)) != mask) {
 			  ++max_digit;
 			  mask <<= 1; mask |= 1;
+			}
+		      }
 		      radixIntroSort(first, last, functor, 1 << max_digit);
+		    }
 		    template <typename Value,
 			      bool sign = std::numeric_limits<Value>::is_signed >
 		    struct RadixSortSelector {
 		      template <typename Iterator, typename Functor>
 		      static void sort(Iterator first, Iterator last, Functor functor) {
 			radixSignedSort<Value>(first, last, functor);
+		      }
 		    };
 		    template <typename Value>
 		    struct RadixSortSelector<Value, false> {
 		      template <typename Iterator, typename Functor>
 		      static void sort(Iterator first, Iterator last, Functor functor) {
 			radixUnsignedSort<Value>(first, last, functor);
+		      }
 		    };
+		  }
 		  /// \ingroup auxalg
 		  ///
 		  /// \brief Sorts the STL compatible range into ascending order.
 		  ///
 		  /// The \c radixSort sorts the STL compatible range into ascending
 		  /// order.  The radix sort algorithm can sort the items which mapped
 		  /// to an integer with an adaptable unary function \c functor and the
 		  /// order will be ascending by these mapped values. As function
 		  /// specialization it is possible to use a normal function instead
 		  /// of the functor object or if the functor is not given it will use
-		  /// an identity function instead.
+		  /// The \c radixSort sorts an STL compatible range into ascending
 		  /// order.  The radix sort algorithm can sort items which are mapped
 		  /// to integers with an adaptable unary function \c functor and the
 		  /// order will be ascending according to these mapped values.
 		  ///
 		  /// This implemented radix sort is a special quick sort which pivot
 		  /// value is choosen to partite the items on the next
 		  /// bit. Therefore, let be \c c the maximal capacity and \c n the
 		  /// number of the items in the container, the time complexity of the
 		  /// algorithm is \f$ O(\log(c)n) \f$ and the additional space
 		  /// complexity is \f$ O(\log(c)) \f$.
 		  /// It is also possible to use a normal function instead
 		  /// of the functor object. If the functor is not given it will use
 		  /// the identity function instead.
 		  ///
 		  /// This is a special quick sort algorithm where the pivot
 		  /// values to split the items are choosen to be \f$ 2^k \f$ for each \c k.
 		  /// Therefore, the time complexity of the
 		  /// algorithm is \f$ O(\log(c)n) \f$ and it uses \f$ O(\log(c)) \f$,
 		  /// additional space, where \c c is the maximal value and \c n is the
 		  /// number of the items in the container.
 		  ///
 		  /// \param first The begin of the given range.
 		  /// \param last The end of the given range.
 		  /// \param functor An adaptible unary function or a normal function
 		  /// which maps the items to any integer type which can be either
 		  /// signed or unsigned.
 		  ///
 		  /// \sa counterSort()
 		  template <typename Iterator, typename Functor>
 		  void radixSort(Iterator first, Iterator last, Functor functor) {
 		    using namespace _radix_sort_bits;
 		    typedef typename Functor::result_type Value;
 		    RadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
 		  void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
 		    using namespace _radix_sort_bits;
 		    RadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
 		  void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
 		    using namespace _radix_sort_bits;
 		    RadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
 		  void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
 		    using namespace _radix_sort_bits;
 		    RadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
 		  void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
 		    using namespace _radix_sort_bits;
 		    RadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator>
@@ -384,92 +387,91 @@
 			  std::copy(buffer + length, buffer + 2 * length, first);
+			}
 		      } catch (...) {
 			allocator.deallocate(buffer, 2 * length);
 			throw;
+		      }
 		      allocator.deallocate(buffer, 2 * length);
+		    }
 		    template <typename Value,
 			      bool sign = std::numeric_limits<Value>::is_signed >
 		    struct CounterSortSelector {
 		      template <typename Iterator, typename Functor>
 		      static void sort(Iterator first, Iterator last, Functor functor) {
 			counterSignedSort<Value>(first, last, functor);
+		      }
 		    };
 		    template <typename Value>
 		    struct CounterSortSelector<Value, false> {
 		      template <typename Iterator, typename Functor>
 		      static void sort(Iterator first, Iterator last, Functor functor) {
 			counterUnsignedSort<Value>(first, last, functor);
+		      }
 		    };
+		  }
 		  /// \ingroup auxalg
 		  ///
-		  /// \brief Sorts stable the STL compatible range into ascending order.
+		  /// \brief Sorts the STL compatible range into ascending order in a stable
 		  /// way.
 		  ///
 		  /// The \c counterSort sorts the STL compatible range into ascending
 		  /// order.  The counter sort algorithm can sort the items which
 		  /// mapped to an integer with an adaptable unary function \c functor
 		  /// and the order will be ascending by these mapped values. As
 		  /// function specialization it is possible to use a normal function
 		  /// instead of the functor object or if the functor is not given it
-		  /// will use an identity function instead.
+		  /// This function sorts an STL compatible range into ascending
 		  /// order according to an integer mapping in the same as radixSort() does.
 		  ///
-		  /// The implemented counter sort use a radix forward sort on the
+		  /// This sorting algorithm is stable, i.e. the order of two equal
 		  /// element remains the same after the sorting.
 		  ///
 		  /// This sort algorithm  use a radix forward sort on the
 		  /// bytes of the integer number. The algorithm sorts the items
 		  /// byte-by-byte, first it counts how many times occurs a byte value
 		  /// in the containerm, and with the occurence number the container
 		  /// can be copied to an other in asceding order in \c O(n) time.
 		  /// Let be \c c the maximal capacity of the integer type and \c n
 		  /// the number of the items in the container, the time complexity of
 		  /// the algorithm is \f$ O(\log(c)n) \f$ and the additional space
-		  /// complexity is \f$ O(n) \f$.
+		  /// byte-by-byte. First, it counts how many times a byte value occurs
 		  /// in the container, then it copies the corresponding items to
 		  /// another container in asceding order in \c O(n) time.
 		  ///
 		  /// The sorting algorithm is stable, i.e. the order of two equal
 		  /// element remains the same.
 		  /// The time complexity of the algorithm is \f$ O(\log(c)n) \f$ and
 		  /// it uses \f$ O(n) \f$, additional space, where \c c is the
 		  /// maximal value and \c n is the number of the items in the
 		  /// container.
 		  ///
 		  /// \param first The begin of the given range.
 		  /// \param last The end of the given range.
 		  /// \param functor An adaptible unary function or a normal function
 		  /// which maps the items to any integer type which can be either
 		  /// signed or unsigned.
 		  /// \sa radixSort()
 		  template <typename Iterator, typename Functor>
 		  void counterSort(Iterator first, Iterator last, Functor functor) {
 		    using namespace _radix_sort_bits;
 		    typedef typename Functor::result_type Value;
 		    CounterSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
 		  void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) {
 		    using namespace _radix_sort_bits;
 		    CounterSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
 		  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
 		    using namespace _radix_sort_bits;
 		    CounterSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
 		  void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
 		    using namespace _radix_sort_bits;
 		    CounterSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
 		  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
 		    using namespace _radix_sort_bits;
 		    CounterSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator>

test/radix_sort_test.cc

Show inline comments

 		/* -*- C++ -*-
+		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <lemon/time_measure.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/maps.h>
 		#include <lemon/radix_sort.h>
 		#include <lemon/math.h>
 		#include "test_tools.h"
 		#include <vector>
 		#include <algorithm>
 		using namespace lemon;
 		static const int n = 10000;
 		struct Negate {
 		  typedef int argument_type;

0 comments (0 inline)

RhodeCode

Login to your account