mono/mcs/class/System.Data/System.Data.Common/Index.cs

//
// System.Data.Common.Key.cs
//
// Author:
//   Boris Kirzner  <[email protected]>
//   Konstantin Triger ([email protected])
//

/*
  * Copyright (c) 2002-2004 Mainsoft Corporation.
  *
  * Permission is hereby granted, free of charge, to any person obtaining a
  * copy of this software and associated documentation files (the "Software"),
  * to deal in the Software without restriction, including without limitation
  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  * and/or sell copies of the Software, and to permit persons to whom the
  * Software is furnished to do so, subject to the following conditions:
  *
  * The above copyright notice and this permission notice shall be included in
  * all copies or substantial portions of the Software.
  *
  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  * DEALINGS IN THE SOFTWARE.
  */

using System;
using System.Collections;

using System.Text;

namespace System.Data.Common
{
	enum IndexDuplicatesState { Unknown, True, False }; 
	/// <summary>
	/// Summary description for Index.
	/// </summary>
	internal class Index
	{
		#region Fields

		int[] _array;
		int _size;
		Key _key;
		int _refCount = 0;
		IndexDuplicatesState _hasDuplicates;

		#endregion // Fields

		#region Constructors

		internal Index(Key key)
		{
			_key = key;
			Reset();
		}

		#endregion // Constructors

		#region Properties

		internal Key Key 
		{
			get {
				return _key;
			}
		}

		internal int Size
		{
			get {
				EnsureArray();
				return _size;
			}
		}

		internal int RefCount
		{
			get {
				return _refCount;
			}
		}

		internal int IndexToRecord(int index){
			return index < 0 ? index : Array[index];
		}

		private int[] Array
		{
			get {
				EnsureArray();
				return _array;
			}
		}

		internal bool HasDuplicates
		{
			get {
				if (_array == null || _hasDuplicates == IndexDuplicatesState.Unknown) {
					EnsureArray();
					if (_hasDuplicates == IndexDuplicatesState.Unknown) {
						// check for duplicates
						_hasDuplicates = IndexDuplicatesState.False;
						for(int i = 0; i < Size - 1; i++) {
							if (Key.CompareRecords(Array[i],Array[i+1]) == 0) {
								_hasDuplicates = IndexDuplicatesState.True;
								break;
							}
						}
					}
				}
				return (_hasDuplicates == IndexDuplicatesState.True);
			}
		}

		#endregion // Properties

		#region Methods

		internal int[] Duplicates {
			get {
				if (!HasDuplicates)
					return null;

				ArrayList dups = new ArrayList();

				bool inRange = false;
				for(int i = 0; i < Size - 1; i++) {
					if (Key.CompareRecords(Array[i],Array[i+1]) == 0){
						if (!inRange) {
							dups.Add(Array[i]);
							inRange = true;
						}

						dups.Add(Array[i+1]);
					}
					else
						inRange = false;
				}

				return (int[])dups.ToArray(typeof(int));
			}
		}

		private void EnsureArray()
		{
			if (_array == null) {
				RebuildIndex();
			}
		}

		internal int[] GetAll()
		{
			return Array;
		}

		internal void Reset()
		{
			_array = null;
			RebuildIndex();
		}

		private void RebuildIndex()
		{
			// consider better capacity approximation
			_array = new int[Key.Table.RecordCache.CurrentCapacity];
			_size = 0;
			foreach(DataRow row in Key.Table.Rows) {
				int record = Key.GetRecord(row);
				if (record != -1) {
					_array[_size++] = record;
				}
			}
			_hasDuplicates = IndexDuplicatesState.False;
			// Note : MergeSort may update hasDuplicates to True
			Sort();
		}

		private void Sort()
		{
			//QuickSort(Array,0,Size-1);
			MergeSort(Array,Size);
		}
		
		/*
		 * Returns record number of the record equal to the key values supplied 
		 * in the meaning of index key, or -1 if no equal record found.
		 */
		internal int Find(object[] keys)
		{
			int index = FindIndex(keys);
			return IndexToRecord(index);
		}

		/*
		 * Returns record index (location) of the record equal to the key values supplied 
		 * in the meaning of index key, or -1 if no equal record found.
		 */
		internal int FindIndex(object[] keys)
		{
			if (keys == null || keys.Length != Key.Columns.Length) {
				throw new ArgumentException("Expecting " + Key.Columns.Length + " value(s) for the key being indexed, " +
					"but received " + ((keys == null) ? 0 : keys.Length) + " value(s).");
			}

			int tmp = Key.Table.RecordCache.NewRecord();
			try {
				// init key values for temporal record
				for(int i = 0; i < Key.Columns.Length; i++) {
					Key.Columns[i].DataContainer[tmp] = keys[i];
				}
				return FindIndex(tmp);
			}
//			catch(FormatException) {
//				return -1;
//			}
//			catch(InvalidCastException) {
//				return -1;
//			}
			finally {
				Key.Table.RecordCache.DisposeRecord(tmp);
			}
		}

		/*
		 * Returns record number of the record equal to the record supplied 
		 * in the meaning of index key, or -1 if no equal record found.
		 */
		internal int Find(int record)
		{
			int index = FindIndex(record);
			return IndexToRecord(index);
		}

		/*
		 * Returns array of record numbers of the records equal equal to the key values supplied 
		 * in the meaning of index key, or -1 if no equal record found.
		 */
		internal int[] FindAll(object[] keys)
		{
			int[] indexes = FindAllIndexes(keys);
			IndexesToRecords(indexes);
			return indexes;
		}

		/*
		 * Returns array of indexes of the records inside the index equal equal to the key values supplied 
		 * in the meaning of index key, or -1 if no equal record found.
		 */
		internal int[] FindAllIndexes(object[] keys)
		{
			if (keys == null || keys.Length != Key.Columns.Length) {
				throw new ArgumentException("Expecting " + Key.Columns.Length + " value(s) for the key being indexed," +
					"but received " + ((keys == null) ? 0 : keys.Length) + " value(s).");
			}

			int tmp = Key.Table.RecordCache.NewRecord();
			try {
				// init key values for temporal record
				for(int i = 0; i < Key.Columns.Length; i++) {
					Key.Columns[i].DataContainer[tmp] = keys[i];
				}
				return FindAllIndexes(tmp);
			}
			catch(FormatException) {
				return new int[0];
			}
			catch(InvalidCastException) {
				return new int[0];
			}
			finally {
				Key.Table.RecordCache.DisposeRecord(tmp);
			}
		}

		/*
		 * Returns array of record numbers of the records equal to the record supplied 
		 * in the meaning of index key, or empty list if no equal records found.
		 */
		internal int[] FindAll(int record)
		{
			int[] indexes = FindAllIndexes(record);
            IndexesToRecords(indexes);
			return indexes;
		}

		/*
		 * Returns array of indexes of the records inside the index that equal to the record supplied 
		 * in the meaning of index key, or empty list if no equal records found.
		 */
		internal int[] FindAllIndexes(int record)
		{
			int index = FindIndex(record);

			if (index == -1) {
				return new int[0];
			}

			int startIndex = index++;
			int endIndex = index;
			
			for(;startIndex >= 0 && Key.CompareRecords(Array[startIndex],record) == 0;startIndex--);
			for(;endIndex < Size && Key.CompareRecords(Array[endIndex],record) == 0;endIndex++);
			
			int length = endIndex - startIndex - 1;
			int[] indexes = new int[length];
			
			for(int i = 0; i < length; i++) {
				indexes[i] = ++startIndex;
			}
			
			return indexes;
		}

		/*
		 * Returns index inside the array where record number of the record equal to the record supplied 
		 * in the meaning of index key is sored, or -1 if no equal record found.
		 */
		private int FindIndex(int record)
		{
			if (Size == 0) {
				return -1;
			}
			return BinarySearch(Array,0,Size - 1,record);
		}

		/*
		 * Finds exact location of the record specified
		 */ 
		private int FindIndexExact(int record)
		{
			for (int i = 0, size = Size; i < size; i++)
				if (Array[i] == record)
					return i;

			return -1;
		}

		/*
		 * Returns array of records from the indexes (locations) inside the index
		 */
		private void IndexesToRecords(int[] indexes)
		{
			for(int i = 0; i < indexes.Length; i++) {
				indexes[i] = Array[indexes[i]];
			}
		}

		internal void Delete(DataRow row)
		{
			int oldRecord = Key.GetRecord(row);

			Delete(oldRecord);
		}

		internal void Delete(int oldRecord)
		{
			if (oldRecord == -1)
				return;

			int index = FindIndexExact(oldRecord);
			if (index != -1) {
				if ((_hasDuplicates == IndexDuplicatesState.True)) {
					int c1 = 1;
					int c2 = 1;

					if (index > 0) {
						c1 = Key.CompareRecords(Array[index - 1],oldRecord);
					}
					if (index < Size - 1) {
						c2 = Key.CompareRecords(Array[index + 1],oldRecord);
					}

					if (c1 == 0 ^ c2 == 0) {
						_hasDuplicates = IndexDuplicatesState.Unknown;
					}
				}
				Remove(index);
			}
		}

		private void Remove(int index)
		{
			if (Size > 1) {
				System.Array.Copy(Array,index+1,Array,index,Size - index - 1);
			}
			_size--;
		}


		internal void Update(DataRow row,int oldRecord, DataRowVersion oldVersion, DataRowState oldState)
		{			
			bool contains = Key.ContainsVersion (oldState, oldVersion);
			int newRecord = Key.GetRecord(row);	
			// the record did not appeared in the index before update
			if (oldRecord == -1 || Size == 0 || !contains) {
				if (newRecord >= 0) {
					if (FindIndexExact(newRecord) < 0)
						Add(row,newRecord);
				}
				return;
			}
			
			// the record will not appeare in the index after update
			if (newRecord < 0 || !Key.CanContain (newRecord)) {
				Delete (oldRecord);
				return;
			}

			int oldIdx = FindIndexExact(oldRecord);

			if( oldIdx == -1 ) {
				Add(row,newRecord);
				return;
			}
				
			int newIdx = -1;
			int compare = Key.CompareRecords(Array[oldIdx],newRecord);
			int start,end;

			int c1 = 1;
			int c2 = 1;

			if (compare == 0) {
				if (Array[oldIdx] == newRecord) {
					// we deal with the same record that didn't change
					// in the context of current index.
					// so , do nothing.
					return;
				}
			}
			else {
				if ((_hasDuplicates == IndexDuplicatesState.True)) {
					if (oldIdx > 0) {
						c1 = Key.CompareRecords(Array[oldIdx - 1],newRecord);
					}
					if (oldIdx < Size - 1) {
						c2 = Key.CompareRecords(Array[oldIdx + 1],newRecord);
					}

					if ((c1 == 0 ^ c2 == 0) && compare != 0) {
						_hasDuplicates = IndexDuplicatesState.Unknown;
					}
				}
			}
			
			if ((oldIdx == 0 && compare > 0) || (oldIdx == (Size - 1) && compare < 0) || (compare == 0)) {
				// no need to switch cells
				newIdx = oldIdx;
			}
			else {
				if (compare < 0) {
					// search after the old place
					start = oldIdx + 1;
					end = Size - 1;
				}
				else {
					// search before the old palce
					start = 0;
					end = oldIdx - 1;
				}

				newIdx = LazyBinarySearch(Array,start,end,newRecord);					

				if (oldIdx < newIdx) {
					System.Array.Copy(Array,oldIdx + 1,Array,oldIdx,newIdx - oldIdx);
					if (Key.CompareRecords (Array [newIdx], newRecord) > 0)
						--newIdx;
				}
				else if (oldIdx > newIdx){
					System.Array.Copy(Array,newIdx,Array,newIdx + 1,oldIdx - newIdx);
					if (Key.CompareRecords (Array [newIdx], newRecord) < 0)
						++newIdx;
				}
			}			
			Array[newIdx] = newRecord;

			if (compare != 0) {
				if (!(_hasDuplicates == IndexDuplicatesState.True)) {
					if (newIdx > 0) {
						c1 = Key.CompareRecords(Array[newIdx - 1],newRecord);
					}
					if (newIdx < Size - 1) {
						c2 = Key.CompareRecords(Array[newIdx + 1],newRecord);
					}

					if (c1 == 0 || c2 == 0) {
						_hasDuplicates = IndexDuplicatesState.True;
					}
				}
			}
		}

		internal void Add(DataRow row) {
			Add(row, Key.GetRecord(row));
		}

		private void Add(DataRow row,int newRecord)
		{
			int newIdx;

			if (newRecord < 0 || !Key.CanContain (newRecord))
				return;

			if (Size == 0) {
				newIdx = 0;
			}
			else {
				newIdx = LazyBinarySearch(Array,0,Size - 1,newRecord);
				// if newl value is greater - insert afer old value
				// else - insert before old value
				if (Key.CompareRecords(Array[newIdx],newRecord) < 0) {
					newIdx++;
				}
			}
					
			Insert(newIdx,newRecord);

			int c1 = 1;
			int c2 = 1;
			if (!(_hasDuplicates == IndexDuplicatesState.True)) {
				if (newIdx > 0) {
					c1 = Key.CompareRecords(Array[newIdx - 1],newRecord);
				}
				if (newIdx < Size - 1) {
					c2 = Key.CompareRecords(Array[newIdx + 1],newRecord);
				}

				if (c1 == 0 || c2 == 0) {
					_hasDuplicates = IndexDuplicatesState.True;
				}
			}
		}

		private void Insert(int index,int r)
		{
			if (Array.Length == Size) {
				int[] tmp = (Size == 0) ? new int[16] : new int[Size << 1];
				System.Array.Copy(Array,0,tmp,0,index);
				tmp[index] = r;
				System.Array.Copy(Array,index,tmp,index + 1,Size - index);
				_array = tmp;
			}
			else {
				System.Array.Copy(Array,index,Array,index + 1,Size - index);
				Array[index] = r;
			}
			_size++;
		}

		private void MergeSort(int[] to, int length)
        {
            int[] from = new int[length];
            System.Array.Copy(to, 0, from, 0, from.Length);

            MergeSort(from, to, 0, from.Length);
        }

        private void MergeSort(int[] from, int[] to,int p, int r)
        {
            int q = (p + r) >> 1;
	        if (q == p) {
                return;
            }        

            MergeSort(to, from, p, q);
            MergeSort(to, from, q, r);

            // merge
            for (int middle = q, current = p;;) {
				int res = Key.CompareRecords(from[p],from[q]);
                if (res > 0) {
                    to[current++] = from[q++];

                    if (q == r) {
                        while( p < middle) {
                                to[current++] = from[p++];
						}
                        break;
                    }
                }
                else {

					if (res == 0) {
						_hasDuplicates = IndexDuplicatesState.True;
					}

                    to[current++] = from[p++];

                    if (p == middle) {
                        while( q < r) {
                                to[current++] = from[q++];
						}
                        break;
                    }
                }
            }
		}

		private void QuickSort(int[] a,int p,int r)
		{
			if (p < r) {
				int q = Partition(a,p,r);
				QuickSort(a,p,q);
				QuickSort(a,q+1,r);
			}
		}

		private int Partition(int[] a,int p,int r)
		{
			int x = a[p];
			int i = p - 1;
			int j = r + 1;

			while(true) {
				// decrement upper limit while values are greater then border value
				do {
					j--;
				}
				while(Key.CompareRecords(a[j],x) > 0);	//while(a[j] > x);

				do {
					i++;
				}
				while(Key.CompareRecords(a[i],x) < 0);	//while(a[i] < x);
				
				if (i<j) {
					int tmp = a[j];
					a[j] = a[i];
					a[i] = tmp;
				}
				else {
					return j;
				}
			}
		}

		private int BinarySearch(int[] a, int p, int r,int b)
		{
			int i = LazyBinarySearch(a,p,r,b);

			return (Key.CompareRecords(a[i],b) == 0) ? i : -1;
		}

		// Lazy binary search only returns the cell number the search finished in,
		// but does not checks that the correct value was actually found
		private int LazyBinarySearch(int[] a, int p, int r,int b)
		{
			if ( p == r ) {
				return p;
			}

			int q = (p+r) >> 1;

			int compare = Key.CompareRecords(a[q],b);
			if (compare < 0) { // if (a[q] < b) {
				return LazyBinarySearch(a,q+1,r,b);
			}
			else if (compare > 0) { // a[q] > b
				return LazyBinarySearch(a,p,q,b);
			}	
			else { // a[q] == b
				return q;
			}
		}

		internal void AddRef()
		{
			_refCount++;
		}

		internal void RemoveRef()
		{
			_refCount--;
		}

		/*
		// Prints indexes. For debugging.
		internal void Print ()
                {
                        for (int i=0; i < Size; i++) {
                                Console.Write ("Index {0} record {1}: ", i, Array [i]);
                                for (int j=0; j < Key.Table.Columns.Count; j++) {
                                        DataColumn col = Key.Table.Columns [j];
                                        if (Array [i] >= 0)
                                                Console.Write ("{0,15} ", col [Array [i]]);
                                }
                                Console.WriteLine ();
                        }
                }
		*/
		
		#endregion // Methods
	}
}