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

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