Mercurial > projects > dynamin

comparison dynamin/core/list.d @ 83:3cfc83a99cbc

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add List.opIndexAssign and switch to one callback for change notification. Also, update controls to work with the new API.
author Jordan Miner <jminer7@gmail.com>
date Sun, 18 Jul 2010 22:20:50 -0500
parents de94552446ab
children 7653269724db
comparison
equal deleted inserted replaced
82:e52546f41851 83:3cfc83a99cbc
35 // MUST use (high + low) >>> 1 to find the average 35 // MUST use (high + low) >>> 1 to find the average
36 // TODO: Search() 36 // TODO: Search()
37 // TODO: QuickSort() 37 // TODO: QuickSort()
38 // TODO: HeapSort() 38 // TODO: HeapSort()
39 // TODO: Sort() - calls HeapSort() so stable sort is default 39 // TODO: Sort() - calls HeapSort() so stable sort is default
40 class List(T, bool hasDelegates = false) { 40
41 /// Represents the ways items can be changed in a list.
42 enum ListChangeType {
43 /// An item was added to the list.
44 Added,
45 /// An item was removed from the list.
46 Removed,
47 /// An item was replaced with another item.
48 Replaced
49 }
50
51 class List(T, bool changeNotification = false) {
41 protected: 52 protected:
42 T[] _data; 53 T[] _data;
43 uint _count; 54 uint _count;
44 static if(hasDelegates) { 55 static if(changeNotification)
45 void delegate(T, int) whenAdded; 56 void delegate(ListChangeType, T, T, uint) whenChanged;
46 void delegate(T, int) whenRemoved;
47 }
48 const int DefaultCapacity = 16; 57 const int DefaultCapacity = 16;
49 public: 58 public:
50 static if(hasDelegates) { 59 static if(changeNotification) {
51 /// whenAdded or whenRemoved is called right after an item is added 60 /// whenChanged is called right after an item is added, removed, or replaced
52 /// or removed 61 this(void delegate(ListChangeType, T, T, uint) whenChanged) {
53 this(void delegate(T, int) whenAdded, 62 this(DefaultCapacity, whenChanged);
54 void delegate(T, int) whenRemoved) {
55 this(DefaultCapacity, whenAdded, whenRemoved);
56 } 63 }
57 this(uint capacity, 64 this(uint capacity,
58 void delegate(T, int) whenAdded, 65 void delegate(ListChangeType, T, T, uint) whenChanged) {
59 void delegate(T, int) whenRemoved) {
60 _data = new T[capacity]; 66 _data = new T[capacity];
61 this.whenAdded = whenAdded; 67 this.whenChanged = whenChanged;
62 this.whenRemoved = whenRemoved;
63 } 68 }
64 } else { 69 } else {
65 this() { 70 this() {
66 this(DefaultCapacity); 71 this(DefaultCapacity);
67 } 72 }
103 return; 108 return;
104 _data.length = max(neededCap, (capacity+1)*2); 109 _data.length = max(neededCap, (capacity+1)*2);
105 } 110 }
106 T opIndex(uint index) { 111 T opIndex(uint index) {
107 return _data[0.._count][index]; 112 return _data[0.._count][index];
113 }
114 void opIndexAssign(T item, uint index) {
115 T oldItem = _data[0.._count][index];
116 _data[0.._count][index] = item;
117 static if(changeNotification)
118 whenChanged(ListChangeType.Replaced, oldItem, item, index);
108 } 119 }
109 void push(T item) { 120 void push(T item) {
110 add(item); 121 add(item);
111 } 122 }
112 T pop() { 123 T pop() {
115 T item = _data[_count-1]; 126 T item = _data[_count-1];
116 // must null out to allow to be collected 127 // must null out to allow to be collected
117 static if(is(T == class) || is(T == interface)) 128 static if(is(T == class) || is(T == interface))
118 _data[_count-1] = cast(T)null; 129 _data[_count-1] = cast(T)null;
119 --_count; 130 --_count;
120 static if(hasDelegates) 131 static if(changeNotification)
121 whenRemoved(item, _count); 132 whenChanged(ListChangeType.Removed, item, T.init, _count);
122 return item; 133 return item;
123 } 134 }
124 void add(T item) { 135 void add(T item) {
125 insert(item, _count); 136 insert(item, _count);
126 } 137 }
138 // must null out to allow to be collected 149 // must null out to allow to be collected
139 static if(is(T == class) || is(T == interface)) 150 static if(is(T == class) || is(T == interface))
140 _data[_count-1] = cast(T)null; 151 _data[_count-1] = cast(T)null;
141 --_count; 152 --_count;
142 153
143 static if(hasDelegates) 154 static if(changeNotification)
144 whenRemoved(item, index); 155 whenChanged(ListChangeType.Removed, item, T.init, index);
145 } 156 }
146 void insert(T item, uint index) { 157 void insert(T item, uint index) {
147 maybeEnlarge(_count+1); 158 maybeEnlarge(_count+1);
148 arrayCopy!(T)(_data, index, _data, index+1, _count - index); 159 arrayCopy!(T)(_data, index, _data, index+1, _count - index);
149 _data[index] = item; 160 _data[index] = item;
150 ++_count; 161 ++_count;
151 static if(hasDelegates) 162 static if(changeNotification)
152 whenAdded(item, index); 163 whenChanged(ListChangeType.Added, T.init, item, index);
153 } 164 }
154 void clear() { 165 void clear() {
155 for(; _count > 0; --_count) { 166 for(; _count > 0; --_count) {
156 static if(hasDelegates) 167 static if(changeNotification)
157 whenRemoved(_data[_count-1], _count-1); 168 whenChanged(ListChangeType.Removed, _data[_count-1], T.init, _count-1);
158 // must null out to allow to be collected 169 // must null out to allow to be collected
159 static if(is(T == class) || is(T == interface)) 170 static if(is(T == class) || is(T == interface))
160 data[_count-1] = cast(T)null; 171 data[_count-1] = cast(T)null;
161 } 172 }
162 } 173 }
208 list.removeAt(1); 219 list.removeAt(1);
209 assert(list.data == "eo!, Ma"); 220 assert(list.data == "eo!, Ma");
210 list.clear(); 221 list.clear();
211 assert(list.data == ""); 222 assert(list.data == "");
212 223
213 int a = 0, r = 0; 224 int a = 0, r = 0, r2 = 0;
214 void added(string, int) { a++; }; 225 void changed(ListChangeType t, string o, string n, uint) {
215 void removed(string, int) { r++; }; 226 if(t == ListChangeType.Added) {
216 auto list2 = new List!(string, true)(&added, &removed); 227 a++;
217 assert(a == 0 && r == 0); 228 assert(o == "" && n != "");
229 }
230 if(t == ListChangeType.Removed) {
231 r++;
232 assert(n == "" && o != "");
233 }
234 if(t == ListChangeType.Replaced) {
235 r2++;
236 }
237 };
238 auto list2 = new List!(string, true)(&changed);
239 assert(a == 0 && r == 0 && r2 == 0);
218 list2.add("hello"); 240 list2.add("hello");
219 assert(a == 1 && r == 0); 241 assert(a == 1 && r == 0 && r2 == 0);
220 assert(list2.pop() == "hello"); 242 assert(list2.pop() == "hello");
221 assert(a == 1 && r == 1); 243 assert(a == 1 && r == 1 && r2 == 0);
222 244
223 list2.add("Hi"); 245 list2.add("Hi");
224 list2.add("Jacob!"); 246 list2.add("Jacob");
225 assert(a == 3 && r == 1); 247 assert(a == 3 && r == 1 && r2 == 0);
248 list2[1] = "Matt";
249 assert(a == 3 && r == 1 && r2 == 1);
250 list2.insert("John", 1);
251 list2.insert("Pete", 3);
252 assert(list2.data == ["Hi", "John", "Matt", "Pete"]);
253 assert(a == 5 && r == 1 && r2 == 1);
254 list2.removeAt(0);
255 assert(list2.data == ["John", "Matt", "Pete"]);
256 assert(a == 5 && r == 2 && r2 == 1);
226 list2.clear(); 257 list2.clear();
227 assert(a == 3 && r == 3); 258 assert(a == 5 && r == 5 && r2 == 1);
228 } 259 }
229 260