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
17 no_warning
"useless-type-test" # to avoid warning with nitc while compiling with c_src
20 import abstract_collection
22 # One dimension array of objects.
23 abstract class AbstractArrayRead[E
]
28 redef fun is_empty
do return _length
== 0
35 if self[i
] == item
then return true
41 redef fun has_only
(item
)
46 if self[i
] != item
then return false
58 if self[i
] == item
then res
+= 1
64 redef fun index_of
(item
) do return index_of_from
(item
, 0)
66 redef fun last_index_of
(item
) do return last_index_of_from
(item
, length-1
)
68 redef fun index_of_from
(item
, pos
) do
72 if self[i
] == item
then
80 redef fun last_index_of_from
(item
, pos
) do
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)
114 if start
< new_start
then
118 dest
[new_start
+i
] = self[start
+i
]
123 dest
[new_start
+i
] = self[start
+i
]
135 if e
!= null then e
.output
140 redef fun iterator
: IndexedIterator[E
] do
141 var res
= _free_iterator
142 if res
== null then return new ArrayIterator[E
](self)
144 _free_iterator
= null
148 # An old iterator, free to reuse.
149 # Once an iterator is `finish`, it become reusable.
150 # Since some arrays are iterated a lot, this avoid most of the
151 # continuous allocation/garbage-collection of the needed iterators.
152 private var free_iterator
: nullable ArrayIterator[E
] = null
154 redef fun reverse_iterator
do return new ArrayReverseIterator[E
](self)
156 # Returns a sub-array containing `count` elements starting from `from`.
158 # For most cases (see other case bellow),
159 # the first element is `from` and
160 # the last element is `from+count-1`.
163 # var a = [10, 20, 30, 40, 50]
164 # assert a.sub(0, 3) == [10, 20, 30]
165 # assert a.sub(3, 2) == [40, 50]
166 # assert a.sub(3, 1) == [40]
169 # If `count` is 0 or negative then an empty array is returned
172 # assert a.sub(3,0).is_empty
173 # assert a.sub(3,-1).is_empty
176 # If `from < 0` or `from+count>length` then inexistent elements are ignored.
177 # In this case the length of the result is lower than count.
180 # assert a.sub(-2, 4) == [10, 20]
181 # assert a.sub(4, 99) == [50]
182 # assert a.sub(-9, 99) == [10,20,30,40,50]
183 # assert a.sub(-99, 9).is_empty
185 fun sub
(from
: Int, count
: Int): Array[E
] do
193 var to
= from
+ count
197 var res
= new Array[E
].with_capacity
(to
- from
)
206 # Resizable one dimension array of objects.
207 abstract class AbstractArray[E
]
208 super AbstractArrayRead[E
]
211 # Force the capacity to be at least `cap`.
212 # The capacity of the array is an internal information.
213 # However, this method can be used to prepare a large amount of add
214 fun enlarge
(cap
: Int) is abstract
216 redef fun push
(item
) do add
(item
)
220 assert not_empty
: not is_empty
228 assert not_empty
: not is_empty
231 copy_to
(1, l
, self, 0)
236 redef fun unshift
(item
)
241 copy_to
(0, l
, self, 1)
246 redef fun insert
(item
, pos
) do
248 copy_to
(pos
, length-pos
, self, pos
+ 1)
252 redef fun insert_all
(coll
, pos
)
255 if l
== 0 then return
258 copy_to
(pos
, length-pos-l
, self, pos
+ l
)
265 redef fun add
(item
) do self[length
] = item
267 redef fun clear
do _length
= 0
269 redef fun remove
(item
) do remove_at
(index_of
(item
))
271 redef fun remove_all
(item
)
273 var i
= index_of
(item
)
276 i
= index_of_from
(item
, i
)
280 redef fun remove_at
(i
)
283 if i
>= 0 and i
< l
then
293 # Invert two elements in the array
295 # var a = [10, 20, 30, 40]
297 # assert a == [10, 40, 30, 20]
298 fun swap_at
(a
: Int,b
: Int)
306 # Resizable one dimension array of objects.
308 # Arrays have a literal representation.
310 # var a = [12, 32, 8]
311 # # is equivalent with:
312 # var b = new Array[Int]
318 super AbstractArray[E
]
323 assert index
: index
>= 0 and index
< _length
324 return _items
.as(not null)[index
]
327 redef fun []=(index
, item
)
329 assert index
: index
>= 0 and index
< _length
+ 1
330 if _capacity
<= index
then
333 if _length
<= index
then
336 _items
.as(not null)[index
] = item
342 if _capacity
<= l
then
346 _items
.as(not null)[l
] = item
349 # Slight optimization for arrays
350 redef fun add_all
(items
)
353 var nl
= l
+ items
.length
354 if _capacity
< nl
then
358 if items
isa Array[E
] then
361 _items
.as(not null)[l
] = items
._items
.as(not null)[k
]
367 _items
.as(not null)[l
] = item
375 redef fun copy_to
(start
, len
, dest
, new_start
)
377 # Fast code when source and destination are two arrays
379 if not dest
isa Array[E
] then
384 # Enlarge dest if required
385 var dest_len
= new_start
+ len
386 if dest_len
> dest
.length
then
387 dest
.enlarge
(dest_len
)
388 dest
.length
= dest_len
391 # Get underlying native arrays
392 var items
= self.items
393 if items
== null then return
394 var dest_items
= dest
.items
395 assert dest_items
!= null
398 items
.memmove
(start
, len
, dest_items
, new_start
)
401 redef fun enlarge
(cap
)
404 if cap
<= c
then return
405 while c
<= cap
do c
= c
* 2 + 2
406 var a
= new NativeArray[E
](c
)
407 if _capacity
> 0 then _items
.as(not null).copy_to
(a
, _length
)
412 # Create an empty array.
419 # Create an array from a collection.
420 init from
(items
: Collection[E
]) do
421 with_capacity
(items
.length
)
425 # Create an array with some `objects`.
426 init with_items
(objects
: E
...)
428 _items
= objects
._items
429 _capacity
= objects
._capacity
430 _length
= objects
.length
433 # Create an empty array with a given capacity.
434 init with_capacity
(cap
: Int)
436 assert positive
: cap
>= 0
437 _items
= new NativeArray[E
](cap
)
442 # Create an array of `count` elements
443 init filled_with
(value
: E
, count
: Int)
445 assert positive
: count
>= 0
446 _items
= new NativeArray[E
](count
)
456 # Create a array filled with a given native array.
457 init with_native
(nat
: NativeArray[E
], size
: Int)
459 assert positive
: size
>= 0
465 # The internal storage.
466 private var items
: nullable NativeArray[E
] = null
468 # The size of `_items`.
469 private var capacity
: Int = 0
473 if not o
isa Array[nullable Object] then return super
474 # Efficient implementation
476 if l
!= o
.length
then return false
477 if l
== 0 then return true
479 var it
= _items
.as(not null)
480 var oit
= o
._items
.as(not null)
482 if it
[i
] != oit
[i
] then return false
488 # Shallow clone of `self`
500 # Note that the clone is shallow and elements are shared between `self` and the result.
509 redef fun clone
do return to_a
511 # Concatenation of arrays.
513 # Returns a new array built by concatenating `self` and `other` together.
518 # assert a3 == [1,2,3,4,5,6]
520 # Because a new array is always created, future modification on `self` and `other`
521 # does not impact the previously computed result.
525 # assert a3 == [1,2,3,4,5,6] # unchanged
526 # assert a1 + a2 == [1,2,3,30,4,5,6,60]
527 fun +(other
: Array[E
]): Array[E
]
529 var res
= new Array[E
].with_capacity
(length
+ other
.length
)
535 # Repetition of arrays.
537 # returns a new array built by concatenating `self` `repeat` times.
540 # assert (a * 0).is_empty
541 # assert a * 1 == [1,2,3]
542 # assert a * 2 == [1,2,3,1,2,3]
543 # assert (a * 10).length == 30
544 fun *(repeat
: Int): Array[E
]
547 var res
= new Array[E
].with_capacity
(length
* repeat
)
556 # An `Iterator` on `AbstractArray`
557 private class ArrayIterator[E
]
558 super IndexedIterator[E
]
560 redef fun item
do return _array
[_index
]
562 # redef fun item=(e) do _array[_index] = e
564 redef fun is_ok
do return _index
< _array
.length
566 redef fun next
do _index
+= 1
570 var array
: AbstractArrayRead[E
]
572 redef fun finish
do _array
._free_iterator
= self
575 private class ArrayReverseIterator[E
]
576 super ArrayIterator[E
]
578 redef fun is_ok
do return _index
>= 0
580 redef fun next
do _index
-= 1
584 _index
= _array
.length
- 1
587 # Do not cache `self`
588 redef fun finish
do end
591 # Others collections ##########################################################
593 # A set implemented with an Array.
597 # The stored elements.
598 private var array
: Array[E
] is noinit
600 redef fun has
(e
) do return _array
.has
(e
)
602 redef fun add
(e
) do if not _array
.has
(e
) then _array
.add
(e
)
604 redef fun is_empty
do return _array
.is_empty
606 redef fun length
do return _array
.length
610 assert _array
.length
> 0
614 redef fun remove
(item
)
616 var i
= _array
.index_of
(item
)
617 if i
>= 0 then remove_at
(i
)
620 redef fun remove_all
(item
) do remove
(item
)
622 redef fun clear
do _array
.clear
624 redef fun iterator
do return new ArraySetIterator[E
](_array
.iterator
)
626 # Assume the capacity is at least `cap`.
627 fun enlarge
(cap
: Int) do _array
.enlarge
(cap
)
629 private fun remove_at
(i
: Int)
631 _array
[i
] = _array
.last
635 # Create an empty set
636 init do _array
= new Array[E
]
638 # Create an empty set with a given capacity.
639 init with_capacity
(i
: Int) do _array
= new Array[E
].with_capacity
(i
)
641 redef fun new_set
do return new ArraySet[E
]
643 # Shallow clone of `self`
646 # var a = new ArraySet[Int]
657 # Note that the clone is shallow and keys and values are shared between `self` and the result.
660 # var aa = new ArraySet[Array[Int]]
669 var res
= new ArraySet[E
]
675 # Iterators on sets implemented with arrays.
676 private class ArraySetIterator[E
]
679 redef fun is_ok
do return _iter
.is_ok
681 redef fun next
do _iter
.next
683 redef fun item
: E
do return _iter
.item
685 var iter
: Iterator[E
]
689 # Associative arrays implemented with an array of (key, value) pairs.
691 super CoupleMap[K
, E
]
699 return _items
[i
].second
701 return provide_default_value
(key
)
706 redef fun []=(key
, item
)
710 _items
[i
].second
= item
712 _items
.push
(new Couple[K
,E
](key
, item
))
716 redef var keys
: RemovableCollection[K
] = new ArrayMapKeys[K
, E
](self) is lazy
717 redef var values
: RemovableCollection[E
] = new ArrayMapValues[K
, E
](self) is lazy
720 redef fun length
do return _items
.length
722 redef fun couple_iterator
do return _items
.iterator
724 redef fun is_empty
do return _items
.is_empty
726 redef fun clear
do _items
.clear
728 # Assume the capacity to be at least `cap`.
729 fun enlarge
(cap
: Int) do _items
.enlarge
(cap
)
731 redef fun couple_at
(key
)
742 private var items
= new Array[Couple[K
,E
]]
744 # fast remove the ith element of the array
745 private fun remove_at_index
(i
: Int)
747 _items
[i
] = _items
.last
751 # The last positive result given by a index(1) call
752 private var last_index
: Int = 0
754 # Where is the `key` in `_item`?
755 # return -1 if not found
756 private fun index
(key
: K
): Int
759 if l
< _items
.length
and _items
[l
].first
== key
then return l
762 while i
< _items
.length
do
763 if _items
[i
].first
== key
then
772 # Shallow clone of `self`
775 # var a = new ArrayMap[String,Int]
784 # Note that the clone is shallow and keys and values are shared between `self` and the result.
787 # var aa = new ArrayMap[String, Array[Int]]
796 var res
= new ArrayMap[K
,E
]
802 private class ArrayMapKeys[K
, E
]
803 super RemovableCollection[K
]
805 var map
: ArrayMap[K
, E
]
806 redef fun count
(k
) do if self.has
(k
) then return 1 else return 0
807 redef fun first
do return self.map
._items
.first
.first
808 redef fun has
(k
) do return self.map
.index
(k
) >= 0
809 redef fun has_only
(k
) do return (self.has
(k
) and self.length
== 1) or self.is_empty
810 redef fun is_empty
do return self.map
.is_empty
811 redef fun length
do return self.map
.length
812 redef fun iterator
do return new MapKeysIterator[K
, E
](self.map
.iterator
)
813 redef fun clear
do self.map
.clear
814 redef fun remove
(key
)
816 var i
= self.map
.index
(key
)
817 if i
>= 0 then self.map
.remove_at_index
(i
)
819 redef fun remove_all
(key
) do self.remove
(key
)
822 private class ArrayMapValues[K
, E
]
823 super RemovableCollection[E
]
825 var map
: ArrayMap[K
, E
]
826 redef fun first
do return self.map
._items
.first
.second
827 redef fun is_empty
do return self.map
.is_empty
828 redef fun length
do return self.map
.length
829 redef fun iterator
do return new MapValuesIterator[K
, E
](self.map
.iterator
)
834 for i
in self.map
._items
do if i
.second
== item
then return true
839 redef fun has_only
(item
)
841 for i
in self.map
._items
do if i
.second
!= item
then return false
846 redef fun count
(item
)
849 for i
in self.map
._items
do if i
.second
== item
then nb
+= 1
853 redef fun clear
do self.map
.clear
855 redef fun remove
(item
)
858 var i
= map
._items
.length
- 1
860 if map
._items
[i
].second
== item
then
861 map
.remove_at_index
(i
)
868 redef fun remove_all
(item
)
871 var i
= map
._items
.length
- 1
873 if map
._items
[i
].second
== item
then
874 map
.remove_at_index
(i
)
881 # Comparable array for comparable elements.
883 # For two arrays, if one is a prefix, then it is lower.
886 # var a12 = new ArrayCmp[nullable Int].with_items(1,2)
887 # var a123 = new ArrayCmp[nullable Int].with_items(1,2,3)
891 # Otherwise, the first element just after the longest
892 # common prefix gives the order between the two arrays.
895 # var a124 = new ArrayCmp[nullable Int].with_items(1,2,4)
896 # var a13 = new ArrayCmp[nullable Int].with_items(1,3)
901 # Obviously, two equal arrays are equal.
904 # var b12 = new ArrayCmp[nullable Int].with_items(1,2)
905 # assert (a12 <=> b12) == 0
908 # `null` is considered lower than any other elements.
909 # But is still greater than no element.
912 # var a12n = new ArrayCmp[nullable Int].with_items(1,2,null)
916 class ArrayCmp[E
: nullable Comparable]
919 redef type OTHER: ArrayCmp[E
] is fixed
921 redef fun <(o
) do return (self <=> o
) < 0
927 if l
== 0 then return 0
928 var it
= _items
.as(not null)
929 var oit
= o
._items
.as(not null)
932 if l
< ol
then len
= l
else len
= ol
937 if b
== null then return 1
939 if d
!= 0 then return d
941 if b
!= null then return -1
949 # Others tools ################################################################
951 redef class Iterator[E
]
952 # Interate on `self` and build an array
955 var res
= new Array[E
]
965 redef class Collection[E
]
966 # Build a new array from a collection
969 var res
= new Array[E
].with_capacity
(length
)
975 # Native classes ##############################################################
978 # Access are unchecked and it has a fixed size
979 # Not for public use: may become private.
980 universal NativeArray[E
]
981 # Creates a new NativeArray of capacity `length`
982 new(length
: Int) is intern
983 # The length of the array
984 fun length
: Int is intern
985 # Use `self` to initialize a standard Nit Array.
986 fun to_a
: Array[E
] do return new Array[E
].with_native
(self, length
)
988 # Get item at `index`.
989 fun [](index
: Int): E
is intern
991 # Set `item` at `index`.
992 fun []=(index
: Int, item
: E
) is intern
994 # Copy `length` items to `dest`.
995 fun copy_to
(dest
: NativeArray[E
], length
: Int) is intern
997 # Copy `length` items to `dest` starting from `dest`.
998 fun memmove
(start
: Int, length
: Int, dest
: NativeArray[E
], dest_start
: Int) is intern do
999 if start
< dest_start
then
1003 dest
[dest_start
+i
] = self[start
+i
]
1008 dest
[dest_start
+i
] = self[start
+i
]
1014 #fun =(o: NativeArray[E]): Bool is intern
1015 #fun !=(o: NativeArray[E]): Bool is intern