Optimize your game

[dyox]

Optimizations

Fast Dictionnary

using System;
using System.Collections;
using System.Diagnostics;
using System.Runtime.Serialization;
using System.Security.Permissions;
using System.Collections.Generic;

namespace TerrainEngine
{
    [Serializable()]
    [System.Runtime.InteropServices.ComVisible(false)]
    public class FastDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary, ISerializable, IDeserializationCallback
    {
        private struct Entry
        {
            public int hashCode;    // Lower 31 bits of hash code, -1 if unused
            public int next;        // Index of next entry, -1 if last
            public TKey key;           // Key of entry
            public TValue value;         // Value of entry
        }

        private int[] buckets;
        private Entry[] entries;
        private int count;
        private int version;
        private int freeList;
        private int freeCount;
        private IEqualityComparer<TKey> comparer;
        private KeyCollection keys;
        private ValueCollection values;
        private Object _syncRoot;

        private SerializationInfo m_siInfo; //A temporary variable which we need during deserialization.

        // constants for serialization
        private const String VersionName = "Version";
        private const String HashSizeName = "HashSize";  // Must save buckets.Length
        private const String KeyValuePairsName = "KeyValuePairs";
        private const String ComparerName = "Comparer";

        public FastDictionary() : this(100, null) { }

        public FastDictionary(int capacity) : this(capacity, null) { }

        public FastDictionary(IEqualityComparer<TKey> comparer) : this(0, comparer) { }

        public FastDictionary(int capacity, IEqualityComparer<TKey> comparer)
        {
            if (capacity < 0) throw new ArgumentOutOfRangeException("Capacity");
            if (capacity > 0) Initialize(capacity);
            if (comparer == null) comparer = EqualityComparer<TKey>.Default;
            this.comparer = comparer;
        }

        public FastDictionary(IDictionary<TKey, TValue> dictionary) : this(dictionary, null) { }

        public FastDictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer) :
            this(dictionary != null ? dictionary.Count : 0, comparer)
        {

            if (dictionary == null)
            {
                throw new ArgumentNullException("Dictionary");
            }

            foreach (KeyValuePair<TKey, TValue> pair in dictionary)
            {
                Add(pair.Key, pair.Value);
            }
        }

        protected FastDictionary(SerializationInfo info, StreamingContext context)
        {
            //We can't do anything with the keys and values until the entire graph has been deserialized
            //and we have a resonable estimate that GetHashCode is not going to fail.  For the time being,
            //we'll just cache this.  The graph is not valid until OnDeserialization has been called.
            m_siInfo = info;
        }

        public IEqualityComparer<TKey> Comparer
        {
            get
            {
                return comparer;
            }
        }

        public int Count
        {
            get { return count - freeCount; }
        }

        public KeyCollection Keys
        {
            get
            {
                if (keys == null) keys = new KeyCollection(this);
                return keys;
            }
        }

        ICollection<TKey> IDictionary<TKey, TValue>.Keys
        {
            get
            {
                if (keys == null) keys = new KeyCollection(this);
                return keys;
            }
        }

        public ValueCollection Values
        {
            get
            {
                if (values == null) values = new ValueCollection(this);
                return values;
            }
        }

        ICollection<TValue> IDictionary<TKey, TValue>.Values
        {
            get
            {
                if (values == null) values = new ValueCollection(this);
                return values;
            }
        }

        public TValue this[TKey key]
        {
            get
            {
                int i = FindEntry(key);
                if (i >= 0) return entries[i].value;
                throw new KeyNotFoundException();
                return default(TValue);
            }
            set
            {
                Insert(key, value, false);
            }
        }

        public void Add(TKey key, TValue value)
        {
            Insert(key, value, true);
        }

        void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> keyValuePair)
        {
            Add(keyValuePair.Key, keyValuePair.Value);
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> keyValuePair)
        {
            int i = FindEntry(keyValuePair.Key);
            if (i >= 0 && EqualityComparer<TValue>.Default.Equals(entries[i].value, keyValuePair.Value))
            {
                return true;
            }
            return false;
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> keyValuePair)
        {
            int i = FindEntry(keyValuePair.Key);
            if (i >= 0 && EqualityComparer<TValue>.Default.Equals(entries[i].value, keyValuePair.Value))
            {
                Remove(keyValuePair.Key);
                return true;
            }
            return false;
        }

        public void Clear()
        {
            if (count > 0)
            {
                for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;
                Array.Clear(entries, 0, count);
                freeList = -1;
                count = 0;
                freeCount = 0;
                version++;
            }
        }

        public bool ContainsKey(TKey key)
        {
            return FindEntry(key) >= 0;
        }

        public bool ContainsValue(TValue value)
        {
            if (value == null)
            {
                for (int i = 0; i < count; i++)
                {
                    if (entries[i].hashCode >= 0 && entries[i].value == null) return true;
                }
            }
            else
            {
                EqualityComparer<TValue> c = EqualityComparer<TValue>.Default;
                for (int i = 0; i < count; i++)
                {
                    if (entries[i].hashCode >= 0 && c.Equals(entries[i].value, value)) return true;
                }
            }
            return false;
        }

        private void CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
        {
            if (array == null)
            {
                throw new ArgumentNullException("array");

            }

            if (index < 0 || index > array.Length)
            {
                throw new ArgumentOutOfRangeException("index", "ArgumentOutOfRange_NeedNonNegNum");
            }

            if (array.Length - index < Count)
            {
                throw new ArgumentException("Arg_ArrayPlusOffTooSmall");
            }

            int count = this.count;
            Entry[] entries = this.entries;
            for (int i = 0; i < count; i++)
            {
                if (entries[i].hashCode >= 0)
                {
                    array[index++] = new KeyValuePair<TKey, TValue>(entries[i].key, entries[i].value);
                }
            }
        }

        public Enumerator GetEnumerator()
        {
            return new Enumerator(this, Enumerator.KeyValuePair);
        }

        IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
        {
            return new Enumerator(this, Enumerator.KeyValuePair);
        }

        [SecurityPermissionAttribute(SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
        public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
        {
            if (info == null)
            {
                throw new ArgumentNullException("info");
            }
            info.AddValue(VersionName, version);
            info.AddValue(ComparerName, comparer, typeof(IEqualityComparer<TKey>));
            info.AddValue(HashSizeName, buckets == null ? 0 : buckets.Length); //This is the length of the bucket array.
            if (buckets != null)
            {
                KeyValuePair<TKey, TValue>[] array = new KeyValuePair<TKey, TValue>[Count];
                CopyTo(array, 0);
                info.AddValue(KeyValuePairsName, array, typeof(KeyValuePair<TKey, TValue>[]));
            }
        }

        private int FindEntry(TKey key)
        {
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next)
            {
                if (entries[i].hashCode == hashCode)
                    if (comparer.Equals(entries[i].key, key))
                        return i;

            }
            return -1;
        }

        private void Initialize(int capacity)
        {
            int size = HashHelpers.GetPrime(capacity);
            buckets = new int[size];
            for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;
            entries = new Entry[size];
            freeList = -1;
        }

        public int InitOrGetPosition(TKey key)
        {
            return Insert(key, default(TValue), true);
        }

        public void StoreAtPosition(int pos, TValue value)
        {
            entries[pos].value = value;
            version++;
        }

        public TValue GetAtPosition(int pos)
        {
            return entries[pos].value;
        }

        private int Insert(TKey key, TValue value, bool add)
        {
            if (key == null)
            {
                throw new ArgumentNullException("key");
            }

            if (buckets == null) Initialize(1000);
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next)
            {
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
                {
                    if (add)
                    {
                        return i;
                    }
                    entries[i].value = value;
                    version++;
                    return i;
                }
            }
            int index;
            if (freeCount > 0)
            {
                index = freeList;
                freeList = entries[index].next;
                freeCount--;
            }
            else
            {
                if (count == entries.Length) Resize();
                index = count;
                count++;
            }
            int bucket = hashCode % buckets.Length;
            entries[index].hashCode = hashCode;
            entries[index].next = buckets[bucket];
            entries[index].key = key;
            entries[index].value = value;
            buckets[bucket] = index;
            version++;

            return index;
        }

        public virtual void OnDeserialization(Object sender)
        {
            if (m_siInfo == null)
            {
                // It might be necessary to call OnDeserialization from a container if the container object also implements
                // OnDeserialization. However, remoting will call OnDeserialization again.
                // We can return immediately if this function is called twice.
                // Note we set m_siInfo to null at the end of this method.
                return;
            }

            int realVersion = m_siInfo.GetInt32(VersionName);
            int hashsize = m_siInfo.GetInt32(HashSizeName);
            comparer = (IEqualityComparer<TKey>)m_siInfo.GetValue(ComparerName, typeof(IEqualityComparer<TKey>));

            if (hashsize != 0)
            {
                buckets = new int[hashsize];
                for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;
                entries = new Entry[hashsize];
                freeList = -1;

                KeyValuePair<TKey, TValue>[] array = (KeyValuePair<TKey, TValue>[])
                    m_siInfo.GetValue(KeyValuePairsName, typeof(KeyValuePair<TKey, TValue>[]));

                if (array == null)
                {
                    throw new SerializationException("Serialization_MissingKeyValuePairs");
                }

                for (int i = 0; i < array.Length; i++)
                {
                    if (array[i].Key == null)
                    {
                        throw new SerializationException("Serialization_NullKey");
                    }
                    Insert(array[i].Key, array[i].Value, true);
                }
            }
            else
            {
                buckets = null;
            }

            version = realVersion;
            m_siInfo = null;
        }

        private void Resize()
        {
            int newSize = HashHelpers.GetPrime(count * 2);
            int[] newBuckets = new int[newSize];
            for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
            Entry[] newEntries = new Entry[newSize];
            Array.Copy(entries, 0, newEntries, 0, count);
            for (int i = 0; i < count; i++)
            {
                int bucket = newEntries[i].hashCode % newSize;
                newEntries[i].next = newBuckets[bucket];
                newBuckets[bucket] = i;
            }
            buckets = newBuckets;
            entries = newEntries;
        }

        public bool Remove(TKey key)
        {
            if (key == null)
            {
                throw new ArgumentNullException("key");
            }

            if (buckets != null)
            {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                int bucket = hashCode % buckets.Length;
                int last = -1;
                for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next)
                {
                    if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
                    {
                        if (last < 0)
                        {
                            buckets[bucket] = entries[i].next;
                        }
                        else
                        {
                            entries[last].next = entries[i].next;
                        }
                        entries[i].hashCode = -1;
                        entries[i].next = freeList;
                        entries[i].key = default(TKey);
                        entries[i].value = default(TValue);
                        freeList = i;
                        freeCount++;
                        version++;
                        return true;
                    }
                }
            }
            return false;
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            int i = FindEntry(key);
            if (i >= 0)
            {
                value = entries[i].value;
                return true;
            }
            value = default(TValue);
            return false;
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly
        {
            get { return false; }
        }

        void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
        {
            CopyTo(array, index);
        }

        void ICollection.CopyTo(Array array, int index)
        {
            if (array == null)
            {
                throw new ArgumentNullException("array");
            }

            if (array.Rank != 1)
            {
                throw new ArgumentException("Arg_RankMultiDimNotSupported");
            }

            if (array.GetLowerBound(0) != 0)
            {
                throw new ArgumentException("Arg_NonZeroLowerBound");
            }

            if (index < 0 || index > array.Length)
            {
                throw new ArgumentOutOfRangeException("index", "ArgumentOutOfRange_NeedNonNegNum");
            }

            if (array.Length - index < Count)
            {
                throw new ArgumentException("Arg_ArrayPlusOffTooSmall");
            }

            KeyValuePair<TKey, TValue>[] pairs = array as KeyValuePair<TKey, TValue>[];
            if (pairs != null)
            {
                CopyTo(pairs, index);
            }
            else if (array is DictionaryEntry[])
            {
                DictionaryEntry[] dictEntryArray = array as DictionaryEntry[];
                Entry[] entries = this.entries;
                for (int i = 0; i < count; i++)
                {
                    if (entries[i].hashCode >= 0)
                    {
                        dictEntryArray[index++] = new DictionaryEntry(entries[i].key, entries[i].value);
                    }
                }
            }
            else
            {
                object[] objects = array as object[];
                if (objects == null)
                {
                    throw new ArgumentException("Argument_InvalidArrayType");
                }

                try
                {
                    int count = this.count;
                    Entry[] entries = this.entries;
                    for (int i = 0; i < count; i++)
                    {
                        if (entries[i].hashCode >= 0)
                        {
                            objects[index++] = new KeyValuePair<TKey, TValue>(entries[i].key, entries[i].value);
                        }
                    }
                }
                catch (ArrayTypeMismatchException)
                {
                    throw new ArgumentException("Argument_InvalidArrayType");
                }
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this, Enumerator.KeyValuePair);
        }

        bool ICollection.IsSynchronized
        {
            get { return false; }
        }

        object ICollection.SyncRoot
        {
            get
            {
                if (_syncRoot == null)
                {
                    System.Threading.Interlocked.CompareExchange(ref _syncRoot, new Object(), null);
                }
                return _syncRoot;
            }
        }

        bool IDictionary.IsFixedSize
        {
            get { return false; }
        }

        bool IDictionary.IsReadOnly
        {
            get { return false; }
        }

        ICollection IDictionary.Keys
        {
            get { return (ICollection)Keys; }
        }

        ICollection IDictionary.Values
        {
            get { return (ICollection)Values; }
        }

        object IDictionary.this[object key]
        {
            get
            {
                if (IsCompatibleKey(key))
                {
                    int i = FindEntry((TKey)key);
                    if (i >= 0)
                    {
                        return entries[i].value;
                    }
                }
                return null;
            }
            set
            {
                VerifyKey(key);
                VerifyValueType(value);
                this[(TKey)key] = (TValue)value;
            }
        }

        private static void VerifyKey(object key)
        {
            if (key == null)
            {
                throw new ArgumentNullException("key");
            }

            if (!(key is TKey))
            {
                throw new ArgumentException("Invalid type", "key");
            }
        }

        private static bool IsCompatibleKey(object key)
        {
            if (key == null)
            {
                throw new ArgumentNullException("key");
            }

            return (key is TKey);
        }

        private static void VerifyValueType(object value)
        {
            if ((value is TValue) || (value == null && !typeof(TValue).IsValueType))
            {
                return;
            }
            throw new ArgumentException("Invalid type", "value");
        }

        void IDictionary.Add(object key, object value)
        {
            VerifyKey(key);
            VerifyValueType(value);
            Add((TKey)key, (TValue)value);
        }

        bool IDictionary.Contains(object key)
        {
            if (IsCompatibleKey(key))
            {
                return ContainsKey((TKey)key);
            }
            return false;
        }

        IDictionaryEnumerator IDictionary.GetEnumerator()
        {
            return new Enumerator(this, Enumerator.DictEntry);
        }

        void IDictionary.Remove(object key)
        {
            if (IsCompatibleKey(key))
            {
                Remove((TKey)key);
            }
        }

        [Serializable()]
        public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>,
            IDictionaryEnumerator
        {
            private FastDictionary<TKey, TValue> dictionary;
            private int version;
            private int index;
            private KeyValuePair<TKey, TValue> current;
            private int getEnumeratorRetType;  // What should Enumerator.Current return?

            internal const int DictEntry = 1;
            internal const int KeyValuePair = 2;

            internal Enumerator(FastDictionary<TKey, TValue> dictionary, int getEnumeratorRetType)
            {
                this.dictionary = dictionary;
                version = dictionary.version;
                index = 0;
                this.getEnumeratorRetType = getEnumeratorRetType;
                current = new KeyValuePair<TKey, TValue>();
            }

            public bool MoveNext()
            {
                if (version != dictionary.version)
                {
                    throw new InvalidOperationException("InvalidOperation_EnumFailedVersion");
                }

                // Use unsigned comparison since we set index to dictionary.count+1 when the enumeration ends.
                // dictionary.count+1 could be negative if dictionary.count is Int32.MaxValue
                while ((uint)index < (uint)dictionary.count)
                {
                    if (dictionary.entries[index].hashCode >= 0)
                    {
                        current = new KeyValuePair<TKey, TValue>(dictionary.entries[index].key, dictionary.entries[index].value);
                        index++;
                        return true;
                    }
                    index++;
                }

                index = dictionary.count + 1;
                current = new KeyValuePair<TKey, TValue>();
                return false;
            }

            public KeyValuePair<TKey, TValue> Current
            {
                get { return current; }
            }

            public void Dispose()
            {
            }

            object IEnumerator.Current
            {
                get
                {
                    if (index == 0 || (index == dictionary.count + 1))
                    {
                        throw new InvalidOperationException("InvalidOperation_EnumOpCantHappen");
                    }

                    if (getEnumeratorRetType == DictEntry)
                    {
                        return new System.Collections.DictionaryEntry(current.Key, current.Value);
                    }
                    else
                    {
                        return new KeyValuePair<TKey, TValue>(current.Key, current.Value);
                    }
                }
            }

            void IEnumerator.Reset()
            {
                if (version != dictionary.version)
                {
                    throw new InvalidOperationException("InvalidOperation_EnumFailedVersion");
                }

                index = 0;
                current = new KeyValuePair<TKey, TValue>();
            }

            DictionaryEntry IDictionaryEnumerator.Entry
            {
                get
                {
                    if (index == 0 || (index == dictionary.count + 1))
                    {
                        throw new InvalidOperationException("InvalidOperation_EnumOpCantHappen");
                    }

                    return new DictionaryEntry(current.Key, current.Value);
                }
            }

            object IDictionaryEnumerator.Key
            {
                get
                {
                    if (index == 0 || (index == dictionary.count + 1))
                    {
                        throw new InvalidOperationException("InvalidOperation_EnumOpCantHappen");
                    }

                    return current.Key;
                }
            }

            object IDictionaryEnumerator.Value
            {
                get
                {
                    if (index == 0 || (index == dictionary.count + 1))
                    {
                        throw new InvalidOperationException("InvalidOperation_EnumOpCantHappen");
                    }

                    return current.Value;
                }
            }
        }

        [DebuggerDisplay("Count = {Count}")]
        [Serializable()]
        public sealed class KeyCollection : ICollection<TKey>, ICollection
        {
            private FastDictionary<TKey, TValue> dictionary;

            public KeyCollection(FastDictionary<TKey, TValue> dictionary)
            {
                if (dictionary == null)
                {
                    throw new ArgumentNullException("dictionary");
                }
                this.dictionary = dictionary;
            }

            public Enumerator GetEnumerator()
            {
                return new Enumerator(dictionary);
            }

            public void CopyTo(TKey[] array, int index)
            {
                if (array == null)
                {
                    throw new ArgumentNullException("array");
                }

                if (index < 0 || index > array.Length)
                {
                    throw new ArgumentOutOfRangeException("index", "ArgumentOutOfRange_NeedNonNegNum");
                }

                if (array.Length - index < dictionary.Count)
                {
                    throw new ArgumentException("Arg_ArrayPlusOffTooSmall");
                }

                int count = dictionary.count;
                Entry[] entries = dictionary.entries;
                for (int i = 0; i < count; i++)
                {
                    if (entries[i].hashCode >= 0) array[index++] = entries[i].key;
                }
            }

            public int Count
            {
                get { return dictionary.Count; }
            }

            bool ICollection<TKey>.IsReadOnly
            {
                get { return true; }
            }

            void ICollection<TKey>.Add(TKey item)
            {
                throw new NotSupportedException("NotSupported_KeyCollectionSet");
            }

            void ICollection<TKey>.Clear()
            {
                throw new NotSupportedException("NotSupported_KeyCollectionSet");
            }

            bool ICollection<TKey>.Contains(TKey item)
            {
                return dictionary.ContainsKey(item);
            }

            bool ICollection<TKey>.Remove(TKey item)
            {
                throw new NotSupportedException("NotSupported_KeyCollectionSet");
            }

            IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator()
            {
                return new Enumerator(dictionary);
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return new Enumerator(dictionary);
            }

            void ICollection.CopyTo(Array array, int index)
            {
                if (array == null)
                {
                    throw new ArgumentNullException("array");
                }

                if (array.Rank != 1)
                {
                    throw new ArgumentException("Arg_RankMultiDimNotSupported");
                }

                if (array.GetLowerBound(0) != 0)
                {
                    throw new ArgumentException("Arg_NonZeroLowerBound");
                }

                if (index < 0 || index > array.Length)
                {
                    throw new ArgumentOutOfRangeException("index", "ArgumentOutOfRange_NeedNonNegNum");
                }

                if (array.Length - index < dictionary.Count)
                {
                    throw new ArgumentException("Arg_ArrayPlusOffTooSmall");
                }

                TKey[] keys = array as TKey[];
                if (keys != null)
                {
                    CopyTo(keys, index);
                }
                else
                {
                    object[] objects = array as object[];
                    if (objects == null)
                    {
                        throw new ArgumentException("Argument_InvalidArrayType");
                    }

                    int count = dictionary.count;
                    Entry[] entries = dictionary.entries;
                    try
                    {
                        for (int i = 0; i < count; i++)
                        {
                            if (entries[i].hashCode >= 0) objects[index++] = entries[i].key;
                        }
                    }
                    catch (ArrayTypeMismatchException)
                    {
                        throw new ArgumentException("Argument_InvalidArrayType");
                    }
                }
            }

            bool ICollection.IsSynchronized
            {
                get { return false; }
            }

            Object ICollection.SyncRoot
            {
                get { return ((ICollection)dictionary).SyncRoot; }
            }

            [Serializable()]
            public struct Enumerator : IEnumerator<TKey>, System.Collections.IEnumerator
            {
                private FastDictionary<TKey, TValue> dictionary;
                private int index;
                private int version;
                private TKey currentKey;

                internal Enumerator(FastDictionary<TKey, TValue> dictionary)
                {
                    this.dictionary = dictionary;
                    version = dictionary.version;
                    index = 0;
                    currentKey = default(TKey);
                }

                public void Dispose()
                {
                }

                public bool MoveNext()
                {
                    if (version != dictionary.version)
                    {
                        throw new InvalidOperationException("InvalidOperation_EnumFailedVersion");
                    }

                    while ((uint)index < (uint)dictionary.count)
                    {
                        if (dictionary.entries[index].hashCode >= 0)
                        {
                            currentKey = dictionary.entries[index].key;
                            index++;
                            return true;
                        }
                        index++;
                    }

                    index = dictionary.count + 1;
                    currentKey = default(TKey);
                    return false;
                }

                public TKey Current
                {
                    get
                    {
                        return currentKey;
                    }
                }

                Object System.Collections.IEnumerator.Current
                {
                    get
                    {
                        if (index == 0 || (index == dictionary.count + 1))
                        {
                            throw new InvalidOperationException("InvalidOperation_EnumOpCantHappen");
                        }

                        return currentKey;
                    }
                }

                void System.Collections.IEnumerator.Reset()
                {
                    if (version != dictionary.version)
                    {
                        throw new InvalidOperationException("InvalidOperation_EnumFailedVersion");
                    }

                    index = 0;
                    currentKey = default(TKey);
                }
            }
        }

        [DebuggerDisplay("Count = {Count}")]
        [Serializable()]
        public sealed class ValueCollection : ICollection<TValue>, ICollection
        {
            private FastDictionary<TKey, TValue> dictionary;

            public ValueCollection(FastDictionary<TKey, TValue> dictionary)
            {
                if (dictionary == null)
                {
                    throw new ArgumentNullException("dictionary");
                }
                this.dictionary = dictionary;
            }

            public Enumerator GetEnumerator()
            {
                return new Enumerator(dictionary);
            }

            public void CopyTo(TValue[] array, int index)
            {
                if (array == null)
                {
                    throw new ArgumentNullException("array");
                }

                if (index < 0 || index > array.Length)
                {
                    throw new ArgumentOutOfRangeException("index", "ArgumentOutOfRange_NeedNonNegNum");
                }

                if (array.Length - index < dictionary.Count)
                {
                    throw new ArgumentException("Arg_ArrayPlusOffTooSmall");
                }

                int count = dictionary.count;
                Entry[] entries = dictionary.entries;
                for (int i = 0; i < count; i++)
                {
                    if (entries[i].hashCode >= 0) array[index++] = entries[i].value;
                }
            }

            public int Count
            {
                get { return dictionary.Count; }
            }

            bool ICollection<TValue>.IsReadOnly
            {
                get { return true; }
            }

            void ICollection<TValue>.Add(TValue item)
            {
                throw new NotSupportedException("NotSupported_ValueCollectionSet");
            }

            bool ICollection<TValue>.Remove(TValue item)
            {
                throw new NotSupportedException("NotSupported_ValueCollectionSet");
            }

            void ICollection<TValue>.Clear()
            {
                throw new NotSupportedException("NotSupported_ValueCollectionSet");
            }

            bool ICollection<TValue>.Contains(TValue item)
            {
                return dictionary.ContainsValue(item);
            }

            IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator()
            {
                return new Enumerator(dictionary);
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return new Enumerator(dictionary);
            }

            void ICollection.CopyTo(Array array, int index)
            {
                if (array == null)
                {
                    throw new ArgumentNullException("array");
                }

                if (array.Rank != 1)
                {
                    throw new ArgumentException("Arg_RankMultiDimNotSupported");
                }

                if (array.GetLowerBound(0) != 0)
                {
                    throw new ArgumentException("Arg_NonZeroLowerBound");
                }

                if (index < 0 || index > array.Length)
                {
                    throw new ArgumentOutOfRangeException("index", "ArgumentOutOfRange_NeedNonNegNum");
                }

                if (array.Length - index < dictionary.Count)
                    throw new ArgumentException("Arg_ArrayPlusOffTooSmall");

                TValue[] values = array as TValue[];
                if (values != null)
                {
                    CopyTo(values, index);
                }
                else
                {
                    object[] objects = array as object[];
                    if (objects == null)
                    {
                        throw new ArgumentException("Argument_InvalidArrayType");
                    }

                    int count = dictionary.count;
                    Entry[] entries = dictionary.entries;
                    try
                    {
                        for (int i = 0; i < count; i++)
                        {
                            if (entries[i].hashCode >= 0) objects[index++] = entries[i].value;
                        }
                    }
                    catch (ArrayTypeMismatchException)
                    {
                        throw new ArgumentException("Argument_InvalidArrayType");
                    }
                }
            }

            bool ICollection.IsSynchronized
            {
                get { return false; }
            }

            Object ICollection.SyncRoot
            {
                get { return ((ICollection)dictionary).SyncRoot; }
            }

            [Serializable()]
            public struct Enumerator : IEnumerator<TValue>, System.Collections.IEnumerator
            {
                private FastDictionary<TKey, TValue> dictionary;
                private int index;
                private int version;
                private TValue currentValue;

                internal Enumerator(FastDictionary<TKey, TValue> dictionary)
                {
                    this.dictionary = dictionary;
                    version = dictionary.version;
                    index = 0;
                    currentValue = default(TValue);
                }

                public void Dispose()
                {
                }

                public bool MoveNext()
                {
                    if (version != dictionary.version)
                    {
                        throw new InvalidOperationException("InvalidOperation_EnumFailedVersion");
                    }

                    while ((uint)index < (uint)dictionary.count)
                    {
                        if (dictionary.entries[index].hashCode >= 0)
                        {
                            currentValue = dictionary.entries[index].value;
                            index++;
                            return true;
                        }
                        index++;
                    }
                    index = dictionary.count + 1;
                    currentValue = default(TValue);
                    return false;
                }

                public TValue Current
                {
                    get
                    {
                        return currentValue;
                    }
                }

                Object System.Collections.IEnumerator.Current
                {
                    get
                    {
                        if (index == 0 || (index == dictionary.count + 1))
                        {
                            throw new InvalidOperationException("InvalidOperation_EnumOpCantHappen");
                        }

                        return currentValue;
                    }
                }

                void System.Collections.IEnumerator.Reset()
                {
                    if (version != dictionary.version)
                    {
                        throw new InvalidOperationException("InvalidOperation_EnumFailedVersion");
                    }
                    index = 0;
                    currentValue = default(TValue);
                }
            }
        }
    }

    internal static class HashHelpers
    {
        // Table of prime numbers to use as hash table sizes.
        // The entry used for capacity is the smallest prime number in this aaray
        // that is larger than twice the previous capacity.

        internal static readonly int[] primes = {
            3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
            1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
            17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
            187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
            1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};

        internal static bool IsPrime(int candidate)
        {
            if ((candidate & 1) != 0)
            {
                int limit = (int)Math.Sqrt(candidate);
                for (int divisor = 3; divisor <= limit; divisor += 2)
                {
                    if ((candidate % divisor) == 0)
                        return false;
                }
                return true;
            }
            return (candidate == 2);
        }

        internal static int GetPrime(int min)
        {
            if (min < 0)
                throw new ArgumentException("min");

            for (int i = 0; i < primes.Length; i++)
            {
                int prime = primes[i];
                if (prime >= min) return prime;
            }

            //outside of our predefined table.
            //compute the hard way.
            for (int i = (min | 1); i < Int32.MaxValue; i += 2)
            {
                if (IsPrime(i))
                    return i;
            }
            return min;
        }
    }
}

Fast 3D List

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TerrainEngine
{
    public class Fast3DArray<T>
    {
        public int SizeX, SizeY, SizeZ;
        public T[] Array;

        public Fast3DArray(int SizeX, int SizeY, int SizeZ)
        {
            this.SizeX = SizeX;
            this.SizeY = SizeY;
            this.SizeZ = SizeZ;
            this.Array = new T[SizeX * SizeY * SizeZ];
        }

        public T this[int x, int y, int z]
        {
            get
            {
                return Array[x * SizeY * SizeZ + y * SizeZ + z];
            }
            set
            {
                Array[x * SizeY * SizeZ + y * SizeZ + z] = value;
            }
        }
    }
}

Fast Random

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using UnityEngine;


public class FastRandom
{
    public long _seed;

    public FastRandom(long seed)
    {
        this._seed = seed;
        if (_seed == 0)
            _seed = 1;
    }

    long randomLong()
    {
        _seed ^= (_seed << 21);
        _seed ^= (_seed >> 35) & 0xFF;
        _seed ^= (_seed << 4);
        return _seed;
    }

    public int randomInt()
    {
        _seed ^= (_seed << 21);
        _seed ^= (_seed >> 35) & 0xFF;
        _seed ^= (_seed << 4);
        return (int)_seed;
    }

    public int randomInt(int range)
    {
        return (int)randomLong() % range;
    }

    public int randomIntAbs()
    {
        return fastAbs(randomInt());
    }

    public int randomIntAbs(int range)
    {
        return fastAbs(randomInt() % range);
    }

    public double randomDouble()
    {
        return randomLong() / ((double)long.MaxValue - 1d);
    }

    public float randomFloat()
    {
        return randomLong() / ((float)long.MaxValue - 1f);
    }

    public Vector3 randomVector3f()
    {
        return new Vector3(randomFloat(), randomFloat(), randomFloat());
    }

    public float randomPosFloat()
    {
        return 0.5f * (randomFloat() + 1.0f);
    }

    public bool randomBoolean()
    {
        return randomLong() > 0;
    }

    public String randomCharacterString(int length)
    {
        StringBuilder s = new StringBuilder();

        for (int i = 0; i < length / 2; i++)
        {
            s.Append((char)('a' + fastAbs(randomDouble()) * 26d));
            s.Append((char)('A' + fastAbs(randomDouble()) * 26d));
        }

        return s.ToString();
    }

    public double standNormalDistrDouble()
    {

        double q = Double.MaxValue;
        double u1 = 0;
        double u2;

        while (q >= 1d || q == 0)
        {
            u1 = randomDouble();
            u2 = randomDouble();

            q = Math.Pow(u1, 2) + Math.Pow(u2, 2);
        }

        double p = Math.Sqrt((-2d * (Math.Log(q))) / q);
        return u1 * p;
    }

    public static int fastAbs(int i)
    {
        return (i >= 0) ? i : -i;
    }

    public static float fastAbs(float d)
    {
        return (d >= 0) ? d : -d;
    }

    public static double fastAbs(double d)
    {
        return (d >= 0) ? d : -d;
    }
}

public struct SFastRandom
{
    private long _seed;

    public SFastRandom(long seed)
    {
        this._seed = seed;
    }

    public void InitSeed(long seed)
    {
        this._seed = seed;
        randomLong();
        randomLong();
    }

    public long randomLong()
    {
        _seed ^= (_seed << 21);
        _seed ^= (_seed >> 35) & 0xFF;
        _seed ^= (_seed << 4);
        return _seed;
    }

    public int randomInt()
    {
        return (int)randomLong();
    }

    public int randomInt(int range)
    {
        return (int)randomLong() % range;
    }

    public int randomIntAbs()
    {
        return fastAbs(randomInt());
    }

    public int randomIntAbs(int range)
    {
        return fastAbs(randomInt() % range);
    }

    public double randomDouble()
    {
        return randomLong() / ((double)long.MaxValue - 1d);
    }

    public float randomFloat()
    {
        return randomLong() / ((float)long.MaxValue - 1f);
    }

    public Vector3 randomVector3f()
    {
        return new Vector3(randomFloat(), randomFloat(), randomFloat());
    }

    public void randomVector3f(ref Vector3 p, float Scale)
    {
        p.x = randomFloat() * Scale;
        p.y = randomFloat() * Scale;
        p.z = randomFloat() * Scale;
    }

    public void randomVector3fXZ(ref Vector3 p, float Scale)
    {
        p.x += randomFloat() * Scale;
        p.z += randomFloat() * Scale;
    }

    public float randomPosFloat()
    {
        return 0.5f * (randomFloat() + 1.0f);
    }

    public bool randomBoolean()
    {
        return randomLong() > 0;
    }

    public String randomCharacterString(int length)
    {
        StringBuilder s = new StringBuilder();

        for (int i = 0; i < length / 2; i++)
        {
            s.Append((char)('a' + fastAbs(randomDouble()) * 26d));
            s.Append((char)('A' + fastAbs(randomDouble()) * 26d));
        }

        return s.ToString();
    }

    public double standNormalDistrDouble()
    {

        double q = Double.MaxValue;
        double u1 = 0;
        double u2;

        while (q >= 1d || q == 0)
        {
            u1 = randomDouble();
            u2 = randomDouble();

            q = Math.Pow(u1, 2) + Math.Pow(u2, 2);
        }

        double p = Math.Sqrt((-2d * (Math.Log(q))) / q);
        return u1 * p;
    }

    public static int fastAbs(int i)
    {
        return (i >= 0) ? i : -i;
    }

    public static float fastAbs(float d)
    {
        return (d >= 0) ? d : -d;
    }

    public static double fastAbs(double d)
    {
        return (d >= 0) ? d : -d;
    }
}

Fast multi-threaded List

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TerrainEngine
{
    /// <summary>
    /// Fast Threaded List. Objects are stored in waiting list. All elements are pushed to the working list when Process() is call.
    /// </summary>
    public class TransitionList<T>
    {
        public List<T> Interdata;
        public List<T> List;
        public volatile int WaitingCount;
        public int Count
        {
            get
            {
                return List.Count;
            }
        }

        public TransitionList()
        {
            Interdata = new List<T>();
            List = new List<T>();
            WaitingCount = 0;
        }

        public void Process()
        {
            if (WaitingCount == 0)
                return;

            lock (Interdata)
            {
                List.AddRange(Interdata);
                Interdata.Clear();
                WaitingCount = 0;
            }
        }

        public void AddUnsafe(T obj)
        {
            lock (Interdata)
            {
                Interdata.Add(obj);
                WaitingCount = Interdata.Count;
            }
        }

        public void AddRangeUnsafe(T[] objs)
        {
            lock (Interdata)
            {
                Interdata.AddRange(objs);
                WaitingCount = Interdata.Count;
            }
        }

        #region Safe

        public void AddSafe(T obj)
        {
            List.Add(obj);
        }

        public void AddRangeSafe(T[] obj)
        {
            List.AddRange(obj);
        }

        public bool Remove(T obj)
        {
            return List.Remove(obj);
        }

        public void Clear()
        {
            List.Clear();
            Interdata.Clear();
            WaitingCount = 0;
        }

        public T[] ToArray()
        {
            return List.ToArray();
        }

        #endregion
    }
}

Fast Multi-Threaded Queue

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TerrainEngine
{
    /// <summary>
    /// Fast Threaded List. Objects are added in waiting list. All elements are pushed to the working list when Process() is call.
    /// </summary>
    public class TransitionQueue<T>
    {
        public List<T> Interdata;
        public Queue<T> List;
        public volatile int WaitingCount;
        public int Count
        {
            get
            {
                return List.Count;
            }
        }

        public TransitionQueue()
        {
            Interdata = new List<T>();
            List = new Queue<T>();
            WaitingCount = 0;
        }

        public void Process()
        {
            if (WaitingCount == 0)
                return;

            lock (Interdata)
            {
                for (int i = 0; i < Interdata.Count; ++i)
                {
                    List.Enqueue(Interdata[i]);
                }

                Interdata.Clear();
                WaitingCount = 0;
            }
        }

        public void AddUnsafe(T obj)
        {
            lock (Interdata)
            {
                Interdata.Add(obj);
                WaitingCount = Interdata.Count;
            }
        }

        public void AddRangeUnsafe(T[] objs)
        {
            lock (Interdata)
            {
                Interdata.AddRange(objs);
                WaitingCount = Interdata.Count;
            }
        }

        public void Clear()
        {
            List.Clear();
            Interdata.Clear();
            WaitingCount = 0;
        }
    }
}

Global Log System

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using UnityEngine;

/// <summary>
/// Unified Logger , usable in Unity and Server.
/// Use Init to register delegate function for draw message. Unity : Debug.Log,Debug.LogWarning,etc...
/// </summary>
static public class GeneralLog
{
    public delegate void OnLogDelegate(object message);
    public delegate void OnExceptionDelgate(Exception e);

    static public OnLogDelegate OnLog;
    static public OnLogDelegate OnLogWarning;
    static public OnLogDelegate OnLogError;
    static public OnLogDelegate OnLogDebug;
    static public OnLogDelegate OnLogSuccess;
    static public OnExceptionDelgate OnLogException;
    static public OnLogDelegate OnLogArray;
    static public bool Inited = false;
    static public bool DrawLogs = true;

    static public void Init(OnLogDelegate Log, OnLogDelegate Warning, OnLogDelegate Error, OnExceptionDelgate Ex)
    {
        if (!Inited)
        {
            Inited = true;
            OnLog += Log;
            OnLogWarning += Warning;
            OnLogError += Error;
            OnLogException += Ex;
            OnLogSuccess += Log;
        }
    }

    static public void Log(object message)
    {
        if (!Inited)
        {
            Init(Debug.Log, Debug.LogWarning, Debug.LogError, Debug.LogException);
        }

        if (OnLog != null)
            OnLog(message);
    }

    static public void Log(object title, object message)
    {
        if (OnLog != null)
            OnLog(title + " : " + message);
    }

    static public void LogWarning(object message)
    {
        if (!Inited)
        {
            Init(Debug.Log, Debug.LogWarning, Debug.LogError, Debug.LogException);
        }

        if (OnLogWarning != null)
            OnLogWarning(message);
    }

    static public void LogError(object message)
    {
        if (!Inited)
        {
            Init(Debug.Log, Debug.LogWarning, Debug.LogError, Debug.LogException);
        }

        if (OnLogError != null)
            OnLogError(message);
    }

    static public void LogDebug(object message)
    {
        if (!Inited)
        {
            Init(Debug.Log, Debug.LogWarning, Debug.LogError, Debug.LogException);
        }

        if (OnLogDebug != null)
            OnLogDebug(message);
    }

    static public void LogSuccess(object message)
    {
        if (OnLogSuccess != null)
            OnLogSuccess(message);
    }

    static public void LogWarning(object title, object message)
    {
        if (OnLogWarning != null)
            OnLogWarning(title + " : " + message);
    }

    static public void LogDebug(object title, object message)
    {
        if (OnLogDebug != null)
            OnLogDebug(title + " : " + message);
    }

    static public void LogError(object title, object message)
    {
        if (OnLogError != null)
            OnLogError(title + " : " + message);
    }

    static public void LogSuccess(object title, object message)
    {
        if (OnLogSuccess != null)
            OnLogSuccess(title + " : " + message);
    }

    static public void LogException(Exception e)
    {
        if (OnLogException != null)
            OnLogException(e);
    }

    static public void LogArray(string name, byte[] dump, int start, int len, bool Force = false)
    {
        if (OnLogArray != null)
            OnLogArray("P " + name + " : " + Hex(dump, start, len));
    }

    static public string Hex(byte[] dump, int start, int len)
    {
        StringBuilder hexDump = new StringBuilder();

        try
        {
            int end = start + len;
            for (int i = start; i < end; i += 16)
            {
                StringBuilder text = new StringBuilder();
                StringBuilder hex = new StringBuilder();
                hex.Append("\n");

                for (int j = 0; j < 16; j++)
                {
                    if (j + i < end)
                    {
                        byte val = dump[j + i];
                        hex.Append(" ");
                        hex.Append(dump[j + i].ToString("X2"));
                        if (j == 3 || j == 7 || j == 11)
                            hex.Append(" ");
                        if (val >= 32 && val <= 127)
                        {
                            text.Append((char)val);
                        }
                        else
                        {
                            text.Append(".");
                        }
                    }
                    else
                    {
                        hex.Append("   ");
                        text.Append("  ");
                    }
                }
                hex.Append("  ");
                hex.Append("//" + text.ToString());
                hexDump.Append(hex.ToString());
            }
        }
        catch (Exception e)
        {
            LogError("HexDump", e.ToString());
        }

        return hexDump.ToString();
    }
}

Fast QuadTree (ref less)

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

namespace TerrainEngine
{
    public class QuadTreeChildsArray<T>
    {
        public QuadTreeNode<T>[] Array;
        public int Count = 0;

        public QuadTreeChildsArray(QuadTreeNode<T> MainNode, int MaxLevel)
        {
            Array = new QuadTreeNode<T>[QuadTreeNode<T>.GetMaxChilds(MaxLevel) + 1];
            Array[0] = MainNode;
            Count = 1;
        }

        public void GetIndex(ref int Index)
        {
            Index = Count;
            Count += 8;
        }
    }

    public struct QuadTreeNode<T>
    {
        public byte m_level, m_id;
        public Vector3 m_position;
        public float m_size;
        public bool Closed;
        public Vector3 m_center
        {
            get
            {
                return new Vector3(m_position.x + m_size * 0.5f, m_position.y + m_size * 0.5f, m_position.z + m_size * 0.5f);
            }
        }

        public int ParentIndex; // Parent Index in Array
        public int StartIndex;  // StartIndex for childs in Array
        public int Index; // Index of this node in Array
        public T Data; // Data that node contains

        public QuadTreeNode(byte id, byte ParentLevel, int ParentStartIndex, int ParentIndex, Vector3 Position, float Size)
        {
            this.StartIndex = -1;
            this.Data = default(T);

            this.Closed = false;
            this.m_id = id;
            this.m_position = Position;
            this.m_size = Size;
            if (ParentIndex != -1)
            {
                this.m_level = (byte)(ParentLevel + 1);
                this.Index = ParentStartIndex + id;
                this.ParentIndex = ParentIndex;
            }
            else
            {
                this.Index = 0;
                this.ParentIndex = -1;
                this.m_level = 0;
            }
        }

        public void Init(byte id, byte ParentLevel, int ParentStartIndex, int ParentIndex, Vector3 Position, float Size)
        {
            this.Closed = false;
            this.m_id = id;
            this.m_position = Position;
            this.m_size = Size;

            if (ParentIndex != -1)
            {
                this.m_level = (byte)(ParentLevel + 1);
                this.Index = ParentStartIndex + id;
                this.ParentIndex = ParentIndex;
            }
            else
            {
                this.Index = 0;
                this.ParentIndex = -1;
                this.m_level = 0;
            }
        }

        public void SubDivise(QuadTreeChildsArray<T> Array, int Level)
        {
            if (m_level >= Level)
            {
                CloseChilds(Array);
                return;
            }

            if (!HasChilds())
            {
                Closed = false;

                float MidSize = m_size * 0.5f;

                if (!HasChildArray())
                {
                    Array.GetIndex(ref StartIndex);
                    Array.Array[StartIndex] = new QuadTreeNode<T>(0, m_level, StartIndex, Index, m_position, MidSize);
                    Array.Array[StartIndex + 1] = new QuadTreeNode<T>(1, m_level, StartIndex, Index, m_position + new Vector3(0, 0, MidSize), MidSize);
                    Array.Array[StartIndex + 2] = new QuadTreeNode<T>(2, m_level, StartIndex, Index, m_position + new Vector3(MidSize, 0, MidSize), MidSize);
                    Array.Array[StartIndex + 3] = new QuadTreeNode<T>(3, m_level, StartIndex, Index, m_position + new Vector3(MidSize, 0, 0), MidSize);
                }
                else
                {
                    Array.Array[StartIndex].Init(0, m_level, StartIndex, Index, m_position, MidSize);
                    Array.Array[StartIndex + 1].Init(1, m_level, StartIndex, Index, m_position + new Vector3(0, 0, MidSize), MidSize);
                    Array.Array[StartIndex + 2].Init(2, m_level, StartIndex, Index, m_position + new Vector3(MidSize, 0, MidSize), MidSize);
                    Array.Array[StartIndex + 3].Init(3, m_level, StartIndex, Index, m_position + new Vector3(MidSize, 0, 0), MidSize);
                }
            }

            Array.Array[StartIndex].SubDivise(Array, Level);
            Array.Array[StartIndex + 1].SubDivise(Array, Level);
            Array.Array[StartIndex + 2].SubDivise(Array, Level);
            Array.Array[StartIndex + 3].SubDivise(Array, Level);
        }

        public void Close(QuadTreeChildsArray<T> Array)
        {
            CloseChilds(Array);
        }

        public void Reset(QuadTreeChildsArray<T> Array)
        {
            Closed = true;
            if (HasChildArray())
            {
                float MidSize = m_size * 0.5f;
                Array.Array[StartIndex].Init(0, m_level, StartIndex, Index, m_position, MidSize);
                Array.Array[StartIndex + 1].Init(1, m_level, StartIndex, Index, m_position + new Vector3(0, 0, MidSize), MidSize);
                Array.Array[StartIndex + 2].Init(2, m_level, StartIndex, Index, m_position + new Vector3(MidSize, 0, MidSize), MidSize);
                Array.Array[StartIndex + 3].Init(3, m_level, StartIndex, Index, m_position + new Vector3(MidSize, 0, 0), MidSize);

                Array.Array[StartIndex].Reset(Array);
                Array.Array[StartIndex + 1].Reset(Array);
                Array.Array[StartIndex + 2].Reset(Array);
                Array.Array[StartIndex + 3].Reset(Array);
            }
        }

        public int GetOpenParent(QuadTreeChildsArray<T> Array)
        {
            if (ParentIndex == -1 || Array.Array[ParentIndex].HasChilds())
                return Index;

            return Array.Array[ParentIndex].GetOpenParent(Array);
        }

        public void GetArrayCount(QuadTreeChildsArray<T> Array, ref int Count)
        {
            if (HasChilds())
            {
                Count += 4;
                for (int i = 0; i < 4; ++i)
                    Array.Array[StartIndex + i].GetArrayCount(Array, ref Count);
            }
        }

        static public int GetMaxChilds(int MaxLevel)
        {
            int Count = 4;
            int Childs = 4;
            for (int i = 0; i < MaxLevel - 1; ++i)
            {
                Count += Childs * 4;
                Childs = Childs * 4;
            }

            return Count;
        }

        #region Childs

        public bool HasChilds()
        {
            if (!Closed && HasChildArray())
                return true;

            return false;
        }

        public bool HasChildArray()
        {
            return StartIndex != -1;
        }

        public void GetChilds(QuadTreeChildsArray<T> Array, List<int> L)
        {
            if (HasChilds())
            {
                Array.Array[StartIndex].GetChilds(Array, L);
                Array.Array[StartIndex + 1].GetChilds(Array, L);
                Array.Array[StartIndex + 2].GetChilds(Array, L);
                Array.Array[StartIndex + 3].GetChilds(Array, L);
            }
            else
                L.Add(Index);
        }

        public void GetAllChilds(QuadTreeChildsArray<T> Array, List<int> L)
        {
            L.Add(Index);
            if (StartIndex != -1)
            {
                Array.Array[StartIndex].GetAllChilds(Array, L);
                Array.Array[StartIndex + 1].GetAllChilds(Array, L);
                Array.Array[StartIndex + 2].GetAllChilds(Array, L);
                Array.Array[StartIndex + 3].GetAllChilds(Array, L);
            }
        }

        public void CloseChilds(QuadTreeChildsArray<T> Array)
        {
            if (HasChilds())
            {
                Closed = true;

                Array.Array[StartIndex].Close(Array);
                Array.Array[StartIndex + 1].Close(Array);
                Array.Array[StartIndex + 2].Close(Array);
                Array.Array[StartIndex + 3].Close(Array);
            }
        }

        public bool GetChild(QuadTreeChildsArray<T> Array, Vector3 Position, ref int NodeIndex)
        {
            if (Contains(Position))
            {
                if (HasChilds())
                {
                    if (Array.Array[StartIndex].GetChild(Array, Position, ref NodeIndex))
                        return true;
                    if (Array.Array[StartIndex + 1].GetChild(Array, Position, ref NodeIndex))
                        return true;
                    if (Array.Array[StartIndex + 2].GetChild(Array, Position, ref NodeIndex))
                        return true;
                    if (Array.Array[StartIndex + 3].GetChild(Array, Position, ref NodeIndex))
                        return true;
                }
                else
                {
                    NodeIndex = Index;
                    return true;
                }
            }

            return false;
        }

        public bool Contains(Vector3 Position)
        {
            if (Position.x >= m_position.x
                && Position.z >= m_position.z)
            {
                if (Position.x < m_position.x + m_size
                    && Position.z < m_position.z + m_size)
                {
                    return true;
                }
            }

            return false;
        }

        public bool ContainsAround(Vector3 Position, float Power)
        {
            float offset = 1f + (0.125f * m_level) * Power;
            if (Position.x >= m_position.x - m_size * offset
                && Position.z >= m_position.z - m_size * offset)
            {
                if (Position.x < m_position.x + m_size * (1f + offset)
                    && Position.z < m_position.z + m_size * (1f + offset))
                {
                    return true;
                }
            }

            return false;
        }

        #endregion

        #region Positions

        public Vector3 Right
        {
            get
            {
                return m_position + new Vector3(m_size, 0, 0);
            }
        }

        public Vector3 Forward
        {
            get
            {
                return m_position + new Vector3(0, 0, m_size);
            }
        }

        public Vector3 RightForward
        {
            get
            {
                return m_position + new Vector3(m_size, 0, m_size);
            }
        }

        #endregion

        public override string ToString()
        {
            return "Level:" + m_level + ",Index:" + Index + ",ParentIndex:" + ParentIndex;
        }
    }
}

[Kiwasi]

I stopped taking this seriously as soon as I saw using System.Linq.

How is this better then using a List?

I was particularly impressed with the implementation of AddSafe, which is not safe at all.

[Azmar]

This has the potential to be an amazing thread, I can feel it! OP needs benchmarks on this stuff, as I am slightly skeptical on some of them.

[Ostwind]

Should be in the scripting section…

[hippocoder]

Depends if it’s going to be just scripts.

[JamesLeeNZ]

Some of those belong in a meme… with that awkward dude with the braces… awkward steve maybe

“Fast List”

“Implements Array based version negating all benefits of list”

[roojerry]

@JamesLeeNZ

Some of those belong in a meme… with that awkward dude with the braces… awkward steve maybe

“Fast List”

“Implements Array based version negating all benefits of list”

[dyox]

You can just benchmark. (It does not use link)

Fast List :
And ‘AddSafe’ is not for thread use.
But for fast add a new element without checking the capacity of the array.
Example : add 10 vertices
Slist.CheckArray(10).
SList.AddSafe(p1);
SList.AddSafe(p2);
SList.AddSafe(p3);
etc…

For procedural mesh
//Vertices
SList.Add(A,B,C,D);
// Indices
SList.Add(0,1,2,3);

DoubleSize value :
Used when you know approx how many objects will be on the list.
List() double the capacity when limit reached. Not very useful when you know that you list will contains 1000 or 1500 or 2000 objects. You set a default capacity to 1000 and double size to 500. You will not have list with capacity of 2000 or 4000 when you only use 1500.

3D / 2D array, optimized for the garbage collector.

TransitionList avoid a lot of Lock(). And lock only one time to push all waiting elements on the working array. One TransitionList per thread. Only one thread using the working array.

When working on complex systems where a function is called billions of times this kind of optimization is very important.

But I’m glad you’re taking more time to create a meme that to read a code.

[sputnikbar]

“But I’m glad you’re taking more time to create a meme that to read a code.”

Et pan !

[Sarthak123]

Efficiency is more important I think.

[Zuntatos]

@JamesLeeNZ

System.Collections.Generic.List is array based as well.

You must be thinking of a LinkedList.

LinkedList is nearly always slower than a List, except for inserting/removing at a known position (you have the node).

[Dantus]

@dyox , this kind of optimization comes with a price! There are no exceptions which can make it a lot more difficult to debug the code. When you make a post like this one, it would be nice to see a warning at the very beginning that clearly mentions that, because it is important for many.
It is clearly visible how this is useful or more likely even required for your use cases. But for most projects, this is not needed and the safe variants of those classes are clearly preferable. There is a good reason that the Mono and .Net implementations have additional checks and throw exceptions. Their intention is definitely not to make it slower.

In my opinion, there is a good reason that this kind of code exists, but it has to be marked accordingly. Unfortunately you are missing that point. Even worse, you create the impression that the code does the same, but is additionally optimized, which is definitely not true. With appropriate labeling, this would be an awesome contribution!

[Kiwasi]

@dyox

And ‘AddSafe’ is not for thread use.

Convention. The term safe typically used to indicate one of several things.

• Thread safe
• Memory safe
• Will not throw an error

In your case the AddSafe method is actually less safe, it bypasses index checking for speed. That’s fine, but calling it safe is wrong.

And if you don’t use Linq, why have you got a using statement for it? That’s just sloppy.

You can see why I take the memes more seriously then your code?

[ZJP]

@Kiwasi

I stopped taking this seriously as soon as I saw using System.Linq.

My thought. Always read ‘NEVER use Linq if you think about performance/optimisation’

[JasonBricco]

This is great for my use case. Thanks!

[Ryiah]

@dyox

And ‘AddSafe’ is not for thread use.
But for fast add a new element without checking the capacity of the array.

If people are getting confused simply by looking at the name then you may want to consider a different name. How about calling it ‘AddUnchecked’ or ‘AddUnverified’? Anything that indicates it isn’t actually safe.

Adding a comment (ideally an XML documentation comment) that points this out would help too.

[Philip-Rowlands]

@ZJP

My thought. Always read ‘NEVER use Linq if you think about performance/optimisation’

Why not? What kind of performance impact does it have?

EDIT: I had a look around on StackOverflow, and I found this answer. So far, it hasn’t been a problem for me…but it’s something I’ll have to keep in mind.

[hippocoder]

Why not find out?