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