/*
 * Created on Jul 6, 2007
 * Created by Paul Gardner
 * Copyright (C) 2007 Aelitis, All Rights Reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 * 
 * AELITIS, SAS au capital de 63.529,40 euros
 * 8 Allee Lenotre, La Grille Royale, 78600 Le Mesnil le Roi, France.
 *
 */

package com.aelitis.azureus.core.speedmanager.impl;

import java.io.File;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Random;

import org.gudy.azureus2.core3.util.Debug;
import org.gudy.azureus2.core3.util.DisplayFormatters;
import org.gudy.azureus2.core3.util.FileUtil;
import org.gudy.azureus2.core3.util.IndentWriter;
import org.gudy.azureus2.core3.util.SystemTime;

import com.aelitis.azureus.core.speedmanager.SpeedManagerLimitEstimate;
import com.aelitis.azureus.core.speedmanager.SpeedManagerPingMapper;
import com.aelitis.azureus.core.speedmanager.SpeedManagerPingZone;

class
SpeedManagerPingMapperImpl
	implements SpeedManagerPingMapper
{
	static final int VARIANCE_GOOD_VALUE		= 50;
	static final int VARIANCE_BAD_VALUE			= 150;
	static final int VARIANCE_MAX				= VARIANCE_BAD_VALUE*10;
	
	static final int RTT_BAD_MIN				= 350;
	static final int RTT_BAD_MAX				= 500;
	
	static final int RTT_MAX					= 30*1000;

		// don't make this too large as we don't start considering capacity decreases until this
		// is full
	
	static final int MAX_BAD_LIMIT_HISTORY		= 16;
	
	static final int SPEED_DIVISOR = 256;
	
	private static final int SPEED_HISTORY_PERIOD	= 3*60*1000; // 3 min
	private static final int SPEED_HISTORY_COUNT	= SPEED_HISTORY_PERIOD / SpeedManagerImpl.UPDATE_PERIOD_MILLIS;
		
	private SpeedManagerImpl	speed_manager;
	private String				name;
	private boolean				variance;
	private boolean				trans;
			
	private int	ping_count;
	
	private pingValue[]	pings;
	private int			max_pings;
	
	private pingValue	prev_ping;
	
	private int[]		x_speeds = new int[ SPEED_HISTORY_COUNT ];
	private int[]		y_speeds = new int[ SPEED_HISTORY_COUNT ];
	
	private int speeds_next;
	
	private LinkedList	regions;
		
	private int last_x;
	private int	last_y;
	
	private int[]	recent_metrics = new int[3];
	private int		recent_metrics_next;
	
	private limitEstimate	up_estimate;
	private limitEstimate	down_estimate;
	
	private LinkedList	last_bad_ups;
	private LinkedList	last_bad_downs;
	
	private static final int BAD_PROGRESS_COUNTDOWN	= 5;
	
	private limitEstimate	last_bad_up;
	private int				bad_up_in_progress_count;
	
	private limitEstimate	last_bad_down;
	private int				bad_down_in_progress_count;

	private limitEstimate	best_good_up;
	private limitEstimate	best_good_down;
	
	private limitEstimate	up_capacity		= getNullLimit();
	private limitEstimate	down_capacity	= getNullLimit();
	
	private File	history_file;
	
	protected
	SpeedManagerPingMapperImpl(
		SpeedManagerImpl		_speed_manager,
		String					_name,
		int						_entries ,
		boolean					_variance,
		boolean					_transient )
	{
		speed_manager	= _speed_manager;
		name			= _name;
		max_pings		= _entries;
		variance		= _variance;
		trans			= _transient;	
		
		init();
	}
	
	protected void
	init()
	{
		pings		= new pingValue[max_pings];
		ping_count	= 0;
		
		regions	= new LinkedList();
		
		up_estimate		= getNullLimit();
		down_estimate	= getNullLimit();

		last_bad_ups		= new LinkedList();
		last_bad_downs		= new LinkedList();
		
		last_bad_up					= null;
		bad_up_in_progress_count	= 0;
		
		last_bad_down				= null;
		bad_down_in_progress_count	= 0;
		
		best_good_up 	= null;
		best_good_down	= null;
		
		up_capacity 	= getNullLimit();
		down_capacity 	= getNullLimit();

		prev_ping 			= null;
		recent_metrics_next	= 0;
	}
	
	protected synchronized void
	loadHistory(
		File		file )
	{
		try{
			if ( history_file != null && history_file.equals( file )){
				
				return;
			}
			
			if ( history_file != null ){
				
				saveHistory();
			}
			
			history_file = file;

			init();
			
			if ( history_file.exists()){
							
				Map map = FileUtil.readResilientFile( history_file );
				
				List	p = (List)map.get( "pings" );
				
				if ( p != null ){
					
					for (int i=0;i<p.size();i++){
						
						Map	m = (Map)p.get(i);
						
						int	x 		= ((Long)m.get( "x" )).intValue();
						int	y 		= ((Long)m.get( "y" )).intValue();
						int	metric 	= ((Long)m.get( "m" )).intValue();
						
						if ( i == 0 ){
							
							last_x	= 0;
							last_y	= 0;						
						}
						
						if ( variance ){
							
							if ( metric > VARIANCE_MAX ){
						
								metric = VARIANCE_MAX;
							}
						}else{
							
							if ( metric > RTT_MAX ){
								
								metric = RTT_MAX;
							}						
						}
						
						addPingSupport( x, y, -1, metric );
					}
				}
								
				last_bad_ups 	= loadLimits( map, "lbus" );
				last_bad_downs 	= loadLimits( map, "lbds" );
				
				if ( last_bad_ups.size() > 0 ){
					
					last_bad_up	= (limitEstimate)last_bad_ups.get(last_bad_ups.size()-1);
				}
				
				if ( last_bad_downs.size() > 0 ){
					
					last_bad_down	= (limitEstimate)last_bad_downs.get(last_bad_downs.size()-1);
				}

				best_good_up	= loadLimit((Map)map.get( "bgu" ));
				best_good_down	= loadLimit((Map)map.get( "bgd" ));
				
				up_capacity 	= loadLimit((Map)map.get( "upcap" ));
				down_capacity 	= loadLimit((Map)map.get( "downcap" ));
				
				log( "Loaded " + ping_count + " entries from " + history_file + ": bad_up=" + getLimitString(last_bad_ups) + ", bad_down=" + getLimitString(last_bad_downs));
			}
		
			prev_ping 			= null;
			recent_metrics_next	= 0;
			
			updateLimitEstimates();	
				
		}catch( Throwable e ){
			
			Debug.printStackTrace(e);
		}
	}
	
	protected synchronized void
	saveHistory()
	{
		try{
			if ( history_file == null ){
				
				return;
			}
			
			Map	map = new HashMap();
			
			List p = new ArrayList(ping_count);
			
				// NOTE: add to this you will need to modify the "reset" method appropriately
			
			map.put( "pings", p );
			
			for (int i=0;i<ping_count;i++){
				
				pingValue ping = pings[i];
				
				Map	m = new HashMap();
				
				p.add( m );
				
				m.put( "x", new Long(ping.getX()));
				m.put( "y", new Long(ping.getY()));
				m.put( "m", new Long(ping.getMetric()));
			}
			
			saveLimits( map, "lbus", last_bad_ups );
			saveLimits( map, "lbds", last_bad_downs );

			if ( best_good_up != null ){
				
				map.put( "bgu", saveLimit( best_good_up ));
			}
			
			if ( best_good_down != null ){
				
				map.put( "bgd", saveLimit( best_good_down ));
			}

			map.put( "upcap", 	saveLimit( up_capacity ));
			map.put( "downcap", saveLimit( down_capacity ));

			FileUtil.writeResilientFile( history_file, map );
			
			log( "Saved " + p.size() + " entries to " + history_file );
		
		}catch( Throwable e ){
			
			Debug.printStackTrace(e);
		}
	}
	
	protected LinkedList
	loadLimits(
		Map		map,
		String	name )
	{
		LinkedList	result = new LinkedList();
		
		List	l = (List)map.get(name);
		
		if ( l != null ){
			
			for (int i=0;i<l.size();i++){
				
				Map m = (Map)l.get(i);
							
				result. add(loadLimit( m ));
			}
		}
		
		return( result );
	}
	
	protected limitEstimate
	loadLimit(
		Map	m )
	{
		if ( m == null ){
			
			return( getNullLimit());
		}
		
		int	speed = ((Long)m.get( "s" )).intValue();
		
		double	metric = Double.parseDouble( new String((byte[])m.get("m")));
		
		int	hits = ((Long)m.get( "h" )).intValue();

		long	when = ((Long)m.get("w")).longValue();
		
		byte[]	t_bytes = (byte[])m.get("t");
		
		double type = t_bytes==null?SpeedManagerLimitEstimate.TYPE_ESTIMATED :Double.parseDouble( new String( t_bytes ));
		
		return( new limitEstimate( speed, type, metric, hits, when, new int[0][] ));
	}
	
	protected void
	saveLimits(
		Map				map,
		String			name,
		List			limits )
	{
		List	l = new ArrayList();
		
		for (int i=0;i<limits.size();i++){
			
			limitEstimate limit = (limitEstimate)limits.get(i);
			
			Map	m = saveLimit( limit );
			
			l.add( m );
		}
		
		map.put( name, l );
	}
	
	protected Map
	saveLimit(
		limitEstimate	limit )
	{
		if ( limit == null ){
			
			limit = getNullLimit();
		}
		
		Map	m = new HashMap();
		
		m.put( "s", new Long( limit.getBytesPerSec()));
		
		m.put( "m", String.valueOf( limit.getMetricRating()));
		
		m.put( "t", String.valueOf( limit.getEstimateType()));
		
		m.put( "h", new Long( limit.getHits()));
		
		m.put( "w", new Long( limit.getWhen()));	
		
		return( m );
	}
	
	public boolean
	isActive()
	{
		return( variance );
	}
	
	protected limitEstimate
	getNullLimit()
	{
		return( new limitEstimate( 0, SpeedManagerLimitEstimate.TYPE_UNKNOWN, 0, 0, 0, new int[0][] ));
	}
	
	protected String
	getLimitString(
		List	limits )
	{
		String	str = "";
		
		for (int i=0;i<limits.size();i++){
	
			str += (i==0?"":",") + ((limitEstimate)limits.get(i)).getString();
		}
		
		return( str );
	}
	
	protected void
	log(
		String	str )
	{
		if ( speed_manager != null ){
		
			speed_manager.log( str );
		}
	}
	
	public String
	getName()
	{
		return( name );
	}
	
	protected synchronized void
	addSpeed(
		int		x,
		int		y )
	{
		x = x/SPEED_DIVISOR;
		y = y/SPEED_DIVISOR;
		
		if ( x > 65535 )x = 65535;
		if ( y > 65535 )y = 65535;

		addSpeedSupport( x, y );
	}
	
	protected synchronized void
	addSpeedSupport(
		int		x,
		int		y )
	{
		x_speeds[speeds_next] = x;
		y_speeds[speeds_next] = y;
				
		speeds_next = (speeds_next+1)%SPEED_HISTORY_COUNT;
		
		int	min_x	= Integer.MAX_VALUE;
		int	min_y	= Integer.MAX_VALUE;
		
		for (int i=0;i<SPEED_HISTORY_COUNT;i++){
			
			min_x = Math.min( min_x, x_speeds[i] );
			min_y = Math.min( min_y, y_speeds[i] );
		}
		
		min_x *= SPEED_DIVISOR;
		min_y *= SPEED_DIVISOR;
				
		if ( up_capacity.getEstimateType() != SpeedManagerLimitEstimate.TYPE_MANUAL){
			
			if ( min_x > up_capacity.getBytesPerSec()){
				
				up_capacity.setBytesPerSec( min_x );
				
				up_capacity.setMetricRating( 0 );
				
				up_capacity.setEstimateType( SpeedManagerLimitEstimate.TYPE_ESTIMATED);
				
				speed_manager.informUpCapChanged();
			}
		}
		
		if ( down_capacity.getEstimateType() != SpeedManagerLimitEstimate.TYPE_MANUAL){
			
			if ( min_y > down_capacity.getBytesPerSec()){
				
				down_capacity.setBytesPerSec( min_y );
				
				down_capacity.setMetricRating( 0 );
				
				down_capacity.setEstimateType( SpeedManagerLimitEstimate.TYPE_ESTIMATED);

				speed_manager.informDownCapChanged();
			}
		}
	}
	
	protected synchronized void
	addPing(
		int		x,
		int		y,
		int		rtt,
		boolean	re_base )
	{
		x = x/SPEED_DIVISOR;
		y = y/SPEED_DIVISOR;
		
		if ( x > 65535 )x = 65535;
		if ( y > 65535 )y = 65535;
		if ( rtt > 65535 )rtt = variance?VARIANCE_MAX:RTT_MAX;
		if ( rtt == 0 )rtt = 1;
		
			// ping time won't refer to current x+y due to latencies, apply to average between
			// current and previous
				
		int	average_x = (x + last_x )/2;
		int	average_y = (y + last_y )/2;
		
		last_x	= x;
		last_y	= y;
		
		x	= average_x;
		y	= average_y;
		
		int	metric;
		
		if ( variance ){
			
			if ( re_base ){
				
				log( "Re-based variance" );
				
				recent_metrics_next = 0;
			}

			recent_metrics[recent_metrics_next++%recent_metrics.length] = rtt;
			
			int var_metric = 0;
			int rtt_metric = 0;

			if ( recent_metrics_next > 1 ){
				
				int	entries = Math.min( recent_metrics_next, recent_metrics.length );
				
				int total = 0;
				
				for (int i=0;i<entries;i++){
					
					total += recent_metrics[i];
				}
				
				int	average = total/entries;
				
				int	total_deviation = 0;
				
				for (int i=0;i<entries;i++){

					int	deviation = recent_metrics[i] - average;
					
					total_deviation += deviation * deviation;
				}
				
					// we deliberately don't divide by num samples as this accentuates larger deviations
				
				var_metric = (int)Math.sqrt( total_deviation );
				
					// variance is a useful measure. however, under some conditions, in particular high
					// download speeds, we get elevated ping times with little variance
					// factor this in
				
				if ( entries == recent_metrics.length ){
					
					int	total_rtt = 0;
					
					for (int i=0;i<entries;i++){

						total_rtt += recent_metrics[i];
					}
					
					int	average_rtt = total_rtt / recent_metrics.length;
					
					if ( average_rtt >= RTT_BAD_MAX ){
						
						rtt_metric = VARIANCE_BAD_VALUE;
						
					}else if ( average_rtt > RTT_BAD_MIN ){
						
						int	rtt_diff 	= RTT_BAD_MAX - RTT_BAD_MIN;
						int	rtt_base	= average_rtt - RTT_BAD_MIN;
						
						rtt_metric = VARIANCE_GOOD_VALUE + (( VARIANCE_BAD_VALUE - VARIANCE_GOOD_VALUE ) * rtt_base ) / rtt_diff;
					}
				}
			}
						
			metric = Math.max( var_metric, rtt_metric );
			
			if ( metric < VARIANCE_BAD_VALUE ){
				
				addSpeedSupport( x, y );
				
			}else{
				
				addSpeedSupport( 0, 0 );
			}
		}else{
			
			metric = rtt;
		}
		
		region new_region = addPingSupport( x, y, rtt, metric );
		
		updateLimitEstimates();
		
		if ( variance ){
		
			String up_e 	= getShortString( getEstimatedUploadLimit( false )) + "," + 
								getShortString(getEstimatedUploadLimit( true )) + "," +
								getShortString(getEstimatedUploadCapacityBytesPerSec());
			
			String down_e 	= getShortString(getEstimatedDownloadLimit( false )) + "," + 
								getShortString(getEstimatedDownloadLimit( true )) + "," +
								getShortString(getEstimatedDownloadCapacityBytesPerSec());
			
			log( "Ping: rtt="+rtt+",x="+x+",y="+y+",m="+metric + 
					(new_region==null?"":(",region=" + new_region.getString())) + 
					",mr=" + getCurrentMetricRating() + 
					",up=[" + up_e + (best_good_up==null?"":(":"+getShortString(best_good_up))) + 
						"],down=[" + down_e + (best_good_down==null?"":(":"+getShortString(best_good_down))) + "]" +
					",bu="+getLimitStr(last_bad_ups,true)+",bd="+getLimitStr(last_bad_downs,true));
		}
	}
	
	protected region
	addPingSupport(
		int		x,
		int		y,
		int		rtt,
		int		metric )
	{
		if ( ping_count == pings.length ){

				// discard oldest pings and reset 
							
			int	to_discard = pings.length/10;
			
			if ( to_discard < 3 ){
				
				to_discard = 3;
			}
			
			ping_count = pings.length - to_discard;

			System.arraycopy(pings, to_discard, pings, 0, ping_count);
			
			for (int i=0;i<to_discard;i++ ){
				
				regions.removeFirst();
			}
		}
				
		pingValue	ping = new pingValue( x, y, metric );

		pings[ping_count++] = ping;
		
		region	new_region = null;
		
		if ( prev_ping != null ){
			
			new_region = new region(prev_ping,ping);
			
			regions.add( new_region );
		}
		
		prev_ping = ping;

		return( new_region );
	}
	
	public synchronized int[][]
	getHistory()
	{
		int[][]	result = new int[ping_count][];

		for (int i=0;i<ping_count;i++){
			
			pingValue	ping = pings[i];
			
			result[i] = new int[]{ SPEED_DIVISOR*ping.getX(), SPEED_DIVISOR*ping.getY(), ping.getMetric()};
		}
		
		return( result );
	}
	
	public synchronized SpeedManagerPingZone[]
	getZones()
	{
		return((SpeedManagerPingZone[])regions.toArray( new SpeedManagerPingZone[regions.size()] ));
	}
	
	public synchronized SpeedManagerLimitEstimate
	getEstimatedUploadLimit(
		boolean	persistent )
	{
		return( adjustForPersistence( up_estimate, best_good_up, last_bad_up, persistent ));
	}
	
	public synchronized SpeedManagerLimitEstimate
	getEstimatedDownloadLimit(
		boolean	persistent )
	{
		return( adjustForPersistence( down_estimate, best_good_down, last_bad_down, persistent ));
	}

	public SpeedManagerLimitEstimate
	getLastBadUploadLimit()
	{
		return( last_bad_up );
	}
	
	public SpeedManagerLimitEstimate
	getLastBadDownloadLimit()
	{
		return( last_bad_down );
	}
	
	public synchronized SpeedManagerLimitEstimate[]
	getBadUploadHistory()
	{
		return((SpeedManagerLimitEstimate[])last_bad_ups.toArray(new SpeedManagerLimitEstimate[last_bad_ups.size()]));
	}

	public synchronized SpeedManagerLimitEstimate[]
	getBadDownloadHistory()
	{
		return((SpeedManagerLimitEstimate[])last_bad_downs.toArray(new SpeedManagerLimitEstimate[last_bad_downs.size()]));	
	}
	                             	
	protected SpeedManagerLimitEstimate
	adjustForPersistence(
		limitEstimate		estimate,
		limitEstimate		best_good,	
		limitEstimate		last_bad,	
		boolean				persistent )
	{
		if ( estimate == null ){
			
			return( null );
		}
		
		if ( persistent ){
			
				// if result is bad then we return this
			
			if ( estimate.getMetricRating() == -1 ){
				
				return( estimate );
			}
			
				// see if best good/last bad are relevant
			
			limitEstimate	persistent_limit = null;
			
			if ( best_good != null && last_bad != null ){
				
				if ( last_bad.getWhen() > best_good.getWhen()){
					
					persistent_limit = last_bad;
					
				}else{
					
					if ( best_good.getBytesPerSec() > last_bad.getBytesPerSec()){
						
						persistent_limit = best_good;
						
					}else{
						
						persistent_limit = last_bad;
					}
				}
			}else if ( best_good != null ){
				
				persistent_limit = best_good;
				
			}else if ( last_bad != null ){
				
				persistent_limit = last_bad;
			}
			
			if ( persistent_limit == null ){
				
				return( estimate );
			}

			if ( estimate.getBytesPerSec() > persistent_limit.getBytesPerSec()){
				
				return( estimate );
				
			}else{
									
				// need to convert this into a good rating to correspond to the 
				// actual estimate type we have
					
				limitEstimate res = estimate.getClone();
				
				res.setBytesPerSec(persistent_limit.getBytesPerSec());

				return( res );
			}
		}else{
			
			return( estimate );
		}
	}
		
	protected void
	updateLimitEstimates()
	{
		double cm = getCurrentMetricRating();
		
		up_estimate 	= getEstimatedLimit( true );
				
		if ( up_estimate != null ){
			
			double metric = up_estimate.getMetricRating();
			
			if ( metric == -1 ){
			
				if ( bad_up_in_progress_count == 0 ){
					
						// don't count the duplicates we naturally get when sitting here with a bad limit
						// and nothing going on to change this situation
					
					if ( last_bad_up == null || last_bad_up.getBytesPerSec() != up_estimate.getBytesPerSec()){
						
						bad_up_in_progress_count = BAD_PROGRESS_COUNTDOWN;
						
						last_bad_ups.addLast( up_estimate );
						
						if ( last_bad_ups.size() > MAX_BAD_LIMIT_HISTORY ){
							
							last_bad_ups.removeFirst();
						}
						
						checkCapacityDecrease( true, up_capacity, last_bad_ups );
					}
				}
								
				last_bad_up = up_estimate;
				
			}else if ( metric == 1 ){
				
				if ( best_good_up == null ){
					
					best_good_up = up_estimate;
					
				}else{
					
					if ( best_good_up.getBytesPerSec() < up_estimate.getBytesPerSec()){
						
						best_good_up = up_estimate;
					}
				}
			}
			
			if ( bad_up_in_progress_count > 0 ){
				
				if ( cm == -1 ){ 
					
					bad_up_in_progress_count = BAD_PROGRESS_COUNTDOWN;
					
				}else if ( cm == 1 ){
				
					bad_up_in_progress_count--;
				}
			}
		}
	
		
		down_estimate 	= getEstimatedLimit( false );
				
		if ( down_estimate != null ){
			
			double metric = down_estimate.getMetricRating();
			
			if ( metric == -1 ){
			
				if ( bad_down_in_progress_count == 0 ){
					
					if ( last_bad_down == null || last_bad_down.getBytesPerSec() != down_estimate.getBytesPerSec()){

						bad_down_in_progress_count = BAD_PROGRESS_COUNTDOWN;

						last_bad_downs.addLast( down_estimate );
						
						if ( last_bad_downs.size() > MAX_BAD_LIMIT_HISTORY ){
							
							last_bad_downs.removeFirst();
						}
						
						checkCapacityDecrease( false, down_capacity, last_bad_downs );
					}
				}
								
				last_bad_down = down_estimate;
				
			}else if ( metric == 1 ){
				
				if ( best_good_down == null ){
					
					best_good_down = down_estimate;
					
				}else{
					
					if ( best_good_down.getBytesPerSec() < down_estimate.getBytesPerSec()){
						
						best_good_down = down_estimate;
					}
				}
			}
			
			if ( bad_down_in_progress_count > 0 ){
				
				if ( cm == -1 ){ 
			
					bad_down_in_progress_count = BAD_PROGRESS_COUNTDOWN;
					
				}else if ( cm == 1 ){
				
					bad_down_in_progress_count--;
				}
			}
		}
	}
	
	protected void
	checkCapacityDecrease(
		boolean			is_up,
		limitEstimate	capacity,
		LinkedList		bads )
	{
		if ( capacity.getEstimateType() == SpeedManagerLimitEstimate.TYPE_MANUAL){
			
			return;
		}
		
		if ( bads.size() < MAX_BAD_LIMIT_HISTORY ){
			
			return;
		}
		
			// remeber, 0 means UNLIMITED!!!
		
		int	cap = capacity.getBytesPerSec();
		
			// sanity check
		
		if ( cap > 0 && cap < 10*1024 ){
		
			return;
		}
		
		List b = new ArrayList( bads );
		
		Collections.sort(
			b,
			new Comparator()
			{
				public int 
				compare(
					Object o1, 
					Object o2 )
				{
					limitEstimate	l1 = (limitEstimate)o1;
					limitEstimate	l2 = (limitEstimate)o2;
					
					return( l1.getBytesPerSec() - l2.getBytesPerSec());
				}
			});
		
			// drop top bottom quarter of measurements
		
		int	start 	= MAX_BAD_LIMIT_HISTORY/4;
		int	end		= MAX_BAD_LIMIT_HISTORY - start;
		
		int	total 	= 0;
		int	num		= 0;
		
		for (int i=start;i<end;i++){
		
			int	s = ((limitEstimate)b.get(i)).getBytesPerSec();
			
			total += s;
			
			num++;
		}
		
		int	average = total/num;
		
			// only consider decreases!
		
		if ( cap > 0 && average >= cap ){
			
			log( "Not reducing " + (is_up?"up":"down") + " capacity - average=" + DisplayFormatters.formatByteCountToKiBEtcPerSec( average ) + ",capacity=" + DisplayFormatters.formatByteCountToKiBEtcPerSec( cap ));

			return;
		}
		
		int	total_deviation = 0;
		
		for (int i=start;i<end;i++){
			
			int	s = ((limitEstimate)b.get(i)).getBytesPerSec();

			int	deviation = s - average;
			
			total_deviation += deviation * deviation;
		}
		
		int	deviation = (int)Math.sqrt( total_deviation / num );
		
			// adjust if deviation within 50% of capacity
		
		if ( cap <= 0 || ( deviation < cap/2 && average < cap )){
			
			log( "Reducing " + (is_up?"up":"down") + " capacity from " + cap + " to " + average + " due to frequent lower chokes (deviation=" + DisplayFormatters.formatByteCountToKiBEtcPerSec(deviation) + ")" );
			
			capacity.setBytesPerSec( average );
			
			capacity.setEstimateType( SpeedManagerLimitEstimate.TYPE_CHOKE_ESTIMATED);

				// remove the last 1/4 bad stats so we don't reconsider adjusting until more data collected
			
			for (int i=0;i<start;i++){
				
				bads.removeFirst();
			}
		}else{
			
			log( "Not reducing " + (is_up?"up":"down") + " capacity - deviation=" + DisplayFormatters.formatByteCountToKiBEtcPerSec( deviation ) + ",capacity=" + DisplayFormatters.formatByteCountToKiBEtcPerSec( cap ));

		}
	}
	
	protected synchronized limitEstimate
	getEstimatedLimit(
		boolean		up )
	{
		if ( !variance ){
			
			return( getNullLimit() );
		}
		
		int	num_samples = regions.size();
		
		if ( num_samples == 0 ){
			
			return( getNullLimit());
		}
		
		Iterator	it = regions.iterator();
		
		int	max_end = 0;
		
		while( it.hasNext()){
			
			region r = (region)it.next();
			
			int	end		= (up?r.getUploadEndBytesPerSec():r.getDownloadEndBytesPerSec())/SPEED_DIVISOR;
			
			if ( end > max_end ){
				
				max_end = end;
			}
		}
						
		int	sample_end = max_end + 1;
		
		int[]	totals 			= new int[sample_end];
		short[]	hits			= new short[sample_end];				
		short[]	worst_var_type	= new short[sample_end];
											
		ListIterator sample_it = regions.listIterator( 0 );
			
			// flatten out all observations into a single munged metric

		while( sample_it.hasNext()){
			
			region r = (region)sample_it.next();
		
			int	start 	= (up?r.getUploadStartBytesPerSec():r.getDownloadStartBytesPerSec())/SPEED_DIVISOR;
			int	end		= (up?r.getUploadEndBytesPerSec():r.getDownloadEndBytesPerSec())/SPEED_DIVISOR;
			int	metric	= r.getMetric();
		
			int	weighted_start;
			int	weighted_end;
			
			short	this_var_type;
			
			if ( metric < VARIANCE_GOOD_VALUE ){
			
					// a good variance applies to all speeds up to this one. This means
					// that previously occuring bad variance will get flattened out by
					// subsequent good variance
				
				weighted_start 	= 0;	
				weighted_end	= end;
				this_var_type 	= 0;
				
			}else if ( metric < VARIANCE_BAD_VALUE ){
				
					// medium values, treat at face value
				
				weighted_start 	= start;
				weighted_end	= end;
				this_var_type	= VARIANCE_GOOD_VALUE;

			}else{
				
					// bad ones, treat at face value
				
				weighted_start 	= start;
				weighted_end	= max_end;
				this_var_type	= VARIANCE_BAD_VALUE;
			}
			
			for (int j=weighted_start;j<=weighted_end;j++){
			
					// a bad variance resets totals as we have encountered this after (in time)
					// the existing data and this is more relevant and replaces any feel good
					// factor we might have accumulated via prior observations
				
				if ( this_var_type == VARIANCE_BAD_VALUE && worst_var_type[j] <= this_var_type ){
					
					totals[j]	= 0;
					hits[j]		= 0;
					
					worst_var_type[j] = this_var_type;
				}
				
				totals[j] += metric;
				hits[j]++;
			}
		}

			// now average out values based on history computed above
						
		for (int i=0;i<sample_end;i++){
			
			int	hit = hits[i];
			
			if ( hit > 0 ){
				
				int	average = totals[i]/hit;
				
				totals[i] = average;
				
				if ( average < VARIANCE_GOOD_VALUE ){

					worst_var_type[i] = 0;
				
				}else if ( average < VARIANCE_BAD_VALUE ){
				
					worst_var_type[i] = VARIANCE_GOOD_VALUE;

				}else{
					
					worst_var_type[i] = VARIANCE_BAD_VALUE;
				}
			}
		}
			
			// break history up into segments of same speed 
		
		int	last_average 			= -1;
		int	last_average_change		= 0;
		int last_average_worst_var	= 0;
		int	last_max_hits			= 0;
		
		int	worst_var	= 0;
		
		List segments = new ArrayList(totals.length);
		
		for (int i=0;i<sample_end;i++){
			
			int var		= worst_var_type[i];
			int	hit 	= hits[i];
			
			if ( var > worst_var ){
				
				worst_var = var;
			}
			
			int average = totals[i];
			
			if ( i == 0 ){
				
				last_average = average;
				
			}else if ( last_average != average ){
				
				segments.add( new int[]{ last_average, last_average_change*SPEED_DIVISOR, (i-1)*SPEED_DIVISOR, last_average_worst_var, last_max_hits });
				
				last_average 			= average;
				last_average_change		= i;
				last_average_worst_var	= var;
				last_max_hits			= hit;
			}else{
				
				last_average_worst_var 	= Math.max( var, last_average_worst_var );
				last_max_hits			= Math.max( hit, last_max_hits );
			}
		}
		
		if ( last_average_change != sample_end - 1 ){
		
			segments.add( new int[]{ last_average, last_average_change*SPEED_DIVISOR, (sample_end-1)*SPEED_DIVISOR, last_average_worst_var, last_max_hits });
		}
		
		int[]	estimate_seg 	= null;
		
		int estimate_var	= 0;

			// take smallest bad value and largest good
		
		if ( worst_var == VARIANCE_BAD_VALUE ){
			
			for (int i=segments.size()-1;i>=0;i-- ){
						
				int[]	seg = (int[])segments.get(i);
				
				int	var = seg[3];
				
				if ( var >= worst_var ){
						
					estimate_seg 	= seg;
					estimate_var	= var;
				}
			}
		}else{
			for (int i=0;i<segments.size();i++){
			
				int[]	seg = (int[])segments.get(i);
			
				int	var = seg[3];
			
				if ( var >= worst_var ){
				
					estimate_seg 	= seg;
					estimate_var	= var;
				}
			}
		}
		
		int	estimate_speed;
		int	estimate_hits;
		
		if ( estimate_seg == null ){
			
			estimate_speed 	= -1;
			estimate_hits	= 0;

		}else{
			
			estimate_speed 	= -1;
			
			if ( worst_var == 0 ){
				
				estimate_speed = estimate_seg[2];
				
			}else if ( worst_var == VARIANCE_GOOD_VALUE ){
				
				estimate_speed = ( estimate_seg[1] + estimate_seg[2])/2;

			}else{
				
				estimate_speed = estimate_seg[1];
			}
			
			estimate_hits = estimate_seg[4];
		}
		
			// override any estimates < 5K to be OK ones as there's little point in recording negative
			// values lower than this
		
		if ( estimate_speed < 5*1024 ){
			
			estimate_var = VARIANCE_GOOD_VALUE;
			
				// value of 0 means unlimited
			
			if ( estimate_speed <= 0 ){
				
				estimate_speed = 1;
			}
		}
		
		limitEstimate result = 
			new limitEstimate(
					estimate_speed,
					SpeedManagerLimitEstimate.TYPE_ESTIMATED,
					convertMetricToRating( estimate_var ),
					estimate_hits, 
					SystemTime.getCurrentTime(),
					(int[][])segments.toArray(new int[segments.size()][]));
		
		return( result );
	}
	
	public synchronized double
	getCurrentMetricRating()
	{
		if ( ping_count == 0 ){
			
			return( 0 );
		}
		
		int	latest_metric = pings[ping_count-1].getMetric();
		
		if ( variance ){
			
			return( convertMetricToRating( latest_metric ));
			
		}else{
		
			return( 0 );
		}
	}
	
	public SpeedManagerLimitEstimate
	getEstimatedUploadCapacityBytesPerSec()
	{
		return( up_capacity );
	}
	
	public void
	setEstimatedDownloadCapacityBytesPerSec(
		int		bytes_per_sec,
		float	estimate_type )
	{
		if ( down_capacity.getBytesPerSec() != bytes_per_sec || down_capacity.getEstimateType() != estimate_type ){
			
			down_capacity.setBytesPerSec( bytes_per_sec );
			down_capacity.setEstimateType( estimate_type );
			
			speed_manager.informDownCapChanged();
		}
	}
	
	public SpeedManagerLimitEstimate
	getEstimatedDownloadCapacityBytesPerSec()
	{
		return( down_capacity );
	}
	
	public void
	setEstimatedUploadCapacityBytesPerSec(
		int		bytes_per_sec,
		float	estimate_type )
	{
		if ( up_capacity.getBytesPerSec() != bytes_per_sec || up_capacity.getEstimateType() != estimate_type ){

			up_capacity.setBytesPerSec( bytes_per_sec );
			up_capacity.setEstimateType( estimate_type );
			
			speed_manager.informUpCapChanged();
		}
	}
	
	protected synchronized void
	reset()
	{
		setEstimatedDownloadCapacityBytesPerSec( 0, SpeedManagerLimitEstimate.TYPE_UNKNOWN);
		setEstimatedUploadCapacityBytesPerSec( 0, SpeedManagerLimitEstimate.TYPE_UNKNOWN);
		
		ping_count	= 0;
		regions.clear();
		
		last_bad_down	= null;
		last_bad_downs.clear();
		
		last_bad_up		= null;
		last_bad_ups.clear();
		
		saveHistory();
	}
	
	protected double
	convertMetricToRating(
		int		metric )
	{
		if ( metric < VARIANCE_GOOD_VALUE ){
			
			return( +1 );
			
		}else if ( metric >= VARIANCE_BAD_VALUE ){
			
			return( -1 );
			
		}else{
			
			double val =  1 - ((double)metric - VARIANCE_GOOD_VALUE )/50;
			
				// sanitize
			
			if ( val < -1 ){
				
				val = -1;
				
			}else if ( val > 1 ){
				
				val = 1;
			}
			
			return( val );
		}
	}
	
	protected String
	getLimitStr(
		List	limits,
		boolean	short_form )
	{
		String	str = "";
		
		if ( limits != null ){
			
			Iterator	it = limits.iterator();
			
			while( it.hasNext()){
				
				str += (str.length()==0?"":",");
				
				limitEstimate	l = (limitEstimate)it.next();
				
				if ( short_form ){
					str += getShortString( l );
				}else{
					str += l.getString();
				}
			}
		}
		
		return( str );
	}
	
	protected String
	getShortString(
		SpeedManagerLimitEstimate l )
	{
		return( DisplayFormatters.formatByteCountToKiBEtcPerSec( l.getBytesPerSec()));
	}
	
	protected void 
	generateEvidence(
		IndentWriter writer ) 
	{
		writer.println( "up_cap=" + up_capacity.getString());
		writer.println( "down_cap=" + down_capacity.getString());
				
		writer.println( "bad_up=" + getLimitStr( last_bad_ups, false ));			
		writer.println( "bad_down=" + getLimitStr( last_bad_downs, false ));
		
		if ( best_good_up != null ){
			writer.println( "best_up=" + best_good_up.getString());
		}
		if ( best_good_down != null ){
			writer.println( "best_down=" + best_good_down.getString());
		}
	}
	
	public void
	destroy()
	{
		if ( trans ){
			
			speed_manager.destroy( this );
			
		}else{
	
			Debug.out( "Attempt to destroy non-transient mapper!" );
		}
	}
	
	class
	pingValue
	{
		private short	x;
		private short	y;
		private short	metric;
		
		protected
		pingValue(
			int		_x,
			int		_y,
			int		_m )
		{
			x		= (short)_x;
			y		= (short)_y;
			metric	= (short)_m;
		}
		
		protected int
		getX()
		{
			return(((int)(x))&0xffff );
		}
		
		protected int
		getY()
		{
			return(((int)(y))&0xffff );
		}
		
		protected int
		getMetric()
		{
			return(((int)(metric))&0xffff );
		}
		
		protected String
		getString()
		{
			return("x=" + getX()+",y=" + getY() +",m=" + getMetric());
		}
	}

	class
	region
		implements SpeedManagerPingZone
	{
		private short	x1;
		private short	y1;
		private short	x2;
		private short	y2;
		private short	metric;
		
		protected
		region(
			pingValue		p1,
			pingValue		p2 )
		{
			x1 = (short)p1.getX();
			y1 = (short)p1.getY();
			x2 = (short)p2.getX();
			y2 = (short)p2.getY();
			
			if ( x2 < x1 ){
				short t = x1;
				x1 = x2;
				x2 = t;
			}
			if ( y2 < y1 ){
				short t = y1;
				y1 = y2;
				y2 = t;
			}
			metric = (short)((p1.getMetric()+p2.getMetric())/2);
		}
		
		public int
		getX1()
		{
			return( x1 & 0x0000ffff );
		}
		
		public int
		getY1()
		{
			return( y1 & 0x0000ffff );
		}
		
		public int
		getX2()
		{
			return( x2 & 0x0000ffff );
		}
		
		public int
		getY2()
		{
			return( y2 & 0x0000ffff );
		}
					
		public int
		getUploadStartBytesPerSec()
		{
			return( getX1()*SPEED_DIVISOR );
		}
		
		public int
		getUploadEndBytesPerSec()
		{
			return( getX2()*SPEED_DIVISOR + (SPEED_DIVISOR-1));
		}
		
		public int
		getDownloadStartBytesPerSec()
		{
			return( getY1()*SPEED_DIVISOR );
		}
		
		public int
		getDownloadEndBytesPerSec()
		{
			return( getY2()*SPEED_DIVISOR + (SPEED_DIVISOR-1));
		}
		
		public int
		getMetric()
		{
			return( metric & 0x0000ffff );

		}
					
		public String
		getString()
		{				
			return( "x="+getX1() + ",y="+getY1()+",w=" + (getX2()-getX1()+1) +",h=" + (getY2()-getY1()+1));
		}
	}
	
	class
	limitEstimate
		implements SpeedManagerLimitEstimate, Cloneable
	{
		private int		speed;
		private float	estimate_type;
		private float	metric_rating;
		private long	when;
		private int		hits;
		
		private int[][]	segs;
		
		protected
		limitEstimate(
			int			_speed,
			double		_estimate_type,
			double		_metric_rating,
			int			_hits,
			long		_when,
			int[][]		_segs )
		{
			speed				= _speed;
			estimate_type		= (float)_estimate_type;
			metric_rating		= (float)_metric_rating;
			hits				= _hits;
			when				= _when;
			segs				= _segs;
			
				// sanitize
			
			if ( metric_rating < -1 ){
				
				metric_rating = -1;
				
			}else if ( metric_rating > 1 ){
				
				metric_rating = 1;
			}
		}
		
		public int
		getBytesPerSec()
		{
			return( speed );
		}
		
		protected void
		setBytesPerSec(
			int		s )
		{
			speed	= s;
		}
		
		public float
		getEstimateType()
		{
			return( estimate_type );
		}
		
		public void
		setEstimateType(
			float	et )
		{
			estimate_type = et;
		}
		
		public float
		getMetricRating()
		{
			return( metric_rating );
		}
		
		protected void
		setMetricRating(
			float	mr )
		{
			metric_rating	= mr;
		}
		
		public int[][]
		getSegments()
		{
			return( segs );
		}
		
		protected int
		getHits()
		{
			return( hits );
		}
		
		protected long
		getWhen()
		{
			return( when );
		}
		
		public limitEstimate
		getClone()
		{
			try{
				return((limitEstimate)clone());
				
			}catch( Throwable e ){
								
				return( null );
			}
		}
		
		public String
		getString()
		{
			return( "speed=" + DisplayFormatters.formatByteCountToKiBEtc( speed )+
					",metric=" + metric_rating + ",segs=" + segs.length + ",hits=" + hits + ",when=" + when );
		}
	}
	
	
	public static void
	main(
		String[]	args )
	{
		SpeedManagerPingMapperImpl pm = new SpeedManagerPingMapperImpl( null, "test", 100, true, false );
		
		Random rand = new Random();
		
		int[][] phases = { 
				{ 50, 0, 100000, 50 },
				{ 50, 100000, 200000, 200 },
				{ 50, 50000, 50000, 200 },
				{ 50, 0, 100000, 50 },

		};
		
		for (int i=0;i<phases.length;i++){
			
			int[]	phase = phases[i];
			
			System.out.println( "**** phase " + i );
			
			for (int j=0;j<phase[0];j++){
			
				int	x_base 	= phase[1];
				int	x_var	= phase[2];
				int r = phase[3];
				
				pm.addPing( x_base + rand.nextInt( x_var ), x_base + rand.nextInt( x_var ), rand.nextInt( r ), false);
			
				SpeedManagerLimitEstimate up 	= pm.getEstimatedUploadLimit( false );
				SpeedManagerLimitEstimate down 	= pm.getEstimatedDownloadLimit( false );
				
				if ( up != null && down != null ){
					
					System.out.println( up.getString() + "," + down.getString());
				}
			}
		}
	}
}