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