lib/core/collection/circular_array.nit

   1 # This file is part of NIT (http://www.nitlanguage.org).
   2 #
   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
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   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.
  14
  15 # Efficient data structure to access both end of the sequence.
  16 module circular_array
  17
  18 import array
  19
  20 # Efficient data structure to access both end of the sequence.
  21 #
  22 # A circular array offers efficient random access,
  23 # efficient manipulation for both ends of the structure (push, pop, ) and
  24 # automatic amortized growth.
  25 #
  26 # Therefore it can be used as is or as and efficient queue (FIFO/LIFO)
  27 class CircularArray[E]
  28         super Sequence[E]
  29
  30         # The low-level storage of the items.
  31         #
  32         # Internally, there is two main configurations
  33         #
  34         # One part: from `head` to `tail` (inclusive)
  35         #
  36         # ~~~raw
  37         # ...0123...
  38         #    h  t
  39         # ~~~
  40         #
  41         # Two parts: from `head` to `capacity-1`,
  42         # then from `0` to `tail` (both inclusive)
  43         # Test with `head > tail`
  44         #
  45         # ~~~raw
  46         # 345....012
  47         #   t    h
  48         # ~~~
  49         #
  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.
  52         #
  53         # Initially the native is not allocated, the first one is done with `enlarge`
  54         private var native: NativeArray[E] is noautoinit
  55
  56         # The offset of the `first` item in `native`
  57         private var head = 0
  58
  59         # The offset of the `last` item in `native`
  60         private var tail: Int = -1
  61
  62         redef var length = 0
  63
  64         # Transform an index into an offset.
  65         #
  66         # The method takes care of the initial gap and the possible wrapping.
  67         #
  68         # REQUIRE: `0 <= index and index < length`
  69         private fun offset(index: Int): Int
  70         do
  71                 assert index >= 0
  72                 var head = self._head
  73                 var tail = self._tail
  74                 var offset = head + index
  75
  76                 if head > tail then
  77                         # Two parts
  78                         var capacity = native.length
  79                         if offset < capacity then
  80                                 return offset
  81                         end
  82                         offset -= capacity
  83                 end
  84
  85                 assert offset <= tail
  86                 return offset
  87         end
  88
  89         redef fun [](index) do return native[offset(index)]
  90
  91         redef fun []=(index, item) do
  92                 var l = length
  93                 if index == l then
  94                         push(item)
  95                         return
  96                 end
  97                 native[offset(index)] = item
  98         end
  99
 100         redef fun push(item) do
 101                 var l = length + 1
 102                 enlarge(l)
 103                 length = l
 104
 105                 var native = _native
 106                 var cap = native.length
 107                 var t = tail + 1
 108                 if t >= cap then t -= cap
 109
 110                 native[t] = item
 111                 tail = t
 112         end
 113
 114         redef fun add_all(items) do
 115                 enlarge length + items.length
 116                 super
 117         end
 118
 119         redef fun pop do
 120                 var l = length - 1
 121                 assert l >= 0
 122                 length = l
 123
 124                 var native = _native
 125                 var t = tail
 126                 var res = native[t]
 127
 128                 t -= 1
 129                 if t < 0 then t += native.length
 130                 tail = t
 131
 132                 return res
 133         end
 134
 135         redef fun unshift(item) do
 136                 var l = length + 1
 137                 enlarge(l)
 138                 length = l
 139
 140                 var native = _native
 141                 var h = head - 1
 142                 if h < 0 then h += native.length
 143
 144                 native[h] = item
 145                 head = h
 146         end
 147
 148         redef fun shift do
 149                 var l = length - 1
 150                 assert l >= 0
 151                 length = l
 152
 153                 var native = _native
 154                 var h = head
 155                 var res = native[h]
 156
 157                 h += 1
 158                 var cap = native.length
 159                 if h >= cap then h -= cap
 160                 head = h
 161
 162                 return res
 163         end
 164
 165         # Ensure at least a given capacity
 166         #
 167         # If the current capacity is enough, then no-op.
 168         fun enlarge(capacity: Int)
 169         do
 170                 # First allocation
 171                 if not isset _native then
 172                         var new_c = 8
 173                         while new_c < capacity do new_c *= 2
 174                         native = new NativeArray[E](new_c)
 175                         return
 176                 end
 177
 178                 # Compute more capacity
 179                 var c = native.length
 180                 if capacity <= c then return
 181                 var new_c = c
 182                 while new_c < capacity do new_c *= 2
 183
 184                 var new_native = new NativeArray[E](new_c)
 185
 186                 # Reallocation: just realign the parts on 0
 187                 if head > tail then
 188                         # Two parts
 189                         native.memmove(head, c-head, new_native, 0)
 190                         native.memmove(0, tail+1, new_native, c-head)
 191                 else
 192                         # One part
 193                         native.memmove(head, length, new_native, 0)
 194                 end
 195                 head = 0
 196                 tail = length - 1
 197                 native = new_native
 198         end
 199
 200         redef fun insert(item, index)
 201         do
 202                 # Special insertion at the end (is push)
 203                 if index >= length then
 204                         assert index == length
 205                         push(item)
 206                         return
 207                 end
 208                 assert index >= 0
 209
 210                 var new_len = length + 1
 211
 212                 # TODO be more efficient:
 213                 # Here, we just allocate a new native and copy everything.
 214
 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)
 219
 220                 # Copy everything
 221                 var i = 0
 222                 while i < index do
 223                         new_native[i] = self[i]
 224                         i += 1
 225                 end
 226                 new_native[index] = item
 227                 var l = length
 228                 while i < l do
 229                         new_native[i+1] = self[i]
 230                         i += 1
 231                 end
 232
 233                 # Use the new native array
 234                 length = new_len
 235                 head = 0
 236                 tail = new_len - 1
 237                 native = new_native
 238         end
 239
 240         redef fun clear do
 241                 length = 0
 242                 head = 0
 243                 tail = -1
 244         end
 245
 246         redef fun iterator do return new CircularArrayIterator[E](self)
 247 end
 248
 249 private class CircularArrayIterator[E]
 250         super IndexedIterator[E]
 251
 252         var array: CircularArray[E]
 253
 254         redef var index = 0
 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
 258 end