logo

class

sys::List

sys::Obj
  sys::List
   1  //
   2  // Copyright (c) 2006, Brian Frank and Andy Frank
   3  // Licensed under the Academic Free License version 3.0
   4  //
   5  // History:
   6  //   4 Jan 06  Brian Frank  Creation
   7  //
   8  
   9  **
  10  ** List represents an liner sequence of Objects indexed by an Int.
  11  **
  12  final class List
  13  {
  14  
  15  //////////////////////////////////////////////////////////////////////////
  16  // Constructor
  17  //////////////////////////////////////////////////////////////////////////
  18  
  19    **
  20    ** Constructor with of type and initial capacity.
  21    **
  22    new make(Type of, Int capacity)
  23  
  24    **
  25    ** Constructor for Obj[] with initial capacity.
  26    **
  27    new makeObj(Int capacity)
  28  
  29  //////////////////////////////////////////////////////////////////////////
  30  // Identity
  31  //////////////////////////////////////////////////////////////////////////
  32  
  33    **
  34    ** Two Lists are equal if they have the same number of items and all
  35    ** the items at each index return true for equals().
  36    **
  37    override Bool equals(Obj that)
  38  
  39    **
  40    ** Return platform dependent hashcode based a hash of the items
  41    ** of the list.
  42    **
  43    override Int hash()
  44  
  45    **
  46    ** Get the item Type of this List.
  47    **
  48    ** Examples:
  49    **   ["hi"].of    ->  Str.type
  50    **   [[2, 3]].of  ->  Int[].type
  51    **
  52    Type of()
  53  
  54  //////////////////////////////////////////////////////////////////////////
  55  // Access
  56  //////////////////////////////////////////////////////////////////////////
  57  
  58    **
  59    ** Return if size == 0.  This method is idempotent.
  60    **
  61    Bool isEmpty()
  62  
  63    **
  64    ** The number of items in the list.  If the size is set greater than
  65    ** the current size then the list is automatically grown to be a sparse
  66    ** list with new items defaulting to null.  If the size is set less than
  67    ** the current size then any items with indices past the new size are
  68    ** automatically removed.  Changing size automatically allocates new
  69    ** storage so that capacity exactly matches the new size.  Getting size
  70    ** is idempotent, setting size throws ReadonlyErr if readonly.
  71    **
  72    Int size
  73  
  74    **
  75    ** The number of items this list can hold without allocating more memory.
  76    ** Capacity is always greater or equal to size.  If adding a large
  77    ** number of items, it may be more efficient to manually set capacity.
  78    ** See the trim() method to automatically set capacity to size.  Throw
  79    ** ArgErr if attempting to set capacity less than size.  Getting capacity
  80    ** is idempotent, setting capacity throws ReadonlyErr if readonly.
  81    **
  82    Int capacity
  83  
  84    **
  85    ** Get is used to return the item at the specified the index.  A
  86    ** negative index may be used to access an index from the end of the
  87    ** list.  For example get(-1) is translated into get(size()-1).  The
  88    ** get method is accessed via the [] shortcut operator.  Throw
  89    ** IndexErr if index is out of range.  This method is idempotent.
  90    **
  91    V get(Int index)
  92  
  93    **
  94    ** Return a sub-list based on the specified range.  Negative indexes
  95    ** may be used to access from the end of the list.  This method
  96    ** is accessed via the [] operator.  This method is idempotent.
  97    ** Throw IndexErr if range illegal.
  98    **
  99    ** Examples:
 100    **   list := [0, 1, 2, 3]
 101    **   list[0..2]   -> [0, 1, 2]
 102    **   list[3..3]   -> [3]
 103    **   list[-2..-1] -> [2, 3]
 104    **   list[0...2]  -> [0, 1]
 105    **   list[1..-2]  -> [1, 2]
 106    **
 107    L slice(Range range)
 108  
 109    **
 110    ** Return if this list contains the specified item using
 111    ** the == operator (shortcut for equals method) to check
 112    ** for equality.  This method is idempotent.
 113    **
 114    Bool contains(V item)
 115  
 116    **
 117    ** Return if this list contains every item in the specified
 118    ** list using the == operator (shortcut for equals method).
 119    ** This method is idempotent.
 120    **
 121    Bool containsAll(L list)
 122  
 123    **
 124    ** Return the integer index of the specified item using
 125    ** the == operator (shortcut for equals method) to check
 126    ** for equality.  The search starts at the specified offset
 127    ** and returns the first match.  The offset may be negative
 128    ** to access from end of list.  Throw IndexErr if offset is
 129    ** out of range.  If the item is not found return null.
 130    ** This method is idempotent.
 131    **
 132    Int index(V item, Int offset := 0)
 133  
 134    **
 135    ** Return the item at index 0, or if empty return null.
 136    ** This method is idempotent.
 137    **
 138    V first()
 139  
 140    **
 141    ** Return the item at index-1, or if empty return null.
 142    ** This method is idempotent.
 143    **
 144    V last()
 145  
 146    **
 147    ** Create a shallow duplicate copy of this List.  The items
 148    ** themselves are not duplicated.  This method is idempotent.
 149    **
 150    L dup()
 151  
 152  //////////////////////////////////////////////////////////////////////////
 153  // Modification
 154  //////////////////////////////////////////////////////////////////////////
 155  
 156    **
 157    ** Set is used to overwrite the item at the specified the index.  A
 158    ** negative index may be used to access an index from the end of the
 159    ** list.  The set method is accessed via the []= shortcut operator.
 160    ** If you wish to use List as a sparse array and set values greater
 161    ** then size, then manually set size larger.  Return this.  Throw
 162    ** IndexErr if index is out of range.  Throw ReadonlyErr if readonly.
 163    **
 164    L set(Int index, V item)
 165  
 166    **
 167    ** Add the specified item to the end of the list.  The item will have
 168    ** an index of size.  Size is incremented by 1.  Return this.  Throw
 169    ** ReadonlyErr if readonly.
 170    **
 171    L add(V item)
 172  
 173    **
 174    ** Add all the items in the specified list to the end of this list.
 175    ** Size is incremented by list.size.  Return this.  Throw ReadonlyErr
 176    ** if readonly.
 177    **
 178    L addAll(L list)
 179  
 180    **
 181    ** Insert the item at the specified index.  A negative index may be
 182    ** used to access an index from the end of the list.  Size is incremented
 183    ** by 1.  Return this.  Throw IndexErr if index is out of range.  Throw
 184    ** ReadonlyErr if readonly.
 185    **
 186    L insert(Int index, V item)
 187  
 188    **
 189    ** Insert all the items in the specified list into this list at the
 190    ** specified index.  A negative index may be used to access an index
 191    ** from the end of the list.  Size is incremented by list.size.  Return
 192    ** this.  Throw IndexErr if index is out of range.  Throw ReadonlyErr
 193    ** if readonly.
 194    **
 195    L insertAll(Int index, L list)
 196  
 197    **
 198    ** Remove the specified value from the list.  The value is compared
 199    ** using the == operator (shortcut for equals method).  Return the
 200    ** removed value and decrement size by 1.  If the value is not found,
 201    ** then return null.  Throw ReadonlyErr if readonly.
 202    **
 203    V remove(V item)
 204  
 205    **
 206    ** Remove the object at the specified index.  A negative index may be
 207    ** used to access an index from the end of the list.  Size is decremented
 208    ** by 1.  Return the item removed.  Throw IndexErr if index is out of
 209    ** range.  Throw ReadonlyErr if readonly.
 210    **
 211    V removeAt(Int index)
 212  
 213    **
 214    ** Remove all items from the list and set size to 0.  Return this.
 215    ** Throw ReadonlyErr if readonly.
 216    **
 217    L clear()
 218  
 219    **
 220    ** Trim the capacity such that the underlying storage is optimized
 221    ** for the current size.  Return this.  Throw ReadonlyErr if readonly.
 222    **
 223    L trim()
 224  
 225  //////////////////////////////////////////////////////////////////////////
 226  // Stack
 227  //////////////////////////////////////////////////////////////////////////
 228  
 229    **
 230    ** Return the item at index-1, or if empty return null.
 231    ** This method has the same semantics as last().  This method
 232    ** is idempotent.
 233    **
 234    V peek()
 235  
 236    **
 237    ** Remove the last item and return it, or return null if the list
 238    ** is empty.  This method as the same semantics as remove(-1), with
 239    ** the exception of has an empty list is handled.  Throw ReadonlyErr
 240    ** if readonly.
 241    **
 242    V pop()
 243  
 244    **
 245    ** Add the specified item to the end of the list.  Return this.
 246    ** This method has the same semantics as add(item).  Throw ReadonlyErr
 247    ** if readonly.
 248    **
 249    L push(V item)
 250  
 251  //////////////////////////////////////////////////////////////////////////
 252  // Iterators
 253  //////////////////////////////////////////////////////////////////////////
 254  
 255    **
 256    ** Call the specified function for every item in the list starting
 257    ** with index 0 and incrementing up to size-1.  This method is
 258    ** idempotent.
 259    **
 260    ** Example:
 261    **   ["a", "b", "c"].each |Str s| { echo(s) }
 262    **
 263    Void each(|V item, Int index| c)
 264  
 265    **
 266    ** Reverse each - call the specified function for every item in
 267    ** the list starting with index size-1 and decrementing down
 268    ** to 0.  This method is idempotent.
 269    **
 270    ** Example:
 271    **   ["a", "b", "c"].eachr |Str s| { echo(s) }
 272    **
 273    Void eachr(|V item, Int index| c)
 274  
 275    **
 276    ** Return the first item in the list for which c returns true.
 277    ** If c returns false for every item, then return null.  This
 278    ** method is idempotent.
 279    **
 280    ** Example:
 281    **   list := [0, 1, 2, 3, 4]
 282    **   list.find |Int v->Bool| { return v.toStr == "3" } -> 3
 283    **   list.find |Int v->Bool| { return v.toStr == "7" } -> null
 284    **
 285    V find(|V item, Int index->Bool| c)
 286  
 287    **
 288    ** Return a new list containing the items for which c returns
 289    ** true.  If c returns false for every item, then return an
 290    ** empty list.  The inverse of this method is exclude().  This
 291    ** method is idempotent.
 292    **
 293    ** Example:
 294    **   list := [0, 1, 2, 3, 4]
 295    **   list.findAll |Int v->Bool| { return v%2==0 } -> [0, 2, 4]
 296    **
 297    L findAll(|V item, Int index->Bool| c)
 298  
 299    **
 300    ** Return a new list containing all the items which are an instance
 301    ** of the specified type such that item.type.fits(t) is true.  Any null
 302    ** items are automatically excluded.  If none of the items are instance
 303    ** of the specified type, then an empty list is returned.  The returned
 304    ** list will be a list of t.  This method is idempotent.
 305    **
 306    ** Example:
 307    **   list := ["a", 3, "foo", 5sec, null]
 308    **   list.findType(Str.type) -> Str["a", "foo"]
 309    **
 310    L findType(Type t)
 311  
 312    **
 313    ** Return a new list containing the items for which c returns
 314    ** false.  If c returns true for every item, then return an
 315    ** empty list.  The inverse of this method is findAll().  This
 316    ** method is idempotent.
 317    **
 318    ** Example:
 319    **   list := [0, 1, 2, 3, 4]
 320    **   list.exclude |Int v->Bool| { return v%2==0 } -> [1, 3]
 321    **
 322    L exclude(|V item, Int index->Bool| c)
 323  
 324    **
 325    ** Return true if c returns true for any of the items in
 326    ** the list.  If the list is empty, return false.  This method
 327    ** is idempotent.
 328    **
 329    ** Example:
 330    **   list := ["ant", "bear"]
 331    **   list.any |Str v->Bool| { return v.size >= 4 } -> true
 332    **   list.any |Str v->Bool| { return v.size >= 5 } -> false
 333    **
 334    Bool any(|V item, Int index->Bool| c)
 335  
 336    **
 337    ** Return true if c returns true for all of the items in
 338    ** the list.  If the list is empty, return true.  This method
 339    ** is idempotent.
 340    **
 341    ** Example:
 342    **   list := ["ant", "bear"]
 343    **   list.all |Str v->Bool| { return v.size >= 3 } -> true
 344    **   list.all |Str v->Bool| { return v.size >= 4 } -> false
 345    **
 346    Bool all(|V item, Int index->Bool| c)
 347  
 348    **
 349    ** Append to acc the result of calling c for every item in
 350    ** this list.  Return acc.  This method is idempotent.
 351    **
 352    ** Example:
 353    **   list := [3, 4, 5]
 354    **   list.map(Int[,]) |Int v->Obj| { return v*2 } -> [6, 8, 10]
 355    **
 356    List map(List acc, |V item, Int index->Obj| c)
 357  
 358    **
 359    ** Reduce is used to iterate through every item in the list
 360    ** to reduce the list into a single value called the reduction.
 361    ** The initial value of the reduction is passed in as the init
 362    ** parameter, then passed back to the closure along with each
 363    ** item.  This method is idempotent.
 364    **
 365    ** Example:
 366    **   list := [1, 2, 3]
 367    **   list.reduce(0) |Obj r, Int v->Obj| { return (Int)r + v } -> 6
 368    **
 369    Obj reduce(Obj init, |Obj reduction, V item, Int index->Obj| c)
 370  
 371    **
 372    ** Return the minimum value of the list.  If c is provided, then it
 373    ** implements the comparator returning -1, 0, or 1.  If c is null
 374    ** then the <=> operator is used (shortcut for compare method).  If
 375    ** the list is empty, return null.  This method is idempotent.
 376    **
 377    ** Example:
 378    **   list := ["albatross", "dog", "horse"]
 379    **   list.min -> "albatross"
 380    **   list.min |Str a, Str b->Int| { return a.size <=> b.size } -> "dog"
 381    **
 382    V min(|V a, V b->Int| c := null)
 383  
 384    **
 385    ** Return the maximum value of the list.  If c is provided, then it
 386    ** implements the comparator returning -1, 0, or 1.  If c is null
 387    ** then the <=> operator is used (shortcut for compare method).  If
 388    ** the list is empty, return null.  This method is idempotent.
 389    **
 390    ** Example:
 391    **   list := ["albatross", "dog", "horse"]
 392    **   list.max -> "horse"
 393    **   list.max |Str a, Str b->Int| { return a.size <=> b.size } -> "albatross"
 394    **
 395    V max(|V a, V b->Int| c := null)
 396  
 397    **
 398    ** Returns a new list with all duplicate items removed such that the
 399    ** resulting list is a proper set.  Duplicates are detected using hash()
 400    ** and the == operator (shortcut for equals method).  This method is
 401    ** idempotent.
 402    **
 403    ** Example:
 404    **   ["a", "a", "b", "c", "b", "b"].unique -> ["a", "b", "c"]
 405    **
 406    L unique()
 407  
 408    **
 409    ** Return a new list which is the union of this list and the given list.
 410    ** The union is defined as the unique items which are in *either* list.
 411    ** The resulting list is ordered first by this list's order, and secondarily
 412    ** by that's order.  The new list is guaranteed to be unique with no duplicate
 413    ** values.  Equality is determined using hash() and the == operator
 414    ** (shortcut for equals method).  This method is idempotent.
 415    **
 416    ** Example:
 417    **   [1, 2].union([3, 2]) -> [1, 2, 3]
 418    **
 419    L union(L that)
 420  
 421    **
 422    ** Return a new list which is the intersection of this list and the
 423    ** given list.  The intersection is defined as the unique items which
 424    ** are in *both* lists.  The new list will be ordered according to this
 425    ** list's order.  The new list is guaranteed to be unique with no duplicate
 426    ** values.  Equality is determined using hash() and the == operator
 427    ** (shortcut for equals method).  This method is idempotent.
 428    **
 429    ** Example:
 430    **   [0, 1, 2, 3].intersection([5, 3, 1]) -> [1, 3]
 431    **   [0, null, 2].intersection([null, 0, 1, 2, 3]) -> [0, null, 2]
 432    **
 433    L intersection(L that)
 434  
 435  //////////////////////////////////////////////////////////////////////////
 436  // Utils
 437  //////////////////////////////////////////////////////////////////////////
 438  
 439    **
 440    ** Perform an in-place sort on this list.  If a method is provided
 441    ** it implements the comparator returning -1, 0, or 1.  If the
 442    ** comparator method is null then sorting is based on the
 443    ** value's <=> operator (shortcut for compare method).  Return this.
 444    ** Throw ReadonlyErr if readonly.
 445    **
 446    ** Example:
 447    **   s := ["candy", "ate", "he"]
 448    **
 449    **   s.sort
 450    **   // s now evaluates to [ate, candy, he]
 451    **
 452    **   s.sort |Str a, Str b->Int| { return a.size <=> b.size }
 453    **   // s now evaluates to ["he", "ate", "candy"]
 454    **
 455    L sort(|V a, V b->Int| c := null)
 456  
 457    **
 458    ** Reverse sort - perform an in-place reverse sort on this list.  If
 459    ** a method is provided it implements the comparator returning -1,
 460    ** 0, or 1.  If the comparator method is null then sorting is based
 461    ** on the items <=> operator (shortcut for compare method).  Return
 462    ** this.  Throw ReadonlyErr if readonly.
 463    **
 464    ** Example:
 465    **   [3, 2, 4, 1].sortr ->  [4, 3, 2, 1]
 466    **
 467    L sortr(|V a, V b->Int| c := null)
 468  
 469    **
 470    ** Reverse the order of the items of this list in-place.  Return this.
 471    ** Throw ReadonlyErr if readonly.
 472    **
 473    ** Example:
 474    **   [1, 2, 3, 4].sort  ->  [4, 3, 2, 1]
 475    **
 476    L reverse()
 477  
 478    **
 479    ** Swap the items at the two specified indexes.  Negative indexes may
 480    ** used to access an index from the end of the list.  Return this.
 481    ** Throw ReadonlyErr if readonly.
 482    **
 483    L swap(Int indexA, Int indexB)
 484  
 485  //////////////////////////////////////////////////////////////////////////
 486  // Conversion
 487  //////////////////////////////////////////////////////////////////////////
 488  
 489    **
 490    ** Return a string representation the list.  This method is idempotent.
 491    **
 492    override Str toStr()
 493  
 494    **
 495    ** Return a string by concatenating each item's toStr result
 496    ** using the the specified separator string.  If c is non-null
 497    ** then it is used to format each item into a string, otherwise
 498    ** Obj.toStr is used.  This method is idempotent.
 499    **
 500    ** Example:
 501    **   ["a", "b", "c"].join -> "abc"
 502    **   ["a", "b", "c"].join("-") -> "a-b-c"
 503    **   ["a", "b", "c"].join("-") |Str s->Str| { return "($s)" } -> "(a)-(b)-(c)"
 504    **
 505    Str join(Str separator := "", |V item, Int index->Str| c := null)
 506  
 507    // TODO
 508    //   flatten, fill, binarySearch
 509  
 510  //////////////////////////////////////////////////////////////////////////
 511  // Readonly
 512  //////////////////////////////////////////////////////////////////////////
 513  
 514    **
 515    ** Return if this List is readonly.  A readonly List is guaranteed to
 516    ** be immutable (although its items may be mutable themselves).  Any
 517    ** attempt to  modify a readonly List will result in ReadonlyErr.  Use
 518    ** rw() to get a read-write List from a readonly List.  Methods
 519    ** documented as idempotent may be used safely with a readonly List.
 520    ** This method is idempotent.
 521    **
 522    Bool isRO()
 523  
 524    **
 525    ** Return if this List is read-write.  A read-write List is mutable
 526    ** and may be modified.  Use ro() to get a readonly List from a
 527    ** read-write List.  This method is idempotent.
 528    **
 529    Bool isRW()
 530  
 531    **
 532    ** Get a readonly, immutable List instance with the same contents
 533    ** as this List (although the items may be mutable themselves).  If
 534    ** this List is already readonly, then return this.  Only methods
 535    ** documented as idempotent may be used safely with a readonly List,
 536    ** all others will throw ReadonlyErr.  This method is idempotent.
 537    ** See isImmutable and toImmutable for deep immutability.
 538    **
 539    L ro()
 540  
 541    **
 542    ** Get a read-write, mutable List instance with the same contents
 543    ** as this List.  If this List is already read-write, then return this.
 544    ** This method is idempotent.
 545    **
 546    L rw()
 547  
 548    **
 549    ** Return an immutable List which returns true for Obj.isImmtable.
 550    ** If this List is already immutable, then return this.  This method
 551    ** is effectively a "deep ro()" which guarantees that if any items
 552    ** are Lists or Maps, then they are made immutable by recursively calling
 553    ** toImmutable.  All other items must return true for Obj.isImmutable,
 554    ** otherwise NotImmutableErr is thrown.  This method must be used
 555    ** whenever setting a const List field.  This method is idempotent.
 556    **
 557    L toImmutable()
 558  
 559  }