permlib 0.2.9
Library for permutation computations
base_sorter.h
1// ---------------------------------------------------------------------------
2//
3// This file is part of PermLib.
4//
5// Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
6// All rights reserved.
7//
8// Redistribution and use in source and binary forms, with or without
9// modification, are permitted provided that the following conditions
10// are met:
11// 1. Redistributions of source code must retain the above copyright
12// notice, this list of conditions and the following disclaimer.
13// 2. Redistributions in binary form must reproduce the above copyright
14// notice, this list of conditions and the following disclaimer in the
15// documentation and/or other materials provided with the distribution.
16// 3. The name of the author may not be used to endorse or promote products
17// derived from this software without specific prior written permission.
18//
19// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29//
30// ---------------------------------------------------------------------------
31
32
33#ifndef BASESORTER_H
34#define BASESORTER_H
35
36#include <boost/utility.hpp>
37
38namespace permlib {
39
41template<class ORDER>
42class OrderedSorter : public std::binary_function<unsigned long, unsigned long, bool> {
43public:
45 bool operator() (unsigned long a, unsigned long b) const {
46 BOOST_ASSERT(a < m_size && b < m_size);
47 return m_order[a] < m_order[b];
48 }
49protected:
51
54 explicit OrderedSorter(unsigned int size)
55 : m_size(size),
56 // initialize m_size elements with value m_size
58 {}
59
61 explicit OrderedSorter(ORDER order)
62 : m_size(order.size()), m_order(order)
63 {}
64
66 unsigned int m_size;
68 ORDER m_order;
69};
70
72
76class BaseSorter : public OrderedSorter<std::vector<unsigned long> > {
77public:
79
84 template <class InputIterator>
85 BaseSorter(unsigned int size, InputIterator begin, InputIterator end)
86 : OrderedSorter<std::vector<unsigned long> >(size)
87 {
88 fillOrder(begin, end, m_order);
89 }
90
92
97 template <class InputIterator>
98 static void fillOrder(InputIterator begin, InputIterator end, std::vector<unsigned long>& order) {
99 InputIterator it;
100 unsigned int i = 0;
101 // base elements first
102 for (it = begin; it != end; ++it) {
103 order[*it] = ++i;
104 }
105 }
106};
107
108
110
113class BaseSorterByReference : public OrderedSorter<const std::vector<unsigned long>&> {
114public:
116 explicit BaseSorterByReference(const std::vector<unsigned long>& order) : OrderedSorter<const std::vector<unsigned long>& >(order)
117 { }
118
120 template <class InputIterator>
121 static std::vector<unsigned long> createOrder(unsigned int size, InputIterator begin, InputIterator end) {
122 std::vector<unsigned long> order(size,size);
123 BaseSorter::fillOrder(begin, end, order);
124 return order;
125 }
126};
127
128}
129
130#endif // -- BASESORTER_H
A sorter that sorts a sequence (e.g. ) with respect to a given input ordering (e.g....
Definition: base_sorter.h:113
BaseSorterByReference(const std::vector< unsigned long > &order)
constructor
Definition: base_sorter.h:116
static std::vector< unsigned long > createOrder(unsigned int size, InputIterator begin, InputIterator end)
constructs an ordering array with the same parameters as BaseSorter for use with BaseSorterByReferenc...
Definition: base_sorter.h:121
A sorter that sorts a sequence (e.g. ) with respect to a given input ordering (e.g....
Definition: base_sorter.h:76
BaseSorter(unsigned int size, InputIterator begin, InputIterator end)
constructor
Definition: base_sorter.h:85
static void fillOrder(InputIterator begin, InputIterator end, std::vector< unsigned long > &order)
constructs an ordering array
Definition: base_sorter.h:98
A sorter that sorts a sequence with respect to a given input ordering.
Definition: base_sorter.h:42
unsigned int m_size
size of domain which the order applies to
Definition: base_sorter.h:66
OrderedSorter(unsigned int size)
constructor for direct vector usage
Definition: base_sorter.h:54
bool operator()(unsigned long a, unsigned long b) const
true iff a preceeds b in given sequence
Definition: base_sorter.h:45
OrderedSorter(ORDER order)
constructor for reference use
Definition: base_sorter.h:61
ORDER m_order
array which defines the order of points
Definition: base_sorter.h:68
STL namespace.