1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
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;
}
}
}
}
|
