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
]
25 redef fun length
do return _length
27 redef fun is_empty
do return _length
== 0
34 if self[i
] == item
then return true
40 redef fun has_only
(item
)
45 if self[i
] != item
then return false
57 if self[i
] == item
then res
+= 1
63 redef fun index_of
(item
) do return index_of_from
(item
, 0)
65 redef fun last_index_of
(item
: E
): Int do return last_index_of_from
(item
, length-1
)
67 redef fun index_of_from
(item
: E
, pos
: Int): Int
72 if self[i
] == item
then
80 redef fun last_index_of_from
(item
: E
, pos
: Int): Int
84 if self[i
] == item
then
93 # Return a new array that is the reverse of `self`
95 # assert [1,2,3].reversed == [3, 2, 1]
96 fun reversed
: Array[E
]
99 var result
= new Array[E
].with_capacity
(cmp
)
102 result
.add
(self[cmp
])
107 # Copy a portion of `self` to an other array.
109 # var a = [1, 2, 3, 4]
110 # var b = [10, 20, 30, 40, 50]
111 # a.copy_to(1, 2, b, 2)
112 # assert b == [10, 20, 2, 3, 50]
113 protected fun copy_to
(start
: Int, len
: Int, dest
: AbstractArray[E
], new_start
: Int)
119 dest
[new_start
+i
] = self[start
+i
]
129 if e
!= null then e
.output
134 redef fun iterator
: ArrayIterator[E
] do return new ArrayIterator[E
](self)
135 redef fun reverse_iterator
do return new ArrayReverseIterator[E
](self)
138 # Resizable one dimension array of objects.
139 abstract class AbstractArray[E
]
140 super AbstractArrayRead[E
]
143 # Force the capacity to be at least `cap`.
144 # The capacity of the array is an internal information.
145 # However, this method can be used to prepare a large amount of add
146 fun enlarge
(cap
: Int) is abstract
148 redef fun push
(item
) do add
(item
)
152 assert not_empty
: not is_empty
160 assert not_empty
: not is_empty
172 redef fun unshift
(item
)
182 redef fun insert
(item
: E
, pos
: Int)
185 copy_to
(pos
, length-pos
, self, pos
+ 1)
189 redef fun add
(item
) do self[length
] = item
191 redef fun clear
do _length
= 0
193 redef fun remove
(item
) do remove_at
(index_of
(item
))
195 redef fun remove_all
(item
)
197 var i
= index_of
(item
)
200 i
= index_of_from
(item
, i
)
204 redef fun remove_at
(i
)
207 if i
>= 0 and i
< l
then
217 # Invert two elements in the array
219 # var a = [10, 20, 30, 40]
221 # assert a == [10, 40, 30, 20]
222 fun swap_at
(a
: Int,b
: Int)
230 # Resizable one dimension array of objects.
232 # Arrays have a literal representation.
233 # var a = [12, 32, 8]
234 # # is equivalent with:
235 # var b = new Array[Int]
241 super AbstractArray[E
]
242 super ArrayCapable[E
]
246 assert index
: index
>= 0 and index
< _length
250 redef fun []=(index
, item
)
252 assert index
: index
>= 0 and index
< _length
+ 1
253 if _capacity
<= index
then
256 if _length
<= index
then
265 if _capacity
<= l
then
272 redef fun enlarge
(cap
)
275 if cap
<= c
then return
276 while c
<= cap
do c
= c
* 2 + 2
277 var a
= calloc_array
(c
)
278 if _capacity
> 0 then _items
.copy_to
(a
, _length
)
283 # Create an empty array.
290 # Create an array from a collection.
291 init from
(items
: Collection[E
]) do
292 with_capacity
(items
.length
)
296 # Create an array with some `objects`.
297 init with_items
(objects
: E
...)
299 _items
= objects
._items
300 _capacity
= objects
._capacity
301 _length
= objects
.length
304 # Create an empty array with a given capacity.
305 init with_capacity
(cap
: Int)
307 assert positive
: cap
>= 0
308 _items
= calloc_array
(cap
)
313 # Create an array of `count` elements
314 init filled_with
(value
: E
, count
: Int)
316 assert positive
: count
>= 0
317 _items
= calloc_array
(count
)
327 # Create a array filled with a given native array.
328 init with_native
(nat
: NativeArray[E
], size
: Int)
330 assert positive
: size
>= 0
336 # The internal storage.
337 var _items
: nullable NativeArray[E
] = null
339 # Do not use this method
340 # FIXME: Remove it once modules can intrude non local modules
341 fun intern_items
: NativeArray[E
] do return _items
.as(not null)
343 # The size of `_items`.
344 var _capacity
: Int = 0
348 if not o
isa Array[nullable Object] then return super
349 # Efficient implementation
351 if l
!= o
.length
then return false
356 if it
[i
] != oit
[i
] then return false
363 # An `Iterator` on `AbstractArray`
364 private class ArrayIterator[E
]
365 super IndexedIterator[E
]
367 redef fun item
do return _array
[_index
]
369 # redef fun item=(e) do _array[_index] = e
371 redef fun is_ok
do return _index
< _array
.length
373 redef fun next
do _index
+= 1
375 init(a
: AbstractArrayRead[E
])
382 redef fun index
do return _index
383 var _array
: AbstractArrayRead[E
]
386 private class ArrayReverseIterator[E
]
387 super ArrayIterator[E
]
389 redef fun is_ok
do return _index
>= 0
391 redef fun next
do _index
-= 1
393 init(a
: AbstractArrayRead[E
])
396 _index
= a
.length
- 1
400 # Others collections ##########################################################
402 # A set implemented with an Array.
403 class ArraySet[E
: Object]
406 # The stored elements.
409 redef fun has
(e
) do return _array
.has
(e
)
411 redef fun add
(e
) do if not _array
.has
(e
) then _array
.add
(e
)
413 redef fun is_empty
do return _array
.is_empty
415 redef fun length
do return _array
.length
419 assert _array
.length
> 0
423 redef fun remove
(item
)
425 var i
= _array
.index_of
(item
)
426 if i
>= 0 then remove_at
(i
)
429 redef fun remove_all
(item
) do remove
(item
)
431 redef fun clear
do _array
.clear
433 redef fun iterator
do return new ArraySetIterator[E
](_array
.iterator
)
435 # Assume the capacity is at least `cap`.
436 fun enlarge
(cap
: Int) do _array
.enlarge
(cap
)
438 private fun remove_at
(i
: Int)
440 _array
[i
] = _array
.last
444 # Create an empty set
445 init do _array
= new Array[E
]
447 # Create an empty set with a given capacity.
448 init with_capacity
(i
: Int) do _array
= new Array[E
].with_capacity
(i
)
450 redef fun new_set
do return new ArraySet[E
]
453 # Iterators on sets implemented with arrays.
454 private class ArraySetIterator[E
: Object]
457 redef fun is_ok
do return _iter
.is_ok
459 redef fun next
do _iter
.next
461 redef fun item
: E
do return _iter
.item
463 init(iter
: ArrayIterator[E
]) do _iter
= iter
465 var _iter
: ArrayIterator[E
]
469 # Associative arrays implemented with an array of (key, value) pairs.
470 class ArrayMap[K
: Object, E
]
471 super CoupleMap[K
, E
]
478 return _items
[i
].second
480 return provide_default_value
(key
)
485 redef fun []=(key
, item
)
489 _items
[i
].second
= item
491 _items
.push
(new Couple[K
,E
](key
, item
))
495 redef var keys
: RemovableCollection[K
] = new ArrayMapKeys[K
, E
](self)
496 redef var values
: RemovableCollection[E
] = new ArrayMapValues[K
, E
](self)
499 redef fun length
do return _items
.length
501 redef fun couple_iterator
do return _items
.iterator
503 redef fun is_empty
do return _items
.is_empty
505 redef fun clear
do _items
.clear
507 # Assume the capacity to be at least `cap`.
508 fun enlarge
(cap
: Int) do _items
.enlarge
(cap
)
510 redef fun couple_at
(key
)
521 var _items
= new Array[Couple[K
,E
]]
523 # fast remove the ith element of the array
524 private fun remove_at_index
(i
: Int)
526 _items
[i
] = _items
.last
530 # The last positive result given by a index(1) call
531 var _last_index
: Int = 0
533 # Where is the `key` in `_item`?
534 # return -1 if not found
535 private fun index
(key
: K
): Int
538 if l
< _items
.length
and _items
[l
].first
== key
then return l
541 while i
< _items
.length
do
542 if _items
[i
].first
== key
then
552 private class ArrayMapKeys[K
: Object, E
]
553 super RemovableCollection[K
]
555 var map
: ArrayMap[K
, E
]
556 redef fun count
(k
) do if self.has
(k
) then return 1 else return 0
557 redef fun first
do return self.map
._items
.first
.first
558 redef fun has
(k
) do return self.map
.index
(k
) >= 0
559 redef fun has_only
(k
) do return (self.has
(k
) and self.length
== 1) or self.is_empty
560 redef fun is_empty
do return self.map
.is_empty
561 redef fun length
do return self.map
.length
562 redef fun iterator
do return new MapKeysIterator[K
, E
](self.map
.iterator
)
563 redef fun clear
do self.map
.clear
564 redef fun remove
(key
)
566 var i
= self.map
.index
(key
)
567 if i
>= 0 then self.map
.remove_at_index
(i
)
569 redef fun remove_all
(key
) do self.remove
(key
)
572 private class ArrayMapValues[K
: Object, E
]
573 super RemovableCollection[E
]
575 var map
: ArrayMap[K
, E
]
576 redef fun first
do return self.map
._items
.first
.second
577 redef fun is_empty
do return self.map
.is_empty
578 redef fun length
do return self.map
.length
579 redef fun iterator
do return new MapValuesIterator[K
, E
](self.map
.iterator
)
584 for i
in self.map
._items
do if i
.second
== item
then return true
589 redef fun has_only
(item
)
591 for i
in self.map
._items
do if i
.second
!= item
then return false
596 redef fun count
(item
)
599 for i
in self.map
._items
do if i
.second
== item
then nb
+= 1
603 redef fun clear
do self.map
.clear
605 redef fun remove
(item
)
608 var i
= map
._items
.length
- 1
610 if map
._items
[i
].second
== item
then
611 map
.remove_at_index
(i
)
618 redef fun remove_all
(item
)
621 var i
= map
._items
.length
- 1
623 if map
._items
[i
].second
== item
then
624 map
.remove_at_index
(i
)
631 # Comparable array for comparable elements.
633 # For two arrays, if one is a prefix, then it is lower.
636 # var a12 = new ArrayCmp[nullable Int].with_items(1,2)
637 # var a123 = new ArrayCmp[nullable Int].with_items(1,2,3)
641 # Otherwise, the first element just after the longest
642 # common prefix gives the order between the two arrays.
645 # var a124 = new ArrayCmp[nullable Int].with_items(1,2,4)
646 # var a13 = new ArrayCmp[nullable Int].with_items(1,3)
651 # Obviously, two equal arrays are equal.
654 # var b12 = new ArrayCmp[nullable Int].with_items(1,2)
655 # assert (a12 <=> b12) == 0
658 # `null` is considered lower than any other elements.
659 # But is still greater than no element.
662 # var a12n = new ArrayCmp[nullable Int].with_items(1,2,null)
666 class ArrayCmp[E
: nullable Comparable]
669 redef type OTHER: ArrayCmp[E
] is fixed
671 redef fun <(o
) do return (self <=> o
) < 0
681 if l
< ol
then len
= l
else len
= ol
686 if b
== null then return 1
687 var d
= a
<=> b
.as(Comparable)
688 if d
!= 0 then return d
690 if b
!= null then return -1
698 # Others tools ################################################################
700 redef class Iterator[E
]
701 # Interate on `self` and build an array
704 var res
= new Array[E
]
713 redef class Collection[E
]
714 # Build a new array from a collection
717 var res
= new Array[E
].with_capacity
(length
)
723 # Native classes ##############################################################
725 # Subclasses of this class can create native arrays
726 interface ArrayCapable[E
]
727 # Get a new array of `size` elements.
728 protected fun calloc_array
(size
: Int): NativeArray[E
] is intern
732 # Access are unchecked and it has a fixed size
733 # Not for public use: may become private.
734 universal NativeArray[E
]
735 # Creates a new NativeArray of capacity `length`
736 new(length
: Int) is intern
737 # The length of the array
738 fun length
: Int is intern
739 # Use `self` to initialize a standard Nit Array.
740 fun to_a
: Array[E
] do return new Array[E
].with_native
(self, length
)
741 fun [](index
: Int): E
is intern
742 fun []=(index
: Int, item
: E
) is intern
743 fun copy_to
(dest
: NativeArray[E
], length
: Int) is intern
744 #fun =(o: NativeArray[E]): Bool is intern
745 #fun !=(o: NativeArray[E]): Bool is intern