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