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
{
// ҪƵʵ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;
}
}
}
}
|
