Mercurial > projects > orange

comparison orange/util/collection/Array.d @ 1:11a31bd929f9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Removed dependency on private library
author Jacob Carlborg <doob@me.com>
date Mon, 31 May 2010 16:06:36 +0200
parents
children 99c52d46822a
comparison
equal deleted inserted replaced
0:f7b078e85f7f 1:11a31bd929f9
1 /**
2 * Copyright: Copyright (c) 2008-2009 Jacob Carlborg. All rights reserved.
3 * Authors: Jacob Carlborg
4 * Version: Initial created: 2008
5 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0)
6 *
7 */
8 module orange.util.collection.Array;
9
10 version (Tango)
11 {
12 static import tango.core.Array;
13 import tango.stdc.string : memmove;
14 static import tango.text.Util;
15 }
16
17 else
18 {
19 version = Phobos;
20
21 import std.c.string : memmove;
22 }
23
24 /**
25 * Inserts the specified element at the specified position in the array. Shifts the
26 * element currently at that position (if any) and any subsequent elements to the right.
27 *
28 * Params:
29 * arr = the array to insert the element into
30 * index = the index at which the specified element is to be inserted
31 * element = the element to be inserted
32 *
33 * Returns: the modified array
34 *
35 * Throws: AssertException if the length of the array is 0
36 * Throws: AssertException if the $(D_PARAM index) argument is
37 * greater than the length of this array.
38 */
39 T[] insert (T, U = size_t) (ref T[] arr, U index, T element)
40 in
41 {
42 assert(arr.length > 0, "mambo.collection.Array.insert: The length of the array was 0");
43 assert(index <= arr.length, "mambo.collection.Array.insert: The index was greater than the length of the array");
44 }
45 body
46 {
47 if (index == arr.length)
48 {
49 arr ~= element;
50 return arr;
51 }
52
53 else if (index == 0)
54 arr = element ~ arr;
55
56 else
57 arr = arr[0 .. index] ~ element ~ arr[index .. $];
58
59 return arr;
60 }
61
62 /**
63 * Inserts the specified elements at the specified position in the array. Shifts the
64 * element currently at that position (if any) and any subsequent elements to the right.
65 *
66 * Params:
67 * arr = the array to insert the element into
68 * index = the index at which the specified element is to be inserted
69 * element = the element to be inserted
70 *
71 * Returns: the modified array
72 *
73 * Throws: AssertException if the length of the array is 0
74 * Throws: AssertException if the $(D_PARAM index) argument is
75 * not less or equal than the length of this array.
76 */
77 T[] insert (T, U = size_t) (ref T[] arr, U index, T[] element)
78 in
79 {
80 assert(arr.length > 0, "mambo.collection.Array.insert: The length of the array was 0");
81 assert(index <= arr.length, "mambo.collection.Array.insert: The index was greater than the length of the array");
82 }
83 body
84 {
85 if (index == arr.length)
86 {
87 arr ~= element;
88 return arr;
89 }
90
91 else if (index == 0)
92 arr = element ~ arr;
93
94 else
95 arr = arr[0 .. index] ~ element ~ arr[index .. $];
96
97 return arr;
98 }
99
100 /**
101 * Inserts the specified element at the specified position in the array. Shifts the
102 * element currently at that position (if any) and any subsequent elements to the right.
103 *
104 * Params:
105 * arr = the array to add the element to
106 * index = the index at which the specified element is to be inserted
107 * element = the element to be inserted
108 *
109 * Returns: the modified array
110 *
111 * Throws: AssertException if the length of the array is 0
112 * Throws: AssertException if the $(D_PARAM index) argument is
113 * not less than the length of this array.
114 */
115 T[] add (T, U = size_t) (ref T[] arr, U index, T element)
116 in
117 {
118 assert(arr.length > 0, "mambo.collection.Array.add: The length of the array was 0");
119 assert(index <= arr.length, "mambo.collection.Array.add: The index was greater than the length of the array");
120 }
121 body
122 {
123 return insert(arr, index, element);
124 }
125
126 /**
127 * Appends the specified element to the end of the array.
128 *
129 * Params:
130 * arr = the array to add the element to
131 * element = element to be appended to this list
132 *
133 * Returns: the modified array
134 */
135 T[] add (T) (ref T[] arr, T element)
136 {
137 return arr ~= element;
138 }
139
140 /**
141 * Removes the element at the specified position in the array if it could find it and
142 * returns it. Shifts any subsequent elements to the left.
143 *
144 * Params:
145 * arr = the array to remove the element from
146 * index = the index of the element to be removed
147 *
148 * Returns: the element that was removed
149 *
150 * Throws: AssertException if the length of the array is 0
151 * Throws: AssertException if the $(D_PARAM index) argument is
152 * not less than the length of this array.
153 */
154 T remove (T, U = size_t) (ref T[] arr, U index)
155 in
156 {
157 assert(arr.length > 0, "mambo.collection.Array.remove: The length of the array was 0");
158 assert(index < arr.length, "mambo.collection.Array.remove: The index was greater than the length of the array");
159 }
160 body
161 {
162 T ret = arr[index];
163
164 if (index == 0)
165 arr = arr[1 .. $];
166
167 else if (index == arr.length - 1)
168 arr = arr[0 .. $ - 1];
169
170 else
171 {
172 if (index < arr.length - 1)
173 memmove(&arr[index], &arr[index + 1], T.sizeof * (arr.length - index - 1));
174
175 arr.length = arr.length - 1;
176 }
177
178 return ret;
179 }
180
181 /**
182 * Removes the specified element from the array if it could find it and returns it.
183 * Shifts any subsequent elements to the left.
184 *
185 * Params:
186 * arr = the array to remove the element from
187 * element = the element to be removed
188 *
189 * Returns: the element that was removed or T.max
190 *
191 * Throws: AssertException if the length of the array is 0
192 */
193 T remove (T) (ref T[] arr, T element)
194 in
195 {
196 assert(arr.length > 0, "mambo.collection.Array.remove: The length of the array was 0");
197 }
198 out (result)
199 {
200 assert(result is element);
201 }
202 body
203 {
204 size_t index = arr.indexOf(element);
205
206 if (index == size_t.max)
207 return T.max;
208
209 return arr.remove(index);
210 }
211
212 /**
213 * Returns the index of the first occurrence of the specified element in the array, or
214 * U.max if the array does not contain the element.
215 *
216 * Params:
217 * arr = the array to get the index of the element from
218 * element = the element to find
219 * start = the index where to begin the search
220 *
221 * Returns: the index of the element or U.max if it's not in the array
222 *
223 * Throws: AssertException if the length of the array is 0
224 * Throws: AssertException if the return value is greater or
225 * equal to the length of the array.
226 */
227 U indexOf (T, U = size_t) (T[] arr, T element, U start = 0)
228 in
229 {
230 assert(start >= 0, "mambo.collection.Array.indexOf: The start index was less than 0");
231 }
232 body
233 {
234 version (Tango)
235 {
236 U index = tango.text.Util.locate(arr, element, start);
237
238 if (index == arr.length)
239 index = U.max;
240
241 return index;
242 }
243
244 else
245 {
246 if (start > arr.length)
247 start = arr.length;
248
249 for (U i = start; i < arr.length; i++)
250 if (arr[i] == element)
251 return i;
252
253 return U.max;
254 }
255 }
256
257 /**
258 * Returns $(D_KEYWORD true) if the array contains the specified element.
259 *
260 * Params:
261 * arr = the array to check if it contains the element
262 * element = the element whose presence in the array is to be tested
263 *
264 * Returns: $(D_KEYWORD true) if the array contains the specified element
265 *
266 * Throws: AssertException if the length of the array is 0
267 */
268 bool contains (T) (T[] arr, T element)
269 in
270 {
271 assert(arr.length > 0, "mambo.collection.Array.contains: The length of the array was 0");
272 }
273 body
274 {
275 return arr.indexOf!(T, size_t)(element) < size_t.max;
276 }
277
278 /**
279 * Returns $(D_KEYWORD true) if this array contains no elements.
280 *
281 * Params:
282 * arr = the array to check if it's empty
283 *
284 * Returns: $(D_KEYWORD true) if this array contains no elements
285 */
286 bool isEmpty (T) (T[] arr)
287 {
288 return arr.length == 0;
289 }
290
291 /**
292 * Returns $(D_KEYWORD true) if this array contains no elements.
293 *
294 * Params:
295 * arr = the array to check if it's empty
296 *
297 * Returns: $(D_KEYWORD true) if this array contains no elements
298 */
299 alias isEmpty empty;
300
301 /**
302 * Removes all of the elements from this array. The array will be empty after this call
303 * returns.
304 *
305 * Params:
306 * arr = the array to clear
307 *
308 * Returns: the cleared array
309 *
310 * Throws: AssertException if length of the return array isn't 0
311 */
312 T[] clear (T) (T[] arr)
313 out (result)
314 {
315 assert(result.length == 0, "mambo.collection.Array.clear: The length of the resulting array was not 0");
316 }
317 body
318 {
319 return arr.length = 0;
320 }
321
322 /**
323 * Returns the element at the specified position in the array.
324 *
325 * Params:
326 * arr = the array to get the element from
327 * index = index of the element to return
328 *
329 * Returns: the element at the specified position in the array
330 *
331 * Throws: AssertException if the length of the array is 0
332 * Throws: AssertException if the $(D_PARAM index) argument is
333 * not less than the length of this array.
334 */
335 T get (T, U = size_t) (T[] arr, U index)
336 in
337 {
338 assert(arr.length > 0, "mambo.collection.Array.get: The length of the array was 0");
339 assert(index < arr.length, "mambo.collection.Array.get: The index was greater than the length of the array");
340 }
341 body
342 {
343 return arr[index];
344 }
345
346 /**
347 * Returns the index of the last occurrence of the specifed element
348 *
349 * Params:
350 * arr = the array to get the index of the element from
351 * element = the element to find the index of
352 *
353 * Returns: the index of the last occurrence of the element in the
354 * specified array, or U.max
355 * if the element does not occur.
356 *
357 * Throws: AssertException if the length of the array is 0
358 * Throws: AssertException if the return value is less than -1 or
359 * greater than the length of the array - 1.
360 */
361 U lastIndexOf (T, U = size_t) (T[] arr, T element)
362 in
363 {
364 assert(arr.length > 0, "mambo.collection.Array.lastIndexOf: The length of the array was 0");
365 }
366 body
367 {
368 version (Tango)
369 {
370 U index = tango.text.Util.locatePrior(arr, element);
371
372 if (index == arr.length)
373 return U.max;
374
375 return index;
376 }
377
378 else
379 {
380 foreach_reverse (i, e ; arr)
381 if (e is element)
382 return i;
383
384 return U.max;
385 }
386 }
387
388 /**
389 * Returns the number of elements in the specified array.
390 *
391 * Params:
392 * arr = the array to get the number of elements from
393 *
394 * Returns: the number of elements in this list
395 */
396 U size (T, U = size_t) (T[] arr)
397 {
398 return arr.length;
399 }
400
401 /**
402 * Finds the first occurence of element in arr
403 *
404 * Params:
405 * arr = the array to find the element in
406 * element = the element to find
407 * start = at which position to start finding
408 *
409 * Returns: the index of the first match or U.max if no match was found.
410 */
411 alias indexOf find;
412
413 /**
414 * Replaces a section of $(D_PARAM arr) with elements starting at $(D_PARAM pos) ending
415 * $(D_PARAM n) elements after
416 *
417 * Params:
418 * arr = the array to do the replace in
419 * pos = position within the array of the first element of the section to be replaced
420 * n = length of the section to be replaced within the array
421 * elements = the elements to replace with
422 *
423 * Throws:
424 * AssertException if pos is greater than the length of the array
425 *
426 * Returns: the array
427 */
428 T[] replace (T, U = size_t) (ref T[] arr, U pos, U n, T[] elements)
429 in
430 {
431 assert(pos <= arr.length, "mambo.collection.Array.replace: The position was greter than the length of the array");
432 }
433 body
434 {
435 U i;
436 U nr = n;
437
438 if (nr > arr.length)
439 nr = arr.length - 1;
440
441 if (nr == elements.length)
442 {
443 U eIndex;
444
445 for (i = pos, eIndex = 0; i <= nr; i++, eIndex++)
446 arr[i] = elements[eIndex];
447
448 return arr;
449 }
450
451 else if (elements.length == 0)
452 {
453 U index = pos + n;
454
455 if (index >= arr.length)
456 index = arr.length;
457
458 return arr = arr[0 .. pos] ~ arr[index .. $];
459 }
460
461 else
462 {
463 U eIndex;
464
465 for (i = pos, eIndex = 0; eIndex < nr && i < arr.length && eIndex < elements.length; i++, eIndex++)
466 arr[i] = elements[eIndex];
467
468 // no positions left and elements are left in elements, insert elements
469 if (eIndex < elements.length)
470 return arr = arr[0 .. i] ~ elements[eIndex .. $] ~ arr[i .. $];
471
472 // positions left to replace but no elements, remove those positions
473 else if (nr > eIndex)
474 {
475 U index = pos + nr;
476
477 if (index >= arr.length)
478 index = arr.length;
479
480 return arr = arr[0 .. pos + eIndex] ~ arr[index .. $];
481 }
482
483 }
484
485 return arr;
486 }
487
488 /**
489 * Erases a part of the array content, shortening the length of the array.
490 *
491 * Params:
492 * arr = the array to erase elements from
493 * start = the position within the array of the first element to be erased
494 * n = amount of elements to be removed. It may remove less elements if the
495 * end of the array is reached before the n elements have been erased.
496 * The default value of n indicates that all the elements until the end
497 * of the array should be erased.
498 *
499 * Throws:
500 * AssertException if pos is greater than the length of the array
501 *
502 * Returns: the array
503 */
504 T[] erase (T, U = size_t) (ref T[] arr, U start = 0, U n = U.max)
505 in
506 {
507 assert(start <= arr.length, "mambo.collection.Array.erase: The start position was greater than the length of the array");
508 }
509 body
510 {
511 U end;
512
513 if (n == U.max)
514 end = arr.length;
515
516 else
517 {
518 end = start + n;
519
520 if (end > arr.length)
521 end = arr.length;
522 }
523
524 return arr = arr[0 .. start] ~ arr[end .. $];
525 }
526
527 /**
528 * Compares to arrays. Returns 0 if the content matches, less than zero
529 * if a is "less" than b, or greater than zero where a is "bigger".
530 *
531 * Params:
532 * a = the first array
533 * b = the second array
534 * end = the index where the comparision will end
535 *
536 * Returns: Returns 0 if the content matches, less than zero if a is
537 * "less" than b, or greater than zero where a is "bigger".
538 */
539 int compare (T, U = size_t) (T[] a, T[] b, U end = U.max)
540 {
541 U ia = end;
542 U ib = end;
543
544 if (ia > a.length)
545 ia = a.length;
546
547 if (ib > b.length)
548 ib = b.length;
549
550 return typeid(T[]).compare(&a[0 .. ia], &b[0 .. ib]);
551 }
552
553 /**
554 * Compares the content of the given array to the content of a comparing
555 * array, which is formed according to the arguments passed.
556 *
557 * The function returns 0 if all the elements in the compared contents compare
558 * equal, a negative value if the first element that does not match compares to
559 * less in the array than in the comparing array, and a positive value in
560 * the opposite case.
561 *
562 * Params:
563 * a = the first array to compare with
564 * pos = position of the beginning of the compared slice, i.e. the first element in the array (in a) to be compared against the comparing array.
565 * n = length of the compared slice.
566 * b = array with the content to be used as comparing array.
567 *
568 * Returns: 0 if the compared array are equal, otherwise a number different from 0 is returned, with its sign indicating whether the array is considered greater than the comparing array passed as parameter (positive sign), or smaller (negative sign).
569 *
570 * Throws: AssertException if pos is specified with a position greater than the length of the corresponding array
571 */
572 int compare (T, U = size_t) (T[] a, size_t pos, size_t n, T[] b)
573 in
574 {
575 assert(pos <= b.length);
576 }
577 body
578 {
579 U end = pos + n;
580
581 if (end > b.length)
582 end = b.length;
583
584 return typeid(T[]).compare(&b[pos .. end], &a[0 .. $]);
585 }
586
587 /**
588 * Reserves the given amount of allocated storage for the given array.
589 *
590 * Params:
591 * a = the array to reserve allocated storage for
592 * capacity = the amount of allocated storage to be reserved
593 */
594 void reserve (T) (ref T[] a, size_t amount = 0)
595 {
596 a = (new T[amount])[0 .. 0];
597 }
598
599 /**
600 * Returns true if a begins with b
601 *
602 * Params:
603 * a = the array to
604 * b =
605 *
606 * Returns: true if a begins with b, otherwise false
607 */
608 bool beginsWith (T) (T[] a, T[] b)
609 {
610 return a.length > b.length && a[0 .. b.length] == b;
611 }
612
613 /**
614 * Returns true if a ends with b
615 *
616 * Params:
617 * a = the array to
618 * b =
619 *
620 * Returns: true if a ends with b, otherwise false
621 */
622 bool endsWith (T) (T[] a, T[] b)
623 {
624 return a.length > b.length && a[$ - b.length .. $] == b;
625 }