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 WeightedMedian {
25 @Optional public Item median;
27 // Relative pos = pos - median.accumulated weight
30 public WeightedMedian()
32 maxItems = Integer.MAX_VALUE;
35 public WeightedMedian(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 );
64 if (value < i.value) {
66 // i = 1st, add new item as first
68 i.prev = new Item( weight, value, null, i );
73 // value is between two items, add new item
74 if (i.prev.value < value) {
75 Item n = new Item( weight, value, i.prev, i );
86 if (value > i.value) {
88 // i = last, add new item as last
90 i.next = new Item( weight, value, i, null );
95 // value is between two items, add new item
96 if (i.next.value > value) {
97 Item n = new Item( weight, value, i, i.next );
109 rpos += (value<median.value?-1:1) * weight / 2;
111 median = median.prev;
112 rpos += median.weight;
114 while (rpos>=median.weight) {
115 rpos -= median.weight;
116 median = median.next;
119 if (itemCount>maxItems) coalesce();
124 public void coalesce() {
125 coalesceVerySimple();
129 * Simple coalesce, combine two samples
131 public void coalesceVerySimple()
133 Item i = median.next;
138 if (n.next!=null) n.next.prev = i;
140 Item itemToMerge = n.weight>i.weight ? n : i;
141 Item mergeToItem = n.weight>i.weight ? i : n;
143 double totWeight = mergeToItem.weight+itemToMerge.weight;
144 //mergeToItem.value = ( mergeToItem.value * mergeToItem.weight + itemToMerge.value * itemToMerge.weight ) / totWeight;
145 mergeToItem.weight = totWeight;
154 if (p.prev!=null) p.prev.next = i;
156 Item itemToMerge = p.weight>i.weight ? p : i;
157 Item mergeToItem = p.weight>i.weight ? p : i;
159 double totWeight = mergeToItem.weight+itemToMerge.weight;
160 //mergeToItem.value = ( mergeToItem.value * mergeToItem.weight + itemToMerge.value * itemToMerge.weight ) / totWeight;
161 mergeToItem.weight = totWeight;
163 i.weight = totWeight;
168 public double getMedian()
170 if (median==null) return Double.NaN;
175 public String toString() {
176 StringBuilder sb = new StringBuilder();
177 sb.append( "Median="+getMedian()+" ");
182 sb.append("(value="+i.value+", w="+i.weight+", pos="+rpos+")");
184 sb.append("(value="+i.value+", w="+i.weight+")");
189 return sb.toString();
193 if (median==null) return null;
195 while (i.prev!=null) i = i.prev;
200 static public class Item {
201 public double weight;
204 public Item(double weight, double value) {
205 this.weight = weight;
209 public Item(double weight, double value, Item prev, Item next) {
210 this.weight = weight;
223 public String toString() {
224 return "(value="+value+", w="+weight+")";