Perl Module Tree::Matica Documentation

NAME

Tree::Matica - A Perl package for list based functional programing.

SYNOPSIS

     # importing all functions. Recommended.
     use Tree::Matica;

     # importing a selection of functions.
     use Tree::Matica ('functionName1', 'functionName2', etc);

OVERVIEW

This package provides about 30 functions for creating and manipulating trees. (tree as nested lists) These functions include tree constructors, selectors, mutators, structure transformers and a set of functions usually found in functional programing languages. Together they form a consistent way of functional programing on trees -- a paradigm often used in Lisp programing.

Perl provides nested lists using references. Familiarity with Perl references is necessary in using this module.

In this documentation, a tree will mean a nested lists of the form [[…],…]. In other words, when you read "…f(tree) does xxx.", it means the argument to f is a reference to a list. Anything in the tree that is not an array reference is considered an atom. Atoms should be either numbers or strings. Other data types such as hash, tie, typeglob, handle, reference to anything other than array, are not expected.

The following is a list of functions provided by this module.

    Tree constructors
        Range, Table

    Tree measurers
        Depth, LeafCount, NonleafCount, NodeCount, Dimensions

    Branchs and Nodes Extractors
        Part, Level

        Possible Addition: Extract, Take, Drop, Rest, First, Last, Cases,
        DeleteCases.

    Structure Transformation
        Transpose, FlattenAt

        Unimplemented: Distribute, Thread, Operate, Flatten, Sequence.

    Functions on Flat Lists
        RotateLeft

        Unimplemented: Union, Intersection, Complement, Append, Prepend,
        Join, Partition, Split

    Misc
        Function, Map

        Unimplemented: Apply, MapIndexed, MapAll, MapThread, Nest, NestList,
        FixedPoint, FixedPointList, Fold, FoldList, Outer, Inner, Cross.

    Tree Index Set Utilities
        RandomIndexSet, LeavesIndexSet, NonleavesIndexSet, MinimumIndexSet,
        CompleteIndexSet, IndexSetSort, TreeToIndexSet, IndexSetToTree

    Miscellaneous Functions
        UniqueString, RandomInteger, RandomReal

Installation:

This package should be placed in a directory named Tree. And Tree
should be placed in one of Perl library paths. (see 'perldoc lib') Or,
use the following code:

  use lib '/path/to/Tree/dir';
  use Tree::Matica;

Detailed Documentation

  Tree constructors
    Range

    Range($iMax) generates the list [1, 2, … , $iMax].

    Range($iMin, $iMax) generates the list [$iMin, … , $iMax].

    Range($iMin, $iMax, $iStep) uses increment $iStep, with the last element
    in the result being less or equal to $iMax. $iStep cannot be 0. If
    $iStep is negative, then the role of $iMin and $iMax are reversed.

    If Range fails, 0 is returned.

    Example:

     Range(5); # returns [1,2,3,4,5]

     Range(5,10); # returns [5,6,7,8,9,10]

     Range( 5, 7, 0.3); # returns [5, 5.3, 5.6, 5.9, 6.2, 6.5, 6.8]

     Range( 5, -4, -2); # returns [5,3,1,-1,-3]

    Table

    Table('exprString', [iMax]) generates a list of iMax copies of value of
    eval('exprString'), and returns the reference to the list. i.e.
    [eval('exprString'),eval('exprString'),…]

    Table('exprString', ['i', iMax]) generates a list of the values by
    evaluating 'exprString' when 'i' in the string runs from 1 to iMax.

    Table('exprString', ['i', iMin, iMax]) starts with 'i' = iMin.

    Table('exprString', ['i', iMin, iMax, iStep]) uses steps iStep. If iStep
    is negative, then the role of iMin and iMax are reversed. Inputs such as
    [1, -3 , 1] returns bad result.

    Table('exprString', ['i', iMin, iMax, iStep], ['j', jMin, jMax, iStep],
    … ) gives a array by iterating 'i', 'j' in 'exprString'. For example,
    Table('f(i,j)', ['i',1,3], ['j',5,6]) returns [[f(1, 5), f(1, 6)], [f(2,
    5), f(2, 6)], [f(3, 5), f(3, 6)]].

    In general, Table has the form Table('expressionString', iterator1,
    iterator2, etc) where 'expressionString' is a string that will be
    evaluated by eval. iterator have one of the following forms [iMax],
    ['dummyVarString',iMax], ['dummyVarString',iMin, iMax], or
    ['dummyVarString',iMin, iMax, iStep].

    If Table fails, 0 is returned. Table can fail, for example, when the
    argument are not appropriate references or the iterator range is bad
    such as ['i',5,1].

    Example:

     Table('q(s)' ,[3]); # returns ['s','s','s']

     Table( 'i**2' , ['i', 4]); # returns [1, 4, 9, 16]

     Table('[i,j,k]',['i',2],['j',100,200,100],['k',5,6])
     # returns [[[[1,100,5],[1,100,6]],[[1,200,5],[1,200,6]]],
     #          [[[2,100,5],[2,100,6]],[[2,200,5],[2,200,6]]]]

  Tree Measurers
    Depth

    Depth(tree) returns a positive integer: the maximum number of indexes
    needed to specify any part of given tree.

    The argument must be a reference to a nested list.

    Related: LeafCount, NonleafCount, NodeCount, Dimensions.

    Example:

     Depth([]); # returns 0.

     Depth([5,98,'x']); # returns 1.

     Depth([ 'level1' , ['level2', [ 'level3', [ 'level4']]], ['lev1']]);
     # returns 4.

    LeafCount

    LeafCount(tree) returns the number of leaves in a tree.

    The argument must be a reference to a nested list. (i.e. [[…],…]) An
    atom is anything in the tree that is not an array reference. (should be
    either numbers or strings only.)

    Related: NonleafCount, NodeCount, Depth, Dimensions.

    Example:

     LeafCount([]); # returns 0.

     LeafCount([5,98,'x']); # returns 3.

     LeafCount([['1', [ '2', [ 3, '4']]], [ [5], '6']]);
     # returns 6.

    NonleafCount

    NonleafCount(tree) returns a the number of non-leaf nodes in a tree
    (root is also a non-leaf node).

    The argument must be a reference to a nested list. (i.e. [[…],…]) An
    atom is anything in the tree that is not an array reference. (should be
    either numbers or strings only.)

    It is always true that NodeCount(tree) == NonleafCount(tree) +
    LeafCount(tree).

    Related: LeafCount, NodeCount, Depth, Dimensions.

    Example:

     NonleafCount([]); # returns 0.

     NonleafCount([5,98,'x']);
     # returns 1, because this is a tree with three branches from the root,
     # and each branch is a leaf. The only non-leaf node is the root.

     NonleafCount([['a','b'],['c','d']]);
     # returns 3. This tree has two nodes from the root, each has two nodes.

     NonleafCount([['a']]);
     # returns 2.

    NodeCount

    NodeCount(tree) returns the number of nodes in a tree. It is always true
    that NodeCount(tree) == NodeCount(tree) + LeafCount(tree).

    Related: LeafCount, NonleafCount, Depth, Dimensions

    Example:

     NodeCount([]); # returns 0.

     NodeCount([5,98,'x']);
     # returns 4, because this is a tree with three branches plus the root.

     NodeCount([['a','b'],['c','d']]);
     # returns 7.

     NodeCount([['a']]);
     # returns 3.

    Dimensions

    Dimensions(tree) returns a reference to a list of the form [n_1, n_2,
    …, n_i, …], where every node at ith level of the given tree has
    n_(i+1) children. For example, [[['a'],['b'],['c']],[[1],[2],[3]]] has
    dimensions [2,3,1]. In other words, Dimensions returns a list of m items
    if the argument is an m-dimensional (rectangular) array.

    Related: Depth, NonleafCount, LeafCount, NodeCount.

    Example:

     Dimensions([]); # returns [].

     Dimensions([5,98,'x']); # returns [3].

     Dimensions([['a','b','c'],[1,2,3]]); # returns [2,3].

     Dimensions([[['a'],['b'],['c']],[[1],[2],[3]]]); # returns [2,3,1].

     Dimensions([['a','b','c'],[1,2]]); # returns [2].

  Branchs and Nodes Extractors
    Part

    Part(tree, e1, e2, e3,…) returns a branch of the tree at position
    index (e1, e2, e3,…). The e_i are integers. For example,
    Part([[['0','a','b'],'h'],'x','t'], 0, 0, 2) returns 'b'. If e_i is
    negative, counting starts from right. Cyclic counting is also used. For
    example, Part([0,1,2], 3) returns 0 and Part([0,1,2], -4) returns 2.

    Each element e_i can also be a list of integers of the form [e_i_1,
    e_i_2, e_i_3,…]. In such case, Part returns the Cartesian product of
    all e_i. For example, Part([[['0','a','b'],'h'],'x','t'], 0, 0, [1,2])
    returns ['a','b'], which has position indexes (0,0,1) and (0,0,2).
    Part($tree, [1,2],0,[3,4]) will return [['part 1 0 3', 'part 1 0
    4'],['part 2 0 3', 'part 2 0 4']].

    Related: Extract, Level.

    Example:

     Part(['a','b','c'], 0); # returns 'a'.

     Part(['a','b','c'], 3); # returns 'a'.

     Part(['a','b','c'], -1); # returns 'c'.

     Part([5,[98, 44],'x'], 1, 0); # returns 98.

     Part([5,[98, 44],'x','y'], [3,2,3]); # returns ['y', 'x', 'y'].

     $tree = [[['000', '001'], ['010', '011']], [['100', '101'], ['110', '111']]];
     Part($tree, 0, 0); # returns ['000', '001'].
     Part($tree, 0, -1); # returns ['010', '011'].
     Part($tree, 0, 1, 0); # returns '010'.
     Part($tree, 0, 1, [0,0]); # returns ['010', '010'].
     Part($tree, 0, [1,0], 0); # returns ['010', '000'].
     Part($tree, 0, [1,0], [1,0]); # returns [['011','010'],['001','000']].

     Part($tree, [1,-4], [4,1,4], [0]);
     # returns [[['100'], ['110'], ['100']], [['000'], ['010'], ['000']]].

    Level

    Level(tree, [n]) returns a list of all nodes that are on the nth level
    of the tree. Level 0 is the root, consisting of the whole tree. Level 1
    is the immediate elements in the list, i.e. those accessible by
    $tree->[m1]. Level 2 are those accessible by $tree->[m1][m2], and so on.

    If n is negative, levels are counted from leaves to root. That is,
    Level(tree, [-n]) for a positive n returns all nodes in the tree that
    have depth n. The depth of a tree, Depth(tree), is the maximum number of
    indexes needed to specify any node, plus one. (i.e. a node at level n
    for a positive n has depth n+1.) (see Depth.)

    Level( tree, [n, m]) returns a list of all nodes of the tree that's on
    levels n to m inclusive. Either one of n or m can be negative. For
    example, Level( tree, [2,-2]) returns all nodes on level 2 or more, and
    has depth 2 or greater.

    Level( tree, n) is equivalent to Level( tree, [1, n]).

    In general, the form is Level( tree, levelSpec), where levelSpec has one
    of the forms: n, [n], [n, m], where the first two forms are shortcuts.
    That is, n is equivalent to [1,n], and [n] is equivalent to [n, n].

    If the levelSpec is beyond the depth of the tree, or if it doesn't make
    sense (For example, [5,3] or [-3,-5]), an empty list is returned. (i.e. []).
    Note: levelSpec such as [3,-2] is not necessarily illegal.

    Nodes in the result list is ordered by their position indexes'
    components ascending (i.e. [2,1] comes before [3].). When there is a tie
    (For example, [2] vs. [2,1]), index length descending is used (i.e. [2,1] comes
    before [2]). For example, here's a complete index set sorted the way
    Level would:
    [[0],[1,0],[1,1,0],[1,1,1],[1,1,2],[1,1],[1,2,0],[1,2,1],[1,2,2],[1,2],[
    1],[2,0],[2,1,0],[2,1,1],[2,1,2],[2,1],[2,2,0],[2,2,1],[2,2,2],[2,2],[2]
    ]. See IndexSetSort for details about sorting nodes.

    Related: Part, Extract.

    Example:

     Level( $tree, [0]); # returns [ $tree ].

     Level( $tree, [1]); # returns $tree unchanged.

     Level( [[1,2],[3,[44]],'a'], [2]); # returns [ 1,2,3,[44] ].

     Level( [[1,2],[3,[44]],'a'], [3]); # returns [ 44 ].

     Level( [[1,2],[3,[44]],'a'], [-1]);
     # returns all the leaves [ 1,2,3,44,'a' ].
     # In other words, atoms or leaves are those having depth 1.

     Level( [[1,2],[3,[44]]], [-2]);
     # returns [ [1,2], [44] ] because both element has depth 2.

     Level( [[1,2],[3,[44]]], [-3]); # returns [ [3,[44]] ]

     Level( [[1,2],[3,[44]]], [-4]);
     # returns [ [[1,2],[3,[44]]] ] because the whole tree has depth 4.;

     Level( [[1,2],[3,[44]]], [-5]);
     # returns [ ] because the tree has depth 4. i.e. It's root node has depth 4.
     # No other node can have depth greater than the root.;

     Level( [[1,2],[3,[44]]], [1,2]);
     # returns [ 1, 2, [1,2], 3, [44], [3,[44]] ]
     # the result consists of all nodes that requires 1 or 2 indexes to access.
     # their position indexes in the tree are:
     # [0,0], [0,1], [0], [1,0], [1,1], [1]
     # note the order returned.

     Level( [[1,2],[3,[44]]], [1,3]);
     # returns [ 1, 2, [1,2], 3, 44, [44], [3,[44]] ]
     # these are nodes on levels 1 to 3.
     # their position indexes are
     # [0,0], [0,1], [0], [1,0], [1,1,0], [1,1], [1]

     Level( [[1,2],[3,[44]]], [2,3]);
     # returns [ 1, 2, 3, 44, [44] ]
     # their position indexes are
     # [0,0], [0,1], [1,0], [1,1,0], [1,1]

     Level( [[1,2],[3,[44]]], [2,-1]);
     # returns [ 1, 2, 3, 44, [44] ]

     Level( [[1,2],[3,[44]]], [2,-2]);
     # returns [ [44] ] because [44] is the only node on level 2
     # or greater and have a depth of 2 or more.

     Level( [[1,2],[3,[44]]], [1,-2]);
     # returns [ [1,2], [44], [3,[44]] ]
     # these are nodes on level 1 or greater and have a depth of 2 or more.

     Level( [[1,2],[3,[44]]], [-10,-2]);
     # returns [ [1,2], [44], [3,[44]], [[1,2],[3,[44]]] ]
     # i.e. all nodes having depth <= 10 and >= 2. Their depths are 2, 2, 3, 4.

     Level( [[1,2],[3,[44]]], [-2,1]);
     # returns [ [1,2] ];
     # i.e. all nodes having depth <= 2 and on level <= 1.

     Level( [[1,2],[3,[44]]], [-2,2]);
     # returns [ 1,2,[1,2],3,[44] ];
     # i.e. all nodes having depth <= 2 and on level <= 2.

     Level( [[1,2],[3,[44]]], [-2,3]);
     # returns [1,2,[1,2],3,44,[44]];
     # i.e. all nodes having depth <= 2 and on level <= 3.

  Structure Transformation
    Transpose

    Transpose(tree) returns a result that is the given tree with the first
    two levels transposed. For example, Transpose( [[1,2,3],['a','b','c']] ) returns
    [[1,'a'],[2,'b'],[3,'c']].

    Transpose(tree, permutationList) transposes the tree according to
    permutationList of the form [n1,n2,…,nm], where each n_i is a unique
    positive integer from 1 to m. Transpose($tree) is equivalent to
    Transpose($tree, [2,1] ).

    Transpose restructures a tree into a different shape. Here
    are some explanations, examples follows at the end. First, we'll use a
    simple example to illustrate. Suppose we have $tree =
    [[1,2,3],['a','b','c']] and $permutationList = [2,1]. The elements at
    level two of the tree have these position indexes:

     element    position index
        1            [0,0]
        2            [0,1]
        3            [0,2]
       'a'           [1,0]
       'b'           [1,1]
       'c'           [1,2]

    Since the length of $permutationList is two, thus Transpose will reshape
    the tree at level two. For each node, Transpose will apply the given
    permutation to its position index. Here's the result:

     element    position index
        1            [0,0]
        2            [1,0]
        3            [2,0]
       'a'           [0,1]
       'b'           [1,1]
       'c'           [2,1]

    Transpose then construct a tree by this new element/index pair. The
    result is [[1,'a'],[2,'b'],[3,'c']]. Because transposition with
    permutation [2,1] is common (matrix computations), thus it is the
    default behavior for Transpose with just one argument.

    The given tree needs to be a rectangular array only up to the level m,
    where m is the length of the specified permutation. For example, suppose
    we have $tree = [[1,2,3],[$anotherTree,'b','c']] and $permutationList =
    [2,1]. It all works just as before, except that the element 'a' is
    substituted by $anotherTree. For example, Transpose([[ 1,2,3],[
    ['m','n'] ,'b','c']], [2,1]) returns [[1,['m','n']],[2,'b'],[3,'c']].

    Longer permutations also works similarly. For example, suppose

    $tree = [ [['x1','x2'],['y1','y2'],['z1','z2']], [ ['a1','a2']
    ,['b1','b2'], ['c1','c2']]]; $permutationList = [3,1,2];

    Since the length of $permutationList is 3, thus looking at level 3 of
    the tree we have

     element    position index
               before /  after permute by [3,1,2]
       'x1'    [0,0,0]  [0,0,0]
       'x2'    [0,0,1]  [1,0,0]
       'y1'    [0,1,0]  [0,0,1]
       'y2'    [0,1,1]  [1,0,1]
       'z1'    [0,2,0]  [0,0,2]
       'z2'    [0,2,1]  [1,0,2]
       'a1'    [1,0,0]  [0,1,0]
       'a2'    [1,0,1]  [1,1,0]
       'b1'    [1,1,0]  [0,1,1]
       'b2'    [1,1,1]  [1,1,1]
       'c1'    [1,2,0]  [0,1,2]
       'c2'    [1,2,1]  [1,1,2]

    Therefore, the result is
    [[['x1','y1','z1'],['a1','b1','c1']],[['x2','y2','z2'],['a2','b2','c2']]
    ].

    There are some implied restrictions on the input to Transpose: 1. The
    second argument must be a permutation of a range of m numbers that
    starts with one. 2. The tree must be a rectangular array up to level m.
    That is, Length(Dimensions($tree)) >= m.

    A property of Transpose: If $tree is a rectangular array, then the
    following is always true. Permute(Dimensions($tree), $permutationList)
    == Dimensions(Transpose($tree, $permutationList))

    If $tree is a rectangular array up to level m only, then the left and
    right hand side agrees up to the first m numbers.

    Example:

     my $tree =
      [
       [ ['x1','x2'], ['y1','y2'], ['z1','z2']],
       [ ['a1','a2'], ['b1','b2'], ['c1','c2']]
      ];

     Transpose( $tree, [1, 2, 3]);
     # returns [[['x1','x2'],['y1','y2'],['z1','z2']],[['a1','a2'],['b1','b2'],['c1','c2']]]

     Transpose( $tree, [1, 3, 2]);
     # returns [[['x1','y1','z1'],['x2','y2','z2']],[['a1','b1','c1'],['a2','b2','c2']]]

     Transpose( $tree, [2, 1, 3]);
     # returns [[['x1','x2'],['a1','a2']],[['y1','y2'],['b1','b2']],[['z1','z2'],['c1','c2']]]

     Transpose( $tree, [2, 3, 1]);
     # returns [[['x1','a1'],['x2','a2']],[['y1','b1'],['y2','b2']],[['z1','c1'],['z2','c2']]]

     Transpose( $tree, [3, 1, 2]);
     # returns [[['x1','y1','z1'],['a1','b1','c1']],[['x2','y2','z2'],['a2','b2','c2']]]

     Transpose( $tree, [3, 2, 1]);
     # returns [[['x1','a1'],['y1','b1'],['z1','c1']],[['x2','a2'],['y2','b2'],['z2','c2']]]

     Transpose( $tree, [2, 1]);
     # returns [[['x1','x2'],['a1','a2']],[['y1','y2'],['b1','b2']],[['z1','z2'],['c1','c2']]]

    FlattenAt

    FlattenAt(tree, positionIndex) returns a modified version of given tree
    where the node (subtree) at positionIndex is moved (flattened) up to its
    parent generation. (In other words: the brackets of the element at
    positionIndex is removed.)

    Related: Flatten, Sequence, xxxxx.

    Example:

     FlattenAt(['a', ['b']], [1]); # returns ['a', 'b'].

     FlattenAt(['a', 'b'], [0]);
     # xxxxx returns 0 and prints "Error: position [0] of tree has no parts and cannot be flattened".

     FlattenAt([[8,['a']], [3] ], [0]); # returns [8, ['a'], [3] ]

     FlattenAt([ [8, ['a']], [3] ], [0,1]); # returns [ [8, 'a'], [3] ]

  Functions on Flat Lists
    RotateLeft

    RotateLeft($arrayReference) returns an array reference that is the given
    array with elements rotated to the left. RotateLeft($arrayReference, n)
    rotates by n. n is an integer. ($n can be negative or 0)

    Example:

     RotateLeft([1..4], 2) # returns [3,4,1,2].

    Example:

     for (my $i=0;$i<=3;$i++) {print qq(@{RotateLeft([0..3],$i)}\n);};
     # prints a 4 x 4 Latin square
     0 1 2 3
     1 2 3 0
     2 3 0 1
     3 0 1 2

  Misc
    Function

    Function(parameterList,'expressionString') returns a function. The
    function takes parameters in parameterList and has body
    expressionString. parameterList is a reference to a list of strings,
    each represents a parameter name. For example: ['i','j']. The return
    value of Function is a reference to a function.

    Example:

    &{Function(['i','j'],'i + j')}(3,4); # returns 7.

    Map

    Map(f, tree) returns the result of applying f to tree. f must be a
    reference to a subroutine or anonymous function. For example: Map( sub
    {$_**2;}, [9,2,5]); returns [81,4,25].

    Map(f, tree, levelSpec) maps f to nodes specified by levelSpec. Map(f,
    tree) is equivalent to Map(f, tree, [1]). The general form of levelSpec
    is [m,n], meaning levels m to n inclusive. f is applied to the tree in
    the same order as the function 'Level'. That is, commonly known as
    "depth first". See Level for detail about levels and levelSpec.

    Map(f, tree, [1]) has the same functionality as Perl's "map".

    The most common use of Map is applying a function to a specific level of
    a tree. For example, Map( $func , $tree, [2]) will return a modified
    $tree, where all nodes (subtrees) at level 2 are transformed by having
    $func applied to them. For example:

     Map($f, [[$subTree1,$subTree2], 'anAtom', [$subTree3] ], [2])
     # returns [[&{$f}($subTree1), &{$f}($subTree2)], 'anAtom', [ &{$f}($subTree3) ] ].

     Map($f, [[$subTree1,$subTree2], 'anAtom', [$subTree3] ], [1])
     # returns [&{$f}([$subTree1, $subTree2]), &{$f}('anAtom'), &{$f}([$subTree3]) ].

    Map( $func , $tree, [-1]) will apply $func to all the leaves of the
    tree.

    Related: xxxxx, Apply, MapIndexed, MapAll, MapThread.

    Example:

     Map( sub {$_[0]**2;}, [1,2,3,4]); # returns [1,4,9,16].

     Map( sub {$_[0]**2;}, [1,2,3,4], [1]); # returns [1,4,9,16].

     Map( sub {$_[0]**2;}, [[1],[2],[3]], [2]); # returns [[1],[4],[9]].
     # The levelSpec [-1] specified all the atoms/leaves of the tree.

     Map( sub {$_[0]**2;}, [7,[3],[5]], [-1]); # returns [49,[9],[25]].

    xxxxxx Needs more examples. Need examples that uses multiple levels, and
    practical examples showing the usefulness of Map.

    UniqueString

    UniqueString('aString', n) returns a reference to a list of n elements
    of strings, none of which are in the given string and no two are
    identical. Each string starts with 'unik' and followed by digits.

    Example:

     UniqueString('Something about love…', 2);
     # returns ['unik23946', 'unik14135'].

    RandomInteger

    RandomInteger(iMin, iMax) returns a pseudo-random integer between iMin
    and iMax, including the boundaries. iMin and iMax should be integers, if
    not, their integer part is taken.

    RandomInteger calls Perl's "rand" function. It's quality is dependent on
    "rand".

    Example:

     RandomInteger(-5, 3);

    RandomReal

    RandomReal(iMin, iMmax) returns a pseudo-random real number between real
    numbers rMin and rMax.

    RandomReal calls Perl's "rand" function. It's quality is dependent on
    "rand".

    Example:

     RandomReal(-3.7, 10);

    RandomIndexSet

    RandomIndexSet() returns a random list of indexes. e.g.
    [[3,2,5],[0,3],[4,2,0,4]].

    RandomIndexSet([minIndexNumber, maxIndexNumber], [minIndexLength,
    maxIndexLength], [minTotalIndexes, maxTotalIndexes]) generates a list of
    random indexes based on given parameters.

    Not all arguments must be given. The default parameters are
    RandomIndexSet([0,4],[1,4],[1,10]). Supplied ones will replace the
    default beginning from left.

    Example:

     RandomIndexSet()
    # returns [[3,2,5],[0,3]]

     RandomIndexSet([0,8],[1,5],[5,5])
    # returns [[7], [6], [4, 4, 5], [3], [8, 8, 7]]

    LeavesIndexSet

    LeavesIndexSet([index1,index2,…]) returns a modified version of input
    in which non-leaf indexes are deleted. Indexes are of the form
    [n1,n2,n3,…] where the n are non-negative integers.

    Related: NonleavesIndexSet.

    Example:

     LeavesIndexSet([[2], [4], [4, 2], [4, 3], [4, 3, 5]])
     # returns [[2], [4, 2], [4, 3, 5]].

    NonleavesIndexSet

    NonleavesIndexSet([index1,index2,…]) returns a modified version of
    input in which leaf indexes are deleted. Indexes are of the form
    [n1,n2,n3,…] where the n are non-negative integers.

    Related: LeavesIndexSet.

    Example:

     NonleavesIndexSet([[2], [4], [4, 2], [4, 3], [4, 3, 5]])
     # returns [[4], [4, 3]].

    MinimumIndexSet

    MinimumIndexSet([index1,index2,…]) returns a modified version of input
    in which indexes that can be inferred from other indexes are deleted.
    Indexes are of the form [n1,n2,n3,…] where the n are non-negative
    integers.

    Related: CompleteIndexSet, FullArrayIndexSet.

    Example:

     MinimumIndexSet([[1], [2], [3], [2, 3], [2, 2], [2, 3, 7], [3, 1]])
     # returns [[2, 3, 7], [3, 1]].

    CompleteIndexSet

    CompleteIndexSet([index1,index2,…]) returns a modified version of
    argument in which indexes that are implied by givens are inserted. The
    elements in the result list is arbitrary ordered, and without
    duplicates.

    Related: MinimumIndexSet, FullArrayIndexSet, IndexSetSort.

    Example:

    The empty array [] in the result represents the index for the root node.

     IndexSetSort( CompleteIndexSet( [[2, 1]] ) );
     # returns [[],[0],[1],[2],[2,0],[2,1]].

     IndexSetSort( CompleteIndexSet( [[2, 1], [3]] ) );
     # returns [[],[0],[1],[2],[3],[2,0],[2,1]].

     IndexSetSort( CompleteIndexSet( [[2, 1], [3], [3]] ) );
     # returns [[],[0],[1],[2],[3],[2,0],[2,1]].

     IndexSetSort( CompleteIndexSet( [[3, 3], [4]] ) );
     # returns [[],[0],[1],[2],[3],[4],[3,0],[3,1],[3,2],[3,3]].

     IndexSetSort( CompleteIndexSet( [[3, 3], [1, 1], [4]] ) );
     # returns [[],[0],[1],[2],[3],[4],[1,0],[1,1],[3,0],[3,1],[3,2],[3,3]].

    IndexSetSort

    IndexSetSort([index1,index2,…]) returns the indexes sorted. This is
    equivalent to IndexSetSort([index1,index2,…],0,1,1). The indexes have
    the form [[a1,a2,…],[b1,b2,…],…].

    IndexSetSort([index1,index2,…], $sortByIndexFirstQ, $indexAscendingQ,
    $lengthAscendingQ) returns the indexes sorted. The rest of the
    parameters are booleans specifying the sorting criterions application
    order and directions.

    The indexes are sorted using two criterions: (1) index number sequence
    from left to right. (2) the length of the indexes.

    sortByIndexFirstQ controls which criterion will be used first. The other
    two arguments indexAscendingQ, lengthAscendingQ controls the ascending
    or decending direction for each criterion. The three booleans forms a
    total of 8 possible ways of ordering. Any number of the booleans can be
    omitted. User specified booleans will replace the defaults (0, 1, 1)
    from the left.

    Example:

    IndexSetSort([[0], [1, 0], [1, 1, 0], [1, 1, 1], [1, 1, 2], [1, 1], [1,
    2, 0], [1, 2, 1], [1, 2, 2], [1, 2], [1], [2, 0], [2, 1, 0], [2, 1, 1],
    [2, 1, 2], [2, 1], [2, 2, 0], [2, 2, 1], [2, 2, 2], [2, 2], [2]], 0, 1,
    1);

    Depending on the last three arguments, it returns one of the following:

    #(0,0,0) #sort by (depth decending, then index decending).
    #[[2,2,2],[2,2,1],[2,2,0],[2,1,2],[2,1,1],[2,1,0],[1,2,2],[1,2,1],[1,2,0
    ],[1,1,2],[1,1,1],[1,1,0],[2,2],[2,1],[2,0],[1,2],[1,1],[1,0],[2],[1],[0
    ]];

    #(0,0,1) #sort by (depth ascending, then index decending).
    #[[2],[1],[0],[2,2],[2,1],[2,0],[1,2],[1,1],[1,0],[2,2,2],[2,2,1],[2,2,0
    ],[2,1,2],[2,1,1],[2,1,0],[1,2,2],[1,2,1],[1,2,0],[1,1,2],[1,1,1],[1,1,0
    ]];

    #(0,1,0) #sort by (depth decending, then index ascending).
    #[[1,1,0],[1,1,1],[1,1,2],[1,2,0],[1,2,1],[1,2,2],[2,1,0],[2,1,1],[2,1,2
    ],[2,2,0],[2,2,1],[2,2,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2],[0],[1],[2
    ]];

    #(0,1,1) #sort by (depth ascending, then index ascending). (Common)
    #[[0],[1],[2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2],[1,1,0],[1,1,1],[1,1,2
    ],[1,2,0],[1,2,1],[1,2,2],[2,1,0],[2,1,1],[2,1,2],[2,2,0],[2,2,1],[2,2,2
    ]];

    #(1,0,0) #sort by (index decending, then depth decending).
    #[[2,2,2],[2,2,1],[2,2,0],[2,2],[2,1,2],[2,1,1],[2,1,0],[2,1],[2,0],[2],
    [1,2,2],[1,2,1],[1,2,0],[1,2],[1,1,2],[1,1,1],[1,1,0],[1,1],[1,0],[1],[0
    ]];

    #(1,0,1) #sort by (index decending, then depth ascending).
    #[[2],[2,2],[2,2,2],[2,2,1],[2,2,0],[2,1],[2,1,2],[2,1,1],[2,1,0],[2,0],
    [1],[1,2],[1,2,2],[1,2,1],[1,2,0],[1,1],[1,1,2],[1,1,1],[1,1,0],[1,0],[0
    ]];

    #(1,1,0) #Sort by (index ascending, then depth decending): (Common)
    #[[0],[1,0],[1,1,0],[1,1,1],[1,1,2],[1,1],[1,2,0],[1,2,1],[1,2,2],[1,2],
    [1],[2,0],[2,1,0],[2,1,1],[2,1,2],[2,1],[2,2,0],[2,2,1],[2,2,2],[2,2],[2
    ]];

    #(1,1,1) #Sort by (index ascending, then depth ascending): (Common)
    #[[0],[1],[1,0],[1,1],[1,1,0],[1,1,1],[1,1,2],[1,2],[1,2,0],[1,2,1],[1,2
    ,2],[2],[2,0],[2,1],[2,1,0],[2,1,1],[2,1,2],[2,2],[2,2,0],[2,2,1],[2,2,2
    ]];

    TreeToIndexSet

    TreeToIndexSet(tree) returns a list of all atoms (leaves) and their
    positions that represents the tree completely. The return value consists
    of pairs of position indexes and corresponding atoms.

    The input tree must have the form [[…],…] where an atomic element is
    anything that is not a reference to an array. The return value is a
    reference to an array, of the form [[positionIndex1,
    atom1],[positionIndex2,atom2],…], where each positionIndex has the
    form [n1,n2,…].

    Unimplemented extension: TreeToIndexSet(tree,levelSpec) returns the
    indexes and corresponding subexpression at levspec. xxxxx

    Related: xxxxx IndexSetToExpression.

    Example:

     TreeToIndexSet( [0,1,2,3] );
     # returns [[[0],0],[[1],1],[[2],2],[[3],3]]

     TreeToIndexSet( [[3,4],'b',[[7,8],'love']] );
     # returns [[[0,0],3],[[0,1],4],[[1],'b'],[[2,0,0],7],[[2,0,1],8],[[2,1],'love']]

     TreeToIndexSet( [[[1,1],[1,2]],[[2,1],[2,2]],[[3,1],[3,2]]] );
     # returns:  [[[0,0,0],1],[[0,0,1],1],[[0,1,0],1],[[0,1,1],2],
     #            [[1,0,0],2],[[1,0,1],1],[[1,1,0],2],[[1,1,1],2],
     #            [[2,0,0],3],[[2,0,1],1],[[2,1,0],3],[[2,1,1],2]]

     # hash references can also serve as atoms, but not recommended.
     TreeToIndexSet ( [[3,4],[{'key1' => 1,'key2' => 2}, 5]] )
     # returns: [[[0,0],3],[[0,1],4],[[1,0],{'key1' => 1,'key2' => 2}],[[1,1],5]]

    IndexSetToTree

    IndexSetToTree(positionIndexSetWithAtoms) returns a reference to a
    nested list specified by positionIndexSetWithAtoms.

    positionIndexSetWithAtoms is of the form [[positionIndex1,
    atom1],[positionIndex2,atom2],…] where a positionIndex has the form
    [n1,n2,…] and an atom is either string or number. The return value is
    a reference to a nested list, i.e. [[[…],…],…].

    IndexSetToTree( TreeToIndexSet( args)) returns the args unchanged.

    Related: TreeToIndexSet.

    Example:

     IndexSetToTree( [[[0],0],[[1],1],[[2],2],[[3],3]] );
     # returns [0,1,2,3]

     IndexSetToTree( [[[0,0],3],[[0,1],4],[[1],'b'],[[2,0,0],7],[[2,0,1],8],[[2,1],'love']] );
     # returns [[3,4],'b',[[7,8],'love']]

     IndexSetToTree(
      [[[0,0,0],1],[[0,0,1],1],[[0,1,0],1],
       [[0,1,1],2],[[1,0,0],2],[[1,0,1],1],
       [[1,1,0],2],[[1,1,1],2],[[2,0,0],3],
       [[2,0,1],1],[[2,1,0],3],[[2,1,1],2]] );
     # returns: [[[1,1],[1,2]],[[2,1],[2,2]],[[3,1],[3,2]]]

     # hash references do not work well as atoms.
     IndexSetToTree ( [[[0,0],3],[[0,1],4],[[1,0],{'key1' => 1,'key2' => 2}],[[1,1],5]] )
     # returns: [[3,4],['HASH(0x256dea4)', 5]]

AUTHOR

 Xah Lee, (xah@xahlee.org)
 http://xahlee.org/

This module is created on 1998/10.

This package is written with the help of comp.lang.perl.* newsgroups. In particular, the following people have contributed around 1998 to 1999 (not ordered): David Alan Black (dblack@@email.njin.net), Larry Rosler (lr@@hpl.hp.com), John Porter (jdporter@@min.net), Rick Delaney (rick.delaney@@shaw.wave.ca).

Copyright 1998 to 2005 by Xah Lee. This software is licensed under the GNU Public License. The license is available at http://www.gnu.org/copyleft/gpl.html

Disclaimer: Mathematica is a trademark and product of Wolfram Research Incorporated. The Perl module Matica.pm is not affiliated by Wolfram Research Inc.

2005-05