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 java.util.Arrays;
15 import java.util.Comparator;
16 import java.util.Iterator;
17 import java.util.PriorityQueue;
18 import java.util.TreeMap;
20 import org.simantics.databoard.annotations.Referable;
23 * Weighted median approximation
25 * @author toni.kalajainen
27 public class WeightedMedianApprox {
29 static final Comparator<Item> valueComparator;
30 static final Comparator<Double> double_comparator, reverse_double_comparator;
33 public TreeMap<Double, Item> lower;
34 public TreeMap<Double, Item> upper;
35 public int maxSize = Integer.MAX_VALUE;
38 public WeightedMedianApprox() {
39 lower = new TreeMap<Double, Item>( reverse_double_comparator );
40 upper = new TreeMap<Double, Item>( double_comparator );
43 public WeightedMedianApprox(int maxSize) {
45 this.maxSize = maxSize;
55 public void add(double weight, double value) {
57 System.out.println("Adding (value="+value+", weight="+weight+")");
59 median = new Item(weight, value);
64 if ( value == median.value ) {
65 median.weight += weight;
69 TreeMap<Double, Item> map = value>median.value ? upper : lower;
70 Item i = map.get( value );
74 map.put(value, new Item(weight, value));
77 rpos += (value<median.value?-1:1) * weight / 2;
82 coalesce((count+1)/2);
87 // Relative Pos - Balance
89 upper.put(median.value, median);
90 median = lower.remove( lower.firstKey() );
91 rpos += median.weight;
93 while (rpos>=median.weight) {
94 rpos -= median.weight;
95 lower.put(median.value, median);
96 median = upper.remove( upper.firstKey() );
101 public double getMedian() {
102 if (median==null) return Double.NaN;
107 return upper.size() + lower.size() + (median==null?0:1);
111 public String toString() {
112 StringBuilder sb = new StringBuilder();
113 sb.append( "Median="+getMedian()+" ");
115 PriorityQueue<Item> q = new PriorityQueue<Item>( size(), valueComparator );
116 q.addAll(lower.values());
117 if (median!=null) q.add(median);
118 q.addAll(upper.values());
120 while ( !q.isEmpty() ) {
122 sb.append("(value=");
126 if (i == median) sb.append(", pos="+rpos);
130 return sb.toString();
134 * Halves sample count.
135 * Combines items whose combination causes smallest error.
137 public void coalesce(int targetCount) {
141 ErrorStack err = new ErrorStack();
143 Iterator<Item> itr = lower.values().iterator();
144 while (itr.hasNext()) {
145 Item item = itr.next();
148 err.addItem( median );
149 itr = upper.values().iterator();
150 while (itr.hasNext()) {
151 Item item = itr.next();
154 MergeAction[] errs = err.finish();
155 for (int i=targetCount-1; i>=0; i--) {
156 MergeAction e = errs[i];
157 System.out.println(" Merging "+e.itemToMerge+" to "+e.mergeToItem+", err="+e.error);
158 e.mergeToItem.weight += e.itemToMerge.weight;
159 if (e.itemToMerge == median) {
160 median = e.mergeToItem;
161 TreeMap<Double, Item> map = e.mergeToItem.value < median.value ? lower : upper;
162 map.remove(e.mergeToItem.value);
163 if (e.itemToMerge.value<e.mergeToItem.value) {
164 rpos += e.itemToMerge.weight;
168 TreeMap<Double, Item> map = e.itemToMerge.value < median.value ? lower : upper;
169 map.remove(e.mergeToItem.value);
175 static public class Item {
176 public double weight;
179 public Item(double weight, double value) {
180 this.weight = weight;
184 public String toString() {
185 return "(value="+value+", w="+weight+")";
196 errs = new MergeAction[ count - 1 ];
200 void addItem(Item item) {
202 MergeAction e = new MergeAction();
203 e.mergeToItem = prev;
204 e.itemToMerge = item;
205 double valueDiff = Math.abs(e.itemToMerge.value - e.mergeToItem.value);
206 double mergeError = valueDiff * e.itemToMerge.weight;
207 e.error = mergeError;
212 MergeAction[] finish() {
213 MergeErrorComparator c = new MergeErrorComparator();
214 c.median = median!=null?median.value:0;
215 Arrays.sort(errs, c);
220 static class MergeAction {
222 public Item mergeToItem, itemToMerge;
226 * This comparator minimizes error, then maximizes distance to median
228 static class MergeErrorComparator implements Comparator<MergeAction> {
231 public int compare(MergeAction o1, MergeAction o2) {
232 double diff = o1.error - o2.error;
234 double distToMedian1 = o1.mergeToItem.value - median;
235 double distToMedian2 = o2.mergeToItem.value - median;
236 diff = distToMedian1 - distToMedian2;
238 } else return diff<0?-1:1;
245 valueComparator = new Comparator<Item>() {
247 public int compare(Item o1, Item o2) {
248 double diff = o1.value - o2.value;
249 return diff==0.0 ? 0 : ( diff<0?-1:1);
253 reverse_double_comparator = new Comparator<Double>() {
255 public int compare(Double o1, Double o2) {
256 Double d1 = (Double) o1;
257 Double d2 = (Double) o2;
259 return d == 0.0 ? 0 : (d<0?-1:1);
262 double_comparator = new Comparator<Double>() {
264 public int compare(Double o1, Double o2) {
265 Double d1 = (Double) o1;
266 Double d2 = (Double) o2;
268 return d == 0.0 ? 0 : (d<0?-1:1);