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 var length = 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         redef fun last_index_of(item: E): Int do return last_index_of_from(item, length-1)
  65
  66         redef fun index_of_from(item: E, pos: Int): Int
  67         do
  68                 var i = pos
  69                 var len = length
  70                 while i < len do
  71                         if self[i] == item then
  72                                 return i
  73                         end
  74                         i += 1
  75                 end
  76                 return -1
  77         end
  78
  79         redef fun last_index_of_from(item: E, pos: Int): Int
  80         do
  81                 var i = pos
  82                 while i >= 0 do
  83                         if self[i] == item then
  84                                 return i
  85                         else
  86                                 i -= 1
  87                         end
  88                 end
  89                 return -1
  90         end
  91
  92         # Return a new array that is the reverse of `self`
  93         #
  94         #     assert [1,2,3].reversed      ==  [3, 2, 1]
  95         fun reversed: Array[E]
  96         do
  97                 var cmp = _length
  98                 var result = new Array[E].with_capacity(cmp)
  99                 while cmp > 0 do
 100                         cmp -= 1
 101                         result.add(self[cmp])
 102                 end
 103                 return result
 104         end
 105
 106         # Copy a portion of `self` to an other array.
 107         #
 108         #     var a = [1, 2, 3, 4]
 109         #     var b = [10, 20, 30, 40, 50]
 110         #     a.copy_to(1, 2, b, 2)
 111         #     assert b      ==  [10, 20, 2, 3, 50]
 112         fun copy_to(start: Int, len: Int, dest: AbstractArray[E], new_start: Int)
 113         do
 114                 # TODO native one
 115                 var i = len
 116                 while i > 0 do
 117                         i -= 1
 118                         dest[new_start+i] = self[start+i]
 119                 end
 120         end
 121
 122         redef fun output
 123         do
 124                 var i = 0
 125                 var l = length
 126                 while i < l do
 127                         var e = self[i]
 128                         if e != null then e.output
 129                         i += 1
 130                 end
 131         end
 132
 133         redef fun iterator: ArrayIterator[E] do return new ArrayIterator[E](self)
 134         redef fun reverse_iterator do return new ArrayReverseIterator[E](self)
 135 end
 136
 137 # Resizable one dimension array of objects.
 138 abstract class AbstractArray[E]
 139         super AbstractArrayRead[E]
 140         super Sequence[E]
 141
 142         # Force the capacity to be at least `cap`.
 143         # The capacity of the array is an internal information.
 144         # However, this method can be used to prepare a large amount of add
 145         fun enlarge(cap: Int) is abstract
 146
 147         redef fun push(item) do add(item)
 148
 149         redef fun pop
 150         do
 151                 assert not_empty: not is_empty
 152                 var r = last
 153                 _length -= 1
 154                 return r
 155         end
 156
 157         redef fun shift
 158         do
 159                 assert not_empty: not is_empty
 160                 var r = first
 161                 var i = 1
 162                 var l = length
 163                 while i < l do
 164                         self[i-1] = self[i]
 165                         i += 1
 166                 end
 167                 _length = l - 1
 168                 return r
 169         end
 170
 171         redef fun unshift(item)
 172         do
 173                 var i = length - 1
 174                 while i >= 0 do
 175                         self[i+1] = self[i]
 176                         i -= 1
 177                 end
 178                 self[0] = item
 179         end
 180
 181         redef fun insert(item: E, pos: Int)
 182         do
 183                 enlarge(length + 1)
 184                 copy_to(pos, length-pos, self, pos + 1)
 185                 self[pos] = item
 186         end
 187
 188         redef fun insert_all(coll, pos)
 189         do
 190                 var l = coll.length
 191                 if l == 0 then return
 192                 enlarge(length + l)
 193                 _length += l
 194                 copy_to(pos, length-pos-l, self, pos + l)
 195                 for c in coll do
 196                         self[pos] = c
 197                         pos += 1
 198                 end
 199         end
 200
 201         redef fun add(item) do self[length] = item
 202
 203         redef fun clear do _length = 0
 204
 205         redef fun remove(item) do remove_at(index_of(item))
 206
 207         redef fun remove_all(item)
 208         do
 209                 var i = index_of(item)
 210                 while i >= 0 do
 211                         remove_at(i)
 212                         i = index_of_from(item, i)
 213                 end
 214         end
 215
 216         redef fun remove_at(i)
 217         do
 218                 var l = length
 219                 if i >= 0 and i < l then
 220                         var j = i + 1
 221                         while j < l do
 222                                 self[j-1] = self[j]
 223                                 j += 1
 224                         end
 225                         _length = l - 1
 226                 end
 227         end
 228
 229         # Invert two elements in the array
 230         #
 231         #     var a = [10, 20, 30, 40]
 232         #     a.swap_at(1, 3)
 233         #     assert a      ==  [10, 40, 30, 20]
 234         fun swap_at(a: Int,b: Int)
 235         do
 236             var e = self[a]
 237             self[a] = self[b]
 238             self[b] = e
 239         end
 240 end
 241
 242 # Resizable one dimension array of objects.
 243 #
 244 # Arrays have a literal representation.
 245 #
 246 #     var a = [12, 32, 8]
 247 #     # is equivalent with:
 248 #     var b = new Array[Int]
 249 #     b.push(12)
 250 #     b.push(32)
 251 #     b.push(8)
 252 #     assert a == b
 253 class Array[E]
 254         super AbstractArray[E]
 255         super Cloneable
 256
 257         redef fun [](index)
 258         do
 259                 assert index: index >= 0 and index < _length
 260                 return _items[index]
 261         end
 262
 263         redef fun []=(index, item)
 264         do
 265                 assert index: index >= 0 and index < _length + 1
 266                 if _capacity <= index then
 267                         enlarge(index + 1)
 268                 end
 269                 if _length <= index then
 270                         _length = index + 1
 271                 end
 272                 _items[index] = item
 273         end
 274
 275         redef fun add(item)
 276         do
 277                 var l = _length
 278                 if _capacity <= l then
 279                         enlarge(l + 1)
 280                 end
 281                 _length = l + 1
 282                 _items[l] = item
 283         end
 284
 285         # Slight optimization for arrays
 286         redef fun add_all(items)
 287         do
 288                 var l = _length
 289                 var nl = l + items.length
 290                 if _capacity < nl then
 291                         enlarge nl
 292                 end
 293
 294                 if items isa Array[E] then
 295                         var k = 0
 296                         while l < nl do
 297                                 _items[l] = items._items[k]
 298                                 l += 1
 299                                 k += 1
 300                         end
 301                 else
 302                         for item in items do
 303                                 _items[l] = item
 304                                 l += 1
 305                         end
 306                 end
 307
 308                 _length = nl
 309         end
 310
 311         redef fun enlarge(cap)
 312         do
 313                 var c = _capacity
 314                 if cap <= c then return
 315                 while c <= cap do c = c * 2 + 2
 316                 var a = new NativeArray[E](c)
 317                 if _capacity > 0 then _items.copy_to(a, _length)
 318                 _items = a
 319                 _capacity = c
 320         end
 321
 322         # Create an empty array.
 323         init
 324         do
 325                 _capacity = 0
 326                 _length = 0
 327         end
 328
 329         # Create an array from a collection.
 330         init from(items: Collection[E]) do
 331                 with_capacity(items.length)
 332                 self.add_all(items)
 333         end
 334
 335         # Create an array with some `objects`.
 336         init with_items(objects: E...)
 337         do
 338                 _items = objects._items
 339                 _capacity = objects._capacity
 340                 _length = objects.length
 341         end
 342
 343         # Create an empty array with a given capacity.
 344         init with_capacity(cap: Int)
 345         do
 346                 assert positive: cap >= 0
 347                 _items = new NativeArray[E](cap)
 348                 _capacity = cap
 349                 _length = 0
 350         end
 351
 352         # Create an array of `count` elements
 353         init filled_with(value: E, count: Int)
 354         do
 355                 assert positive: count >= 0
 356                 _items = new NativeArray[E](count)
 357                 _capacity = count
 358                 _length = count
 359                 var i = 0
 360                 while i < count do
 361                         self[i] = value
 362                         i += 1
 363                 end
 364         end
 365
 366         # Create a array filled with a given native array.
 367         init with_native(nat: NativeArray[E], size: Int)
 368         do
 369                 assert positive: size >= 0
 370                 _items = nat
 371                 _capacity = size
 372                 _length = size
 373         end
 374
 375         # The internal storage.
 376         private var items: nullable NativeArray[E] = null
 377
 378         # The size of `_items`.
 379         private var capacity: Int = 0
 380
 381         redef fun ==(o)
 382         do
 383                 if not o isa Array[nullable Object] then return super
 384                 # Efficient implementation
 385                 var l = length
 386                 if l != o.length then return false
 387                 var i = 0
 388                 var it = _items
 389                 var oit = o._items
 390                 while i < l do
 391                         if it[i] != oit[i] then return false
 392                         i += 1
 393                 end
 394                 return true
 395         end
 396
 397         # Shallow clone of `self`
 398         #
 399         # ~~~
 400         # var a = [1,2,3]
 401         # var b = a.clone
 402         # assert a == b
 403         # a.add 4
 404         # assert a != b
 405         # b.add 4
 406         # assert a == b
 407         # ~~~
 408         #
 409         # Note that the clone is shallow and elements are shared between `self` and the result.
 410         #
 411         # ~~~
 412         # var aa = [a]
 413         # var bb = aa.clone
 414         # assert aa == bb
 415         # aa.first.add 5
 416         # assert aa == bb
 417         # ~~~
 418         redef fun clone do return to_a
 419
 420         # Concatenation of arrays.
 421         #
 422         # Returns a new array built by concatenating `self` and `other` together.
 423         #
 424         #     var a1 = [1,2,3]
 425         #     var a2 = [4,5,6]
 426         #     var a3 = a1 + a2
 427         #     assert a3 == [1,2,3,4,5,6]
 428         #
 429         # Because a new array is always created, future modification on `self` and `other`
 430         # does not impact the previously computed result.
 431         #
 432         #     a1.add(30)
 433         #     a2.add(60)
 434         #     assert a3      == [1,2,3,4,5,6] # unchanged
 435         #     assert a1 + a2 == [1,2,3,30,4,5,6,60]
 436         fun +(other: Array[E]): Array[E]
 437         do
 438                 var res = new Array[E].with_capacity(length + other.length)
 439                 res.append(self)
 440                 res.append(other)
 441                 return res
 442         end
 443
 444         # Repetition of arrays.
 445         #
 446         # returns a new array built by concatenating `self` `repeat` times.
 447         #
 448         #     var a = [1,2,3]
 449         #     assert (a * 0).is_empty
 450         #     assert a * 1  ==  [1,2,3]
 451         #     assert a * 2  ==  [1,2,3,1,2,3]
 452         #     assert (a * 10).length  ==  30
 453         fun *(repeat: Int): Array[E]
 454         do
 455                 assert repeat >= 0
 456                 var res = new Array[E].with_capacity(length * repeat)
 457                 while repeat > 0 do
 458                         res.add_all(self)
 459                         repeat -= 1
 460                 end
 461                 return res
 462         end
 463 end
 464
 465 # An `Iterator` on `AbstractArray`
 466 private class ArrayIterator[E]
 467         super IndexedIterator[E]
 468
 469         redef fun item do return _array[_index]
 470
 471         # redef fun item=(e) do _array[_index] = e
 472
 473         redef fun is_ok do return _index < _array.length
 474
 475         redef fun next do _index += 1
 476
 477         redef var index = 0
 478
 479         var array: AbstractArrayRead[E]
 480 end
 481
 482 private class ArrayReverseIterator[E]
 483         super ArrayIterator[E]
 484
 485         redef fun is_ok do return _index >= 0
 486
 487         redef fun next do _index -= 1
 488
 489         init
 490         do
 491                 _index = _array.length - 1
 492         end
 493 end
 494
 495 # Others collections ##########################################################
 496
 497 # A set implemented with an Array.
 498 class ArraySet[E]
 499         super Set[E]
 500         super Cloneable
 501
 502         # The stored elements.
 503         private var array: Array[E] is noinit
 504
 505         redef fun has(e) do return _array.has(e)
 506
 507         redef fun add(e) do if not _array.has(e) then _array.add(e)
 508
 509         redef fun is_empty do return _array.is_empty
 510
 511         redef fun length do return _array.length
 512
 513         redef fun first
 514         do
 515                 assert _array.length > 0
 516                 return _array.first
 517         end
 518
 519         redef fun remove(item)
 520         do
 521                 var i = _array.index_of(item)
 522                 if i >= 0 then remove_at(i)
 523         end
 524
 525         redef fun remove_all(item) do remove(item)
 526
 527         redef fun clear do _array.clear
 528
 529         redef fun iterator do return new ArraySetIterator[E](_array.iterator)
 530
 531         # Assume the capacity is at least `cap`.
 532         fun enlarge(cap: Int) do _array.enlarge(cap)
 533
 534         private fun remove_at(i: Int)
 535         do
 536                 _array[i] = _array.last
 537                 _array.pop
 538         end
 539
 540         # Create an empty set
 541         init do _array = new Array[E]
 542
 543         # Create an empty set with a given capacity.
 544         init with_capacity(i: Int) do _array = new Array[E].with_capacity(i)
 545
 546         redef fun new_set do return new ArraySet[E]
 547
 548         # Shallow clone of `self`
 549         #
 550         # ~~~
 551         # var a = new ArraySet[Int]
 552         # a.add 1
 553         # a.add 2
 554         # var b = a.clone
 555         # assert a == b
 556         # a.add 3
 557         # assert a != b
 558         # b.add 3
 559         # assert a == b
 560         # ~~~
 561         #
 562         # Note that the clone is shallow and keys and values are shared between `self` and the result.
 563         #
 564         # ~~~
 565         # var aa = new ArraySet[Array[Int]]
 566         # aa.add([1,2])
 567         # var bb = aa.clone
 568         # assert aa == bb
 569         # aa.first.add 5
 570         # assert aa == bb
 571         # ~~~
 572         redef fun clone
 573         do
 574                 var res = new ArraySet[E]
 575                 res.add_all self
 576                 return res
 577         end
 578 end
 579
 580 # Iterators on sets implemented with arrays.
 581 private class ArraySetIterator[E]
 582         super Iterator[E]
 583
 584         redef fun is_ok do return _iter.is_ok
 585
 586         redef fun next do _iter.next
 587
 588         redef fun item: E do return _iter.item
 589
 590         var iter: ArrayIterator[E]
 591 end
 592
 593
 594 # Associative arrays implemented with an array of (key, value) pairs.
 595 class ArrayMap[K, E]
 596         super CoupleMap[K, E]
 597         super Cloneable
 598
 599         # O(n)
 600         redef fun [](key)
 601         do
 602                 var i = index(key)
 603                 if i >= 0 then
 604                         return _items[i].second
 605                 else
 606                         return provide_default_value(key)
 607                 end
 608         end
 609
 610         # O(n)
 611         redef fun []=(key, item)
 612         do
 613                 var i = index(key)
 614                 if i >= 0 then
 615                         _items[i].second = item
 616                 else
 617                         _items.push(new Couple[K,E](key, item))
 618                 end
 619         end
 620
 621         redef var keys: RemovableCollection[K] = new ArrayMapKeys[K, E](self)
 622         redef var values: RemovableCollection[E] = new ArrayMapValues[K, E](self)
 623
 624         # O(1)
 625         redef fun length do return _items.length
 626
 627         redef fun couple_iterator do return _items.iterator
 628
 629         redef fun is_empty do return _items.is_empty
 630
 631         redef fun clear do _items.clear
 632
 633         # Assume the capacity to be at least `cap`.
 634         fun enlarge(cap: Int) do _items.enlarge(cap)
 635
 636         redef fun couple_at(key)
 637         do
 638                 var i = index(key)
 639                 if i >= 0 then
 640                         return _items[i]
 641                 else
 642                         return null
 643                 end
 644         end
 645
 646         # Internal storage.
 647         private var items = new Array[Couple[K,E]]
 648
 649         # fast remove the ith element of the array
 650         private fun remove_at_index(i: Int)
 651         do
 652                 _items[i] = _items.last
 653                 _items.pop
 654         end
 655
 656         # The last positive result given by a index(1) call
 657         private var last_index: Int = 0
 658
 659         # Where is the `key` in `_item`?
 660         # return -1 if not found
 661         private fun index(key: K): Int
 662         do
 663                 var l = _last_index
 664                 if l < _items.length and _items[l].first == key then return l
 665
 666                 var i = 0
 667                 while i < _items.length do
 668                         if _items[i].first == key then
 669                                 _last_index = i
 670                                 return i
 671                         end
 672                         i += 1
 673                 end
 674                 return -1
 675         end
 676
 677         # Shallow clone of `self`
 678         #
 679         # ~~~
 680         # var a = new ArrayMap[String,Int]
 681         # a["one"] = 1
 682         # a["two"] = 2
 683         # var b = a.clone
 684         # assert a == b
 685         # a["zero"] = 0
 686         # assert a != b
 687         # ~~~
 688         #
 689         # Note that the clone is shallow and keys and values are shared between `self` and the result.
 690         #
 691         # ~~~
 692         # var aa = new ArrayMap[String, Array[Int]]
 693         # aa["two"] = [1,2]
 694         # var bb = aa.clone
 695         # assert aa == bb
 696         # aa["two"].add 5
 697         # assert aa == bb
 698         # ~~~
 699         redef fun clone
 700         do
 701                 var res = new ArrayMap[K,E]
 702                 res.recover_with self
 703                 return res
 704         end
 705 end
 706
 707 private class ArrayMapKeys[K, E]
 708         super RemovableCollection[K]
 709         # The original map
 710         var map: ArrayMap[K, E]
 711         redef fun count(k) do if self.has(k) then return 1 else return 0
 712         redef fun first do return self.map._items.first.first
 713         redef fun has(k) do return self.map.index(k) >= 0
 714         redef fun has_only(k) do return (self.has(k) and self.length == 1) or self.is_empty
 715         redef fun is_empty do return self.map.is_empty
 716         redef fun length do return self.map.length
 717         redef fun iterator do return new MapKeysIterator[K, E](self.map.iterator)
 718         redef fun clear do self.map.clear
 719         redef fun remove(key)
 720         do
 721                 var i = self.map.index(key)
 722                 if i >= 0 then self.map.remove_at_index(i)
 723         end
 724         redef fun remove_all(key) do self.remove(key)
 725 end
 726
 727 private class ArrayMapValues[K, E]
 728         super RemovableCollection[E]
 729         # The original map
 730         var map: ArrayMap[K, E]
 731         redef fun first do return self.map._items.first.second
 732         redef fun is_empty do return self.map.is_empty
 733         redef fun length do return self.map.length
 734         redef fun iterator do return new MapValuesIterator[K, E](self.map.iterator)
 735
 736         # O(n)
 737         redef fun has(item)
 738         do
 739                 for i in self.map._items do if i.second == item then return true
 740                 return false
 741         end
 742
 743         # O(n)
 744         redef fun has_only(item)
 745         do
 746                 for i in self.map._items do if i.second != item then return false
 747                 return true
 748         end
 749
 750         # O(n)
 751         redef fun count(item)
 752         do
 753                 var nb = 0
 754                 for i in self.map._items do if i.second == item then nb += 1
 755                 return nb
 756         end
 757
 758         redef fun clear do self.map.clear
 759
 760         redef fun remove(item)
 761         do
 762                 var map = self.map
 763                 var i = map._items.length - 1
 764                 while i >= 0 do
 765                         if map._items[i].second == item then
 766                                 map.remove_at_index(i)
 767                                 return
 768                         end
 769                         i -= 1
 770                 end
 771         end
 772
 773         redef fun remove_all(item)
 774         do
 775                 var map = self.map
 776                 var i = map._items.length - 1
 777                 while i >= 0 do
 778                         if map._items[i].second == item then
 779                                 map.remove_at_index(i)
 780                         end
 781                         i -= 1
 782                 end
 783         end
 784 end
 785
 786 # Comparable array for comparable elements.
 787 #
 788 # For two arrays, if one is a prefix, then it is lower.
 789 #
 790 # ~~~
 791 # var a12 = new ArrayCmp[nullable Int].with_items(1,2)
 792 # var a123 = new ArrayCmp[nullable Int].with_items(1,2,3)
 793 # assert a12 < a123
 794 # ~~~
 795 #
 796 # Otherwise, the first element just after the longest
 797 # common prefix gives the order between the two arrays.
 798 #
 799 # ~~~
 800 # var a124 = new ArrayCmp[nullable Int].with_items(1,2,4)
 801 # var a13 = new ArrayCmp[nullable Int].with_items(1,3)
 802 # assert a12  < a123
 803 # assert a123 < a13
 804 # ~~~
 805 #
 806 # Obviously, two equal arrays are equal.
 807 #
 808 # ~~~
 809 # var b12 = new ArrayCmp[nullable Int].with_items(1,2)
 810 # assert (a12 <=> b12) == 0
 811 # ~~~
 812 #
 813 # `null` is considered lower than any other elements.
 814 # But is still greater than no element.
 815 #
 816 # ~~~
 817 # var a12n = new ArrayCmp[nullable Int].with_items(1,2,null)
 818 # assert a12n < a123
 819 # assert a12  < a12n
 820 # ~~~
 821 class ArrayCmp[E: nullable Comparable]
 822         super Array[E]
 823         super Comparable
 824         redef type OTHER: ArrayCmp[E] is fixed
 825
 826         redef fun <(o) do return (self <=> o) < 0
 827
 828         redef fun <=>(o)
 829         do
 830                 var it = _items
 831                 var oit = o._items
 832                 var i = 0
 833                 var l = length
 834                 var ol = o.length
 835                 var len
 836                 if l < ol then len = l else len = ol
 837                 while i < len do
 838                         var a = it[i]
 839                         var b = oit[i]
 840                         if a != null then
 841                                 if b == null then return 1
 842                                 var d = a <=> b.as(Comparable)
 843                                 if d != 0 then return d
 844                         else
 845                                 if b != null then return -1
 846                         end
 847                         i += 1
 848                 end
 849                 return l <=> ol
 850         end
 851 end
 852
 853 # Others tools ################################################################
 854
 855 redef class Iterator[E]
 856         # Interate on `self` and build an array
 857         fun to_a: Array[E]
 858         do
 859                 var res = new Array[E]
 860                 while is_ok do
 861                         res.add(item)
 862                         next
 863                 end
 864                 return res
 865         end
 866 end
 867
 868 redef class Collection[E]
 869         # Build a new array from a collection
 870         fun to_a: Array[E]
 871         do
 872                 var res = new Array[E].with_capacity(length)
 873                 res.add_all(self)
 874                 return res
 875         end
 876 end
 877
 878 # Native classes ##############################################################
 879
 880 # Native Nit array
 881 # Access are unchecked and it has a fixed size
 882 # Not for public use: may become private.
 883 universal NativeArray[E]
 884         # Creates a new NativeArray of capacity `length`
 885         new(length: Int) is intern
 886         # The length of the array
 887         fun length: Int is intern
 888         # Use `self` to initialize a standard Nit Array.
 889         fun to_a: Array[E] do return new Array[E].with_native(self, length)
 890
 891         # Get item at `index`.
 892         fun [](index: Int): E is intern
 893
 894         # Set `item` at `index`.
 895         fun []=(index: Int, item: E) is intern
 896
 897         # Copy `length` items to `dest`.
 898         fun copy_to(dest: NativeArray[E], length: Int) is intern
 899         #fun =(o: NativeArray[E]): Bool is intern
 900         #fun !=(o: NativeArray[E]): Bool is intern
 901 end