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