//
// Copyright (c) 2006, Brian Frank and Andy Frank
// Licensed under the Academic Free License version 3.0
//
// History:
// 4 Jan 06 Brian Frank Creation
//
**
** List represents an liner sequence of Objects indexed by an Int.
**
** See `docCookbook::Lists` for coding examples.
**
final class List
{
//////////////////////////////////////////////////////////////////////////
// Constructor
//////////////////////////////////////////////////////////////////////////
**
** Constructor with of type and initial capacity.
**
new make(Type of, Int capacity)
**
** Constructor for Obj[] with initial capacity.
**
new makeObj(Int capacity)
//////////////////////////////////////////////////////////////////////////
// Identity
//////////////////////////////////////////////////////////////////////////
**
** Two Lists are equal if they have the same number of items and all
** the items at each index return true for equals().
**
override Bool equals(Obj that)
**
** Return platform dependent hashcode based a hash of the items
** of the list.
**
override Int hash()
**
** Get the item Type of this List.
**
** Examples:
** ["hi"].of => Str.type
** [[2, 3]].of => Int[].type
**
Type of()
//////////////////////////////////////////////////////////////////////////
// Access
//////////////////////////////////////////////////////////////////////////
**
** Return if size == 0. This method is idempotent.
**
Bool isEmpty()
**
** The number of items in the list. If the size is set greater than
** the current size then the list is automatically grown to be a sparse
** list with new items defaulting to null. If the size is set less than
** the current size then any items with indices past the new size are
** automatically removed. Changing size automatically allocates new
** storage so that capacity exactly matches the new size. Getting size
** is idempotent, setting size throws ReadonlyErr if readonly.
**
Int size
**
** The number of items this list can hold without allocating more memory.
** Capacity is always greater or equal to size. If adding a large
** number of items, it may be more efficient to manually set capacity.
** See the trim() method to automatically set capacity to size. Throw
** ArgErr if attempting to set capacity less than size. Getting capacity
** is idempotent, setting capacity throws ReadonlyErr if readonly.
**
Int capacity
**
** Get is used to return the item at the specified the index. A
** negative index may be used to access an index from the end of the
** list. For example get(-1) is translated into get(size()-1). The
** get method is accessed via the [] shortcut operator. Throw
** IndexErr if index is out of range. This method is idempotent.
**
V get(Int index)
**
** Return a sub-list based on the specified range. Negative indexes
** may be used to access from the end of the list. This method
** is accessed via the [] operator. This method is idempotent.
** Throw IndexErr if range illegal.
**
** Examples:
** list := [0, 1, 2, 3]
** list[0..2] => [0, 1, 2]
** list[3..3] => [3]
** list[-2..-1] => [2, 3]
** list[0...2] => [0, 1]
** list[1..-2] => [1, 2]
**
L slice(Range range)
**
** Return if this list contains the specified item using
** the == operator (shortcut for equals method) to check
** for equality. This method is idempotent.
**
Bool contains(V item)
**
** Return if this list contains every item in the specified
** list using the == operator (shortcut for equals method).
** This method is idempotent.
**
Bool containsAll(L list)
**
** Return the integer index of the specified item using
** the == operator (shortcut for equals method) to check
** for equality. The search starts at the specified offset
** and returns the first match. The offset may be negative
** to access from end of list. Throw IndexErr if offset is
** out of range. If the item is not found return null.
** This method is idempotent.
**
Int index(V item, Int offset := 0)
**
** Return the item at index 0, or if empty return null.
** This method is idempotent.
**
V first()
**
** Return the item at index-1, or if empty return null.
** This method is idempotent.
**
V last()
**
** Create a shallow duplicate copy of this List. The items
** themselves are not duplicated. This method is idempotent.
**
L dup()
//////////////////////////////////////////////////////////////////////////
// Modification
//////////////////////////////////////////////////////////////////////////
**
** Set is used to overwrite the item at the specified the index. A
** negative index may be used to access an index from the end of the
** list. The set method is accessed via the []= shortcut operator.
** If you wish to use List as a sparse array and set values greater
** then size, then manually set size larger. Return this. Throw
** IndexErr if index is out of range. Throw ReadonlyErr if readonly.
**
L set(Int index, V item)
**
** Add the specified item to the end of the list. The item will have
** an index of size. Size is incremented by 1. Return this. Throw
** ReadonlyErr if readonly.
**
L add(V item)
**
** Add all the items in the specified list to the end of this list.
** Size is incremented by list.size. Return this. Throw ReadonlyErr
** if readonly.
**
L addAll(L list)
**
** Insert the item at the specified index. A negative index may be
** used to access an index from the end of the list. Size is incremented
** by 1. Return this. Throw IndexErr if index is out of range. Throw
** ReadonlyErr if readonly.
**
L insert(Int index, V item)
**
** Insert all the items in the specified list into this list at the
** specified index. A negative index may be used to access an index
** from the end of the list. Size is incremented by list.size. Return
** this. Throw IndexErr if index is out of range. Throw ReadonlyErr
** if readonly.
**
L insertAll(Int index, L list)
**
** Remove the specified value from the list. The value is compared
** using the == operator (shortcut for equals method). Return the
** removed value and decrement size by 1. If the value is not found,
** then return null. Throw ReadonlyErr if readonly.
**
V remove(V item)
**
** Remove the object at the specified index. A negative index may be
** used to access an index from the end of the list. Size is decremented
** by 1. Return the item removed. Throw IndexErr if index is out of
** range. Throw ReadonlyErr if readonly.
**
V removeAt(Int index)
**
** Remove all items from the list and set size to 0. Return this.
** Throw ReadonlyErr if readonly.
**
L clear()
**
** Trim the capacity such that the underlying storage is optimized
** for the current size. Return this. Throw ReadonlyErr if readonly.
**
L trim()
//////////////////////////////////////////////////////////////////////////
// Stack
//////////////////////////////////////////////////////////////////////////
**
** Return the item at index-1, or if empty return null.
** This method has the same semantics as last(). This method
** is idempotent.
**
V peek()
**
** Remove the last item and return it, or return null if the list
** is empty. This method as the same semantics as remove(-1), with
** the exception of has an empty list is handled. Throw ReadonlyErr
** if readonly.
**
V pop()
**
** Add the specified item to the end of the list. Return this.
** This method has the same semantics as add(item). Throw ReadonlyErr
** if readonly.
**
L push(V item)
//////////////////////////////////////////////////////////////////////////
// Iterators
//////////////////////////////////////////////////////////////////////////
**
** Call the specified function for every item in the list starting
** with index 0 and incrementing up to size-1. This method is
** idempotent.
**
** Example:
** ["a", "b", "c"].each |Str s| { echo(s) }
**
Void each(|V item, Int index| c)
**
** Reverse each - call the specified function for every item in
** the list starting with index size-1 and decrementing down
** to 0. This method is idempotent.
**
** Example:
** ["a", "b", "c"].eachr |Str s| { echo(s) }
**
Void eachr(|V item, Int index| c)
**
** Return the first item in the list for which c returns true.
** If c returns false for every item, then return null. This
** method is idempotent.
**
** Example:
** list := [0, 1, 2, 3, 4]
** list.find |Int v->Bool| { return v.toStr == "3" } => 3
** list.find |Int v->Bool| { return v.toStr == "7" } => null
**
V find(|V item, Int index->Bool| c)
**
** Return a new list containing the items for which c returns
** true. If c returns false for every item, then return an
** empty list. The inverse of this method is exclude(). This
** method is idempotent.
**
** Example:
** list := [0, 1, 2, 3, 4]
** list.findAll |Int v->Bool| { return v%2==0 } => [0, 2, 4]
**
L findAll(|V item, Int index->Bool| c)
**
** Return a new list containing all the items which are an instance
** of the specified type such that item.type.fits(t) is true. Any null
** items are automatically excluded. If none of the items are instance
** of the specified type, then an empty list is returned. The returned
** list will be a list of t. This method is idempotent.
**
** Example:
** list := ["a", 3, "foo", 5sec, null]
** list.findType(Str.type) => Str["a", "foo"]
**
L findType(Type t)
**
** Return a new list containing the items for which c returns
** false. If c returns true for every item, then return an
** empty list. The inverse of this method is findAll(). This
** method is idempotent.
**
** Example:
** list := [0, 1, 2, 3, 4]
** list.exclude |Int v->Bool| { return v%2==0 } => [1, 3]
**
L exclude(|V item, Int index->Bool| c)
**
** Return true if c returns true for any of the items in
** the list. If the list is empty, return false. This method
** is idempotent.
**
** Example:
** list := ["ant", "bear"]
** list.any |Str v->Bool| { return v.size >= 4 } => true
** list.any |Str v->Bool| { return v.size >= 5 } => false
**
Bool any(|V item, Int index->Bool| c)
**
** Return true if c returns true for all of the items in
** the list. If the list is empty, return true. This method
** is idempotent.
**
** Example:
** list := ["ant", "bear"]
** list.all |Str v->Bool| { return v.size >= 3 } => true
** list.all |Str v->Bool| { return v.size >= 4 } => false
**
Bool all(|V item, Int index->Bool| c)
**
** Append to acc the result of calling c for every item in
** this list. Return acc. This method is idempotent.
**
** Example:
** list := [3, 4, 5]
** list.map(Int[,]) |Int v->Obj| { return v*2 } => [6, 8, 10]
**
List map(List acc, |V item, Int index->Obj| c)
**
** Reduce is used to iterate through every item in the list
** to reduce the list into a single value called the reduction.
** The initial value of the reduction is passed in as the init
** parameter, then passed back to the closure along with each
** item. This method is idempotent.
**
** Example:
** list := [1, 2, 3]
** list.reduce(0) |Obj r, Int v->Obj| { return (Int)r + v } => 6
**
Obj reduce(Obj init, |Obj reduction, V item, Int index->Obj| c)
**
** Return the minimum value of the list. If c is provided, then it
** implements the comparator returning -1, 0, or 1. If c is null
** then the <=> operator is used (shortcut for compare method). If
** the list is empty, return null. This method is idempotent.
**
** Example:
** list := ["albatross", "dog", "horse"]
** list.min => "albatross"
** list.min |Str a, Str b->Int| { return a.size <=> b.size } => "dog"
**
V min(|V a, V b->Int| c := null)
**
** Return the maximum value of the list. If c is provided, then it
** implements the comparator returning -1, 0, or 1. If c is null
** then the <=> operator is used (shortcut for compare method). If
** the list is empty, return null. This method is idempotent.
**
** Example:
** list := ["albatross", "dog", "horse"]
** list.max => "horse"
** list.max |Str a, Str b->Int| { return a.size <=> b.size } => "albatross"
**
V max(|V a, V b->Int| c := null)
**
** Returns a new list with all duplicate items removed such that the
** resulting list is a proper set. Duplicates are detected using hash()
** and the == operator (shortcut for equals method). This method is
** idempotent.
**
** Example:
** ["a", "a", "b", "c", "b", "b"].unique => ["a", "b", "c"]
**
L unique()
**
** Return a new list which is the union of this list and the given list.
** The union is defined as the unique items which are in *either* list.
** The resulting list is ordered first by this list's order, and secondarily
** by that's order. The new list is guaranteed to be unique with no duplicate
** values. Equality is determined using hash() and the == operator
** (shortcut for equals method). This method is idempotent.
**
** Example:
** [1, 2].union([3, 2]) => [1, 2, 3]
**
L union(L that)
**
** Return a new list which is the intersection of this list and the
** given list. The intersection is defined as the unique items which
** are in *both* lists. The new list will be ordered according to this
** list's order. The new list is guaranteed to be unique with no duplicate
** values. Equality is determined using hash() and the == operator
** (shortcut for equals method). This method is idempotent.
**
** Example:
** [0, 1, 2, 3].intersection([5, 3, 1]) => [1, 3]
** [0, null, 2].intersection([null, 0, 1, 2, 3]) => [0, null, 2]
**
L intersection(L that)
//////////////////////////////////////////////////////////////////////////
// Utils
//////////////////////////////////////////////////////////////////////////
**
** Perform an in-place sort on this list. If a method is provided
** it implements the comparator returning -1, 0, or 1. If the
** comparator method is null then sorting is based on the
** value's <=> operator (shortcut for compare method). Return this.
** Throw ReadonlyErr if readonly.
**
** Example:
** s := ["candy", "ate", "he"]
**
** s.sort
** // s now evaluates to [ate, candy, he]
**
** s.sort |Str a, Str b->Int| { return a.size <=> b.size }
** // s now evaluates to ["he", "ate", "candy"]
**
L sort(|V a, V b->Int| c := null)
**
** Reverse sort - perform an in-place reverse sort on this list. If
** a method is provided it implements the comparator returning -1,
** 0, or 1. If the comparator method is null then sorting is based
** on the items <=> operator (shortcut for compare method). Return
** this. Throw ReadonlyErr if readonly.
**
** Example:
** [3, 2, 4, 1].sortr => [4, 3, 2, 1]
**
L sortr(|V a, V b->Int| c := null)
**
** Reverse the order of the items of this list in-place. Return this.
** Throw ReadonlyErr if readonly.
**
** Example:
** [1, 2, 3, 4].sort => [4, 3, 2, 1]
**
L reverse()
**
** Swap the items at the two specified indexes. Negative indexes may
** used to access an index from the end of the list. Return this.
** Throw ReadonlyErr if readonly.
**
L swap(Int indexA, Int indexB)
//////////////////////////////////////////////////////////////////////////
// Conversion
//////////////////////////////////////////////////////////////////////////
**
** Return a string representation the list. This method is idempotent.
**
override Str toStr()
**
** Return a string by concatenating each item's toStr result
** using the the specified separator string. If c is non-null
** then it is used to format each item into a string, otherwise
** Obj.toStr is used. This method is idempotent.
**
** Example:
** ["a", "b", "c"].join => "abc"
** ["a", "b", "c"].join("-") => "a-b-c"
** ["a", "b", "c"].join("-") |Str s->Str| { return "($s)" } => "(a)-(b)-(c)"
**
Str join(Str separator := "", |V item, Int index->Str| c := null)
// TODO
// flatten, fill, binarySearch
//////////////////////////////////////////////////////////////////////////
// Readonly
//////////////////////////////////////////////////////////////////////////
**
** Return if this List is readonly. A readonly List is guaranteed to
** be immutable (although its items may be mutable themselves). Any
** attempt to modify a readonly List will result in ReadonlyErr. Use
** rw() to get a read-write List from a readonly List. Methods
** documented as idempotent may be used safely with a readonly List.
** This method is idempotent.
**
Bool isRO()
**
** Return if this List is read-write. A read-write List is mutable
** and may be modified. Use ro() to get a readonly List from a
** read-write List. This method is idempotent.
**
Bool isRW()
**
** Get a readonly, immutable List instance with the same contents
** as this List (although the items may be mutable themselves). If
** this List is already readonly, then return this. Only methods
** documented as idempotent may be used safely with a readonly List,
** all others will throw ReadonlyErr. This method is idempotent.
** See isImmutable and toImmutable for deep immutability.
**
L ro()
**
** Get a read-write, mutable List instance with the same contents
** as this List. If this List is already read-write, then return this.
** This method is idempotent.
**
L rw()
**
** Return an immutable List which returns true for Obj.isImmtable.
** If this List is already immutable, then return this. This method
** is effectively a "deep ro()" which guarantees that if any items
** are Lists or Maps, then they are made immutable by recursively calling
** toImmutable. All other items must return true for Obj.isImmutable,
** otherwise NotImmutableErr is thrown. This method must be used
** whenever setting a const List field. This method is idempotent.
**
L toImmutable()
}