Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Squeezing more performance from SortedList

, 10 Oct 2008 CPOL
A SortedList implementations using a cyclic algorithm and C# IDictionary tweaks.
SplitArrayDictionary_demo.zip
SplitArrayDictionary_bin
Debug
SplitArrayDictionary.exe
SplitArrayDictionary.vshost.exe
SplitArrayDictionary.vshost.exe.manifest
Release
SplitArrayDictionary.exe
SplitArrayDictionary_src.zip
SplitArrayDictionary_src
Properties
src
using System.Collections.Generic;
using System.Diagnostics;
using System;
namespace SplitArrayDictionary
{
abstract public class SplitArrayDictionary<TKey,TValue>
   : SortedCyclicSplitArray<TKey,TValue>,IDictionary<TKey, TValue>
    where TKey : IComparable<TKey>
{
    protected SplitArrayDictionary(	int capacity) : base(capacity)
    { }    
    

    #region IDictionary<TKey,TValue> Members
    // Summary:
    //     Adds an element with the provided key and value to the System.Collections.Generic.IDictionary<TKey,TValue>.
    //
    // Parameters:
    //   key:
    //     The object to use as the key of the element to add.
    //
    // Parameters:
    //
    //   value:
    //     The object to use as the value of the element to add.
    //
    // Exceptions:
    //   System.ArgumentException:
    //     An element with the same key already exists in the System.Collections.Generic.IDictionary<TKey,TValue>.
    //
    //  System.InvalidOperationException:
    //     Dictionary is full.
    public void Add(TKey key, TValue value)
    {
        if (Full)
        {
            throw new System.InvalidOperationException("Dictionary is full.");
        }

        if (!Insert(key,value,false))
        {
            throw new System.ArgumentException("An element with the same key already exists in the System.Collections.Generic.IDictionary<TKey,TValue>.");
        }
    }

    public bool ContainsKey(TKey key)
    {
        TValue dummy;
        return TryGetValue(key, out dummy);        
    }

    public ICollection<TKey> Keys
    {
        get { throw new System.NotImplementedException(); }
    }

    public bool Remove(TKey key)
    {
        return base.RemoveByKey(key);
    }

    //
    // Summary:
    //     Gets the value associated with the specified key.
    //
    // Parameters:
    //   key:
    //     The key whose value to get.
    //
    // Parameters:
    //
    //   value:
    //     When this method returns, the value associated with the specified key, if
    //     the key is found; otherwise, the default value for the type of the value
    //     parameter. This parameter is passed uninitialized.
    //
    // Returns:
    //     true if the object that implements System.Collections.Generic.IDictionary<TKey,TValue>
    //     contains an element with the specified key; otherwise, false.
    //    
    public virtual bool TryGetValue(TKey key, out TValue value)
    {
        if (KeyMightBeInArray(key))
        {
            int index;
            if (TryCyclicBinarySearch(key, out index))
            {
                value = GetValue(index);
                return true;
            }
        }
        value = default(TValue);
        return false;
    }

    public ICollection<TValue> Values
    {
        get 
        { 
            return new TValue[] {};
            //throw new System.NotImplementedException(); 
        }
    }

    // Summary:
    //     Gets or sets the element with the specified key.
    //
    // Parameters:
    //   key:
    //     The key of the element to get or set.
    //
    // Returns:
    //     The element with the specified key.
    //
    // Exceptions:    
    //   System.Collections.Generic.KeyNotFoundException:
    //     The property is retrieved and key is not found.
    //    
    public TValue this[TKey key]
    {
        get
        {
            TValue value;
             if (TryGetValue(key, out value))
            {
                return value;
            }
            throw new System.Collections.Generic.KeyNotFoundException();
        }
        set
        {
            if (!Insert(key, value, true))
            {
                throw new System.InvalidOperationException("Dictionary is full.");
            }
            else
            {
                //key already exists
                //Insert just replaced the value
            }
            
        }
    }

    #endregion

    #region ICollection<KeyValuePair<TKey,TValue>> Members

    // Summary:
    //     Adds an item to the System.Collections.Generic.ICollection<T>.
    //
    // Parameters:
    //   item:
    //     The object to add to the System.Collections.Generic.ICollection<T>.
    public void Add(KeyValuePair<TKey, TValue> item)
    {
        this.Add(item.Key, item.Value);
    }

    // Summary:
    //     Removes all items from the System.Collections.Generic.ICollection<T>.
    //
    // Exceptions:
    //   System.NotSupportedException:
    //     The System.Collections.Generic.ICollection<T> is read-only.
    void ICollection<KeyValuePair<TKey, TValue>>.Clear()
    {
        Clear();
    }

    // Summary:
    //     Determines whether the System.Collections.Generic.ICollection<T> contains
    //     a specific value.
    //
    // Parameters:
    //   item:
    //     The object to locate in the System.Collections.Generic.ICollection<T>.
    //
    // Returns:
    //     true if item is found in the System.Collections.Generic.ICollection<T>; otherwise,
    //     false.
    public bool Contains(KeyValuePair<TKey, TValue> item)
    {
        TValue value;
        if (TryGetValue(item.Key, out value))
        {
            return (value.Equals(item.Value));
        }
        return false;
    }

    // Summary:
    //     Copies the elements of the System.Collections.Generic.ICollection<T> to an
    //     System.Array, starting at a particular System.Array index.
    //
    // Parameters:
    //   array:
    //     The one-dimensional System.Array that is the destination of the elements
    //     copied from System.Collections.Generic.ICollection<T>. The System.Array must
    //     have zero-based indexing.
    //
    //   arrayIndex:
    //     The zero-based index in array at which copying begins.
    //
    // Exceptions:
    //   System.ArgumentNullException:
    //     array is null.
    //
    //   System.ArgumentOutOfRangeException:
    //     arrayIndex is less than 0.
    //
    //   System.ArgumentException:
    //     array is multidimensional.-or-arrayIndex is equal to or greater than the
    //     length of array.-or-The number of elements in the source System.Collections.Generic.ICollection<T>
    //     is greater than the available space from arrayIndex to the end of the destination
    //     array.-or-Type T cannot be cast automatically to the type of the destination
    //     array.
    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
    {
        if (array == null)
        {
            throw new ArgumentNullException("array", "Array cannot be null");
        }
        if (array.Rank != 1)
        {
            throw new ArgumentException("Only single dimentional arrays are supported for the requested operation","array");
        }
        if (arrayIndex < 0)
        {
            throw new ArgumentOutOfRangeException("arrayIndex", "Non-negative number required.");
        }
        if ((array.Length - arrayIndex) < base.Count)
        {
            throw new ArgumentException("Destination array is not long enough to copy all the items in the collection. Check array index and length.");
        }
        var e = this.GetEnumerator();
        while (e.MoveNext())
        {
            array[arrayIndex] = e.Current;
            arrayIndex++;
        }
    }

    // Summary:
    //     Gets the number of elements contained in the System.Collections.Generic.ICollection<T>.
    //
    // Returns:
    //     The number of elements contained in the System.Collections.Generic.ICollection<T>.
    int ICollection<KeyValuePair<TKey, TValue>>.Count
    {
        get { return base.Count; }
    }

    // Summary:
    //     Gets a value indicating whether the System.Collections.Generic.ICollection<T>
    //     is read-only.
    //
    // Returns:
    //     true if the System.Collections.Generic.ICollection<T> is read-only; otherwise,
    //     false.
    public bool IsReadOnly
    {
        get { return false; }
    }

    public bool Remove(KeyValuePair<TKey, TValue> item)
    {
        return base.RemoveByKeyValue(item.Key, item.Value);
    }

    #endregion

}//class
}//namespace

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

itaifrenkel
Software Developer
Israel Israel
No Biography provided

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150326.1 | Last Updated 10 Oct 2008
Article Copyright 2007 by itaifrenkel
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid