|
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
|
|
|
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
|
