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 does 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