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