Menu
▾
▴
[Geotools-commits] svn - r38414 - in branches/2.7.x/modules/library: main/src/main/java/org/geotools/data main/src/main/java/org/geotools/data/sort main/src/main/java/org/geotools/feature/collection main/src/test/java/org/geotools/data main/src/test/java/org/geotools/data/collection main/src/test/java/org/geotools/data/sort metadata/src/main/java/org/geotools/factory
|
From: <svn...@os...> - 2011-12-13 09:39:31
|
Author: aaime Date: 2011-12-13 01:39:22 -0800 (Tue, 13 Dec 2011) New Revision: 38414 Added: branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/ branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/CompositeComparator.java branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/FeatureBlockReader.java branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/FeatureReaderFeatureIterator.java branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/FidComparator.java branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/MergeSortDumper.java branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/MergeSortReader.java branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/PropertyComparator.java branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/SortedFeatureIterator.java branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/SortedFeatureReader.java branches/2.7.x/modules/library/main/src/main/java/org/geotools/feature/collection/SortedSimpleFeatureCollection.java branches/2.7.x/modules/library/main/src/test/java/org/geotools/data/collection/SortedFeatureCollectionTest.java branches/2.7.x/modules/library/main/src/test/java/org/geotools/data/sort/ branches/2.7.x/modules/library/main/src/test/java/org/geotools/data/sort/SortedReaderTest.java Modified: branches/2.7.x/modules/library/metadata/src/main/java/org/geotools/factory/Hints.java Log: [GEOT-3975] Create a sorted feature collection decorator that does not require in memory sorting Added: branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/CompositeComparator.java =================================================================== --- branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/CompositeComparator.java (rev 0) +++ branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/CompositeComparator.java 2011-12-13 09:39:22 UTC (rev 38414) @@ -0,0 +1,49 @@ +/* + * GeoTools - The Open Source Java GIS Toolkit + * http://geotools.org + * + * (C) 2004-2008, Open Source Geospatial Foundation (OSGeo) + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; + * version 2.1 of the License. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + */ +package org.geotools.data.sort; + +import java.util.Comparator; +import java.util.List; + +import org.opengis.feature.simple.SimpleFeature; + +/** + * A composite comparator that applies the provided comparators as a hierarchical list, the first + * comparator that returns a non zero value "wins" + * + * @author Andrea Aime - GeoSolutions + * + */ +class CompositeComparator implements Comparator<SimpleFeature> { + + List<Comparator<SimpleFeature>> comparators; + + public CompositeComparator(List<Comparator<SimpleFeature>> comparators) { + this.comparators = comparators; + } + + public int compare(SimpleFeature f1, SimpleFeature f2) { + for (Comparator<SimpleFeature> comp : comparators) { + int result = comp.compare(f1, f2); + if (result != 0) { + return result; + } + } + return 0; + } + +} Added: branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/FeatureBlockReader.java =================================================================== --- branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/FeatureBlockReader.java (rev 0) +++ branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/FeatureBlockReader.java 2011-12-13 09:39:22 UTC (rev 38414) @@ -0,0 +1,159 @@ +/* + * GeoTools - The Open Source Java GIS Toolkit + * http://geotools.org + * + * (C) 2004-2008, Open Source Geospatial Foundation (OSGeo) + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; + * version 2.1 of the License. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + */ +package org.geotools.data.sort; + +import java.io.ByteArrayInputStream; +import java.io.IOException; +import java.io.ObjectInputStream; +import java.io.RandomAccessFile; + +import org.geotools.feature.simple.SimpleFeatureBuilder; +import org.opengis.feature.simple.SimpleFeature; +import org.opengis.feature.simple.SimpleFeatureType; +import org.opengis.feature.type.AttributeDescriptor; + +import com.vividsolutions.jts.geom.Geometry; +import com.vividsolutions.jts.io.ParseException; +import com.vividsolutions.jts.io.WKBReader; + +/** + * Reads the features stored in the specified block of a {@link RandomAccessFile} + * + * @author Andrea Aime - GeoSolutions + */ +class FeatureBlockReader { + + RandomAccessFile raf; + + SimpleFeatureType schema; + + SimpleFeatureBuilder builder; + + SimpleFeature curr; + + long offset; + + int count; + + public FeatureBlockReader(RandomAccessFile raf, long start, int count, SimpleFeatureType schema) { + this.raf = raf; + this.offset = start; + this.count = count; + this.schema = schema; + this.builder = new SimpleFeatureBuilder(schema); + } + + public SimpleFeature feature() throws IOException { + if (curr == null && count > 0) { + curr = readNextFeature(); + } + return curr; + } + + public SimpleFeature next() throws IOException { + curr = readNextFeature(); + return curr; + } + + private SimpleFeature readNextFeature() throws IOException { + if (count <= 0) { + return null; + } + + // move to the next feature offset + raf.seek(offset); + + // read the fid, check for file end + String fid = raf.readUTF(); + // read the other attributes, build the feature + for (AttributeDescriptor ad : schema.getAttributeDescriptors()) { + Object att = readAttribute(ad); + builder.add(att); + } + // update the offset for the next feature + offset = raf.getFilePointer(); + count--; + + // return the feature + return builder.buildFeature(fid); + } + + /** + * Reads the attributes. + * + * @param ad + * @return + * @throws IOException + */ + Object readAttribute(AttributeDescriptor ad) throws IOException { + // See the comments in {@link MergeSortDumper#writeAttribute(RandomAccessFile, + // AttributeDescriptor, Object)} to get an insight on why the method is built like this + boolean isNull = raf.readBoolean(); + if (isNull) { + return null; + } else { + Class<?> binding = ad.getType().getBinding(); + if (binding == Boolean.class) { + return raf.readBoolean(); + } else if (binding == Byte.class || binding == byte.class) { + return raf.readByte(); + } else if (binding == Short.class || binding == short.class) { + return raf.readShort(); + } else if (binding == Integer.class || binding == int.class) { + return raf.readInt(); + } else if (binding == Long.class || binding == long.class) { + return raf.readLong(); + } else if (binding == Float.class || binding == float.class) { + return raf.readFloat(); + } else if (binding == Double.class || binding == double.class) { + return raf.readDouble(); + } else if (binding == String.class) { + return raf.readUTF(); + } else if (binding == java.sql.Date.class) { + return new java.sql.Date(raf.readLong()); + } else if (binding == java.sql.Time.class) { + return new java.sql.Time(raf.readLong()); + } else if (binding == java.sql.Timestamp.class) { + return new java.sql.Timestamp(raf.readLong()); + } else if (binding == java.util.Date.class) { + return new java.util.Date(raf.readLong()); + } else if (Geometry.class.isAssignableFrom(binding)) { + WKBReader reader = new WKBReader(); + int length = raf.readInt(); + byte[] buffer = new byte[length]; + raf.read(buffer); + try { + return reader.read(buffer); + } catch (ParseException e) { + throw (IOException ) new IOException("Failed to parse the geometry WKB").initCause(e); + } + } else { + int length = raf.readInt(); + byte[] buffer = new byte[length]; + raf.read(buffer); + ByteArrayInputStream bis = new ByteArrayInputStream(buffer); + ObjectInputStream ois = new ObjectInputStream(bis); + try { + return ois.readObject(); + } catch (ClassNotFoundException e) { + throw (IOException) new IOException("Could not read back object").initCause(e); + } + } + } + } + +} Added: branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/FeatureReaderFeatureIterator.java =================================================================== --- branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/FeatureReaderFeatureIterator.java (rev 0) +++ branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/FeatureReaderFeatureIterator.java 2011-12-13 09:39:22 UTC (rev 38414) @@ -0,0 +1,62 @@ +/* + * GeoTools - The Open Source Java GIS Toolkit + * http://geotools.org + * + * (C) 2004-2008, Open Source Geospatial Foundation (OSGeo) + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; + * version 2.1 of the License. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + */ +package org.geotools.data.sort; + +import java.io.IOException; +import java.util.NoSuchElementException; + +import org.geotools.data.simple.SimpleFeatureIterator; +import org.geotools.data.simple.SimpleFeatureReader; +import org.opengis.feature.simple.SimpleFeature; + +/** + * A simple feature iterator wrapping a feature reader + */ +class FeatureReaderFeatureIterator implements SimpleFeatureIterator { + SimpleFeatureReader reader; + + public FeatureReaderFeatureIterator(SimpleFeatureReader reader) { + this.reader = reader; + } + + public boolean hasNext() { + try { + return reader.hasNext(); + } catch (IOException e) { + throw new RuntimeException("Reader failed", e); + } + } + + public SimpleFeature next() { + if (!hasNext()) { + throw new NoSuchElementException(); + } + try { + return reader.next(); + } catch (Exception e) { + throw new RuntimeException("Reader failed", e); + } + } + + public void close() { + try { + reader.close(); + } catch (IOException e) { + // we tried, n problem + } + } +}; Added: branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/FidComparator.java =================================================================== --- branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/FidComparator.java (rev 0) +++ branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/FidComparator.java 2011-12-13 09:39:22 UTC (rev 38414) @@ -0,0 +1,67 @@ +/* + * GeoTools - The Open Source Java GIS Toolkit + * http://geotools.org + * + * (C) 2004-2008, Open Source Geospatial Foundation (OSGeo) + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; + * version 2.1 of the License. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + */ +package org.geotools.data.sort; + +import java.util.Comparator; + +import org.opengis.feature.simple.SimpleFeature; + +/** + * Compares two feature based on their feature id + * + * @author Andrea Aime - GeoSolutions + */ +class FidComparator implements Comparator<SimpleFeature> { + + boolean ascending; + + /** + * Builds a new comparator + * + * @param inverse If true the comparator will force an ascending order (descending otherwise) + */ + public FidComparator(boolean ascending) { + this.ascending = ascending; + } + + public int compare(SimpleFeature f1, SimpleFeature f2) { + int result = compareAscending(f1, f2); + if (ascending) { + return result; + } else { + return result * -1; + } + } + + private int compareAscending(SimpleFeature f1, SimpleFeature f2) { + String id1 = f1.getID(); + String id2 = f2.getID(); + + if (id1 == null) { + if (id2 == null) { + return 0; + } else { + return -1; + } + } else if (id2 == null) { + return 1; + } else { + return id1.compareTo(id2); + } + } + +} Added: branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/MergeSortDumper.java =================================================================== --- branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/MergeSortDumper.java (rev 0) +++ branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/MergeSortDumper.java 2011-12-13 09:39:22 UTC (rev 38414) @@ -0,0 +1,273 @@ +/* + * GeoTools - The Open Source Java GIS Toolkit + * http://geotools.org + * + * (C) 2004-2008, Open Source Geospatial Foundation (OSGeo) + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; + * version 2.1 of the License. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + */ +package org.geotools.data.sort; + +import java.io.ByteArrayOutputStream; +import java.io.File; +import java.io.IOException; +import java.io.ObjectOutputStream; +import java.io.RandomAccessFile; +import java.io.Serializable; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.Date; +import java.util.List; + +import org.geotools.data.Query; +import org.geotools.data.collection.ListFeatureCollection; +import org.geotools.data.simple.DelegateSimpleFeatureReader; +import org.geotools.data.simple.SimpleFeatureIterator; +import org.geotools.data.simple.SimpleFeatureReader; +import org.geotools.factory.Hints; +import org.opengis.feature.simple.SimpleFeature; +import org.opengis.feature.simple.SimpleFeatureType; +import org.opengis.feature.type.AttributeDescriptor; +import org.opengis.filter.sort.SortBy; +import org.opengis.filter.sort.SortOrder; + +import com.vividsolutions.jts.geom.Geometry; +import com.vividsolutions.jts.io.WKBWriter; + +class MergeSortDumper { + + static final boolean canSort(SimpleFeatureType schema, SortBy[] sortBy) { + if (sortBy == SortBy.UNSORTED) { + return true; + } + + // check all attributes are serializable + for (AttributeDescriptor ad : schema.getAttributeDescriptors()) { + Class<?> binding = ad.getType().getBinding(); + if (!Serializable.class.isAssignableFrom(binding)) { + return false; + } + } + + // check all sorting attributes are comparable + for (SortBy sb : sortBy) { + if (sb != SortBy.NATURAL_ORDER && sb != SortBy.REVERSE_ORDER) { + AttributeDescriptor ad = schema.getDescriptor(sb.getPropertyName() + .getPropertyName()); + Class<?> binding = ad.getType().getBinding(); + if (ad == null || !Comparable.class.isAssignableFrom(binding) + || Geometry.class.isAssignableFrom(binding)) { + return false; + } + } + } + + return true; + } + + static SimpleFeatureReader getDelegateReader(SimpleFeatureReader reader, Query query) + throws IOException { + Hints hints = query.getHints(); + int maxFeatures = 1000; + if (hints != null && hints.get(Hints.MAX_MEMORY_SORT) != null) { + maxFeatures = (Integer) hints.get(Hints.MAX_MEMORY_SORT); + } else if (Hints.getSystemDefault(Hints.MAX_MEMORY_SORT) != null) { + maxFeatures = (Integer) Hints.getSystemDefault(Hints.MAX_MEMORY_SORT); + } + + return getDelegateReader(reader, query.getSortBy(), maxFeatures); + } + + static SimpleFeatureReader getDelegateReader(SimpleFeatureReader reader, SortBy[] sortBy, + int maxFeatures) throws IOException { + Comparator<SimpleFeature> comparator = getComparator(sortBy); + + // easy case, no sorting needed + if (comparator == null) { + return reader; + } + + // double check + SimpleFeatureType schema = reader.getFeatureType(); + if (!canSort(schema, sortBy)) { + throw new IllegalArgumentException( + "The specified reader cannot be sorted, either the " + + "sorting properties are not comparable or the attributes are not serializable"); + } + + int count = 0; + File file = null; + RandomAccessFile raf = null; + List<SimpleFeature> features = new ArrayList<SimpleFeature>(); + List<FeatureBlockReader> readers = new ArrayList<FeatureBlockReader>(); + boolean cleanFile = true; + try { + // read and store into files as necessary + while (reader.hasNext()) { + SimpleFeature f = reader.next(); + features.add(f); + count++; + + if (count > maxFeatures) { + Collections.sort(features, comparator); + if (raf == null) { + file = File.createTempFile("sorted", ".features"); + file.delete(); + raf = new RandomAccessFile(file, "rw"); + } + FeatureBlockReader fbr = storeToFile(raf, features, schema); + readers.add(fbr); + count = 0; + features.clear(); + } + } + + // return the appropriate reader + if (raf == null) { + // simple case, we managed to keep everything in memory, sort and return a + // reader based on the collection contents + Collections.sort(features, comparator); + + SimpleFeatureIterator fi = new ListFeatureCollection(schema, features).features(); + return new DelegateSimpleFeatureReader(schema, fi); + } else { + // go merge-sort + cleanFile = false; + return new MergeSortReader(schema, raf, file, readers, comparator); + } + + } finally { + if (cleanFile && raf != null) { + raf.close(); + file.delete(); + } + + reader.close(); + } + } + + /** + * Writes the feature attributes to a binary file + * + * @param features + * @return + * @throws IOException + */ + static FeatureBlockReader storeToFile(RandomAccessFile raf, List<SimpleFeature> features, + SimpleFeatureType schema) throws IOException { + long start = raf.getFilePointer(); + + // write each attribute in the random access file + List<AttributeDescriptor> attributes = schema.getAttributeDescriptors(); + for (SimpleFeature sf : features) { + // write feature id + raf.writeUTF(sf.getID()); + // write the attributes + for (AttributeDescriptor ad : attributes) { + Object value = sf.getAttribute(ad.getLocalName()); + writeAttribute(raf, ad, value); + } + } + + return new FeatureBlockReader(raf, start, features.size(), schema); + } + + static void writeAttribute(RandomAccessFile raf, AttributeDescriptor ad, Object value) + throws IOException { + if (value == null) { + // null marker + raf.writeBoolean(true); + } else { + // not null, write the contents. This one requires some explanation. We are not + // writing any type metadata in the stream for the types we can optimize (primitives, + // numbers, + // strings and the like). This means we have to be 100% sure the class we're writing is + // actually the one we can optimize for, and not some subclass. Thus, we are authorized + // to use identity comparison instead of isAssignableFrom or equality, when we read back + // it must be as if we did not serialize stuff at all + raf.writeBoolean(false); + Class<?> binding = ad.getType().getBinding(); + if (binding == Boolean.class) { + raf.writeBoolean((Boolean) value); + } else if (binding == Byte.class || binding == byte.class) { + raf.writeByte((Byte) value); + } else if (binding == Short.class || binding == short.class) { + raf.writeShort((Short) value); + } else if (binding == Integer.class || binding == int.class) { + raf.writeInt((Integer) value); + } else if (binding == Long.class || binding == long.class) { + raf.writeLong((Long) value); + } else if (binding == Float.class || binding == float.class) { + raf.writeFloat((Float) value); + } else if (binding == Double.class || binding == double.class) { + raf.writeDouble((Double) value); + } else if (binding == String.class) { + raf.writeUTF((String) value); + } else if (binding == java.sql.Date.class || binding == java.sql.Time.class + || binding == java.sql.Timestamp.class || binding == java.util.Date.class) { + raf.writeLong(((Date) value).getTime()); + } else if (Geometry.class.isAssignableFrom(binding)) { + WKBWriter writer = new WKBWriter(); + byte[] buffer = writer.write((Geometry) value); + int length = buffer.length; + raf.writeInt(length); + raf.write(buffer); + } else { + // can't optimize, in this case we use an ObjectOutputStream to write out + // full metadata + ByteArrayOutputStream bos = new ByteArrayOutputStream(); + ObjectOutputStream oos = new ObjectOutputStream(bos); + oos.writeObject(value); + oos.flush(); + byte[] bytes = bos.toByteArray(); + raf.writeInt(bytes.length); + raf.write(bytes); + } + } + } + + /** + * Builds a comparator out of the sortBy list + * + * @param sortBy + * @return + */ + static Comparator<SimpleFeature> getComparator(SortBy[] sortBy) { + // handle the easy cases, no sorting or natural sorting + if (sortBy == SortBy.UNSORTED || sortBy == null) { + return null; + } + + // build a list of comparators + List<Comparator<SimpleFeature>> comparators = new ArrayList<Comparator<SimpleFeature>>(); + for (SortBy sb : sortBy) { + if (sb == SortBy.NATURAL_ORDER) { + comparators.add(new FidComparator(true)); + } else if (sb == SortBy.REVERSE_ORDER) { + comparators.add(new FidComparator(false)); + } else { + String name = sb.getPropertyName().getPropertyName(); + boolean ascending = sb.getSortOrder() == SortOrder.ASCENDING; + comparators.add(new PropertyComparator(name, ascending)); + } + } + + // return the final comparator + if (comparators.size() == 1) { + return comparators.get(0); + } else { + return new CompositeComparator(comparators); + } + + } + +} Added: branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/MergeSortReader.java =================================================================== --- branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/MergeSortReader.java (rev 0) +++ branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/MergeSortReader.java 2011-12-13 09:39:22 UTC (rev 38414) @@ -0,0 +1,101 @@ +/* + * GeoTools - The Open Source Java GIS Toolkit + * http://geotools.org + * + * (C) 2004-2008, Open Source Geospatial Foundation (OSGeo) + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; + * version 2.1 of the License. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + */ +package org.geotools.data.sort; + +import java.io.File; +import java.io.IOException; +import java.io.RandomAccessFile; +import java.util.Comparator; +import java.util.List; +import java.util.NoSuchElementException; + +import org.geotools.data.simple.SimpleFeatureReader; +import org.opengis.feature.simple.SimpleFeature; +import org.opengis.feature.simple.SimpleFeatureType; + +/** + * Reads from a list of {@link FeatureBlockReader} backed by a {@link RandomAccessFile} and performs + * the classic merge-sort algorithm + * + * @author Andrea Aime - GeoSolutions + * + */ +class MergeSortReader implements SimpleFeatureReader { + + List<FeatureBlockReader> readers; + + RandomAccessFile raf; + + File file; + + SimpleFeatureType schema; + + Comparator<SimpleFeature> comparator; + + public MergeSortReader(SimpleFeatureType schema, RandomAccessFile raf, File file, + List<FeatureBlockReader> readers, Comparator<SimpleFeature> comparator) { + this.schema = schema; + this.comparator = comparator; + this.readers = readers; + this.raf = raf; + this.file = file; + } + + public SimpleFeatureType getFeatureType() { + return schema; + } + + public SimpleFeature next() throws IOException, IllegalArgumentException, + NoSuchElementException { + if (readers.size() == 0) { + throw new NoSuchElementException(); + } + + // find the smallest feature + int selected = 0; + for (int i = 1; i < readers.size(); i++) { + SimpleFeature sf = readers.get(selected).feature(); + SimpleFeature cf = readers.get(i).feature(); + if (comparator.compare(sf, cf) > 0) { + selected = i; + } + } + + // move on the reader of the selected feature + FeatureBlockReader reader = readers.get(selected); + SimpleFeature sf = reader.feature(); + if (reader.next() == null) { + readers.remove(selected); + } + + // return the selected feature + return sf; + } + + public boolean hasNext() throws IOException { + return readers.size() > 0; + } + + public void close() throws IOException { + try { + raf.close(); + } finally { + file.delete(); + } + } + +} Added: branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/PropertyComparator.java =================================================================== --- branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/PropertyComparator.java (rev 0) +++ branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/PropertyComparator.java 2011-12-13 09:39:22 UTC (rev 38414) @@ -0,0 +1,71 @@ +/* + * GeoTools - The Open Source Java GIS Toolkit + * http://geotools.org + * + * (C) 2004-2008, Open Source Geospatial Foundation (OSGeo) + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; + * version 2.1 of the License. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + */ +package org.geotools.data.sort; + +import java.util.Comparator; + +import org.opengis.feature.simple.SimpleFeature; + +/** + * Compares two feature based on an attribute value + * + * @author Andrea Aime - GeoSolutions + */ +class PropertyComparator implements Comparator<SimpleFeature> { + + String propertyName; + + boolean ascending; + + /** + * Builds a new comparator + * + * @param propertyName The property name to be used + * @param inverse If true the comparator will force an ascending order (descending otherwise) + */ + public PropertyComparator(String propertyName, boolean ascending) { + this.propertyName = propertyName; + this.ascending = ascending; + } + + public int compare(SimpleFeature f1, SimpleFeature f2) { + int result = compareAscending(f1, f2); + if (ascending) { + return result; + } else { + return result * -1; + } + } + + private int compareAscending(SimpleFeature f1, SimpleFeature f2) { + Comparable o1 = (Comparable) f1.getAttribute(propertyName); + Comparable o2 = (Comparable) f2.getAttribute(propertyName); + + if (o1 == null) { + if (o2 == null) { + return 0; + } else { + return -1; + } + } else if (o2 == null) { + return 1; + } else { + return o1.compareTo(o2); + } + } + +} Added: branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/SortedFeatureIterator.java =================================================================== --- branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/SortedFeatureIterator.java (rev 0) +++ branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/SortedFeatureIterator.java 2011-12-13 09:39:22 UTC (rev 38414) @@ -0,0 +1,70 @@ +/* + * GeoTools - The Open Source Java GIS Toolkit + * http://geotools.org + * + * (C) 2004-2008, Open Source Geospatial Foundation (OSGeo) + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; + * version 2.1 of the License. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + */ +package org.geotools.data.sort; + +import java.io.IOException; +import java.io.Serializable; +import java.util.NoSuchElementException; + +import org.geotools.data.simple.DelegateSimpleFeatureReader; +import org.geotools.data.simple.SimpleFeatureIterator; +import org.geotools.data.simple.SimpleFeatureReader; +import org.opengis.feature.simple.SimpleFeature; +import org.opengis.feature.simple.SimpleFeatureType; +import org.opengis.filter.sort.SortBy; + +/** + * Sorts features based on the specified sorting order + * + * @source $URL$ + */ +public class SortedFeatureIterator implements SimpleFeatureIterator { + + FeatureReaderFeatureIterator delegate; + + /** + * Checks if the schema and the sortBy are suitable for merge/sort. All attributes need to be + * {@link Serializable}, all sorting attributes need to be {@link Comparable} + * + * @param schema + * @param sortBy + * @return + */ + public static final boolean canSort(SimpleFeatureType schema, SortBy[] sortBy) { + return MergeSortDumper.canSort(schema, sortBy); + } + + public SortedFeatureIterator(SimpleFeatureIterator iterator, SimpleFeatureType schema, + SortBy[] sortBy, int maxFeatures) throws IOException { + DelegateSimpleFeatureReader reader = new DelegateSimpleFeatureReader(schema, iterator); + SimpleFeatureReader sorted = new SortedFeatureReader(reader, sortBy, maxFeatures); + this.delegate = new FeatureReaderFeatureIterator(sorted); + } + + public boolean hasNext() { + return delegate.hasNext(); + } + + public SimpleFeature next() throws NoSuchElementException { + return delegate.next(); + } + + public void close() { + delegate.close(); + + } +} Added: branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/SortedFeatureReader.java =================================================================== --- branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/SortedFeatureReader.java (rev 0) +++ branches/2.7.x/modules/library/main/src/main/java/org/geotools/data/sort/SortedFeatureReader.java 2011-12-13 09:39:22 UTC (rev 38414) @@ -0,0 +1,94 @@ +/* + * GeoTools - The Open Source Java GIS Toolkit + * http://geotools.org + * + * (C) 2004-2008, Open Source Geospatial Foundation (OSGeo) + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; + * version 2.1 of the License. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + */ +package org.geotools.data.sort; + +import java.io.IOException; +import java.io.Serializable; +import java.util.NoSuchElementException; + +import org.geotools.data.Query; +import org.geotools.data.simple.SimpleFeatureReader; +import org.geotools.factory.Hints; +import org.opengis.feature.simple.SimpleFeature; +import org.opengis.feature.simple.SimpleFeatureType; +import org.opengis.filter.sort.SortBy; + +/** + * FeatureReader used to sort contents. + * <p> + * The implementation makes use of {@link MergeSortDumper). + * + * @source $URL$ + */ +public class SortedFeatureReader implements SimpleFeatureReader { + + SimpleFeatureReader delegate; + + /** + * Checks if the schema and the sortBy are suitable for merge/sort. All attributes need to be + * {@link Serializable}, all sorting attributes need to be {@link Comparable} + * + * @param schema + * @param sortBy + * @return + */ + public static final boolean canSort(SimpleFeatureType schema, SortBy[] sortBy) { + return MergeSortDumper.canSort(schema, sortBy); + } + + /** + * Builds a new sorting feature reader + * + * @param reader The reader to be sorted + * @param query The query holding the SortBy directives, and the eventual max features in memory + * hint {@link Hints#MAX_MEMORY_SORT} + */ + public SortedFeatureReader(SimpleFeatureReader reader, Query query) throws IOException { + this.delegate = MergeSortDumper.getDelegateReader(reader, query); + } + + /** + * Builds a new sorting feature reader + * + * @param reader The reader to be sorted + * @param sortBy The sorting directives + * @param maxFeatures The maximum number of features to keep in memory + * @throws IOException + */ + public SortedFeatureReader(SimpleFeatureReader reader, SortBy[] sortBy, int maxFeatures) + throws IOException { + this.delegate = MergeSortDumper.getDelegateReader(reader, sortBy, maxFeatures); + } + + public SimpleFeatureType getFeatureType() { + return delegate.getFeatureType(); + } + + public SimpleFeature next() throws IOException, IllegalArgumentException, + NoSuchElementException { + return delegate.next(); + } + + public boolean hasNext() throws IOException { + return delegate.hasNext(); + } + + public void close() throws IOException { + delegate.close(); + } + +} Added: branches/2.7.x/modules/library/main/src/main/java/org/geotools/feature/collection/SortedSimpleFeatureCollection.java =================================================================== --- branches/2.7.x/modules/library/main/src/main/java/org/geotools/feature/collection/SortedSimpleFeatureCollection.java (rev 0) +++ branches/2.7.x/modules/library/main/src/main/java/org/geotools/feature/collection/SortedSimpleFeatureCollection.java 2011-12-13 09:39:22 UTC (rev 38414) @@ -0,0 +1,61 @@ +package org.geotools.feature.collection; + +import java.io.IOException; +import java.util.Iterator; + +import org.geotools.data.simple.SimpleFeatureCollection; +import org.geotools.data.simple.SimpleFeatureIterator; +import org.geotools.data.sort.SortedFeatureIterator; +import org.geotools.data.store.FeatureIteratorIterator; +import org.geotools.factory.Hints; +import org.geotools.feature.FeatureIterator; +import org.opengis.feature.simple.SimpleFeature; +import org.opengis.filter.sort.SortBy; + +/** + * A wrapper that will sort a feature collection using a size sensitive algorithm, in main memory + * for small collections, using secondary memory otherwise. The threshold is defined by the + * {@link Hints#MAX_MEMORY_SORT} feature count + * + * @author Andrea Aime - GeoSolutions + * + */ +public class SortedSimpleFeatureCollection extends DecoratingSimpleFeatureCollection { + + private SortBy[] sort; + + public SortedSimpleFeatureCollection(SimpleFeatureCollection delegate, SortBy[] sort) { + super(delegate); + this.sort = sort; + } + + @Override + public SimpleFeatureIterator features() { + try { + SimpleFeatureIterator features = ((SimpleFeatureCollection) delegate).features(); + // sort if necessary + if (sort != null) { + features = new SortedFeatureIterator(features, getSchema(), sort, -1); + } + return features; + } catch (IOException e) { + throw new RuntimeException(e); + } + } + + @Override + public Iterator iterator() { + return new FeatureIteratorIterator<SimpleFeature>(features()); + } + + @Override + public void close(FeatureIterator<SimpleFeature> close) { + close.close(); + } + + @Override + public void close(Iterator<SimpleFeature> close) { + FeatureIteratorIterator<SimpleFeature> fii = (FeatureIteratorIterator<SimpleFeature>) close; + delegate.close(fii.getDelegate()); + } +} Added: branches/2.7.x/modules/library/main/src/test/java/org/geotools/data/collection/SortedFeatureCollectionTest.java =================================================================== --- branches/2.7.x/modules/library/main/src/test/java/org/geotools/data/collection/SortedFeatureCollectionTest.java (rev 0) +++ branches/2.7.x/modules/library/main/src/test/java/org/geotools/data/collection/SortedFeatureCollectionTest.java 2011-12-13 09:39:22 UTC (rev 38414) @@ -0,0 +1,68 @@ +/* + * GeoTools - The Open Source Java GIS Toolkit + * http://geotools.org + * + * (C) 2002-2008, Open Source Geospatial Foundation (OSGeo) + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; + * version 2.1 of the License. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + */ +package org.geotools.data.collection; + +import java.util.Comparator; + +import org.geotools.data.DataUtilities; +import org.geotools.data.simple.SimpleFeatureIterator; +import org.geotools.data.store.FeatureCollectionWrapperTestSupport; +import org.geotools.factory.CommonFactoryFinder; +import org.geotools.feature.collection.SortedSimpleFeatureCollection; +import org.opengis.feature.simple.SimpleFeature; +import org.opengis.filter.FilterFactory2; +import org.opengis.filter.sort.SortBy; +import org.opengis.filter.sort.SortOrder; + +public class SortedFeatureCollectionTest extends FeatureCollectionWrapperTestSupport { + + FilterFactory2 ff = CommonFactoryFinder.getFilterFactory2(null); + + public void testNaturalSort() throws Exception { + SortedSimpleFeatureCollection sorted = new SortedSimpleFeatureCollection(delegate, + new SortBy[] { SortBy.NATURAL_ORDER }); + checkSorted(sorted, DataUtilities.sortComparator(SortBy.NATURAL_ORDER)); + } + + public void testReverseSort() throws Exception { + SortedSimpleFeatureCollection sorted = new SortedSimpleFeatureCollection(delegate, + new SortBy[] { SortBy.REVERSE_ORDER }); + checkSorted(sorted, DataUtilities.sortComparator(SortBy.REVERSE_ORDER)); + } + + public void testSortAttribute() throws Exception { + SortBy sort = ff.sort("someAtt", SortOrder.ASCENDING); + SortedSimpleFeatureCollection sorted = new SortedSimpleFeatureCollection(delegate, + new SortBy[] { sort }); + checkSorted(sorted, DataUtilities.sortComparator(sort)); + } + + private void checkSorted(SortedSimpleFeatureCollection sorted, + Comparator<SimpleFeature> comparator) { + SimpleFeatureIterator fi = sorted.features(); + SimpleFeature prev = null; + while (fi.hasNext()) { + SimpleFeature curr = fi.next(); + if (prev != null) { + assertTrue("Failed on " + prev + " / " + curr, comparator.compare(prev, curr) <= 0); + } + prev = curr; + } + fi.close(); + } + +} Added: branches/2.7.x/modules/library/main/src/test/java/org/geotools/data/sort/SortedReaderTest.java =================================================================== --- branches/2.7.x/modules/library/main/src/test/java/org/geotools/data/sort/SortedReaderTest.java (rev 0) +++ branches/2.7.x/modules/library/main/src/test/java/org/geotools/data/sort/SortedReaderTest.java 2011-12-13 09:39:22 UTC (rev 38414) @@ -0,0 +1,276 @@ +package org.geotools.data.sort; + +import static org.junit.Assert.*; + +import java.io.IOException; +import java.util.Date; +import java.util.NoSuchElementException; + +import org.geotools.data.simple.DelegateSimpleFeatureReader; +import org.geotools.data.simple.SimpleFeatureCollection; +import org.geotools.data.simple.SimpleFeatureIterator; +import org.geotools.data.simple.SimpleFeatureReader; +import org.geotools.factory.CommonFactoryFinder; +import org.geotools.feature.DefaultFeatureCollection; +import org.geotools.feature.simple.SimpleFeatureBuilder; +import org.geotools.feature.simple.SimpleFeatureTypeBuilder; +import org.geotools.referencing.crs.DefaultGeographicCRS; +import org.junit.After; +import org.junit.Before; +import org.junit.Test; +import org.opengis.feature.simple.SimpleFeature; +import org.opengis.feature.simple.SimpleFeatureType; +import org.opengis.filter.FilterFactory; +import org.opengis.filter.sort.SortBy; +import org.opengis.filter.sort.SortOrder; + +import com.vividsolutions.jts.geom.Coordinate; +import com.vividsolutions.jts.geom.GeometryFactory; +import com.vividsolutions.jts.geom.LineString; +import com.vividsolutions.jts.geom.Point; + +/** + * + * + * @source $URL$ + */ +public class SortedReaderTest { + + SimpleFeatureReader fr; + + FilterFactory ff; + + SortBy[] peopleAsc; + + SortBy[] peopleDesc; + + SortBy[] fidAsc; + + SimpleFeatureType schema; + + SimpleFeatureCollection fc; + + private SortBy[] dateAsc; + + @Before + public void setup() throws IOException { + SimpleFeatureTypeBuilder typeBuilder = new SimpleFeatureTypeBuilder(); + + typeBuilder.setName("test"); + typeBuilder.setNamespaceURI("test"); + typeBuilder.setCRS(DefaultGeographicCRS.WGS84); + typeBuilder.add("defaultGeom", Point.class, DefaultGeographicCRS.WGS84); + typeBuilder.add("PERSONS", Integer.class); + typeBuilder.add("byte", Byte.class); + typeBuilder.add("short", Short.class); + typeBuilder.add("long", Long.class); + typeBuilder.add("float", Float.class); + typeBuilder.add("double", Double.class); + typeBuilder.add("date", Date.class); + typeBuilder.add("sql_date", java.sql.Date.class); + typeBuilder.add("sql_time", java.sql.Time.class); + typeBuilder.add("sql_timestamp", java.sql.Timestamp.class); + typeBuilder.add("otherGeom", LineString.class); + typeBuilder.setDefaultGeometry("defaultGeom"); + + schema = (SimpleFeatureType) typeBuilder.buildFeatureType(); + + SimpleFeatureBuilder builder = new SimpleFeatureBuilder(schema); + + GeometryFactory gf = new GeometryFactory(); + fc = new DefaultFeatureCollection("test", schema); + + double x = -140; + double y = 45; + final int features = 500; + for (int i = 0; i < features; i++) { + Point point = gf.createPoint(new Coordinate(x + i, y + i)); + point.setUserData(DefaultGeographicCRS.WGS84); + + builder.add(point); + builder.add(new Integer(i)); + builder.add(new Byte((byte) i)); + builder.add(new Short((short) i)); + builder.add(new Long(i)); + builder.add(new Float(i)); + builder.add(new Double(i)); + builder.add(new Date()); + builder.add(new java.sql.Date(System.currentTimeMillis())); + builder.add(new java.sql.Time(System.currentTimeMillis())); + builder.add(new java.sql.Timestamp(System.currentTimeMillis())); + + LineString line = gf.createLineString(new Coordinate[] { new Coordinate(x + i, y + i), + new Coordinate(x + i + 1, y + i + 1) }); + line.setUserData(DefaultGeographicCRS.WGS84); + builder.add(line); + + fc.add(builder.buildFeature(i + "")); + } + + // add a feature with a null geometry + builder.add(null); + builder.add(new Integer(-1)); + builder.add(null); + fc.add(builder.buildFeature((features + 1) + "")); + + fr = new DelegateSimpleFeatureReader(schema, fc.features()); + + ff = CommonFactoryFinder.getFilterFactory(null); + peopleAsc = new SortBy[] { ff.sort("PERSONS", SortOrder.ASCENDING) }; + peopleDesc = new SortBy[] { ff.sort("PERSONS", SortOrder.DESCENDING) }; + dateAsc = new SortBy[] { ff.sort("date", SortOrder.ASCENDING) }; + fidAsc = new SortBy[] { SortBy.NATURAL_ORDER }; + } + + @After + public void tearDown() throws IOException { + fr.close(); + } + + @Test + public void testCanSort() { + assertTrue(SortedFeatureReader.canSort(schema, peopleAsc)); + assertTrue(SortedFeatureReader.canSort(schema, peopleDesc)); + assertTrue(SortedFeatureReader.canSort(schema, fidAsc)); + } + + @Test + public void testMemorySort() throws IOException { + // make it so that we are not going to hit the disk + SimpleFeatureReader sr = null; + try { + sr = new SortedFeatureReader(fr, peopleAsc, 1000); + assertSortedOnPeopleAsc(sr); + } finally { + if (sr != null) { + sr.close(); + } + } + } + + @Test + public void testFileSortDate() throws IOException { + // make it so that we are not going to hit the disk + SimpleFeatureReader sr = null; + try { + sr = new SortedFeatureReader(fr, dateAsc, 100); + assertSortedOnDateAsc(sr); + } finally { + if (sr != null) { + sr.close(); + } + } + } + + @Test + public void testFileSortPeople() throws IOException { + // make it so that we are not going to hit the disk + SimpleFeatureReader sr = null; + try { + sr = new SortedFeatureReader(fr, peopleAsc, 5); + assertSortedOnPeopleAsc(sr); + } finally { + if (sr != null) { + sr.close(); + } + } + } + + @Test + public void testIteratorSortReduce() throws IOException { + // make it so that we are not going to hit the disk + SimpleFeatureIterator fi = null; + try { + fi = new SortedFeatureIterator(fc.features(), schema, peopleAsc, 1000); + assertSortedOnPeopleAsc(fi); + } finally { + if (fi != null) { + fi.close(); + } + } + } + + @Test + public void testSortDescending() throws IOException { + // make it so that we are not going to hit the disk + SimpleFeatureReader sr = null; + try { + sr = new SortedFeatureReader(fr, peopleDesc, 1000); + double prev = -1; + while (fr.hasNext()) { + SimpleFeature f = fr.next(); + double curr = (Double) f.getAttribute("PERSONS"); + if (prev > 0) { + assertTrue(curr <= prev); + } + prev = curr; + } + } finally { + if (sr != null) { + sr.close(); + } + } + } + + @Test + public void testSortNatural() throws IOException { + // make it so that we are not going to hit the disk + SimpleFeatureReader sr = null; + try { + sr = new SortedFeatureReader(fr, fidAsc, 1000); + String prev = null; + while (fr.hasNext()) { + SimpleFeature f = fr.next(); + String id = f.getID(); + if (prev != null) { + assertTrue(id.compareTo(prev) >= 0); + } + prev = id; + } + } finally { + if (sr != null) { + sr.close(); + } + } + } + + private void assertSortedOnPeopleAsc(SimpleFeatureReader fr) throws IllegalArgumentException, + NoSuchElementException, IOException { + double prev = -1; + while (fr.hasNext()) { + SimpleFeature f = fr.next(); + int curr = (Integer) f.getAttribute("PERSONS"); + if (prev > 0) { + assertTrue(curr >= prev); + } + prev = curr; + } + } + + private void assertSortedOnDateAsc(SimpleFeatureReader fr) throws IllegalArgumentException, + NoSuchElementException, IOException { + Date prev = null; + while (fr.hasNext()) { + SimpleFeature f = fr.next(); + Date curr = (Date) f.getAttribute("date"); + if (prev != null) { + assertTrue(prev.compareTo(curr) <= 0); + } + prev = curr; + } + } + + private void assertSortedOnPeopleAsc(SimpleFeatureIterator fi) throws IllegalArgumentException, + NoSuchElementException, IOException { + double prev = -1; + while (fi.hasNext()) { + SimpleFeature f = fi.next(); + int curr = (Integer) f.getAttribute("PERSONS"); + if (prev > 0) { + assertTrue(curr >= prev); + } + prev = curr; + } + } + +} Modified: branches/2.7.x/modules/library/metadata/src/main/java/org/geotools/factory/Hints.java =================================================================== --- branches/2.7.x/modules/library/metadata/src/main/java/org/geotools/factory/Hints.java 2011-12-08 22:39:09 UTC (rev 38413) +++ branches/2.7.x/modules/library/metadata/src/main/java/org/geotools/factory/Hints.java 2011-12-13 09:39:22 UTC (rev 38414) @@ -573,6 +573,15 @@ public static final Key FEATURE_2D = new Key(Boolean.class); /** + * Key to control the maximum number of features that will be kept in memory + * when performing a fallback merge-sort (used when the datastore does not have + * native means to handle feature sorting) + * + * @since 2.7.4 + */ + public static final Key MAX_MEMORY_SORT = new Key(Integer.class); + + /** * Asks a datastore having a vector pyramid (pre-generalized geometries) * to return the geometry version whose points have been generalized * less than the spefiedi distance (further generalization might be |
