*misc

16 files changed, 462 insertions, 2 deletions

diff --git a/UnityCollection/Assets/Infrastructure/CollectionExtends.meta b/UnityCollection/Assets/Infrastructure/CollectionsExt.meta
index 3b91f43..3b91f43 100644
--- a/UnityCollection/Assets/Infrastructure/CollectionExtends.meta
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt.meta
diff --git a/UnityCollection/Assets/Infrastructure/CollectionsExt/Algorithm.meta b/UnityCollection/Assets/Infrastructure/CollectionsExt/Algorithm.meta
new file mode 100644
index 0000000..43d5050
--- /dev/null
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/Algorithm.meta
@@ -0,0 +1,8 @@
+fileFormatVersion: 2
+guid: a9bec1ede7fb14a41af93bbef82ad271
+folderAsset: yes
+DefaultImporter:
+  externalObjects: {}
+  userData: 
+  assetBundleName: 
+  assetBundleVariant: 
diff --git a/UnityCollection/Assets/Infrastructure/CollectionsExt/Algorithm/SortingUtility.cs b/UnityCollection/Assets/Infrastructure/CollectionsExt/Algorithm/SortingUtility.cs
new file mode 100644
index 0000000..ff2a015
--- /dev/null
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/Algorithm/SortingUtility.cs
@@ -0,0 +1,14 @@
+using System.Collections;

+using System.Collections.Generic;

+using UnityEngine;

+

+namespace CollectionsExt.Algorithm

+{

+

+    // 排序

+    public static class SortingUtility

+    {

+

+    }

+

+}

diff --git a/UnityCollection/Assets/Infrastructure/CollectionsExt/Algorithm/SortingUtility.cs.meta b/UnityCollection/Assets/Infrastructure/CollectionsExt/Algorithm/SortingUtility.cs.meta
new file mode 100644
index 0000000..c266e6f
--- /dev/null
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/Algorithm/SortingUtility.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 44830cea9cf8b3c4db4aca7e7357d5d6
+MonoImporter:
+  externalObjects: {}
+  serializedVersion: 2
+  defaultReferences: []
+  executionOrder: 0
+  icon: {instanceID: 0}
+  userData: 
+  assetBundleName: 
+  assetBundleVariant: 
diff --git a/UnityCollection/Assets/Infrastructure/CollectionsExt/BinarySearchTree.cs b/UnityCollection/Assets/Infrastructure/CollectionsExt/BinarySearchTree.cs
new file mode 100644
index 0000000..ef6118a
--- /dev/null
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/BinarySearchTree.cs
@@ -0,0 +1,18 @@
+using System.Collections;

+using System.Collections.Generic;

+using UnityEngine;

+

+public class BinarySearchTree : MonoBehaviour

+{

+    // Start is called before the first frame update

+    void Start()

+    {

+        

+    }

+

+    // Update is called once per frame

+    void Update()

+    {

+        

+    }

+}

diff --git a/UnityCollection/Assets/Infrastructure/CollectionsExt/BinarySearchTree.cs.meta b/UnityCollection/Assets/Infrastructure/CollectionsExt/BinarySearchTree.cs.meta
new file mode 100644
index 0000000..7dd1f7c
--- /dev/null
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/BinarySearchTree.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 40581e5f59b91df409fbdb0ed8ac6a61
+MonoImporter:
+  externalObjects: {}
+  serializedVersion: 2
+  defaultReferences: []
+  executionOrder: 0
+  icon: {instanceID: 0}
+  userData: 
+  assetBundleName: 
+  assetBundleVariant: 
diff --git a/UnityCollection/Assets/Infrastructure/CollectionsExt/GraphUtility.cs b/UnityCollection/Assets/Infrastructure/CollectionsExt/GraphUtility.cs
new file mode 100644
index 0000000..f0f9dfb
--- /dev/null
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/GraphUtility.cs
@@ -0,0 +1,13 @@
+using System.Collections;

+using System.Collections.Generic;

+using UnityEngine;

+

+namespace CollectionsExt

+{

+

+    public static class GraphUtility

+    {

+

+    }

+

+}

diff --git a/UnityCollection/Assets/Infrastructure/CollectionsExt/GraphUtility.cs.meta b/UnityCollection/Assets/Infrastructure/CollectionsExt/GraphUtility.cs.meta
new file mode 100644
index 0000000..90acebd
--- /dev/null
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/GraphUtility.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 3f941530f721cda449eab3504920060e
+MonoImporter:
+  externalObjects: {}
+  serializedVersion: 2
+  defaultReferences: []
+  executionOrder: 0
+  icon: {instanceID: 0}
+  userData: 
+  assetBundleName: 
+  assetBundleVariant: 
diff --git a/UnityCollection/Assets/Infrastructure/CollectionsExt/IndexedSet.cs b/UnityCollection/Assets/Infrastructure/CollectionsExt/IndexedSet.cs
new file mode 100644
index 0000000..9a9d865
--- /dev/null
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/IndexedSet.cs
@@ -0,0 +1,162 @@
+using System;
+using System.Collections;
+using System.Collections.Generic;
+
+namespace CollectionsExt
+{

+    // �����Ҫ��Ƶ�ʵIJ��롢ɾ�������������е�Ψһ���ݣ�ʹ������ṹ���ȵ�����ListЧ�ʸߣ���Ϊ

+    // ��ϣ���ķ���ʱ��O(1)Ҫ���ڱ���Listȷ������Ψһ�Ե�ʱ��O(n)
+
+    // �ռ任ʱ�䣬�ۺ���list�����飩���ֵ䣨��ϣ�������ŵ㣬֧��
+    // 1. ���ٵ��������
+    // 2. ���ٵIJ����ɾ��
+    // 3. Ψһֵ
+    // 4. ˳�����
+    // 5. ����
+    internal class IndexedSet<T> : IList<T>
+    {
+        //This is a container that gives:
+        //  - Unique items
+        //  - Fast random removal
+        //  - Fast unique inclusion to the end
+        //  - Sequential access
+        //Downsides:
+        //  - Uses more memory
+        //  - Ordering is not persistent
+        //  - Not Serialization Friendly.
+
+        //We use a Dictionary to speed up list lookup, this makes it cheaper to guarantee no duplicates (set)
+        //When removing we move the last item to the removed item position, this way we only need to update the index cache of a single item. (fast removal)
+        //Order of the elements is not guaranteed. A removal will change the order of the items.
+
+        readonly List<T> m_List = new List<T>();
+        Dictionary<T, int> m_Dictionary = new Dictionary<T, int>();
+
+        public void Add(T item)
+        {
+            m_List.Add(item);
+            m_Dictionary.Add(item, m_List.Count - 1);
+        }
+
+        public bool AddUnique(T item)
+        {
+            if (m_Dictionary.ContainsKey(item))
+                return false;
+
+            m_List.Add(item);
+            m_Dictionary.Add(item, m_List.Count - 1);
+
+            return true;
+        }
+
+        public bool Remove(T item)
+        {
+            int index = -1;
+            if (!m_Dictionary.TryGetValue(item, out index))
+                return false;
+
+            RemoveAt(index);
+            return true;
+        }
+
+        public IEnumerator<T> GetEnumerator()
+        {
+            throw new System.NotImplementedException();
+        }
+
+        IEnumerator IEnumerable.GetEnumerator()
+        {
+            return GetEnumerator();
+        }
+
+        public void Clear()
+        {
+            m_List.Clear();
+            m_Dictionary.Clear();
+        }
+
+        public bool Contains(T item)
+        {
+            return m_Dictionary.ContainsKey(item);
+        }
+
+        public void CopyTo(T[] array, int arrayIndex)
+        {
+            m_List.CopyTo(array, arrayIndex);
+        }
+
+        public int Count { get { return m_List.Count; } }
+        public bool IsReadOnly { get { return false; } }
+        public int IndexOf(T item)
+        {
+            int index = -1;
+            m_Dictionary.TryGetValue(item, out index);
+            return index;
+        }
+
+        public void Insert(int index, T item)
+        {
+            //We could support this, but the semantics would be weird. Order is not guaranteed..
+            throw new NotSupportedException("Random Insertion is semantically invalid, since this structure does not guarantee ordering.");
+        }
+
+        public void RemoveAt(int index)
+        {
+            T item = m_List[index];
+            m_Dictionary.Remove(item);
+            if (index == m_List.Count - 1)
+                m_List.RemoveAt(index);
+            else
+            {
+                // ����
+                int replaceItemIndex = m_List.Count - 1;
+                T replaceItem = m_List[replaceItemIndex];
+                m_List[index] = replaceItem;
+                m_Dictionary[replaceItem] = index;
+                m_List.RemoveAt(replaceItemIndex);
+            }
+        }
+
+        public T this[int index]
+        {
+            get { return m_List[index]; }
+            set
+            {
+                T item = m_List[index];
+                m_Dictionary.Remove(item);
+                m_List[index] = value;
+                m_Dictionary.Add(item, index); // ���������⣬Ӧ����value
+            }
+        }
+
+        public void RemoveAll(Predicate<T> match)
+        {
+            //I guess this could be optmized by instead of removing the items from the list immediatly,
+            //We move them to the end, and then remove all in one go.
+            //But I don't think this is going to be the bottleneck, so leaving as is for now.
+            int i = 0;
+            while (i < m_List.Count)
+            {
+                T item = m_List[i];
+                if (match(item))
+                    Remove(item);
+                else
+                    i++;
+            }
+        }
+
+        //Sorts the internal list, this makes the exposed index accessor sorted as well.
+        //But note that any insertion or deletion, can unorder the collection again.
+        public void Sort(Comparison<T> sortLayoutFunction)
+        {
+            //There might be better ways to sort and keep the dictionary index up to date.
+            m_List.Sort(sortLayoutFunction);
+            //Rebuild the dictionary index.
+            for (int i = 0; i < m_List.Count; ++i)
+            {
+                T item = m_List[i];
+                m_Dictionary[item] = i;
+            }
+        }
+    }
+}
diff --git a/UnityCollection/Assets/Infrastructure/CollectionsExt/IndexedSet.cs.meta b/UnityCollection/Assets/Infrastructure/CollectionsExt/IndexedSet.cs.meta
new file mode 100644
index 0000000..1f6bc6d
--- /dev/null
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/IndexedSet.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 4c58c0d2f281bac479b6b45c68043671
+MonoImporter:
+  externalObjects: {}
+  serializedVersion: 2
+  defaultReferences: []
+  executionOrder: 0
+  icon: {instanceID: 0}
+  userData: 
+  assetBundleName: 
+  assetBundleVariant: 
diff --git a/UnityCollection/Assets/Infrastructure/CollectionsExt/MaxHeap.cs b/UnityCollection/Assets/Infrastructure/CollectionsExt/MaxHeap.cs
new file mode 100644
index 0000000..09066f1
--- /dev/null
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/MaxHeap.cs
@@ -0,0 +1,158 @@
+using System;
+using System.Collections.Generic;
+
+namespace CollectionsExt
+{
+    // 最大堆
+    public class MaxHeap<T>
+    {
+        private const int InitialCapacity = 4;
+
+        private T[] _arr;
+        private int _lastItemIndex;
+        private IComparer<T> _comparer;
+
+        public MaxHeap()
+            : this(InitialCapacity, Comparer<T>.Default)
+        {
+        }
+
+        public MaxHeap(int capacity)
+            : this(capacity, Comparer<T>.Default)
+        {
+        }
+
+        public MaxHeap(Comparison<T> comparison)
+            : this(InitialCapacity, Comparer<T>.Create(comparison))
+        {
+        }
+
+        public MaxHeap(IComparer<T> comparer)
+            : this(InitialCapacity, comparer)
+        {
+        }
+
+        public MaxHeap(int capacity, IComparer<T> comparer)
+        {
+            _arr = new T[capacity];
+            _lastItemIndex = -1;
+            _comparer = comparer;
+        }
+
+        public int Count
+        {
+            get
+            {
+                return _lastItemIndex + 1;
+            }
+        }
+
+        public void Add(T item)
+        {
+            if (_lastItemIndex == _arr.Length - 1)
+            {
+                Resize();
+            }
+
+            _lastItemIndex++;
+            _arr[_lastItemIndex] = item;
+
+            MaxHeapifyUp(_lastItemIndex);
+        }
+
+        public T Remove()
+        {
+            if (_lastItemIndex == -1)
+            {
+                throw new InvalidOperationException("The heap is empty");
+            }
+
+            T removedItem = _arr[0];
+            _arr[0] = _arr[_lastItemIndex];
+            _lastItemIndex--;
+
+            MaxHeapifyDown(0);
+
+            return removedItem;
+        }
+
+        public T Peek()
+        {
+            if (_lastItemIndex == -1)
+            {
+                throw new InvalidOperationException("The heap is empty");
+            }
+
+            return _arr[0];
+        }
+
+        public void Clear()
+        {
+            _lastItemIndex = -1;
+        }
+
+        // 堆顶是最小值
+        private void MaxHeapifyUp(int index)
+        {
+            if (index == 0)
+            {
+                return;
+            }
+
+            int childIndex = index;
+            int parentIndex = (index - 1) / 2;
+
+            // 堆顶是最小值
+            if (_comparer.Compare(_arr[childIndex], _arr[parentIndex]) > 0)
+            {
+                // swap the parent and the child
+                T temp = _arr[childIndex];
+                _arr[childIndex] = _arr[parentIndex];
+                _arr[parentIndex] = temp;
+
+                // 递归
+                MaxHeapifyUp(parentIndex);
+            }
+        }
+
+        private void MaxHeapifyDown(int index)
+        {
+            int leftChildIndex = index * 2 + 1;
+            int rightChildIndex = index * 2 + 2;
+            int biggestItemIndex = index; // The index of the parent
+
+            if (leftChildIndex <= _lastItemIndex &&
+                _comparer.Compare(_arr[leftChildIndex], _arr[biggestItemIndex]) > 0)
+            {
+                biggestItemIndex = leftChildIndex;
+            }
+
+            if (rightChildIndex <= _lastItemIndex &&
+                _comparer.Compare(_arr[rightChildIndex], _arr[biggestItemIndex]) < 0)
+            {
+                biggestItemIndex = rightChildIndex;
+            }
+
+            if (biggestItemIndex != index)
+            {
+                // swap the parent with the biggest of the child items
+                T temp = _arr[index];
+                _arr[index] = _arr[biggestItemIndex];
+                _arr[biggestItemIndex] = temp;
+
+                MaxHeapifyDown(biggestItemIndex);
+            }
+        }
+
+        private void Resize()
+        {
+            T[] newArr = new T[_arr.Length * 2];
+            for (int i = 0; i < _arr.Length; i++)
+            {
+                newArr[i] = _arr[i];
+            }
+
+            _arr = newArr;
+        }
+    }
+}
diff --git a/UnityCollection/Assets/Infrastructure/CollectionsExt/MaxHeap.cs.meta b/UnityCollection/Assets/Infrastructure/CollectionsExt/MaxHeap.cs.meta
new file mode 100644
index 0000000..b15e928
--- /dev/null
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/MaxHeap.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 807a3d1c83110494bb638cb588b062b2
+MonoImporter:
+  externalObjects: {}
+  serializedVersion: 2
+  defaultReferences: []
+  executionOrder: 0
+  icon: {instanceID: 0}
+  userData: 
+  assetBundleName: 
+  assetBundleVariant: 
diff --git a/UnityCollection/Assets/Infrastructure/CollectionExtends/MinHeap.cs b/UnityCollection/Assets/Infrastructure/CollectionsExt/MinHeap.cs
index 420f146..68ddabb 100644
--- a/UnityCollection/Assets/Infrastructure/CollectionExtends/MinHeap.cs
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/MinHeap.cs
@@ -1,8 +1,10 @@
 using System;
 using System.Collections.Generic;
 
-namespace CollectionExtend
+namespace CollectionsExt
 {
+    // 最小堆，堆顶是最小值。
+    // 如果需要维护一个优先队列，用堆结构，调堆的效率是O(logn)快于遍历的O(n)
     public class MinHeap<T>
     {
         private const int InitialCapacity = 4;
@@ -90,7 +92,7 @@ namespace CollectionExtend
             _lastItemIndex = -1;
         }
 
-        // 堆顶是最小值
+        // 调堆,O(logn)
         private void MinHeapifyUp(int index)
         {
             if (index == 0)
@@ -114,6 +116,7 @@ namespace CollectionExtend
             }
         }
 
+        // 调堆,O(logn)
         private void MinHeapifyDown(int index)
         {
             int leftChildIndex = index * 2 + 1;
diff --git a/UnityCollection/Assets/Infrastructure/CollectionExtends/MinHeap.cs.meta b/UnityCollection/Assets/Infrastructure/CollectionsExt/MinHeap.cs.meta
index d06ef93..d06ef93 100644
--- a/UnityCollection/Assets/Infrastructure/CollectionExtends/MinHeap.cs.meta
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/MinHeap.cs.meta
diff --git a/UnityCollection/Assets/Infrastructure/CollectionsExt/SkipList.cs b/UnityCollection/Assets/Infrastructure/CollectionsExt/SkipList.cs
new file mode 100644
index 0000000..5320f0b
--- /dev/null
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/SkipList.cs
@@ -0,0 +1,18 @@
+using System.Collections;

+using System.Collections.Generic;

+using UnityEngine;

+

+public class SkipList : MonoBehaviour

+{

+    // Start is called before the first frame update

+    void Start()

+    {

+        

+    }

+

+    // Update is called once per frame

+    void Update()

+    {

+        

+    }

+}

diff --git a/UnityCollection/Assets/Infrastructure/CollectionsExt/SkipList.cs.meta b/UnityCollection/Assets/Infrastructure/CollectionsExt/SkipList.cs.meta
new file mode 100644
index 0000000..0caa332
--- /dev/null
+++ b/UnityCollection/Assets/Infrastructure/CollectionsExt/SkipList.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: a6e7d17f852ca7444869bdd26f25d4d0
+MonoImporter:
+  externalObjects: {}
+  serializedVersion: 2
+  defaultReferences: []
+  executionOrder: 0
+  icon: {instanceID: 0}
+  userData: 
+  assetBundleName: 
+  assetBundleVariant: