1 # This file is part of NIT (http://www.nitlanguage.org).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 # Efficient data structure to access both end of the sequence.
20 # Efficient data structure to access both end of the sequence.
22 # A circular array offers efficient random access,
23 # efficient manipulation for both ends of the structure (push, pop, ) and
24 # automatic amortized growth.
26 # Therefore it can be used as is or as and efficient queue (FIFO/LIFO)
27 class CircularArray[E
]
30 # The low-level storage of the items.
32 # Internally, there is two main configurations
34 # One part: from `head` to `tail` (inclusive)
41 # Two parts: from `head` to `capacity-1`,
42 # then from `0` to `tail` (both inclusive)
43 # Test with `head > tail`
50 # For consistency, *length* and *index* are used in the context of the sequence (self) and
51 # *capacity* and *offset* are used in the context of the native array.
53 # Initially the native is not allocated, the first one is done with `enlarge`
54 private var native
: NativeArray[E
] is noautoinit
56 # The offset of the `first` item in `native`
59 # The offset of the `last` item in `native`
60 private var tail
: Int = -1
64 # Transform an index into an offset.
66 # The method takes care of the initial gap and the possible wrapping.
68 # REQUIRE: `0 <= index and index < length`
69 private fun offset
(index
: Int): Int
74 var offset
= head
+ index
78 var capacity
= native
.length
79 if offset
< capacity
then
89 redef fun [](index
) do return native
[offset
(index
)]
91 redef fun []=(index
, item
) do
97 native
[offset
(index
)] = item
100 redef fun push
(item
) do
106 var cap
= native
.length
108 if t
>= cap
then t
-= cap
114 redef fun add_all
(items
) do
115 enlarge length
+ items
.length
129 if t
< 0 then t
+= native
.length
135 redef fun unshift
(item
) do
142 if h
< 0 then h
+= native
.length
158 var cap
= native
.length
159 if h
>= cap
then h
-= cap
165 # Ensure at least a given capacity
167 # If the current capacity is enough, then no-op.
168 fun enlarge
(capacity
: Int)
171 if not isset _native
then
173 while new_c
< capacity
do new_c
*= 2
174 native
= new NativeArray[E
](new_c
)
178 # Compute more capacity
179 var c
= native
.length
180 if capacity
<= c
then return
182 while new_c
< capacity
do new_c
*= 2
184 var new_native
= new NativeArray[E
](new_c
)
186 # Reallocation: just realign the parts on 0
189 native
.memmove
(head
, c-head
, new_native
, 0)
190 native
.memmove
(0, tail
+1, new_native
, c-head
)
193 native
.memmove
(head
, length
, new_native
, 0)
200 redef fun insert
(item
, index
)
202 # Special insertion at the end (is push)
203 if index
>= length
then
204 assert index
== length
210 var new_len
= length
+ 1
212 # TODO be more efficient:
213 # Here, we just allocate a new native and copy everything.
215 # Allocate a new native array
216 var c
= native
.length
217 while c
< new_len
do c
*= 2
218 var new_native
= new NativeArray[E
](c
)
223 new_native
[i
] = self[i
]
226 new_native
[index
] = item
229 new_native
[i
+1] = self[i
]
233 # Use the new native array
246 redef fun iterator
do return new CircularArrayIterator[E
](self)
249 private class CircularArrayIterator[E
]
250 super IndexedIterator[E
]
252 var array
: CircularArray[E
]
255 redef fun is_ok
do return index
< array
.length
256 redef fun item
do return array
[index
]
257 redef fun next
do index
+= 1