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