File: System\Data\Services\Client\ArraySet.cs
Project: ndp\fx\src\DataWeb\Client\System.Data.Services.Client.csproj (System.Data.Services.Client)
//---------------------------------------------------------------------
// <copyright file="ArraySet.cs" company="Microsoft">
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// </copyright>
// <summary>
// a set, collection of unordered, distinct objects, implemented as an array
// </summary>
//---------------------------------------------------------------------
 
namespace System.Data.Services.Client
{
    using System;
    using System.Collections.Generic;
    using System.Diagnostics;
 
    /// <summary>a set, collection of unordered, distinct objects, implemented as an array</summary>
    /// <typeparam name="T">element type</typeparam>
    [DebuggerDisplay("Count = {count}")]
    internal struct ArraySet<T> : IEnumerable<T> where T : class
    {
        /// <summary>item array of T</summary>
        private T[] items;
 
        /// <summary>count of elements in the items array</summary>
        private int count;
 
        /// <summary>number of Add and RemoveAt operations</summary>
        private int version;
 
        /// <summary>
        /// array set with an intial capacity
        /// </summary>
        /// <param name="capacity">initial capacity</param>
        public ArraySet(int capacity)
        {
            this.items = new T[capacity];
            this.count = 0;
            this.version = 0;
        }
 
        /// <summary>count of elements in the set</summary>
        public int Count
        {
            get { return this.count; }
        }
 
        /// <summary>get an item from an index in the set</summary>
        /// <param name="index">index to access</param>
        public T this[int index]
        {
            get
            {
                Debug.Assert(index < this.count);
                return this.items[index];
            }
        }
 
        /// <summary>add new element to the set</summary>
        /// <param name="item">element to add</param>
        /// <param name="equalityComparer">equality comparison function to avoid duplicates</param>
        /// <returns>true if actually added, false if a duplicate was discovered</returns>
        public bool Add(T item, Func<T, T, bool> equalityComparer)
        {
            if ((null != equalityComparer) && this.Contains(item, equalityComparer))
            {
                return false;
            }
 
            int index = this.count++;
            if ((null == this.items) || (index == this.items.Length))
            {   // grow array in size, with minimum size being 32
                Array.Resize<T>(ref this.items, Math.Min(Math.Max(index, 16), Int32.MaxValue / 2) * 2);
            }
 
            this.items[index] = item;
            unchecked
            {
                this.version++;
            }
 
            return true;
        }
 
        /// <summary>is the element contained within the set</summary>
        /// <param name="item">item to find</param>
        /// <param name="equalityComparer">comparer</param>
        /// <returns>true if the element is contained</returns>
        public bool Contains(T item, Func<T, T, bool> equalityComparer)
        {
            return (0 <= this.IndexOf(item, equalityComparer));
        }
 
        /// <summary>
        /// enumerator
        /// </summary>
        /// <returns>enumerator</returns>
        public IEnumerator<T> GetEnumerator()
        {
            for (int i = 0; i < this.count; ++i)
            {
                yield return this.items[i];
            }
        }
 
        /// <summary>
        /// enumerator
        /// </summary>
        /// <returns>enumerator</returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
        
        /// <summary>Find the current index of element within the set</summary>
        /// <param name="item">item to find</param>
        /// <param name="comparer">comparision function</param>
        /// <returns>index of the item else (-1)</returns>
        public int IndexOf(T item, Func<T, T, bool> comparer)
        {
            return this.IndexOf(item, IdentitySelect, comparer);
        }
 
        /// <summary>Find the current index of element within the set</summary>
        /// <typeparam name="K">selected type</typeparam>
        /// <param name="item">item to find</param>
        /// <param name="select">selector for item to compare</param>
        /// <param name="comparer">item to compare</param>
        /// <returns>index of the item else (-1)</returns>
        public int IndexOf<K>(K item, Func<T, K> select, Func<K, K, bool> comparer)
        {
            T[] array = this.items;
            if (null != array)
            {
                int length = this.count;
                for (int i = 0; i < length; ++i)
                {
                    if (comparer(item, select(array[i])))
                    {
                        return i;
                    }
                }
            }
 
            return -1;
        }
 
        /// <summary>Remove the matched item from within the set</summary>
        /// <param name="item">item to find within the set</param>
        /// <param name="equalityComparer">comparer to find item to remove</param>
        /// <returns>the item that was actually contained else its default</returns>
        public T Remove(T item, Func<T, T, bool> equalityComparer)
        {
            int index = this.IndexOf(item, equalityComparer);
            if (0 <= index)
            {
                item = this.items[index];
                this.RemoveAt(index);
                return item;
            }
 
            return default(T);
        }
 
        /// <summary>Remove an item at a specific index from within the set</summary>
        /// <param name="index">index of item to remove within the set</param>
        public void RemoveAt(int index)
        {
            Debug.Assert(unchecked((uint)index < (uint)this.count), "index out of range");
            T[] array = this.items;
            int lastIndex = --this.count;
            array[index] = array[lastIndex];
            array[lastIndex] = default(T);
 
            if ((0 == lastIndex) && (256 <= array.Length))
            {
                this.items = null;
            }
            else if ((256 < array.Length) && (lastIndex < array.Length / 4))
            {   // shrink to half size when count is a quarter
                Array.Resize(ref this.items, array.Length / 2);
            }
 
            unchecked
            {
                this.version++;
            }
        }
 
        /// <summary>Sort array based on selected value out of item being stored</summary>
        /// <typeparam name="K">selected type</typeparam>
        /// <param name="selector">selector</param>
        /// <param name="comparer">comparer</param>
        public void Sort<K>(Func<T, K> selector, Func<K, K, int> comparer)
        {
            if (null != this.items)
            {
                SelectorComparer<K> scomp;
                scomp.Selector = selector;
                scomp.Comparer = comparer;
                Array.Sort<T>(this.items, 0, this.count, scomp);
            }
        }
 
        /// <summary>Sets the capacity to the actual number of elements in the ArraySet.</summary>
        public void TrimToSize()
        {
            Array.Resize(ref this.items, this.count);
        }
 
        /// <summary>identity selector, returns self</summary>
        /// <param name="arg">input</param>
        /// <returns>output</returns>
        private static T IdentitySelect(T arg)
        {
            return arg;
        }
 
        /// <summary>Compare selected value out of t</summary>
        /// <typeparam name="K">comparison type</typeparam>
        private struct SelectorComparer<K> : IComparer<T>
        {
            /// <summary>Select something out of T</summary>
            internal Func<T, K> Selector;
 
            /// <summary>Comparer of selected value</summary>
            internal Func<K, K, int> Comparer;
 
            /// <summary>Compare</summary>
            /// <param name="x">x</param>
            /// <param name="y">y</param>
            /// <returns>int</returns>
            int IComparer<T>.Compare(T x, T y)
            {
                return this.Comparer(this.Selector(x), this.Selector(y));
            }
        }
    }
}