001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2005-2006, GeoTools Project Managment Committee (PMC)
005: *
006: * This library is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU Lesser General Public
008: * License as published by the Free Software Foundation;
009: * version 2.1 of the License.
010: *
011: * This library is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * Lesser General Public License for more details.
015: */
016: package org.geotools.feature.visitor;
017:
018: import java.util.ArrayList;
019: import java.util.Collections;
020: import java.util.List;
021:
022: import org.geotools.factory.CommonFactoryFinder;
023: import org.geotools.feature.Feature;
024: import org.geotools.feature.FeatureType;
025: import org.geotools.filter.IllegalFilterException;
026: import org.opengis.filter.FilterFactory;
027: import org.opengis.filter.expression.Expression;
028:
029: /**
030: * Calculates the median of an attribute in all features of a collection
031: *
032: * @author Cory Horner, Refractions
033: *
034: * @since 2.2.M2
035: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/library/main/src/main/java/org/geotools/feature/visitor/MedianVisitor.java $
036: */
037: public class MedianVisitor implements FeatureCalc {
038: private Expression expr;
039: private List list = new ArrayList();
040: /**
041: * This var is only used to store the median for optimized functions, where
042: * we don't have a complete list, but just the answer instead (merging will
043: * be disabled until some cool code is written to handle this). Only
044: * setValue(median) should write to this var. If this value is not null, it
045: * takes priority over list.
046: */
047: private Object median = null;
048:
049: public MedianVisitor(String attributeTypeName) {
050: FilterFactory factory = CommonFactoryFinder
051: .getFilterFactory(null);
052: expr = factory.property(attributeTypeName);
053: }
054:
055: public MedianVisitor(int attributeTypeIndex, FeatureType type)
056: throws IllegalFilterException {
057: FilterFactory factory = CommonFactoryFinder
058: .getFilterFactory(null);
059: expr = factory.property(type.getAttributeType(
060: attributeTypeIndex).getName());
061: }
062:
063: public MedianVisitor(String attrName, FeatureType type)
064: throws IllegalFilterException {
065: FilterFactory factory = CommonFactoryFinder
066: .getFilterFactory(null);
067: expr = factory.property(type.getAttributeType(attrName)
068: .getName());
069: }
070:
071: public MedianVisitor(Expression expr) throws IllegalFilterException {
072: this .expr = expr;
073: }
074:
075: public void visit(Feature feature) {
076: /**
077: * Visitor function
078: */
079: Object result = expr.evaluate(feature);
080: if (result instanceof Comparable) {
081: Comparable value = (Comparable) result;
082: list.add(value);
083: } else {
084: throw new IllegalStateException(
085: "Expression is not comparable!");
086: }
087: }
088:
089: public Expression getExpression() {
090: return expr;
091: }
092:
093: /**
094: * Return the median of all features in the collection
095: */
096: public Object getMedian() {
097: if (median != null) {
098: //median was overwritten by an optimization
099: return median;
100: } else {
101: //we're got a list of items, determine the median...
102: Object newMedian = findMedian(list);
103: if (newMedian == null) {
104: throw new IllegalStateException(
105: "Must visit before median value is ready!");
106: }
107: return newMedian;
108: }
109: }
110:
111: /**
112: * Reset the stored information about the median.
113: */
114: public void reset() {
115: this .list.clear();
116: this .median = null;
117: }
118:
119: public CalcResult getResult() {
120: if (median != null) {
121: // median was overwritten by an optimization
122: return new MedianResult(median);
123: } else if (list.size() < 1) {
124: // no items in the list
125: return null;
126: } else {
127: // we have a list; create a CalcResult containing the list
128: return new MedianResult(list);
129: }
130: }
131:
132: public void setValue(List list) {
133: reset();
134: this .list = list;
135: }
136:
137: public void setValue(Comparable median) {
138: reset();
139: this .median = median;
140: }
141:
142: public static class MedianResult extends AbstractCalcResult {
143: private List list;
144: /**
145: * When an optimization is used, median will have a value and list will
146: * not. This var takes priority over list.
147: */
148: private Object median;
149:
150: public MedianResult(List newList) {
151: this .list = newList;
152: this .median = null;
153: }
154:
155: public MedianResult(Object median) {
156: this .list = null;
157: this .median = median;
158: }
159:
160: public List getList() {
161: return list;
162: }
163:
164: public Object getValue() {
165: if (median != null) {
166: return median;
167: } else {
168: return findMedian(list);
169: }
170: }
171:
172: public boolean isCompatible(CalcResult targetResults) {
173: //list each calculation result which can merge with this type of result
174: if (targetResults instanceof MedianResult)
175: return true;
176: return false;
177: }
178:
179: public boolean isOptimized() {
180: if (median != null)
181: return true;
182: else
183: return false;
184: }
185:
186: public CalcResult merge(CalcResult resultsToAdd) {
187: if (!isCompatible(resultsToAdd)) {
188: throw new IllegalArgumentException(
189: "Parameter is not a compatible type");
190: }
191: if (resultsToAdd instanceof MedianResult) {
192: MedianResult moreResults = (MedianResult) resultsToAdd;
193: //ensure both MedianResults are NOT optimized
194: if (isOptimized() || moreResults.isOptimized()) {
195: throw new IllegalArgumentException(
196: "Optimized median results cannot be merged.");
197: }
198: //merge away...
199: List toAdd = (ArrayList) moreResults.getList();
200: List newList = new ArrayList();
201: //extract each item to an array, and convert to a common data type
202: int size = list.size() + toAdd.size();
203: Object[] values = new Object[size];
204: int i;
205: for (i = 0; i < list.size(); i++)
206: values[i] = list.get(i);
207: for (int j = 0; j < toAdd.size(); j++)
208: values[i + j] = toAdd.get(j);
209: Class bestClass = CalcUtil.bestClass(values);
210: for (int k = 0; k < size; k++) {
211: if (values[k].getClass() != bestClass)
212: values[k] = CalcUtil.convert(values[k],
213: bestClass);
214: newList.add((Comparable) values[k]);
215: }
216: return new MedianResult(newList);
217: } else {
218: throw new IllegalArgumentException(
219: "The CalcResults claim to be compatible, but the appropriate merge method has not been implemented.");
220: }
221: }
222: }
223:
224: /**
225: * Given a list, determines the median value and returns it. For numbers,
226: * the middle value is returned, or the average of the two middle numbers if
227: * there are an even number of elements. For non-numeric values (strings,
228: * etc) where the number of elements is even, a list containing the two
229: * middle elements is returned.
230: *
231: * @param list an arraylist which is to be sorted and its median extracted
232: * @return the median
233: */
234: private static Object findMedian(List list) {
235: if (list.size() < 1) {
236: return null;
237: }
238: Object median;
239: Collections.sort(list);
240:
241: int index = -1;
242: index = (int) list.size() / 2;
243:
244: if ((list.size() % 2) == 0) {
245: // even number of elements, so we must average the 2 middle ones, or
246: // return a list for non-numeric elements
247: Object input1 = list.get(index - 1);
248: Object input2 = list.get(index);
249:
250: if ((input1 instanceof Number)
251: && (input2 instanceof Number)) {
252: Number num1 = (Number) input1;
253: Number num2 = (Number) input2;
254: Number[] numbers = new Number[2];
255: numbers[0] = num1;
256: numbers[1] = num2;
257: median = CalcUtil.average(numbers);
258: } else { //NaN
259: //return a list containing the two middle elements
260: List newList = new ArrayList();
261: newList.add(input1);
262: newList.add(input2);
263: median = newList;
264: }
265: } else {
266: // an odd number of elements are in the list, so we simply return
267: // the one in the middle, which we've already calculated the index
268: // for.
269: median = list.get(index);
270: }
271: return median;
272: }
273: }
|