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//
41template<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