Mercurial > projects > dynamin
annotate dynamin/core/list.d @ 80:f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
author | Jordan Miner <jminer7@gmail.com> |
---|---|
date | Sat, 17 Jul 2010 16:51:03 -0500 |
parents | c2566ab82535 |
children | de94552446ab |
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 } |
80
f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents:
56
diff
changeset
|
48 const int DefaultCapacity = 16; |
0 | 49 public: |
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
50 static if(hasDelegates) { |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
51 /// 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
|
52 /// or removed |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
53 this(void delegate(T, int) whenAdded, |
80
f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents:
56
diff
changeset
|
54 void delegate(T, int) whenRemoved) { |
f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents:
56
diff
changeset
|
55 this(DefaultCapacity, whenAdded, whenRemoved); |
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
56 } |
80
f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents:
56
diff
changeset
|
57 this(uint capacity, |
f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents:
56
diff
changeset
|
58 void delegate(T, int) whenAdded, |
f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents:
56
diff
changeset
|
59 void delegate(T, int) whenRemoved) { |
f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents:
56
diff
changeset
|
60 _data = new T[capacity]; |
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
61 this.whenAdded = whenAdded; |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
62 this.whenRemoved = whenRemoved; |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
63 } |
80
f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents:
56
diff
changeset
|
64 } else { |
f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents:
56
diff
changeset
|
65 this() { |
f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents:
56
diff
changeset
|
66 this(DefaultCapacity); |
f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents:
56
diff
changeset
|
67 } |
f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents:
56
diff
changeset
|
68 this(uint capacity) { |
f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents:
56
diff
changeset
|
69 _data = new T[capacity]; |
f1e176a76c00
Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents:
56
diff
changeset
|
70 } |
0 | 71 } |
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
72 static List!(T) fromArray(T[] arr...) { |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
73 auto list = new List!(T)(); |
0 | 74 list._data = arr.dup; |
75 list._count = arr.length; | |
76 return list; | |
77 } | |
78 uint count() { | |
79 return _count; | |
80 } | |
81 uint capacity() { | |
82 return _data.length; | |
83 } | |
84 T[] toArray() { | |
85 return _data[0.._count].dup; | |
86 } | |
87 T[] data() { | |
88 return _data[0.._count]; | |
89 } | |
90 /*string toString() { | |
91 string str = "["; | |
92 if(Count > 0) | |
93 str ~= ToString(this[0]); | |
94 foreach(item; this) { | |
95 str ~= ", "; | |
96 str ~= ToString(item); | |
97 } | |
98 str ~= "]"; | |
99 return str; | |
100 }*/ | |
101 protected void maybeEnlarge(uint neededCap) { | |
102 if(neededCap <= capacity) | |
103 return; | |
104 _data.length = max(neededCap, (capacity+1)*2); | |
105 } | |
106 T opIndex(uint index) { | |
107 return _data[0.._count][index]; | |
108 } | |
109 void push(T item) { | |
110 add(item); | |
111 } | |
112 T pop() { | |
113 if(_count < 1) | |
56
c2566ab82535
Edit comments and fix a typo.
Jordan Miner <jminer7@gmail.com>
parents:
55
diff
changeset
|
114 throw new Exception("List.pop() - List is empty"); |
0 | 115 T item = _data[_count-1]; |
116 // must null out to allow to be collected | |
117 static if(is(T == class) || is(T == interface)) | |
118 _data[_count-1] = cast(T)null; | |
119 --_count; | |
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
120 static if(hasDelegates) |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
121 whenRemoved(item, _count); |
0 | 122 return item; |
123 } | |
124 void add(T item) { | |
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
125 insert(item, _count); |
0 | 126 } |
127 void remove(T item) { | |
128 uint i = find(item); | |
129 if(i == -1) | |
130 return; | |
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
131 |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
132 for(++i; i < _count; ++i) |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
133 _data[i-1] = _data[i]; |
0 | 134 // must null out to allow to be collected |
135 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
|
136 _data[_count-1] = cast(T)null; |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
137 --_count; |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
138 |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
139 static if(hasDelegates) |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
140 whenRemoved(item, i); |
0 | 141 } |
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
142 void insert(T item, uint index) { |
0 | 143 maybeEnlarge(_count+1); |
144 arrayCopy!(T)(_data, index, _data, index+1, _count - index); | |
145 _data[index] = item; | |
146 ++_count; | |
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
147 static if(hasDelegates) |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
148 whenAdded(item, index); |
0 | 149 } |
150 void clear() { | |
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
151 for(; _count > 0; --_count) { |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
152 static if(hasDelegates) |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
153 whenRemoved(_data[_count-1], _count-1); |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
154 // 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
|
155 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
|
156 data[_count-1] = cast(T)null; |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
157 } |
0 | 158 } |
159 uint find(T item) { | |
160 foreach(i, item2; _data) | |
161 if(item == item2) // if(item2 == item) would crash on a null item | |
162 return i; | |
163 return -1; | |
164 } | |
165 //trimCapacity() | |
166 //opIndex | |
167 //opIndexAssign | |
168 //opConcat | |
169 //opEquals | |
170 //opSlice | |
171 //opSliceAssign | |
172 int opApply(int delegate(inout T item) dg) { | |
173 for(uint i = 0; i < _count; ++i) { | |
174 if(int result = dg(_data[i])) | |
175 return result; | |
176 } | |
177 return 0; | |
178 } | |
179 //so you can do: | |
180 //foreach(i, item; list) | |
181 int opApply(int delegate(inout uint index, inout T item) dg) { | |
182 for(uint i = 0; i < _count; ++i) { | |
183 if(int result = dg(i, _data[i])) | |
184 return result; | |
185 } | |
186 return 0; | |
187 } | |
188 | |
189 } | |
190 unittest { | |
191 auto list = List!(char).fromArray("Hello, Mat"); | |
192 list.add('t'); | |
193 assert(list.data == "Hello, Matt"); | |
194 assert(list.pop() == 't'); | |
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
195 assert(list.data == "Hello, Mat"); |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
196 list.insert('!', 5); |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
197 assert(list.data == "Hello!, Mat"); |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
198 list.remove('l'); |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
199 assert(list.data == "Helo!, Mat"); |
0 | 200 list.clear(); |
201 assert(list.data == ""); | |
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
202 |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
203 int a = 0, r = 0; |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
204 void added(string, int) { a++; }; |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
205 void removed(string, int) { r++; }; |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
206 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
|
207 assert(a == 0 && r == 0); |
0 | 208 list2.add("hello"); |
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
209 assert(a == 1 && r == 0); |
0 | 210 assert(list2.pop() == "hello"); |
55
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
211 assert(a == 1 && r == 1); |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
212 |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
213 list2.add("Hi"); |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
214 list2.add("Jacob!"); |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
215 assert(a == 3 && r == 1); |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
216 list2.clear(); |
c138461bf845
Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents:
0
diff
changeset
|
217 assert(a == 3 && r == 3); |
0 | 218 } |
219 |