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
]
24 redef readable var _length
: Int = 0
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 protected 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)
136 # Resizable one dimension array of objects.
137 abstract class AbstractArray[E
]
138 super AbstractArrayRead[E
]
141 # Force the capacity to be at least `cap`.
142 # The capacity of the array is an internal information.
143 # However, this method can be used to prepare a large amount of add
144 fun enlarge
(cap
: Int) is abstract
146 redef fun push
(item
) do add
(item
)
150 assert not_empty
: not is_empty
158 assert not_empty
: not is_empty
170 redef fun unshift
(item
)
180 redef fun insert
(item
: E
, pos
: Int)
183 copy_to
(pos
, length-pos
, self, pos
+ 1)
187 redef fun add
(item
) do self[length
] = item
189 redef fun clear
do _length
= 0
191 redef fun remove
(item
) do remove_at
(index_of
(item
))
193 redef fun remove_all
(item
)
195 var i
= index_of
(item
)
198 i
= index_of_from
(item
, i
)
202 redef fun remove_at
(i
)
205 if i
>= 0 and i
< l
then
215 # Invert two elements in the array
217 # var a = [10, 20, 30, 40]
219 # assert a == [10, 40, 30, 20]
220 fun swap_at
(a
: Int,b
: Int)
228 # Resizable one dimension array of objects.
230 # Arrays have a literal representation.
231 # var a = [12, 32, 8]
232 # # is equivalent with:
233 # var b = new Array[Int]
239 super AbstractArray[E
]
240 super ArrayCapable[E
]
244 assert index
: index
>= 0 and index
< _length
248 redef fun []=(index
, item
)
250 assert index
: index
>= 0 and index
< _length
+ 1
251 if _capacity
<= index
then
254 if _length
<= index
then
263 if _capacity
<= l
then
270 redef fun enlarge
(cap
)
273 if cap
<= c
then return
274 while c
<= cap
do c
= c
* 2 + 2
275 var a
= calloc_array
(c
)
276 if _capacity
> 0 then _items
.copy_to
(a
, _length
)
281 # Create an empty array.
288 # Create an array from a collection.
289 init from
(items
: Collection[E
]) do
290 with_capacity
(items
.length
)
294 # Create an array with some `objects`.
295 init with_items
(objects
: E
...)
297 _items
= objects
._items
298 _capacity
= objects
._capacity
299 _length
= objects
.length
302 # Create an empty array with a given capacity.
303 init with_capacity
(cap
: Int)
305 assert positive
: cap
>= 0
306 _items
= calloc_array
(cap
)
311 # Create an array of `count` elements
312 init filled_with
(value
: E
, count
: Int)
314 assert positive
: count
>= 0
315 _items
= calloc_array
(count
)
325 # Create a array filled with a given native array.
326 init with_native
(nat
: NativeArray[E
], size
: Int)
328 assert positive
: size
>= 0
334 # The internal storage.
335 var _items
: nullable NativeArray[E
] = null
337 # Do not use this method
338 # FIXME: Remove it once modules can intrude non local modules
339 fun intern_items
: NativeArray[E
] do return _items
.as(not null)
341 # The size of `_items`.
342 var _capacity
: Int = 0
345 # An `Iterator` on `AbstractArray`
346 private class ArrayIterator[E
]
347 super IndexedIterator[E
]
349 redef fun item
do return _array
[_index
]
351 # redef fun item=(e) do _array[_index] = e
353 redef fun is_ok
do return _index
< _array
.length
355 redef fun next
do _index
+= 1
357 init(a
: AbstractArrayRead[E
])
363 redef readable var _index
: Int = 0
364 var _array
: AbstractArrayRead[E
]
367 # Others collections ##########################################################
369 # A set implemented with an Array.
370 class ArraySet[E
: Object]
373 # The stored elements.
376 redef fun has
(e
) do return _array
.has
(e
)
378 redef fun add
(e
) do if not _array
.has
(e
) then _array
.add
(e
)
380 redef fun is_empty
do return _array
.is_empty
382 redef fun length
do return _array
.length
386 assert _array
.length
> 0
390 redef fun remove
(item
)
392 var i
= _array
.index_of
(item
)
393 if i
>= 0 then remove_at
(i
)
396 redef fun remove_all
(item
) do remove
(item
)
398 redef fun clear
do _array
.clear
400 redef fun iterator
do return new ArraySetIterator[E
](_array
.iterator
)
402 # Assume the capacity is at least `cap`.
403 fun enlarge
(cap
: Int) do _array
.enlarge
(cap
)
405 private fun remove_at
(i
: Int)
407 _array
[i
] = _array
.last
411 # Create an empty set
412 init do _array
= new Array[E
]
414 # Create an empty set with a given capacity.
415 init with_capacity
(i
: Int) do _array
= new Array[E
].with_capacity
(i
)
418 # Iterators on sets implemented with arrays.
419 private class ArraySetIterator[E
: Object]
422 redef fun is_ok
do return _iter
.is_ok
424 redef fun next
do _iter
.next
426 redef fun item
: E
do return _iter
.item
428 init(iter
: ArrayIterator[E
]) do _iter
= iter
430 var _iter
: ArrayIterator[E
]
434 # Associative arrays implemented with an array of (key, value) pairs.
435 class ArrayMap[K
: Object, E
]
436 super CoupleMap[K
, E
]
443 return _items
[i
].second
445 return provide_default_value
(key
)
450 redef fun []=(key
, item
)
454 _items
[i
].second
= item
456 _items
.push
(new Couple[K
,E
](key
, item
))
460 redef var keys
: ArrayMapKeys[K
, E
] = new ArrayMapKeys[K
, E
](self)
461 redef var values
: ArrayMapValues[K
, E
] = new ArrayMapValues[K
, E
](self)
464 redef fun length
do return _items
.length
466 redef fun couple_iterator
do return _items
.iterator
468 redef fun is_empty
do return _items
.is_empty
470 redef fun clear
do _items
.clear
472 # Assume the capacity to be at least `cap`.
473 fun enlarge
(cap
: Int) do _items
.enlarge
(cap
)
475 redef fun couple_at
(key
)
486 var _items
: Array[Couple[K
,E
]]
488 # fast remove the ith element of the array
489 private fun remove_at_index
(i
: Int)
491 _items
[i
] = _items
.last
495 # The last positive result given by a index(1) call
496 var _last_index
: Int = 0
498 # Where is the `key` in `_item`?
499 # return -1 if not found
500 private fun index
(key
: K
): Int
503 if l
< _items
.length
and _items
[l
].first
== key
then return l
506 while i
< _items
.length
do
507 if _items
[i
].first
== key
then
519 _items
= new Array[Couple[K
,E
]]
523 private class ArrayMapKeys[K
: Object, E
]
524 super RemovableCollection[K
]
526 var map
: ArrayMap[K
, E
]
527 redef fun count
(k
) do if self.has
(k
) then return 1 else return 0
528 redef fun first
do return self.map
._items
.first
.first
529 redef fun has
(k
) do return self.map
.index
(k
) >= 0
530 redef fun has_only
(k
) do return (self.has
(k
) and self.length
== 1) or self.is_empty
531 redef fun is_empty
do return self.map
.is_empty
532 redef fun length
do return self.map
.length
533 redef fun iterator
do return new MapKeysIterator[K
, E
](self.map
.iterator
)
534 redef fun clear
do self.map
.clear
535 redef fun remove
(key
)
537 var i
= self.map
.index
(key
)
538 if i
>= 0 then self.map
.remove_at_index
(i
)
540 redef fun remove_all
(key
) do self.remove
(key
)
543 private class ArrayMapValues[K
: Object, E
]
544 super RemovableCollection[E
]
546 var map
: ArrayMap[K
, E
]
547 redef fun first
do return self.map
._items
.first
.second
548 redef fun is_empty
do return self.map
.is_empty
549 redef fun length
do return self.map
.length
550 redef fun iterator
do return new MapValuesIterator[K
, E
](self.map
.iterator
)
555 for i
in self.map
._items
do if i
.second
== item
then return true
560 redef fun has_only
(item
)
562 for i
in self.map
._items
do if i
.second
!= item
then return false
567 redef fun count
(item
)
570 for i
in self.map
._items
do if i
.second
== item
then nb
+= 1
574 redef fun clear
do self.map
.clear
576 redef fun remove
(item
)
579 var i
= map
._items
.length
- 1
581 if map
._items
[i
].second
== item
then
582 map
.remove_at_index
(i
)
589 redef fun remove_all
(item
)
592 var i
= map
._items
.length
- 1
594 if map
._items
[i
].second
== item
then
595 map
.remove_at_index
(i
)
603 # Others tools ################################################################
605 redef class Iterator[E
]
606 # Interate on `self` and build an array
609 var res
= new Array[E
]
618 redef class Collection[E
]
619 # Build a new array from a collection
626 # Native classes ##############################################################
628 # Subclasses of this class can create native arrays
629 interface ArrayCapable[E
]
630 # Get a new array of `size` elements.
631 protected fun calloc_array
(size
: Int): NativeArray[E
] is intern
634 # Native C array (void ...).
635 universal NativeArray[E
]
636 fun [](index
: Int): E
is intern
637 fun []=(index
: Int, item
: E
) is intern
638 fun copy_to
(dest
: NativeArray[E
], length
: Int) is intern
639 #fun =(o: NativeArray[E]): Bool is intern
640 #fun !=(o: NativeArray[E]): Bool is intern