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