//  $Id: RangeMap.java,v 1.1 2006/05/20 17:02:03 Sasha Buzko Exp $
//
//  Copyright (c) 2000-2002  San Diego Supercomputer Center (SDSC),
//  a facility operated jointly by the University of California,
//  San Diego (UCSD) and General Atomics, San Diego, California, USA.
//
//  Users and possessors of this source code are hereby granted a
//  nonexclusive, royalty-free copyright and design patent license to
//  use this code in individual software.  License is not granted for
//  commercial resale, in whole or in part, without prior written
//  permission from SDSC.  This source is provided "AS IS" without express
//  or implied warranty of any kind.
//
//  For further information, please see:  http://mbt.sdsc.edu
//
//  History:
//  $Log: RangeMap.java,v $
//  Revision 1.1  2006/05/20 17:02:03  Sasha Buzko
//  Updated version
//
//  Revision 1.1  2006/04/30 20:13:59  Sasha Buzko
//  New version of the app
//
//  Revision 1.1  2006/04/15 19:42:26  Sasha Buzko
//  Initial commit
//
//  Revision 1.1  2005/11/13 04:35:07  Administrator
//  *** empty log message ***
//
//  Revision 1.10  2003/10/06 23:41:17  moreland
//  Corrected typo in exception string.
//
//  Revision 1.9  2003/10/03 23:58:40  moreland
//  Added collapseOn flag and get/set methods.
//
//  Revision 1.8  2003/04/28 21:58:34  moreland
//  Added setRangeValue method.
//
//  Revision 1.7  2003/04/25 17:27:07  moreland
//  Moved exhaustive collapse code into a "collapse" method.
//  The "append" method now keeps the last range automatically/cheaply collapsed.
//
//  Revision 1.6  2003/04/24 21:01:55  moreland
//  Added getRange method that returns a COPY of an (int[]) range.
//
//  Revision 1.5  2003/04/24 17:16:25  moreland
//  Added safe range walking methods.
//  Added append and remove methods.
//
//  Revision 1.4  2003/04/24 00:19:59  moreland
//  Removed outdated StructureComponentID references.
//
//  Revision 1.3  2003/04/23 22:56:57  moreland
//  Fixed off-by-one error at the end of the range.
//  Added "text diagrams" to better document the setRange method.
//  Added code to collapse/join ranges after a setRange is performed.
//
//  Revision 1.2  2003/03/19 22:25:23  moreland
//  Moved binary search code out of getValue into new private findRange method.
//  Added public getContiguousValue method to do efficient range value searches.
//
//  Revision 1.1  2003/02/27 21:03:59  moreland
//  First version.
//
//  Revision 1.0  2003/02/12 18:33:20  moreland
//  First implementation/check-in.
//


package edu.sdsc.mbt.util;


import java.util.Hashtable;
import java.util.Vector;


/**
 *  The RangeMap class provides a means to map an integer value
 *  (such as an index) that falls in a fixed range (min and max)
 *  to application-supplied Objects. This can be used to efficiently
 *  associate properties (colors, radii, etc) to a numbered set of objects.
 *  <P>
 *  @author John L. Moreland
 */
public class RangeMap
{
	/**
	 * The minimum value for the spaned range.
	 */
	private int rangeMin = 0;

	/**
	 * The maximum value for the spaned range.
	 */
	private int rangeMax = 0;

	/**
	 *  The sorted range tuple objects (ie: int[2]).
	 */
	private Vector ranges = new Vector( );

	/**
	 *  The value objects keyed by range tuple objects (ie: int[2]).
	 */
	private Hashtable values = new Hashtable( );

	/**
	 *  The transparency changed.
	 */
	private Object defaultValue = null;

	/**
	 *  Flag to enable/disable collapse feature.
	 */
	private boolean collapseOn = true;

	//
	// Constructor.
	//

	/**
	 *  Construct a RangeMap object with the specified min, max, and
	 *  default value.
	 */
	public RangeMap( int min, int max, Object defaultObject )
	{
		reset( min, max, defaultObject );
	}

	//
	// Public RangeMap methods.
	//

	/**
	 *  Get the minimum range index.
	 */
	public int getMin( )
	{
		return rangeMin;
	}

	/**
	 *  Get the maximum range index.
	 */
	public int getMax( )
	{
		return rangeMax;
	}

	/**
	 *  Set flag to enable/disable collapse feature.
	 */
	public void setCollapseOn( boolean state )
	{
		collapseOn = state;
	}

	/**
	 *  Get flag to enable/disable collapse feature.
	 */
	public boolean getCollapseOn( )
	{
		return collapseOn;
	}


	/**
	 *  Assign an object value to the specified range.
	 */
	public void setRange( int start, int stop, Object value )
	{
		// Make sure that the parameters are valid.
		if ( start > stop )
			throw new IllegalArgumentException( "stop must be >= start" );
		if ( start < rangeMin )
			throw new IllegalArgumentException( "start must be >= min" );
		if ( stop > rangeMax )
			throw new IllegalArgumentException( "stop must be <= max" );
		if ( value == null )
			throw new IllegalArgumentException( "value was null" );

		int newRange[] = { start, stop };
		boolean haveAddedNewRange = false;
	/*
		System.err.println( "DEBUG: before setRange of " + newRange[0] + " - " + newRange[1] );
		System.err.print( "   " );
		for ( int i=0; i<ranges.size(); i++ )
		{
			int[] range = (int[]) ranges.elementAt( i );
			System.err.print( range[0] + "-" + range[1] + " , " );
		}
		System.err.println( "" );
	*/

		// Overlay the set of objects spaned by the new range.
		for ( int i=0; i<ranges.size(); i++ )
		{
			int[] range = (int[]) ranges.elementAt( i );

			if ( newRange[1] < range[0] )
			{
				// System.err.println( "JLM DEBUG: APPLY ALGORITHM 1" );

				// The new range falls fully to the left of the current range,
				// so do nothing to the current range (there's no overlap).
				//
				//  |                            |   |                            |
				//  |[0]      newRange        [1]|   |[0]       range          [1]|
				//  ------------------------------   ------------------------------
			}
			else if ( newRange[0] > range[1] )
			{
				// System.err.println( "JLM DEBUG: APPLY ALGORITHM 2" );

				// The new range falls fully to the right of the current range,
				// so do nothing to the current range (there's no overlap).
				//
				//  |                            |   |                            |
				//  |[0]       range          [1]|   |[0]      newRange        [1]|
				//  ------------------------------   ------------------------------
			}
			else if ( (newRange[0] == range[0]) && (newRange[1] == range[1]) )
			{
				// System.err.println( "JLM DEBUG: APPLY ALGORITHM 3" );

				// The new range exactly matches the current range,
				// so simply replace the value object and break.
				//
				//  |                            |
				//  |[0]        range         [1]|
				//  ------------------------------
				//  |                            |
				//  |[0]       newRange       [1]|
				//  ------------------------------

				values.put( range, value );
				break;
			}
			else if ( (newRange[0] > range[0]) && (newRange[1] < range[1]) )
			{
				// System.err.println( "JLM DEBUG: APPLY ALGORITHM 4" );

				// The new range lies completely within the current range,
				// so sub-divide the current range into 3 pieces, and break.
				//
				//  |                                               |
				//  |[0]               range                     [1]|
				//  ------------------------------------------------|
				//           |                            |
				//           |[0]      newRange        [1]|
				//           ------------------------------

				Object oldValue = values.get( range );

				// right piece
				int rightSide[] = { newRange[1]+1, range[1] };
				ranges.add( i+1, rightSide );
				values.put( rightSide, oldValue );

				// middle piece
				ranges.add( i+1, newRange );
				values.put( newRange, value );

				// left piece (original range and value objects)
				range[1] = newRange[0]-1;
				// Its already in the ranges Vector
				// Its already in the values Hashtable

				break;
			}
			else if ( (newRange[0] <= range[0]) && (newRange[1] >= range[1]) )
			{
				// System.err.println( "JLM DEBUG: APPLY ALGORITHM 5" );

				// The new range completely envelopes the current range.
				//
				//           |                            |
				//           |[0]        range         [1]|
				//  |        ------------------------------         |
				//  |[0]               newRange                  [1]|
				//  ------------------------------------------------|

				// Remove the current range/value
				ranges.remove( i );
				values.remove( range );

				// Insert the new range (if it hasn't been already)
				if ( ! haveAddedNewRange )
				{
					haveAddedNewRange = true;
					ranges.add( i, newRange );
					values.put( newRange, value );
				}
				else
				{
					// Since the ranges.remove shifts items left,
					// we need to reprocess the i-th index.
					i--; // It will be incremented to i again by the for loop.
					continue;
				}
			}
			else if ( (newRange[0] > range[0]) && (newRange[0] <= range[1]) && (newRange[1] >= range[1]) )
			{
				// System.err.println( "JLM DEBUG: APPLY ALGORITHM 6" );

				// There's a partial overlap covering inside and up to or
				// past the end of the current range.
				//
				//  |                            |
				//  |[0]        range         [1]|
				//  ------------------------------
				//                |                            |
				//                |[0]       newRange       [1]|
				//                ------------------------------

				// left piece (original range and value objects)
				range[1] = newRange[0]-1;
				// Its already in the ranges Vector
				// Its already in the values Hashtable

				// right piece
				haveAddedNewRange = true;
				ranges.add( i+1, newRange );
				values.put( newRange, value );

				// Don't process the new piece on the next iteration!
				i++;
			}
			else if ( (newRange[0] <= range[0]) && (newRange[1] < range[1]) )
			{
				// System.err.println( "JLM DEBUG: APPLY ALGORITHM 7" );

				// There's a partial overlap extending from a prior range
				// to somehwere inside the current range.
				//
				//                 |                            |
				//                 |[0]        range         [1]|
				//                 ------------------------------
				//  |                            |
				//  |[0]       newRange       [1]|
				//  ------------------------------

				// newRange:
				if ( newRange[0] == range[0] )
				{
					// The new piece starts at the begining of the original range,
					// so we need to insert a new range here.
					// System.err.println( "JLM DEBUG: add( " + i + ", " + value + ")" );
					ranges.add( i, newRange );
					values.put( newRange, value );
				}
				else
				{
					// The newRange should have already been added to the ranges Vector
					// in a prior pass. It should also already in the values Hashtable.
				}
				// right piece (original range and value objects)
				range[0] = newRange[1]+1;

				// We've fully inserted the new range.
				break;
			}
		}

		// Walk through all the ranges and collapse/join ranges
		// where adjacent values are equal.
		// JLM DEBUG: This should probably be custom collapse code
		// so that we only look at neigboring ranges not all ranges...
		collapse( );

	/*
		//
		// Check range consistancy
		//

		System.err.println( "   after setRange, size = " + ranges.size( ) );
		System.err.print( "   " );
		for ( int i=0; i<ranges.size(); i++ )
		{
			int[] range = (int[]) ranges.elementAt( i );
			System.err.print( range[0] + "-" + range[1] + " , " );
		}
		System.err.println( "" );

		// Check both endpoints
		int[] rangeA = (int[]) ranges.elementAt( 0 );
		if ( rangeA[0] != rangeMin )
			throw new IllegalArgumentException(
				"rangeA[0] " + rangeA[0] + " != rangeMin " + rangeMin );
		int[] rangeB = (int[]) ranges.elementAt( ranges.size() - 1 );
		if ( rangeB[1] != rangeMax )
			throw new IllegalArgumentException(
				"rangeA[1] " + rangeA[1] + " != rangeMax " + rangeMax );
		// Check internal ranges
		for ( int i=1; i<ranges.size(); i++ )
		{
			rangeB = (int[]) ranges.elementAt( i );
			if ( (rangeA[1]+1) != rangeB[0] )
			throw new IllegalArgumentException(
				"range " + i + " of " + (ranges.size() - 1) + ", " +
				"rangeA[1] " + rangeA[1] + " missmatch with rangeB[0] " + rangeB[0] );
			rangeA = rangeB;
		}
	*/
	}

	/**
	 * Walk through all the ranges and collapse/join ranges
	 * where adjacent values are equal.
	 */
	private void collapse( )
	{
		if ( ! collapseOn ) return;

		int size = ranges.size();
		if ( size > 1 )
		{
			int prior[] = (int[]) ranges.elementAt( 0 );
			Object priorObj = values.get( prior );
			for ( int i=1; i<size; i++ )
			{
				int current[] = (int[]) ranges.elementAt( i );
				Object currentObj = values.get( current );

				if ( currentObj == priorObj )
				{
					// Same value, so collapse (extend prior and remove current).
					prior[1] = current[1];
					ranges.remove( i );
					values.remove( current );
					size--;
					// Since ranges have shifted, we nee to see the "new" i range.
					i--;
				}
				else
				{
					prior = current;
					priorObj = currentObj;
				}
			}
		}
	}

	/**
	 *  Clear the specified range by setting it to the default value.
	 */
	public void clearRange( int start, int stop )
	{
		setRange( start, stop, defaultValue );
	}

	/**
	 *  Clear the entire RangeMap by setting everything to the default value.
	 */
	public void clearAll( )
	{
		ranges.clear( );
		values.clear( );

		// Add an initial default range and value
		int range[] = { rangeMin, rangeMax };
		ranges.add( range );
		values.put( range, defaultValue );
	}

	/**
	 *  Reset the entire RangeMap by setting new max, min and default values,
	 *  and by clearing all existing ranges.
	 */
	public void reset( int min, int max, Object defaultValue )
	{
		if ( min > max )
			throw new IllegalArgumentException( "min > max" );
		if ( defaultValue == null )
			throw new IllegalArgumentException( "default value was null" );

		rangeMin = min;
		rangeMax = max;
		this.defaultValue = defaultValue;

		clearAll( );
	}

	/**
	 *  Set the default value to a new value.
	 *  Make sure that prior ranges with the default value are updated.
	 */
	public void setDefaultValue( Object newDefault )
	{
		if ( newDefault == defaultValue ) return;
		if ( newDefault == null ) return;

		// Replace the current default values with the new default value
		for ( int i=0; i<ranges.size(); i++ )
		{
			int[] range = (int[]) ranges.elementAt( i );
			Object value = values.get( range );
			if ( value == defaultValue )
				values.put( range, newDefault );
		}
		// Now set the new defaultValue
		defaultValue = newDefault;
	}

	/**
	 *  Find the range element asocciated with the given index.
	 */
	private int findRange( int index )
	{
		if ( index < rangeMin )
			throw new IllegalArgumentException( "index " + index + " < rangeMin " + rangeMin );
		if ( index > rangeMax )
			throw new IllegalArgumentException( "index " + index + " > rangeMax " + rangeMax );

		// Do a binary search to find the range in which the index lives
		int low = 0;
		int high = ranges.size() - 1;
		while ( low <= high )
		{
			int mid = (low + high) / 2;
			int[] range = (int[]) ranges.elementAt( mid );

			// If the index is inside this range, return range index.
			if ( (index >= range[0]) && (index <= range[1]) )
				return mid;
			else if ( index < range[0] )
				high = mid - 1;
			else
				low = mid + 1;
		}

		// We should never get here, since we should always find a value.
//		System.err.println( "index=" + index );
//		System.err.println( "rangeMin=" + rangeMin );
//		System.err.println( "rangeMax=" + rangeMax );
//		System.err.println( "ranges.size=" + ranges.size() );
		for ( int i=0; i<ranges.size(); i++ )
		{
			int[] range = (int[]) ranges.elementAt( i );
//			System.err.println( "range[" + i + "] = " + range[0] + " - " + range[1] );
//			System.err.println( "   value = " + values.get( range ) );
		}
		throw new IllegalArgumentException( "RangeMap.findRange did not find a range!" );
	}

	/**
	 *  Assign an object value to the specified index.
	 */
	public void setValue( int index, Object value )
	{
		setRange( index, index, value );
	}

	/**
	 *  Get the value object asocciated with the given index.
	 */
	public Object getValue( int index )
	{
		if ( index < rangeMin )
			throw new IllegalArgumentException( "index " + index + " < rangeMin " + rangeMin );
		if ( index > rangeMax )
			throw new IllegalArgumentException( "index " + index + " > rangeMax " + rangeMax );

		int rangeIndex = findRange( index );
		int[] range = (int[]) ranges.elementAt( rangeIndex );

		// If the index is inside this range, return the associated value.
		if ( (index >= range[0]) && (index <= range[1]) )
			return values.get( range );

		return null;
	}

	/**
	 *  Get the value object asocciated with the given start and end indexes.
	 *  If a single range does not span the entire start and end indexes, null is returned.
	 *  <P>
	 *  This method is useful for efficiently determining if an entire index range maps
	 *  contiguously (unbroken) to the same value object.
	 *  <P>
	 *  Example, in order to test that a given chain is selected, simply pass the
	 *  chain's start atom index and end atom index to this method. If the chain is
	 *  selected, the return value should be a boolean "True" object. If all atoms
	 *  in the given chain are not all selected, then this method would return null.
	 */
	public Object getContiguousValue( int start_index, int end_index )
	{
		int rangeIndex = findRange( start_index );
		int[] range = (int[]) ranges.elementAt( rangeIndex );
		if ( range == null ) return null;

		if ( (end_index >= range[0]) && (end_index <= range[1]) )
			return values.get( range );

		return null;
	}

	/**
	 *  Get the number of ranges currently assigned to this map.
	 */
	public int getRangeCount( )
	{
		return ranges.size( );
	}

	/**
	 *  Get the value currently associated with the given rangeIndex.
	 */
	public Object getRangeValue( int rangeIndex )
	{
		int[] range = (int[]) ranges.elementAt( rangeIndex );
		return values.get( range );
	}

	/**
	 *  Set the value currently associated with the given rangeIndex.
	 */
	public void setRangeValue( int rangeIndex, Object value )
	{
		if ( value == null )
			throw new IllegalArgumentException( "null value" );
		int[] range = (int[]) ranges.elementAt( rangeIndex );
		values.put( range, value );
	}

	/**
	 *  Get the range currently associated with the given rangeIndex.
	 */
	public int[] getRange( int rangeIndex )
	{
		int[] range = (int[]) ranges.elementAt( rangeIndex );
		// Copy it so the user can't change our copy out from under us!
		int[] result = { range[0], range[1] };
		return result;
	}

	/**
	 *  Get the startIndex for the given rangeIndex.
	 */
	public int getRangeStart( int rangeIndex )
	{
		int[] range = (int[]) ranges.elementAt( rangeIndex );
		return range[0];
	}

	/**
	 *  Get the endIndex for the given rangeIndex.
	 */
	public int getRangeEnd( int rangeIndex )
	{
		int[] range = (int[]) ranges.elementAt( rangeIndex );
		return range[1];
	}

	/**
	 * Append a new value (increasing the range maximum by 1).
	 */
	public void append( Object value )
	{
		if ( value == null )
			throw new IllegalArgumentException( "null value" );

		rangeMax++;

		// If last range value matches the new value, just extend last range.
		// This keeps the last/appended range automatically "collapsed".

		int[] lastRange = (int[]) ranges.elementAt( ranges.size()-1 );
		Object lastValue = values.get( lastRange );
		if ( lastValue == value )
		{
			lastRange[1] += 1;
		}
		else
		{
			int range[] = { rangeMax, rangeMax };
			ranges.add( range );
			values.put( range, value );
		}
	}

	/**
	 * Remove an index (decreasing the range maximum by 1 and causing
	 * all subsequent index values to be decreased by 1).
	 */
	public void remove( int index )
	{
		if ( (index < rangeMin) || (index > rangeMax) )
			throw new IllegalArgumentException( "index out of bounds" );

		int rangeIndex = findRange( index );
		int[] range = (int[]) ranges.elementAt( rangeIndex );
		if ( range[0] == range[1] )
		{
			values.remove( range );
			ranges.remove( rangeIndex );
		}
		else
		{
			range[1] -= 1;
			rangeIndex++;
		}

		// Simply subtract 1 from the remaining range start/end tuples.
		int rangeCount = ranges.size( );
		for ( int r=rangeIndex; r<rangeCount; r++ )
		{
			range = (int[]) ranges.elementAt( r );
			range[0] -= 1;
			range[1] -= 1;
		}

		// JLM DEBUG: This should probably be custom collapse code
		// so that we only look at neigboring ranges not all ranges...
		collapse( );
	}

	// public void insert( index, value );
}