lib: some update towards more use of new constructors
[nit.git] / lib / standard / collection / array.nit
1 # This file is part of NIT ( http://www.nitlanguage.org ).
2 #
3 # Copyright 2004-2008 Jean Privat <jean@pryen.org>
4 # Copyright 2008 Floréal Morandat <morandat@lirmm.fr>
5 #
6 # This file is free software, which comes along with NIT. This software is
7 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
8 # without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
9 # PARTICULAR PURPOSE. You can modify it is you want, provided this header
10 # is kept unaltered, and a notification of the changes is added.
11 # You are allowed to redistribute it and sell it, alone or is a part of
12 # another product.
13
14 # This module introduces the standard array structure.
15 # It also implements two other abstract collections : ArrayMap and ArraySet
16 module array
17
18 import abstract_collection
19
20 # One dimension array of objects.
21 abstract class AbstractArrayRead[E]
22 super SequenceRead[E]
23
24 redef var length = 0
25
26 redef fun is_empty do return _length == 0
27
28 redef fun has(item)
29 do
30 var i = 0
31 var l = length
32 while i < l do
33 if self[i] == item then return true
34 i += 1
35 end
36 return false
37 end
38
39 redef fun has_only(item)
40 do
41 var i = 0
42 var l = length
43 while i < l do
44 if self[i] != item then return false
45 i += 1
46 end
47 return true
48 end
49
50 redef fun count(item)
51 do
52 var res = 0
53 var i = 0
54 var l = length
55 while i < l do
56 if self[i] == item then res += 1
57 i += 1
58 end
59 return res
60 end
61
62 redef fun index_of(item) do return index_of_from(item, 0)
63
64 redef fun last_index_of(item: E): Int do return last_index_of_from(item, length-1)
65
66 redef fun index_of_from(item: E, pos: Int): Int
67 do
68 var i = pos
69 var len = length
70 while i < len do
71 if self[i] == item then
72 return i
73 end
74 i += 1
75 end
76 return -1
77 end
78
79 redef fun last_index_of_from(item: E, pos: Int): Int
80 do
81 var i = pos
82 while i >= 0 do
83 if self[i] == item then
84 return i
85 else
86 i -= 1
87 end
88 end
89 return -1
90 end
91
92 # Return a new array that is the reverse of `self`
93 #
94 # assert [1,2,3].reversed == [3, 2, 1]
95 fun reversed: Array[E]
96 do
97 var cmp = _length
98 var result = new Array[E].with_capacity(cmp)
99 while cmp > 0 do
100 cmp -= 1
101 result.add(self[cmp])
102 end
103 return result
104 end
105
106 # Copy a portion of `self` to an other array.
107 #
108 # var a = [1, 2, 3, 4]
109 # var b = [10, 20, 30, 40, 50]
110 # a.copy_to(1, 2, b, 2)
111 # assert b == [10, 20, 2, 3, 50]
112 protected fun copy_to(start: Int, len: Int, dest: AbstractArray[E], new_start: Int)
113 do
114 # TODO native one
115 var i = len
116 while i > 0 do
117 i -= 1
118 dest[new_start+i] = self[start+i]
119 end
120 end
121
122 redef fun output
123 do
124 var i = 0
125 var l = length
126 while i < l do
127 var e = self[i]
128 if e != null then e.output
129 i += 1
130 end
131 end
132
133 redef fun iterator: ArrayIterator[E] do return new ArrayIterator[E](self)
134 redef fun reverse_iterator do return new ArrayReverseIterator[E](self)
135 end
136
137 # Resizable one dimension array of objects.
138 abstract class AbstractArray[E]
139 super AbstractArrayRead[E]
140 super Sequence[E]
141
142 # Force the capacity to be at least `cap`.
143 # The capacity of the array is an internal information.
144 # However, this method can be used to prepare a large amount of add
145 fun enlarge(cap: Int) is abstract
146
147 redef fun push(item) do add(item)
148
149 redef fun pop
150 do
151 assert not_empty: not is_empty
152 var r = last
153 _length -= 1
154 return r
155 end
156
157 redef fun shift
158 do
159 assert not_empty: not is_empty
160 var r = first
161 var i = 1
162 var l = length
163 while i < l do
164 self[i-1] = self[i]
165 i += 1
166 end
167 _length = l - 1
168 return r
169 end
170
171 redef fun unshift(item)
172 do
173 var i = length - 1
174 while i >= 0 do
175 self[i+1] = self[i]
176 i -= 1
177 end
178 self[0] = item
179 end
180
181 redef fun insert(item: E, pos: Int)
182 do
183 enlarge(length + 1)
184 copy_to(pos, length-pos, self, pos + 1)
185 self[pos] = item
186 end
187
188 redef fun insert_all(coll, pos)
189 do
190 var l = coll.length
191 if l == 0 then return
192 enlarge(length + l)
193 _length += l
194 copy_to(pos, length-pos-l, self, pos + l)
195 for c in coll do
196 self[pos] = c
197 pos += 1
198 end
199 end
200
201 redef fun add(item) do self[length] = item
202
203 redef fun clear do _length = 0
204
205 redef fun remove(item) do remove_at(index_of(item))
206
207 redef fun remove_all(item)
208 do
209 var i = index_of(item)
210 while i >= 0 do
211 remove_at(i)
212 i = index_of_from(item, i)
213 end
214 end
215
216 redef fun remove_at(i)
217 do
218 var l = length
219 if i >= 0 and i < l then
220 var j = i + 1
221 while j < l do
222 self[j-1] = self[j]
223 j += 1
224 end
225 _length = l - 1
226 end
227 end
228
229 # Invert two elements in the array
230 #
231 # var a = [10, 20, 30, 40]
232 # a.swap_at(1, 3)
233 # assert a == [10, 40, 30, 20]
234 fun swap_at(a: Int,b: Int)
235 do
236 var e = self[a]
237 self[a] = self[b]
238 self[b] = e
239 end
240 end
241
242 # Resizable one dimension array of objects.
243 #
244 # Arrays have a literal representation.
245 # var a = [12, 32, 8]
246 # # is equivalent with:
247 # var b = new Array[Int]
248 # b.push(12)
249 # b.push(32)
250 # b.push(8)
251 # assert a == b
252 class Array[E]
253 super AbstractArray[E]
254 super ArrayCapable[E]
255
256 redef fun [](index)
257 do
258 assert index: index >= 0 and index < _length
259 return _items[index]
260 end
261
262 redef fun []=(index, item)
263 do
264 assert index: index >= 0 and index < _length + 1
265 if _capacity <= index then
266 enlarge(index + 1)
267 end
268 if _length <= index then
269 _length = index + 1
270 end
271 _items[index] = item
272 end
273
274 redef fun add(item)
275 do
276 var l = _length
277 if _capacity <= l then
278 enlarge(l + 1)
279 end
280 _length = l + 1
281 _items[l] = item
282 end
283
284 redef fun enlarge(cap)
285 do
286 var c = _capacity
287 if cap <= c then return
288 while c <= cap do c = c * 2 + 2
289 var a = calloc_array(c)
290 if _capacity > 0 then _items.copy_to(a, _length)
291 _items = a
292 _capacity = c
293 end
294
295 # Create an empty array.
296 init
297 do
298 _capacity = 0
299 _length = 0
300 end
301
302 # Create an array from a collection.
303 init from(items: Collection[E]) do
304 with_capacity(items.length)
305 self.add_all(items)
306 end
307
308 # Create an array with some `objects`.
309 init with_items(objects: E...)
310 do
311 _items = objects._items
312 _capacity = objects._capacity
313 _length = objects.length
314 end
315
316 # Create an empty array with a given capacity.
317 init with_capacity(cap: Int)
318 do
319 assert positive: cap >= 0
320 _items = calloc_array(cap)
321 _capacity = cap
322 _length = 0
323 end
324
325 # Create an array of `count` elements
326 init filled_with(value: E, count: Int)
327 do
328 assert positive: count >= 0
329 _items = calloc_array(count)
330 _capacity = count
331 _length = count
332 var i = 0
333 while i < count do
334 self[i] = value
335 i += 1
336 end
337 end
338
339 # Create a array filled with a given native array.
340 init with_native(nat: NativeArray[E], size: Int)
341 do
342 assert positive: size >= 0
343 _items = nat
344 _capacity = size
345 _length = size
346 end
347
348 # The internal storage.
349 private var items: nullable NativeArray[E] = null
350
351 # Do not use this method
352 # FIXME: Remove it once modules can intrude non local modules
353 fun intern_items: NativeArray[E] do return _items.as(not null)
354
355 # The size of `_items`.
356 private var capacity: Int = 0
357
358 redef fun ==(o)
359 do
360 if not o isa Array[nullable Object] then return super
361 # Efficient implementation
362 var l = length
363 if l != o.length then return false
364 var i = 0
365 var it = _items
366 var oit = o._items
367 while i < l do
368 if it[i] != oit[i] then return false
369 i += 1
370 end
371 return true
372 end
373 end
374
375 # An `Iterator` on `AbstractArray`
376 private class ArrayIterator[E]
377 super IndexedIterator[E]
378
379 redef fun item do return _array[_index]
380
381 # redef fun item=(e) do _array[_index] = e
382
383 redef fun is_ok do return _index < _array.length
384
385 redef fun next do _index += 1
386
387 init(a: AbstractArrayRead[E])
388 do
389 _array = a
390 _index = 0
391 end
392
393 redef var index = 0
394
395 private var array: AbstractArrayRead[E]
396 end
397
398 private class ArrayReverseIterator[E]
399 super ArrayIterator[E]
400
401 redef fun is_ok do return _index >= 0
402
403 redef fun next do _index -= 1
404
405 init(a: AbstractArrayRead[E])
406 do
407 _array = a
408 _index = a.length - 1
409 end
410 end
411
412 # Others collections ##########################################################
413
414 # A set implemented with an Array.
415 class ArraySet[E: Object]
416 super Set[E]
417
418 # The stored elements.
419 private var array: Array[E] is noinit
420
421 redef fun has(e) do return _array.has(e)
422
423 redef fun add(e) do if not _array.has(e) then _array.add(e)
424
425 redef fun is_empty do return _array.is_empty
426
427 redef fun length do return _array.length
428
429 redef fun first
430 do
431 assert _array.length > 0
432 return _array.first
433 end
434
435 redef fun remove(item)
436 do
437 var i = _array.index_of(item)
438 if i >= 0 then remove_at(i)
439 end
440
441 redef fun remove_all(item) do remove(item)
442
443 redef fun clear do _array.clear
444
445 redef fun iterator do return new ArraySetIterator[E](_array.iterator)
446
447 # Assume the capacity is at least `cap`.
448 fun enlarge(cap: Int) do _array.enlarge(cap)
449
450 private fun remove_at(i: Int)
451 do
452 _array[i] = _array.last
453 _array.pop
454 end
455
456 # Create an empty set
457 init do _array = new Array[E]
458
459 # Create an empty set with a given capacity.
460 init with_capacity(i: Int) do _array = new Array[E].with_capacity(i)
461
462 redef fun new_set do return new ArraySet[E]
463 end
464
465 # Iterators on sets implemented with arrays.
466 private class ArraySetIterator[E: Object]
467 super Iterator[E]
468
469 redef fun is_ok do return _iter.is_ok
470
471 redef fun next do _iter.next
472
473 redef fun item: E do return _iter.item
474
475 init(iter: ArrayIterator[E]) do _iter = iter
476
477 private var iter: ArrayIterator[E]
478 end
479
480
481 # Associative arrays implemented with an array of (key, value) pairs.
482 class ArrayMap[K: Object, E]
483 super CoupleMap[K, E]
484
485 # O(n)
486 redef fun [](key)
487 do
488 var i = index(key)
489 if i >= 0 then
490 return _items[i].second
491 else
492 return provide_default_value(key)
493 end
494 end
495
496 # O(n)
497 redef fun []=(key, item)
498 do
499 var i = index(key)
500 if i >= 0 then
501 _items[i].second = item
502 else
503 _items.push(new Couple[K,E](key, item))
504 end
505 end
506
507 redef var keys: RemovableCollection[K] = new ArrayMapKeys[K, E](self)
508 redef var values: RemovableCollection[E] = new ArrayMapValues[K, E](self)
509
510 # O(1)
511 redef fun length do return _items.length
512
513 redef fun couple_iterator do return _items.iterator
514
515 redef fun is_empty do return _items.is_empty
516
517 redef fun clear do _items.clear
518
519 # Assume the capacity to be at least `cap`.
520 fun enlarge(cap: Int) do _items.enlarge(cap)
521
522 redef fun couple_at(key)
523 do
524 var i = index(key)
525 if i >= 0 then
526 return _items[i]
527 else
528 return null
529 end
530 end
531
532 # Internal storage.
533 private var items = new Array[Couple[K,E]]
534
535 # fast remove the ith element of the array
536 private fun remove_at_index(i: Int)
537 do
538 _items[i] = _items.last
539 _items.pop
540 end
541
542 # The last positive result given by a index(1) call
543 private var last_index: Int = 0
544
545 # Where is the `key` in `_item`?
546 # return -1 if not found
547 private fun index(key: K): Int
548 do
549 var l = _last_index
550 if l < _items.length and _items[l].first == key then return l
551
552 var i = 0
553 while i < _items.length do
554 if _items[i].first == key then
555 _last_index = i
556 return i
557 end
558 i += 1
559 end
560 return -1
561 end
562 end
563
564 private class ArrayMapKeys[K: Object, E]
565 super RemovableCollection[K]
566 # The original map
567 var map: ArrayMap[K, E]
568 redef fun count(k) do if self.has(k) then return 1 else return 0
569 redef fun first do return self.map._items.first.first
570 redef fun has(k) do return self.map.index(k) >= 0
571 redef fun has_only(k) do return (self.has(k) and self.length == 1) or self.is_empty
572 redef fun is_empty do return self.map.is_empty
573 redef fun length do return self.map.length
574 redef fun iterator do return new MapKeysIterator[K, E](self.map.iterator)
575 redef fun clear do self.map.clear
576 redef fun remove(key)
577 do
578 var i = self.map.index(key)
579 if i >= 0 then self.map.remove_at_index(i)
580 end
581 redef fun remove_all(key) do self.remove(key)
582 end
583
584 private class ArrayMapValues[K: Object, E]
585 super RemovableCollection[E]
586 # The original map
587 var map: ArrayMap[K, E]
588 redef fun first do return self.map._items.first.second
589 redef fun is_empty do return self.map.is_empty
590 redef fun length do return self.map.length
591 redef fun iterator do return new MapValuesIterator[K, E](self.map.iterator)
592
593 # O(n)
594 redef fun has(item)
595 do
596 for i in self.map._items do if i.second == item then return true
597 return false
598 end
599
600 # O(n)
601 redef fun has_only(item)
602 do
603 for i in self.map._items do if i.second != item then return false
604 return true
605 end
606
607 # O(n)
608 redef fun count(item)
609 do
610 var nb = 0
611 for i in self.map._items do if i.second == item then nb += 1
612 return nb
613 end
614
615 redef fun clear do self.map.clear
616
617 redef fun remove(item)
618 do
619 var map = self.map
620 var i = map._items.length - 1
621 while i >= 0 do
622 if map._items[i].second == item then
623 map.remove_at_index(i)
624 return
625 end
626 i -= 1
627 end
628 end
629
630 redef fun remove_all(item)
631 do
632 var map = self.map
633 var i = map._items.length - 1
634 while i >= 0 do
635 if map._items[i].second == item then
636 map.remove_at_index(i)
637 end
638 i -= 1
639 end
640 end
641 end
642
643 # Comparable array for comparable elements.
644 #
645 # For two arrays, if one is a prefix, then it is lower.
646 #
647 # ~~~
648 # var a12 = new ArrayCmp[nullable Int].with_items(1,2)
649 # var a123 = new ArrayCmp[nullable Int].with_items(1,2,3)
650 # assert a12 < a123
651 # ~~~
652 #
653 # Otherwise, the first element just after the longest
654 # common prefix gives the order between the two arrays.
655 #
656 # ~~~
657 # var a124 = new ArrayCmp[nullable Int].with_items(1,2,4)
658 # var a13 = new ArrayCmp[nullable Int].with_items(1,3)
659 # assert a12 < a123
660 # assert a123 < a13
661 # ~~~
662 #
663 # Obviously, two equal arrays are equal.
664 #
665 # ~~~
666 # var b12 = new ArrayCmp[nullable Int].with_items(1,2)
667 # assert (a12 <=> b12) == 0
668 # ~~~
669 #
670 # `null` is considered lower than any other elements.
671 # But is still greater than no element.
672 #
673 # ~~~
674 # var a12n = new ArrayCmp[nullable Int].with_items(1,2,null)
675 # assert a12n < a123
676 # assert a12 < a12n
677 # ~~~
678 class ArrayCmp[E: nullable Comparable]
679 super Array[E]
680 super Comparable
681 redef type OTHER: ArrayCmp[E] is fixed
682
683 redef fun <(o) do return (self <=> o) < 0
684
685 redef fun <=>(o)
686 do
687 var it = _items
688 var oit = o._items
689 var i = 0
690 var l = length
691 var ol = o.length
692 var len
693 if l < ol then len = l else len = ol
694 while i < len do
695 var a = it[i]
696 var b = oit[i]
697 if a != null then
698 if b == null then return 1
699 var d = a <=> b.as(Comparable)
700 if d != 0 then return d
701 else
702 if b != null then return -1
703 end
704 i += 1
705 end
706 return l <=> ol
707 end
708 end
709
710 # Others tools ################################################################
711
712 redef class Iterator[E]
713 # Interate on `self` and build an array
714 fun to_a: Array[E]
715 do
716 var res = new Array[E]
717 while is_ok do
718 res.add(item)
719 next
720 end
721 return res
722 end
723 end
724
725 redef class Collection[E]
726 # Build a new array from a collection
727 fun to_a: Array[E]
728 do
729 var res = new Array[E].with_capacity(length)
730 res.add_all(self)
731 return res
732 end
733 end
734
735 # Native classes ##############################################################
736
737 # Subclasses of this class can create native arrays
738 interface ArrayCapable[E]
739 # Get a new array of `size` elements.
740 protected fun calloc_array(size: Int): NativeArray[E] is intern
741 end
742
743 # Native Nit array
744 # Access are unchecked and it has a fixed size
745 # Not for public use: may become private.
746 universal NativeArray[E]
747 # Creates a new NativeArray of capacity `length`
748 new(length: Int) is intern
749 # The length of the array
750 fun length: Int is intern
751 # Use `self` to initialize a standard Nit Array.
752 fun to_a: Array[E] do return new Array[E].with_native(self, length)
753 fun [](index: Int): E is intern
754 fun []=(index: Int, item: E) is intern
755 fun copy_to(dest: NativeArray[E], length: Int) is intern
756 #fun =(o: NativeArray[E]): Bool is intern
757 #fun !=(o: NativeArray[E]): Bool is intern
758 end