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 dimention array of objects.
21 class AbstractArrayRead[E
]
22 special SequenceRead[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
50 redef fun has_key
(index
) do return index
>= 0 and index
< length
58 if self[i
] == item
then res
+= 1
64 redef fun index_of
(item
) do return index_of_from
(item
, 0)
66 fun last_index_of
(item
: E
): Int do return last_index_of_from
(item
, length-1
)
68 fun index_of_from
(item
: E
, pos
: Int): Int
73 if self[i
] == item
then
81 fun last_index_of_from
(item
: E
, pos
: Int): Int
85 if self[i
] == item
then
94 fun reversed
: Array[E
]
97 var result
= new Array[E
].with_capacity
(cmp
)
100 result
.add
(self[cmp
])
105 protected fun copy_to
(start
: Int, len
: Int, dest
: AbstractArray[E
], new_start
: Int)
111 dest
[new_start
+i
] = self[start
+i
]
121 if e
!= null then e
.output
126 redef fun iterator
: ArrayIterator[E
] do return new ArrayIterator[E
](self)
128 # Two arrays are equals if they have the same items in the same order.
131 if not o
isa AbstractArray[E
] or o
is null then return false
133 if o
.length
!= l
then return false
136 if self[i
] != o
[i
] then return false
143 # Resizeable one dimention array of objects.
144 class AbstractArray[E
]
145 special AbstractArrayRead[E
]
147 fun enlarge
(cap
: Int) is abstract
149 redef fun push
(item
) do add
(item
)
153 assert not_empty
: not is_empty
161 assert not_empty
: not is_empty
173 redef fun unshift
(item
)
183 fun insert
(item
: E
, pos
: Int)
186 copy_to
(pos
, length-pos
, self, pos
+ 1)
190 redef fun add
(item
) do self[length
] = item
192 redef fun clear
do _length
= 0
194 redef fun remove
(item
) do remove_at
(index_of
(item
))
196 redef fun remove_all
(item
)
198 var i
= index_of
(item
)
201 i
= index_of_from
(item
, i
)
205 redef fun remove_at
(i
)
208 if i
>= 0 and i
< l
then
219 # Resizeable one dimention array of objects.
221 # Arrays have a literal representation.
223 # is equivalent with:
229 special AbstractArray[E
]
230 special ArrayCapable[E
]
245 assert index
: index
>= 0 and index
< _length
249 redef fun []=(index
, item
)
251 assert index
: index
>= 0 and index
< _length
+ 1
252 if _capacity
<= index
then
255 if _length
<= index
then
264 if _capacity
<= l
then
271 redef fun enlarge
(cap
)
274 if cap
<= c
then return
275 while c
<= cap
do c
= c
* 2 + 2
276 var a
= calloc_array
(c
)
277 if _capacity
> 0 then _items
.copy_to
(a
, _length
)
282 # Create an empty array.
289 # Create an array with some `items'.
290 init with_items
(objects
: E
...)
292 _items
= objects
._items
293 _capacity
= objects
._capacity
294 _length
= objects
.length
297 # Create an empty array with a given capacity.
298 init with_capacity
(cap
: Int)
300 assert positive
: cap
>= 0
301 _items
= calloc_array
(cap
)
306 # Create an array of `count' elements
307 init filled_with
(value
: E
, count
: Int)
309 assert positive
: count
>= 0
310 _items
= calloc_array
(count
)
320 # Create a array filled with a given native array.
321 init with_native
(nat
: NativeArray[E
], size
: Int)
323 assert positive
: size
>= 0
329 # The internal storage.
330 var _items
: nullable NativeArray[E
] = null
332 # Do not use this method
333 # FIXME: Remove it once modules can intrude non local modules
334 fun intern_items
: NativeArray[E
] do return _items
.as(not null)
336 # The size of `_items'.
337 var _capacity
: Int = 0
339 # Sort the array using the !cmp function.
343 sub_sort
(0, length-1
) !cmp
(x
,y
) = cmp
(x
, y
)
346 # Sort `array' between `from' and `to' indices
347 private fun sub_sort
(from
: Int, to
: Int)
352 else if from
+ 7 < to
then
353 var pivot
= self[from
]
357 while i
<= to
and cmp
(self[i
], pivot
) <= 0 do i
+= 1
358 while j
> i
and cmp
(self[j
], pivot
) >= 0 do j
-= 1
365 self[from
] = self[i-1
]
367 sub_sort
(from
, i-2
) !cmp
(x
,y
) = cmp
(x
, y
)
368 sub_sort
(i
, to
) !cmp
(x
,y
) = cmp
(x
, y
)
376 if cmp
(min_v
, self[j
]) > 0 then
392 # An `Iterator' on `AbstractArray'
393 class ArrayIterator[E
]
394 special IndexedIterator[E
]
395 redef fun item
do return _array
[_index
]
397 # redef fun item=(e) do _array[_index] = e
399 redef fun is_ok
do return _index
< _array
.length
401 redef fun next
do _index
+= 1
403 init(a
: AbstractArrayRead[E
])
409 redef readable var _index
: Int = 0
410 var _array
: AbstractArrayRead[E
]
413 # Others collections ##########################################################
415 # A set implemented with an Array.
416 class ArraySet[E
: Object]
418 # The stored elements.
421 redef fun has
(e
) do return _array
.has
(e
)
423 redef fun add
(e
) do if not _array
.has
(e
) then _array
.add
(e
)
425 redef fun is_empty
do return _array
.is_empty
427 redef fun length
do return _array
.length
431 assert _array
.length
> 0
435 redef fun remove
(item
)
437 var i
= _array
.index_of
(item
)
438 if i
>= 0 then remove_at
(i
)
441 redef fun remove_all
(item
) do remove
(item
)
443 redef fun clear
do _array
.clear
445 redef fun iterator
do return new ArraySetIterator[E
](_array
.iterator
)
447 # Assume the capacitydd is at least `cap'.
448 fun enlarge
(cap
: Int) do _array
.enlarge
(cap
)
450 private fun remove_at
(i
: Int)
452 _array
[i
] = _array
.last
456 # Create an empty set
457 init do _array
= new Array[E
]
459 # Create an empty set with a given capacity.
460 init with_capacity
(i
: Int) do _array
= new Array[E
].with_capacity
(i
)
463 # Iterators on sets implemented with arrays.
464 class ArraySetIterator[E
: Object]
467 redef fun is_ok
do return _iter
.is_ok
469 redef fun next
do _iter
.next
471 redef fun item
: E
do return _iter
.item
473 init(iter
: ArrayIterator[E
]) do _iter
= iter
475 var _iter
: ArrayIterator[E
]
479 # Associative arrays implemented with an array of (key, value) pairs.
480 class ArrayMap[K
: Object, E
]
481 special CoupleMap[K
, E
]
488 return _items
[i
].second
495 redef fun []=(key
, item
)
499 _items
[i
].second
= item
501 _items
.push
(new Couple[K
,E
](key
, item
))
506 redef fun has_key
(key
) do return index
(key
) >= 0
511 for i
in _items
do if i
.second
== item
then return true
516 redef fun has_only
(item
)
518 for i
in _items
do if i
.second
!= item
then return false
523 redef fun length
do return _items
.length
525 redef fun first
do return _items
.first
.second
528 redef fun count
(item
)
531 for i
in _items
do if i
.second
== item
then nb
+= 1
535 redef fun iterator
: CoupleMapIterator[K
, E
] do return new CoupleMapIterator[K
, E
](_items
.iterator
)
537 redef fun is_empty
do return _items
.is_empty
539 redef fun remove
(item
)
541 var i
= _items
.length
- 1
543 if _items
[i
].second
== item
then
551 redef fun remove_all
(item
: E
)
553 var i
= _items
.length
- 1
555 if _items
[i
].second
== item
then
562 redef fun remove_at
(key
)
565 if i
>= 0 then remove_at_index
(i
)
568 redef fun clear
do _items
.clear
570 # Assume the capacity to be at least `cap'.
571 fun enlarge
(cap
: Int) do _items
.enlarge
(cap
)
573 redef fun couple_at
(key
)
584 var _items
: Array[Couple[K
,E
]]
586 # fast remove the ith element of the array
587 private fun remove_at_index
(i
: Int)
589 _items
[i
] = _items
.last
593 # The last positive result given by a index(1) call
594 var _last_index
: Int = 0
596 # Where is the `key' in `_item'?
597 # return -1 if not found
598 private fun index
(key
: K
): Int
601 if l
< _items
.length
and _items
[l
].first
== key
then return l
604 while i
< _items
.length
do
605 if _items
[i
].first
== key
then
617 _items
= new Array[Couple[K
,E
]]
621 # Others tools ################################################################
623 redef class Iterator[E
]
624 # Interate on `self' and build an array
627 var res
= new Array[E
]
636 redef class Collection[E
]
637 # Build a new array from a collection
644 # Native classes ##############################################################
646 # Subclasses of this class can create native arrays
647 interface ArrayCapable[E
]
648 # Get a new array of `size' elements.
649 protected fun calloc_array
(size
: Int): NativeArray[E
] is intern
652 # Native C array (void ...).
653 universal NativeArray[E
]
654 fun [](index
: Int): E
is intern
655 fun []=(index
: Int, item
: E
) is intern
656 fun copy_to
(dest
: NativeArray[E
], length
: Int) is intern
657 #fun =(o: NativeArray[E]): Bool is intern
658 #fun !=(o: NativeArray[E]): Bool is intern