/*
* Copyright (c) 2010 Nokia Corporation and/or its subsidiary(-ies).
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* - Redistributions of source code must retain the above copyright notice,
*   this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright notice,
*   this list of conditions and the following disclaimer in the documentation
*   and/or other materials provided with the distribution.
* - Neither the name of Nokia Corporation nor the names of its contributors
*   may be used to endorse or promote products derived from this software
*   without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
* 
* Initial Contributors:
* Nokia Corporation - initial contribution.
*
* Contributors:
*
* Description: 
*
*/

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using HeapLib.Cells;
using SymbianUtils.Collections;

namespace HeapLib.Array
{
	public class HeapCellArray : HeapCellArrayBase
	{
		#region Constructors & destructor
		public HeapCellArray()
            : this( 100 )
		{
		}

		public HeapCellArray( int aGranularity )
		{
            iComparer = new HeapCellComparerByAddress();
            iSortedList = new SortedList<uint, HeapCell>();
            iFlatList = new List<HeapCell>( aGranularity );
		}

		public HeapCellArray( HeapCellArray aCopy )
            : this( aCopy.Count + 1 )
		{
			foreach( HeapCell cell in aCopy )
			{
				Add( cell );
			}
		}
		#endregion

		#region API
        public override void Clear()
        {
            iFlatList.Clear();
            iSortedList.Clear();
        }

        public override void Add( HeapCell aCell )
        {
            uint address = aCell.Address;
            //
            iSortedList.Add( address, aCell );
            //
            int insertPos = iFlatList.BinarySearch( aCell, iComparer );
            System.Diagnostics.Debug.Assert( insertPos < 0 );
            insertPos = ~insertPos;
            iFlatList.Insert( insertPos, aCell );
        }

        public override void Remove( HeapCell aCell )
        {
            uint address = aCell.Address;
            if ( iSortedList.ContainsKey( address ) )
            {
                HeapCell c = iSortedList[ address ];
                iSortedList.Remove( address );
                iFlatList.Remove( c );
            }
        }

        public override int CellIndex( HeapCell aCell )
		{
            int ret = -1;
            //
            uint address = aCell.Address;
            int pos = iFlatList.BinarySearch( aCell, iComparer );
            if ( pos >= 0 )
            {
                ret = pos;
            }
            //
			return ret;
		}

        public override HeapCell CellByAddress( uint aAddress, out int aIndex )
        {
            HeapCell ret = null;

            // If we're using an address-based comparer, we can optimise the lookup.
            // Otherwise, we have to fall back to the slow iterative base class algorithm.
            if ( iComparer is HeapCellComparerByAddress )
            {
                HeapCell temp = new HeapCell( aAddress, 0, HeapCell.TType.EAllocated );
                aIndex = iFlatList.BinarySearch( temp, iComparer );
                if ( aIndex < 0 )
                {
                    // There wasn't an exact match, so the binary search algorithm returns
                    // us the next largest entry - or in other words, the insertion point
                    // if we were about to insert a new cell into the list.
                    //
                    // Because we want to locate the cell that contains the specified
                    // address value, then most likely it's the prior cell.
                    aIndex = ~aIndex - 1;
                }
                if ( aIndex >= 0 && aIndex < iFlatList.Count )
                {
                    ret = iFlatList[ aIndex ];
                }
                else
                {
                    aIndex = -1;
                }
            }
            else
            {
                ret = base.CellByAddress( aAddress, out aIndex );
            }
            //
            return ret;
        }
      
        public override HeapCell CellByExactAddress( uint aAddress, out int aIndex )
        {
            aIndex = -1;
            HeapCell ret = null;
            iSortedList.TryGetValue( aAddress, out ret );
            if ( ret != null )
            {
                aIndex = CellIndex( ret );
            }
            return ret;
        }
        #endregion

		#region Properties
		public override int Count
		{
            get { return iFlatList.Count; }
		}

        public override HeapCell this[ int aIndex ]
		{
            get
            {
                HeapCell ret = iFlatList[ aIndex ];
                return ret;
            }
		}
		#endregion

        #region Sorting
        public void SortByAddress()
        {
            IComparer<HeapCell> comparer = new HeapCellComparerByAddress();
            Sort( comparer );
        }

        public void SortByType()
        {
            IComparer<HeapCell> comparer = new HeapCellComparerByType();
            Sort( comparer );
        }

        public void SortByLength()
        {
            IComparer<HeapCell> comparer = new HeapCellComparerByLength();
            Sort( comparer );
        }
        #endregion

        #region Internal methods
        private void Sort( IComparer<HeapCell> aComparer )
        {
            iComparer = aComparer;
            iFlatList.Sort( iComparer );
        }
        #endregion

		#region Data members
        private IComparer<HeapCell> iComparer = null;
        private List<HeapCell> iFlatList = new List<HeapCell>();
        private SortedList<uint, HeapCell> iSortedList = new SortedList<uint, HeapCell>();
		#endregion
	}
}