You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@usergrid.apache.org by sn...@apache.org on 2014/01/28 23:21:42 UTC
[32/96] [abbrv] [partial] Change package namespace to
org.apache.usergrid
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/exceptions/TransactionNotFoundException.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/exceptions/TransactionNotFoundException.java b/stack/core/src/main/java/org/apache/usergrid/persistence/exceptions/TransactionNotFoundException.java
new file mode 100644
index 0000000..21bc13e
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/exceptions/TransactionNotFoundException.java
@@ -0,0 +1,45 @@
+/*******************************************************************************
+ * Copyright 2012 Apigee Corporation
+ *
+ * Licensed 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.
+ ******************************************************************************/
+package org.apache.usergrid.persistence.exceptions;
+
+
+public class TransactionNotFoundException extends PersistenceException {
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = -3579346096812510039L;
+
+
+ public TransactionNotFoundException() {
+ super();
+ }
+
+
+ public TransactionNotFoundException( String message, Throwable cause ) {
+ super( message, cause );
+ }
+
+
+ public TransactionNotFoundException( String message ) {
+ super( message );
+ }
+
+
+ public TransactionNotFoundException( Throwable cause ) {
+ super( cause );
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/exceptions/UnexpectedEntityTypeException.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/exceptions/UnexpectedEntityTypeException.java b/stack/core/src/main/java/org/apache/usergrid/persistence/exceptions/UnexpectedEntityTypeException.java
new file mode 100644
index 0000000..7f59830
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/exceptions/UnexpectedEntityTypeException.java
@@ -0,0 +1,45 @@
+/*******************************************************************************
+ * Copyright 2012 Apigee Corporation
+ *
+ * Licensed 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.
+ ******************************************************************************/
+package org.apache.usergrid.persistence.exceptions;
+
+
+public class UnexpectedEntityTypeException extends PersistenceException {
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = 8221919267880904834L;
+
+
+ public UnexpectedEntityTypeException() {
+ super();
+ }
+
+
+ public UnexpectedEntityTypeException( String message, Throwable cause ) {
+ super( message, cause );
+ }
+
+
+ public UnexpectedEntityTypeException( String message ) {
+ super( message );
+ }
+
+
+ public UnexpectedEntityTypeException( Throwable cause ) {
+ super( cause );
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/geo/CollectionGeoSearch.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/geo/CollectionGeoSearch.java b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/CollectionGeoSearch.java
new file mode 100644
index 0000000..eed451e
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/CollectionGeoSearch.java
@@ -0,0 +1,51 @@
+package org.apache.usergrid.persistence.geo;
+
+
+import java.nio.ByteBuffer;
+import java.util.List;
+import java.util.TreeSet;
+import java.util.UUID;
+
+import org.apache.usergrid.persistence.EntityManager;
+import org.apache.usergrid.persistence.EntityRef;
+import org.apache.usergrid.persistence.IndexBucketLocator;
+import org.apache.usergrid.persistence.cassandra.CassandraService;
+import org.apache.usergrid.persistence.geo.model.Point;
+
+import me.prettyprint.hector.api.beans.HColumn;
+import static org.apache.usergrid.persistence.cassandra.CassandraPersistenceUtils.key;
+
+
+/**
+ * Class for loading collection search data
+ *
+ * @author tnine
+ */
+public class CollectionGeoSearch extends GeoIndexSearcher {
+
+ private final String collectionName;
+ private final EntityRef headEntity;
+
+
+ public CollectionGeoSearch( EntityManager entityManager, IndexBucketLocator locator, CassandraService cass,
+ EntityRef headEntity, String collectionName ) {
+ super( entityManager, locator, cass );
+ this.collectionName = collectionName;
+ this.headEntity = headEntity;
+ }
+
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see org.apache.usergrid.persistence.query.ir.result.GeoIterator.GeoIndexSearcher
+ * #doSearch()
+ */
+ @Override
+ protected TreeSet<HColumn<ByteBuffer, ByteBuffer>> doSearch( List<String> geoCells, UUID startId, Point searchPoint,
+ String propertyName, int pageSize ) throws Exception {
+
+ return query( key( headEntity.getUuid(), collectionName, propertyName ), geoCells, searchPoint, startId,
+ pageSize );
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/geo/ConnectionGeoSearch.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/geo/ConnectionGeoSearch.java b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/ConnectionGeoSearch.java
new file mode 100644
index 0000000..be0d620
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/ConnectionGeoSearch.java
@@ -0,0 +1,50 @@
+package org.apache.usergrid.persistence.geo;
+
+
+import java.nio.ByteBuffer;
+import java.util.List;
+import java.util.TreeSet;
+import java.util.UUID;
+
+import org.apache.usergrid.persistence.EntityManager;
+import org.apache.usergrid.persistence.IndexBucketLocator;
+import org.apache.usergrid.persistence.cassandra.CassandraService;
+import org.apache.usergrid.persistence.geo.model.Point;
+
+import me.prettyprint.hector.api.beans.HColumn;
+import static org.apache.usergrid.persistence.Schema.INDEX_CONNECTIONS;
+import static org.apache.usergrid.persistence.cassandra.CassandraPersistenceUtils.key;
+
+
+/**
+ * Class for loading connection data
+ *
+ * @author tnine
+ */
+public class ConnectionGeoSearch extends GeoIndexSearcher {
+
+ private final UUID connectionId;
+
+
+ public ConnectionGeoSearch( EntityManager entityManager, IndexBucketLocator locator, CassandraService cass,
+ UUID connectionId ) {
+ super( entityManager, locator, cass );
+
+ this.connectionId = connectionId;
+ }
+
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see
+ * org.apache.usergrid.persistence.query.ir.result.GeoIterator.GeoIndexSearcher
+ * #doSearch()
+ */
+ @Override
+ protected TreeSet<HColumn<ByteBuffer, ByteBuffer>> doSearch( List<String> geoCells, UUID startId, Point searchPoint,
+ String propertyName, int pageSize ) throws Exception {
+
+ return query( key( connectionId, INDEX_CONNECTIONS, propertyName ), geoCells, searchPoint, startId, pageSize );
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/geo/EntityLocationRef.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/geo/EntityLocationRef.java b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/EntityLocationRef.java
new file mode 100644
index 0000000..138edae
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/EntityLocationRef.java
@@ -0,0 +1,210 @@
+package org.apache.usergrid.persistence.geo;
+
+
+import java.util.UUID;
+
+import org.apache.usergrid.persistence.EntityRef;
+import org.apache.usergrid.persistence.geo.model.Point;
+import org.apache.usergrid.utils.UUIDUtils;
+
+import me.prettyprint.hector.api.beans.DynamicComposite;
+import static org.apache.commons.lang.math.NumberUtils.toDouble;
+import static org.apache.usergrid.utils.StringUtils.stringOrSubstringAfterLast;
+import static org.apache.usergrid.utils.StringUtils.stringOrSubstringBeforeFirst;
+
+
+public class EntityLocationRef implements EntityRef {
+
+ private UUID uuid;
+
+ private String type;
+
+ private UUID timestampUuid = UUIDUtils.newTimeUUID();
+
+ private double latitude;
+
+ private double longitude;
+
+ private double distance;
+
+
+ public EntityLocationRef() {
+ }
+
+
+ public EntityLocationRef( EntityRef entity, double latitude, double longitude ) {
+ this( entity.getType(), entity.getUuid(), latitude, longitude );
+ }
+
+
+ public EntityLocationRef( String type, UUID uuid, double latitude, double longitude ) {
+ this.type = type;
+ this.uuid = uuid;
+ this.latitude = latitude;
+ this.longitude = longitude;
+ }
+
+
+ public EntityLocationRef( EntityRef entity, UUID timestampUuid, double latitude, double longitude ) {
+ this( entity.getType(), entity.getUuid(), timestampUuid, latitude, longitude );
+ }
+
+
+ public EntityLocationRef( String type, UUID uuid, UUID timestampUuid, double latitude, double longitude ) {
+ this.type = type;
+ this.uuid = uuid;
+ this.timestampUuid = timestampUuid;
+ this.latitude = latitude;
+ this.longitude = longitude;
+ }
+
+
+ public EntityLocationRef( EntityRef entity, UUID timestampUuid, String coord ) {
+ this.type = entity.getType();
+ this.uuid = entity.getUuid();
+ this.timestampUuid = timestampUuid;
+ this.latitude = toDouble( stringOrSubstringBeforeFirst( coord, ',' ) );
+ this.longitude = toDouble( stringOrSubstringAfterLast( coord, ',' ) );
+ }
+
+
+ @Override
+ public UUID getUuid() {
+ return uuid;
+ }
+
+
+ public void setUuid( UUID uuid ) {
+ this.uuid = uuid;
+ }
+
+
+ @Override
+ public String getType() {
+ return type;
+ }
+
+
+ public void setType( String type ) {
+ this.type = type;
+ }
+
+
+ public UUID getTimestampUuid() {
+ return timestampUuid;
+ }
+
+
+ public void setTimestampUuid( UUID timestampUuid ) {
+ this.timestampUuid = timestampUuid;
+ }
+
+
+ public double getLatitude() {
+ return latitude;
+ }
+
+
+ public void setLatitude( double latitude ) {
+ this.latitude = latitude;
+ }
+
+
+ public double getLongitude() {
+ return longitude;
+ }
+
+
+ public void setLongitude( double longitude ) {
+ this.longitude = longitude;
+ }
+
+
+ public Point getPoint() {
+ return new Point( latitude, longitude );
+ }
+
+
+ public DynamicComposite getColumnName() {
+ return new DynamicComposite( uuid, type, timestampUuid );
+ }
+
+
+ public DynamicComposite getColumnValue() {
+ return new DynamicComposite( latitude, longitude );
+ }
+
+
+ public long getTimestampInMicros() {
+ return UUIDUtils.getTimestampInMicros( timestampUuid );
+ }
+
+
+ public long getTimestampInMillis() {
+ return UUIDUtils.getTimestampInMillis( timestampUuid );
+ }
+
+
+ public double getDistance() {
+ return distance;
+ }
+
+
+ /** Calculate, set and return the distance from this location to the point specified */
+ public double calcDistance( Point point ) {
+ distance = GeocellUtils.distance( getPoint(), point );
+ return distance;
+ }
+
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see java.lang.Object#hashCode()
+ */
+ @Override
+ public int hashCode() {
+ final int prime = 31;
+ int result = 1;
+ result = prime * result + ( ( type == null ) ? 0 : type.hashCode() );
+ result = prime * result + ( ( uuid == null ) ? 0 : uuid.hashCode() );
+ return result;
+ }
+
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see java.lang.Object#equals(java.lang.Object)
+ */
+ @Override
+ public boolean equals( Object obj ) {
+ if ( this == obj ) {
+ return true;
+ }
+ if ( obj == null ) {
+ return false;
+ }
+ if ( getClass() != obj.getClass() ) {
+ return false;
+ }
+ EntityLocationRef other = ( EntityLocationRef ) obj;
+ if ( type == null ) {
+ if ( other.type != null ) {
+ return false;
+ }
+ }
+ else if ( !type.equals( other.type ) ) {
+ return false;
+ }
+ if ( uuid == null ) {
+ if ( other.uuid != null ) {
+ return false;
+ }
+ }
+ else if ( !uuid.equals( other.uuid ) ) {
+ return false;
+ }
+ return true;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/geo/EntityLocationRefDistanceComparator.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/geo/EntityLocationRefDistanceComparator.java b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/EntityLocationRefDistanceComparator.java
new file mode 100644
index 0000000..baa5218
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/EntityLocationRefDistanceComparator.java
@@ -0,0 +1,77 @@
+/*******************************************************************************
+ * Copyright 2012 Apigee Corporation
+ *
+ * Licensed 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.
+ ******************************************************************************/
+package org.apache.usergrid.persistence.geo;
+
+
+import java.util.Comparator;
+
+import org.apache.usergrid.utils.UUIDUtils;
+
+
+/**
+ * Compares 2 entity location refs by distance. The one with the larger distance is considered greater than one with a
+ * smaller distance. If the distances are the same they time uuids are compared based on the UUIDUtils.compare for time
+ * uuids. The one with a larger time is considered greater
+ *
+ * @author tnine
+ */
+public class EntityLocationRefDistanceComparator implements Comparator<EntityLocationRef> {
+
+ /**
+ *
+ */
+ public EntityLocationRefDistanceComparator() {
+ }
+
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
+ */
+ @Override
+ public int compare( EntityLocationRef o1, EntityLocationRef o2 ) {
+
+ if ( o1 == null ) {
+
+ //second is not null
+ if ( o2 != null ) {
+ return 1;
+ }
+ //both null
+ return 0;
+ }
+ //second is null, first isn't
+ else if ( o2 == null ) {
+ return -1;
+ }
+
+ double o1Distance = o1.getDistance();
+ double o2Distance = o2.getDistance();
+
+
+ int doubleCompare = Double.compare( o1Distance, o2Distance );
+
+
+ // int doubleCompare = Double.compare(o1.getDistance(), o2.getDistance());
+
+ if ( doubleCompare != 0 ) {
+ return doubleCompare;
+ }
+
+ return UUIDUtils.compare( o1.getUuid(), o2.getUuid() );
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/geo/GeoIndexSearcher.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/geo/GeoIndexSearcher.java b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/GeoIndexSearcher.java
new file mode 100644
index 0000000..d3f1158
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/GeoIndexSearcher.java
@@ -0,0 +1,366 @@
+package org.apache.usergrid.persistence.geo;
+
+
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.TreeSet;
+import java.util.UUID;
+
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+import org.apache.commons.lang.StringUtils;
+import org.apache.usergrid.persistence.EntityManager;
+import org.apache.usergrid.persistence.IndexBucketLocator;
+import org.apache.usergrid.persistence.IndexBucketLocator.IndexType;
+import org.apache.usergrid.persistence.cassandra.CassandraService;
+import org.apache.usergrid.persistence.cassandra.GeoIndexManager;
+import org.apache.usergrid.persistence.cassandra.index.IndexMultiBucketSetLoader;
+import org.apache.usergrid.persistence.geo.model.Point;
+import org.apache.usergrid.persistence.geo.model.Tuple;
+
+import me.prettyprint.cassandra.serializers.DoubleSerializer;
+import me.prettyprint.cassandra.serializers.StringSerializer;
+import me.prettyprint.cassandra.serializers.UUIDSerializer;
+import me.prettyprint.hector.api.beans.AbstractComposite.ComponentEquality;
+import me.prettyprint.hector.api.beans.DynamicComposite;
+import me.prettyprint.hector.api.beans.HColumn;
+import static org.apache.usergrid.persistence.Schema.DICTIONARY_GEOCELL;
+import static org.apache.usergrid.persistence.cassandra.ApplicationCF.ENTITY_INDEX;
+import static org.apache.usergrid.persistence.cassandra.CassandraPersistenceUtils.key;
+import static org.apache.usergrid.utils.CompositeUtils.setEqualityFlag;
+
+
+public abstract class GeoIndexSearcher {
+
+ private static final Logger logger = LoggerFactory.getLogger( GeoIndexSearcher.class );
+
+ private static final EntityLocationRefDistanceComparator COMP = new EntityLocationRefDistanceComparator();
+
+ // The maximum *practical* geocell resolution.
+ private static final int MAX_GEOCELL_RESOLUTION = GeoIndexManager.MAX_RESOLUTION;
+
+ /** Max number of records to read+parse from cass per tile */
+ private static final int MAX_FETCH_SIZE = 1000;
+
+ protected final EntityManager em;
+ protected final IndexBucketLocator locator;
+ protected final CassandraService cass;
+
+
+ /**
+ * @param entityManager
+ * @param pageSize
+ * @param headEntity
+ * @param searchPoint
+ * @param propertyName
+ * @param distance
+ */
+ public GeoIndexSearcher( EntityManager entityManager, IndexBucketLocator locator, CassandraService cass ) {
+ this.em = entityManager;
+ this.locator = locator;
+ this.cass = cass;
+ }
+
+
+ /**
+ * Perform a search from the center. The corresponding entities returned must be >= minDistance(inclusive) and <
+ * maxDistance (exclusive)
+ *
+ * @param maxResults The maximum number of results to include
+ * @param minDistance The minimum distance (inclusive)
+ * @param maxDistance The maximum distance (exclusive)
+ * @param entityClass The entity class
+ * @param baseQuery The base query
+ * @param queryEngine The query engine to use
+ * @param maxGeocellResolution The max resolution to use when searching
+ */
+ public final SearchResults proximitySearch( final EntityLocationRef minMatch, final List<String> geoCells,
+ Point searchPoint, String propertyName, double minDistance,
+ double maxDistance, final int maxResults ) throws Exception {
+
+ List<EntityLocationRef> entityLocations = new ArrayList<EntityLocationRef>( maxResults );
+
+ List<String> curGeocells = new ArrayList<String>();
+ String curContainingGeocell = null;
+
+ // we have some cells used from last time, re-use them
+ if ( geoCells != null && geoCells.size() > 0 ) {
+ curGeocells.addAll( geoCells );
+ curContainingGeocell = geoCells.get( 0 );
+ }
+ // start at the bottom
+ else {
+
+ /*
+ * The currently-being-searched geocells. NOTES: Start with max possible.
+ * Must always be of the same resolution. Must always form a rectangular
+ * region. One of these must be equal to the cur_containing_geocell.
+ */
+ curContainingGeocell = GeocellUtils.compute( searchPoint, MAX_GEOCELL_RESOLUTION );
+ curGeocells.add( curContainingGeocell );
+ }
+
+ if ( minMatch != null ) {
+ minMatch.calcDistance( searchPoint );
+ }
+ // Set of already searched cells
+ Set<String> searchedCells = new HashSet<String>();
+
+ List<String> curGeocellsUnique = null;
+
+ double closestPossibleNextResultDist = 0;
+
+ /*
+ * Assumes both a and b are lists of (entity, dist) tuples, *sorted by
+ * dist*. NOTE: This is an in-place merge, and there are guaranteed no
+ * duplicates in the resulting list.
+ */
+
+ int noDirection[] = { 0, 0 };
+ List<Tuple<int[], Double>> sortedEdgesDistances = Arrays.asList( new Tuple<int[], Double>( noDirection, 0d ) );
+ boolean done = false;
+ UUID lastReturned = null;
+
+ while ( !curGeocells.isEmpty() && entityLocations.size() < maxResults ) {
+ closestPossibleNextResultDist = sortedEdgesDistances.get( 0 ).getSecond();
+ if ( maxDistance > 0 && closestPossibleNextResultDist > maxDistance ) {
+ break;
+ }
+
+ Set<String> curTempUnique = new HashSet<String>( curGeocells );
+ curTempUnique.removeAll( searchedCells );
+ curGeocellsUnique = new ArrayList<String>( curTempUnique );
+
+ Set<HColumn<ByteBuffer, ByteBuffer>> queryResults = null;
+
+ lastReturned = null;
+
+ // we need to keep searching everything in our tiles until we don't get
+ // any more results, then we'll have the closest points and can move on
+ // do the next tiles
+ do {
+ queryResults = doSearch( curGeocellsUnique, lastReturned, searchPoint, propertyName, MAX_FETCH_SIZE );
+
+ if ( logger.isDebugEnabled() ) {
+ logger.debug( "fetch complete for: {}", StringUtils.join( curGeocellsUnique, ", " ) );
+ }
+
+ searchedCells.addAll( curGeocells );
+
+ // Begin storing distance from the search result entity to the
+ // search center along with the search result itself, in a tuple.
+
+ // Merge new_results into results
+ for ( HColumn<ByteBuffer, ByteBuffer> column : queryResults ) {
+
+ DynamicComposite composite = DynamicComposite.fromByteBuffer( column.getName() );
+
+ UUID uuid = composite.get( 0, UUIDSerializer.get() );
+
+ lastReturned = uuid;
+
+ String type = composite.get( 1, StringSerializer.get() );
+ UUID timestampUuid = composite.get( 2, UUIDSerializer.get() );
+ composite = DynamicComposite.fromByteBuffer( column.getValue() );
+ Double latitude = composite.get( 0, DoubleSerializer.get() );
+ Double longitude = composite.get( 1, DoubleSerializer.get() );
+
+ EntityLocationRef entityLocation =
+ new EntityLocationRef( type, uuid, timestampUuid, latitude, longitude );
+
+ double distance = entityLocation.calcDistance( searchPoint );
+
+ // discard, it's too close or too far, of closer than the minimum we
+ // should match, skip it
+ if ( distance < minDistance || ( maxDistance != 0 && distance > maxDistance ) || ( minMatch != null
+ && COMP.compare( entityLocation, minMatch ) <= 0 ) ) {
+ continue;
+ }
+
+ int index = Collections.binarySearch( entityLocations, entityLocation, COMP );
+
+ // already in the index
+ if ( index > -1 ) {
+ continue;
+ }
+
+ // set the insert index
+ index = ( index + 1 ) * -1;
+
+ // no point in adding it
+ if ( index >= maxResults ) {
+ continue;
+ }
+
+ // results.add(index, entity);
+ // distances.add(index, distance);
+ entityLocations.add( index, entityLocation );
+
+ /**
+ * Discard an additional entries as we iterate to avoid holding them
+ * all in ram
+ */
+ while ( entityLocations.size() > maxResults ) {
+ entityLocations.remove( entityLocations.size() - 1 );
+ }
+ }
+ }
+ while ( queryResults != null && queryResults.size() == MAX_FETCH_SIZE );
+
+ /**
+ * We've searched everything and have a full set, we want to return the
+ * "current" tiles to search next time for the cursor, since cass could
+ * contain more results
+ */
+ if ( done || entityLocations.size() == maxResults ) {
+ break;
+ }
+
+ sortedEdgesDistances = GeocellUtils.distanceSortedEdges( curGeocells, searchPoint );
+
+ if ( queryResults.size() == 0 || curGeocells.size() == 4 ) {
+ /*
+ * Either no results (in which case we optimize by not looking at
+ * adjacents, go straight to the parent) or we've searched 4 adjacent
+ * geocells, in which case we should now search the parents of those
+ * geocells.
+ */
+ curContainingGeocell =
+ curContainingGeocell.substring( 0, Math.max( curContainingGeocell.length() - 1, 0 ) );
+ if ( curContainingGeocell.length() == 0 ) {
+ // final check - top level tiles
+ curGeocells.clear();
+ String[] items = "0123456789abcdef".split( "(?!^)" );
+ for ( String item : items ) {
+ curGeocells.add( item );
+ }
+ done = true;
+ }
+ else {
+ List<String> oldCurGeocells = new ArrayList<String>( curGeocells );
+ curGeocells.clear();
+ for ( String cell : oldCurGeocells ) {
+ if ( cell.length() > 0 ) {
+ String newCell = cell.substring( 0, cell.length() - 1 );
+ if ( !curGeocells.contains( newCell ) ) {
+ curGeocells.add( newCell );
+ }
+ }
+ }
+ }
+ }
+ else if ( curGeocells.size() == 1 ) {
+ // Get adjacent in one direction.
+ // TODO(romannurik): Watch for +/- 90 degree latitude edge case
+ // geocells.
+ for ( int i = 0; i < sortedEdgesDistances.size(); i++ ) {
+
+ int nearestEdge[] = sortedEdgesDistances.get( i ).getFirst();
+ String edge = GeocellUtils.adjacent( curGeocells.get( 0 ), nearestEdge );
+
+ // we're at the edge of the world, search in a different direction
+ if ( edge == null ) {
+ continue;
+ }
+
+ curGeocells.add( edge );
+ break;
+ }
+ }
+ else if ( curGeocells.size() == 2 ) {
+ // Get adjacents in perpendicular direction.
+ int nearestEdge[] =
+ GeocellUtils.distanceSortedEdges( Arrays.asList( curContainingGeocell ), searchPoint ).get( 0 )
+ .getFirst();
+ int[] perpendicularNearestEdge = { 0, 0 };
+ if ( nearestEdge[0] == 0 ) {
+ // Was vertical, perpendicular is horizontal.
+ for ( Tuple<int[], Double> edgeDistance : sortedEdgesDistances ) {
+ if ( edgeDistance.getFirst()[0] != 0 ) {
+ perpendicularNearestEdge = edgeDistance.getFirst();
+ break;
+ }
+ }
+ }
+ else {
+ // Was horizontal, perpendicular is vertical.
+ for ( Tuple<int[], Double> edgeDistance : sortedEdgesDistances ) {
+ if ( edgeDistance.getFirst()[0] == 0 ) {
+ perpendicularNearestEdge = edgeDistance.getFirst();
+ break;
+ }
+ }
+ }
+ List<String> tempCells = new ArrayList<String>();
+ for ( String cell : curGeocells ) {
+ tempCells.add( GeocellUtils.adjacent( cell, perpendicularNearestEdge ) );
+ }
+ curGeocells.addAll( tempCells );
+ }
+
+ logger.debug( "{} results found.", entityLocations.size() );
+ }
+
+ // now we have our final sets, construct the results
+
+ return new SearchResults( entityLocations, curGeocells );
+ }
+
+
+ protected TreeSet<HColumn<ByteBuffer, ByteBuffer>> query( Object key, List<String> curGeocellsUnique,
+ Point searchPoint, UUID startId, int count )
+ throws Exception {
+
+ List<Object> keys = new ArrayList<Object>();
+
+ UUID appId = em.getApplicationRef().getUuid();
+
+ for ( String geoCell : curGeocellsUnique ) {
+
+ // add buckets for each geoCell
+
+ for ( String indexBucket : locator.getBuckets( appId, IndexType.GEO, geoCell ) ) {
+ keys.add( key( key, DICTIONARY_GEOCELL, geoCell, indexBucket ) );
+ }
+ }
+
+ DynamicComposite start = null;
+
+ if ( startId != null ) {
+ start = new DynamicComposite( startId );
+ setEqualityFlag( start, ComponentEquality.GREATER_THAN_EQUAL );
+ }
+
+ TreeSet<HColumn<ByteBuffer, ByteBuffer>> columns =
+ IndexMultiBucketSetLoader.load( cass, ENTITY_INDEX, appId, keys, start, null, count, false );
+
+ return columns;
+ }
+
+
+ protected abstract TreeSet<HColumn<ByteBuffer, ByteBuffer>> doSearch( List<String> geoCells, UUID startId,
+ Point searchPoint, String propertyName,
+ int pageSize ) throws Exception;
+
+
+ public static class SearchResults {
+
+ public final List<EntityLocationRef> entityLocations;
+ public final List<String> lastSearchedGeoCells;
+
+
+ /**
+ * @param entityLocations
+ * @param curGeocells
+ */
+ public SearchResults( List<EntityLocationRef> entityLocations, List<String> lastSearchedGeoCells ) {
+ this.entityLocations = entityLocations;
+ this.lastSearchedGeoCells = lastSearchedGeoCells;
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/geo/GeocellManager.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/geo/GeocellManager.java b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/GeocellManager.java
new file mode 100644
index 0000000..c69a291
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/GeocellManager.java
@@ -0,0 +1,179 @@
+package org.apache.usergrid.persistence.geo;
+
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+
+import org.apache.usergrid.persistence.cassandra.GeoIndexManager;
+import org.apache.usergrid.persistence.geo.model.BoundingBox;
+import org.apache.usergrid.persistence.geo.model.CostFunction;
+import org.apache.usergrid.persistence.geo.model.DefaultCostFunction;
+import org.apache.usergrid.persistence.geo.model.Point;
+
+
+/**
+ #
+ # Copyright 2010 Alexandre Gellibert
+ #
+ # Licensed 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.
+ */
+
+
+/**
+ * Ported java version of python geocell: http://code.google.com/p/geomodel/source/browse/trunk/geo/geocell.py
+ * <p/>
+ * Defines the notion of 'geocells' and exposes methods to operate on them.
+ * <p/>
+ * A geocell is a hexadecimal string that defines a two dimensional rectangular region inside the [-90,90] x [-180,180]
+ * latitude/longitude space. A geocell's 'resolution' is its length. For most practical purposes, at high resolutions,
+ * geocells can be treated as single points.
+ * <p/>
+ * Much like geohashes (see http://en.wikipedia.org/wiki/Geohash), geocells are hierarchical, in that any prefix of a
+ * geocell is considered its ancestor, with geocell[:-1] being geocell's immediate parent cell.
+ * <p/>
+ * To calculate the rectangle of a given geocell string, first divide the [-90,90] x [-180,180] latitude/longitude space
+ * evenly into a 4x4 grid like so:
+ * <p/>
+ * +---+---+---+---+ (90, 180) | a | b | e | f | +---+---+---+---+ | 8 | 9 | c | d | +---+---+---+---+ | 2 | 3 | 6 | 7 |
+ * +---+---+---+---+ | 0 | 1 | 4 | 5 | (-90,-180) +---+---+---+---+
+ * <p/>
+ * NOTE: The point (0, 0) is at the intersection of grid cells 3, 6, 9 and c. And, for example, cell 7 should be the
+ * sub-rectangle from (-45, 90) to (0, 180).
+ * <p/>
+ * Calculate the sub-rectangle for the first character of the geocell string and re-divide this sub-rectangle into
+ * another 4x4 grid. For example, if the geocell string is '78a', we will re-divide the sub-rectangle like so:
+ * <p/>
+ * . . . . . . +----+----+----+----+ (0, 180) | 7a | 7b | 7e | 7f |
+ * +----+----+----+----+ | 78 | 79 | 7c | 7d | +----+----+----+----+ | 72 | 73 | 76 | 77 | +----+----+----+----+ | 70 |
+ * 71 | 74 | 75 | . . (-45,90) +----+----+----+----+ . . . .
+ * <p/>
+ * Continue to re-divide into sub-rectangles and 4x4 grids until the entire geocell string has been exhausted. The final
+ * sub-rectangle is the rectangular region for the geocell.
+ *
+ * @author api.roman.public@gmail.com (Roman Nurik)
+ * @author (java portage) Alexandre Gellibert
+ */
+
+public class GeocellManager {
+
+ // The maximum *practical* geocell resolution.
+ public static final int MAX_GEOCELL_RESOLUTION = GeoIndexManager.MAX_RESOLUTION;
+
+ // The maximum number of geocells to consider for a bounding box search.
+ private static final int MAX_FEASIBLE_BBOX_SEARCH_CELLS = 300;
+
+ // Function used if no custom function is used in bestBboxSearchCells method
+ private static final CostFunction DEFAULT_COST_FUNCTION = new DefaultCostFunction();
+
+ // private static final Logger logger = GeocellLogger.get();
+
+
+ /**
+ * Returns the list of geocells (all resolutions) that are containing the point
+ *
+ * @return Returns the list of geocells (all resolutions) that are containing the point
+ */
+ public static List<String> generateGeoCell( Point point ) {
+ List<String> geocells = new ArrayList<String>();
+ String geocellMax = GeocellUtils.compute( point, GeocellManager.MAX_GEOCELL_RESOLUTION );
+ for ( int i = 1; i < GeocellManager.MAX_GEOCELL_RESOLUTION; i++ ) {
+ geocells.add( GeocellUtils.compute( point, i ) );
+ }
+ geocells.add( geocellMax );
+ return geocells;
+ }
+
+
+ /**
+ * Returns an efficient set of geocells to search in a bounding box query.
+ * <p/>
+ * This method is guaranteed to return a set of geocells having the same resolution (except in the case of
+ * antimeridian search i.e when east < west).
+ *
+ * @param bbox: A geotypes.Box indicating the bounding box being searched.
+ * @param costFunction: A function that accepts two arguments: numCells: the number of cells to search resolution:
+ * the resolution of each cell to search and returns the 'cost' of querying against this number of cells at the
+ * given resolution.)
+ *
+ * @return A list of geocell strings that contain the given box.
+ */
+ public static List<String> bestBboxSearchCells( BoundingBox bbox, CostFunction costFunction ) {
+ if ( bbox.getEast() < bbox.getWest() ) {
+ BoundingBox bboxAntimeridian1 =
+ new BoundingBox( bbox.getNorth(), bbox.getEast(), bbox.getSouth(), GeocellUtils.MIN_LONGITUDE );
+ BoundingBox bboxAntimeridian2 =
+ new BoundingBox( bbox.getNorth(), GeocellUtils.MAX_LONGITUDE, bbox.getSouth(), bbox.getWest() );
+ List<String> antimeridianList = bestBboxSearchCells( bboxAntimeridian1, costFunction );
+ antimeridianList.addAll( bestBboxSearchCells( bboxAntimeridian2, costFunction ) );
+ return antimeridianList;
+ }
+
+ String cellNE = GeocellUtils.compute( bbox.getNorthEast(), GeocellManager.MAX_GEOCELL_RESOLUTION );
+ String cellSW = GeocellUtils.compute( bbox.getSouthWest(), GeocellManager.MAX_GEOCELL_RESOLUTION );
+
+ // The current lowest BBOX-search cost found; start with practical infinity.
+ double minCost = Double.MAX_VALUE;
+
+ // The set of cells having the lowest calculated BBOX-search cost.
+ List<String> minCostCellSet = new ArrayList<String>();
+
+ // First find the common prefix, if there is one.. this will be the base
+ // resolution.. i.e. we don't have to look at any higher resolution cells.
+ int minResolution = 0;
+ int maxResoltuion = Math.min( cellNE.length(), cellSW.length() );
+ while ( minResolution < maxResoltuion && cellNE.substring( 0, minResolution + 1 )
+ .startsWith( cellSW.substring( 0, minResolution + 1 ) ) ) {
+ minResolution++;
+ }
+
+ // Iteravely calculate all possible sets of cells that wholely contain
+ // the requested bounding box.
+ for ( int curResolution = minResolution; curResolution < GeocellManager.MAX_GEOCELL_RESOLUTION + 1;
+ curResolution++ ) {
+ String curNE = cellNE.substring( 0, curResolution );
+ String curSW = cellSW.substring( 0, curResolution );
+
+ int numCells = GeocellUtils.interpolationCount( curNE, curSW );
+ if ( numCells > MAX_FEASIBLE_BBOX_SEARCH_CELLS ) {
+ continue;
+ }
+
+ List<String> cellSet = GeocellUtils.interpolate( curNE, curSW );
+ Collections.sort( cellSet );
+
+ double cost;
+ if ( costFunction == null ) {
+ cost = DEFAULT_COST_FUNCTION.defaultCostFunction( cellSet.size(), curResolution );
+ }
+ else {
+ cost = costFunction.defaultCostFunction( cellSet.size(), curResolution );
+ }
+
+ if ( cost <= minCost ) {
+ minCost = cost;
+ minCostCellSet = cellSet;
+ }
+ else {
+ if ( minCostCellSet.size() == 0 ) {
+ minCostCellSet = cellSet;
+ }
+ // Once the cost starts rising, we won't be able to do better, so abort.
+ break;
+ }
+ }
+ // logger.log(Level.INFO, "Calculate cells "+StringUtils.join(minCostCellSet, ",
+ // ")+" in box ("+bbox.getSouth()+","+bbox.getWest()+") ("+bbox.getNorth()+","+bbox.getEast()+")");
+ return minCostCellSet;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/geo/GeocellUtils.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/geo/GeocellUtils.java b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/GeocellUtils.java
new file mode 100644
index 0000000..2bbf694
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/GeocellUtils.java
@@ -0,0 +1,539 @@
+/*
+Copyright 2010 Alexandre Gellibert
+
+Licensed 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.
+ */
+package org.apache.usergrid.persistence.geo;
+
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.LinkedList;
+import java.util.List;
+
+import org.apache.usergrid.persistence.geo.comparator.DoubleTupleComparator;
+import org.apache.usergrid.persistence.geo.model.BoundingBox;
+import org.apache.usergrid.persistence.geo.model.Point;
+import org.apache.usergrid.persistence.geo.model.Tuple;
+
+/**
+ #
+ # Copyright 2010 Alexandre Gellibert
+ #
+ # Licensed 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.
+ */
+
+
+/**
+ * Utils class to compute geocells.
+ *
+ * @author api.roman.public@gmail.com (Roman Nurik)
+ * @author (java portage) Alexandre Gellibert
+ */
+public final class GeocellUtils {
+
+ public static final float MIN_LONGITUDE = -180.0f;
+ public static final float MAX_LONGITUDE = 180.0f;
+ public static final float MIN_LATITUDE = -90.0f;
+ public static final float MAX_LATITUDE = 90.0f;
+ // Geocell algorithm constants.
+ public static final int GEOCELL_GRID_SIZE = 4;
+ private static final String GEOCELL_ALPHABET = "0123456789abcdef";
+
+ // Direction enumerations.
+ private static final int[] NORTHWEST = new int[] { -1, 1 };
+ private static final int[] NORTH = new int[] { 0, 1 };
+ private static final int[] NORTHEAST = new int[] { 1, 1 };
+ private static final int[] EAST = new int[] { 1, 0 };
+ private static final int[] SOUTHEAST = new int[] { 1, -1 };
+ private static final int[] SOUTH = new int[] { 0, -1 };
+ private static final int[] SOUTHWEST = new int[] { -1, -1 };
+ private static final int[] WEST = new int[] { -1, 0 };
+
+ private static final int RADIUS = 6378135;
+
+
+ private GeocellUtils() {
+ // no instantiation allowed
+ }
+
+
+ /**
+ * Determines whether the given cells are collinear along a dimension.
+ * <p/>
+ * Returns True if the given cells are in the same row (columnTest=False) or in the same column (columnTest=True).
+ *
+ * @param cell1 : The first geocell string.
+ * @param cell2 : The second geocell string.
+ * @param columnTest : A boolean, where False invokes a row collinearity test and 1 invokes a column collinearity
+ * test.
+ *
+ * @return A bool indicating whether or not the given cells are collinear in the given dimension.
+ */
+ public static boolean collinear( String cell1, String cell2, boolean columnTest ) {
+
+ for ( int i = 0; i < Math.min( cell1.length(), cell2.length() ); i++ ) {
+ int l1[] = subdivXY( cell1.charAt( i ) );
+ int x1 = l1[0];
+ int y1 = l1[1];
+ int l2[] = subdivXY( cell2.charAt( i ) );
+ int x2 = l2[0];
+ int y2 = l2[1];
+
+ // Check row collinearity (assure y's are always the same).
+ if ( !columnTest && y1 != y2 ) {
+ return false;
+ }
+
+ // Check column collinearity (assure x's are always the same).
+ if ( columnTest && x1 != x2 ) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+
+ /**
+ * Calculates the grid of cells formed between the two given cells.
+ * <p/>
+ * Generates the set of cells in the grid created by interpolating from the given Northeast geocell to the given
+ * Southwest geocell.
+ * <p/>
+ * Assumes the Northeast geocell is actually Northeast of Southwest geocell.
+ *
+ * @param cellNE : The Northeast geocell string.
+ * @param cellSW : The Southwest geocell string.
+ *
+ * @return A list of geocell strings in the interpolation.
+ */
+ public static List<String> interpolate( String cellNE, String cellSW ) {
+ // 2D array, will later be flattened.
+ LinkedList<LinkedList<String>> cellSet = new LinkedList<LinkedList<String>>();
+ LinkedList<String> cellFirst = new LinkedList<String>();
+ cellFirst.add( cellSW );
+ cellSet.add( cellFirst );
+
+ // First get adjacent geocells across until Southeast--collinearity with
+ // Northeast in vertical direction (0) means we're at Southeast.
+ while ( !collinear( cellFirst.getLast(), cellNE, true ) ) {
+ String cellTmp = adjacent( cellFirst.getLast(), EAST );
+ if ( cellTmp == null ) {
+ break;
+ }
+ cellFirst.add( cellTmp );
+ }
+
+ // Then get adjacent geocells upwards.
+ while ( !cellSet.getLast().getLast().equalsIgnoreCase( cellNE ) ) {
+
+ LinkedList<String> cellTmpRow = new LinkedList<String>();
+ for ( String g : cellSet.getLast() ) {
+ cellTmpRow.add( adjacent( g, NORTH ) );
+ }
+ if ( cellTmpRow.getFirst() == null ) {
+ break;
+ }
+ cellSet.add( cellTmpRow );
+ }
+
+ // Flatten cellSet, since it's currently a 2D array.
+ List<String> result = new ArrayList<String>();
+ for ( LinkedList<String> list : cellSet ) {
+ result.addAll( list );
+ }
+ return result;
+ }
+
+
+ /**
+ * Computes the number of cells in the grid formed between two given cells.
+ * <p/>
+ * Computes the number of cells in the grid created by interpolating from the given Northeast geocell to the given
+ * Southwest geocell. Assumes the Northeast geocell is actually Northeast of Southwest geocell.
+ *
+ * @param cellNE : The Northeast geocell string.
+ * @param cellSW : The Southwest geocell string.
+ *
+ * @return An int, indicating the number of geocells in the interpolation.
+ */
+ public static int interpolationCount( String cellNE, String cellSW ) {
+
+ BoundingBox bboxNE = computeBox( cellNE );
+ BoundingBox bboxSW = computeBox( cellSW );
+
+ double cellLatSpan = bboxSW.getNorth() - bboxSW.getSouth();
+ double cellLonSpan = bboxSW.getEast() - bboxSW.getWest();
+
+ double numCols = ( ( bboxNE.getEast() - bboxSW.getWest() ) / cellLonSpan );
+ double numRows = ( ( bboxNE.getNorth() - bboxSW.getSouth() ) / cellLatSpan );
+
+ double totalCols = numCols * numRows * 1.0;
+ if ( totalCols > Integer.MAX_VALUE ) {
+ return Integer.MAX_VALUE;
+ }
+ return ( int ) totalCols;
+ }
+
+
+ /**
+ * Calculates all of the given geocell's adjacent geocells.
+ *
+ * @param cell : The geocell string for which to calculate adjacent/neighboring cells.
+ *
+ * @return A list of 8 geocell strings and/or None values indicating adjacent cells.
+ */
+
+ public static List<String> allAdjacents( String cell ) {
+ List<String> result = new ArrayList<String>();
+ for ( int[] d : Arrays.asList( NORTHWEST, NORTH, NORTHEAST, EAST, SOUTHEAST, SOUTH, SOUTHWEST, WEST ) ) {
+ result.add( adjacent( cell, d ) );
+ }
+ return result;
+ }
+
+
+ /**
+ * Calculates the geocell adjacent to the given cell in the given direction.
+ *
+ * @param cell : The geocell string whose neighbor is being calculated.
+ * @param dir : An (x, y) tuple indicating direction, where x and y can be -1, 0, or 1. -1 corresponds to West for x
+ * and South for y, and 1 corresponds to East for x and North for y. Available helper constants are NORTH, EAST,
+ * SOUTH, WEST, NORTHEAST, NORTHWEST, SOUTHEAST, and SOUTHWEST.
+ *
+ * @return The geocell adjacent to the given cell in the given direction, or None if there is no such cell.
+ */
+ public static String adjacent( String cell, int[] dir ) {
+ if ( cell == null ) {
+ return null;
+ }
+ int dx = dir[0];
+ int dy = dir[1];
+ char[] cellAdjArr = cell.toCharArray(); // Split the geocell string
+ // characters into a list.
+ int i = cellAdjArr.length - 1;
+
+ while ( i >= 0 && ( dx != 0 || dy != 0 ) ) {
+ int l[] = subdivXY( cellAdjArr[i] );
+ int x = l[0];
+ int y = l[1];
+
+ // Horizontal adjacency.
+ if ( dx == -1 ) { // Asking for left.
+ if ( x == 0 ) { // At left of parent cell.
+ x = GEOCELL_GRID_SIZE - 1; // Becomes right edge of adjacent parent.
+ }
+ else {
+ x--; // Adjacent, same parent.
+ dx = 0; // Done with x.
+ }
+ }
+ else if ( dx == 1 ) { // Asking for right.
+ if ( x == GEOCELL_GRID_SIZE - 1 ) { // At right of parent cell.
+ x = 0; // Becomes left edge of adjacent parent.
+ }
+ else {
+ x++; // Adjacent, same parent.
+ dx = 0; // Done with x.
+ }
+ }
+
+ // Vertical adjacency.
+ if ( dy == 1 ) { // Asking for above.
+ if ( y == GEOCELL_GRID_SIZE - 1 ) { // At top of parent cell.
+ y = 0; // Becomes bottom edge of adjacent parent.
+ }
+ else {
+ y++; // Adjacent, same parent.
+ dy = 0; // Done with y.
+ }
+ }
+ else if ( dy == -1 ) { // Asking for below.
+ if ( y == 0 ) { // At bottom of parent cell.
+ y = GEOCELL_GRID_SIZE - 1; // Becomes top edge of adjacent parent.
+ }
+ else {
+ y--; // Adjacent, same parent.
+ dy = 0; // Done with y.
+ }
+ }
+
+ int l2[] = { x, y };
+ cellAdjArr[i] = subdivChar( l2 );
+ i--;
+ }
+ // If we're not done with y then it's trying to wrap vertically,
+ // which is a failure.
+ if ( dy != 0 ) {
+ return null;
+ }
+
+ // At this point, horizontal wrapping is done inherently.
+ return new String( cellAdjArr );
+ }
+
+
+ /**
+ * Returns whether or not the given cell contains the given point.
+ *
+ * @return Returns whether or not the given cell contains the given point.
+ */
+ public static boolean containsPoint( String cell, Point point ) {
+ return compute( point, cell.length() ).equalsIgnoreCase( cell );
+ }
+
+
+ /**
+ * Returns the shortest distance between a point and a geocell bounding box.
+ * <p/>
+ * If the point is inside the cell, the shortest distance is always to a 'edge' of the cell rectangle. If the point
+ * is outside the cell, the shortest distance will be to either a 'edge' or 'corner' of the cell rectangle.
+ *
+ * @return The shortest distance from the point to the geocell's rectangle, in meters.
+ */
+ public static double pointDistance( String cell, Point point ) {
+ BoundingBox bbox = computeBox( cell );
+
+ boolean betweenWE = bbox.getWest() <= point.getLon() && point.getLon() <= bbox.getEast();
+ boolean betweenNS = bbox.getSouth() <= point.getLat() && point.getLat() <= bbox.getNorth();
+
+ if ( betweenWE ) {
+ if ( betweenNS ) {
+ // Inside the geocell.
+ return Math.min( Math.min( distance( point, new Point( bbox.getSouth(), point.getLon() ) ),
+ distance( point, new Point( bbox.getNorth(), point.getLon() ) ) ),
+ Math.min( distance( point, new Point( point.getLat(), bbox.getEast() ) ),
+ distance( point, new Point( point.getLat(), bbox.getWest() ) ) ) );
+ }
+ else {
+ return Math.min( distance( point, new Point( bbox.getSouth(), point.getLon() ) ),
+ distance( point, new Point( bbox.getNorth(), point.getLon() ) ) );
+ }
+ }
+ else {
+ if ( betweenNS ) {
+ return Math.min( distance( point, new Point( point.getLat(), bbox.getEast() ) ),
+ distance( point, new Point( point.getLat(), bbox.getWest() ) ) );
+ }
+ else {
+ // TODO(romannurik): optimize
+ return Math.min( Math.min( distance( point, new Point( bbox.getSouth(), bbox.getEast() ) ),
+ distance( point, new Point( bbox.getNorth(), bbox.getEast() ) ) ),
+ Math.min( distance( point, new Point( bbox.getSouth(), bbox.getWest() ) ),
+ distance( point, new Point( bbox.getNorth(), bbox.getWest() ) ) ) );
+ }
+ }
+ }
+
+
+ /**
+ * Computes the geocell containing the given point to the given resolution.
+ * <p/>
+ * This is a simple 16-tree lookup to an arbitrary depth (resolution).
+ *
+ * @param point : The geotypes.Point to compute the cell for.
+ * @param resolution : An int indicating the resolution of the cell to compute.
+ *
+ * @return The geocell string containing the given point, of length resolution.
+ */
+ public static String compute( Point point, int resolution ) {
+ float north = MAX_LATITUDE;
+ float south = MIN_LATITUDE;
+ float east = MAX_LONGITUDE;
+ float west = MIN_LONGITUDE;
+
+ StringBuilder cell = new StringBuilder();
+ while ( cell.length() < resolution ) {
+ float subcellLonSpan = ( east - west ) / GEOCELL_GRID_SIZE;
+ float subcellLatSpan = ( north - south ) / GEOCELL_GRID_SIZE;
+
+ int x = Math.min( ( int ) ( GEOCELL_GRID_SIZE * ( point.getLon() - west ) / ( east - west ) ),
+ GEOCELL_GRID_SIZE - 1 );
+ int y = Math.min( ( int ) ( GEOCELL_GRID_SIZE * ( point.getLat() - south ) / ( north - south ) ),
+ GEOCELL_GRID_SIZE - 1 );
+
+ int l[] = { x, y };
+ cell.append( subdivChar( l ) );
+
+ south += subcellLatSpan * y;
+ north = south + subcellLatSpan;
+
+ west += subcellLonSpan * x;
+ east = west + subcellLonSpan;
+ }
+ return cell.toString();
+ }
+
+
+ /**
+ * Computes the rectangular boundaries (bounding box) of the given geocell.
+ *
+ * @param cell_ : The geocell string whose boundaries are to be computed.
+ *
+ * @return A geotypes.Box corresponding to the rectangular boundaries of the geocell.
+ */
+ public static BoundingBox computeBox( String cell_ ) {
+ if ( cell_ == null ) {
+ return null;
+ }
+
+ BoundingBox bbox = new BoundingBox( 90.0, 180.0, -90.0, -180.0 );
+ StringBuilder cell = new StringBuilder( cell_ );
+ while ( cell.length() > 0 ) {
+ double subcellLonSpan = ( bbox.getEast() - bbox.getWest() ) / GEOCELL_GRID_SIZE;
+ double subcellLatSpan = ( bbox.getNorth() - bbox.getSouth() ) / GEOCELL_GRID_SIZE;
+
+ int l[] = subdivXY( cell.charAt( 0 ) );
+ int x = l[0];
+ int y = l[1];
+
+ bbox = new BoundingBox( bbox.getSouth() + subcellLatSpan * ( y + 1 ),
+ bbox.getWest() + subcellLonSpan * ( x + 1 ), bbox.getSouth() + subcellLatSpan * y,
+ bbox.getWest() + subcellLonSpan * x );
+
+ cell.deleteCharAt( 0 );
+ }
+
+ return bbox;
+ }
+
+
+ /**
+ * Returns whether or not the given geocell string defines a valid geocell.
+ *
+ * @return Returns whether or not the given geocell string defines a valid geocell.
+ */
+ public static boolean isValid( String cell ) {
+ if ( cell == null || cell.trim().length() == 0 ) {
+ return false;
+ }
+ for ( char c : cell.toCharArray() ) {
+ if ( GEOCELL_ALPHABET.indexOf( c ) < 0 ) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+
+ /**
+ * Returns the (x, y) of the geocell character in the 4x4 alphabet grid.
+ *
+ * @return Returns the (x, y) of the geocell character in the 4x4 alphabet grid.
+ */
+ public static int[] subdivXY( char char_ ) {
+ // NOTE: This only works for grid size 4.
+ int charI = GEOCELL_ALPHABET.indexOf( char_ );
+ return new int[] {
+ ( charI & 4 ) >> 1 | ( charI & 1 ) >> 0, ( charI & 8 ) >> 2 | ( charI & 2 ) >> 1
+ };
+ }
+
+
+ /**
+ * Returns the geocell character in the 4x4 alphabet grid at pos. (x, y).
+ *
+ * @return Returns the geocell character in the 4x4 alphabet grid at pos. (x, y).
+ */
+ public static char subdivChar( int[] pos ) {
+ // NOTE: This only works for grid size 4.
+ return GEOCELL_ALPHABET.charAt( ( pos[1] & 2 ) << 2 |
+ ( pos[0] & 2 ) << 1 |
+ ( pos[1] & 1 ) << 1 |
+ ( pos[0] & 1 ) << 0 );
+ }
+
+
+ /**
+ * Calculates the great circle distance between two points (law of cosines).
+ *
+ * @param p1 : indicating the first point.
+ * @param p2 : indicating the second point.
+ *
+ * @return The 2D great-circle distance between the two given points, in meters.
+ */
+ public static double distance( Point p1, Point p2 ) {
+ double p1lat = Math.toRadians( p1.getLat() );
+ double p1lon = Math.toRadians( p1.getLon() );
+ double p2lat = Math.toRadians( p2.getLat() );
+ double p2lon = Math.toRadians( p2.getLon() );
+ return RADIUS * Math.acos( makeDoubleInRange(
+ Math.sin( p1lat ) * Math.sin( p2lat ) + Math.cos( p1lat ) * Math.cos( p2lat ) * Math
+ .cos( p2lon - p1lon ) ) );
+ }
+
+
+ /**
+ * This function is used to fix issue 10: GeocellUtils.distance(...) uses Math.acos(arg) method. In some cases arg >
+ * 1 (i.e 1.0000000002), so acos cannot be calculated and the method returns NaN.
+ *
+ * @return a double between -1 and 1
+ */
+ public static double makeDoubleInRange( double d ) {
+ double result = d;
+ if ( d > 1 ) {
+ result = 1;
+ }
+ else if ( d < -1 ) {
+ result = -1;
+ }
+ return result;
+ }
+
+
+ /**
+ * Returns the edges of the rectangular region containing all of the given geocells, sorted by distance from the
+ * given point, along with the actual distances from the point to these edges.
+ *
+ * @param cells : The cells (should be adjacent) defining the rectangular region whose edge distances are
+ * requested.
+ * @param point : The point that should determine the edge sort order.
+ *
+ * @return A list of (direction, distance) tuples, where direction is the edge and distance is the distance from the
+ * point to that edge. A direction value of (0,-1), for example, corresponds to the South edge of the
+ * rectangular region containing all of the given geocells.
+ * <p/>
+ * TODO(romannurik): Assert that lat,lon are actually inside the geocell.
+ */
+ public static List<Tuple<int[], Double>> distanceSortedEdges( List<String> cells, Point point ) {
+ List<BoundingBox> boxes = new ArrayList<BoundingBox>();
+ for ( String cell : cells ) {
+ boxes.add( computeBox( cell ) );
+ }
+ double maxNorth = Double.NEGATIVE_INFINITY;
+ double maxEast = Double.NEGATIVE_INFINITY;
+ double maxSouth = Double.POSITIVE_INFINITY;
+ double maxWest = Double.POSITIVE_INFINITY;
+ for ( BoundingBox box : boxes ) {
+ maxNorth = Math.max( maxNorth, box.getNorth() );
+ maxEast = Math.max( maxEast, box.getEast() );
+ maxSouth = Math.min( maxSouth, box.getSouth() );
+ maxWest = Math.min( maxWest, box.getWest() );
+ }
+ List<Tuple<int[], Double>> result = new ArrayList<Tuple<int[], Double>>();
+ result.add( new Tuple<int[], Double>( SOUTH, distance( new Point( maxSouth, point.getLon() ), point ) ) );
+ result.add( new Tuple<int[], Double>( NORTH, distance( new Point( maxNorth, point.getLon() ), point ) ) );
+ result.add( new Tuple<int[], Double>( WEST, distance( new Point( point.getLat(), maxWest ), point ) ) );
+ result.add( new Tuple<int[], Double>( EAST, distance( new Point( point.getLat(), maxEast ), point ) ) );
+ Collections.sort( result, new DoubleTupleComparator() );
+ return result;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/geo/comparator/DoubleTupleComparator.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/geo/comparator/DoubleTupleComparator.java b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/comparator/DoubleTupleComparator.java
new file mode 100644
index 0000000..07e4015
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/comparator/DoubleTupleComparator.java
@@ -0,0 +1,23 @@
+package org.apache.usergrid.persistence.geo.comparator;
+
+
+import java.util.Comparator;
+
+import org.apache.usergrid.persistence.geo.model.Tuple;
+
+
+public class DoubleTupleComparator implements Comparator<Tuple<int[], Double>> {
+
+ public int compare( Tuple<int[], Double> o1, Tuple<int[], Double> o2 ) {
+ if ( o1 == null && o2 == null ) {
+ return 0;
+ }
+ if ( o1 == null ) {
+ return -1;
+ }
+ if ( o2 == null ) {
+ return 1;
+ }
+ return o1.getSecond().compareTo( o2.getSecond() );
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/BoundingBox.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/BoundingBox.java b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/BoundingBox.java
new file mode 100644
index 0000000..99d6f7a
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/BoundingBox.java
@@ -0,0 +1,71 @@
+/*
+Copyright 2010 Alexandre Gellibert
+
+Licensed 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.
+*/
+
+package org.apache.usergrid.persistence.geo.model;
+
+
+/** @author Alexandre Gellibert */
+public class BoundingBox {
+
+ private Point northEast;
+ private Point southWest;
+
+
+ public BoundingBox( double north, double east, double south, double west ) {
+ double north_, south_;
+ if ( south > north ) {
+ south_ = north;
+ north_ = south;
+ }
+ else {
+ south_ = south;
+ north_ = north;
+ }
+
+ // Don't swap east and west to allow disambiguation of
+ // antimeridian crossing.
+
+ northEast = new Point( north_, east );
+ southWest = new Point( south_, west );
+ }
+
+
+ public double getNorth() {
+ return northEast.getLat();
+ }
+
+
+ public double getSouth() {
+ return southWest.getLat();
+ }
+
+
+ public double getWest() {
+ return southWest.getLon();
+ }
+
+
+ public double getEast() {
+ return northEast.getLon();
+ }
+
+
+ public Point getNorthEast() {
+ return northEast;
+ }
+
+
+ public Point getSouthWest() {
+ return southWest;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/CostFunction.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/CostFunction.java b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/CostFunction.java
new file mode 100644
index 0000000..6d9914b
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/CostFunction.java
@@ -0,0 +1,33 @@
+/*
+Copyright 2010 Alexandre Gellibert
+
+Licensed 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.
+*/
+
+package org.apache.usergrid.persistence.geo.model;
+
+
+/**
+ * Interface to create a cost function used in geocells algorithm. This function will determine the cost of an operation
+ * depending of number of cells and resolution. When the cost is going higher, the algorithm stops. The cost depends on
+ * application use of geocells.
+ *
+ * @author Alexandre Gellibert
+ */
+public interface CostFunction {
+
+ /**
+ * @param numCells number of cells found
+ * @param resolution resolution of those cells
+ *
+ * @return the cost of the operation
+ */
+ public double defaultCostFunction( int numCells, int resolution );
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/DefaultCostFunction.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/DefaultCostFunction.java b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/DefaultCostFunction.java
new file mode 100644
index 0000000..c2dd6a8
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/DefaultCostFunction.java
@@ -0,0 +1,34 @@
+/*
+Copyright 2010 Alexandre Gellibert
+
+Licensed 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.
+*/
+
+package org.apache.usergrid.persistence.geo.model;
+
+
+import org.apache.usergrid.persistence.geo.GeocellUtils;
+
+
+/**
+ * Default cost function used if no cost function is specified in Geocell.bestBboxSearchCells method.
+ *
+ * @author Alexandre Gellibert
+ */
+public class DefaultCostFunction implements CostFunction {
+
+ /*
+ * (non-Javadoc)
+ * @see com.beoui.utils.CostFunction#defaultCostFunction(int, int)
+ */
+ public double defaultCostFunction( int numCells, int resolution ) {
+ return numCells > Math.pow( GeocellUtils.GEOCELL_GRID_SIZE, 2 ) ? Double.MAX_VALUE : 0;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/Point.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/Point.java b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/Point.java
new file mode 100644
index 0000000..c8bf77c
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/Point.java
@@ -0,0 +1,58 @@
+/*
+Copyright 2010 Alexandre Gellibert
+
+Licensed 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.
+*/
+
+package org.apache.usergrid.persistence.geo.model;
+
+
+import org.apache.commons.lang.Validate;
+
+
+/** @author Alexandre Gellibert */
+public class Point {
+
+ private double lat;
+ private double lon;
+
+
+ public Point() {
+
+ }
+
+
+ public Point( double lat, double lon ) {
+ Validate.isTrue( !( lat > 90.0 || lat < -90.0 ), "Latitude must be in [-90, 90] but was ", lat );
+ Validate.isTrue( !( lon > 180.0 || lon < -180.0 ), "Longitude must be in [-180, 180] but was ", lon );
+ this.lat = lat;
+ this.lon = lon;
+ }
+
+
+ public double getLat() {
+ return lat;
+ }
+
+
+ public void setLat( double lat ) {
+ this.lat = lat;
+ }
+
+
+ public double getLon() {
+ return lon;
+ }
+
+
+ public void setLon( double lon ) {
+ this.lon = lon;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/Tuple.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/Tuple.java b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/Tuple.java
new file mode 100644
index 0000000..83c018f
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/geo/model/Tuple.java
@@ -0,0 +1,24 @@
+package org.apache.usergrid.persistence.geo.model;
+
+
+public class Tuple<A, B> {
+
+ private A first;
+ private B second;
+
+
+ public Tuple( A first, B second ) {
+ this.first = first;
+ this.second = second;
+ }
+
+
+ public A getFirst() {
+ return first;
+ }
+
+
+ public B getSecond() {
+ return second;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/AllNode.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/AllNode.java b/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/AllNode.java
new file mode 100644
index 0000000..08053f3
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/AllNode.java
@@ -0,0 +1,54 @@
+package org.apache.usergrid.persistence.query.ir;
+
+
+/**
+ * Used to represent a "select all". This will iterate over the entities by UUID
+ *
+ * @author tnine
+ */
+public class AllNode extends QueryNode {
+
+
+ private final QuerySlice slice;
+ private final boolean forceKeepFirst;
+
+
+ /**
+ * Note that the slice isn't used on select, but is used when creating cursors
+ *
+ * @param id. The unique numeric id for this node
+ * @param forceKeepFirst True if we don't allow the iterator to skip the first result, regardless of cursor state.
+ * Used for startUUID paging
+ */
+ public AllNode( int id, boolean forceKeepFirst ) {
+ this.slice = new QuerySlice( "uuid", id );
+ this.forceKeepFirst = forceKeepFirst;
+ }
+
+
+ /* (non-Javadoc)
+ * @see org.apache.usergrid.persistence.query.ir.QueryNode#visit(org.apache.usergrid.persistence.query.ir.NodeVisitor)
+ */
+ @Override
+ public void visit( NodeVisitor visitor ) throws Exception {
+ visitor.visit( this );
+ }
+
+
+ @Override
+ public String toString() {
+ return "AllNode";
+ }
+
+
+ /** @return the slice */
+ public QuerySlice getSlice() {
+ return slice;
+ }
+
+
+ /** @return the skipFirstMatch */
+ public boolean isForceKeepFirst() {
+ return forceKeepFirst;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/AndNode.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/AndNode.java b/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/AndNode.java
new file mode 100644
index 0000000..3e889b2
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/AndNode.java
@@ -0,0 +1,43 @@
+/*******************************************************************************
+ * Copyright 2012 Apigee Corporation
+ *
+ * Licensed 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.
+ ******************************************************************************/
+package org.apache.usergrid.persistence.query.ir;
+
+
+/**
+ * Node where the results need intersected. Used instead of a SliceNode when one of the children is an operation other
+ * than slices. I.E OR, NOT etc
+ *
+ * @author tnine
+ */
+public class AndNode extends BooleanNode {
+
+ /**
+ * @param left
+ * @param right
+ */
+ public AndNode( QueryNode left, QueryNode right ) {
+ super( left, right );
+ }
+
+
+ /* (non-Javadoc)
+ * @see org.apache.usergrid.persistence.query.ir.QueryNode#visit(org.apache.usergrid.persistence.query.ir.NodeVisitor)
+ */
+ @Override
+ public void visit( NodeVisitor visitor ) throws Exception {
+ visitor.visit( this );
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/BooleanNode.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/BooleanNode.java b/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/BooleanNode.java
new file mode 100644
index 0000000..e4eb813
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/BooleanNode.java
@@ -0,0 +1,48 @@
+/*******************************************************************************
+ * Copyright 2012 Apigee Corporation
+ *
+ * Licensed 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.
+ ******************************************************************************/
+package org.apache.usergrid.persistence.query.ir;
+
+
+/** @author tnine */
+public abstract class BooleanNode extends QueryNode {
+
+ protected QueryNode left;
+ protected QueryNode right;
+
+
+ public BooleanNode( QueryNode left, QueryNode right ) {
+ this.left = left;
+ this.right = right;
+ }
+
+
+ /** @return the left */
+ public QueryNode getLeft() {
+ return left;
+ }
+
+
+ /** @return the right */
+ public QueryNode getRight() {
+ return right;
+ }
+
+
+ @Override
+ public String toString() {
+ return "BooleanNode [left=" + left + ", right=" + right + "]";
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/EmailIdentifierNode.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/EmailIdentifierNode.java b/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/EmailIdentifierNode.java
new file mode 100644
index 0000000..b126eb9
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/EmailIdentifierNode.java
@@ -0,0 +1,31 @@
+package org.apache.usergrid.persistence.query.ir;
+
+
+import org.apache.usergrid.persistence.Identifier;
+
+
+/**
+ * Class to represent a UUID based Identifier query
+ *
+ * @author tnine
+ */
+public class EmailIdentifierNode extends QueryNode {
+
+ private final Identifier identifier;
+
+
+ public EmailIdentifierNode( Identifier identifier ) {
+ this.identifier = identifier;
+ }
+
+
+ @Override
+ public void visit( NodeVisitor visitor ) throws Exception {
+ visitor.visit( this );
+ }
+
+
+ public Identifier getIdentifier() {
+ return identifier;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/NameIdentifierNode.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/NameIdentifierNode.java b/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/NameIdentifierNode.java
new file mode 100644
index 0000000..9b6f2e0
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/NameIdentifierNode.java
@@ -0,0 +1,28 @@
+package org.apache.usergrid.persistence.query.ir;
+
+
+/**
+ * Class to represent a UUID based Identifier query
+ *
+ * @author tnine
+ */
+public class NameIdentifierNode extends QueryNode {
+
+ private final String name;
+
+
+ public NameIdentifierNode( String name ) {
+ this.name = name;
+ }
+
+
+ @Override
+ public void visit( NodeVisitor visitor ) throws Exception {
+ visitor.visit( this );
+ }
+
+
+ public String getName() {
+ return name;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/NodeVisitor.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/NodeVisitor.java b/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/NodeVisitor.java
new file mode 100644
index 0000000..ab8c2b3
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/NodeVisitor.java
@@ -0,0 +1,78 @@
+/*******************************************************************************
+ * Copyright 2012 Apigee Corporation
+ *
+ * Licensed 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.
+ ******************************************************************************/
+package org.apache.usergrid.persistence.query.ir;
+
+
+/** @author tnine */
+public interface NodeVisitor {
+
+ /**
+ *
+ * @param node
+ * @throws Exception
+ */
+ public void visit( AndNode node ) throws Exception;
+
+ /**
+ *
+ * @param node
+ * @throws Exception
+ */
+ public void visit( NotNode node ) throws Exception;
+
+ /**
+ *
+ * @param node
+ * @throws Exception
+ */
+ public void visit( OrNode node ) throws Exception;
+
+ /**
+ *
+ * @param node
+ * @throws Exception
+ */
+ public void visit( SliceNode node ) throws Exception;
+
+ /**
+ *
+ * @param node
+ * @throws Exception
+ */
+ public void visit( WithinNode node ) throws Exception;
+
+ /**
+ *
+ * @param node
+ * @throws Exception
+ */
+ public void visit( AllNode node ) throws Exception;
+
+ /** Visit the name identifier node */
+ public void visit( NameIdentifierNode nameIdentifierNode ) throws Exception;
+
+ /** Visit the uuid identifier node */
+ public void visit( UuidIdentifierNode uuidIdentifierNode );
+
+ /**
+ * @param orderByNode
+ * @throws Exception
+ */
+ public void visit( OrderByNode orderByNode ) throws Exception;
+
+ /** Visit the email id node */
+ public void visit( EmailIdentifierNode emailIdentifierNode ) throws Exception;
+}
http://git-wip-us.apache.org/repos/asf/incubator-usergrid/blob/2c2acbe4/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/NotNode.java
----------------------------------------------------------------------
diff --git a/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/NotNode.java b/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/NotNode.java
new file mode 100644
index 0000000..e8d037d
--- /dev/null
+++ b/stack/core/src/main/java/org/apache/usergrid/persistence/query/ir/NotNode.java
@@ -0,0 +1,62 @@
+/*******************************************************************************
+ * Copyright 2012 Apigee Corporation
+ *
+ * Licensed 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.
+ ******************************************************************************/
+package org.apache.usergrid.persistence.query.ir;
+
+
+/** @author tnine */
+public class NotNode extends QueryNode {
+
+ protected QueryNode subtractNode, keepNode;
+
+
+ /** @param keepNode may be null if there are parents to this */
+ public NotNode( QueryNode subtractNode, QueryNode keepNode ) {
+ this.subtractNode = subtractNode;
+ this.keepNode = keepNode;
+// throw new RuntimeException( "I'm a not node" );
+ }
+
+
+ /** @return the child */
+ public QueryNode getSubtractNode() {
+ return subtractNode;
+ }
+
+
+ /** @return the all */
+ public QueryNode getKeepNode() {
+ return keepNode;
+ }
+
+
+ /*
+ * (non-Javadoc)
+ *
+ * @see
+ * org.apache.usergrid.persistence.query.ir.QueryNode#visit(org.apache.usergrid.persistence
+ * .query.ir.NodeVisitor)
+ */
+ @Override
+ public void visit( NodeVisitor visitor ) throws Exception {
+ visitor.visit( this );
+ }
+
+
+ @Override
+ public String toString() {
+ return "NotNode [child=" + subtractNode + "]";
+ }
+}