1 package frost.collections
2
3 uses frost.unsafe.Pointer
4
5 ====================================================================================================
6 Standard implementation of the `List` interface. `Array` is a resizable random-access array,
7 featuring constant time reads and writes. Appending new elements to the array can be expensive, as
8 it may require the backing store to be increased in size which in turn may require a memory copy.
9
10 Particularly for bigger arrays, it is best to avoid this expensive size increase by pre-allocating
11 the array with the expected number of elements it will contain using [init(Int)].
12 ====================================================================================================
13 class Array<T> : List<T> {
14 @private
15 constant DEFAULT_CAPACITY := 16
16
17 @private
18 var _count := 0
19
20 @private
21 var capacity:Int
22
23 @private
24 var data:Pointer<T>
25
26 ================================================================================================
27 Creates a new, empty `Array`.
28 ================================================================================================
29 init() {
30 init(DEFAULT_CAPACITY)
31 }
32
33 ================================================================================================
34 Creates a new, empty `Array` with the specified maximum capacity. The `Array` will allocate
35 enough memory to hold `capacity` elements at the time of its creation.
36 ================================================================================================
37 init(capacity:Int) {
38 self.capacity := capacity
39 data := Pointer<T>.alloc(capacity)
40 }
41
42 ================================================================================================
43 Creates a new `Array` containing all the elements in another collection.
44 ================================================================================================
45 init(other:CollectionView<T>) {
46 init(other.count.max(DEFAULT_CAPACITY))
47 for v in other {
48 add(v)
49 }
50 }
51
52 ================================================================================================
53 Creates a new `Array` containing `count` copies of `value`.
54 ================================================================================================
55 init(count:Int, value:T) {
56 init(capacity)
57 for i in 0 .. count {
58 add(value)
59 }
60 }
61
62 ================================================================================================
63 Creates a new `Array` containing `count` values produced by `generator`. `generator` is called
64 `count` times, starting with the parameter `0` and ending with `count - 1`.
65 ================================================================================================
66 init(count:Int, generator:(Int)=&>(T)) {
67 init(capacity)
68 for i in 0 .. count {
69 add(generator(i))
70 }
71 }
72
73 @private
74 init(data:Pointer<T>, count:Int) {
75 self.data := data->Pointer<T>
76 self._count := count
77 self.capacity := count
78 }
79
80 @override
81 method cleanup() {
82 clear()
83 data.destroy()
84 }
85
86 ================================================================================================
87 Returns an entry from this array.
88 ================================================================================================
89 @override
90 @priority(2)
91 function [](index:Int):T {
92 return data[index]
93 }
94
95 ================================================================================================
96 Returns a new array containing a slice of this array. The new array is an independent shallow
97 copy: they contain the same elements, so modifying to the elements will be visible in both
98 arrays, but modifications to the arrays themselves (adding / removing / replacing elements) will
99 not.
100 ================================================================================================
101 @priority(2)
102 function [](r:Range<Int>):Array<T> {
103 var max := r.max
104 if r.inclusive {
105 max += 1
106 }
107 def count := max - r.min
108 def result := Pointer<T>.alloc(count)
109 for i in 0 .. count {
110 result[i] := self[r.min + i]
111 }
112 return Array<T>(result, count)
113 }
114
115 ================================================================================================
116 Returns a new array containing a slice of this array. The new array is an independent shallow
117 copy: they contain the same elements, so modifying to the elements will be visible in both
118 arrays, but modifications to the arrays themselves (adding / removing / replacing elements) will
119 not.
120 ================================================================================================
121 @priority(1)
122 function [](r:Range<Int?>):Array<T> {
123 def start:Int
124 if r.min !== null {
125 start := r.min
126 }
127 else {
128 start := 0
129 }
130
131 var end:Int
132 if r.max !== null {
133 end := r.max
134 }
135 else {
136 end := count
137 if r.inclusive {
138 end -= 1
139 }
140 }
141 return self[Range<Int>(start, end, r.inclusive)]
142 }
143
144 ================================================================================================
145 Replaces an element in this array with a new element.
146 ================================================================================================
147 @override
148 method []:=(index:Int, value:T) {
149 data[index] := value
150 }
151
152 @override
153 method insert(index:Int, value:T) {
154 -- FIXME performance, this is horrendously slow
155 ensureCapacity(count + 1)
156 for i in count .. index by -1 {
157 data[i] := data[i - 1->Int]
158 }
159 _count += 1
160 data[index] := value
161 }
162
163 @override
164 method add(value:T) {
165 ensureCapacity(_count + 1)
166 data[_count] := value
167 _count += 1
168 }
169
170 @override
171 method addAll(c:CollectionView<T>) {
172 ensureCapacity(_count + c.count)
173 for v in c {
174 data[_count] := v
175 _count += 1
176 }
177 }
178
179 @private
180 method ensureCapacity(newCapacity:Int) {
181 if newCapacity <= capacity {
182 return
183 }
184 def oldCapacity := capacity
185 capacity := capacity.max(1)
186 while capacity < newCapacity {< newCapacity {
187 capacity *= 2
188 }
189 data := data.realloc(oldCapacity, capacity)
190 }
191
192 @override
193 function get_count():Int {
194 return _count
195 }
196
197 @override
198 method removeIndex(index:Int):T {
199 -- FIXME performance, this is horrendously slow
200 def result := self[index]
201 for i in index .. _count - 1 {
202 self[i] := self[i + 1]
203 }
204 _count -= 1
205 data.clear(_count)
206 return result
207 }
208
209 @override
210 method clear() {
211 _count := 0
212 for i in 0 .. capacity {
213 data.clear(i)
214 }
215 }
216
217 ================================================================================================
218 As [ListView.filter((T)=>(Bit))], but returns an `Array`.
219 ================================================================================================
220 @priority(2)
221 function filter(predicate:(T)=>(Bit)):Array<T> {
222 def result := Array<T>()
223 for v in self {
224 if predicate(v) {
225 result.add(v)
226 }
227 }
228 return result
229 }
230
231 ================================================================================================
232 As [ListView.filter((T)=&>(Bit))], but returns an `Array`.
233 ================================================================================================
234 @priority(2)
235 method filter(predicate:(T)=&>(Bit)):Array<T> {
236 def result := Array<T>()
237 for v in self {
238 if predicate(v) {
239 result.add(v)
240 }
241 }
242 return result
243 }
244
245 ================================================================================================
246 As [ListView.combine(ListView<U>)], but returns an `Array`.
247 ================================================================================================
248 @priority(2)
249 @pre(count = other.count)
250 function combine<U>(other:ListView<U>):Array<(T, U)> {
251 def result := Array<(T, U)>(count)
252 for i in 0 .. count {
253 result.add((self[i], other[i]))
254 }
255 return result
256 }
257
258 ================================================================================================
259 As [ListView.combine(ListView<U>, (T, U)=>(V))], but returns an `Array`.
260 ================================================================================================
261 @priority(4)
262 @pre(count = other.count)
263 function combine<U, V>(other:ListView<U>, f:(T, U)=>(V)):Array<V> {
264 def result := Array<V>(count)
265 for i in 0 .. count {
266 result.add(f(self[i], other[i]))
267 }
268 return result
269 }
270
271 ================================================================================================
272 As [ListView.combine(ListView<U>, (T, U)=&>(V))], but returns an `Array`.
273 ================================================================================================
274 @priority(3)
275 @pre(count = other.count)
276 method combine<U, V>(other:ListView<U>, f:(T, U)=&>(V)):Array<V> {
277 def result := Array<V>(count)
278 for i in 0 .. count {
279 result.add(f(self[i], other[i]))
280 }
281 return result
282 }
283
284 ================================================================================================
285 As [ListView.sort], but returns an `Array`.
286 ================================================================================================
287 @priority(1)
288 method sort(greater:(T, T)=>(Bit)):Array<T> {
289 def result := Array<T>(self)
290 MergeSort.sort(result, greater)
291 return result
292 }
293
294 @override
295 function get_toString():String {
296 def result := MutableString()
297 result.append("[")
298 var separator := ""
299 for v in self {
300 result.append(separator)
301 separator := ", "
302 -- FIXME cast shouldn't be necessary
303 if v->Object? !== null {
304 result.append(v)
305 }
306 else {
307 result.append("<null>")
308 }
309 }
310 result.append("]")
311 return result.finish()
312 }
313 }
314