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 dimention array of objects.
  21 class AbstractArrayRead[E]
  22         super SequenceRead[E]
  23         # The current length
  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         fun last_index_of(item: E): Int do return last_index_of_from(item, length-1)
  65
  66         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         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         fun reversed: Array[E]
  93         do
  94                 var cmp = _length
  95                 var result = new Array[E].with_capacity(cmp)
  96                 while cmp > 0 do
  97                         cmp -= 1
  98                         result.add(self[cmp])
  99                 end
 100                 return result
 101         end
 102
 103         protected fun copy_to(start: Int, len: Int, dest: AbstractArray[E], new_start: Int)
 104         do
 105                 # TODO native one
 106                 var i = len
 107                 while i > 0 do
 108                         i -= 1
 109                         dest[new_start+i] = self[start+i]
 110                 end
 111         end
 112
 113         redef fun output
 114         do
 115                 var i = 0
 116                 var l = length
 117                 while i < l do
 118                         var e = self[i]
 119                         if e != null then e.output
 120                         i += 1
 121                 end
 122         end
 123
 124         redef fun iterator: ArrayIterator[E] do return new ArrayIterator[E](self)
 125
 126         # Two arrays are equals if they have the same items in the same order.
 127         redef fun ==(o)
 128         do
 129                 if not o isa AbstractArray[E] or o is null then return false
 130                 var l = length
 131                 if o.length != l then return false
 132                 var i = 0
 133                 while i < l do
 134                         if self[i] != o[i] then return false
 135                         i += 1
 136                 end
 137                 return true
 138         end
 139 end
 140
 141 # Resizeable one dimention array of objects.
 142 class AbstractArray[E]
 143         super AbstractArrayRead[E]
 144         super Sequence[E]
 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         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         fun swap_at( a : Int, b : Int )
 217         do
 218             var e = self[a]
 219             self[a] = b
 220             self[b] = e
 221         end
 222 end
 223
 224 # Resizeable one dimention array of objects.
 225 #
 226 # Arrays have a literal representation.
 227 #     a = [12, 32, 8]
 228 # is equivalent with:
 229 #     a = new Array[Int]
 230 #     a.push(12)
 231 #     a.push(32)
 232 #     a.push(8)
 233 class Array[E]
 234         super AbstractArray[E]
 235         super ArrayCapable[E]
 236         redef fun iterate
 237                 !each(e: E)
 238         do
 239                 var i = 0
 240                 var l = _length
 241                 var items = _items
 242                 while i < length do
 243                         each(items[i])
 244                         i += 1
 245                 end
 246         end
 247
 248         redef fun [](index)
 249         do
 250                 assert index: index >= 0 and index < _length
 251                 return _items[index]
 252         end
 253
 254         redef fun []=(index, item)
 255         do
 256                 assert index: index >= 0 and index < _length + 1
 257                 if _capacity <= index then
 258                         enlarge(index + 1)
 259                 end
 260                 if _length <= index then
 261                         _length = index + 1
 262                 end
 263                 _items[index] = item
 264         end
 265
 266         redef fun add(item)
 267         do
 268                 var l = _length
 269                 if _capacity <= l then
 270                         enlarge(l + 1)
 271                 end
 272                 _length = l + 1
 273                 _items[l] = item
 274         end
 275
 276         redef fun enlarge(cap)
 277         do
 278                 var c = _capacity
 279                 if cap <= c then return
 280                 while c <= cap do c = c * 2 + 2
 281                 var a = calloc_array(c)
 282                 if _capacity > 0 then _items.copy_to(a, _length)
 283                 _items = a
 284                 _capacity = c
 285         end
 286
 287         # Create an empty array.
 288         init
 289         do
 290                 _capacity = 0
 291                 _length = 0
 292         end
 293
 294         # Create an array with some `items'.
 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
 344         # Sort the array using the !cmp function.
 345         fun sort
 346                 !cmp(e1,e2: E): Int
 347         do
 348                 sub_sort(0, length-1) !cmp(x,y) = cmp(x, y)
 349         end
 350
 351         # Sort `array' between `from' and `to' indices
 352         private fun sub_sort(from: Int, to: Int)
 353                 !cmp(e1,e2: E): Int
 354         do
 355                 if from >= to then
 356                         return
 357                 else if from + 7 < to then
 358                         var pivot = self[from]
 359                         var i = from
 360                         var j = to
 361                         while j > i do
 362                                 while i <= to and cmp(self[i], pivot) <= 0 do i += 1
 363                                 while j > i and cmp(self[j], pivot) >= 0 do j -= 1
 364                                 if j > i then
 365                                         var t = self[i]
 366                                         self[i] = self[j]
 367                                         self[j] = t
 368                                 end
 369                         end
 370                         self[from] = self[i-1]
 371                         self[i-1] = pivot
 372                         sub_sort(from, i-2) !cmp(x,y) = cmp(x, y)
 373                         sub_sort(i, to) !cmp(x,y) = cmp(x, y)
 374                 else
 375                         var i = from
 376                         while i < to do
 377                                 var min = i
 378                                 var min_v = self[i]
 379                                 var j = i
 380                                 while j <= to do
 381                                         if cmp(min_v, self[j]) > 0 then
 382                                                 min = j
 383                                                 min_v = self[j]
 384                                         end
 385                                         j += 1
 386                                 end
 387                                 if min != i then
 388                                         self[min] = self[i]
 389                                         self[i] = min_v
 390                                 end
 391                                 i += 1
 392                         end
 393                 end
 394         end
 395 end
 396
 397 # An `Iterator' on `AbstractArray'
 398 class ArrayIterator[E]
 399         super IndexedIterator[E]
 400         redef fun item do return _array[_index]
 401
 402         # redef fun item=(e) do _array[_index] = e
 403
 404         redef fun is_ok do return _index < _array.length
 405
 406         redef fun next do _index += 1
 407
 408         init(a: AbstractArrayRead[E])
 409         do
 410                 _array = a
 411                 _index = 0
 412         end
 413
 414         redef readable var _index: Int = 0
 415         var _array: AbstractArrayRead[E]
 416 end
 417
 418 # Others collections ##########################################################
 419
 420 # A set implemented with an Array.
 421 class ArraySet[E: Object]
 422         super Set[E]
 423         # The stored elements.
 424         var _array: Array[E]
 425
 426         redef fun has(e) do return _array.has(e)
 427
 428         redef fun add(e) do if not _array.has(e) then _array.add(e)
 429
 430         redef fun is_empty do return _array.is_empty
 431
 432         redef fun length do return _array.length
 433
 434         redef fun first
 435         do
 436                 assert _array.length > 0
 437                 return _array.first
 438         end
 439
 440         redef fun remove(item)
 441         do
 442                 var i = _array.index_of(item)
 443                 if i >= 0 then remove_at(i)
 444         end
 445
 446         redef fun remove_all(item) do remove(item)
 447
 448         redef fun clear do _array.clear
 449
 450         redef fun iterator do return new ArraySetIterator[E](_array.iterator)
 451
 452         # Assume the capacitydd is at least `cap'.
 453         fun enlarge(cap: Int) do _array.enlarge(cap)
 454
 455         private fun remove_at(i: Int)
 456         do
 457                 _array[i] = _array.last
 458                 _array.pop
 459         end
 460
 461         # Create an empty set
 462         init do _array = new Array[E]
 463
 464         # Create an empty set with a given capacity.
 465         init with_capacity(i: Int) do _array = new Array[E].with_capacity(i)
 466 end
 467
 468 # Iterators on sets implemented with arrays.
 469 class ArraySetIterator[E: Object]
 470         super Iterator[E]
 471
 472         redef fun is_ok do return _iter.is_ok
 473
 474         redef fun next do _iter.next
 475
 476         redef fun item: E do return _iter.item
 477
 478         init(iter: ArrayIterator[E]) do _iter = iter
 479
 480         var _iter: ArrayIterator[E]
 481 end
 482
 483
 484 # Associative arrays implemented with an array of (key, value) pairs.
 485 class ArrayMap[K: Object, E]
 486         super CoupleMap[K, E]
 487
 488         # O(n)
 489         redef fun [](key)
 490         do
 491                 var i = index(key)
 492                 if i >= 0 then
 493                         return _items[i].second
 494                 else
 495                         abort
 496                 end
 497         end
 498
 499         # O(n)
 500         redef fun []=(key, item)
 501         do
 502                 var i = index(key)
 503                 if i >= 0 then
 504                         _items[i].second = item
 505                 else
 506                         _items.push(new Couple[K,E](key, item))
 507                 end
 508         end
 509
 510         redef var keys: ArrayMapKeys[K, E] = new ArrayMapKeys[K, E](self)
 511         redef var values: ArrayMapValues[K, E] = new ArrayMapValues[K, E](self)
 512
 513         # O(1)
 514         redef fun length do return _items.length
 515
 516         redef fun iterator: CoupleMapIterator[K, E] do return new CoupleMapIterator[K, E](_items.iterator)
 517
 518         redef fun is_empty do return _items.is_empty
 519
 520         redef fun clear do _items.clear
 521
 522         # Assume the capacity to be at least `cap'.
 523         fun enlarge(cap: Int) do _items.enlarge(cap)
 524
 525         redef fun couple_at(key)
 526         do
 527                 var i = index(key)
 528                 if i >= 0 then
 529                         return _items[i]
 530                 else
 531                         return null
 532                 end
 533         end
 534
 535         # Internal storage.
 536         var _items: Array[Couple[K,E]]
 537
 538         # fast remove the ith element of the array
 539         private fun remove_at_index(i: Int)
 540         do
 541                 _items[i] = _items.last
 542                 _items.pop
 543         end
 544
 545         # The last positive result given by a index(1) call
 546         var _last_index: Int = 0
 547
 548         # Where is the `key' in `_item'?
 549         # return -1 if not found
 550         private fun index(key: K): Int
 551         do
 552                 var l = _last_index
 553                 if l < _items.length and _items[l].first == key then return l
 554
 555                 var i = 0
 556                 while i < _items.length do
 557                         if _items[i].first == key then
 558                                 _last_index = i
 559                                 return i
 560                         end
 561                         i += 1
 562                 end
 563                 return -1
 564         end
 565
 566         # A new empty map.
 567         init
 568         do
 569                 _items = new Array[Couple[K,E]]
 570         end
 571 end
 572
 573 class ArrayMapKeys[K: Object, E]
 574         super RemovableCollection[K]
 575         # The original map
 576         var map: ArrayMap[K, E]
 577         redef fun count(k) do if self.has(k) then return 1 else return 0
 578         redef fun first do return self.map._items.first.first
 579         redef fun has(k) do return self.map.index(k) >= 0
 580         redef fun has_only(k) do return (self.has(k) and self.length == 1) or self.is_empty
 581         redef fun is_empty do return self.map.is_empty
 582         redef fun length do return self.map.length
 583         redef fun iterator do return new MapKeysIterator[K, E](self.map.iterator)
 584         redef fun clear do self.map.clear
 585         redef fun remove(key)
 586         do
 587                 var i = self.map.index(key)
 588                 if i >= 0 then self.map.remove_at_index(i)
 589         end
 590         redef fun remove_all(key) do self.remove(key)
 591 end
 592
 593 class ArrayMapValues[K: Object, E]
 594         super RemovableCollection[K]
 595         # The original map
 596         var map: ArrayMap[K, E]
 597         redef fun first do return self.map._items.first.first
 598         redef fun is_empty do return self.map.is_empty
 599         redef fun length do return self.map.length
 600         redef fun iterator do return new MapValuesIterator[K, E](self.map.iterator)
 601
 602         # O(n)
 603         redef fun has(item)
 604         do
 605                 for i in self.map._items do if i.second == item then return true
 606                 return false
 607         end
 608
 609         # O(n)
 610         redef fun has_only(item)
 611         do
 612                 for i in self.map._items do if i.second != item then return false
 613                 return true
 614         end
 615
 616         # O(n)
 617         redef fun count(item)
 618         do
 619                 var nb = 0
 620                 for i in self.map._items do if i.second == item then nb += 1
 621                 return nb
 622         end
 623
 624         redef fun clear do self.map.clear
 625
 626         redef fun remove(item)
 627         do
 628                 var map = self.map
 629                 var i = map._items.length - 1
 630                 while i >= 0 do
 631                         if map._items[i].second == item then
 632                                 map.remove_at_index(i)
 633                                 return
 634                         end
 635                         i -= 1
 636                 end
 637         end
 638
 639         redef fun remove_all(item)
 640         do
 641                 var map = self.map
 642                 var i = map._items.length - 1
 643                 while i >= 0 do
 644                         if map._items[i].second == item then
 645                                 map.remove_at_index(i)
 646                         end
 647                         i -= 1
 648                 end
 649         end
 650 end
 651
 652
 653 # Others tools ################################################################
 654
 655 redef class Iterator[E]
 656         # Interate on `self' and build an array
 657         fun to_a: Array[E]
 658         do
 659                 var res = new Array[E]
 660                 while is_ok do
 661                         res.add(item)
 662                         next
 663                 end
 664                 return res
 665         end
 666 end
 667
 668 redef class Collection[E]
 669         # Build a new array from a collection
 670         fun to_a: Array[E]
 671         do
 672                 return iterator.to_a
 673         end
 674 end
 675
 676 # Native classes ##############################################################
 677
 678 # Subclasses of this class can create native arrays
 679 interface ArrayCapable[E]
 680         # Get a new array of `size' elements.
 681         protected fun calloc_array(size: Int): NativeArray[E] is intern
 682 end
 683
 684 # Native C array (void ...).
 685 universal NativeArray[E]
 686         fun [](index: Int): E is intern
 687         fun []=(index: Int, item: E) is intern
 688         fun copy_to(dest: NativeArray[E], length: Int) is intern
 689         #fun =(o: NativeArray[E]): Bool is intern
 690         #fun !=(o: NativeArray[E]): Bool is intern
 691 end