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