lib/standard/collection/array.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2004-2008 Jean Privat <jean@pryen.org>
   4 # Copyright 2008 Floréal Morandat <morandat@lirmm.fr>
   5 #
   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
  12 # another product.
  13
  14 # This module introduces the standard array structure.
  15 # It also implements two other abstract collections : ArrayMap and ArraySet
  16 package array
  17
  18 import abstract_collection
  19
  20 # One dimention array of objects.
  21 class AbstractArrayRead[E]
  22 special IndexedCollectionRead[E]
  23         # The current length
  24         redef readable var _length: Int = 0
  25
  26         redef fun is_empty do return _length == 0
  27
  28         redef fun has(item)
  29         do
  30                 var i = 0
  31                 var l = length
  32                 while i < l do
  33                         if self[i] == item then return true
  34                         i += 1
  35                 end
  36                 return false
  37         end
  38
  39         redef fun has_only(item)
  40         do
  41                 var i = 0
  42                 var l = length
  43                 while i < l do
  44                         if self[i] != item then return false
  45                         i += 1
  46                 end
  47                 return true
  48         end
  49
  50         redef fun has_key(index) do return index >= 0 and index < length
  51
  52         redef fun count(item)
  53         do
  54                 var res = 0
  55                 var i = 0
  56                 var l = length
  57                 while i < l do
  58                         if self[i] == item then res += 1
  59                         i += 1
  60                 end
  61                 return res
  62         end
  63
  64         redef fun index_of(item) do return index_of_from(item, 0)
  65
  66         fun last_index_of(item: E): Int do return last_index_of_from(item, length-1)
  67
  68         fun index_of_from(item: E, pos: Int): Int
  69         do
  70                 var i = pos
  71                 var len = length
  72                 while i < len do
  73                         if self[i] == item then
  74                                 return i
  75                         end
  76                         i += 1
  77                 end
  78                 return -1
  79         end
  80
  81         fun last_index_of_from(item: E, pos: Int): Int
  82         do
  83                 var i = pos
  84                 while i >= 0 do
  85                         if self[i] == item then
  86                                 return i
  87                         else
  88                                 i -= 1
  89                         end
  90                 end
  91                 return -1
  92         end
  93
  94         fun reversed: Array[E]
  95         do
  96                 var cmp = _length
  97                 var result = new Array[E].with_capacity(cmp)
  98                 while cmp > 0 do
  99                         cmp -= 1
 100                         result.add(self[cmp])
 101                 end
 102                 return result
 103         end
 104
 105         protected fun copy_to(start: Int, len: Int, dest: AbstractArray[E], new_start: Int)
 106         do
 107                 # TODO native one
 108                 var i = len
 109                 while i > 0 do
 110                         i -= 1
 111                         dest[new_start+i] = self[start+i]
 112                 end
 113         end
 114
 115         redef fun output
 116         do
 117                 var i = 0
 118                 var l = length
 119                 while i < l do
 120                         var e = self[i]
 121                         if e != null then e.output
 122                         i += 1
 123                 end
 124         end
 125
 126         redef fun iterator: ArrayIterator[E] do return new ArrayIterator[E](self)
 127
 128         # Two arrays are equals if they have the same items in the same order.
 129         redef fun ==(o)
 130         do
 131                 if not o isa AbstractArray[E] or o is null then return false
 132                 var l = length
 133                 if o.length != l then return false
 134                 var i = 0
 135                 while i < l do
 136                         if self[i] != o[i] then return false
 137                         i += 1
 138                 end
 139                 return true
 140         end
 141 end
 142
 143 # Resizeable one dimention array of objects.
 144 class AbstractArray[E]
 145 special AbstractArrayRead[E]
 146 special IndexedCollection[E]
 147         fun enlarge(cap: Int) is abstract
 148
 149         redef fun push(item) do add(item)
 150
 151         redef fun pop
 152         do
 153                 assert not_empty: not is_empty
 154                 var r = last
 155                 _length -= 1
 156                 return r
 157         end
 158
 159         redef fun shift
 160         do
 161                 assert not_empty: not is_empty
 162                 var r = first
 163                 var i = 1
 164                 var l = length
 165                 while i < l do
 166                         self[i-1] = self[i]
 167                         i += 1
 168                 end
 169                 _length = l - 1
 170                 return r
 171         end
 172
 173         redef fun unshift(item)
 174         do
 175                 var i = length - 1
 176                 while i > 0 do
 177                         self[i+1] = self[i]
 178                         i -= 1
 179                 end
 180                 self[0] = item
 181         end
 182
 183         fun insert(item: E, pos: Int)
 184         do
 185                 enlarge(length + 1)
 186                 copy_to(pos, length-pos, self, pos + 1)
 187                 self[pos] = item
 188         end
 189
 190         redef fun add(item) do self[length] = item
 191
 192         redef fun clear do _length = 0
 193
 194         redef fun remove(item) do remove_at(index_of(item))
 195
 196         redef fun remove_all(item)
 197         do
 198                 var i = index_of(item)
 199                 while i >= 0 do
 200                         remove_at(i)
 201                         i = index_of_from(item, i)
 202                 end
 203         end
 204
 205         redef fun remove_at(i)
 206         do
 207                 var l = length
 208                 if i >= 0 and i < l then
 209                         var j = i + 1
 210                         while j < l do
 211                                 self[j-1] = self[j]
 212                                 j += 1
 213                         end
 214                         _length = l - 1
 215                 end
 216         end
 217 end
 218
 219 # Resizeable one dimention array of objects.
 220 #
 221 # Arrays have a literal representation.
 222 #     a = [12, 32, 8]
 223 # is equivalent with:
 224 #     a = new Array[Int]
 225 #     a.push(12)
 226 #     a.push(32)
 227 #     a.push(8)
 228 class Array[E]
 229 special AbstractArray[E]
 230 special ArrayCapable[E]
 231         redef fun [](index)
 232         do
 233                 assert index: index >= 0 and index < _length
 234                 return _items[index]
 235         end
 236
 237         redef fun []=(index, item)
 238         do
 239                 assert index: index >= 0 and index < _length + 1
 240                 if _capacity <= index then
 241                         enlarge(index + 1)
 242                 end
 243                 if _length <= index then
 244                         _length = index + 1
 245                 end
 246                 _items[index] = item
 247         end
 248
 249         redef fun add(item)
 250         do
 251                 var l = _length
 252                 if _capacity <= l then
 253                         enlarge(l + 1)
 254                 end
 255                 _length = l + 1
 256                 _items[l] = item
 257         end
 258
 259         redef fun enlarge(cap)
 260         do
 261                 var c = _capacity
 262                 if cap <= c then return
 263                 while c <= cap do c = c * 2 + 2
 264                 var a = calloc_array(c)
 265                 if _capacity > 0 then _items.copy_to(a, _length)
 266                 _items = a
 267                 _capacity = c
 268         end
 269
 270         # Create an empty array.
 271         init
 272         do
 273                 _capacity = 0
 274                 _length = 0
 275         end
 276
 277         # Create an array with some `items'.
 278         init with_items(objects: E...)
 279         do
 280                 _items = objects._items
 281                 _capacity = objects._capacity
 282                 _length = objects.length
 283         end
 284
 285         # Create an empty array with a given capacity.
 286         init with_capacity(cap: Int)
 287         do
 288                 assert positive: cap >= 0
 289                 _items = calloc_array(cap)
 290                 _capacity = cap
 291                 _length = 0
 292         end
 293
 294         # Create an array of `count' elements
 295         init filled_with(value: E, count: Int)
 296         do
 297                 assert positive: count >= 0
 298                 _items = calloc_array(count)
 299                 _capacity = count
 300                 _length = count
 301                 var i = 0
 302                 while i < count do
 303                         self[i] = value
 304                         i += 1
 305                 end
 306         end
 307
 308         # Create a array filled with a given native array.
 309         init with_native(nat: NativeArray[E], size: Int)
 310         do
 311                 assert positive: size >= 0
 312                 _items = nat
 313                 _capacity = size
 314                 _length = size
 315         end
 316
 317         # The internal storage.
 318         var _items: nullable NativeArray[E] = null
 319
 320         # Do not use this method
 321         # FIXME: Remove it once modules can intrude non local modules
 322         fun intern_items: NativeArray[E] do return _items.as(not null)
 323
 324         # The size of `_items'.
 325         var _capacity: Int = 0
 326 end
 327
 328 # An `Iterator' on `AbstractArray'
 329 class ArrayIterator[E]
 330 special IndexedIterator[E]
 331         redef fun item do return _array[_index]
 332
 333         # redef fun item=(e) do _array[_index] = e
 334
 335         redef fun is_ok do return _index < _array.length
 336
 337         redef fun next do _index += 1
 338
 339         init(a: AbstractArrayRead[E])
 340         do
 341                 _array = a
 342                 _index = 0
 343         end
 344
 345         redef readable var _index: Int = 0
 346         var _array: AbstractArrayRead[E]
 347 end
 348
 349 # Others collections ##########################################################
 350
 351 # A set implemented with an Array.
 352 class ArraySet[E]
 353 special Set[E]
 354         # The stored elements.
 355         var _array: Array[E]
 356
 357         redef fun has(e) do return _array.has(e)
 358
 359         redef fun add(e) do if not _array.has(e) then _array.add(e)
 360
 361         redef fun is_empty do return _array.is_empty
 362
 363         redef fun length do return _array.length
 364
 365         redef fun first
 366         do
 367                 assert _array.length > 0
 368                 return _array.first
 369         end
 370
 371         redef fun remove(item)
 372         do
 373                 var i = _array.index_of(item)
 374                 if i >= 0 then remove_at(i)
 375         end
 376
 377         redef fun remove_all(item) do remove(item)
 378
 379         redef fun clear do _array.clear
 380
 381         redef fun iterator do return new ArraySetIterator[E](_array.iterator)
 382
 383         # Assume the capacitydd is at least `cap'.
 384         fun enlarge(cap: Int) do _array.enlarge(cap)
 385
 386         private fun remove_at(i: Int)
 387         do
 388                 _array[i] = _array.last
 389                 _array.pop
 390         end
 391
 392         # Create an empty set
 393         init do _array = new Array[E]
 394
 395         # Create an empty set with a given capacity.
 396         init with_capacity(i: Int) do _array = new Array[E].with_capacity(i)
 397 end
 398
 399 # Iterators on sets implemented with arrays.
 400 class ArraySetIterator[E]
 401 special Iterator[E]
 402
 403         redef fun is_ok do return _iter.is_ok
 404
 405         redef fun next do _iter.next
 406
 407         redef fun item: E do return _iter.item
 408
 409         init(iter: ArrayIterator[E]) do _iter = iter
 410
 411         var _iter: ArrayIterator[E]
 412 end
 413
 414
 415 # Associative arrays implemented with an array of (key, value) pairs.
 416 class ArrayMap[K, E]
 417 special CoupleMap[K, E]
 418
 419         # O(n)
 420         redef fun [](key)
 421         do
 422                 var i = index(key)
 423                 if i >= 0 then
 424                         return _items[i].second
 425                 else
 426                         abort
 427                 end
 428         end
 429
 430         # O(n)
 431         redef fun []=(key, item)
 432         do
 433                 var i = index(key)
 434                 if i >= 0 then
 435                         _items[i].second = item
 436                 else
 437                         _items.push(new Couple[K,E](key, item))
 438                 end
 439         end
 440
 441         # O(n)
 442         redef fun has_key(key) do return index(key) >= 0
 443
 444         # O(n)
 445         redef fun has(item)
 446         do
 447                 for i in _items do if i.second == item then return true
 448                 return false
 449         end
 450
 451         # O(n)
 452         redef fun has_only(item)
 453         do
 454                 for i in _items do if i.second != item then return false
 455                 return true
 456         end
 457
 458         # O(1)
 459         redef fun length do return _items.length
 460
 461         redef fun first do return _items.first.first
 462
 463         # O(n)
 464         redef fun count(item)
 465         do
 466                 var nb = 0
 467                 for i in _items do if i.second == item then nb += 1
 468                 return nb
 469         end
 470
 471         redef fun iterator: CoupleMapIterator[K, E] do return new CoupleMapIterator[K, E](_items.iterator)
 472
 473         redef fun is_empty do return _items.is_empty
 474
 475         redef fun remove(item)
 476         do
 477                 var i = _items.length - 1
 478                 while i >= 0 do
 479                         if _items[i].second == item then
 480                                 remove_at_index(i)
 481                                 return
 482                         end
 483                         i -= 1
 484                 end
 485         end
 486
 487         redef fun remove_all(item: E)
 488         do
 489                 var i = _items.length - 1
 490                 while i >= 0 do
 491                         if _items[i].second == item then
 492                                 remove_at_index(i)
 493                         end
 494                         i -= 1
 495                 end
 496         end
 497
 498         redef fun remove_at(key)
 499         do
 500                 var i = index(key)
 501                 if i >= 0 then remove_at_index(i)
 502         end
 503
 504         redef fun clear do _items.clear
 505
 506         # Assume the capacity to be at least `cap'.
 507         fun enlarge(cap: Int) do _items.enlarge(cap)
 508
 509         redef fun couple_at(key)
 510         do
 511                 var i = index(key)
 512                 if i >= 0 then
 513                         return _items[i]
 514                 else
 515                         return null
 516                 end
 517         end
 518
 519         # Internal storage.
 520         var _items: Array[Couple[K,E]]
 521
 522         # fast remove the ith element of the array
 523         private fun remove_at_index(i: Int)
 524         do
 525                 _items[i] = _items.last
 526                 _items.pop
 527         end
 528
 529         # The last positive result given by a index(1) call
 530         var _last_index: Int = 0
 531
 532         # Where is the `key' in `_item'?
 533         # return -1 if not found
 534         private fun index(key: K): Int
 535         do
 536                 var l = _last_index
 537                 if l < _items.length and _items[l].first == key then return l
 538
 539                 var i = 0
 540                 while i < _items.length do
 541                         if _items[i].first == key then
 542                                 _last_index = i
 543                                 return i
 544                         end
 545                         i += 1
 546                 end
 547                 return -1
 548         end
 549
 550         # A new empty map.
 551         init
 552         do
 553                 _items = new Array[Couple[K,E]]
 554         end
 555 end
 556
 557 # Others tools ################################################################
 558
 559 redef class Iterator[E]
 560         # Interate on `self' and build an array
 561         fun to_a: Array[E]
 562         do
 563                 var res = new Array[E]
 564                 while is_ok do
 565                         res.add(item)
 566                         next
 567                 end
 568                 return res
 569         end
 570 end
 571
 572 redef class Collection[E]
 573         # Build a new array from a collection
 574         fun to_a: Array[E]
 575         do
 576                 return iterator.to_a
 577         end
 578 end
 579
 580 # Native classes ##############################################################
 581
 582 # Subclasses of this class can create native arrays
 583 interface ArrayCapable[E]
 584         # Get a new array of `size' elements.
 585         protected fun calloc_array(size: Int): NativeArray[E] is intern
 586 end
 587
 588 # Native C array (void ...).
 589 universal NativeArray[E]
 590         fun [](index: Int): E is intern
 591         fun []=(index: Int, item: E) is intern
 592         fun copy_to(dest: NativeArray[E], length: Int) is intern
 593         #fun =(o: NativeArray[E]): Bool is intern
 594         #fun !=(o: NativeArray[E]): Bool is intern
 595 end