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