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