--- /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 org.simantics.databoard.annotations.Optional;\r
+import org.simantics.databoard.annotations.Referable;\r
+\r
+/**\r
+ * \r
+ * @author toni.kalajainen\r
+ */\r
+public class WeightedMedian {\r
+\r
+ public int maxItems;\r
+ public int itemCount;\r
+ @Optional public Item median;\r
+ \r
+ // Relative pos = pos - median.accumulated weight \r
+ public double rpos;\r
+ \r
+ public WeightedMedian()\r
+ {\r
+ maxItems = Integer.MAX_VALUE;\r
+ }\r
+ \r
+ public WeightedMedian(int maxItems)\r
+ {\r
+ this.maxItems = maxItems;\r
+ }\r
+ \r
+ public void clear() {\r
+ itemCount = 0;\r
+ median = null;\r
+ rpos = 0;\r
+ }\r
+ \r
+ public void add(double weight, double value)\r
+ {\r
+ if (weight<=0) return;\r
+ if (median == null) {\r
+ median = new Item( weight, value );\r
+ itemCount++;\r
+ rpos = weight / 2;\r
+ return; \r
+ }\r
+ \r
+ Item i = median;\r
+ while (true) {\r
+ \r
+ if (i.value==value) {\r
+ i.weight += weight;\r
+ break;\r
+ }\r
+ \r
+ if (value < i.value) {\r
+ \r
+ // i = 1st, add new item as first\r
+ if (i.prev==null) {\r
+ i.prev = new Item( weight, value, null, i );\r
+ itemCount++;\r
+ break;\r
+ }\r
+ \r
+ // value is between two items, add new item\r
+ if (i.prev.value < value) {\r
+ Item n = new Item( weight, value, i.prev, i );\r
+ itemCount++;\r
+ i.prev.next = n;\r
+ i.prev = n;\r
+ break;\r
+ }\r
+ \r
+ i = i.prev;\r
+ continue;\r
+ } \r
+ \r
+ if (value > i.value) {\r
+ \r
+ // i = last, add new item as last\r
+ if (i.next==null) {\r
+ i.next = new Item( weight, value, i, null ); \r
+ itemCount++;\r
+ break;\r
+ }\r
+ \r
+ // value is between two items, add new item\r
+ if (i.next.value > value) {\r
+ Item n = new Item( weight, value, i, i.next );\r
+ itemCount++;\r
+ i.next.prev = n;\r
+ i.next = n;\r
+ break;\r
+ }\r
+ \r
+ i = i.next;\r
+ continue;\r
+ }\r
+ }\r
+\r
+ rpos += (value<median.value?-1:1) * weight / 2;\r
+ while (rpos<0) {\r
+ median = median.prev;\r
+ rpos += median.weight;\r
+ }\r
+ while (rpos>=median.weight) {\r
+ rpos -= median.weight;\r
+ median = median.next;\r
+ }\r
+ \r
+ if (itemCount>maxItems) coalesce();\r
+ }\r
+ \r
+ /**\r
+ */\r
+ public void coalesce() {\r
+ coalesceVerySimple();\r
+ }\r
+ \r
+ /**\r
+ * Simple coalesce, combine two samples\r
+ */\r
+ public void coalesceVerySimple() \r
+ {\r
+ Item i = median.next;\r
+ while (i!=null) {\r
+ Item n = i.next;\r
+ if (n==null) break;\r
+ i.next = n.next;\r
+ if (n.next!=null) n.next.prev = i;\r
+ \r
+ Item itemToMerge = n.weight>i.weight ? n : i;\r
+ Item mergeToItem = n.weight>i.weight ? i : n;\r
+ \r
+ double totWeight = mergeToItem.weight+itemToMerge.weight;\r
+ //mergeToItem.value = ( mergeToItem.value * mergeToItem.weight + itemToMerge.value * itemToMerge.weight ) / totWeight;\r
+ mergeToItem.weight = totWeight;\r
+ i = i.next;\r
+ }\r
+ \r
+ i = median.prev;\r
+ while (i!=null) {\r
+ Item p = i.prev;\r
+ if (p==null) break;\r
+ i.prev = p.prev;\r
+ if (p.prev!=null) p.prev.next = i;\r
+ \r
+ Item itemToMerge = p.weight>i.weight ? p : i;\r
+ Item mergeToItem = p.weight>i.weight ? p : i;\r
+ \r
+ double totWeight = mergeToItem.weight+itemToMerge.weight;\r
+ //mergeToItem.value = ( mergeToItem.value * mergeToItem.weight + itemToMerge.value * itemToMerge.weight ) / totWeight;\r
+ mergeToItem.weight = totWeight;\r
+ \r
+ i.weight = totWeight;\r
+ i = i.prev;\r
+ } \r
+ }\r
+ \r
+ public double getMedian() \r
+ {\r
+ if (median==null) return Double.NaN;\r
+ return median.value;\r
+ }\r
+ \r
+ @Override\r
+ public String toString() {\r
+ StringBuilder sb = new StringBuilder();\r
+ sb.append( "Median="+getMedian()+" ");\r
+ \r
+ Item i = head();\r
+ while (i!=null) {\r
+ if (i==median) {\r
+ sb.append("(value="+i.value+", w="+i.weight+", pos="+rpos+")");\r
+ } else {\r
+ sb.append("(value="+i.value+", w="+i.weight+")");\r
+ }\r
+ i = i.next;\r
+ }\r
+ \r
+ return sb.toString();\r
+ } \r
+ \r
+ Item head() {\r
+ if (median==null) return null;\r
+ Item i = median;\r
+ while (i.prev!=null) i = i.prev;\r
+ return i;\r
+ }\r
+ \r
+ @Referable\r
+ static public class Item {\r
+ public double weight;\r
+ public double value;\r
+ \r
+ public Item(double weight, double value) {\r
+ this.weight = weight;\r
+ this.value = value;\r
+ }\r
+\r
+ public Item(double weight, double value, Item prev, Item next) {\r
+ this.weight = weight;\r
+ this.value = value;\r
+ this.prev = prev;\r
+ this.next = next;\r
+ }\r
+ \r
+ @Optional\r
+ public Item prev;\r
+ \r
+ @Optional\r
+ public Item next;\r
+ \r
+ @Override\r
+ public String toString() {\r
+ return "(value="+value+", w="+weight+")";\r
+ }\r
+ }\r
+ \r
+}\r