extras/indexing/src/main/java/org/apache/rya/indexing/external/matching/QueryNodeConsolidator.java - rya - Git at Google

 package org.apache.rya.indexing.external.matching;

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *   http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an
  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  * KIND, either express or implied.  See the License for the
  * specific language governing permissions and limitations
  * under the License.
  */

 import java.util.ArrayList;
 import java.util.Comparator;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.SortedSet;
 import java.util.TreeSet;

 import org.eclipse.rdf4j.query.algebra.QueryModelNode;
 import org.eclipse.rdf4j.query.algebra.TupleExpr;
 import org.eclipse.rdf4j.query.algebra.ValueExpr;

 import com.google.common.base.Preconditions;

 /**
  * Given an order List view of an {@link OptionalJoinSegment} taken from a query
  * and an OptionalJoinSegment representing an ExternalSet, this class attempts
  * to consolidate the {@link QueryModelNode}s of the ExternalSet together within
  * the query and order them in a way that is consistent with the ExternalSet.
  * This is the key step in matching the ExternalSet to a subset of a query when
  * LeftJoins are present.
  *
  */
 public class QueryNodeConsolidator {

     private TreeSet<PositionNode> leftJoinPosSet = new TreeSet<>(new PositionComparator());
     private TreeSet<PositionNode> extSetPosSet = new TreeSet<>(new PositionComparator());

     // nonExtSetNodes in query that extSetNodes cannot move past
     private TreeSet<PositionNode> lowerBoundSet = new TreeSet<>(new PositionComparator());
     // nonExtSetNodes in query that extSetNodes cannot move past
     private TreeSet<PositionNode> upperBoundSet = new TreeSet<>(new PositionComparator());
     private int greatestLowerBound = -1;
     private int leastUpperBound = Integer.MAX_VALUE;

     private List<QueryModelNode> queryNodes;
     private List<QueryModelNode> extSetNodes;
     private boolean consolidateCalled = false;
     private boolean returnValConsolidate = false;

     public QueryNodeConsolidator(List<QueryModelNode> queryNodes, List<QueryModelNode> extSetNodes) {
         Preconditions.checkArgument(
                 new HashSet<QueryModelNode>(queryNodes).containsAll(new HashSet<QueryModelNode>(extSetNodes)));
         this.queryNodes = new ArrayList<>(queryNodes);
         this.extSetNodes = new ArrayList<>(extSetNodes);
         int i = 0;
         for (QueryModelNode q : queryNodes) {
             if (q instanceof FlattenedOptional) {
                 leftJoinPosSet.add(new PositionNode(q, i));
             }
             if (extSetNodes.contains(q)) {
                 extSetPosSet.add(new PositionNode(q, i));
             }
             i++;
         }
     }

     /**
      * This method consolidates the ExternalSet nodes within the query. After
      * this method is called, the ExternalSet nodes in the query will be
      * completely consolidated if true is returned and will only be partially
      * consolidated if false is return
      *
      * @return - true or false depending on whether nodes could be entirely
      *         consolidated
      */
     public boolean consolidateNodes() {
         if (consolidateCalled) {
             return returnValConsolidate;
         }
         consolidateCalled = true;
         returnValConsolidate = consolidate() && reOrderExtSetNodes();
         return returnValConsolidate;
     }

     /**
      *
      * @return List of the query's QueryModelNodes
      */
     public List<QueryModelNode> getQueryNodes() {
         return queryNodes;
     }

     // assumes nodes are consolidated -- checks if they can be reordered to
     // match ExternalSet node list
     private boolean reOrderExtSetNodes() {
         int pos = extSetPosSet.last().getPosition();
         for (int j = extSetNodes.size() - 1; j >= 0; j--) {
             QueryModelNode node = extSetNodes.get(j);
             int i = queryNodes.indexOf(node);
             // use ExternalSet node in queryNodes so FlattenedOptional boundVars
             // are consistent with query
             node = queryNodes.get(i);
             if (!moveQueryNode(new PositionNode(node, i), pos)) {
                 return false;
             }
             pos--;
         }
         return true;
     }

     private boolean consolidate() {
         while (canConsolidate()) {
             Move move = getNextMove();
             // if move is empty, then ExternalSet nodes are
             // consolidated
             if (move.isEmpty) {
                 return true;
             }
             moveQueryNode(move.node, move.finalPos);
         }

         return false;
     }

     private boolean canConsolidate() {
         if (greatestLowerBound < leastUpperBound) {
             return true;
         }
         return adjustBounds();
     }

     // if l.u.b < g.l.b, attempt to push g.l.b up
     // assume first ExternalSet position node has position less
     // than g.l.b. - this should be by design given that
     // l.u.b <= g.l.b. and there has to be at least one ExternalSet node
     // positioned before l.u.b.
     private boolean adjustBounds() {

         int finalPos = extSetPosSet.first().getPosition();
         PositionNode node = lowerBoundSet.last();

         return moveQueryNode(node, finalPos);
     }

     // assumes g.l.b <= l.u.b.
     // iterates through ExternalSet nodes in query from lowest position to
     // highest looking for a difference in index position greater than
     // one. Given the leftmost pair of nodes separated by two or more
     // spaces, the leftmost node in the pair is moved so that its final
     // position is one position to the left of the rightmost node. For
     // example, given nodes at index 1 and index 3, the node at index 1
     // is advanced to index 2. This method returns the suggested Move,
     // but does not actually perform the Move.
     private Move getNextMove() {

         Iterator<PositionNode> posIterator = extSetPosSet.iterator();
         PositionNode current;
         if (posIterator.hasNext()) {
             current = posIterator.next();
         } else {
             throw new IllegalStateException("PCJ has no nodes!");
         }
         PositionNode next;
         int pos1 = -1;
         int pos2 = -1;
         while (posIterator.hasNext()) {
             next = posIterator.next();
             pos1 = current.getPosition();
             pos2 = next.getPosition();
             // move nodes are not adjacent
             if (pos1 + 1 < pos2) {
                 if (leastUpperBound > pos2) {
                     return new Move(current, pos2 - 1);
                 }
                 // pos1 < leastUpperBound < pos2 b/c pos1 < leastUpperBound by
                 // design
                 else if (greatestLowerBound < pos1) {
                     return new Move(next, pos1 + 1);
                 }
                 // move current to node after greatestLowerBound
                 else {
                     return new Move(current, greatestLowerBound);
                 }
             }

             current = next;
         }

         return new Move();
     }

     private boolean moveQueryNode(PositionNode node, int position) {

         if (!canMoveNode(node, position)) {
             if (upperBoundSet.size() > 0) {
                 leastUpperBound = upperBoundSet.first().getPosition();
             }
             if (lowerBoundSet.size() > 0) {
                 greatestLowerBound = lowerBoundSet.last().getPosition();
             }
             return false;
         }
         // update QueryModelNodes in leftJoin index so that FlattenedOptional
         // var counts are correct
         updateLeftJoinNodes(node, position);
         // move node in queryNode list
         updateNodeList(node, position, queryNodes);
         // update bounds
         updatePositionNodeSet(node, position, lowerBoundSet);
         updatePositionNodeSet(node, position, upperBoundSet);
         // update leastUppperBound and greatestLowerBound
         if (upperBoundSet.size() > 0) {
             leastUpperBound = upperBoundSet.first().getPosition();
         }
         if (lowerBoundSet.size() > 0) {
             greatestLowerBound = lowerBoundSet.last().getPosition();
         }
         // update positions within leftJoin index
         updatePositionNodeSet(node, position, leftJoinPosSet);
         // no need to update entire set because ExternalSet nodes are not moved
         // past one another during consolidation
         updatePositionNode(node, position, extSetPosSet);

         return true;
     }

     private boolean canMoveNode(PositionNode node, int finalPos) {
         PositionNode bound = getBounds(node, finalPos, queryNodes, leftJoinPosSet);
         if (bound.isEmpty) {
             return true;
         }
         addBound(bound, node, finalPos);
         return false;

     }

     // adds bound to either lowerBoundSet or uppderBoundSet, depending on
     // initial and
     // final position of move
     private void addBound(PositionNode bound, PositionNode node, int finalPos) {
         int diff = finalPos - node.getPosition();

         if (diff == 0) {
             return;
         }

         if (diff > 0) {
             if (upperBoundSet.contains(bound)) {
                 return;
             } else {
                 upperBoundSet.add(bound);
             }
         } else {
             if (lowerBoundSet.contains(bound)) {
                 return;
             } else {
                 lowerBoundSet.add(bound);
             }
         }
     }

     // updates nodes in given TreeSet between node.getPosition() and position
     private void updatePositionNodeSet(PositionNode node, int position, TreeSet<PositionNode> set) {

         if (set.size() == 0) {
             return;
         }

         int oldPos = node.getPosition();
         int diff = position - oldPos;
         SortedSet<PositionNode> posNodes;
         boolean containsNode = false;

         if (diff == 0) {
             return;
         }

         // remove node before decrementing or incrementing to prevent
         // overwriting
         if (set.contains(node)) {
             containsNode = true;
             set.remove(node);
         }

         if (diff > 0) {
             posNodes = set.subSet(node, false, new PositionNode(position), true);

             List<PositionNode> pNodeList = new ArrayList<>();
             for (PositionNode pos : posNodes) {
                 pNodeList.add(pos);
             }
             // decrement posNodes
             for (PositionNode pos : pNodeList) {
                 int p = pos.getPosition() - 1;
                 updatePositionNode(pos, p, set);
             }
         } else {
             posNodes = set.subSet(new PositionNode(position), true, node, false);
             // create list to iterate in reverse order
             List<PositionNode> pNodeList = new ArrayList<>();
             for (PositionNode pos : posNodes) {
                 pNodeList.add(pos);
             }
             // increment elements of TreeSet in reverse order so
             // that no collisions occur - PositionNodes are incremented
             // into slot created by removing node
             for (int i = pNodeList.size() - 1; i >= 0; i--) {
                 PositionNode pNode = pNodeList.get(i);
                 int p = pNode.getPosition() + 1;
                 updatePositionNode(pNode, p, set);
             }
         }

         if (containsNode) {
             node.setPosition(position);
             set.add(node);
         }

     }

     // updates the var counts in specified left join index
     private void updateLeftJoinNodes(PositionNode node, int finalPos) {
         if (node.getNode() instanceof ValueExpr) {
             return;
         }

         int diff = finalPos - node.getPosition();

         if (diff == 0) {
             return;
         }

         if (node.isOptional) {
             leftJoinPosSet.remove(node);
             FlattenedOptional optional = (FlattenedOptional) node.getNode();
             if (diff < 0) {
                 for (int i = node.getPosition() - 1; i > finalPos - 1; i--) {
                     QueryModelNode tempNode = queryNodes.get(i);
                     if (tempNode instanceof ValueExpr) {
                         continue;
                     }
                     optional.addArg((TupleExpr) tempNode);
                 }
             } else {
                 for (int i = node.getPosition() + 1; i < finalPos + 1; i++) {
                     QueryModelNode tempNode = queryNodes.get(i);
                     if (tempNode instanceof ValueExpr) {
                         continue;
                     }
                     optional.removeArg((TupleExpr) tempNode);
                 }
             }
             node.setNode(optional);
             // FlattenedOptional equals does not take into account var counts
             // The following three lines update the var count in the optional in
             // list
             int index = queryNodes.indexOf(optional);
             queryNodes.remove(optional);
             queryNodes.add(index, optional);
             leftJoinPosSet.add(node);

         } else {
             TupleExpr te = (TupleExpr) node.getNode();
             SortedSet<PositionNode> optionals;
             if (diff < 0) {
                 optionals = leftJoinPosSet.subSet(new PositionNode(finalPos), true, node, false);
                 for (PositionNode pNode : optionals) {
                     FlattenedOptional optional = (FlattenedOptional) pNode.getNode();
                     optional.removeArg(te);
                 }
             } else {
                 optionals = leftJoinPosSet.subSet(node, false, new PositionNode(finalPos), true);
                 for (PositionNode pNode : optionals) {
                     FlattenedOptional optional = (FlattenedOptional) pNode.getNode();
                     optional.addArg(te);
                 }
             }
         }

     }

     // works only if moving node to final position does not move it across
     // another node in set
     private void updatePositionNode(PositionNode node, int position, TreeSet<PositionNode> set) {
         set.remove(node);
         node.setPosition(position);
         set.add(node);
     }

     // assumes input data fall within capacity of list
     private void updateNodeList(PositionNode node, int finalPos, List<QueryModelNode> list) {
         int initialPos = node.getPosition();
         QueryModelNode qNode = list.remove(initialPos);
         if (finalPos < list.size()) {
             list.add(finalPos, qNode);
         } else {
             list.add(qNode);
         }
     }

     /**
      *
      * @param node
      * @param finalPos
      * @param list
      * @param leftJoinNodes
      * @return PositionNode - if node cannot be move to final position, this
      *         method returns a non-empty PositionNode representing a bound to
      *         the move. If it can, it returns an empty PositionNode.
      */
     // determine if given node can be moved to finalPos
     // assumes node.position and finalPos fall within index range of list
     private PositionNode getBounds(PositionNode node, int finalPos, List<QueryModelNode> list,
             TreeSet<PositionNode> leftJoinNodes) {

         // filters can be moved up and pushed down join segment
         // without affecting bound and unbound variables of
         // FlattenedOptionals -- Filters can be pushed down as
         // far as possible because it is assumed that any variable
         // that appears in a Filter also appears in a ExternalSet node
         // if Filters can be grouped, then Filter variables will
         // automatically be bound
         if (node.getNode() instanceof ValueExpr) {
             return new PositionNode();
         }

         int diff = finalPos - node.getPosition();

         if (diff == 0) {
             return new PositionNode();
         }

         if (node.isOptional) {
             FlattenedOptional optional = ((FlattenedOptional) node.getNode()).clone();
             if (diff < 0) {
                 for (int i = node.getPosition() - 1; i > finalPos - 1; i--) {
                     QueryModelNode tempNode = list.get(i);
                     if (tempNode instanceof ValueExpr) {
                         continue;
                     }

                     if (!optional.canAddTuple((TupleExpr) tempNode)) {
                         return new PositionNode(tempNode, i);
                     }

                     if (tempNode instanceof FlattenedOptional) {
                         FlattenedOptional tempOptional = (FlattenedOptional) tempNode;
                         if (!tempOptional.canRemoveTuple(optional)) {
                             return new PositionNode(tempNode, i);
                         }

                     }
                     optional.addArg((TupleExpr) tempNode);
                 }
             } else {
                 for (int i = node.getPosition() + 1; i < finalPos + 1; i++) { // TODO
                                                                               // check
                                                                               // bounds
                     QueryModelNode tempNode = list.get(i);
                     if (tempNode instanceof ValueExpr) {
                         continue;
                     }
                     if (!optional.canRemoveTuple((TupleExpr) tempNode)) {
                         return new PositionNode(tempNode, i);
                     }

                     if (tempNode instanceof FlattenedOptional) {
                         FlattenedOptional tempOptional = (FlattenedOptional) tempNode;
                         if (!tempOptional.canAddTuple(optional)) {
                             return new PositionNode(tempNode, i);
                         }
                     }
                     optional.removeArg((TupleExpr) tempNode);
                 }
             }

             return new PositionNode();

         } else {
             TupleExpr te = (TupleExpr) node.getNode();
             SortedSet<PositionNode> leftJoins;
             if (diff < 0) {
                 leftJoins = leftJoinNodes.subSet(new PositionNode(finalPos), true, node, false);

                 for (PositionNode pNode : leftJoins) {
                     FlattenedOptional optional = (FlattenedOptional) pNode.getNode();
                     if (!optional.canRemoveTuple(te)) {
                         return new PositionNode(pNode);
                     }
                 }
             } else {

                 leftJoins = leftJoinNodes.subSet(node, false, new PositionNode(finalPos), true);
                 for (PositionNode pNode : leftJoins) {
                     FlattenedOptional optional = (FlattenedOptional) pNode.getNode();
                     if (!optional.canAddTuple(te)) {
                         return new PositionNode(pNode);
                     }
                 }
             }

             return new PositionNode();

         }

     }

     static class Move {

         PositionNode node;
         int finalPos;
         boolean isEmpty = true;

         public Move(PositionNode node, int finalPos) {
             this.node = node;
             this.finalPos = finalPos;
             this.isEmpty = false;
         }

         public Move() {
         }

     }

     static class PositionNode {

         private int position;
         private QueryModelNode node;
         private boolean isOptional = false;
         boolean isEmpty = true;

         public PositionNode(QueryModelNode node, int position) {
             this.node = node;
             this.position = position;
             this.isOptional = node instanceof FlattenedOptional;
             isEmpty = false;
         }

         public PositionNode(PositionNode node) {
             this(node.node, node.position);
         }

         public PositionNode(int position) {
             this.position = position;
             isEmpty = false;
         }

         public PositionNode() {

         }

         /**
          * @return the position
          */
         public int getPosition() {
             return position;
         }

         /**
          * @param position
          *            the position to set
          */
         public void setPosition(int position) {
             this.position = position;
         }

         /**
          * @return the node
          */
         public QueryModelNode getNode() {
             return node;
         }

         public void setNode(QueryModelNode node) {
             this.node = node;
         }

         public boolean isOptional() {
             return isOptional;
         }

         @Override
         public String toString() {
             return "Node: " + node + " Position: " + position;
         }

     }

     class PositionComparator implements Comparator<PositionNode> {

         @Override
         public int compare(PositionNode node1, PositionNode node2) {

             if (node1.position < node2.position) {
                 return -1;
             }
             if (node1.position > node2.position) {
                 return 1;
             }

             return 0;
         }

     }

 }
	package org.apache.rya.indexing.external.matching;

	/*
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing,
	* software distributed under the License is distributed on an
	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
	* KIND, either express or implied. See the License for the
	* specific language governing permissions and limitations
	* under the License.
	*/

	import java.util.ArrayList;
	import java.util.Comparator;
	import java.util.HashSet;
	import java.util.Iterator;
	import java.util.List;
	import java.util.SortedSet;
	import java.util.TreeSet;

	import org.eclipse.rdf4j.query.algebra.QueryModelNode;
	import org.eclipse.rdf4j.query.algebra.TupleExpr;
	import org.eclipse.rdf4j.query.algebra.ValueExpr;

	import com.google.common.base.Preconditions;

	/**
	* Given an order List view of an {@link OptionalJoinSegment} taken from a query
	* and an OptionalJoinSegment representing an ExternalSet, this class attempts
	* to consolidate the {@link QueryModelNode}s of the ExternalSet together within
	* the query and order them in a way that is consistent with the ExternalSet.
	* This is the key step in matching the ExternalSet to a subset of a query when
	* LeftJoins are present.
	*
	*/
	public class QueryNodeConsolidator {

	private TreeSet<PositionNode> leftJoinPosSet = new TreeSet<>(new PositionComparator());
	private TreeSet<PositionNode> extSetPosSet = new TreeSet<>(new PositionComparator());

	// nonExtSetNodes in query that extSetNodes cannot move past
	private TreeSet<PositionNode> lowerBoundSet = new TreeSet<>(new PositionComparator());
	// nonExtSetNodes in query that extSetNodes cannot move past
	private TreeSet<PositionNode> upperBoundSet = new TreeSet<>(new PositionComparator());
	private int greatestLowerBound = -1;
	private int leastUpperBound = Integer.MAX_VALUE;

	private List<QueryModelNode> queryNodes;
	private List<QueryModelNode> extSetNodes;
	private boolean consolidateCalled = false;
	private boolean returnValConsolidate = false;

	public QueryNodeConsolidator(List<QueryModelNode> queryNodes, List<QueryModelNode> extSetNodes) {
	Preconditions.checkArgument(
	new HashSet<QueryModelNode>(queryNodes).containsAll(new HashSet<QueryModelNode>(extSetNodes)));
	this.queryNodes = new ArrayList<>(queryNodes);
	this.extSetNodes = new ArrayList<>(extSetNodes);
	int i = 0;
	for (QueryModelNode q : queryNodes) {
	if (q instanceof FlattenedOptional) {
	leftJoinPosSet.add(new PositionNode(q, i));
	}
	if (extSetNodes.contains(q)) {
	extSetPosSet.add(new PositionNode(q, i));
	}
	i++;
	}
	}

	/**
	* This method consolidates the ExternalSet nodes within the query. After
	* this method is called, the ExternalSet nodes in the query will be
	* completely consolidated if true is returned and will only be partially
	* consolidated if false is return
	*
	* @return - true or false depending on whether nodes could be entirely
	* consolidated
	*/
	public boolean consolidateNodes() {
	if (consolidateCalled) {
	return returnValConsolidate;
	}
	consolidateCalled = true;
	returnValConsolidate = consolidate() && reOrderExtSetNodes();
	return returnValConsolidate;
	}

	/**
	*
	* @return List of the query's QueryModelNodes
	*/
	public List<QueryModelNode> getQueryNodes() {
	return queryNodes;
	}

	// assumes nodes are consolidated -- checks if they can be reordered to
	// match ExternalSet node list
	private boolean reOrderExtSetNodes() {
	int pos = extSetPosSet.last().getPosition();
	for (int j = extSetNodes.size() - 1; j >= 0; j--) {
	QueryModelNode node = extSetNodes.get(j);
	int i = queryNodes.indexOf(node);
	// use ExternalSet node in queryNodes so FlattenedOptional boundVars
	// are consistent with query
	node = queryNodes.get(i);
	if (!moveQueryNode(new PositionNode(node, i), pos)) {
	return false;
	}
	pos--;
	}
	return true;
	}

	private boolean consolidate() {
	while (canConsolidate()) {
	Move move = getNextMove();
	// if move is empty, then ExternalSet nodes are
	// consolidated
	if (move.isEmpty) {
	return true;
	}
	moveQueryNode(move.node, move.finalPos);
	}

	return false;
	}

	private boolean canConsolidate() {
	if (greatestLowerBound < leastUpperBound) {
	return true;
	}
	return adjustBounds();
	}

	// if l.u.b < g.l.b, attempt to push g.l.b up
	// assume first ExternalSet position node has position less
	// than g.l.b. - this should be by design given that
	// l.u.b <= g.l.b. and there has to be at least one ExternalSet node
	// positioned before l.u.b.
	private boolean adjustBounds() {

	int finalPos = extSetPosSet.first().getPosition();
	PositionNode node = lowerBoundSet.last();

	return moveQueryNode(node, finalPos);
	}

	// assumes g.l.b <= l.u.b.
	// iterates through ExternalSet nodes in query from lowest position to
	// highest looking for a difference in index position greater than
	// one. Given the leftmost pair of nodes separated by two or more
	// spaces, the leftmost node in the pair is moved so that its final
	// position is one position to the left of the rightmost node. For
	// example, given nodes at index 1 and index 3, the node at index 1
	// is advanced to index 2. This method returns the suggested Move,
	// but does not actually perform the Move.
	private Move getNextMove() {

	Iterator<PositionNode> posIterator = extSetPosSet.iterator();
	PositionNode current;
	if (posIterator.hasNext()) {
	current = posIterator.next();
	} else {
	throw new IllegalStateException("PCJ has no nodes!");
	}
	PositionNode next;
	int pos1 = -1;
	int pos2 = -1;
	while (posIterator.hasNext()) {
	next = posIterator.next();
	pos1 = current.getPosition();
	pos2 = next.getPosition();
	// move nodes are not adjacent
	if (pos1 + 1 < pos2) {
	if (leastUpperBound > pos2) {
	return new Move(current, pos2 - 1);
	}
	// pos1 < leastUpperBound < pos2 b/c pos1 < leastUpperBound by
	// design
	else if (greatestLowerBound < pos1) {
	return new Move(next, pos1 + 1);
	}
	// move current to node after greatestLowerBound
	else {
	return new Move(current, greatestLowerBound);
	}
	}

	current = next;
	}

	return new Move();
	}

	private boolean moveQueryNode(PositionNode node, int position) {

	if (!canMoveNode(node, position)) {
	if (upperBoundSet.size() > 0) {
	leastUpperBound = upperBoundSet.first().getPosition();
	}
	if (lowerBoundSet.size() > 0) {
	greatestLowerBound = lowerBoundSet.last().getPosition();
	}
	return false;
	}
	// update QueryModelNodes in leftJoin index so that FlattenedOptional
	// var counts are correct
	updateLeftJoinNodes(node, position);
	// move node in queryNode list
	updateNodeList(node, position, queryNodes);
	// update bounds
	updatePositionNodeSet(node, position, lowerBoundSet);
	updatePositionNodeSet(node, position, upperBoundSet);
	// update leastUppperBound and greatestLowerBound
	if (upperBoundSet.size() > 0) {
	leastUpperBound = upperBoundSet.first().getPosition();
	}
	if (lowerBoundSet.size() > 0) {
	greatestLowerBound = lowerBoundSet.last().getPosition();
	}
	// update positions within leftJoin index
	updatePositionNodeSet(node, position, leftJoinPosSet);
	// no need to update entire set because ExternalSet nodes are not moved
	// past one another during consolidation
	updatePositionNode(node, position, extSetPosSet);

	return true;
	}

	private boolean canMoveNode(PositionNode node, int finalPos) {
	PositionNode bound = getBounds(node, finalPos, queryNodes, leftJoinPosSet);
	if (bound.isEmpty) {
	return true;
	}
	addBound(bound, node, finalPos);
	return false;

	}

	// adds bound to either lowerBoundSet or uppderBoundSet, depending on
	// initial and
	// final position of move
	private void addBound(PositionNode bound, PositionNode node, int finalPos) {
	int diff = finalPos - node.getPosition();

	if (diff == 0) {
	return;
	}

	if (diff > 0) {
	if (upperBoundSet.contains(bound)) {
	return;
	} else {
	upperBoundSet.add(bound);
	}
	} else {
	if (lowerBoundSet.contains(bound)) {
	return;
	} else {
	lowerBoundSet.add(bound);
	}
	}
	}

	// updates nodes in given TreeSet between node.getPosition() and position
	private void updatePositionNodeSet(PositionNode node, int position, TreeSet<PositionNode> set) {

	if (set.size() == 0) {
	return;
	}

	int oldPos = node.getPosition();
	int diff = position - oldPos;
	SortedSet<PositionNode> posNodes;
	boolean containsNode = false;

	if (diff == 0) {
	return;
	}

	// remove node before decrementing or incrementing to prevent
	// overwriting
	if (set.contains(node)) {
	containsNode = true;
	set.remove(node);
	}

	if (diff > 0) {
	posNodes = set.subSet(node, false, new PositionNode(position), true);

	List<PositionNode> pNodeList = new ArrayList<>();
	for (PositionNode pos : posNodes) {
	pNodeList.add(pos);
	}
	// decrement posNodes
	for (PositionNode pos : pNodeList) {
	int p = pos.getPosition() - 1;
	updatePositionNode(pos, p, set);
	}
	} else {
	posNodes = set.subSet(new PositionNode(position), true, node, false);
	// create list to iterate in reverse order
	List<PositionNode> pNodeList = new ArrayList<>();
	for (PositionNode pos : posNodes) {
	pNodeList.add(pos);
	}
	// increment elements of TreeSet in reverse order so
	// that no collisions occur - PositionNodes are incremented
	// into slot created by removing node
	for (int i = pNodeList.size() - 1; i >= 0; i--) {
	PositionNode pNode = pNodeList.get(i);
	int p = pNode.getPosition() + 1;
	updatePositionNode(pNode, p, set);
	}
	}

	if (containsNode) {
	node.setPosition(position);
	set.add(node);
	}

	}

	// updates the var counts in specified left join index
	private void updateLeftJoinNodes(PositionNode node, int finalPos) {
	if (node.getNode() instanceof ValueExpr) {
	return;
	}

	int diff = finalPos - node.getPosition();

	if (diff == 0) {
	return;
	}

	if (node.isOptional) {
	leftJoinPosSet.remove(node);
	FlattenedOptional optional = (FlattenedOptional) node.getNode();
	if (diff < 0) {
	for (int i = node.getPosition() - 1; i > finalPos - 1; i--) {
	QueryModelNode tempNode = queryNodes.get(i);
	if (tempNode instanceof ValueExpr) {
	continue;
	}
	optional.addArg((TupleExpr) tempNode);
	}
	} else {
	for (int i = node.getPosition() + 1; i < finalPos + 1; i++) {
	QueryModelNode tempNode = queryNodes.get(i);
	if (tempNode instanceof ValueExpr) {
	continue;
	}
	optional.removeArg((TupleExpr) tempNode);
	}
	}
	node.setNode(optional);
	// FlattenedOptional equals does not take into account var counts
	// The following three lines update the var count in the optional in
	// list
	int index = queryNodes.indexOf(optional);
	queryNodes.remove(optional);
	queryNodes.add(index, optional);
	leftJoinPosSet.add(node);

	} else {
	TupleExpr te = (TupleExpr) node.getNode();
	SortedSet<PositionNode> optionals;
	if (diff < 0) {
	optionals = leftJoinPosSet.subSet(new PositionNode(finalPos), true, node, false);
	for (PositionNode pNode : optionals) {
	FlattenedOptional optional = (FlattenedOptional) pNode.getNode();
	optional.removeArg(te);
	}
	} else {
	optionals = leftJoinPosSet.subSet(node, false, new PositionNode(finalPos), true);
	for (PositionNode pNode : optionals) {
	FlattenedOptional optional = (FlattenedOptional) pNode.getNode();
	optional.addArg(te);
	}
	}
	}

	}

	// works only if moving node to final position does not move it across
	// another node in set
	private void updatePositionNode(PositionNode node, int position, TreeSet<PositionNode> set) {
	set.remove(node);
	node.setPosition(position);
	set.add(node);
	}

	// assumes input data fall within capacity of list
	private void updateNodeList(PositionNode node, int finalPos, List<QueryModelNode> list) {
	int initialPos = node.getPosition();
	QueryModelNode qNode = list.remove(initialPos);
	if (finalPos < list.size()) {
	list.add(finalPos, qNode);
	} else {
	list.add(qNode);
	}
	}

	/**
	*
	* @param node
	* @param finalPos
	* @param list
	* @param leftJoinNodes
	* @return PositionNode - if node cannot be move to final position, this
	* method returns a non-empty PositionNode representing a bound to
	* the move. If it can, it returns an empty PositionNode.
	*/
	// determine if given node can be moved to finalPos
	// assumes node.position and finalPos fall within index range of list
	private PositionNode getBounds(PositionNode node, int finalPos, List<QueryModelNode> list,
	TreeSet<PositionNode> leftJoinNodes) {

	// filters can be moved up and pushed down join segment
	// without affecting bound and unbound variables of
	// FlattenedOptionals -- Filters can be pushed down as
	// far as possible because it is assumed that any variable
	// that appears in a Filter also appears in a ExternalSet node
	// if Filters can be grouped, then Filter variables will
	// automatically be bound
	if (node.getNode() instanceof ValueExpr) {
	return new PositionNode();
	}

	int diff = finalPos - node.getPosition();

	if (diff == 0) {
	return new PositionNode();
	}

	if (node.isOptional) {
	FlattenedOptional optional = ((FlattenedOptional) node.getNode()).clone();
	if (diff < 0) {
	for (int i = node.getPosition() - 1; i > finalPos - 1; i--) {
	QueryModelNode tempNode = list.get(i);
	if (tempNode instanceof ValueExpr) {
	continue;
	}

	if (!optional.canAddTuple((TupleExpr) tempNode)) {
	return new PositionNode(tempNode, i);
	}

	if (tempNode instanceof FlattenedOptional) {
	FlattenedOptional tempOptional = (FlattenedOptional) tempNode;
	if (!tempOptional.canRemoveTuple(optional)) {
	return new PositionNode(tempNode, i);
	}

	}
	optional.addArg((TupleExpr) tempNode);
	}
	} else {
	for (int i = node.getPosition() + 1; i < finalPos + 1; i++) { // TODO
	// check
	// bounds
	QueryModelNode tempNode = list.get(i);
	if (tempNode instanceof ValueExpr) {
	continue;
	}
	if (!optional.canRemoveTuple((TupleExpr) tempNode)) {
	return new PositionNode(tempNode, i);
	}

	if (tempNode instanceof FlattenedOptional) {
	FlattenedOptional tempOptional = (FlattenedOptional) tempNode;
	if (!tempOptional.canAddTuple(optional)) {
	return new PositionNode(tempNode, i);
	}
	}
	optional.removeArg((TupleExpr) tempNode);
	}
	}

	return new PositionNode();

	} else {
	TupleExpr te = (TupleExpr) node.getNode();
	SortedSet<PositionNode> leftJoins;
	if (diff < 0) {
	leftJoins = leftJoinNodes.subSet(new PositionNode(finalPos), true, node, false);

	for (PositionNode pNode : leftJoins) {
	FlattenedOptional optional = (FlattenedOptional) pNode.getNode();
	if (!optional.canRemoveTuple(te)) {
	return new PositionNode(pNode);
	}
	}
	} else {

	leftJoins = leftJoinNodes.subSet(node, false, new PositionNode(finalPos), true);
	for (PositionNode pNode : leftJoins) {
	FlattenedOptional optional = (FlattenedOptional) pNode.getNode();
	if (!optional.canAddTuple(te)) {
	return new PositionNode(pNode);
	}
	}
	}

	return new PositionNode();

	}

	}

	static class Move {

	PositionNode node;
	int finalPos;
	boolean isEmpty = true;

	public Move(PositionNode node, int finalPos) {
	this.node = node;
	this.finalPos = finalPos;
	this.isEmpty = false;
	}

	public Move() {
	}

	}

	static class PositionNode {

	private int position;
	private QueryModelNode node;
	private boolean isOptional = false;
	boolean isEmpty = true;

	public PositionNode(QueryModelNode node, int position) {
	this.node = node;
	this.position = position;
	this.isOptional = node instanceof FlattenedOptional;
	isEmpty = false;
	}

	public PositionNode(PositionNode node) {
	this(node.node, node.position);
	}

	public PositionNode(int position) {
	this.position = position;
	isEmpty = false;
	}

	public PositionNode() {

	}

	/**
	* @return the position
	*/
	public int getPosition() {
	return position;
	}

	/**
	* @param position
	* the position to set
	*/
	public void setPosition(int position) {
	this.position = position;
	}

	/**
	* @return the node
	*/
	public QueryModelNode getNode() {
	return node;
	}

	public void setNode(QueryModelNode node) {
	this.node = node;
	}

	public boolean isOptional() {
	return isOptional;
	}

	@Override
	public String toString() {
	return "Node: " + node + " Position: " + position;
	}

	}

	class PositionComparator implements Comparator<PositionNode> {

	@Override
	public int compare(PositionNode node1, PositionNode node2) {

	if (node1.position < node2.position) {
	return -1;
	}
	if (node1.position > node2.position) {
	return 1;
	}

	return 0;
	}

	}

	}