1 /*******************************************************************************
2 * Copyright (c) 2007, 2011 Association for Decentralized Information Management in
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.history.util;
14 import org.simantics.databoard.annotations.Optional;
15 import org.simantics.databoard.annotations.Referable;
19 * @author toni.kalajainen
21 public class WeightedMedian2 {
25 @Optional public Item median;
27 // Relative pos = pos - median.accumulated weight
30 public WeightedMedian2()
32 maxItems = Integer.MAX_VALUE;
35 public WeightedMedian2(int maxItems)
37 this.maxItems = maxItems;
46 public void add(double weight, double value)
48 if (weight<=0) return;
50 median = new Item( weight, value );
59 if (value>=i.low && value<=i.high) {
60 double totWeight = i.weight+weight;
61 i.value = ( i.value * i.weight + value * weight ) / totWeight;
68 // i = 1st, add new item as first
70 i.prev = new Item( weight, value, null, i );
75 // value is between two items, add new item
76 if (i.prev.high < value) {
77 Item n = new Item( weight, value, i.prev, i );
90 // i = last, add new item as last
92 i.next = new Item( weight, value, i, null );
97 // value is between two items, add new item
98 if (i.next.low > value) {
99 Item n = new Item( weight, value, i, i.next );
111 rpos += (value<median.low?-1:1) * weight / 2;
113 median = median.prev;
114 rpos += median.weight;
116 while (rpos>=median.weight) {
117 rpos -= median.weight;
118 median = median.next;
121 if (itemCount>maxItems) coalesce();
124 public void coalesce()
126 Item i = median.next;
131 if (n.next!=null) n.next.prev = i;
132 double totWeight = i.weight+n.weight;
134 i.value = ( i.value * i.weight + n.value * n.weight ) / totWeight;
135 i.weight = totWeight;
144 if (p.prev!=null) p.prev.next = i;
145 double totWeight = i.weight+p.weight;
147 i.value = ( i.value * i.weight + p.value * p.weight ) / totWeight;
148 i.weight = totWeight;
153 public double getMedian()
155 if (median==null) return Double.NaN;
156 if (median.low == median.high) return median.value;
157 double d = median.high - median.low;
158 double r = rpos/median.weight;
159 return median.low + d*r;
163 public String toString() {
164 StringBuilder sb = new StringBuilder();
165 sb.append( "Median="+getMedian()+" ");
171 if (i.low==i.high) sb.append(i.value); else
172 sb.append(i.value+" ("+i.low+".."+i.high+")");
173 sb.append(", w="+i.weight);
175 sb.append(", pos="+rpos);
181 return sb.toString();
185 if (median==null) return null;
187 while (i.prev!=null) i = i.prev;
192 static public class Item {
193 public double weight;
200 public Item(double weight, double value) {
201 this.weight = weight;
202 this.low = this.high = value;
205 public Item(double weight, double value, Item prev, Item next) {
206 this.weight = weight;
207 this.value = this.low = this.high = value;
219 public String toString() {
220 if (low==high) return "(value="+value+", w="+weight+")";
221 return "(value="+value+" ("+low+".."+high+"), w="+weight+")";