bundles/org.simantics.history/src/org/simantics/history/util/Median.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.Collections;\r
  15 import java.util.Comparator;\r
  16 import java.util.PriorityQueue;\r
  17 \r
  18 public class Median<T> {\r
  19         \r
  20     PriorityQueue<T> upper;\r
  21     PriorityQueue<T> lower;\r
  22     T median;\r
  23 \r
  24     public Median(Comparator<? super T> comparator) {\r
  25         lower = new PriorityQueue<T>(11, comparator);\r
  26         upper = new PriorityQueue<T>(11, Collections.reverseOrder(comparator));\r
  27     }\r
  28 \r
  29     public Median(int length, Comparator<? super T> comparator) {\r
  30         int c = length/2;\r
  31         if (c<3) c = 3;\r
  32         lower = new PriorityQueue<T>( c, comparator);\r
  33         upper = new PriorityQueue<T>( c, Collections.reverseOrder(comparator));\r
  34     }\r
  35     \r
  36     public void clear() {\r
  37         lower.clear();\r
  38         upper.clear();\r
  39         median = null;\r
  40     }\r
  41 \r
  42     public void add(T e) {\r
  43         if (median == null) {\r
  44             median = e;\r
  45             return;\r
  46         }\r
  47         \r
  48         int cmp = lower.comparator().compare(e, median);\r
  49         if (cmp < 0) {\r
  50             upper.add(e);\r
  51         } else {\r
  52             lower.add(e);\r
  53         }\r
  54 \r
  55         int diff = upper.size() - lower.size();\r
  56         if (diff >= 1) {\r
  57             lower.add(median);\r
  58             median = upper.remove();\r
  59         } else if (diff < -1) {\r
  60             upper.add(median);\r
  61             median = lower.remove();\r
  62         }\r
  63     }\r
  64 \r
  65     public T getMedian() {\r
  66         return median;\r
  67     }\r
  68 \r
  69         public int size() {\r
  70                 return upper.size() + lower.size();\r
  71         }\r
  72         \r
  73         /**\r
  74          * Shrinkages the median by removing from highest and lowest ends\r
  75          * \r
  76          * @param newSize\r
  77          */\r
  78         public void setSize(int newSize) {\r
  79                 int x = newSize/2;\r
  80                 if (upper.size()<x) {\r
  81                         upper.clear();\r
  82                 } else {\r
  83                         int y = upper.size() - x;\r
  84                         for (int i=0; i<y; i++) {\r
  85                                 upper.remove();\r
  86                         }\r
  87                 }\r
  88                 \r
  89                 if (lower.size()<x) {\r
  90                         lower.clear();\r
  91                 } else {\r
  92                         int y = lower.size() - x;\r
  93                         for (int i=0; i<y; i++) {\r
  94                                 lower.remove();\r
  95                         }\r
  96                 }\r
  97         }\r
  98         \r
  99         \r
 100         \r
 101     \r
 102 }