Class Ls extends System.Collections.ArrayList

Introduction

This class adds numerous extensions to the Synergy/DE version of System.Collections.Arraylist to enable: This page documents ls version 1.9 (Download source)
Author: Chip Camden

Contents

  1. Introduction
  2. Contents
  3. Explanation of symbols used
  4. Member reference
    1. append, append$, appendflat$, add$, +, |, & - append to a list
    2. car - the first element in a list
    3. cdr - the second and following elements in a list
    4. chop, chop$ - truncate a list
    5. compact, compact$ - remove null elements from a list
    6. contains - determine if an object is a member of a list
    7. copy - copy a list
    8. countif - conditionally count members
    9. empty - create a new, empty list
    10. Equals - override instance equality testing
    11. flatten - flatten a list
    12. from - create a list from another list or an array
    13. intersection - intersection of two lists
    14. issubsetof - determine whether a list is a subset of another list
    15. issupersetof - determine whether a list is a superset of another list
    16. join - join a list to create a string
    17. keyadd - add an association to an alist
    18. keydel - delete an association from an alist
    19. keyfind - find an element of an alist
    20. keyget, [] - get the value associated with a key in an alist
    21. keygetl - get the list of values associated with a key in an alist
    22. keyset, []= - set the value associated with a key in an alist
    23. of - create a list from an object
    24. map, map$ - map one list to another
    25. merge, merge$ - merge two lists
    26. mergesort - sort a list, using MergeSort
    27. pop - remove and return the first item in a list
    28. push - insert an item at the front of a list
    29. quicksort, quicksort$ - sort a list, using QuickSort
    30. remove, remove$, operator - - remove an object from a list
    31. removeif, removeif$ - conditionally remove items
    32. reverse - reverse a list
    33. rotate$ - reorder members of a list
    34. sort, sort$ - sort a list
    35. subseq - subsequence of a list
    36. subtract, subtract$, - - subtract one list from another
    37. ToString - override string representation
    38. union - union of two lists
    39. uniq, uniq$ - remove duplicates from a list
  5. Compare functors
    1. CompareCar - compare list first elements
    2. CompareDesc - descending sort
    3. CompareList - compare lists
    4. CompareMap1 - map the first object in a comparison
    5. CompareMap2 - map both objects before comparing them
    6. CompareString - compare ToString() results
    7. CompareVar - compare Vars
    8. CompareVarAlpha - compare Vars as alphanumeric
    9. CompareVarDec - compare Vars as decimal
    10. CompareVarInt - compare Vars as integer
  6. Mapper functors
    1. abstract MapObject - map one object to another
      1. MapAssoc - map a key to its association in an alist
      2. MapDeep - recursively map all ls members
      3. MapIf - map objects using MapBoolean
      4. MapKey - create a key => value pair from a value
      5. MapVar - map objects to Var
        1. MapAlpha - map objects to VarAlpha
        2. MapDec - map objects to VarDec
        3. MapInt - map objects to VarInt
    2. abstract MapBoolean - map an object to a boolean
      1. MapNonNull - map true if not null
      2. MapNull - map true if null

Explanation of symbols used

Words in italics indicate an instance of a class. The word corresponds to the class name, except where more than one instance is represented in the same statement. In that case a number (2, 3, etc.) is appended to the class name.

Words in normal typeface are to be taken literally (required punctuation, class name in a static reference, method name, etc.)

The symbol => is used to separate an expression (on the left) from its return value (on the right).

An ellipsis (...) indicates that the previous argument may be repeated any number of times. The description will indicate whether one instance is required.

Generally speaking, methods that end in "$" modify the receiver, while methods that don't end in "$" are free of side-effects. But that isn't always the case. The methods push and pop (as well as the properties car and cdr when set) modify the receiver -- but I have omitted the "$" because their traditional names adequately communicate their side-effects, I believe.

Member reference

methods append, append$, appendflat$, add$; operators +, |, &

ls.append(object) => ls2
ls + object => ls2

ls.append$(object) => ls
ls | object => ls

ls.add$(object) => ls
ls & object => ls

ls.appendflat$(object) => ls

The append method (and the + operator) adds an object to a list, returning a new list. if object is an ArrayList (or a derived class, such as another ls), then all of its members are added instead of the ArrayList itself.

The append$ method (and the | operator) modifies ls by adding the object in place, and returns the modified list. It also expands any Arraylist passed.

The add$ method (and the & operator) operates like append$, but ArrayLists are not expanded. This provides for composing nested lists.

The appendflat$ method operates like append$, but any ArrayList argument is completely flattened. Not only is the Arraylist replaced by its members, but any members of the ArrayList that are ArrayLists are recursively expanded.

In all of the above, if object is a primitive, it will be automatically boxed in a Var

.

Examples of list composition

ls.of(1) | 2 | "fred" | an_object | a_list

Creates a one-dimensional list from three primitives (which are boxed as Vars), an object, and the members of another list


    ls.of("1a") & "1b" &
    &     (ls.of("2a") &
    &           (ls.of("3a") & "3b"))

Creates a tree with three top nodes: "1a", "1b", and another list that contains two nodes: "2a" and another list that contains two nodes: "3a" and "3b". Note that the ampersands on the left side are Synergy/DE line-continuation characters.

Why didn't I use "<<" for append, and reserve "|" and "&" for union and intersection, respectively? Synergy/DE does not provide an override for "<<". I didn't want to use just "<" in case I add comparison operators later, and intersection and union seem like rare enough operations that requiring them to be spelled out should not be onerous.

property car

ls.car => object
ls.car = object
Property for referencing the first element of a list. Because this is a property, auto-boxing of primitives does not occur. In the first form, if the list is empty, ^null is returned.

property cdr

ls.cdr => ls
ls.cdr = ls2
Property for referencing the second and following elements of a list. When retrieved, a new ls containing the second through last items is returned. When set, the second through last elements of the list are removed and replaced with the elements of ls2.

methods chop, chop$

ls.chop(int) => ls2
ls.chop$(int) => ls
Both of these methods truncate the list at the length specified by int (in other words, removing items from that index to the end). The chop method returns a truncated copy of the original list, leaving the original unmodified, while chop$ modifies and returns the original list.

methods compact, compact$

ls.compact() => ls2
ls.compact$() => ls
Both of these methods remove null elements from a list. The compact$ method modifies and returns the original list, while compact returns a modified shallow copy, leaving the original untouched.

method contains

ls.contains(object) => boolean
Returns true if object is a member of the list, otherwise false. This test uses IndexOf, which in turn invokes the Equals() method to compare objects. To determine whether a list is a subset of another list, see issubsetof and issupersetof.

method copy

ls.copy() => ls2
Returns a shallow copy of a list (members are copied by reference).

method countif

ls.countif(mapboolean) => int
Returns the count of the number of elements in the list that, when passed to mapboolean's test method, return true. See MapBoolean.

static method empty

ls.empty() => ls
Creates and returns a new empty list. This method is provided because the syntax new ls() is not valid in all contexts where the result of a method can be used instead.

override method Equals

ls.Equals(object) => boolean
Override of object.Equals() to specialize the comparison of an ls and any ArrayList. The two lists are considered equal if they have the same Count, and invoking Equals() on each of the members of ls returns true when passed the corresponding member of object (or both are ^null).

method flatten

ls.flatten() => ls2
Returns a copy of a list in which all members that are ArrayLists are recursively replaced by their members. The result is a flat list of all non-ArrayList members.

static method from

ls.from(arraylist) => ls
ls.from(array) => ls
ls.from(realarray) => ls   *** Synergy/DE 9.3 and above ***

Creates a new ls from arraylist or array. Members are copied by reference.

For array, up to 3 dimensions are supported for dynamic object arays ([#,#,#]@class), and those dimensions will be preserved as lists within lists. Note that no automatic type conversions will occur. In particular, strings are not converted to VarAlpha. Use the map method to perform these conversions, if desired. For instance, to convert a multi-dimensioned array of strings to a list of lists of VarAlpha:

ls.from(array).map(new MapDeep(new MapAlpha()))

Real arrays of primitive types ([*]type) only work on Synergy/DE version 9.3 and above, due to a compiler bug (tr#30719). If you try to use real arrays with this method in Synergy/DE version 9.1* or even in the 9.2.1 beta, it will crash the Synergy/DE runtime. This method only supports real arrays of one dimension, because I got tired of fighting with the compiler. The primitive values will be boxed as Vars.

Note also that since arrays are 1-based while ArrayLists are 0-based, the indices of members in the resulting list will be one less than their indices in the original array. That goes for both array and realarray

method issubsetof

ls.issubsetof(ls2) => boolean
Returns true if every member of ls can be found in ls2, otherwise false.

method issupersetof

ls.issupersetof(arraylist) => boolean
Returns true if every member of arraylist can be found in ls, otherwise false.

method join

ls.join(string) => string2
Returns a string composed of the return value of the ToString() method of each non-null element in the list, separated by string.

method keyadd

ls.keyadd(object, object2) => ls
Adds object2 to the association for key object. If object or object2 are primitives, they will be boxed as Vars. Unlike method keyset, this method does not delete any previous association with the key, it merely adds another object to the sublist for the association. This allows for multiple objects associated with the same key, as in a multimap.. Use the method keygetl to retrieve all associations for a key as an ls.

method keydel

ls.keydel(object) => ls
Removes the entire first association in the list whose key matches object. See keyfind for details. If object is a primitive, it will be automatically boxed in a Var.

method keyfind

ls.keyfind(object) => ls2
Finds a member of an alist using object as a key. For each element of ls, if that element is also an ls with at least one member, object's Equal() method is invoked to test for a match against the first element of that ls. If it returns true, the ls is returned. If the key is a primitive, it is automatically boxed as a Var. This supports the alist construct in which elements of a list are themselves lists in which the first element is treated as a key. This implementation is a bit naive and underperforms for large arrays (O(n*(n/2)) to randomly access all elements). For a much faster version that is limited to alphanumeric keys and does not provide many of the features of ls, try Hash.

method keyget, property Indexer get

ls.keyget(object) => object2
ls[object] => object2
Gets the value object2 associated with a key object in an alist. If no such key exists in the alist, ^null is returned. If object is a primitive, it is automatically boxed as a Var, except for numeric types passed to the Indexer (in order to avoid hiding ArrayList.Indexer). If more than one value is associated with the key, they are returned in an ls.

method keygetl

ls.keygetl(object) => ls
Gets the list of values associated with key object in an alist. If object is primitive, it will be boxed in a Var. If the key is not found, an empty ls is returned.

method keyset, property Indexer set

ls.keyset(object, object2) => ls
ls[object] = object2
Sets the value object2 associated with a key object in an alist. If the alist already contains an association for the specified key, then that association sublist's cdr is replaced by object2. Otherwise, a new sublist is added to ls containing the pair object, object2. If either object is a primitive, it is automatically boxed as a Var, except for numeric types passed to the Indexer (in order to avoid hiding ArrayList.Indexer).

method intersection

ls.intersection(arraylist) => ls2
Returns a new list containing all of the members of the original list that are also found in arraylist (which can be another ls). Because of the implementation of ls.Equals(), elements that are instances of ls and contain the same members will be treated as identical.

static method of

ls.of(object) => ls
Creates a new single-element ls containing object. if object is a primitive, it will be automatically boxed in a Var.

methods map, map$

ls.map(mapobject) => ls2
ls.map$(mapobject) => ls
These methods map each object in the list to another object, which is the result of passing the original object to mapobject's map method. The ls method map produces a new list, while map$ replaces each item in the original list. See MapObject.

methods merge, merge$

ls.merge(arraylist, compare) => ls2
ls.merge$(arraylist, compare) => ls

Assumes that both lists are sorted, and returns a merged list. The two methods use different algorithms, with merge$ inserting items from arraylist into ls, while merge appends items from each list to the new ls2. Method mergesort uses the merge, which performs slightly better with large lists.

Comparisons between the members of the two lists are performed by calling the test method of compare. See Compare functors.

method mergesort

ls.mergesort(compare) => ls2
Sorts the list, using compare, and returns a new list (leaving ls unmodified). See Compare functors. MergeSort appears from testing to be faster than QuickSort when the list contains more than circa 900,000 elements.

method pop

ls.pop() => object
Removes and returns the first element of the list. If the list is empty, returns ^null.

method push

ls.push(object) => ls
Inserts object at the front of the list, returning the modified list.

methods quicksort, quicksort$

ls.quicksort(compare) => ls2
ls.quicksort$(compare) => ls
Sorts the list, using compare. See Compare functors. Both methods use the in-place QuickSort algorithm, but quicksort copies the list first, while quicksort$ modifies ls. QuickSort appears from testing to be faster than MergeSort when the list contains fewer than circa 900,000 elements.

methods remove, remove$; operator -

ls.remove(object) => ls2
ls.remove$(object) => ls
ls - object => ls2
Removes all occurences of object from ls, returning either a new ls (in the case of remove and the operator -), or the modified receiver (in the case of remove$). If object is not a member of ls, no error occurs. if object is primitive, it will be boxed in a Var so that Var comparisons will apply. See subtract for a method to remove all elements of one list from another.

methods removeif, removeif$

ls.removeif(mapboolean) => ls2
ls.removeif$(mapboolean) => ls
Removes objects from a list that return true when passed to mapboolean's test method. See MapBoolean. The method removeif leaves ls unmodified, while removeif$ modifies and returns ls.

method reverse

ls.reverse() => ls2
Creates and returns a copy of the original list with the order of its members reversed.

method rotate$

ls.rotate$(int...) => ls
Swaps members of a list by index. At least one index is required. The element at the first specified index will be moved to the last specified index. The member at the second specified index (if any) will be moved to the first specified index, and so forth. Returns the modified list.

methods sort, sort$

ls.sort(compare) => ls2
ls.sort$(compare) => ls
Sorts a list, using compare. See Compare functors. The method sort$ uses QuickSort to sort the list in-place, while sort creates a sorted copy of the list. For sort, if the number of elements in the list is less than 900,000, then QuickSort is applied to a copy of the list. If 900,000 or above, MergeSort is used instead.

method subseq

ls.subseq(int) => ls2
ls.subseq(int, int2) => ls2
Returns a list containing the members of the original list beginning at the index specified by int, up to and including the index specified by int2. If int2 is omitted, the last element in the list is assumed.

methods subtract, subtract$; operator -

ls.subtract(arraylist) => ls2
ls.subtract$(arraylist) => ls
ls - arraylist => ls2
Removes all the elements of arraylist from ls. In the case of subtract and the operator -, the ls is unmodified and a new list is returned -- while subtract$ modifies and returns its receiver. If an element in arraylist does not occur in ls, no error occurs. See remove for removing objects from a list.

override method ToString

ls.ToString() => string
Override of object.ToString() to specialize the string representation of lists. the list is represented as a "[" followed by the result of ToString() on each of its elements (separated by commas), followed by a closing "]". Null elements are represented as "^null".

methods union, union$

ls.union(arraylist) => ls2
ls.union$(arraylist) => ls
ls.union(object) => ls2
ls.union$(object) => ls
Returns a list containing all of the members of the original list and all of the members in arraylist (which can be another ls). If object is passed (i.e., a non-ArrayList object), it will be treated as a list of one object -- and if it is primitive it will be boxed as a Var. The union method returns a new list, while union$ modifies the receiver. Unlike append, any element found in both lists is not duplicated. You can therefore use this method to add objects uniquely, as in a set. Because of the implementation of ls.Equals(), elements that are instances of ls and contain the same members will be treated as identical.

methods uniq, uniq$

ls.uniq() => ls2
ls.uniq$() => ls
Both of these methods remove duplicates from a list (based on the element's Equals method). The uniq method returns a uniq'd copy of the list, while uniq$ modifies and returns the original list.

Compare functors

Introduction

The abstract class Compare provides a pattern for functors used in comparisons. It's a poor man's excuse for lambdas, and about the only way to provide a lazy callback that can handle objects in Synergy/DE.

Derived classes must implement one method: test, which takes two object arguments and returns an integer. If the first object is greater than the second, return 1. If equal, return 0, If less than, return -1. The method must be able to handle null objects.

Derived classes may implement other members as needed. For instance, a number of the provided classes (detailed below) implement constructors that take parameters to control their behavior.

Some Compare classes take a Compare as an argument. These are intended to modify the comparison operation in some way. For instance, to compare objects as lists of strings in descending order, you could create a combined functor like: new CompareDesc(new CompareList(new CompareString())). CompareDesc will reverse the sense of the return value from CompareList, which will call CompareString to compare each member of the lists contained within the list. A good combination to use for sorting an associative list by key value (if the keys are strings) would be new CompareCar(new CompareVarAlpha()) .

Compare functors also provide overloads for the comparison operators (==, !=, >, <, >=, and <=), each of which produce a MapBoolean object that performs the specified lazy comparison against the right-hand term (MapCompareEqual, MapCompareNotEqual, MapCompareGreaterThan, MapCompareLessThan, MapCompareGreaterThanOrEqual, MapCompareLessThanOrEqual). See MapBoolean. If the right-hand term is primitive, it will be automatically boxed as a Var. Thus, for example, to create a lazy evaluation functor for testing Vars as greater than 5, use new CompareVar() > 5, which produces a MapBoolean that performs that test against the object passed to its test method.

The following derived classes are provided:

CompareCar

new CompareCar(compare)

If either of the objects is a list, its first element will be used -- otherwise the object itself. If that first element is a list, its first element will be used, and so on recursively until a non-list is encountered. Then the result returned from invoking compare's test method for those two objects will be returned.

This Comparer is useful for sorting associative lists by key. An associative list (or alist) is one in which each element is itself a list, comprised of a key and data. See keyfind.

CompareDesc

new CompareDesc(compare)
Reverses the order provided by compare.

CompareList

new CompareList(compare)
This comparer treats each object as a list. if either of the objects is not a list, then it is automatically wrapped in a list. Each list is then compared (using compare) element by element until not equal, or the end of a list is reached. If one of the lists then contains more elements, it is treated as greater -- if the same, they're equal.

CompareMap1

new CompareMap1(mapobject, compare)
Uses mapobject to map only the first of the two objects to be compared before passing both to compare's test method. This comparer should not be used in a sort, but it may be useful in other contexts, such as the ls methods countif or removeif.

CompareMap2

new CompareMap2(mapobject, compare)
Uses mapobject to map both of the objects to be compared before passing them to compare's test method. This comparer should be used when mapping objects for sorting.

CompareString

new CompareString()
new CompareString(boolean, boolean2)
TestNatural(string, string2) => int

Compares the result of ToString() on both objects. ^null is considered equal to "".

When the constructor is invoked without arguments, defaults to case-insensitive, natural order. If called with arguments, boolean is true for case-sensitive, boolean2 is true for natural order or false for alphanumeric order.

This class also provides the static method TestNatural that compares two strings according to natural order rules.

CompareVar

new CompareVar()
Compares Var objects using Var's built-in comparisons. Non-Vars are treated as greater than Vars, and their order relative to each other is undefined.

CompareVarAlpha

new CompareVarAlpha()
Compares Var objects, casting them to alphanumeric. Non-Vars are treated as greater than Vars, and their order relative to each other is undefined.

CompareVarDec

new CompareVarDec()
Compares Var objects, casting them to decimal. Non-Vars are treated as greater than Vars, and their order relative to each other is undefined.

CompareVarInt

new CompareVarInt()
Compares Var objects, casting them to integer. Non-Vars are treated as greater than Vars, and their order relative to each other is undefined.

Mapper functors

Introduction

Mappers are used to map one object to another object or value. Currently there are two types of mappers, which correspond to the two abstract classes MapObject and MapBoolean.

MapObject

MapObject maps one object to another. Derived classes must override method map, which takes an object as argument and returns an object. The following derived classes may provide what you need:

MapAssoc

new MapAssoc(ls)
Maps objects as keys in an alist (ls), returning their associated object.

MapDeep

new MapDeep(mapobject)

Recursively maps all sublists using mapobject. For each object passed to this mapper's map method, if that object is not an ls, the result is the result of mapping that object using mapobject's map method. If the object is an ls, then the result is a new ls containing the results of mapping each of the original members of that sublist using MapDeep and mapobject.

This mapper if useful for mapping only the leaf nodes in a tree, where branches are represented by lists within lists

.

MapIf

new MapIf(mapboolean, object)
new MapIf(mapboolean, object, object2)
Maps objects to object or object2, depending on the result of passing each incoming object to mapboolean's map method: if true, object, else object2. If object2 is not given, then the original object is returned instead. See MapBoolean. If the resulting object is also a MapObject, the incoming object is passed to its map method to produce the final result. Thus, nested ifs and elses can be achieved, as well as conditional mapping functors per object.

MapKey

new MapKey(mapobject)
Creates key => value pairs from objects, using mapobject to produce the key. The resulting object is an ls containing the key and the original object. Thus, passing a MapKey to the ls methods map or map$ produces an alist.

MapVar

new MapVar()

Treats each object as a Var. Non-Vars are returned as-is. This class is most useful for its derived classes and the operators it provides, which create derived class instances to perform lazy operations on each mapped object.

For instance, new MapVar() + 12 creates a MapVarAdd object (derived from MapVar) that will add 12 to each object being mapped. MapVar provides operations for addition, subtraction, multiplication, division, and unary negation.

If either operand in an expression is a MapVar, it will be passed the object to map until a non-MapVar is returned. Thus it is possible to substitute the object being mapped at multiple points in a mathematical operation. For instance, integer(100) - integer(100) / new MapInt() * new MapInt() provides a poor man's modulo function (100 mod x, where x is the object being mapped) -- at least, until I add modulo to Var and MapVar.

Some derived classes of MapVar may be instantiated directly:

MapAlpha

new MapAlpha()
new MapAlpha(case)
Maps objects to their ToString() representation, optionally manipulating case. Case is an enumeration of Case.NoChange (the default), Case.Upper, or Case.Lower. The resulting string is boxed in a Var. Null objects are mapped to "".

MapDec

new MapDec()
Maps objects to a decimal Var (VarDec). If the incoming object is a Var, it is merely cast as decimal and re-boxed. Otherwise, the object's ToString() representation is boxed as a VarAlpha and then cast as decimal and re-boxed -- resulting in an alpha to decimal conversion, with any non-decimal string returning 0. Null objects are also mapped to 0.

MapInt

new MapInt()
Maps objects to an integer Var (VarInt). If the incoming object is a Var, it is merely cast as integer and re-boxed. Otherwise, the object's ToString() representation is boxed as a VarAlpha and then cast as integer and re-boxed -- resulting in an alpha to integer conversion, with any non-decimal string returning 0. Null objects are also mapped to 0.

MapBoolean

MapBoolean maps an object to a boolean value. Derived classes must override method test, which takes an object as argument and returns a boolean.

MapBoolean includes operator overloads for .and. (&&), .or. (||) and .xor. comparisons against other MapBooleans, each yielding a new MapBoolean that combines the two lazy tests (MapAnd, MapOr, and MapXor, respectively). Synergy/DE optimizations apply -- that is, if the first operation in an .and. yields false, the second operation will not be tested, etc. Grouping with parentheses works as expected. An overload for the .not. operator (!) is also provided, which yields a MapBoolean object that reverses the result of its argument (MapNot).

Most of the provided derived classes are instantiated through the use of operators on either the MapBoolean or Compare classes. But you may create your own derived classes to perform other tests.

The following additional derived classes are provided:

MapNonNull

new MapNonNull()
Maps objects to true if they're not equal to ^null, otherwise false.

MapNull

new MapNull()
Maps objects to true if they're equal to ^null, otherwise false.