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.
@@ -186,44 +186,47 @@
 		      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);
+		  }
@@ -404,52 +407,51 @@
 		    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);
+		  }

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.

0 comments (0 inline)

RhodeCode

Login to your account

1		/* -- C++ --
	1	/* -- mode: C++; indent-tabs-mode: nil; --
2	2	*
3		* This file is a part of LEMON, a generic C++ optimization library
	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5	5	* Copyright (C) 2003-2008
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.