View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *     http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
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          // optimization for case when heap contains one entry,
79          // avoids remove and add
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          // to get to the default case heap has at least
93          // two entries, therefore there must be at least
94          // one entry when get() is called below
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 }