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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
/*
* Copyright (C) 2003-2022 Paolo Boldi and Sebastiano Vigna
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package PACKAGE;
#if KEY_CLASS_Object
import java.util.Comparator;
#endif
import java.util.Arrays;
/** A class providing static methods and objects that do useful things with indirect heaps.
*
* <p>An indirect heap is an extension of a semi-indirect heap using also an
* <em>inversion array</em> of the same length as the reference array,
* satisfying the relation {@code heap[inv[i]]==i} when
* {@code inv[i]>=0}, and {@code inv[heap[i]]==i} for all elements in the heap.
*/
public final class INDIRECT_HEAPS {
private INDIRECT_HEAPS() {}
/** Moves the given element down into the indirect heap until it reaches the lowest possible position.
*
* @param refArray the reference array.
* @param heap the indirect heap (starting at 0).
* @param inv the inversion array.
* @param size the number of elements in the heap.
* @param i the index in the heap of the element to be moved down.
* @param c a type-specific comparator, or {@code null} for the natural order.
* @return the new position in the heap of the element of heap index {@code i}.
*/
SUPPRESS_WARNINGS_KEY_UNCHECKED
public static KEY_GENERIC int downHeap(final KEY_GENERIC_TYPE[] refArray, final int[] heap, final int[] inv, final int size, int i, final KEY_COMPARATOR KEY_GENERIC c) {
assert i < size;
final int e = heap[i];
final KEY_GENERIC_TYPE E = refArray[e];
int child;
if (c == null)
while ((child = (i << 1) + 1) < size) {
int t = heap[child];
final int right = child + 1;
if (right < size && KEY_LESS(refArray[heap[right]], refArray[t])) t = heap[child = right];
if (KEY_LESSEQ(E, refArray[t])) break;
heap[i] = t;
inv[heap[i]] = i;
i = child;
}
else
while ((child = (i << 1) + 1) < size) {
int t = heap[child];
final int right = child + 1;
if (right < size && c.compare(refArray[heap[right]], refArray[t]) < 0) t = heap[child = right];
if (c.compare(E, refArray[t]) <= 0) break;
heap[i] = t;
inv[heap[i]] = i;
i = child;
}
heap[i] = e;
inv[e] = i;
return i;
}
/** Moves the given element up in the indirect heap until it reaches the highest possible position.
*
* Note that in principle after this call the heap property may be violated.
*
* @param refArray the reference array.
* @param heap the indirect heap (starting at 0).
* @param inv the inversion array.
* @param size the number of elements in the heap.
* @param i the index in the heap of the element to be moved up.
* @param c a type-specific comparator, or {@code null} for the natural order.
* @return the new position in the heap of the element of heap index {@code i}.
*/
SUPPRESS_WARNINGS_KEY_UNCHECKED
public static KEY_GENERIC int upHeap(final KEY_GENERIC_TYPE[] refArray, final int[] heap, final int[] inv, final int size, int i, final KEY_COMPARATOR KEY_GENERIC c) {
assert i < size;
final int e = heap[i];
final KEY_GENERIC_TYPE E = refArray[e];
if (c == null)
while (i != 0) {
final int parent = (i - 1) >>> 1;
final int t = heap[parent];
if (KEY_LESSEQ(refArray[t], E)) break;
heap[i] = t;
inv[heap[i]] = i;
i = parent;
}
else
while (i != 0) {
final int parent = (i - 1) >>> 1;
final int t = heap[parent];
if (c.compare(refArray[t], E) <= 0) break;
heap[i] = t;
inv[heap[i]] = i;
i = parent;
}
heap[i] = e;
inv[e] = i;
return i;
}
/** Creates an indirect heap in the given array.
*
* @param refArray the reference array.
* @param offset the first element of the reference array to be put in the heap.
* @param length the number of elements to be put in the heap.
* @param heap the array where the heap is to be created.
* @param inv the inversion array.
* @param c a type-specific comparator, or {@code null} for the natural order.
*/
public static KEY_GENERIC void makeHeap(final KEY_GENERIC_TYPE[] refArray, final int offset, final int length, final int[] heap, final int[] inv, final KEY_COMPARATOR KEY_GENERIC c) {
ARRAYS.ensureOffsetLength(refArray, offset, length);
if (heap.length < length) throw new IllegalArgumentException("The heap length (" + heap.length + ") is smaller than the number of elements (" + length + ")");
if (inv.length < refArray.length) throw new IllegalArgumentException("The inversion array length (" + heap.length + ") is smaller than the length of the reference array (" + refArray.length + ")");
Arrays.fill(inv, 0, refArray.length, -1);
int i = length;
while(i-- != 0) inv[heap[i] = offset + i] = i;
i = length >>> 1;
while(i-- != 0) downHeap(refArray, heap, inv, length, i, c);
}
/** Creates an indirect heap from a given index array.
*
* @param refArray the reference array.
* @param heap an array containing indices into {@code refArray}.
* @param inv the inversion array.
* @param size the number of elements in the heap.
* @param c a type-specific comparator, or {@code null} for the natural order.
*/
public static KEY_GENERIC void makeHeap(final KEY_GENERIC_TYPE[] refArray, final int[] heap, final int[] inv, final int size, final KEY_COMPARATOR KEY_GENERIC c) {
int i = size >>> 1;
while(i-- != 0) downHeap(refArray, heap, inv, size, i, c);
}
}
|
