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
 141         # Two arrays are equals if they have the same items in the same order.
 142         redef fun ==(o)
 143         do
 144                 if not o isa AbstractArray[nullable Object] or o is null then return false
 145                 var l = length
 146                 if o.length != l then return false
 147                 var i = 0
 148                 while i < l do
 149                         if self[i] != o[i] then return false
 150                         i += 1
 151                 end
 152                 return true
 153         end
 154 end
 155
 156 # Resizable one dimension array of objects.
 157 abstract class AbstractArray[E]
 158         super AbstractArrayRead[E]
 159         super Sequence[E]
 160
 161         # Force the capacity to be at least `cap`.
 162         # The capacity of the array is an internal information.
 163         # However, this method can be used to prepare a large amount of add
 164         fun enlarge(cap: Int) is abstract
 165
 166         redef fun push(item) do add(item)
 167
 168         redef fun pop
 169         do
 170                 assert not_empty: not is_empty
 171                 var r = last
 172                 _length -= 1
 173                 return r
 174         end
 175
 176         redef fun shift
 177         do
 178                 assert not_empty: not is_empty
 179                 var r = first
 180                 var i = 1
 181                 var l = length
 182                 while i < l do
 183                         self[i-1] = self[i]
 184                         i += 1
 185                 end
 186                 _length = l - 1
 187                 return r
 188         end
 189
 190         redef fun unshift(item)
 191         do
 192                 var i = length - 1
 193                 while i > 0 do
 194                         self[i+1] = self[i]
 195                         i -= 1
 196                 end
 197                 self[0] = item
 198         end
 199
 200         # Insert an element at a given position, following elements are shifted.
 201         #
 202         #     var a= [10, 20, 30, 40]
 203         #     a.insert(100, 2)
 204         #     assert a      ==  [10, 20, 100, 30, 40]
 205         fun insert(item: E, pos: Int)
 206         do
 207                 enlarge(length + 1)
 208                 copy_to(pos, length-pos, self, pos + 1)
 209                 self[pos] = item
 210         end
 211
 212         redef fun add(item) do self[length] = item
 213
 214         redef fun clear do _length = 0
 215
 216         redef fun remove(item) do remove_at(index_of(item))
 217
 218         redef fun remove_all(item)
 219         do
 220                 var i = index_of(item)
 221                 while i >= 0 do
 222                         remove_at(i)
 223                         i = index_of_from(item, i)
 224                 end
 225         end
 226
 227         redef fun remove_at(i)
 228         do
 229                 var l = length
 230                 if i >= 0 and i < l then
 231                         var j = i + 1
 232                         while j < l do
 233                                 self[j-1] = self[j]
 234                                 j += 1
 235                         end
 236                         _length = l - 1
 237                 end
 238         end
 239
 240         # Invert two elements in the array
 241         #
 242         #     var a = [10, 20, 30, 40]
 243         #     a.swap_at(1, 3)
 244         #     assert a      ==  [10, 40, 30, 20]
 245         fun swap_at(a: Int,b: Int)
 246         do
 247             var e = self[a]
 248             self[a] = self[b]
 249             self[b] = e
 250         end
 251 end
 252
 253 # Resizable one dimension array of objects.
 254 #
 255 # Arrays have a literal representation.
 256 #     var a = [12, 32, 8]
 257 #     # is equivalent with:
 258 #     var b = new Array[Int]
 259 #     b.push(12)
 260 #     b.push(32)
 261 #     b.push(8)
 262 #     assert a == b
 263 class Array[E]
 264         super AbstractArray[E]
 265         super ArrayCapable[E]
 266
 267         redef fun iterate
 268                 !each(e: E)
 269         do
 270                 var i = 0
 271                 var l = _length
 272                 var items = _items
 273                 while i < length do
 274                         each(items[i])
 275                         i += 1
 276                 end
 277         end
 278
 279         redef fun [](index)
 280         do
 281                 assert index: index >= 0 and index < _length
 282                 return _items[index]
 283         end
 284
 285         redef fun []=(index, item)
 286         do
 287                 assert index: index >= 0 and index < _length + 1
 288                 if _capacity <= index then
 289                         enlarge(index + 1)
 290                 end
 291                 if _length <= index then
 292                         _length = index + 1
 293                 end
 294                 _items[index] = item
 295         end
 296
 297         redef fun add(item)
 298         do
 299                 var l = _length
 300                 if _capacity <= l then
 301                         enlarge(l + 1)
 302                 end
 303                 _length = l + 1
 304                 _items[l] = item
 305         end
 306
 307         redef fun enlarge(cap)
 308         do
 309                 var c = _capacity
 310                 if cap <= c then return
 311                 while c <= cap do c = c * 2 + 2
 312                 var a = calloc_array(c)
 313                 if _capacity > 0 then _items.copy_to(a, _length)
 314                 _items = a
 315                 _capacity = c
 316         end
 317
 318         # Create an empty array.
 319         init
 320         do
 321                 _capacity = 0
 322                 _length = 0
 323         end
 324
 325         # Create an array from a collection.
 326         init from(items: Collection[E]) do
 327                 with_capacity(items.length)
 328                 self.add_all(items)
 329         end
 330
 331         # Create an array with some `objects`.
 332         init with_items(objects: E...)
 333         do
 334                 _items = objects._items
 335                 _capacity = objects._capacity
 336                 _length = objects.length
 337         end
 338
 339         # Create an empty array with a given capacity.
 340         init with_capacity(cap: Int)
 341         do
 342                 assert positive: cap >= 0
 343                 _items = calloc_array(cap)
 344                 _capacity = cap
 345                 _length = 0
 346         end
 347
 348         # Create an array of `count` elements
 349         init filled_with(value: E, count: Int)
 350         do
 351                 assert positive: count >= 0
 352                 _items = calloc_array(count)
 353                 _capacity = count
 354                 _length = count
 355                 var i = 0
 356                 while i < count do
 357                         self[i] = value
 358                         i += 1
 359                 end
 360         end
 361
 362         # Create a array filled with a given native array.
 363         init with_native(nat: NativeArray[E], size: Int)
 364         do
 365                 assert positive: size >= 0
 366                 _items = nat
 367                 _capacity = size
 368                 _length = size
 369         end
 370
 371         # The internal storage.
 372         var _items: nullable NativeArray[E] = null
 373
 374         # Do not use this method
 375         # FIXME: Remove it once modules can intrude non local modules
 376         fun intern_items: NativeArray[E] do return _items.as(not null)
 377
 378         # The size of `_items`.
 379         var _capacity: Int = 0
 380
 381         # Sort the array using the !cmp function.
 382         fun sort
 383                 !cmp(e1,e2: E): Int
 384         do
 385                 sub_sort(0, length-1) !cmp(x,y) = cmp(x, y)
 386         end
 387
 388         # Sort `array` between `from` and `to` indices
 389         private fun sub_sort(from: Int, to: Int)
 390                 !cmp(e1,e2: E): Int
 391         do
 392                 if from >= to then
 393                         return
 394                 else if from + 7 < to then
 395                         var pivot = self[from]
 396                         var i = from
 397                         var j = to
 398                         while j > i do
 399                                 while i <= to and cmp(self[i], pivot) <= 0 do i += 1
 400                                 while j > i and cmp(self[j], pivot) >= 0 do j -= 1
 401                                 if j > i then
 402                                         var t = self[i]
 403                                         self[i] = self[j]
 404                                         self[j] = t
 405                                 end
 406                         end
 407                         self[from] = self[i-1]
 408                         self[i-1] = pivot
 409                         sub_sort(from, i-2) !cmp(x,y) = cmp(x, y)
 410                         sub_sort(i, to) !cmp(x,y) = cmp(x, y)
 411                 else
 412                         var i = from
 413                         while i < to do
 414                                 var min = i
 415                                 var min_v = self[i]
 416                                 var j = i
 417                                 while j <= to do
 418                                         if cmp(min_v, self[j]) > 0 then
 419                                                 min = j
 420                                                 min_v = self[j]
 421                                         end
 422                                         j += 1
 423                                 end
 424                                 if min != i then
 425                                         self[min] = self[i]
 426                                         self[i] = min_v
 427                                 end
 428                                 i += 1
 429                         end
 430                 end
 431         end
 432 end
 433
 434 # An `Iterator` on `AbstractArray`
 435 class ArrayIterator[E]
 436         super IndexedIterator[E]
 437
 438         redef fun item do return _array[_index]
 439
 440         # redef fun item=(e) do _array[_index] = e
 441
 442         redef fun is_ok do return _index < _array.length
 443
 444         redef fun next do _index += 1
 445
 446         init(a: AbstractArrayRead[E])
 447         do
 448                 _array = a
 449                 _index = 0
 450         end
 451
 452         redef readable var _index: Int = 0
 453         var _array: AbstractArrayRead[E]
 454 end
 455
 456 # Others collections ##########################################################
 457
 458 # A set implemented with an Array.
 459 class ArraySet[E: Object]
 460         super Set[E]
 461
 462         # The stored elements.
 463         var _array: Array[E]
 464
 465         redef fun has(e) do return _array.has(e)
 466
 467         redef fun add(e) do if not _array.has(e) then _array.add(e)
 468
 469         redef fun is_empty do return _array.is_empty
 470
 471         redef fun length do return _array.length
 472
 473         redef fun first
 474         do
 475                 assert _array.length > 0
 476                 return _array.first
 477         end
 478
 479         redef fun remove(item)
 480         do
 481                 var i = _array.index_of(item)
 482                 if i >= 0 then remove_at(i)
 483         end
 484
 485         redef fun remove_all(item) do remove(item)
 486
 487         redef fun clear do _array.clear
 488
 489         redef fun iterator do return new ArraySetIterator[E](_array.iterator)
 490
 491         # Assume the capacity is at least `cap`.
 492         fun enlarge(cap: Int) do _array.enlarge(cap)
 493
 494         private fun remove_at(i: Int)
 495         do
 496                 _array[i] = _array.last
 497                 _array.pop
 498         end
 499
 500         # Create an empty set
 501         init do _array = new Array[E]
 502
 503         # Create an empty set with a given capacity.
 504         init with_capacity(i: Int) do _array = new Array[E].with_capacity(i)
 505 end
 506
 507 # Iterators on sets implemented with arrays.
 508 class ArraySetIterator[E: Object]
 509         super Iterator[E]
 510
 511         redef fun is_ok do return _iter.is_ok
 512
 513         redef fun next do _iter.next
 514
 515         redef fun item: E do return _iter.item
 516
 517         init(iter: ArrayIterator[E]) do _iter = iter
 518
 519         var _iter: ArrayIterator[E]
 520 end
 521
 522
 523 # Associative arrays implemented with an array of (key, value) pairs.
 524 class ArrayMap[K: Object, E]
 525         super CoupleMap[K, E]
 526
 527         # O(n)
 528         redef fun [](key)
 529         do
 530                 var i = index(key)
 531                 if i >= 0 then
 532                         return _items[i].second
 533                 else
 534                         abort
 535                 end
 536         end
 537
 538         # O(n)
 539         redef fun []=(key, item)
 540         do
 541                 var i = index(key)
 542                 if i >= 0 then
 543                         _items[i].second = item
 544                 else
 545                         _items.push(new Couple[K,E](key, item))
 546                 end
 547         end
 548
 549         redef var keys: ArrayMapKeys[K, E] = new ArrayMapKeys[K, E](self)
 550         redef var values: ArrayMapValues[K, E] = new ArrayMapValues[K, E](self)
 551
 552         # O(1)
 553         redef fun length do return _items.length
 554
 555         redef fun iterator: CoupleMapIterator[K, E] do return new CoupleMapIterator[K, E](_items.iterator)
 556
 557         redef fun is_empty do return _items.is_empty
 558
 559         redef fun clear do _items.clear
 560
 561         # Assume the capacity to be at least `cap`.
 562         fun enlarge(cap: Int) do _items.enlarge(cap)
 563
 564         redef fun couple_at(key)
 565         do
 566                 var i = index(key)
 567                 if i >= 0 then
 568                         return _items[i]
 569                 else
 570                         return null
 571                 end
 572         end
 573
 574         # Internal storage.
 575         var _items: Array[Couple[K,E]]
 576
 577         # fast remove the ith element of the array
 578         private fun remove_at_index(i: Int)
 579         do
 580                 _items[i] = _items.last
 581                 _items.pop
 582         end
 583
 584         # The last positive result given by a index(1) call
 585         var _last_index: Int = 0
 586
 587         # Where is the `key` in `_item`?
 588         # return -1 if not found
 589         private fun index(key: K): Int
 590         do
 591                 var l = _last_index
 592                 if l < _items.length and _items[l].first == key then return l
 593
 594                 var i = 0
 595                 while i < _items.length do
 596                         if _items[i].first == key then
 597                                 _last_index = i
 598                                 return i
 599                         end
 600                         i += 1
 601                 end
 602                 return -1
 603         end
 604
 605         # A new empty map.
 606         init
 607         do
 608                 _items = new Array[Couple[K,E]]
 609         end
 610 end
 611
 612 class ArrayMapKeys[K: Object, E]
 613         super RemovableCollection[K]
 614         # The original map
 615         var map: ArrayMap[K, E]
 616         redef fun count(k) do if self.has(k) then return 1 else return 0
 617         redef fun first do return self.map._items.first.first
 618         redef fun has(k) do return self.map.index(k) >= 0
 619         redef fun has_only(k) do return (self.has(k) and self.length == 1) or self.is_empty
 620         redef fun is_empty do return self.map.is_empty
 621         redef fun length do return self.map.length
 622         redef fun iterator do return new MapKeysIterator[K, E](self.map.iterator)
 623         redef fun clear do self.map.clear
 624         redef fun remove(key)
 625         do
 626                 var i = self.map.index(key)
 627                 if i >= 0 then self.map.remove_at_index(i)
 628         end
 629         redef fun remove_all(key) do self.remove(key)
 630 end
 631
 632 class ArrayMapValues[K: Object, E]
 633         super RemovableCollection[E]
 634         # The original map
 635         var map: ArrayMap[K, E]
 636         redef fun first do return self.map._items.first.second
 637         redef fun is_empty do return self.map.is_empty
 638         redef fun length do return self.map.length
 639         redef fun iterator do return new MapValuesIterator[K, E](self.map.iterator)
 640
 641         # O(n)
 642         redef fun has(item)
 643         do
 644                 for i in self.map._items do if i.second == item then return true
 645                 return false
 646         end
 647
 648         # O(n)
 649         redef fun has_only(item)
 650         do
 651                 for i in self.map._items do if i.second != item then return false
 652                 return true
 653         end
 654
 655         # O(n)
 656         redef fun count(item)
 657         do
 658                 var nb = 0
 659                 for i in self.map._items do if i.second == item then nb += 1
 660                 return nb
 661         end
 662
 663         redef fun clear do self.map.clear
 664
 665         redef fun remove(item)
 666         do
 667                 var map = self.map
 668                 var i = map._items.length - 1
 669                 while i >= 0 do
 670                         if map._items[i].second == item then
 671                                 map.remove_at_index(i)
 672                                 return
 673                         end
 674                         i -= 1
 675                 end
 676         end
 677
 678         redef fun remove_all(item)
 679         do
 680                 var map = self.map
 681                 var i = map._items.length - 1
 682                 while i >= 0 do
 683                         if map._items[i].second == item then
 684                                 map.remove_at_index(i)
 685                         end
 686                         i -= 1
 687                 end
 688         end
 689 end
 690
 691
 692 # Others tools ################################################################
 693
 694 redef class Iterator[E]
 695         # Interate on `self` and build an array
 696         fun to_a: Array[E]
 697         do
 698                 var res = new Array[E]
 699                 while is_ok do
 700                         res.add(item)
 701                         next
 702                 end
 703                 return res
 704         end
 705 end
 706
 707 redef class Collection[E]
 708         # Build a new array from a collection
 709         fun to_a: Array[E]
 710         do
 711                 return iterator.to_a
 712         end
 713 end
 714
 715 # Native classes ##############################################################
 716
 717 # Subclasses of this class can create native arrays
 718 interface ArrayCapable[E]
 719         # Get a new array of `size` elements.
 720         protected fun calloc_array(size: Int): NativeArray[E] is intern
 721 end
 722
 723 # Native C array (void ...).
 724 universal NativeArray[E]
 725         fun [](index: Int): E is intern
 726         fun []=(index: Int, item: E) is intern
 727         fun copy_to(dest: NativeArray[E], length: Int) is intern
 728         #fun =(o: NativeArray[E]): Bool is intern
 729         #fun !=(o: NativeArray[E]): Bool is intern
 730 end