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 
38 namespace permlib {
39 
41 template<class ORDER>
42 class OrderedSorter : public std::binary_function<unsigned long, unsigned long, bool> {
43 public:
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  }
49 protected:
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 
76 class BaseSorter : public OrderedSorter<std::vector<unsigned long> > {
77 public:
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 
113 class BaseSorterByReference : public OrderedSorter<const std::vector<unsigned long>&> {
114 public:
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
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
OrderedSorter(ORDER order)
constructor for reference use
Definition: base_sorter.h:61
STL namespace.
A sorter that sorts a sequence (e.g. ) with respect to a given input ordering (e.g. a base)
Definition: base_sorter.h:113
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
ORDER m_order
array which defines the order of points
Definition: base_sorter.h:68
BaseSorterByReference(const std::vector< unsigned long > &order)
constructor
Definition: base_sorter.h:116
BaseSorter(unsigned int size, InputIterator begin, InputIterator end)
constructor
Definition: base_sorter.h:85
unsigned int m_size
size of domain which the order applies to
Definition: base_sorter.h:66
bool operator()(unsigned long a, unsigned long b) const
true iff a preceeds b in given sequence
Definition: base_sorter.h:45
OrderedSorter(unsigned int size)
constructor for direct vector usage
Definition: base_sorter.h:54
A sorter that sorts a sequence (e.g. ) with respect to a given input ordering (e.g. a base)
Definition: base_sorter.h:76
Definition: abstract_bsgs.h:49