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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
#pragma once
#include "header.h"
#include "extinfo.h"
#include <util/generic/vector.h>
#include <errno.h>
///////////////////////////////////////////////////////////////////////////////
/// Default comparator
template <class TVal>
struct TCompareByLess {
inline bool operator()(const TVal* a, const TVal* b) const {
return TLess<TVal>()(*a, *b);
}
};
///////////////////////////////////////////////////////////////////////////////
template <class TVal, class TIterator, class TCompare = TCompareByLess<TVal>>
class THeapIter {
public:
int Init(TIterator** iters, int count) {
Term();
if (!count)
return 0;
if (!(Heap = (TIterator**)malloc(count * sizeof(TIterator*))))
return ENOMEM;
Count = count;
count = 0;
while (count < Count)
if (count && !(*iters)->Next()) { //here first TIterator is NOT initialized!
Count--;
iters++;
} else {
Heap[count++] = *iters++;
}
count = Count / 2;
while (--count > 0) //Heap[0] is not changed!
Sift(count, Count); //do not try to replace this code by make_heap
return 0;
}
int Init(TIterator* iters, int count) {
TVector<TIterator*> a(count);
for (int i = 0; i < count; ++i)
a[i] = &iters[i];
return Init(&a[0], count);
}
THeapIter()
: Heap(nullptr)
, Count(0)
{
}
THeapIter(TIterator* a, TIterator* b)
: Heap(nullptr)
, Count(0)
{
TIterator* arr[] = {a, b};
if (Init(arr, 2))
ythrow yexception() << "can't Init THeapIter";
}
THeapIter(TVector<TIterator>& v)
: Heap(nullptr)
, Count(0)
{
if (Init(&v[0], v.size())) {
ythrow yexception() << "can't Init THeapIter";
}
}
~THeapIter() {
Term();
}
inline const TVal* Current() const {
if (!Count)
return nullptr;
return (*Heap)->Current();
}
inline const TIterator* CurrentIter() const {
return *Heap;
}
//for ends of last file will use Heap[0] = Heap[0] ! and
//returns Current of eof so Current of eof MUST return NULL
//possible this is bug and need fixing
const TVal* Next() {
if (!Count)
return nullptr;
if (!(*Heap)->Next()) //on first call unitialized first TIterator
*Heap = Heap[--Count]; //will be correctly initialized
if (Count == 2) {
if (TCompare()(Heap[1]->Current(), Heap[0]->Current()))
DoSwap(Heap[1], Heap[0]);
} else
Sift(0, Count);
return Current();
}
inline bool GetExtInfo(typename TExtInfoType<TVal>::TResult* extInfo) const {
return (*Heap)->GetExtInfo(extInfo);
}
inline const ui8* GetExtInfoRaw(size_t* len) const {
return (*Heap)->GetExtInfoRaw(len);
}
void Term() {
::free(Heap);
Heap = nullptr;
Count = 0;
}
protected:
void Sift(int node, int end) {
TIterator* x = Heap[node];
int son;
for (son = 2 * node + 1; son < end; node = son, son = 2 * node + 1) {
if (son < (end - 1) && TCompare()(Heap[son + 1]->Current(), Heap[son]->Current()))
son++;
if (TCompare()(Heap[son]->Current(), x->Current()))
Heap[node] = Heap[son];
else
break;
}
Heap[node] = x;
}
TIterator** Heap;
int Count;
};
///////////////////////////////////////////////////////////////////////////////
|
