--- /dev/null
+/*******************************************************************************\r
+ * Copyright (c) 2007, 2011 Association for Decentralized Information Management in\r
+ * Industry THTH ry.\r
+ * All rights reserved. This program and the accompanying materials\r
+ * are made available under the terms of the Eclipse Public License v1.0\r
+ * which accompanies this distribution, and is available at\r
+ * http://www.eclipse.org/legal/epl-v10.html\r
+ *\r
+ * Contributors:\r
+ * VTT Technical Research Centre of Finland - initial API and implementation\r
+ *******************************************************************************/\r
+package org.simantics.history.util;\r
+\r
+import java.util.Arrays;\r
+import java.util.Comparator;\r
+import java.util.Iterator;\r
+import java.util.PriorityQueue;\r
+import java.util.TreeMap;\r
+\r
+import org.simantics.databoard.annotations.Referable;\r
+\r
+/**\r
+ * Weighted median approximation\r
+ * \r
+ * @author toni.kalajainen\r
+ */\r
+public class WeightedMedianApprox {\r
+\r
+ static final Comparator<Item> valueComparator;\r
+ static final Comparator<Double> double_comparator, reverse_double_comparator;\r
+ \r
+ public Item median;\r
+ public TreeMap<Double, Item> lower;\r
+ public TreeMap<Double, Item> upper;\r
+ public int maxSize = Integer.MAX_VALUE;\r
+ public double rpos;\r
+\r
+ public WeightedMedianApprox() {\r
+ lower = new TreeMap<Double, Item>( reverse_double_comparator );\r
+ upper = new TreeMap<Double, Item>( double_comparator );\r
+ }\r
+ \r
+ public WeightedMedianApprox(int maxSize) {\r
+ this();\r
+ this.maxSize = maxSize;\r
+ }\r
+\r
+ public void clear() {\r
+ lower.clear();\r
+ upper.clear();\r
+ median = null;\r
+ rpos = 0.;\r
+ }\r
+\r
+ public void add(double weight, double value) {\r
+ \r
+ System.out.println("Adding (value="+value+", weight="+weight+")");\r
+ if (median == null) {\r
+ median = new Item(weight, value);\r
+ rpos = weight / 2;\r
+ return;\r
+ }\r
+ \r
+ if ( value == median.value ) {\r
+ median.weight += weight;\r
+ return;\r
+ }\r
+\r
+ TreeMap<Double, Item> map = value>median.value ? upper : lower;\r
+ Item i = map.get( value );\r
+ if ( i != null ) {\r
+ i.weight += weight;\r
+ } else {\r
+ map.put(value, new Item(weight, value));\r
+ }\r
+\r
+ rpos += (value<median.value?-1:1) * weight / 2;\r
+ balance();\r
+\r
+ int count = size();\r
+ if (count>maxSize) {\r
+ coalesce((count+1)/2); \r
+ }\r
+ }\r
+ \r
+ void balance() {\r
+ // Relative Pos - Balance\r
+ while (rpos<0) {\r
+ upper.put(median.value, median);\r
+ median = lower.remove( lower.firstKey() );\r
+ rpos += median.weight;\r
+ }\r
+ while (rpos>=median.weight) {\r
+ rpos -= median.weight;\r
+ lower.put(median.value, median);\r
+ median = upper.remove( upper.firstKey() );\r
+ } \r
+ \r
+ }\r
+\r
+ public double getMedian() {\r
+ if (median==null) return Double.NaN;\r
+ return median.value;\r
+ }\r
+\r
+ public int size() {\r
+ return upper.size() + lower.size() + (median==null?0:1);\r
+ }\r
+ \r
+ @Override\r
+ public String toString() {\r
+ StringBuilder sb = new StringBuilder();\r
+ sb.append( "Median="+getMedian()+" ");\r
+ \r
+ PriorityQueue<Item> q = new PriorityQueue<Item>( size(), valueComparator );\r
+ q.addAll(lower.values());\r
+ if (median!=null) q.add(median);\r
+ q.addAll(upper.values());\r
+ \r
+ while ( !q.isEmpty() ) {\r
+ Item i = q.remove();\r
+ sb.append("(value=");\r
+ sb.append(i.value);\r
+ sb.append(", w=");\r
+ sb.append(i.weight);\r
+ if (i == median) sb.append(", pos="+rpos);\r
+ sb.append(")");\r
+ }\r
+ \r
+ return sb.toString();\r
+ } \r
+ \r
+ /**\r
+ * Halves sample count.\r
+ * Combines items whose combination causes smallest error.\r
+ */\r
+ public void coalesce(int targetCount) {\r
+ int count = size();\r
+ if (count<3) return;\r
+ \r
+ ErrorStack err = new ErrorStack();\r
+ err.start();\r
+ Iterator<Item> itr = lower.values().iterator();\r
+ while (itr.hasNext()) {\r
+ Item item = itr.next();\r
+ err.addItem( item );\r
+ }\r
+ err.addItem( median );\r
+ itr = upper.values().iterator();\r
+ while (itr.hasNext()) {\r
+ Item item = itr.next();\r
+ err.addItem( item );\r
+ }\r
+ MergeAction[] errs = err.finish();\r
+ for (int i=targetCount-1; i>=0; i--) {\r
+ MergeAction e = errs[i];\r
+ System.out.println(" Merging "+e.itemToMerge+" to "+e.mergeToItem+", err="+e.error);\r
+ e.mergeToItem.weight += e.itemToMerge.weight;\r
+ if (e.itemToMerge == median) {\r
+ median = e.mergeToItem;\r
+ TreeMap<Double, Item> map = e.mergeToItem.value < median.value ? lower : upper;\r
+ map.remove(e.mergeToItem.value);\r
+ if (e.itemToMerge.value<e.mergeToItem.value) {\r
+ rpos += e.itemToMerge.weight;\r
+ balance();\r
+ }\r
+ } else {\r
+ TreeMap<Double, Item> map = e.itemToMerge.value < median.value ? lower : upper; \r
+ map.remove(e.mergeToItem.value);\r
+ }\r
+ }\r
+ }\r
+\r
+ @Referable\r
+ static public class Item {\r
+ public double weight;\r
+ public double value;\r
+ public Item() {}\r
+ public Item(double weight, double value) {\r
+ this.weight = weight;\r
+ this.value = value;\r
+ }\r
+ @Override\r
+ public String toString() {\r
+ return "(value="+value+", w="+weight+")";\r
+ } \r
+ } \r
+\r
+ class ErrorStack {\r
+ MergeAction[] errs;\r
+ int count;\r
+ int i;\r
+ Item prev;\r
+ void start() {\r
+ count = size();\r
+ errs = new MergeAction[ count - 1 ];\r
+ i = 0;\r
+ prev = null;\r
+ }\r
+ void addItem(Item item) {\r
+ if (prev!=null) {\r
+ MergeAction e = new MergeAction();\r
+ e.mergeToItem = prev;\r
+ e.itemToMerge = item;\r
+ double valueDiff = Math.abs(e.itemToMerge.value - e.mergeToItem.value);\r
+ double mergeError = valueDiff * e.itemToMerge.weight;\r
+ e.error = mergeError;\r
+ errs[i++] = e;\r
+ }\r
+ prev = item;\r
+ }\r
+ MergeAction[] finish() {\r
+ MergeErrorComparator c = new MergeErrorComparator();\r
+ c.median = median!=null?median.value:0;\r
+ Arrays.sort(errs, c);\r
+ return errs;\r
+ }\r
+ }\r
+ \r
+ static class MergeAction {\r
+ public double error;\r
+ public Item mergeToItem, itemToMerge;\r
+ } \r
+ \r
+ /**\r
+ * This comparator minimizes error, then maximizes distance to median\r
+ */\r
+ static class MergeErrorComparator implements Comparator<MergeAction> {\r
+ double median;\r
+ @Override\r
+ public int compare(MergeAction o1, MergeAction o2) {\r
+ double diff = o1.error - o2.error;\r
+ if (diff==0) {\r
+ double distToMedian1 = o1.mergeToItem.value - median;\r
+ double distToMedian2 = o2.mergeToItem.value - median;\r
+ diff = distToMedian1 - distToMedian2;\r
+ return diff>0?-1:1;\r
+ } else return diff<0?-1:1; \r
+ }\r
+ };\r
+\r
+ \r
+ static {\r
+ \r
+ valueComparator = new Comparator<Item>() {\r
+ @Override\r
+ public int compare(Item o1, Item o2) {\r
+ double diff = o1.value - o2.value;\r
+ return diff==0.0 ? 0 : ( diff<0?-1:1);\r
+ }\r
+ };\r
+ \r
+ reverse_double_comparator = new Comparator<Double>() {\r
+ @Override\r
+ public int compare(Double o1, Double o2) {\r
+ Double d1 = (Double) o1;\r
+ Double d2 = (Double) o2;\r
+ double d = d2-d1;\r
+ return d == 0.0 ? 0 : (d<0?-1:1);\r
+ }};\r
+ \r
+ double_comparator = new Comparator<Double>() {\r
+ @Override\r
+ public int compare(Double o1, Double o2) {\r
+ Double d1 = (Double) o1;\r
+ Double d2 = (Double) o2;\r
+ double d = d1-d2;\r
+ return d == 0.0 ? 0 : (d<0?-1:1);\r
+ }};\r
+ \r
+ }\r
+ \r
+ \r
+}\r
Code Review / simantics / platform.git / blobdiff