COPASI API  4.16.103
CSort.h
Go to the documentation of this file.
1 // Copyright (C) 2010 - 2013 by Pedro Mendes, Virginia Tech Intellectual
2 // Properties, Inc., University of Heidelberg, and The University
3 // of Manchester.
4 // All rights reserved.
5 
6 // Copyright (C) 2008 - 2009 by Pedro Mendes, Virginia Tech Intellectual
7 // Properties, Inc., EML Research, gGmbH, University of Heidelberg,
8 // and The University of Manchester.
9 // All rights reserved.
10 
11 // Copyright (C) 2005 - 2007 by Pedro Mendes, Virginia Tech Intellectual
12 // Properties, Inc. and EML Research, gGmbH.
13 // All rights reserved.
14 
15 #ifndef COPASI_CSort
16 #define COPASI_CSort
17 
18 #include <cmath>
19 #include <algorithm>
20 #include <functional>
21 
22 #include "utilities/CVector.h"
23 
24 template<typename RandomAccessIterator>
26 {
27 public:
28  /**
29  * Constructor
30  */
32 
33  /**
34  * Virtual destructor
35  */
36  virtual ~CompareDefault() {};
37 
38  bool operator()(const std::pair< RandomAccessIterator, size_t > & lhs,
39  const std::pair< RandomAccessIterator, size_t > & rhs)
40  {
41  return *lhs.first < *rhs.first;
42  }
43 };
44 
46 {
47 public:
48  /**
49  * Constructor
50  */
52 
53  /**
54  * Virtual destructor
55  */
56  virtual ~CompareDoubleWithNaN() {};
57 
58  bool operator()(const std::pair< C_FLOAT64 *, size_t > & lhs,
59  const std::pair< C_FLOAT64 *, size_t > & rhs)
60  {
61  return
62  isnan(*lhs.first) ?
63  (isnan(*rhs.first) ? lhs.first < rhs.first : false) :
64  (isnan(*rhs.first) ? true : *lhs.first < *rhs.first);
65  }
66 };
67 
68 /**
69  * Sorting method returning a pivot vector instead of performing the sort.
70  * The underlying sorting method is std::sort with the operator < used for
71  * comparison .
72  * @param RandomAccessIterator first
73  * @param RandomAccessIterator last
74  * @param CVector<size_t> & pivot
75  */
76 template <typename RandomAccessIterator>
77 void sortWithPivot(RandomAccessIterator first,
78  RandomAccessIterator last,
79  CVector<size_t> & pivot)
80 {
82 
83  sortWithPivot(first, last, Compare, pivot);
84 
85  return;
86 }
87 
88 /**
89  * Sorting method returning a pivot vector instead of performing the sort.
90  * The underlying sorting method is std::sort with the specified compare
91  * method used for comparison .
92  * @param RandomAccessIterator first
93  * @param RandomAccessIterator last
94  * @param LessThanCompare method
95  * @param CVector<size_t> & pivot
96  */
97 template <typename RandomAccessIterator, typename LessThanCompare>
98 void sortWithPivot(RandomAccessIterator first,
99  RandomAccessIterator last,
100  LessThanCompare compare,
101  CVector<size_t> & pivot)
102 {
103  assert(first < last);
104 
105  // Initialize the two column array to be sorted
107  ToBeSorted.resize(last - first);
108 
109  RandomAccessIterator it;
110  size_t i;
111 
112  typename std::pair<RandomAccessIterator, size_t> * itToBeSorted;
113 
114  for (it = first, i = 0, itToBeSorted = ToBeSorted.array();
115  it != last;
116  ++it, ++i, ++itToBeSorted)
117  {
118  itToBeSorted->first = it;
119  itToBeSorted->second = i;
120  }
121 
122  itToBeSorted = ToBeSorted.array();
123 
124  std::sort(itToBeSorted,
125  itToBeSorted + (last - first),
126  compare);
127 
128  // Copy the resulting pivots to the pivot vector.
129  pivot.resize(last - first);
130  CVector<size_t>::elementType *itPivot = pivot.array();
131  CVector<size_t>::elementType *endPivot = itPivot + (last - first);
132 
133  for (; itPivot != endPivot; ++itToBeSorted, ++itPivot)
134  *itPivot = itToBeSorted->second;
135 
136  return;
137 }
138 
139 /**
140  * Partial sorting method returning a pivot vector instead of performing
141  * the sort. The underlying sorting method is std::partial sort with the
142  * operator < used for * comparison .
143  * @param RandomAccessIterator first
144  * @param RandomAccessIterator middle
145  * @param RandomAccessIterator last
146  * @param CVector<size_t> & pivot
147  */
148 template <typename RandomAccessIterator>
149 void partialSortWithPivot(RandomAccessIterator first,
150  RandomAccessIterator middle,
151  RandomAccessIterator last,
152  CVector<size_t> & pivot)
153 {
155 
156  partialSortWithPivot(first, middle, last, Compare, pivot);
157 
158  return;
159 }
160 
161 /**
162  * Partial sorting method returning a pivot vector instead of performing the
163  * sort. The underlying sorting method is std::partial_sort with the specified
164  * compare method used for comparison .
165  * @param RandomAccessIterator first
166  * @param RandomAccessIterator middle
167  * @param RandomAccessIterator last
168  * @param LessThanCompare method
169  * @param CVector<size_t> & pivot
170  */
171 template <typename RandomAccessIterator, typename LessThanCompare>
172 void partialSortWithPivot(RandomAccessIterator first,
173  RandomAccessIterator middle,
174  RandomAccessIterator last,
175  LessThanCompare compare,
176  CVector<size_t> & pivot)
177 {
178  assert(first < middle && middle <= last);
179 
180  // Initialize the two column array to be sorted
182  ToBeSorted.resize(last - first);
183 
184  RandomAccessIterator it;
185  size_t i;
186 
187  typename std::pair<RandomAccessIterator, size_t> * itToBeSorted;
188 
189  for (it = first, i = 0, itToBeSorted = ToBeSorted.array();
190  it != last;
191  ++it, ++i, ++itToBeSorted)
192  {
193  itToBeSorted->first = it;
194  itToBeSorted->second = i;
195  }
196 
197  itToBeSorted = ToBeSorted.array();
198 
199  std::partial_sort(itToBeSorted,
200  itToBeSorted + (middle - first),
201  itToBeSorted + (last - first),
202  compare);
203 
204  // Copy the resulting pivots to the pivot vector.
205  pivot.resize(last - first);
206  CVector<size_t>::elementType *itPivot = pivot.array();
207  CVector<size_t>::elementType *endPivot = itPivot + (last - first);
208 
209  for (; itPivot != endPivot; ++itToBeSorted, ++itPivot)
210  *itPivot = itToBeSorted->second;
211 
212  return;
213 }
214 
215 /**
216  * The base functor providing a swap method used in the applyPivot methods.
217  */
218 template <typename IndexType, typename ReturnType>
220 {
221 protected:
222  /**
223  * Default constructor
224  */
226  mpSwap(NULL)
227  {}
228 
229 public:
230  /**
231  * Specific constructor
232  * @param ReturnType (*swap) (IndexType, IndexType)
233  */
234  FSwapBase(ReturnType(*swap)(IndexType, IndexType)):
235  mpSwap(swap)
236  {}
237 
238  /**
239  * Virtual destructor
240  */
241  virtual ~FSwapBase() {};
242 
243  /**
244  * Operator wrapping the provided swap method
245  * @param IndexType to
246  * @param IndexType from
247  * @return ReturnType
248  */
249  virtual void operator()(IndexType to, IndexType from)
250  {
251  (*mpSwap)(to, from);
252  return;
253  }
254 
255 private:
256  /**
257  * A pointer to the swap method
258  */
259  ReturnType(*mpSwap)(IndexType, IndexType);
260 };
261 
262 /**
263  * A derived functor providing means to use a class member as the swap method
264  * to be used in the applyPivot methods.
265  */
266 template <typename ClassType, typename IndexType, typename ReturnType>
267 class FSwapClass : public FSwapBase<IndexType, ReturnType>
268 {
269 protected:
270  /**
271  * Default constructor
272  */
274  FSwapBase<IndexType, ReturnType>(),
275  mpType(NULL),
276  mpSwap(NULL)
277  {}
278 
279 public:
280  /**
281  * Specific constructor
282  * @param ClassType * pType
283  * @param ReturnType (ClassType::*swap) (IndexType, IndexType)
284  */
285  FSwapClass(ClassType * pType, ReturnType(ClassType::*swap)(IndexType, IndexType)):
286  FSwapBase<IndexType, ReturnType>(),
287  mpType(pType),
288  mpSwap(swap)
289  {}
290 
291  /**
292  * Virtual destructor
293  */
294  virtual ~FSwapClass() {};
295 
296  /**
297  * Operator wrapping the provided class member swap method
298  * @param IndexType to
299  * @param IndexType from
300  * @return ReturnType
301  */
302  virtual void operator()(IndexType to, IndexType from)
303  {
304  (*mpType.*mpSwap)(to, from);
305  return;
306  }
307 
308 private:
309  /**
310  * A pointer to the class.
311  */
312  ClassType * mpType;
313 
314  /**
315  * A pointer to the class member swap method.
316  */
317  ReturnType(ClassType::*mpSwap)(IndexType, IndexType);
318 };
319 
320 /**
321  * Reorder the elements according to the provided pivots
322  * The swap method must be of the form:
323  * ReturnType operator() (size_t to, size_t from)
324  * where the ReturnType is not used and therefore arbitrary. Objects of
325  * type FSwapBase are suitable candidates.
326  * @param const CVector<size_t> & pivot
327  * @param SwapMethod swap
328  * @return bool success
329  */
330 template <typename SwapMethod>
331 bool applyPivot(const CVector<size_t> & pivot,
332  SwapMethod swap)
333 {
334  CVector< bool > Applied(pivot.size());
335  Applied = false;
336 
337  size_t i, imax = pivot.size();
338  size_t to;
339  size_t from;
340 
341  for (i = 0; i < imax; i++)
342  if (!Applied[i])
343  {
344  to = i;
345  from = pivot[to];
346 
347  while (from != i)
348  {
349  swap(to, from);
350  Applied[to] = true;
351 
352  to = from;
353  from = pivot[to];
354  }
355 
356  Applied[to] = true;
357  }
358 
359  return true;
360 }
361 
362 /**
363  * Partial reordering of the first 'ordered' elements according to the
364  * provided pivots.
365  * The swap method must be of the form:
366  * ReturnType operator() (size_t to, size_t from)
367  * where the ReturnType is not used and therefore arbitrary. Objects of
368  * type FSwapBase are suitable candidates.
369  * @param const CVector<size_t> & pivot
370  * @param const size_t & ordered
371  * @param SwapMethod swap
372  * @return bool success
373  */
374 template <typename SwapMethod>
376  const size_t & ordered,
377  SwapMethod swap)
378 {
379  CVector< bool > Applied(pivot.size());
380  Applied = false;
381 
382  size_t i;
383  size_t to;
384  size_t from;
385 
386  for (i = 0; i < ordered; i++)
387  if (!Applied[i])
388  {
389  to = i;
390  from = pivot[to];
391 
392  while (from != i)
393  {
394  if (to < ordered || from < ordered)
395  {
396  swap(to, from);
397  Applied[to] = true;
398 
399  to = from;
400  }
401 
402  from = pivot[from];
403  }
404 
405  Applied[to] = true;
406  }
407 
408  return true;
409 }
410 
411 #endif // COPASI_CSort
void sortWithPivot(RandomAccessIterator first, RandomAccessIterator last, CVector< size_t > &pivot)
Definition: CSort.h:77
FSwapBase()
Definition: CSort.h:225
ClassType * mpType
Definition: CSort.h:312
bool operator()(const std::pair< RandomAccessIterator, size_t > &lhs, const std::pair< RandomAccessIterator, size_t > &rhs)
Definition: CSort.h:38
virtual ~FSwapBase()
Definition: CSort.h:241
bool operator()(const std::pair< C_FLOAT64 *, size_t > &lhs, const std::pair< C_FLOAT64 *, size_t > &rhs)
Definition: CSort.h:58
virtual void operator()(IndexType to, IndexType from)
Definition: CSort.h:302
FSwapClass(ClassType *pType, ReturnType(ClassType::*swap)(IndexType, IndexType))
Definition: CSort.h:285
void resize(size_t size, const bool &copy=false)
Definition: CVector.h:301
bool applyPartialPivot(const CVector< size_t > &pivot, const size_t &ordered, SwapMethod swap)
Definition: CSort.h:375
virtual ~FSwapClass()
Definition: CSort.h:294
CompareDefault()
Definition: CSort.h:31
ReturnType(* mpSwap)(IndexType, IndexType)
Definition: CSort.h:259
virtual void operator()(IndexType to, IndexType from)
Definition: CSort.h:249
ReturnType(ClassType::* mpSwap)(IndexType, IndexType)
Definition: CSort.h:317
void partialSortWithPivot(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, CVector< size_t > &pivot)
Definition: CSort.h:149
FSwapBase(ReturnType(*swap)(IndexType, IndexType))
Definition: CSort.h:234
size_t size() const
Definition: CVector.h:100
bool applyPivot(const CVector< size_t > &pivot, SwapMethod swap)
Definition: CSort.h:331
CType * array()
Definition: CVector.h:139
virtual ~CompareDoubleWithNaN()
Definition: CSort.h:56
FSwapClass()
Definition: CSort.h:273
virtual ~CompareDefault()
Definition: CSort.h:36