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
|
package com.jclark.xsl.expr;
import com.jclark.xsl.om.*;
class MergeNodeIterator implements NodeIterator {
private NodeIterator[] iters;
private Node[] nodes;
private int length;
MergeNodeIterator(NodeIterator[] iters, int length) throws XSLException {
this.length = length;
this.iters = iters;
nodes = new Node[length];
int j = 0;
for (int i = 0; i < length; i++) {
if (i != j)
iters[j] = iters[i];
Node tem = iters[j].next();
if (tem != null)
nodes[j++] = tem;
}
this.length = j;
buildHeap();
}
/* Make the heap rooted at i a heap, assuming it children are heaps. */
private final void heapify(int i) {
for (;;) {
int left = (i << 1) | 1;
int right = left + 1;
if (right < length) {
if (compare(left, right) <= 0) {
// left <= right
if (compare(left, i) > 0)
break;
exchange(left, i);
i = left;
}
else {
// right >= left
if (compare(right, i) > 0)
break;
exchange(right, i);
i = right;
}
}
else if (left < length) {
if (compare(left, i) > 0)
break;
exchange(left, i);
i = left;
}
else
break;
}
}
private final void exchange(int i, int j) {
{
Node tem = nodes[i];
nodes[i] = nodes[j];
nodes[j] = tem;
}
{
NodeIterator tem = iters[i];
iters[i] = iters[j];
iters[j] = tem;
}
}
private final int compare(int i, int j) {
return nodes[i].compareTo(nodes[j]);
}
private void buildHeap() {
for (int i = length/2 - 1; i >= 0; --i)
heapify(i);
}
public Node next() throws XSLException {
if (length == 0)
return null;
Node max = nodes[0];
do {
Node tem = iters[0].next();
if (tem == null) {
if (--length == 0)
break;
nodes[0] = nodes[length];
iters[0] = iters[length];
}
else
nodes[0] = tem;
heapify(0);
} while (max.equals(nodes[0]));
return max;
}
}
|
