libStatGen Software  1
InplaceMerge.h
1 /*
2  * Copyright (C) 2010 Regents of the University of Michigan
3  *
4  * This program is free software: you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation, either version 3 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program. If not, see <http://www.gnu.org/licenses/>.
16  */
17 
18 #ifndef _INPLACE_MERGE_H
19 #define _INPLACE_MERGE_H
20 
21 #include <algorithm>
22 #if defined(DEBUG_INPLACE_MERGE)
23 #include "Generic.h"
24 #include <iostream>
25 #endif
26 #include <stdexcept>
27 #include <vector>
28 
29 
30 
31 //
32 // given a partially ordered vector of values, use
33 // inplace_merge to merge the ordered subsets together in some
34 // reasonable fashion.
35 //
36 // On output, values is sorted in ascending order.
37 //
38 // the counts vector is also modified, the result being
39 // undefined, except that counts[0] == values.size() at final exit.
40 //
41 template<typename T> void inplace_merge(
42  std::vector<int> &indeces,
43  std::vector<int> &counts,
44  int first,
45  int last,
46  std::vector<T> &values)
47 {
48  if (first == (last)) return; // empty set -> no merge
49  if (first == (last-1)) return; // only one set present -> no merge
50 
51  // here we see if we have non-adjacent sets to merge,
52  // if so, do them independently, then we can do a final
53  // merge next
54  if (first != (last - 2))
55  {
56  int middle = (first + last) / 2;
57  inplace_merge(indeces, counts, middle, last, values);
58 #if defined(DEBUG_INPLACE_MERGE)
59  std::cout << values;
60 #endif
61  inplace_merge(indeces, counts, first, middle, values);
62 #if defined(DEBUG_INPLACE_MERGE)
63  std::cout << values;
64 #endif
65 
66  // get ready to drop through to below code which will
67  // merge our two merged subsets
68  last = middle + 1;
69  }
70 
71  // inplace_merge just two adjacent sets
72  typename std::vector<T>::iterator startIterator = values.begin()+indeces[first];
73  typename std::vector<T>::iterator middleIterator = values.begin() + indeces[last-1];
74  typename std::vector<T>::iterator endIterator = values.begin() + indeces[last-1] + counts[last - 1];
75  std::inplace_merge(startIterator, middleIterator, endIterator);
76  counts[first] += counts[last - 1];
77 #if defined(DEBUG_INPLACE_MERGE)
78  std::cout << values;
79 #endif
80 
81  return;
82 }
83 
84 #endif