/*******************************************************************************
 * Copyright (c) 2007, 2011 Association for Decentralized Information Management in
 * Industry THTH ry.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     VTT Technical Research Centre of Finland - initial API and implementation
 *******************************************************************************/
package org.simantics.history.util;

import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Median<T> {
	
    PriorityQueue<T> upper;
    PriorityQueue<T> lower;
    T median;

    public Median(Comparator<? super T> comparator) {
        lower = new PriorityQueue<T>(11, comparator);
        upper = new PriorityQueue<T>(11, Collections.reverseOrder(comparator));
    }

    public Median(int length, Comparator<? super T> comparator) {
    	int c = length/2;
    	if (c<3) c = 3;
        lower = new PriorityQueue<T>( c, comparator);
        upper = new PriorityQueue<T>( c, Collections.reverseOrder(comparator));
    }
    
    public void clear() {
    	lower.clear();
    	upper.clear();
    	median = null;
    }

    public void add(T e) {
        if (median == null) {
            median = e;
            return;
        }
        
        int cmp = lower.comparator().compare(e, median);
        if (cmp < 0) {
            upper.add(e);
        } else {
            lower.add(e);
        }

        int diff = upper.size() - lower.size();
        if (diff >= 1) {
            lower.add(median);
            median = upper.remove();
        } else if (diff < -1) {
            upper.add(median);
            median = lower.remove();
        }
    }

    public T getMedian() {
        return median;
    }

	public int size() {
		return upper.size() + lower.size();
	}
	
	/**
	 * Shrinkages the median by removing from highest and lowest ends
	 * 
	 * @param newSize
	 */
	public void setSize(int newSize) {
		int x = newSize/2;
		if (upper.size()<x) {
			upper.clear();
		} else {
			int y = upper.size() - x;
			for (int i=0; i<y; i++) {
				upper.remove();
			}
		}
		
		if (lower.size()<x) {
			lower.clear();
		} else {
			int y = lower.size() - x;
			for (int i=0; i<y; i++) {
				lower.remove();
			}
		}
	}
	
	
	
    
}