/*******************************************************************************
 * 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 org.simantics.databoard.annotations.Optional;
import org.simantics.databoard.annotations.Referable;

/**
 * 
 * @author toni.kalajainen
 */
public class WeightedMedian2 {

	public int maxItems;
	public int itemCount;
	@Optional public Item median;
	
	// Relative pos = pos - median.accumulated weight 
	public double rpos;
	
	public WeightedMedian2()
	{
		maxItems = Integer.MAX_VALUE;
	}
	
	public WeightedMedian2(int maxItems)
	{
		this.maxItems = maxItems;
	}
	
	public void clear() {
		itemCount = 0;
		median = null;
		rpos = 0;
	}
	
	public void add(double weight, double value)
	{
		if (weight<=0) return;
		if (median == null) {
			median = new Item( weight, value );
			itemCount++;
			rpos = weight / 2;
			return;			
		}
		
		Item i = median;
		while (true) {
			
			if (value>=i.low && value<=i.high) {
				double totWeight = i.weight+weight;
				i.value = ( i.value * i.weight + value * weight ) / totWeight;
				i.weight = totWeight;
				break;
			}
			
			if (value < i.low) {
				
				// i = 1st, add new item as first
				if (i.prev==null) {
					i.prev = new Item( weight, value, null, i );
					itemCount++;
					break;
				}
				
				// value is between two items, add new item
				if (i.prev.high < value) {
					Item n = new Item( weight, value, i.prev, i );
					itemCount++;
					i.prev.next = n;
					i.prev = n;
					break;
				}
				
				i = i.prev;
				continue;
			}			
			
			if (value > i.high) {
				
				// i = last, add new item as last
				if (i.next==null) {
					i.next = new Item( weight, value, i, null );					
					itemCount++;
					break;
				}
				
				// value is between two items, add new item
				if (i.next.low > value) {
					Item n = new Item( weight, value, i, i.next );
					itemCount++;
					i.next.prev = n;
					i.next = n;
					break;
				}
				
				i = i.next;
				continue;
			}
		}

		rpos += (value<median.low?-1:1) * weight / 2;
		while (rpos<0) {
			median = median.prev;
			rpos += median.weight;
		}
		while (rpos>=median.weight) {
			rpos -= median.weight;
			median = median.next;
		}
		
		if (itemCount>maxItems) coalesce();
	}
	
	public void coalesce() 
	{
		Item i = median.next;
		while (i!=null) {
			Item n = i.next;
			if (n==null) break;
			i.next = n.next;
			if (n.next!=null) n.next.prev = i;
			double totWeight = i.weight+n.weight;
			i.high = n.high;
			i.value = ( i.value * i.weight + n.value * n.weight ) / totWeight;
			i.weight = totWeight;
			i = i.next;
		}
		
		i = median.prev;
		while (i!=null) {
			Item p = i.prev;
			if (p==null) break;
			i.prev = p.prev;
			if (p.prev!=null) p.prev.next = i;
			double totWeight = i.weight+p.weight;
			i.low = p.low;
			i.value = ( i.value * i.weight + p.value * p.weight ) / totWeight;
			i.weight = totWeight;
			i = i.prev;
		}		
	}
	
	public double getMedian() 
	{
		if (median==null) return Double.NaN;
		if (median.low == median.high) return median.value;
		double d = median.high - median.low;
		double r = rpos/median.weight;
		return median.low + d*r;
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append( "Median="+getMedian()+" ");
		
		Item i = first();
		while (i!=null) {
			sb.append("(");
			sb.append("value=");
			if (i.low==i.high) sb.append(i.value); else 
				sb.append(i.value+" ("+i.low+".."+i.high+")");
			sb.append(", w="+i.weight);
			if (i==median) {
				sb.append(", pos="+rpos);
			}
			sb.append(")");
			i = i.next;
		}
		
		return sb.toString();
	} 
	
	Item first() {
		if (median==null) return null;
		Item i = median;
		while (i.prev!=null) i = i.prev;
		return i;
	}
	
	@Referable
	static public class Item {
		public double weight;
		public double low;
		public double high;
		public double value;
		
		public Item() {}
		
		public Item(double weight, double value) {
			this.weight = weight;
			this.low = this.high = value;
		}

		public Item(double weight, double value, Item prev, Item next) {
			this.weight = weight;
			this.value = this.low = this.high = value;
			this.prev = prev;
			this.next = next;
		}
		
		@Optional
		public Item prev;
		
		@Optional
		public Item next;
		
		@Override
		public String toString() {
			if (low==high) return "(value="+value+", w="+weight+")";
			return "(value="+value+" ("+low+".."+high+"), w="+weight+")";
		}
	}
	
}