diff options
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: |