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