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 WeightedMedian2 {
\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 WeightedMedian2()
\r
32 maxItems = Integer.MAX_VALUE;
\r
35 public WeightedMedian2(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 (value>=i.low && value<=i.high) {
\r
60 double totWeight = i.weight+weight;
\r
61 i.value = ( i.value * i.weight + value * weight ) / totWeight;
\r
62 i.weight = totWeight;
\r
66 if (value < i.low) {
\r
68 // i = 1st, add new item as first
\r
70 i.prev = new Item( weight, value, null, i );
\r
75 // value is between two items, add new item
\r
76 if (i.prev.high < value) {
\r
77 Item n = new Item( weight, value, i.prev, i );
\r
88 if (value > i.high) {
\r
90 // i = last, add new item as last
\r
92 i.next = new Item( weight, value, i, null );
\r
97 // value is between two items, add new item
\r
98 if (i.next.low > value) {
\r
99 Item n = new Item( weight, value, i, i.next );
\r
111 rpos += (value<median.low?-1:1) * weight / 2;
\r
113 median = median.prev;
\r
114 rpos += median.weight;
\r
116 while (rpos>=median.weight) {
\r
117 rpos -= median.weight;
\r
118 median = median.next;
\r
121 if (itemCount>maxItems) coalesce();
\r
124 public void coalesce()
\r
126 Item i = median.next;
\r
129 if (n==null) break;
\r
131 if (n.next!=null) n.next.prev = i;
\r
132 double totWeight = i.weight+n.weight;
\r
134 i.value = ( i.value * i.weight + n.value * n.weight ) / totWeight;
\r
135 i.weight = totWeight;
\r
142 if (p==null) break;
\r
144 if (p.prev!=null) p.prev.next = i;
\r
145 double totWeight = i.weight+p.weight;
\r
147 i.value = ( i.value * i.weight + p.value * p.weight ) / totWeight;
\r
148 i.weight = totWeight;
\r
153 public double getMedian()
\r
155 if (median==null) return Double.NaN;
\r
156 if (median.low == median.high) return median.value;
\r
157 double d = median.high - median.low;
\r
158 double r = rpos/median.weight;
\r
159 return median.low + d*r;
\r
163 public String toString() {
\r
164 StringBuilder sb = new StringBuilder();
\r
165 sb.append( "Median="+getMedian()+" ");
\r
170 sb.append("value=");
\r
171 if (i.low==i.high) sb.append(i.value); else
\r
172 sb.append(i.value+" ("+i.low+".."+i.high+")");
\r
173 sb.append(", w="+i.weight);
\r
175 sb.append(", pos="+rpos);
\r
181 return sb.toString();
\r
185 if (median==null) return null;
\r
187 while (i.prev!=null) i = i.prev;
\r
192 static public class Item {
\r
193 public double weight;
\r
195 public double high;
\r
196 public double value;
\r
200 public Item(double weight, double value) {
\r
201 this.weight = weight;
\r
202 this.low = this.high = value;
\r
205 public Item(double weight, double value, Item prev, Item next) {
\r
206 this.weight = weight;
\r
207 this.value = this.low = this.high = value;
\r
219 public String toString() {
\r
220 if (low==high) return "(value="+value+", w="+weight+")";
\r
221 return "(value="+value+" ("+low+".."+high+"), w="+weight+")";
\r