flow-cutter/id_sort.h at master · kit-algo/flow-cutter · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#ifndef ID_SORT_H
#define ID_SORT_H

#include "array_id_func.h"
#include <cassert>

template<class InIter, class OutIter, class GetID>
void stable_sort_copy_by_id(
	InIter in_begin, InIter in_end,
	OutIter out_iter,
	int id_count, const GetID&get_id
){
	ArrayIDFunc<int>pos(id_count);
	pos.fill(0);
	for(InIter i=in_begin; i!=in_end; ++i)
		++pos[get_id(*i)];

	int sum = 0;
	for(int i=0; i<id_count; ++i){
		int tmp = pos[i];
		pos[i] = sum;
		sum += tmp;
	}

	for(InIter i=in_begin; i!=in_end; ++i)
		*(out_iter+pos[get_id(*i)]++) = *i;
}

template<class InIter, class OutIter, class GetID>
void stable_sort_copy_by_id(
	InIter in_begin, InIter in_end,
	OutIter out_iter,
	const GetID&get_id
){
	stable_sort_copy_by_id(in_begin, in_end, out_iter, get_id.image_count(), get_id);
}

#endif