1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2004-2008 Jean Privat <jean@pryen.org>
4 # Copyright 2008 Floréal Morandat <morandat@lirmm.fr>
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
14 # This module introduces the standard array structure.
15 # It also implements two other abstract collections : ArrayMap and ArraySet
18 import abstract_collection
20 # One dimension array of objects.
21 abstract class AbstractArrayRead[E
]
26 redef fun is_empty
do return _length
== 0
33 if self[i
] == item
then return true
39 redef fun has_only
(item
)
44 if self[i
] != item
then return false
56 if self[i
] == item
then res
+= 1
62 redef fun index_of
(item
) do return index_of_from
(item
, 0)
64 redef fun last_index_of
(item
: E
): Int do return last_index_of_from
(item
, length-1
)
66 redef fun index_of_from
(item
: E
, pos
: Int): Int
71 if self[i
] == item
then
79 redef fun last_index_of_from
(item
: E
, pos
: Int): Int
83 if self[i
] == item
then
92 # Return a new array that is the reverse of `self`
94 # assert [1,2,3].reversed == [3, 2, 1]
95 fun reversed
: Array[E
]
98 var result
= new Array[E
].with_capacity
(cmp
)
101 result
.add
(self[cmp
])
106 # Copy a portion of `self` to an other array.
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 fun copy_to
(start
: Int, len
: Int, dest
: AbstractArray[E
], new_start
: Int)
118 dest
[new_start
+i
] = self[start
+i
]
128 if e
!= null then e
.output
133 redef fun iterator
: ArrayIterator[E
] do return new ArrayIterator[E
](self)
134 redef fun reverse_iterator
do return new ArrayReverseIterator[E
](self)
137 # Resizable one dimension array of objects.
138 abstract class AbstractArray[E
]
139 super AbstractArrayRead[E
]
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
147 redef fun push
(item
) do add
(item
)
151 assert not_empty
: not is_empty
159 assert not_empty
: not is_empty
171 redef fun unshift
(item
)
181 redef fun insert
(item
: E
, pos
: Int)
184 copy_to
(pos
, length-pos
, self, pos
+ 1)
188 redef fun insert_all
(coll
, pos
)
191 if l
== 0 then return
194 copy_to
(pos
, length-pos-l
, self, pos
+ l
)
201 redef fun add
(item
) do self[length
] = item
203 redef fun clear
do _length
= 0
205 redef fun remove
(item
) do remove_at
(index_of
(item
))
207 redef fun remove_all
(item
)
209 var i
= index_of
(item
)
212 i
= index_of_from
(item
, i
)
216 redef fun remove_at
(i
)
219 if i
>= 0 and i
< l
then
229 # Invert two elements in the array
231 # var a = [10, 20, 30, 40]
233 # assert a == [10, 40, 30, 20]
234 fun swap_at
(a
: Int,b
: Int)
242 # Resizable one dimension array of objects.
244 # Arrays have a literal representation.
246 # var a = [12, 32, 8]
247 # # is equivalent with:
248 # var b = new Array[Int]
254 super AbstractArray[E
]
259 assert index
: index
>= 0 and index
< _length
263 redef fun []=(index
, item
)
265 assert index
: index
>= 0 and index
< _length
+ 1
266 if _capacity
<= index
then
269 if _length
<= index
then
278 if _capacity
<= l
then
285 # Slight optimization for arrays
286 redef fun add_all
(items
)
289 var nl
= l
+ items
.length
290 if _capacity
< nl
then
294 if items
isa Array[E
] then
297 _items
[l
] = items
._items
[k
]
311 redef fun enlarge
(cap
)
314 if cap
<= c
then return
315 while c
<= cap
do c
= c
* 2 + 2
316 var a
= new NativeArray[E
](c
)
317 if _capacity
> 0 then _items
.copy_to
(a
, _length
)
322 # Create an empty array.
329 # Create an array from a collection.
330 init from
(items
: Collection[E
]) do
331 with_capacity
(items
.length
)
335 # Create an array with some `objects`.
336 init with_items
(objects
: E
...)
338 _items
= objects
._items
339 _capacity
= objects
._capacity
340 _length
= objects
.length
343 # Create an empty array with a given capacity.
344 init with_capacity
(cap
: Int)
346 assert positive
: cap
>= 0
347 _items
= new NativeArray[E
](cap
)
352 # Create an array of `count` elements
353 init filled_with
(value
: E
, count
: Int)
355 assert positive
: count
>= 0
356 _items
= new NativeArray[E
](count
)
366 # Create a array filled with a given native array.
367 init with_native
(nat
: NativeArray[E
], size
: Int)
369 assert positive
: size
>= 0
375 # The internal storage.
376 private var items
: nullable NativeArray[E
] = null
378 # The size of `_items`.
379 private var capacity
: Int = 0
383 if not o
isa Array[nullable Object] then return super
384 # Efficient implementation
386 if l
!= o
.length
then return false
391 if it
[i
] != oit
[i
] then return false
397 # Shallow clone of `self`
409 # Note that the clone is shallow and elements are shared between `self` and the result.
418 redef fun clone
do return to_a
420 # Concatenation of arrays.
422 # Returns a new array built by concatenating `self` and `other` together.
427 # assert a3 == [1,2,3,4,5,6]
429 # Because a new array is always created, future modification on `self` and `other`
430 # does not impact the previously computed result.
434 # assert a3 == [1,2,3,4,5,6] # unchanged
435 # assert a1 + a2 == [1,2,3,30,4,5,6,60]
436 fun +(other
: Array[E
]): Array[E
]
438 var res
= new Array[E
].with_capacity
(length
+ other
.length
)
444 # Repetition of arrays.
446 # returns a new array built by concatenating `self` `repeat` times.
449 # assert (a * 0).is_empty
450 # assert a * 1 == [1,2,3]
451 # assert a * 2 == [1,2,3,1,2,3]
452 # assert (a * 10).length == 30
453 fun *(repeat
: Int): Array[E
]
456 var res
= new Array[E
].with_capacity
(length
* repeat
)
465 # An `Iterator` on `AbstractArray`
466 private class ArrayIterator[E
]
467 super IndexedIterator[E
]
469 redef fun item
do return _array
[_index
]
471 # redef fun item=(e) do _array[_index] = e
473 redef fun is_ok
do return _index
< _array
.length
475 redef fun next
do _index
+= 1
479 var array
: AbstractArrayRead[E
]
482 private class ArrayReverseIterator[E
]
483 super ArrayIterator[E
]
485 redef fun is_ok
do return _index
>= 0
487 redef fun next
do _index
-= 1
491 _index
= _array
.length
- 1
495 # Others collections ##########################################################
497 # A set implemented with an Array.
502 # The stored elements.
503 private var array
: Array[E
] is noinit
505 redef fun has
(e
) do return _array
.has
(e
)
507 redef fun add
(e
) do if not _array
.has
(e
) then _array
.add
(e
)
509 redef fun is_empty
do return _array
.is_empty
511 redef fun length
do return _array
.length
515 assert _array
.length
> 0
519 redef fun remove
(item
)
521 var i
= _array
.index_of
(item
)
522 if i
>= 0 then remove_at
(i
)
525 redef fun remove_all
(item
) do remove
(item
)
527 redef fun clear
do _array
.clear
529 redef fun iterator
do return new ArraySetIterator[E
](_array
.iterator
)
531 # Assume the capacity is at least `cap`.
532 fun enlarge
(cap
: Int) do _array
.enlarge
(cap
)
534 private fun remove_at
(i
: Int)
536 _array
[i
] = _array
.last
540 # Create an empty set
541 init do _array
= new Array[E
]
543 # Create an empty set with a given capacity.
544 init with_capacity
(i
: Int) do _array
= new Array[E
].with_capacity
(i
)
546 redef fun new_set
do return new ArraySet[E
]
548 # Shallow clone of `self`
551 # var a = new ArraySet[Int]
562 # Note that the clone is shallow and keys and values are shared between `self` and the result.
565 # var aa = new ArraySet[Array[Int]]
574 var res
= new ArraySet[E
]
580 # Iterators on sets implemented with arrays.
581 private class ArraySetIterator[E
]
584 redef fun is_ok
do return _iter
.is_ok
586 redef fun next
do _iter
.next
588 redef fun item
: E
do return _iter
.item
590 var iter
: ArrayIterator[E
]
594 # Associative arrays implemented with an array of (key, value) pairs.
596 super CoupleMap[K
, E
]
604 return _items
[i
].second
606 return provide_default_value
(key
)
611 redef fun []=(key
, item
)
615 _items
[i
].second
= item
617 _items
.push
(new Couple[K
,E
](key
, item
))
621 redef var keys
: RemovableCollection[K
] = new ArrayMapKeys[K
, E
](self) is lazy
622 redef var values
: RemovableCollection[E
] = new ArrayMapValues[K
, E
](self) is lazy
625 redef fun length
do return _items
.length
627 redef fun couple_iterator
do return _items
.iterator
629 redef fun is_empty
do return _items
.is_empty
631 redef fun clear
do _items
.clear
633 # Assume the capacity to be at least `cap`.
634 fun enlarge
(cap
: Int) do _items
.enlarge
(cap
)
636 redef fun couple_at
(key
)
647 private var items
= new Array[Couple[K
,E
]]
649 # fast remove the ith element of the array
650 private fun remove_at_index
(i
: Int)
652 _items
[i
] = _items
.last
656 # The last positive result given by a index(1) call
657 private var last_index
: Int = 0
659 # Where is the `key` in `_item`?
660 # return -1 if not found
661 private fun index
(key
: K
): Int
664 if l
< _items
.length
and _items
[l
].first
== key
then return l
667 while i
< _items
.length
do
668 if _items
[i
].first
== key
then
677 # Shallow clone of `self`
680 # var a = new ArrayMap[String,Int]
689 # Note that the clone is shallow and keys and values are shared between `self` and the result.
692 # var aa = new ArrayMap[String, Array[Int]]
701 var res
= new ArrayMap[K
,E
]
702 res
.recover_with
self
707 private class ArrayMapKeys[K
, E
]
708 super RemovableCollection[K
]
710 var map
: ArrayMap[K
, E
]
711 redef fun count
(k
) do if self.has
(k
) then return 1 else return 0
712 redef fun first
do return self.map
._items
.first
.first
713 redef fun has
(k
) do return self.map
.index
(k
) >= 0
714 redef fun has_only
(k
) do return (self.has
(k
) and self.length
== 1) or self.is_empty
715 redef fun is_empty
do return self.map
.is_empty
716 redef fun length
do return self.map
.length
717 redef fun iterator
do return new MapKeysIterator[K
, E
](self.map
.iterator
)
718 redef fun clear
do self.map
.clear
719 redef fun remove
(key
)
721 var i
= self.map
.index
(key
)
722 if i
>= 0 then self.map
.remove_at_index
(i
)
724 redef fun remove_all
(key
) do self.remove
(key
)
727 private class ArrayMapValues[K
, E
]
728 super RemovableCollection[E
]
730 var map
: ArrayMap[K
, E
]
731 redef fun first
do return self.map
._items
.first
.second
732 redef fun is_empty
do return self.map
.is_empty
733 redef fun length
do return self.map
.length
734 redef fun iterator
do return new MapValuesIterator[K
, E
](self.map
.iterator
)
739 for i
in self.map
._items
do if i
.second
== item
then return true
744 redef fun has_only
(item
)
746 for i
in self.map
._items
do if i
.second
!= item
then return false
751 redef fun count
(item
)
754 for i
in self.map
._items
do if i
.second
== item
then nb
+= 1
758 redef fun clear
do self.map
.clear
760 redef fun remove
(item
)
763 var i
= map
._items
.length
- 1
765 if map
._items
[i
].second
== item
then
766 map
.remove_at_index
(i
)
773 redef fun remove_all
(item
)
776 var i
= map
._items
.length
- 1
778 if map
._items
[i
].second
== item
then
779 map
.remove_at_index
(i
)
786 # Comparable array for comparable elements.
788 # For two arrays, if one is a prefix, then it is lower.
791 # var a12 = new ArrayCmp[nullable Int].with_items(1,2)
792 # var a123 = new ArrayCmp[nullable Int].with_items(1,2,3)
796 # Otherwise, the first element just after the longest
797 # common prefix gives the order between the two arrays.
800 # var a124 = new ArrayCmp[nullable Int].with_items(1,2,4)
801 # var a13 = new ArrayCmp[nullable Int].with_items(1,3)
806 # Obviously, two equal arrays are equal.
809 # var b12 = new ArrayCmp[nullable Int].with_items(1,2)
810 # assert (a12 <=> b12) == 0
813 # `null` is considered lower than any other elements.
814 # But is still greater than no element.
817 # var a12n = new ArrayCmp[nullable Int].with_items(1,2,null)
821 class ArrayCmp[E
: nullable Comparable]
824 redef type OTHER: ArrayCmp[E
] is fixed
826 redef fun <(o
) do return (self <=> o
) < 0
836 if l
< ol
then len
= l
else len
= ol
841 if b
== null then return 1
842 var d
= a
<=> b
.as(Comparable)
843 if d
!= 0 then return d
845 if b
!= null then return -1
853 # Others tools ################################################################
855 redef class Iterator[E
]
856 # Interate on `self` and build an array
859 var res
= new Array[E
]
868 redef class Collection[E
]
869 # Build a new array from a collection
872 var res
= new Array[E
].with_capacity
(length
)
878 # Native classes ##############################################################
881 # Access are unchecked and it has a fixed size
882 # Not for public use: may become private.
883 universal NativeArray[E
]
884 # Creates a new NativeArray of capacity `length`
885 new(length
: Int) is intern
886 # The length of the array
887 fun length
: Int is intern
888 # Use `self` to initialize a standard Nit Array.
889 fun to_a
: Array[E
] do return new Array[E
].with_native
(self, length
)
891 # Get item at `index`.
892 fun [](index
: Int): E
is intern
894 # Set `item` at `index`.
895 fun []=(index
: Int, item
: E
) is intern
897 # Copy `length` items to `dest`.
898 fun copy_to
(dest
: NativeArray[E
], length
: Int) is intern
899 #fun =(o: NativeArray[E]): Bool is intern
900 #fun !=(o: NativeArray[E]): Bool is intern