lucene-java-3.5.0/lucene/src/java/org/apache/lucene/index/CoalescedDeletes.java

   1 package org.apache.lucene.index;
   2
   3 /**
   4  * Licensed to the Apache Software Foundation (ASF) under one or more
   5  * contributor license agreements.  See the NOTICE file distributed with
   6  * this work for additional information regarding copyright ownership.
   7  * The ASF licenses this file to You under the Apache License, Version 2.0
   8  * (the "License"); you may not use this file except in compliance with
   9  * the License.  You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 import java.util.ArrayList;
  21 import java.util.Iterator;
  22 import java.util.HashMap;
  23 import java.util.List;
  24 import java.util.Map;
  25
  26 import org.apache.lucene.search.Query;
  27 import org.apache.lucene.util.PriorityQueue;
  28 import org.apache.lucene.index.BufferedDeletesStream.QueryAndLimit;
  29
  30 class CoalescedDeletes {
  31   final Map<Query,Integer> queries = new HashMap<Query,Integer>();
  32   final List<Iterable<Term>> iterables = new ArrayList<Iterable<Term>>();
  33
  34   @Override
  35   public String toString() {
  36     // note: we could add/collect more debugging information
  37     return "CoalescedDeletes(termSets=" + iterables.size() + ",queries=" + queries.size() + ")";
  38   }
  39
  40   void update(FrozenBufferedDeletes in) {
  41     iterables.add(in.termsIterable());
  42
  43     for(int queryIdx=0;queryIdx<in.queries.length;queryIdx++) {
  44       final Query query = in.queries[queryIdx];
  45       queries.put(query, BufferedDeletes.MAX_INT);
  46     }
  47   }
  48
  49  public Iterable<Term> termsIterable() {
  50    return new Iterable<Term>() {
  51      public Iterator<Term> iterator() {
  52        ArrayList<Iterator<Term>> subs = new ArrayList<Iterator<Term>>(iterables.size());
  53        for (Iterable<Term> iterable : iterables) {
  54          subs.add(iterable.iterator());
  55        }
  56        return mergedIterator(subs);
  57      }
  58    };
  59   }
  60
  61   public Iterable<QueryAndLimit> queriesIterable() {
  62     return new Iterable<QueryAndLimit>() {
  63
  64       public Iterator<QueryAndLimit> iterator() {
  65         return new Iterator<QueryAndLimit>() {
  66           private final Iterator<Map.Entry<Query,Integer>> iter = queries.entrySet().iterator();
  67
  68           public boolean hasNext() {
  69             return iter.hasNext();
  70           }
  71
  72           public QueryAndLimit next() {
  73             final Map.Entry<Query,Integer> ent = iter.next();
  74             return new QueryAndLimit(ent.getKey(), ent.getValue());
  75           }
  76
  77           public void remove() {
  78             throw new UnsupportedOperationException();
  79           }
  80         };
  81       }
  82     };
  83   }
  84
  85   /** provides a merged view across multiple iterators */
  86   static Iterator<Term> mergedIterator(final List<Iterator<Term>> iterators) {
  87     return new Iterator<Term>() {
  88       Term current;
  89       TermMergeQueue queue = new TermMergeQueue(iterators.size());
  90       SubIterator[] top = new SubIterator[iterators.size()];
  91       int numTop;
  92
  93       {
  94         int index = 0;
  95         for (Iterator<Term> iterator : iterators) {
  96           if (iterator.hasNext()) {
  97             SubIterator sub = new SubIterator();
  98             sub.current = iterator.next();
  99             sub.iterator = iterator;
 100             sub.index = index++;
 101             queue.add(sub);
 102           }
 103         }
 104       }
 105
 106       public boolean hasNext() {
 107         if (queue.size() > 0) {
 108           return true;
 109         }
 110
 111         for (int i = 0; i < numTop; i++) {
 112           if (top[i].iterator.hasNext()) {
 113             return true;
 114           }
 115         }
 116         return false;
 117       }
 118
 119       public Term next() {
 120         // restore queue
 121         pushTop();
 122
 123         // gather equal top fields
 124         if (queue.size() > 0) {
 125           pullTop();
 126         } else {
 127           current = null;
 128         }
 129         return current;
 130       }
 131
 132       public void remove() {
 133         throw new UnsupportedOperationException();
 134       }
 135
 136       private void pullTop() {
 137         // extract all subs from the queue that have the same top term
 138         assert numTop == 0;
 139         while (true) {
 140           top[numTop++] = queue.pop();
 141           if (queue.size() == 0
 142               || !(queue.top()).current.equals(top[0].current)) {
 143             break;
 144           }
 145         }
 146         current = top[0].current;
 147       }
 148
 149       private void pushTop() {
 150         // call next() on each top, and put back into queue
 151         for (int i = 0; i < numTop; i++) {
 152           if (top[i].iterator.hasNext()) {
 153             top[i].current = top[i].iterator.next();
 154             queue.add(top[i]);
 155           } else {
 156             // no more terms
 157             top[i].current = null;
 158           }
 159         }
 160         numTop = 0;
 161       }
 162     };
 163   }
 164
 165   private static class SubIterator {
 166     Iterator<Term> iterator;
 167     Term current;
 168     int index;
 169   }
 170
 171   private static class TermMergeQueue extends PriorityQueue<SubIterator> {
 172     TermMergeQueue(int size) {
 173       initialize(size);
 174     }
 175
 176     @Override
 177     protected boolean lessThan(SubIterator a, SubIterator b) {
 178       final int cmp = a.current.compareTo(b.current);
 179       if (cmp != 0) {
 180         return cmp < 0;
 181       } else {
 182         return a.index < b.index;
 183       }
 184     }
 185   }
 186 }