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