*miscHEADmaster

12 files changed, 595 insertions, 0 deletions

diff --git a/Assets/CollectionsExt/BinarySearchTree.cs b/Assets/CollectionsExt/BinarySearchTree.cs
new file mode 100644
index 0000000..ef6118a
--- /dev/null
+++ b/Assets/CollectionsExt/BinarySearchTree.cs
@@ -0,0 +1,18 @@
+锘縰sing 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/Assets/CollectionsExt/BinarySearchTree.cs.meta b/Assets/CollectionsExt/BinarySearchTree.cs.meta
new file mode 100644
index 0000000..7dd1f7c
--- /dev/null
+++ b/Assets/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/Assets/CollectionsExt/GraphUtility.cs b/Assets/CollectionsExt/GraphUtility.cs
new file mode 100644
index 0000000..f0f9dfb
--- /dev/null
+++ b/Assets/CollectionsExt/GraphUtility.cs
@@ -0,0 +1,13 @@
+锘縰sing System.Collections;

+using System.Collections.Generic;

+using UnityEngine;

+

+namespace CollectionsExt

+{

+

+    public static class GraphUtility

+    {

+

+    }

+

+}

diff --git a/Assets/CollectionsExt/GraphUtility.cs.meta b/Assets/CollectionsExt/GraphUtility.cs.meta
new file mode 100644
index 0000000..90acebd
--- /dev/null
+++ b/Assets/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/Assets/CollectionsExt/IndexedSet.cs b/Assets/CollectionsExt/IndexedSet.cs
new file mode 100644
index 0000000..9a9d865
--- /dev/null
+++ b/Assets/CollectionsExt/IndexedSet.cs
@@ -0,0 +1,162 @@
+using System;
+using System.Collections;
+using System.Collections.Generic;
+
+namespace CollectionsExt
+{

+    // 如果需要高频率的插入、删除、访问容器中的唯一数据，使用这个结构。比单独的List效率高，因为

+    // 哈希表的访问时间O(1)要快于遍历List确定数据唯一性的时间O(n)
+
+    // 空间换时间，综合了list（数组）和字典（哈希表）的优点，支持
+    // 1. 快速的随机访问
+    // 2. 快速的插入和删除
+    // 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/Assets/CollectionsExt/IndexedSet.cs.meta b/Assets/CollectionsExt/IndexedSet.cs.meta
new file mode 100644
index 0000000..1f6bc6d
--- /dev/null
+++ b/Assets/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/Assets/CollectionsExt/MaxHeap.cs b/Assets/CollectionsExt/MaxHeap.cs
new file mode 100644
index 0000000..09066f1
--- /dev/null
+++ b/Assets/CollectionsExt/MaxHeap.cs
@@ -0,0 +1,158 @@
+锘縰sing 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/Assets/CollectionsExt/MaxHeap.cs.meta b/Assets/CollectionsExt/MaxHeap.cs.meta
new file mode 100644
index 0000000..b15e928
--- /dev/null
+++ b/Assets/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/Assets/CollectionsExt/MinHeap.cs b/Assets/CollectionsExt/MinHeap.cs
new file mode 100644
index 0000000..68ddabb
--- /dev/null
+++ b/Assets/CollectionsExt/MinHeap.cs
@@ -0,0 +1,160 @@
+锘縰sing System;
+using System.Collections.Generic;
+
+namespace CollectionsExt
+{
+    // 鏈�灏忓爢锛屽爢椤舵槸鏈�灏忓�笺��
+    // 濡傛灉闇�瑕佺淮鎶や竴涓紭鍏堥槦鍒楋紝鐢ㄥ爢缁撴瀯锛岃皟鍫嗙殑鏁堢巼鏄疧(logn)蹇簬閬嶅巻鐨凮(n)
+    public class MinHeap<T>
+    {
+        private const int InitialCapacity = 4;
+
+        private T[] _arr;
+        private int _lastItemIndex;
+        private IComparer<T> _comparer;
+
+        public MinHeap()
+            : this(InitialCapacity, Comparer<T>.Default)
+        {
+        }
+
+        public MinHeap(int capacity)
+            : this(capacity, Comparer<T>.Default)
+        {
+        }
+
+        public MinHeap(Comparison<T> comparison)
+            : this(InitialCapacity, Comparer<T>.Create(comparison))
+        {
+        }
+
+        public MinHeap(IComparer<T> comparer)
+            : this(InitialCapacity, comparer)
+        {
+        }
+
+        public MinHeap(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;
+
+            MinHeapifyUp(_lastItemIndex);
+        }
+
+        public T Remove()
+        {
+            if (_lastItemIndex == -1)
+            {
+                throw new InvalidOperationException("The heap is empty");
+            }
+
+            T removedItem = _arr[0];
+            _arr[0] = _arr[_lastItemIndex];
+            _lastItemIndex--;
+
+            MinHeapifyDown(0);
+
+            return removedItem;
+        }
+
+        public T Peek()
+        {
+            if (_lastItemIndex == -1)
+            {
+                throw new InvalidOperationException("The heap is empty");
+            }
+
+            return _arr[0];
+        }
+
+        public void Clear()
+        {
+            _lastItemIndex = -1;
+        }
+
+        // 璋冨爢,O(logn)
+        private void MinHeapifyUp(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;
+
+                // 閫掑綊
+                MinHeapifyUp(parentIndex);
+            }
+        }
+
+        // 璋冨爢,O(logn)
+        private void MinHeapifyDown(int index)
+        {
+            int leftChildIndex = index * 2 + 1;
+            int rightChildIndex = index * 2 + 2;
+            int smallestItemIndex = index; // The index of the parent
+
+            if (leftChildIndex <= _lastItemIndex &&
+                _comparer.Compare(_arr[leftChildIndex], _arr[smallestItemIndex]) < 0)
+            {
+                smallestItemIndex = leftChildIndex;
+            }
+
+            if (rightChildIndex <= _lastItemIndex &&
+                _comparer.Compare(_arr[rightChildIndex], _arr[smallestItemIndex]) < 0)
+            {
+                smallestItemIndex = rightChildIndex;
+            }
+
+            if (smallestItemIndex != index)
+            {
+                // swap the parent with the smallest of the child items
+                T temp = _arr[index];
+                _arr[index] = _arr[smallestItemIndex];
+                _arr[smallestItemIndex] = temp;
+
+                MinHeapifyDown(smallestItemIndex);
+            }
+        }
+
+        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/Assets/CollectionsExt/MinHeap.cs.meta b/Assets/CollectionsExt/MinHeap.cs.meta
new file mode 100644
index 0000000..d06ef93
--- /dev/null
+++ b/Assets/CollectionsExt/MinHeap.cs.meta
@@ -0,0 +1,11 @@
+fileFormatVersion: 2
+guid: 7957fc1b317c31b4f94f56d48073da22
+MonoImporter:
+  externalObjects: {}
+  serializedVersion: 2
+  defaultReferences: []
+  executionOrder: 0
+  icon: {instanceID: 0}
+  userData: 
+  assetBundleName: 
+  assetBundleVariant: 
diff --git a/Assets/CollectionsExt/SkipList.cs b/Assets/CollectionsExt/SkipList.cs
new file mode 100644
index 0000000..5320f0b
--- /dev/null
+++ b/Assets/CollectionsExt/SkipList.cs
@@ -0,0 +1,18 @@
+锘縰sing 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/Assets/CollectionsExt/SkipList.cs.meta b/Assets/CollectionsExt/SkipList.cs.meta
new file mode 100644
index 0000000..0caa332
--- /dev/null
+++ b/Assets/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: