bundles/org.simantics.history/src/org/simantics/history/util/WeightedMedian2.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 WeightedMedian2 {
  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 WeightedMedian2()
  31         {
  32                 maxItems = Integer.MAX_VALUE;
  33         }
  34
  35         public WeightedMedian2(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 (value>=i.low && value<=i.high) {
  60                                 double totWeight = i.weight+weight;
  61                                 i.value = ( i.value * i.weight + value * weight ) / totWeight;
  62                                 i.weight = totWeight;
  63                                 break;
  64                         }
  65
  66                         if (value < i.low) {
  67
  68                                 // i = 1st, add new item as first
  69                                 if (i.prev==null) {
  70                                         i.prev = new Item( weight, value, null, i );
  71                                         itemCount++;
  72                                         break;
  73                                 }
  74
  75                                 // value is between two items, add new item
  76                                 if (i.prev.high < value) {
  77                                         Item n = new Item( weight, value, i.prev, i );
  78                                         itemCount++;
  79                                         i.prev.next = n;
  80                                         i.prev = n;
  81                                         break;
  82                                 }
  83
  84                                 i = i.prev;
  85                                 continue;
  86                         }
  87
  88                         if (value > i.high) {
  89
  90                                 // i = last, add new item as last
  91                                 if (i.next==null) {
  92                                         i.next = new Item( weight, value, i, null );
  93                                         itemCount++;
  94                                         break;
  95                                 }
  96
  97                                 // value is between two items, add new item
  98                                 if (i.next.low > value) {
  99                                         Item n = new Item( weight, value, i, i.next );
 100                                         itemCount++;
 101                                         i.next.prev = n;
 102                                         i.next = n;
 103                                         break;
 104                                 }
 105
 106                                 i = i.next;
 107                                 continue;
 108                         }
 109                 }
 110
 111                 rpos += (value<median.low?-1:1) * weight / 2;
 112                 while (rpos<0) {
 113                         median = median.prev;
 114                         rpos += median.weight;
 115                 }
 116                 while (rpos>=median.weight) {
 117                         rpos -= median.weight;
 118                         median = median.next;
 119                 }
 120
 121                 if (itemCount>maxItems) coalesce();
 122         }
 123
 124         public void coalesce()
 125         {
 126                 Item i = median.next;
 127                 while (i!=null) {
 128                         Item n = i.next;
 129                         if (n==null) break;
 130                         i.next = n.next;
 131                         if (n.next!=null) n.next.prev = i;
 132                         double totWeight = i.weight+n.weight;
 133                         i.high = n.high;
 134                         i.value = ( i.value * i.weight + n.value * n.weight ) / totWeight;
 135                         i.weight = totWeight;
 136                         i = i.next;
 137                 }
 138
 139                 i = median.prev;
 140                 while (i!=null) {
 141                         Item p = i.prev;
 142                         if (p==null) break;
 143                         i.prev = p.prev;
 144                         if (p.prev!=null) p.prev.next = i;
 145                         double totWeight = i.weight+p.weight;
 146                         i.low = p.low;
 147                         i.value = ( i.value * i.weight + p.value * p.weight ) / totWeight;
 148                         i.weight = totWeight;
 149                         i = i.prev;
 150                 }
 151         }
 152
 153         public double getMedian()
 154         {
 155                 if (median==null) return Double.NaN;
 156                 if (median.low == median.high) return median.value;
 157                 double d = median.high - median.low;
 158                 double r = rpos/median.weight;
 159                 return median.low + d*r;
 160         }
 161
 162         @Override
 163         public String toString() {
 164                 StringBuilder sb = new StringBuilder();
 165                 sb.append( "Median="+getMedian()+" ");
 166
 167                 Item i = first();
 168                 while (i!=null) {
 169                         sb.append("(");
 170                         sb.append("value=");
 171                         if (i.low==i.high) sb.append(i.value); else
 172                                 sb.append(i.value+" ("+i.low+".."+i.high+")");
 173                         sb.append(", w="+i.weight);
 174                         if (i==median) {
 175                                 sb.append(", pos="+rpos);
 176                         }
 177                         sb.append(")");
 178                         i = i.next;
 179                 }
 180
 181                 return sb.toString();
 182         }
 183
 184         Item first() {
 185                 if (median==null) return null;
 186                 Item i = median;
 187                 while (i.prev!=null) i = i.prev;
 188                 return i;
 189         }
 190
 191         @Referable
 192         static public class Item {
 193                 public double weight;
 194                 public double low;
 195                 public double high;
 196                 public double value;
 197
 198                 public Item() {}
 199
 200                 public Item(double weight, double value) {
 201                         this.weight = weight;
 202                         this.low = this.high = value;
 203                 }
 204
 205                 public Item(double weight, double value, Item prev, Item next) {
 206                         this.weight = weight;
 207                         this.value = this.low = this.high = value;
 208                         this.prev = prev;
 209                         this.next = next;
 210                 }
 211
 212                 @Optional
 213                 public Item prev;
 214
 215                 @Optional
 216                 public Item next;
 217
 218                 @Override
 219                 public String toString() {
 220                         if (low==high) return "(value="+value+", w="+weight+")";
 221                         return "(value="+value+" ("+low+".."+high+"), w="+weight+")";
 222                 }
 223         }
 224
 225 }