d95911b7be7235db74607a292668487aa3e008d4
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 IndexedCollectionRead[E
]
24 redef readable attr _length
: Int = 0
26 redef meth is_empty
do return _length
== 0
33 if self[i
] == item
then return true
39 redef meth has_only
(item
)
44 if self[i
] != item
then return false
50 redef meth has_key
(index
) do return index
>= 0 and index
< length
52 redef meth count
(item
)
58 if self[i
] == item
then res
+= 1
64 redef meth index_of
(item
) do return index_of_from
(item
, 0)
66 meth last_index_of
(item
: E
): Int do return last_index_of_from
(item
, length-1
)
68 meth index_of_from
(item
: E
, pos
: Int): Int
73 if self[i
] == item
then
81 meth last_index_of_from
(item
: E
, pos
: Int): Int
85 if self[i
] == item
then
94 meth reversed
: Array[E
]
97 var result
= new Array[E
].with_capacity
(cmp
)
100 result
.add
(self[cmp
])
105 protected meth 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 meth 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
132 assert o
isa AbstractArray[E
]
134 if o
.length
!= l
then return false
137 if self[i
] != o
[i
] then return false
144 # Resizeable one dimention array of objects.
145 class AbstractArray[E
]
146 special AbstractArrayRead[E
]
147 special IndexedCollection[E
]
148 meth enlarge
(cap
: Int) is abstract
150 redef meth push
(item
) do add
(item
)
154 assert not_empty
: not is_empty
162 assert not_empty
: not is_empty
174 redef meth unshift
(item
)
184 meth insert
(item
: E
, pos
: Int)
187 copy_to
(pos
, length-pos
, self, pos
+ 1)
191 redef meth add
(item
) do self[length
] = item
193 redef meth clear
do _length
= 0
195 redef meth remove
(item
) do remove_at
(index_of
(item
))
197 redef meth remove_all
(item
)
199 var i
= index_of
(item
)
202 i
= index_of_from
(item
, i
)
206 redef meth remove_at
(i
)
209 if i
>= 0 and i
< l
then
220 # Resizeable one dimention array of objects.
222 # Arrays have a literal representation.
224 # is equivalent with:
230 special AbstractArray[E
]
231 special ArrayCapable[E
]
234 assert index
: index
>= 0 and index
< _length
238 redef meth
[]=(index
, item
)
240 assert index
: index
>= 0 and index
< _length
+ 1
241 if _capacity
<= index
then
244 if _length
<= index
then
250 redef meth enlarge
(cap
)
253 if cap
<= c
then return
254 while c
<= cap
do c
= c
* 2 + 2
255 var a
= calloc_array
(c
)
256 if _capacity
> 0 then _items
.copy_to
(a
, _length
)
261 # Create an empty array.
268 # Create an array with some `items'.
269 init with_items
(objects
: E
...)
271 _items
= objects
._items
272 _capacity
= objects
._capacity
273 _length
= objects
.length
276 # Create an empty array with a given capacity.
277 init with_capacity
(cap
: Int)
279 assert positive
: cap
>= 0
280 _items
= calloc_array
(cap
)
285 # Create an array of `count' elements
286 init filled_with
(value
: E
, count
: Int)
288 assert positive
: count
>= 0
289 _items
= calloc_array
(count
)
299 # Create a array filled with a given native array.
300 init with_native
(nat
: NativeArray[E
], size
: Int)
302 assert positive
: size
>= 0
308 # The internal storage.
309 attr _items
: NativeArray[E
] = null
311 # The size of `_items'.
312 attr _capacity
: Int = 0
315 # An `Iterator' on `AbstractArray'
316 class ArrayIterator[E
]
317 special IndexedIterator[E
]
318 redef meth item
do return _array
[_index
]
320 # redef meth item=(e) do _array[_index] = e
322 redef meth is_ok
do return _index
< _array
.length
324 redef meth next
do _index
+= 1
326 init(a
: AbstractArrayRead[E
])
328 assert not_nil
: a
!= null
333 redef readable attr _index
: Int = 0
334 attr _array
: AbstractArrayRead[E
]
337 # Others collections ##########################################################
339 # A set implemented with an Array.
342 # The stored elements.
343 attr _array
: Array[E
]
345 redef meth has
(e
) do return _array
.has
(e
)
347 redef meth add
(e
) do if not _array
.has
(e
) then _array
.add
(e
)
349 redef meth is_empty
do return _array
.is_empty
351 redef meth length
do return _array
.length
355 assert _array
.length
> 0
359 redef meth remove
(item
)
361 var i
= _array
.index_of
(item
)
362 if i
>= 0 then remove_at
(i
)
365 redef meth remove_all
(item
) do remove
(item
)
367 redef meth clear
do _array
.clear
369 redef meth iterator
do return new ArraySetIterator[E
](_array
.iterator
)
371 # Assume the capacitydd is at least `cap'.
372 meth enlarge
(cap
: Int) do _array
.enlarge
(cap
)
374 private meth remove_at
(i
: Int)
376 _array
[i
] = _array
.last
380 # Create an empty set
381 init do _array
= new Array[E
]
383 # Create an empty set with a given capacity.
384 init with_capacity
(i
: Int) do _array
= new Array[E
].with_capacity
(i
)
387 # Iterators on sets implemented with arrays.
388 class ArraySetIterator[E
]
391 redef meth is_ok
do return _iter
.is_ok
393 redef meth next
do _iter
.next
395 redef meth item
: E
do return _iter
.item
397 init(iter
: ArrayIterator[E
]) do _iter
= iter
399 attr _iter
: ArrayIterator[E
]
403 # Associative arrays implemented with an array of (key, value) pairs.
405 special CoupleMap[K
, E
]
412 return _items
[i
].second
419 redef meth
[]=(key
, item
)
423 _items
[i
].second
= item
425 _items
.push
(new Couple[K
,E
](key
, item
))
430 redef meth has_key
(key
) do return index
(key
) >= 0
435 for i
in _items
do if i
.second
== item
then return true
440 redef meth has_only
(item
)
442 for i
in _items
do if i
.second
!= item
then return false
447 redef meth length
do return _items
.length
449 redef meth first
do return _items
.first
.first
452 redef meth count
(item
)
455 for i
in _items
do if i
.second
== item
then nb
+= 1
459 redef meth iterator
: CoupleMapIterator[K
, E
] do return new CoupleMapIterator[K
, E
](_items
.iterator
)
461 redef meth is_empty
do return _items
.is_empty
463 redef meth remove
(item
)
465 var i
= _items
.length
- 1
467 if _items
[i
].second
== item
then
475 redef meth remove_all
(item
: E
)
477 var i
= _items
.length
- 1
479 if _items
[i
].second
== item
then
486 redef meth remove_at
(key
)
489 if i
>= 0 then remove_at_index
(i
)
492 redef meth clear
do _items
.clear
494 # Assume the capacity to be at least `cap'.
495 meth enlarge
(cap
: Int) do _items
.enlarge
(cap
)
497 redef meth couple_at
(key
)
508 attr _items
: Array[Couple[K
,E
]]
510 # fast remove the ith element of the array
511 private meth remove_at_index
(i
: Int)
513 _items
[i
] = _items
.last
517 # The last positive result given by a index(1) call
518 attr _last_index
: Int = 0
520 # Where is the `key' in `_item'?
521 # return -1 if not found
522 private meth index
(key
: K
): Int
525 if l
< _items
.length
and _items
[l
].first
== key
then return l
528 while i
< _items
.length
do
529 if _items
[i
].first
== key
then
541 _items
= new Array[Couple[K
,E
]]
545 # Others tools ################################################################
547 redef class Iterator[E
]
548 # Interate on `self' and build an array
551 var res
= new Array[E
]
560 redef class Collection[E
]
561 # Build a new array from a collection
568 # Native classes ##############################################################
570 # Subclasses of this class can create native arrays
571 interface ArrayCapable[E
]
572 # Get a new array of `size' elements.
573 protected meth calloc_array
(size
: Int): NativeArray[E
] is intern
576 # Native C array (void ...).
577 universal NativeArray[E
]
578 meth
[](index
: Int): E
is intern
579 meth
[]=(index
: Int, item
: E
) is intern
580 meth copy_to
(dest
: NativeArray[E
], length
: Int) is intern
581 #meth =(o: NativeArray[E]): Bool is intern
582 #meth !=(o: NativeArray[E]): Bool is intern