Mercurial > projects > dynamin
annotate dynamin/core/list.d @ 55:c138461bf845
Add focusing and other changes that are related
like descendantAdded/Removed events, Window.activated event, and updating List.
Window.state was also added, even though focusing does not depend on it.
| author | Jordan Miner <jminer7@gmail.com> |
|---|---|
| date | Sat, 08 Aug 2009 15:42:27 -0500 |
| parents | aa4efef0f0b1 |
| children | c2566ab82535 |
| rev | line source |
|---|---|
| 0 | 1 // Written in the D programming language |
| 2 // www.digitalmars.com/d/ | |
| 3 | |
| 4 /* | |
| 5 * The contents of this file are subject to the Mozilla Public License Version | |
| 6 * 1.1 (the "License"); you may not use this file except in compliance with | |
| 7 * the License. You may obtain a copy of the License at | |
| 8 * http://www.mozilla.org/MPL/ | |
| 9 * | |
| 10 * Software distributed under the License is distributed on an "AS IS" basis, | |
| 11 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License | |
| 12 * for the specific language governing rights and limitations under the | |
| 13 * License. | |
| 14 * | |
| 15 * The Original Code is the Dynamin library. | |
| 16 * | |
| 17 * The Initial Developer of the Original Code is Jordan Miner. | |
| 18 * Portions created by the Initial Developer are Copyright (C) 2006-2009 | |
| 19 * the Initial Developer. All Rights Reserved. | |
| 20 * | |
| 21 * Contributor(s): | |
| 22 * Jordan Miner <jminer7@gmail.com> | |
| 23 * | |
| 24 */ | |
| 25 | |
| 26 module dynamin.core.list; | |
| 27 | |
| 28 import dynamin.core.global; | |
| 29 import dynamin.core.string; | |
| 30 import dynamin.core.math; | |
| 31 import tango.io.Stdout; | |
| 32 | |
| 33 // TODO: QuickSearch() | |
| 34 // TODO: BinarySearch() | |
| 35 // MUST use (high + low) >>> 1 to find the average | |
| 36 // TODO: Search() | |
| 37 // TODO: QuickSort() | |
| 38 // TODO: HeapSort() | |
| 39 // TODO: Sort() - calls HeapSort() so stable sort is default | |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
40 class List(T, bool hasDelegates = false) { |
| 0 | 41 protected: |
| 42 T[] _data; | |
| 43 uint _count; | |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
44 static if(hasDelegates) { |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
45 void delegate(T, int) whenAdded; |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
46 void delegate(T, int) whenRemoved; |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
47 } |
| 0 | 48 public: |
| 49 this() { | |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
50 this(16); |
| 0 | 51 } |
| 52 this(uint capacity) { | |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
53 _data = new T[capacity]; |
| 0 | 54 } |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
55 static if(hasDelegates) { |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
56 /// whenAdded or whenRemoved is called right after an item is added |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
57 /// or removed |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
58 this(void delegate(T, int) whenAdded, |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
59 void delegate(T, int) whenRemoved) { |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
60 this(16, whenAdded, whenRemoved); |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
61 } |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
62 this(uint capacity, void delegate(T, int) whenAdded, |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
63 void delegate(T, int) whenRemoved) { |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
64 this(capacity); |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
65 this.whenAdded = whenAdded; |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
66 this.whenRemoved = whenRemoved; |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
67 } |
| 0 | 68 } |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
69 static List!(T) fromArray(T[] arr...) { |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
70 auto list = new List!(T)(); |
| 0 | 71 list._data = arr.dup; |
| 72 list._count = arr.length; | |
| 73 return list; | |
| 74 } | |
| 75 uint count() { | |
| 76 return _count; | |
| 77 } | |
| 78 uint capacity() { | |
| 79 return _data.length; | |
| 80 } | |
| 81 T[] toArray() { | |
| 82 return _data[0.._count].dup; | |
| 83 } | |
| 84 T[] data() { | |
| 85 return _data[0.._count]; | |
| 86 } | |
| 87 /*string toString() { | |
| 88 string str = "["; | |
| 89 if(Count > 0) | |
| 90 str ~= ToString(this[0]); | |
| 91 foreach(item; this) { | |
| 92 str ~= ", "; | |
| 93 str ~= ToString(item); | |
| 94 } | |
| 95 str ~= "]"; | |
| 96 return str; | |
| 97 }*/ | |
| 98 protected void maybeEnlarge(uint neededCap) { | |
| 99 if(neededCap <= capacity) | |
| 100 return; | |
| 101 _data.length = max(neededCap, (capacity+1)*2); | |
| 102 } | |
| 103 T opIndex(uint index) { | |
| 104 return _data[0.._count][index]; | |
| 105 } | |
| 106 void push(T item) { | |
| 107 add(item); | |
| 108 } | |
| 109 T pop() { | |
| 110 if(_count < 1) | |
| 111 throw new Exception("List.Pop() - List is empty"); | |
| 112 T item = _data[_count-1]; | |
| 113 // must null out to allow to be collected | |
| 114 static if(is(T == class) || is(T == interface)) | |
| 115 _data[_count-1] = cast(T)null; | |
| 116 --_count; | |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
117 static if(hasDelegates) |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
118 whenRemoved(item, _count); |
| 0 | 119 return item; |
| 120 } | |
| 121 void add(T item) { | |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
122 insert(item, _count); |
| 0 | 123 } |
| 124 // TODO: AddRange? | |
| 125 void remove(T item) { | |
| 126 uint i = find(item); | |
| 127 if(i == -1) | |
| 128 return; | |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
129 |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
130 for(++i; i < _count; ++i) |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
131 _data[i-1] = _data[i]; |
| 0 | 132 // must null out to allow to be collected |
| 133 static if(is(T == class) || is(T == interface)) | |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
134 _data[_count-1] = cast(T)null; |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
135 --_count; |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
136 |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
137 static if(hasDelegates) |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
138 whenRemoved(item, i); |
| 0 | 139 } |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
140 void insert(T item, uint index) { |
| 0 | 141 maybeEnlarge(_count+1); |
| 142 arrayCopy!(T)(_data, index, _data, index+1, _count - index); | |
| 143 _data[index] = item; | |
| 144 ++_count; | |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
145 static if(hasDelegates) |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
146 whenAdded(item, index); |
| 0 | 147 } |
| 148 // TODO: InsertRange? | |
| 149 void clear() { | |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
150 for(; _count > 0; --_count) { |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
151 static if(hasDelegates) |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
152 whenRemoved(_data[_count-1], _count-1); |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
153 // must null out to allow to be collected |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
154 static if(is(T == class) || is(T == interface)) |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
155 data[_count-1] = cast(T)null; |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
156 } |
| 0 | 157 } |
| 158 uint find(T item) { | |
| 159 foreach(i, item2; _data) | |
| 160 if(item == item2) // if(item2 == item) would crash on a null item | |
| 161 return i; | |
| 162 return -1; | |
| 163 } | |
| 164 //trimCapacity() | |
| 165 //opIndex | |
| 166 //opIndexAssign | |
| 167 //opConcat | |
| 168 //opEquals | |
| 169 //opSlice | |
| 170 //opSliceAssign | |
| 171 int opApply(int delegate(inout T item) dg) { | |
| 172 for(uint i = 0; i < _count; ++i) { | |
| 173 if(int result = dg(_data[i])) | |
| 174 return result; | |
| 175 } | |
| 176 return 0; | |
| 177 } | |
| 178 //so you can do: | |
| 179 //foreach(i, item; list) | |
| 180 int opApply(int delegate(inout uint index, inout T item) dg) { | |
| 181 for(uint i = 0; i < _count; ++i) { | |
| 182 if(int result = dg(i, _data[i])) | |
| 183 return result; | |
| 184 } | |
| 185 return 0; | |
| 186 } | |
| 187 | |
| 188 } | |
| 189 unittest { | |
| 190 auto list = List!(char).fromArray("Hello, Mat"); | |
| 191 list.add('t'); | |
| 192 assert(list.data == "Hello, Matt"); | |
| 193 assert(list.pop() == 't'); | |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
194 assert(list.data == "Hello, Mat"); |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
195 list.insert('!', 5); |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
196 assert(list.data == "Hello!, Mat"); |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
197 list.remove('l'); |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
198 assert(list.data == "Helo!, Mat"); |
| 0 | 199 list.clear(); |
| 200 assert(list.data == ""); | |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
201 |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
202 int a = 0, r = 0; |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
203 void added(string, int) { a++; }; |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
204 void removed(string, int) { r++; }; |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
205 auto list2 = new List!(string, true)(&added, &removed); |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
206 assert(a == 0 && r == 0); |
| 0 | 207 list2.add("hello"); |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
208 assert(a == 1 && r == 0); |
| 0 | 209 assert(list2.pop() == "hello"); |
|
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
210 assert(a == 1 && r == 1); |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
211 |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
212 list2.add("Hi"); |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
213 list2.add("Jacob!"); |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
214 assert(a == 3 && r == 1); |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
215 list2.clear(); |
|
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
216 assert(a == 3 && r == 3); |
| 0 | 217 } |
| 218 |