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