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