Mercurial > projects > dynamin

comparison dynamin/core/list.d @ 0:aa4efef0f0b1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial commit of code.
author Jordan Miner <jminer7@gmail.com>
date Mon, 15 Jun 2009 22:10:48 -0500
parents
children c138461bf845
comparison
equal deleted inserted replaced
-1:000000000000 0:aa4efef0f0b1
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
40 // TODO: when D has template inheritance, have separate const_List and List
41 class List(T) {
42 protected:
43 T[] _data;
44 uint _count;
45 void delegate() whenChanged; // TODO: have an index and length...
46 public:
47 this() {
48 this(16, {});
49 }
50 this(uint capacity) {
51 this(capacity, {});
52 }
53 this(void delegate() whenChanged) {
54 this(16, whenChanged);
55 }
56 this(uint capacity, void delegate() whenChanged) {
57 _data = new T[capacity];
58 this.whenChanged = whenChanged;
59 }
60 static List fromArray(T[] arr...) {
61 List list = new List!(T)();
62 list._data = arr.dup;
63 list._count = arr.length;
64 return list;
65 }
66 uint count() {
67 return _count;
68 }
69 uint capacity() {
70 return _data.length;
71 }
72 T[] toArray() {
73 return _data[0.._count].dup;
74 }
75 T[] data() {
76 return _data[0.._count];
77 }
78 /*string toString() {
79 string str = "[";
80 if(Count > 0)
81 str ~= ToString(this[0]);
82 foreach(item; this) {
83 str ~= ", ";
84 str ~= ToString(item);
85 }
86 str ~= "]";
87 return str;
88 }*/
89 protected void maybeEnlarge(uint neededCap) {
90 if(neededCap <= capacity)
91 return;
92 _data.length = max(neededCap, (capacity+1)*2);
93 }
94 T opIndex(uint index) {
95 return _data[0.._count][index];
96 }
97 void push(T item) {
98 add(item);
99 }
100 T pop() {
101 if(_count < 1)
102 throw new Exception("List.Pop() - List is empty");
103 T item = _data[_count-1];
104 // must null out to allow to be collected
105 static if(is(T == class) || is(T == interface))
106 _data[_count-1] = cast(T)null;
107 --_count;
108 whenChanged();
109 return item;
110 }
111 void add(T item) {
112 insert(_count, item);
113 }
114 // TODO: AddRange?
115 void remove(T item) {
116 uint i = find(item);
117 if(i == -1)
118 return;
119 removeRange(i);
120 }
121 void removeRange(uint index, uint length = 1) {
122 arrayCopy!(T)(_data, index+length, _data, index, _count - (index+length));
123 // must null out to allow to be collected
124 static if(is(T == class) || is(T == interface))
125 for(uint i = _count-length; i < _count; ++i)
126 _data[i] = cast(T)null;
127 _count -= length;
128 whenChanged();
129 }
130 void insert(uint index, T item) {
131 maybeEnlarge(_count+1);
132 arrayCopy!(T)(_data, index, _data, index+1, _count - index);
133 _data[index] = item;
134 ++_count;
135 whenChanged();
136 }
137 // TODO: InsertRange?
138 void clear() {
139 // must null out to allow to be collected
140 static if(is(T == class) || is(T == interface))
141 for(uint i = 0; i < count; ++i)
142 data[i] = cast(T)null;
143 _count = 0;
144 whenChanged();
145 }
146 uint find(T item) {
147 foreach(i, item2; _data)
148 if(item == item2) // if(item2 == item) would crash on a null item
149 return i;
150 return -1;
151 }
152 //trimCapacity()
153 //opIndex
154 //opIndexAssign
155 //opConcat
156 //opEquals
157 //opSlice
158 //opSliceAssign
159 int opApply(int delegate(inout T item) dg) {
160 for(uint i = 0; i < _count; ++i) {
161 if(int result = dg(_data[i]))
162 return result;
163 }
164 return 0;
165 }
166 //so you can do:
167 //foreach(i, item; list)
168 int opApply(int delegate(inout uint index, inout T item) dg) {
169 for(uint i = 0; i < _count; ++i) {
170 if(int result = dg(i, _data[i]))
171 return result;
172 }
173 return 0;
174 }
175
176 }
177 unittest {
178 auto list = List!(char).fromArray("Hello, Mat");
179 list.add('t');
180 assert(list.data == "Hello, Matt");
181 assert(list.pop() == 't');
182 list.removeRange(1, 7);
183 assert(list.data == "Hat");
184 list.clear();
185 assert(list.data == "");
186 auto list2 = new List!(string);
187 list2.add("hello");
188 assert(list2.pop() == "hello");
189 }
190