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