java/src/main/com/google/appengine/api/datastore/MultiQueryIterator.java

   1 // Copyright 2009 Google Inc. All Rights Reserved.
   2
   3 package com.google.appengine.api.datastore;
   4
   5 import com.google.appengine.api.datastore.MultiQueryComponent.Order;
   6 import com.google.appengine.api.datastore.Query.FilterPredicate;
   7 import com.google.common.collect.Lists;
   8 import com.google.common.collect.Queues;
   9
  10 import java.util.ArrayList;
  11 import java.util.Deque;
  12 import java.util.Iterator;
  13 import java.util.List;
  14 import java.util.NoSuchElementException;
  15
  16 /**
  17  * This class constructs lists of filters as defined by the components as needed.
  18  *
  19  * It uses both recursive and local stack algorithms so it can save it's
  20  * position in the query construction algorithm between calls to next.
  21  *
  22  */
  23 class MultiQueryIterator implements Iterator<List<List<FilterPredicate>>> {
  24   private final List<MultiQueryComponent> components;
  25   private final List<Integer> componentSubIndex;
  26   private final Deque<List<FilterPredicate>> filtersStack = Queues.newArrayDeque();
  27   private int componentIndex = 0;
  28   private int parallelCount = 0;
  29
  30   private boolean moreResults = true;
  31
  32   public MultiQueryIterator(List<FilterPredicate> baseFilters,
  33       List<MultiQueryComponent> components) {
  34     this.components = components;
  35     filtersStack.push(baseFilters);
  36
  37     componentSubIndex = new ArrayList<Integer>(components.size());
  38     for (MultiQueryComponent component : components) {
  39       componentSubIndex.add(0);
  40     }
  41   }
  42
  43   /**
  44    * Pushes a components filters onto the stack. The stack is cumulative so all
  45    * filters added to the stack exist in the top element of the stack.
  46    *
  47    * @param componentFilters the filters to add to the stack
  48    */
  49   private void pushFilters(List<FilterPredicate> componentFilters) {
  50     List<FilterPredicate> baseFilters = filtersStack.peek();
  51     List<FilterPredicate> filters =
  52         new ArrayList<FilterPredicate>(baseFilters.size() + componentFilters.size());
  53     filters.addAll(baseFilters);
  54     filters.addAll(componentFilters);
  55     filtersStack.push(filters);
  56   }
  57
  58   /**
  59    * This function updates {@link #componentIndex} to point to the next combination
  60    * of serial component filters
  61    *
  62    * @return false if the next combination has looped back to the first combination
  63    */
  64   private boolean advanceSerialComponents() {
  65     for (int i = components.size() - 1; i >= 0; --i) {
  66       MultiQueryComponent component = components.get(i);
  67       if (component.getOrder() != Order.PARALLEL) {
  68         boolean isLastFilter = componentSubIndex.get(i) + 1 == component.getFilters().size();
  69         if (isLastFilter) {
  70           componentSubIndex.set(i, 0);
  71         } else {
  72           componentSubIndex.set(i, componentSubIndex.get(i) + 1);
  73           return true;
  74         }
  75       }
  76     }
  77     return false;
  78   }
  79
  80   /**
  81    * The function accumulates a set of queries that are intended to be run in
  82    * parallel.
  83    *
  84    * @param result the list new filters lists are added to
  85    * @param minIndex the index to stop at when looking for more results
  86    */
  87   private void buildNextResult(List<List<FilterPredicate>> result, int minIndex) {
  88     while (componentIndex >= minIndex) {
  89       if (componentIndex >= components.size()) {
  90         result.add(filtersStack.peek());
  91         --componentIndex;
  92         continue;
  93       }
  94
  95       MultiQueryComponent component = components.get(componentIndex);
  96       if (component.getOrder() == Order.PARALLEL) {
  97         ++parallelCount;
  98         ++componentIndex;
  99         for (List<FilterPredicate> componentFilters : component.getFilters()) {
 100           pushFilters(componentFilters);
 101           buildNextResult(result, componentIndex);
 102           filtersStack.pop();
 103         }
 104         --parallelCount;
 105         componentIndex -= 2;
 106       } else {
 107         if (filtersStack.size() <= componentIndex + 1) {
 108           pushFilters(component.getFilters().get(componentSubIndex.get(componentIndex)));
 109           ++componentIndex;
 110         } else {
 111           filtersStack.pop();
 112           boolean isLastFilter =
 113               componentSubIndex.get(componentIndex) + 1 == component.getFilters().size();
 114           --componentIndex;
 115           if ((parallelCount == 0) && !isLastFilter) {
 116             break;
 117           }
 118         }
 119       }
 120     }
 121     ++componentIndex;
 122   }
 123
 124   @Override
 125   public boolean hasNext() {
 126     return moreResults;
 127   }
 128
 129   @Override
 130   public List<List<FilterPredicate>> next() {
 131     if (!moreResults) {
 132       throw new NoSuchElementException();
 133     }
 134     List<List<FilterPredicate>> result = Lists.newArrayList();
 135     buildNextResult(result, 0);
 136     moreResults = advanceSerialComponents();
 137     return result;
 138   }
 139
 140   @Override
 141   public void remove() {
 142     throw new UnsupportedOperationException();
 143   }
 144 }