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