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