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