[comment {-*- tcl -*- doctools manpage}]
[comment {$Id: struct_list.man 380667 2003-04-15 17:44:51Z jigen $}]
[manpage_begin list n 1.2.2]
[copyright {2003 by Kevin B. Kenny. All rights reserved}]
[moddesc {Tcl Data Structures}]
[titledesc {Procedures for manipulating lists}]
[require Tcl 8.0]
[require struct [opt 1.3]]
[description]

[para]

The [cmd ::struct::list] namespace contains several useful commands
for processing Tcl lists. Generally speaking, they implement
algorithms more complex or specialized than the ones provided by Tcl
itself.

[para]

It exports only a single command, [cmd struct::list]. All
functionality provided here can be reached through a subcommand of
this command.

[section COMMANDS]
[list_begin definitions]

[call [cmd ::struct::list] [method longestCommonSubsequence] \
	[arg sequence1] [arg sequence2] [opt [arg maxOccurs]]]

Returns the longest common subsequence of elements in the two lists
[arg sequence1] and [arg sequence2]. If the [arg maxOccurs] parameter
is provided, the common subsequence is restricted to elements that
occur no more than [arg maxOccurs] times in [arg sequence2].

[nl]

The return value is a list of two lists of equal length. The first
sublist is of indices into [arg sequence1], and the second sublist is
of indices into [arg sequence2].  Each corresponding pair of indices
corresponds to equal elements in the sequences; the sequence returned
is the longest possible.

[call [cmd ::struct::list] [method longestCommonSubsequence2] \
	[arg {sequence1 sequence2}] [opt [arg maxOccurs]]]

Returns an approximation to the longest common sequence of elements in
the two lists [arg sequence1] and [arg sequence2].

If the [arg maxOccurs] parameter is omitted, the subsequence computed
is exactly the longest common subsequence; otherwise, the longest
common subsequence is approximated by first determining the longest
common sequence of only those elements that occur no more than

[arg maxOccurs] times in [arg sequence2], and then using that result
to align the two lists, determining the longest common subsequences of
the sublists between the two elements.

[nl]

As with [method longestCommonSubsequence], the return value is a list
of two lists of equal length.  The first sublist is of indices into
[arg sequence1], and the second sublist is of indices into

[arg sequence2].  Each corresponding pair of indices corresponds to
equal elements in the sequences.  The sequence approximates the
longest common subsequence.


[call [cmd ::struct::list] [method lcsInvert] [arg lcsData] [arg len1] [arg len2]]

This command takes a description of a longest common subsequence

([arg lcsData]), inverts it, and returns the result. Inversion means
here that as the input describes which parts of the two sequences are
identical the output describes the differences instead.

[nl]

To be fully defined the lengths of the two sequences have to be known
and are specified through [arg len1] and [arg len2].

[nl]

The result is a list where each element describes one chunk of the
differences between the two sequences. This description is a list
containing three elements, a type and two pairs of indices into

[arg sequence1] and [arg sequence2] respectively, in this order.

The type can be one of three values:

[list_begin definitions]
[lst_item [const added]]

Describes an addition. I.e. items which are missing in [arg sequence1]
can be found in [arg sequence2].

The pair of indices into [arg sequence1] describes where the added
range had been expected to be in [arg sequence1]. The first index
refers to the item just before the added range, and the second index
refers to the item just after the added range.

The pair of indices into [arg sequence2] describes the range of items
which has been added to it. The first index refers to the first item
in the range, and the second index refers to the last item in the
range.

[lst_item [const deleted]]

Describes a deletion. I.e. items which are in [arg sequence1] are
missing from [arg sequence2].

The pair of indices into [arg sequence1] describes the range of items
which has been deleted. The first index refers to the first item in
the range, and the second index refers to the last item in the range.

The pair of indices into [arg sequence2] describes where the deleted
range had been expected to be in [arg sequence2]. The first index
refers to the item just before the deleted range, and the second index
refers to the item just after the deleted range.

[lst_item [const changed]]

Describes a general change. I.e a range of items in [arg sequence1]
has been replaced by a different range of items in [arg sequence2].

The pair of indices into [arg sequence1] describes the range of items
which has been replaced. The first index refers to the first item in
the range, and the second index refers to the last item in the range.

The pair of indices into [arg sequence2] describes the range of items
replacing the original range. Again the first index refers to the
first item in the range, and the second index refers to the last item
in the range.

[list_end]

[nl]
[example {
    sequence 1 = {a b r a c a d a b r a}
    lcs 1      =   {1 2   4 5     8 9 10}
    lcs 2      =   {0 1   3 4     5 6 7}
    sequence 2 =   {b r i c a     b r a c}

    Inversion  = {{deleted  {0  0} {-1 0}}
                  {changed  {3  3}  {2 2}}
                  {deleted  {6  7}  {4 5}}
                  {added   {10 11}  {8 8}}}
}]

[emph Notes:]
[nl]
[list_begin bullet]
[bullet]
An index of [const -1] in a [term deleted] chunk refers to just before
the first element of the second sequence.

[bullet]
Also an index equal to the length of the first sequence in an
[term added] chunk refers to just behind the end of the sequence.

[list_end]


[call [cmd ::struct::list] [method lcsInvert2] [arg lcs1] [arg lcs2] [arg len1] [arg len2]]

Similar to [method lcsInvert]. Instead of directly taking the result
of a call to [method longestCommonSubsequence] this subcommand expects
the indices for the two sequences in two separate lists.


[call [cmd ::struct::list] [method lcsInvertMerge] [arg lcsData] [arg len1] [arg len2]]

Similar to [method lcsInvert]. It returns essentially the same
structure as that command, except that it may contain chunks of type
[const unchanged] too.

[nl]

These new chunks describe the parts which are unchanged between the
two sequences. This means that the result of this command describes
both the changed and unchanged parts of the two sequences in one
structure.

[nl]
[example {
    sequence 1 = {a b r a c a d a b r a}
    lcs 1      =   {1 2   4 5     8 9 10}
    lcs 2      =   {0 1   3 4     5 6 7}
    sequence 2 =   {b r i c a     b r a c}

    Inversion/Merge  = {{deleted   {0  0} {-1 0}}
                        {unchanged {1  2}  {0 1}}
                        {changed   {3  3}  {2 2}}
                        {unchanged {4  5}  {3 4}}
                        {deleted   {6  7}  {4 5}}
                        {unchanged {8 10}  {5 7}}
                        {added    {10 11}  {8 8}}}
}]


[call [cmd ::struct::list] [method lcsInvertMerge2] [arg lcs1] [arg lcs2] [arg len1] [arg len2]]

Similar to [method lcsInvertMerge]. Instead of directly taking the
result of a call to [method longestCommonSubsequence] this subcommand
expects the indices for the two sequences in two separate lists.



[call [cmd ::struct::list] [method reverse] [arg sequence]]

The subcommand takes a single [arg sequence] as argument and returns a new
sequence containing the elements of the input sequence in reverse
order.


[call [cmd ::struct::list] [method assign] [arg sequence] [opt [arg varname]]...]

The subcommand assigns the first [var n] elements of the input

[arg sequence] to the zero or more variables whose names were listed
after the sequence, where [var n] is the number of specified
variables.

[nl]

If there are more variables specified than there are elements in the
[arg sequence] the empty string will be assigned to the superfluous
variables.

[nl]

If there are more elements in the [arg sequence] than variable names
specified the subcommand returns a list containing the unassigned
elements. Else an empty list is returned.

[example {
    tclsh> ::struct::list assign {a b c d e} foo bar
    c d e
    tclsh> set foo
    a
    tclsh> set bar
    b
}]


[call [cmd ::struct::list] [method flatten] [opt [option -full]] [opt [option --]] [arg sequence]]

The subcommand takes a single [arg sequence] and returns a new
sequence where one level of nesting was removed from the input
sequence. In other words, the sublists in the input sequence are
replaced by their elements.

[nl]

The subcommand will remove any nesting it finds if the option
[option -full] is specified.

[example {
    tclsh> ::struct::list flatten {1 2 3 {4 5} {6 7} {{8 9}} 10}
    1 2 3 4 5 6 7 {8 9} 10
    tclsh> ::struct::list flatten -full {1 2 3 {4 5} {6 7} {{8 9}} 10}
    1 2 3 4 5 6 7 8 9 10
}]


[call [cmd ::struct::list] [method map] [arg sequence] [arg cmdprefix]]

The subcommand takes a [arg sequence] to operate on and a command
prefix ([arg cmdprefix]) specifying an operation, applies the command
prefix to each element of the sequence and returns a sequence
consisting of the results of that application.

[nl]

The command prefix will be evaluated with a single word appended to
it. The evaluation takes place in the context of the caller of the
subcommand.

[nl]

[example {
    tclsh> # squaring all elements in a list

    tclsh> proc sqr {x} {expr {$x*$x}}
    tclsh> ::struct::list map {1 2 3 4 5} sqr
    1 4 9 16 25

    tclsh> # Retrieving the second column from a matrix
    tclsh> # given as list of lists.

    tclsh> proc projection {n list} {::lindex $list $n}
    tclsh> ::struct::list map {{a b c} {1 2 3} {d f g}} {projection 1}
    b 2 f
}]


[call [cmd ::struct::list] [method fold] [arg sequence] [arg initialvalue] [arg cmdprefix]]

The subcommand takes a [arg sequence] to operate on, an arbitrary
string [arg {initial value}] and a command prefix ([arg cmdprefix])
specifying an operation.

[nl]

The command prefix will be evaluated with two words appended to
it. The second of these words will always be an element of the
sequence. The evaluation takes place in the context of the caller of
the subcommand.

[nl]

It then reduces the sequence into a single value through repeated
application of the command prefix and returns that value. This
reduction is done by

[list_begin definitions]
[lst_item [const 1]]

Application of the command to the initial value and the first element
of the list.

[lst_item [const 2]]

Application of the command to the result of the last call and the
second element of the list.

[lst_item [const ...]]
[lst_item [const i]]

Application of the command to the result of the last call and the
[var i]'th element of the list.

[lst_item [const ...]]
[lst_item [const end]]

Application of the command to the result of the last call and the last
element of the list. The result of this call is returned as the result
of the subcommand.

[list_end]
[nl]
[example {
    tclsh> # summing the elements in a list.
    tclsh> proc + {a b} {expr {$a + $b}}
    tclsh> ::listx fold {1 2 3 4 5} 0 +
    15
}]

[call [cmd ::struct::list] [method iota] [arg n]]

The subcommand returns a list containing the integer numbers
in the range [const {[0,n)}]. The element at index [var i]
of the list contain the number [const i].

[nl]

For "[arg n] == [const 0]" an empty list will be returned.


[call [cmd ::struct::list] [method equal] [arg a] [arg b]]

The subcommand compares the two lists [arg a] and [arg b] for
equality. In other words, they have to be of the same length and have
to contain the same elements in the same order. If an element is a
list the same definition of equality applies recursively.

[nl]

A boolean vlaue will be returned as the result of the command.
This value will be [const true] if the two lists are equal, and
[const false] else.


[call [cmd ::struct::list] [method repeat] [arg value] [arg size]...]

The subcommand creates a (nested) list containing the [arg value] in
all positions. The exact size and degree of nesting is determined by
the [arg size] arguments, all of which have to be integer numbers
greater than or equal to zero.

[nl]

A single argument [arg size] which is a list of more than one element
will be treated as if more than argument [arg size] was specified.

[nl]

If only one argument [arg size] is present the returned list will not
be nested, of length [arg size] and contain [arg value] in all
positions.

If more than one [arg size] argument is present the returned
list will be nested, and of the length specified by the last
[arg size] argument given to it. The elements of that list
are defined as the result of [cmd Repeat] for the same arguments,
but with the last [arg size] value removed.

[nl]

An empty list will be returned if no [arg size] arguments are present.

[nl]
[example {
    tclsh> lrepeat  0 3 4
    {0 0 0} {0 0 0} {0 0 0} {0 0 0}
    tclsh> lrepeat  0 {3 4}
    {0 0 0} {0 0 0} {0 0 0} {0 0 0}
    tclsh> lrepeat  0 {3 4 5}
    {{0 0 0} {0 0 0} {0 0 0} {0 0 0}} {{0 0 0} {0 0 0} {0 0 0} {0 0 0}} {{0 0 0} {0 0 0} {0 0 0} {0 0 0}} {{0 0 0} {0 0 0} {0 0 0} {0 0 0}} {{0 0 0} {0 0 0} {0 0 0} {0 0 0}}
}]


[list_end]

[section {LONGEST COMMON SUBSEQUENCE AND FILE COMPARISON}]

[para]

The [method longestCommonSubsequence] subcommand forms the core of a
flexible system for doing differential comparisons of files, similar
to the capability offered by the Unix command [syscmd diff].

While this procedure is quite rapid for many tasks of file comparison,
its performance degrades severely if [arg sequence2] contains many
equal elements (as, for instance, when using this procedure to compare
two files, a quarter of whose lines are blank.  This drawback is
intrinsic to the algorithm used (see the Reference for details).

[para]

One approach to dealing with the performance problem that is sometimes
effective in practice is arbitrarily to exclude elements that appear
more than a certain number of times. 

This number is provided as the [arg maxOccurs] parameter.  If frequent
lines are excluded in this manner, they will not appear in the common
subsequence that is computed; the result will be the longest common
subsequence of infrequent elements.

The procedure [method longestCommonSubsequence2] implements this
heuristic.

It functions as a wrapper around [method longestCommonSubsequence]; it
computes the longest common subsequence of infrequent elements, and
then subdivides the subsequences that lie between the matches to
approximate the true longest common subsequence.

[section REFERENCES]

J. W. Hunt and M. D. McIlroy, "An algorithm for differential 
file comparison," Comp. Sci. Tech. Rep. #41, Bell Telephone 
Laboratories (1976). Available on the Web at the second
author's personal site: [uri http://www.cs.dartmouth.edu/~doug/]

[keywords list diff differential comparison common subsequence]
[keywords {longest common subsequence}]
[keywords reverse]
[keywords assign]
[keywords flatten]
[keywords map]
[keywords folding reduce]
[keywords equality equal repetition repeating]
[manpage_end]
