1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.accumulo.core.iterators.system;
18
19 import java.io.IOException;
20
21 import org.apache.accumulo.core.data.Key;
22 import org.apache.accumulo.core.data.Value;
23 import org.apache.accumulo.core.iterators.SortedKeyValueIterator;
24 import org.apache.commons.collections.buffer.PriorityBuffer;
25
26 public abstract class HeapIterator implements SortedKeyValueIterator<Key,Value> {
27 private PriorityBuffer heap;
28 private SortedKeyValueIterator<Key,Value> currentIter;
29
30 private static class Index implements Comparable<Index> {
31 SortedKeyValueIterator<Key,Value> iter;
32
33 public Index(SortedKeyValueIterator<Key,Value> iter) {
34 this.iter = iter;
35 }
36
37 public int compareTo(Index o) {
38 return iter.getTopKey().compareTo(o.iter.getTopKey());
39 }
40 }
41
42 protected HeapIterator() {
43 heap = null;
44 }
45
46 protected HeapIterator(int maxSize) {
47 createHeap(maxSize);
48 }
49
50 protected void createHeap(int maxSize) {
51 if (heap != null)
52 throw new IllegalStateException("heap already exist");
53
54 heap = new PriorityBuffer(maxSize == 0 ? 1 : maxSize);
55 }
56
57 @Override
58 final public Key getTopKey() {
59 return currentIter.getTopKey();
60 }
61
62 @Override
63 final public Value getTopValue() {
64 return currentIter.getTopValue();
65 }
66
67 @Override
68 final public boolean hasTop() {
69 return heap.size() > 0;
70 }
71
72 @Override
73 final public void next() throws IOException {
74 switch (heap.size()) {
75 case 0:
76 throw new IllegalStateException("Called next() when there is no top");
77 case 1:
78
79
80 currentIter.next();
81 if (!currentIter.hasTop()) {
82 heap.remove();
83 currentIter = null;
84 }
85 break;
86 default:
87 Index idx = (Index) heap.remove();
88 idx.iter.next();
89 if (idx.iter.hasTop()) {
90 heap.add(idx);
91 }
92
93
94
95 currentIter = ((Index) heap.get()).iter;
96 }
97 }
98
99 final protected void clear() {
100 heap.clear();
101 currentIter = null;
102 }
103
104 final protected void addSource(SortedKeyValueIterator<Key,Value> source) {
105
106 if (source.hasTop())
107 heap.add(new Index(source));
108
109 if (heap.size() > 0)
110 currentIter = ((Index) heap.get()).iter;
111 else
112 currentIter = null;
113 }
114
115 }