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