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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
//
// File: sort_HeapSort_Impl.cc
// Symbol: sort.HeapSort-v0.1
// Symbol Type: class
// Babel Version: 0.10.2
// Description: Server-side implementation for sort.HeapSort
//
// WARNING: Automatically generated; only changes within splicers preserved
//
// babel-version = 0.10.2
//
#include "sort_HeapSort_Impl.hh"
#line 14 "../../../../babel/regression/sort/libCxx/sort_HeapSort_Impl.cc"
// DO-NOT-DELETE splicer.begin(sort.HeapSort._includes)
// Put additional includes or other arbitrary code here...
static void remakeHeap(sort::Container &elem,
sort::Comparator &comp,
sort::Counter &cmp,
sort::Counter &swp,
const int32_t last,
int32_t first)
{
const int32_t half = (last >> 1) - 1;
int32_t child;
while (first <= half) {
child = first + first + 1;
if ((child+1) < last) {
cmp.inc();
if (elem.compare(child, child+1, comp) < 0) ++child;
}
cmp.inc();
if (elem.compare(first, child, comp) >= 0) break;
swp.inc();
elem.swap(first, child);
first = child;
}
}
// DO-NOT-DELETE splicer.end(sort.HeapSort._includes)
#line 40 "sort_HeapSort_Impl.cc"
// user-defined constructor.
void sort::HeapSort_impl::_ctor() {
#line 42 "../../../../babel/regression/sort/libCxx/sort_HeapSort_Impl.cc"
// DO-NOT-DELETE splicer.begin(sort.HeapSort._ctor)
// add construction details here
// DO-NOT-DELETE splicer.end(sort.HeapSort._ctor)
#line 48 "sort_HeapSort_Impl.cc"
}
// user-defined destructor.
void sort::HeapSort_impl::_dtor() {
#line 49 "../../../../babel/regression/sort/libCxx/sort_HeapSort_Impl.cc"
// DO-NOT-DELETE splicer.begin(sort.HeapSort._dtor)
// add destruction details here
// DO-NOT-DELETE splicer.end(sort.HeapSort._dtor)
#line 57 "sort_HeapSort_Impl.cc"
}
// static class initializer.
void sort::HeapSort_impl::_load() {
#line 56 "../../../../babel/regression/sort/libCxx/sort_HeapSort_Impl.cc"
// DO-NOT-DELETE splicer.begin(sort.HeapSort._load)
// guaranteed to be called at most once before any other method in this class
// DO-NOT-DELETE splicer.end(sort.HeapSort._load)
#line 66 "sort_HeapSort_Impl.cc"
}
// user-defined static methods: (none)
// user-defined non-static methods:
/**
* Sort elements using Heap Sort.
*/
void
sort::HeapSort_impl::sort (
/* in */ ::sort::Container elems,
/* in */ ::sort::Comparator comp )
throw ()
{
#line 73 "../../../../babel/regression/sort/libCxx/sort_HeapSort_Impl.cc"
// DO-NOT-DELETE splicer.begin(sort.HeapSort.sort)
int32_t i;
const int32_t num = elems.getLength();
sort::Counter cmp = self.getCompareCounter();
sort::Counter swp = self.getSwapCounter();
/* make the heap */
for(i = ((num/2) - 1); i >= 0; --i) {
remakeHeap(elems, comp, cmp, swp, num, i);
}
/* put top of heap at back and remake the heap */
i = num - 1;
while (i > 0) {
swp.inc();
elems.swap(0, i);
remakeHeap(elems, comp, cmp, swp, i--, 0);
}
// DO-NOT-DELETE splicer.end(sort.HeapSort.sort)
#line 99 "sort_HeapSort_Impl.cc"
}
/**
* Return heap sort.
*/
::std::string
sort::HeapSort_impl::getName ()
throw ()
{
#line 100 "../../../../babel/regression/sort/libCxx/sort_HeapSort_Impl.cc"
// DO-NOT-DELETE splicer.begin(sort.HeapSort.getName)
return "Heap sort";
// DO-NOT-DELETE splicer.end(sort.HeapSort.getName)
#line 114 "sort_HeapSort_Impl.cc"
}
#line 106 "../../../../babel/regression/sort/libCxx/sort_HeapSort_Impl.cc"
// DO-NOT-DELETE splicer.begin(sort.HeapSort._misc)
// Put miscellaneous code here
// DO-NOT-DELETE splicer.end(sort.HeapSort._misc)
#line 122 "sort_HeapSort_Impl.cc"
|
