1 /*******************************************************************************
\r
2 * Copyright (c) 2007, 2011 Association for Decentralized Information Management in
\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
10 * VTT Technical Research Centre of Finland - initial API and implementation
\r
11 *******************************************************************************/
\r
12 package org.simantics.history.util;
\r
14 import java.util.Collections;
\r
15 import java.util.Comparator;
\r
16 import java.util.PriorityQueue;
\r
18 public class Median<T> {
\r
20 PriorityQueue<T> upper;
\r
21 PriorityQueue<T> lower;
\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
29 public Median(int length, Comparator<? super T> comparator) {
\r
32 lower = new PriorityQueue<T>( c, comparator);
\r
33 upper = new PriorityQueue<T>( c, Collections.reverseOrder(comparator));
\r
36 public void clear() {
\r
42 public void add(T e) {
\r
43 if (median == null) {
\r
48 int cmp = lower.comparator().compare(e, median);
\r
55 int diff = upper.size() - lower.size();
\r
58 median = upper.remove();
\r
59 } else if (diff < -1) {
\r
61 median = lower.remove();
\r
65 public T getMedian() {
\r
70 return upper.size() + lower.size();
\r
74 * Shrinkages the median by removing from highest and lowest ends
\r
78 public void setSize(int newSize) {
\r
80 if (upper.size()<x) {
\r
83 int y = upper.size() - x;
\r
84 for (int i=0; i<y; i++) {
\r
89 if (lower.size()<x) {
\r
92 int y = lower.size() - x;
\r
93 for (int i=0; i<y; i++) {
\r