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