1 /*******************************************************************************
\r
2 * Copyright (c) 2007, 2011 Association for Decentralized Information Management in
\r
4 * All rights reserved. This program and the accompanying materials
\r
5 * are made available under the terms of the Eclipse Public License v1.0
\r
6 * which accompanies this distribution, and is available at
\r
7 * http://www.eclipse.org/legal/epl-v10.html
\r
10 * VTT Technical Research Centre of Finland - initial API and implementation
\r
11 *******************************************************************************/
\r
12 package org.simantics.history.util;
\r
14 import org.simantics.databoard.annotations.Optional;
\r
15 import org.simantics.databoard.annotations.Referable;
\r
19 * @author toni.kalajainen
\r
21 public class WeightedMedian {
\r
23 public int maxItems;
\r
24 public int itemCount;
\r
25 @Optional public Item median;
\r
27 // Relative pos = pos - median.accumulated weight
\r
30 public WeightedMedian()
\r
32 maxItems = Integer.MAX_VALUE;
\r
35 public WeightedMedian(int maxItems)
\r
37 this.maxItems = maxItems;
\r
40 public void clear() {
\r
46 public void add(double weight, double value)
\r
48 if (weight<=0) return;
\r
49 if (median == null) {
\r
50 median = new Item( weight, value );
\r
59 if (i.value==value) {
\r
64 if (value < i.value) {
\r
66 // i = 1st, add new item as first
\r
68 i.prev = new Item( weight, value, null, i );
\r
73 // value is between two items, add new item
\r
74 if (i.prev.value < value) {
\r
75 Item n = new Item( weight, value, i.prev, i );
\r
86 if (value > i.value) {
\r
88 // i = last, add new item as last
\r
90 i.next = new Item( weight, value, i, null );
\r
95 // value is between two items, add new item
\r
96 if (i.next.value > value) {
\r
97 Item n = new Item( weight, value, i, i.next );
\r
109 rpos += (value<median.value?-1:1) * weight / 2;
\r
111 median = median.prev;
\r
112 rpos += median.weight;
\r
114 while (rpos>=median.weight) {
\r
115 rpos -= median.weight;
\r
116 median = median.next;
\r
119 if (itemCount>maxItems) coalesce();
\r
124 public void coalesce() {
\r
125 coalesceVerySimple();
\r
129 * Simple coalesce, combine two samples
\r
131 public void coalesceVerySimple()
\r
133 Item i = median.next;
\r
136 if (n==null) break;
\r
138 if (n.next!=null) n.next.prev = i;
\r
140 Item itemToMerge = n.weight>i.weight ? n : i;
\r
141 Item mergeToItem = n.weight>i.weight ? i : n;
\r
143 double totWeight = mergeToItem.weight+itemToMerge.weight;
\r
144 //mergeToItem.value = ( mergeToItem.value * mergeToItem.weight + itemToMerge.value * itemToMerge.weight ) / totWeight;
\r
145 mergeToItem.weight = totWeight;
\r
152 if (p==null) break;
\r
154 if (p.prev!=null) p.prev.next = i;
\r
156 Item itemToMerge = p.weight>i.weight ? p : i;
\r
157 Item mergeToItem = p.weight>i.weight ? p : i;
\r
159 double totWeight = mergeToItem.weight+itemToMerge.weight;
\r
160 //mergeToItem.value = ( mergeToItem.value * mergeToItem.weight + itemToMerge.value * itemToMerge.weight ) / totWeight;
\r
161 mergeToItem.weight = totWeight;
\r
163 i.weight = totWeight;
\r
168 public double getMedian()
\r
170 if (median==null) return Double.NaN;
\r
171 return median.value;
\r
175 public String toString() {
\r
176 StringBuilder sb = new StringBuilder();
\r
177 sb.append( "Median="+getMedian()+" ");
\r
182 sb.append("(value="+i.value+", w="+i.weight+", pos="+rpos+")");
\r
184 sb.append("(value="+i.value+", w="+i.weight+")");
\r
189 return sb.toString();
\r
193 if (median==null) return null;
\r
195 while (i.prev!=null) i = i.prev;
\r
200 static public class Item {
\r
201 public double weight;
\r
202 public double value;
\r
204 public Item(double weight, double value) {
\r
205 this.weight = weight;
\r
206 this.value = value;
\r
209 public Item(double weight, double value, Item prev, Item next) {
\r
210 this.weight = weight;
\r
211 this.value = value;
\r
223 public String toString() {
\r
224 return "(value="+value+", w="+weight+")";
\r