bundles/org.simantics.history/src/org/simantics/history/util/WeightedMedianApprox.java

   1 /*******************************************************************************
   2  * Copyright (c) 2007, 2011 Association for Decentralized Information Management in
   3  * Industry THTH ry.
   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
   8  *
   9  * Contributors:
  10  *     VTT Technical Research Centre of Finland - initial API and implementation
  11  *******************************************************************************/
  12 package org.simantics.history.util;
  13
  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;
  19
  20 import org.simantics.databoard.annotations.Referable;
  21
  22 /**
  23  * Weighted median approximation
  24  *
  25  * @author toni.kalajainen
  26  */
  27 public class WeightedMedianApprox {
  28
  29         static final Comparator<Item> valueComparator;
  30         static final Comparator<Double> double_comparator, reverse_double_comparator;
  31
  32     public Item median;
  33     public TreeMap<Double, Item> lower;
  34     public TreeMap<Double, Item> upper;
  35     public int maxSize = Integer.MAX_VALUE;
  36     public double rpos;
  37
  38     public WeightedMedianApprox() {
  39         lower = new TreeMap<Double, Item>( reverse_double_comparator );
  40         upper = new TreeMap<Double, Item>( double_comparator );
  41     }
  42
  43     public WeightedMedianApprox(int maxSize) {
  44         this();
  45         this.maxSize = maxSize;
  46     }
  47
  48     public void clear() {
  49         lower.clear();
  50         upper.clear();
  51         median = null;
  52         rpos = 0.;
  53     }
  54
  55     public void add(double weight, double value) {
  56
  57         System.out.println("Adding (value="+value+", weight="+weight+")");
  58         if (median == null) {
  59             median = new Item(weight, value);
  60                         rpos = weight / 2;
  61             return;
  62         }
  63
  64         if ( value == median.value ) {
  65                 median.weight += weight;
  66                 return;
  67         }
  68
  69         TreeMap<Double, Item> map = value>median.value ? upper : lower;
  70         Item i = map.get( value );
  71         if ( i != null ) {
  72                 i.weight += weight;
  73         } else {
  74                 map.put(value, new Item(weight, value));
  75         }
  76
  77                 rpos += (value<median.value?-1:1) * weight / 2;
  78         balance();
  79
  80         int count = size();
  81         if (count>maxSize) {
  82                 coalesce((count+1)/2);
  83         }
  84     }
  85
  86     void balance() {
  87         // Relative Pos - Balance
  88                 while (rpos<0) {
  89                         upper.put(median.value, median);
  90                         median = lower.remove( lower.firstKey() );
  91                         rpos += median.weight;
  92                 }
  93                 while (rpos>=median.weight) {
  94                         rpos -= median.weight;
  95                         lower.put(median.value, median);
  96                         median = upper.remove( upper.firstKey() );
  97                 }
  98
  99     }
 100
 101     public double getMedian() {
 102         if (median==null) return Double.NaN;
 103         return median.value;
 104     }
 105
 106         public int size() {
 107                 return upper.size() + lower.size() + (median==null?0:1);
 108         }
 109
 110         @Override
 111         public String toString() {
 112                 StringBuilder sb = new StringBuilder();
 113                 sb.append( "Median="+getMedian()+" ");
 114
 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());
 119
 120                 while ( !q.isEmpty() ) {
 121                         Item i = q.remove();
 122                         sb.append("(value=");
 123                         sb.append(i.value);
 124                         sb.append(", w=");
 125                         sb.append(i.weight);
 126                         if (i == median) sb.append(", pos="+rpos);
 127                         sb.append(")");
 128                 }
 129
 130                 return sb.toString();
 131         }
 132
 133         /**
 134          * Halves sample count.
 135          * Combines items whose combination causes smallest error.
 136          */
 137         public void coalesce(int targetCount) {
 138                 int count = size();
 139                 if (count<3) return;
 140
 141                 ErrorStack err = new ErrorStack();
 142                 err.start();
 143                 Iterator<Item> itr = lower.values().iterator();
 144                 while (itr.hasNext()) {
 145                         Item item = itr.next();
 146                         err.addItem( item );
 147                 }
 148                 err.addItem( median );
 149                 itr = upper.values().iterator();
 150                 while (itr.hasNext()) {
 151                         Item item = itr.next();
 152                         err.addItem( item );
 153                 }
 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;
 165                                         balance();
 166                                 }
 167                         } else {
 168                                 TreeMap<Double, Item> map = e.itemToMerge.value < median.value ? lower : upper;
 169                                 map.remove(e.mergeToItem.value);
 170                         }
 171                 }
 172         }
 173
 174         @Referable
 175         static public class Item {
 176                 public double weight;
 177                 public double value;
 178                 public Item() {}
 179                 public Item(double weight, double value) {
 180                         this.weight = weight;
 181                         this.value = value;
 182                 }
 183                 @Override
 184                 public String toString() {
 185                         return "(value="+value+", w="+weight+")";
 186                 }
 187         }
 188
 189         class ErrorStack {
 190                 MergeAction[] errs;
 191                 int count;
 192                 int i;
 193                 Item prev;
 194                 void start() {
 195                         count = size();
 196                         errs = new MergeAction[ count - 1 ];
 197                         i = 0;
 198                         prev = null;
 199                 }
 200                 void addItem(Item item) {
 201                         if (prev!=null) {
 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;
 208                                 errs[i++] = e;
 209                         }
 210                         prev = item;
 211                 }
 212                 MergeAction[] finish() {
 213                         MergeErrorComparator c = new MergeErrorComparator();
 214                         c.median = median!=null?median.value:0;
 215                         Arrays.sort(errs, c);
 216                         return errs;
 217                 }
 218         }
 219
 220         static class MergeAction {
 221                 public double error;
 222                 public Item mergeToItem, itemToMerge;
 223         }
 224
 225         /**
 226          * This comparator minimizes error, then maximizes distance to median
 227          */
 228         static class MergeErrorComparator implements Comparator<MergeAction> {
 229                 double median;
 230                 @Override
 231                 public int compare(MergeAction o1, MergeAction o2) {
 232                         double diff = o1.error - o2.error;
 233                         if (diff==0) {
 234                                 double distToMedian1 = o1.mergeToItem.value - median;
 235                                 double distToMedian2 = o2.mergeToItem.value - median;
 236                                 diff = distToMedian1 - distToMedian2;
 237                                 return diff>0?-1:1;
 238                         } else return diff<0?-1:1;
 239                 }
 240         };
 241
 242
 243         static {
 244
 245                 valueComparator = new Comparator<Item>() {
 246                         @Override
 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);
 250                         }
 251                 };
 252
 253                 reverse_double_comparator = new Comparator<Double>() {
 254                         @Override
 255                         public int compare(Double o1, Double o2) {
 256                         Double d1 = (Double) o1;
 257                         Double d2 = (Double) o2;
 258                         double d = d2-d1;
 259                         return d == 0.0 ? 0 : (d<0?-1:1);
 260                     }};
 261
 262                 double_comparator = new Comparator<Double>() {
 263                         @Override
 264                         public int compare(Double o1, Double o2) {
 265                         Double d1 = (Double) o1;
 266                         Double d2 = (Double) o2;
 267                         double d = d1-d2;
 268                         return d == 0.0 ? 0 : (d<0?-1:1);
 269                     }};
 270
 271         }
 272
 273
 274 }