bundles/org.simantics.history/src/org/simantics/history/util/WeightedMedian.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 org.simantics.databoard.annotations.Optional;\r
  15 import org.simantics.databoard.annotations.Referable;\r
  16 \r
  17 /**\r
  18  * \r
  19  * @author toni.kalajainen\r
  20  */\r
  21 public class WeightedMedian {\r
  22 \r
  23         public int maxItems;\r
  24         public int itemCount;\r
  25         @Optional public Item median;\r
  26         \r
  27         // Relative pos = pos - median.accumulated weight \r
  28         public double rpos;\r
  29         \r
  30         public WeightedMedian()\r
  31         {\r
  32                 maxItems = Integer.MAX_VALUE;\r
  33         }\r
  34         \r
  35         public WeightedMedian(int maxItems)\r
  36         {\r
  37                 this.maxItems = maxItems;\r
  38         }\r
  39         \r
  40         public void clear() {\r
  41                 itemCount = 0;\r
  42                 median = null;\r
  43                 rpos = 0;\r
  44         }\r
  45         \r
  46         public void add(double weight, double value)\r
  47         {\r
  48                 if (weight<=0) return;\r
  49                 if (median == null) {\r
  50                         median = new Item( weight, value );\r
  51                         itemCount++;\r
  52                         rpos = weight / 2;\r
  53                         return;                 \r
  54                 }\r
  55                 \r
  56                 Item i = median;\r
  57                 while (true) {\r
  58                         \r
  59                         if (i.value==value) {\r
  60                                 i.weight += weight;\r
  61                                 break;\r
  62                         }\r
  63                         \r
  64                         if (value < i.value) {\r
  65                                 \r
  66                                 // i = 1st, add new item as first\r
  67                                 if (i.prev==null) {\r
  68                                         i.prev = new Item( weight, value, null, i );\r
  69                                         itemCount++;\r
  70                                         break;\r
  71                                 }\r
  72                                 \r
  73                                 // value is between two items, add new item\r
  74                                 if (i.prev.value < value) {\r
  75                                         Item n = new Item( weight, value, i.prev, i );\r
  76                                         itemCount++;\r
  77                                         i.prev.next = n;\r
  78                                         i.prev = n;\r
  79                                         break;\r
  80                                 }\r
  81                                 \r
  82                                 i = i.prev;\r
  83                                 continue;\r
  84                         }                       \r
  85                         \r
  86                         if (value > i.value) {\r
  87                                 \r
  88                                 // i = last, add new item as last\r
  89                                 if (i.next==null) {\r
  90                                         i.next = new Item( weight, value, i, null );                                    \r
  91                                         itemCount++;\r
  92                                         break;\r
  93                                 }\r
  94                                 \r
  95                                 // value is between two items, add new item\r
  96                                 if (i.next.value > value) {\r
  97                                         Item n = new Item( weight, value, i, i.next );\r
  98                                         itemCount++;\r
  99                                         i.next.prev = n;\r
 100                                         i.next = n;\r
 101                                         break;\r
 102                                 }\r
 103                                 \r
 104                                 i = i.next;\r
 105                                 continue;\r
 106                         }\r
 107                 }\r
 108 \r
 109                 rpos += (value<median.value?-1:1) * weight / 2;\r
 110                 while (rpos<0) {\r
 111                         median = median.prev;\r
 112                         rpos += median.weight;\r
 113                 }\r
 114                 while (rpos>=median.weight) {\r
 115                         rpos -= median.weight;\r
 116                         median = median.next;\r
 117                 }\r
 118                 \r
 119                 if (itemCount>maxItems) coalesce();\r
 120         }\r
 121         \r
 122         /**\r
 123          */\r
 124         public void coalesce() {\r
 125                 coalesceVerySimple();\r
 126         }\r
 127         \r
 128         /**\r
 129          * Simple coalesce, combine two samples\r
 130          */\r
 131         public void coalesceVerySimple() \r
 132         {\r
 133                 Item i = median.next;\r
 134                 while (i!=null) {\r
 135                         Item n = i.next;\r
 136                         if (n==null) break;\r
 137                         i.next = n.next;\r
 138                         if (n.next!=null) n.next.prev = i;\r
 139                         \r
 140                         Item itemToMerge = n.weight>i.weight ? n : i;\r
 141                         Item mergeToItem = n.weight>i.weight ? i : n;\r
 142                         \r
 143                         double totWeight = mergeToItem.weight+itemToMerge.weight;\r
 144                         //mergeToItem.value = ( mergeToItem.value * mergeToItem.weight + itemToMerge.value * itemToMerge.weight ) / totWeight;\r
 145                         mergeToItem.weight = totWeight;\r
 146                         i = i.next;\r
 147                 }\r
 148                 \r
 149                 i = median.prev;\r
 150                 while (i!=null) {\r
 151                         Item p = i.prev;\r
 152                         if (p==null) break;\r
 153                         i.prev = p.prev;\r
 154                         if (p.prev!=null) p.prev.next = i;\r
 155                         \r
 156                         Item itemToMerge = p.weight>i.weight ? p : i;\r
 157                         Item mergeToItem = p.weight>i.weight ? p : i;\r
 158                         \r
 159                         double totWeight = mergeToItem.weight+itemToMerge.weight;\r
 160                         //mergeToItem.value = ( mergeToItem.value * mergeToItem.weight + itemToMerge.value * itemToMerge.weight ) / totWeight;\r
 161                         mergeToItem.weight = totWeight;\r
 162                         \r
 163                         i.weight = totWeight;\r
 164                         i = i.prev;\r
 165                 }               \r
 166         }\r
 167         \r
 168         public double getMedian() \r
 169         {\r
 170                 if (median==null) return Double.NaN;\r
 171                 return median.value;\r
 172         }\r
 173         \r
 174         @Override\r
 175         public String toString() {\r
 176                 StringBuilder sb = new StringBuilder();\r
 177                 sb.append( "Median="+getMedian()+" ");\r
 178                 \r
 179                 Item i = head();\r
 180                 while (i!=null) {\r
 181                         if (i==median) {\r
 182                                 sb.append("(value="+i.value+", w="+i.weight+", pos="+rpos+")");\r
 183                         } else {\r
 184                                 sb.append("(value="+i.value+", w="+i.weight+")");\r
 185                         }\r
 186                         i = i.next;\r
 187                 }\r
 188                 \r
 189                 return sb.toString();\r
 190         } \r
 191         \r
 192         Item head() {\r
 193                 if (median==null) return null;\r
 194                 Item i = median;\r
 195                 while (i.prev!=null) i = i.prev;\r
 196                 return i;\r
 197         }\r
 198         \r
 199         @Referable\r
 200         static public class Item {\r
 201                 public double weight;\r
 202                 public double value;\r
 203                 \r
 204                 public Item(double weight, double value) {\r
 205                         this.weight = weight;\r
 206                         this.value = value;\r
 207                 }\r
 208 \r
 209                 public Item(double weight, double value, Item prev, Item next) {\r
 210                         this.weight = weight;\r
 211                         this.value = value;\r
 212                         this.prev = prev;\r
 213                         this.next = next;\r
 214                 }\r
 215                 \r
 216                 @Optional\r
 217                 public Item prev;\r
 218                 \r
 219                 @Optional\r
 220                 public Item next;\r
 221                 \r
 222                 @Override\r
 223                 public String toString() {\r
 224                         return "(value="+value+", w="+weight+")";\r
 225                 }\r
 226         }\r
 227         \r
 228 }\r