functional.h
Go to the documentation of this file.
1 /*!
2  *
3  *
4  * \brief Small General algorithm collection.
5  *
6  *
7  *
8  *
9  * \author Oswin Krause
10  * \date 2012
11  *
12  *
13  * \par Copyright 1995-2015 Shark Development Team
14  *
15  * <BR><HR>
16  * This file is part of Shark.
17  * <http://image.diku.dk/shark/>
18  *
19  * Shark is free software: you can redistribute it and/or modify
20  * it under the terms of the GNU Lesser General Public License as published
21  * by the Free Software Foundation, either version 3 of the License, or
22  * (at your option) any later version.
23  *
24  * Shark is distributed in the hope that it will be useful,
25  * but WITHOUT ANY WARRANTY; without even the implied warranty of
26  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27  * GNU Lesser General Public License for more details.
28  *
29  * You should have received a copy of the GNU Lesser General Public License
30  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
31  *
32  */
33 #ifndef SHARK_CORE_FUNCTIONAL_H
34 #define SHARK_CORE_FUNCTIONAL_H
35 
36 #include <boost/range/numeric.hpp>
37 #include <boost/range/algorithm/nth_element.hpp>
38 #include <boost/bind.hpp>
40 #include <algorithm>
41 #include <shark/Rng/GlobalRng.h>
42 namespace shark{
43 
44 ///\brief random_shuffle algorithm which stops after acquiring the random subsequence for [begin,middle)
45 template<class RandomAccessIterator, class Rng>
46 void partial_shuffle(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end, Rng& rng){
47  std::random_shuffle(begin,end,rng);
48  // todo: test the algorithm below!
49  //~ typedef typename std::iterator_traits<Iterator>::difference_type difference_type;
50  //~ difference_type n = middle - begin;
51  //~ for (; begin != middle; ++begin,--n) {
52 
53  //~ using std::swap;
54  //~ swap(*begin, begin[rng(n)]);
55  //~ }
56 }
57 
58 ///\brief random_shuffle algorithm which stops after acquiring the random subsequence for [begin,middle)
59 template<class Iterator, class Rng>
60 void shuffle(Iterator begin, Iterator end, Rng& rng){
61  using std::swap;
62  Iterator next = begin;
63  for (std::size_t index = 2; ++next != end; ++index){
64  swap(*next, *(begin + rng(index)));
65  }
66 }
67 
68 
69 ///\brief random_shuffle algorithm which stops after acquiring the random subsequence for [begin,middle)
70 template<class RandomAccessIterator>
71 void partial_shuffle(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end){
72  DiscreteUniform<Rng::rng_type> uni(Rng::globalRng,0,1);
73  partial_shuffle(begin,middle,end,uni);
74 }
75 
76 ///\brief Returns the iterator to the median element. after this call, the range is partially ordered.
77 ///
78 ///After the call, all elements left of the median element are
79 ///guaranteed to be <= median and all element on the right are >= median.
80 
81 template<class Range>
82 typename boost::range_iterator<Range>::type median_element(Range& range){
83  typedef typename boost::range_iterator<Range>::type iterator;
84 
85  std::size_t size = shark::size(range);
86  std::size_t medianPos = (size+1)/2;
87  iterator medianIter = boost::begin(range)+medianPos;
88 
89  boost::nth_element(range,medianIter);
90 
91  return medianIter;
92 }
93 
94 template<class Range>
95 typename boost::range_iterator<Range>::type median_element(Range const& rangeAdaptor){
96  Range adaptorCopy(rangeAdaptor);
97  return median_element(adaptorCopy);
98 }
99 /// \brief Partitions a range in two parts as equal in size as possible.
100 ///
101 /// The Algorithm partitions the range and returns the splitpoint. The elements in the range
102 /// are ordered such that all elements in [begin,splitpoint) < [splitpoint,end).
103 /// This partition is done such that the ranges are as equally sized as possible.
104 /// It is guaranteed that the left range is not empty. However, if the range consists only
105 /// of equal elements, the return value will be the end iterator indicating that there is no
106 /// split possible.
107 /// The whole algorithm runs in linear time by iterating 2 times over the sequence.
108 template<class Range>
109 typename boost::range_iterator<Range>::type partitionEqually(Range& range){
110  typedef typename boost::range_iterator<Range>::type iterator;
111  typedef typename boost::iterator_value<iterator>::type value_type;
112 
113  iterator begin = boost::begin(range);
114  iterator end = boost::end(range);
115  iterator medianIter = median_element(range);
116 
117  // in 99% of the cases we would be done right now. in the remaining 1% the median element is
118  // not unique so we partition the left and the right such that all copies are ordered in the middle
119  value_type median = *medianIter;
120  iterator left = std::partition(begin,medianIter,boost::bind(std::less<value_type>(),_1,median));
121  iterator right = std::partition(medianIter,end,boost::bind(std::equal_to<value_type>(),_1,median));
122 
123  // we guarantee that the left range is not empty
124  if(left == begin){
125  return right;
126  }
127 
128  // now we return left or right, maximizing size balance
129  if (left - begin >= end - right)
130  return left;
131  else
132  return right;
133 }
134 
135 ///\brief Partitions a range in two parts as equal in size as possible and returns it's result
136 ///
137 ///This the verison for adapted ranges.
138 template<class Range>
139 typename boost::range_iterator<Range>::type partitionEqually(Range const& rangeAdaptor){
140  Range adaptorCopy(rangeAdaptor);
141  return partitionEqually(adaptorCopy);
142 }
143 }
144 #endif