'\"
'\" Generated from file 'struct_list\&.man' by tcllib/doctools with format 'nroff'
'\" Copyright (c) 2003-2005 by Kevin B\&. Kenny\&. All rights reserved
'\" Copyright (c) 2003-2012 Andreas Kupries <andreas_kupries@users\&.sourceforge\&.net>
'\"
.TH "struct::list" n 1\&.9 tcllib "Tcl Data Structures"
.\" The -*- nroff -*- definitions below are for supplemental macros used
.\" in Tcl/Tk manual entries.
.\"
.\" .AP type name in/out ?indent?
.\"	Start paragraph describing an argument to a library procedure.
.\"	type is type of argument (int, etc.), in/out is either "in", "out",
.\"	or "in/out" to describe whether procedure reads or modifies arg,
.\"	and indent is equivalent to second arg of .IP (shouldn't ever be
.\"	needed;  use .AS below instead)
.\"
.\" .AS ?type? ?name?
.\"	Give maximum sizes of arguments for setting tab stops.  Type and
.\"	name are examples of largest possible arguments that will be passed
.\"	to .AP later.  If args are omitted, default tab stops are used.
.\"
.\" .BS
.\"	Start box enclosure.  From here until next .BE, everything will be
.\"	enclosed in one large box.
.\"
.\" .BE
.\"	End of box enclosure.
.\"
.\" .CS
.\"	Begin code excerpt.
.\"
.\" .CE
.\"	End code excerpt.
.\"
.\" .VS ?version? ?br?
.\"	Begin vertical sidebar, for use in marking newly-changed parts
.\"	of man pages.  The first argument is ignored and used for recording
.\"	the version when the .VS was added, so that the sidebars can be
.\"	found and removed when they reach a certain age.  If another argument
.\"	is present, then a line break is forced before starting the sidebar.
.\"
.\" .VE
.\"	End of vertical sidebar.
.\"
.\" .DS
.\"	Begin an indented unfilled display.
.\"
.\" .DE
.\"	End of indented unfilled display.
.\"
.\" .SO ?manpage?
.\"	Start of list of standard options for a Tk widget. The manpage
.\"	argument defines where to look up the standard options; if
.\"	omitted, defaults to "options". The options follow on successive
.\"	lines, in three columns separated by tabs.
.\"
.\" .SE
.\"	End of list of standard options for a Tk widget.
.\"
.\" .OP cmdName dbName dbClass
.\"	Start of description of a specific option.  cmdName gives the
.\"	option's name as specified in the class command, dbName gives
.\"	the option's name in the option database, and dbClass gives
.\"	the option's class in the option database.
.\"
.\" .UL arg1 arg2
.\"	Print arg1 underlined, then print arg2 normally.
.\"
.\" .QW arg1 ?arg2?
.\"	Print arg1 in quotes, then arg2 normally (for trailing punctuation).
.\"
.\" .PQ arg1 ?arg2?
.\"	Print an open parenthesis, arg1 in quotes, then arg2 normally
.\"	(for trailing punctuation) and then a closing parenthesis.
.\"
.\"	# Set up traps and other miscellaneous stuff for Tcl/Tk man pages.
.if t .wh -1.3i ^B
.nr ^l \n(.l
.ad b
.\"	# Start an argument description
.de AP
.ie !"\\$4"" .TP \\$4
.el \{\
.   ie !"\\$2"" .TP \\n()Cu
.   el          .TP 15
.\}
.ta \\n()Au \\n()Bu
.ie !"\\$3"" \{\
\&\\$1 \\fI\\$2\\fP (\\$3)
.\".b
.\}
.el \{\
.br
.ie !"\\$2"" \{\
\&\\$1	\\fI\\$2\\fP
.\}
.el \{\
\&\\fI\\$1\\fP
.\}
.\}
..
.\"	# define tabbing values for .AP
.de AS
.nr )A 10n
.if !"\\$1"" .nr )A \\w'\\$1'u+3n
.nr )B \\n()Au+15n
.\"
.if !"\\$2"" .nr )B \\w'\\$2'u+\\n()Au+3n
.nr )C \\n()Bu+\\w'(in/out)'u+2n
..
.AS Tcl_Interp Tcl_CreateInterp in/out
.\"	# BS - start boxed text
.\"	# ^y = starting y location
.\"	# ^b = 1
.de BS
.br
.mk ^y
.nr ^b 1u
.if n .nf
.if n .ti 0
.if n \l'\\n(.lu\(ul'
.if n .fi
..
.\"	# BE - end boxed text (draw box now)
.de BE
.nf
.ti 0
.mk ^t
.ie n \l'\\n(^lu\(ul'
.el \{\
.\"	Draw four-sided box normally, but don't draw top of
.\"	box if the box started on an earlier page.
.ie !\\n(^b-1 \{\
\h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.el \}\
\h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.\}
.fi
.br
.nr ^b 0
..
.\"	# VS - start vertical sidebar
.\"	# ^Y = starting y location
.\"	# ^v = 1 (for troff;  for nroff this doesn't matter)
.de VS
.if !"\\$2"" .br
.mk ^Y
.ie n 'mc \s12\(br\s0
.el .nr ^v 1u
..
.\"	# VE - end of vertical sidebar
.de VE
.ie n 'mc
.el \{\
.ev 2
.nf
.ti 0
.mk ^t
\h'|\\n(^lu+3n'\L'|\\n(^Yu-1v\(bv'\v'\\n(^tu+1v-\\n(^Yu'\h'-|\\n(^lu+3n'
.sp -1
.fi
.ev
.\}
.nr ^v 0
..
.\"	# Special macro to handle page bottom:  finish off current
.\"	# box/sidebar if in box/sidebar mode, then invoked standard
.\"	# page bottom macro.
.de ^B
.ev 2
'ti 0
'nf
.mk ^t
.if \\n(^b \{\
.\"	Draw three-sided box if this is the box's first page,
.\"	draw two sides but no top otherwise.
.ie !\\n(^b-1 \h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.el \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.\}
.if \\n(^v \{\
.nr ^x \\n(^tu+1v-\\n(^Yu
\kx\h'-\\nxu'\h'|\\n(^lu+3n'\ky\L'-\\n(^xu'\v'\\n(^xu'\h'|0u'\c
.\}
.bp
'fi
.ev
.if \\n(^b \{\
.mk ^y
.nr ^b 2
.\}
.if \\n(^v \{\
.mk ^Y
.\}
..
.\"	# DS - begin display
.de DS
.RS
.nf
.sp
..
.\"	# DE - end display
.de DE
.fi
.RE
.sp
..
.\"	# SO - start of list of standard options
.de SO
'ie '\\$1'' .ds So \\fBoptions\\fR
'el .ds So \\fB\\$1\\fR
.SH "STANDARD OPTIONS"
.LP
.nf
.ta 5.5c 11c
.ft B
..
.\"	# SE - end of list of standard options
.de SE
.fi
.ft R
.LP
See the \\*(So manual entry for details on the standard options.
..
.\"	# OP - start of full description for a single option
.de OP
.LP
.nf
.ta 4c
Command-Line Name:	\\fB\\$1\\fR
Database Name:	\\fB\\$2\\fR
Database Class:	\\fB\\$3\\fR
.fi
.IP
..
.\"	# CS - begin code excerpt
.de CS
.RS
.nf
.ta .25i .5i .75i 1i
..
.\"	# CE - end code excerpt
.de CE
.fi
.RE
..
.\"	# UL - underline word
.de UL
\\$1\l'|0\(ul'\\$2
..
.\"	# QW - apply quotation marks to word
.de QW
.ie '\\*(lq'"' ``\\$1''\\$2
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\$2
..
.\"	# PQ - apply parens and quotation marks to word
.de PQ
.ie '\\*(lq'"' (``\\$1''\\$2)\\$3
.\"" fix emacs highlighting
.el (\\*(lq\\$1\\*(rq\\$2)\\$3
..
.\"	# QR - quoted range
.de QR
.ie '\\*(lq'"' ``\\$1''\\-``\\$2''\\$3
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\-\\*(lq\\$2\\*(rq\\$3
..
.\"	# MT - "empty" string
.de MT
.QW ""
..
.BS
.SH NAME
struct::list \- Procedures for manipulating lists
.SH SYNOPSIS
package require \fBTcl 8\&.5 9\fR
.sp
package require \fBstruct::list ?1\&.9?\fR
.sp
\fB::struct::list\fR \fBlongestCommonSubsequence\fR \fIsequence1\fR \fIsequence2\fR ?\fImaxOccurs\fR?
.sp
\fB::struct::list\fR \fBlongestCommonSubsequence2\fR \fIsequence1 sequence2\fR ?\fImaxOccurs\fR?
.sp
\fB::struct::list\fR \fBlcsInvert\fR \fIlcsData\fR \fIlen1\fR \fIlen2\fR
.sp
\fB::struct::list\fR \fBlcsInvert2\fR \fIlcs1\fR \fIlcs2\fR \fIlen1\fR \fIlen2\fR
.sp
\fB::struct::list\fR \fBlcsInvertMerge\fR \fIlcsData\fR \fIlen1\fR \fIlen2\fR
.sp
\fB::struct::list\fR \fBlcsInvertMerge2\fR \fIlcs1\fR \fIlcs2\fR \fIlen1\fR \fIlen2\fR
.sp
\fB::struct::list\fR \fBreverse\fR \fIsequence\fR
.sp
\fB::struct::list\fR \fBshuffle\fR \fIlist\fR
.sp
\fB::struct::list\fR \fBassign\fR \fIsequence\fR \fIvarname\fR ?\fIvarname\fR?\&.\&.\&.
.sp
\fB::struct::list\fR \fBflatten\fR ?\fB-full\fR? ?\fB--\fR? \fIsequence\fR
.sp
\fB::struct::list\fR \fBmap\fR \fIsequence\fR \fIcmdprefix\fR
.sp
\fB::struct::list\fR \fBmapfor\fR \fIvar\fR \fIsequence\fR \fIscript\fR
.sp
\fB::struct::list\fR \fBfilter\fR \fIsequence\fR \fIcmdprefix\fR
.sp
\fB::struct::list\fR \fBfilterfor\fR \fIvar\fR \fIsequence\fR \fIexpr\fR
.sp
\fB::struct::list\fR \fBsplit\fR \fIsequence\fR \fIcmdprefix\fR ?\fIpassVar\fR \fIfailVar\fR?
.sp
\fB::struct::list\fR \fBfold\fR \fIsequence\fR \fIinitialvalue\fR \fIcmdprefix\fR
.sp
\fB::struct::list\fR \fBshift\fR \fIlistvar\fR
.sp
\fB::struct::list\fR \fBiota\fR \fIn\fR
.sp
\fB::struct::list\fR \fBequal\fR ?\fB-simple\fR? ?\fB--\fR? \fIa\fR \fIb\fR
.sp
\fB::struct::list\fR \fBrepeat\fR \fIsize\fR \fIelement1\fR ?\fIelement2\fR \fIelement3\fR\&.\&.\&.?
.sp
\fB::struct::list\fR \fBrepeatn\fR \fIvalue\fR \fIsize\fR\&.\&.\&.
.sp
\fB::struct::list\fR \fBdbJoin\fR ?\fB-inner\fR|\fB-left\fR|\fB-right\fR|\fB-full\fR? ?\fB-keys\fR \fIvarname\fR? {\fIkeycol\fR \fItable\fR}\&.\&.\&.
.sp
\fB::struct::list\fR \fBdbJoinKeyed\fR ?\fB-inner\fR|\fB-left\fR|\fB-right\fR|\fB-full\fR? ?\fB-keys\fR \fIvarname\fR? \fItable\fR\&.\&.\&.
.sp
\fB::struct::list\fR \fBswap\fR \fIlistvar\fR \fIi\fR \fIj\fR
.sp
\fB::struct::list\fR \fBfirstperm\fR \fIlist\fR
.sp
\fB::struct::list\fR \fBnextperm\fR \fIperm\fR
.sp
\fB::struct::list\fR \fBpermutations\fR \fIlist\fR
.sp
\fB::struct::list\fR \fBforeachperm\fR \fIvar\fR \fIlist\fR \fIbody\fR
.sp
.BE
.SH DESCRIPTION
.PP
The \fB::struct::list\fR 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\&.
.PP
It exports only a single command, \fBstruct::list\fR\&. All
functionality provided here can be reached through a subcommand of
this command\&.
.SH COMMANDS
.TP
\fB::struct::list\fR \fBlongestCommonSubsequence\fR \fIsequence1\fR \fIsequence2\fR ?\fImaxOccurs\fR?
Returns a list of indices into \fIsequence1\fR and a corresponding list where
each item is an index into \fIsequence2\fR of the matching value according to the
longest common subsequences algorithm\&.  If \fImaxOccurs\fR is provided, the
common subsequence is restricted to elements that occur no more than
\fImaxOccurs\fR times in \fIsequence2\fR\&.
.sp
.TP
\fB::struct::list\fR \fBlongestCommonSubsequence2\fR \fIsequence1 sequence2\fR ?\fImaxOccurs\fR?
Returns the longest common subsequence of elements in
the two lists \fIsequence1\fR and \fIsequence2\fR\&.
If \fImaxOccurs\fR is provided, the result is only an
approximation, where the longest common subsequence is approximated by first
determining the longest common sequence of only those elements that occur no
more than
\fImaxOccurs\fR times in \fIsequence2\fR, and then using that result
to align the two lists, determining the longest common subsequences of
the sublists between the two elements\&.
.sp
The result is the same as for \fBlongestCommonSubsequence\fR\&.
.TP
\fB::struct::list\fR \fBlcsInvert\fR \fIlcsData\fR \fIlen1\fR \fIlen2\fR
Takes a description of a longest common subsequence
(\fIlcsData\fR), 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\&.
.sp
To be fully defined the lengths of the two sequences have to be known
and are specified through \fIlen1\fR and \fIlen2\fR\&.
.sp
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
\fIsequence1\fR and \fIsequence2\fR respectively, in this order\&.
The type can be one of three values:
.RS
.TP
\fBadded\fR
Describes an addition\&. I\&.e\&. items which are missing in \fIsequence1\fR
can be found in \fIsequence2\fR\&.
The pair of indices into \fIsequence1\fR describes where the added
range had been expected to be in \fIsequence1\fR\&. 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 \fIsequence2\fR 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\&.
.TP
\fBdeleted\fR
Describes a deletion\&. I\&.e\&. items which are in \fIsequence1\fR are
missing from \fIsequence2\fR\&.
The pair of indices into \fIsequence1\fR 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 \fIsequence2\fR describes where the deleted
range had been expected to be in \fIsequence2\fR\&. 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\&.
.TP
\fBchanged\fR
Describes a general change\&. I\&.e a range of items in \fIsequence1\fR
has been replaced by a different range of items in \fIsequence2\fR\&.
The pair of indices into \fIsequence1\fR 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 \fIsequence2\fR 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\&.
.RE
.sp
.CS


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

.CE
.IP
\fINotes:\fR
.sp
.RS
.IP \(bu
An index of \fB-1\fR in a \fIdeleted\fR chunk refers to just before
the first element of the second sequence\&.
.IP \(bu
Also an index equal to the length of the first sequence in an
\fIadded\fR chunk refers to just behind the end of the sequence\&.
.RE
.TP
\fB::struct::list\fR \fBlcsInvert2\fR \fIlcs1\fR \fIlcs2\fR \fIlen1\fR \fIlen2\fR
Similar to \fBlcsInvert\fR\&. Instead of directly taking the result
of a call to \fBlongestCommonSubsequence\fR this subcommand expects
the indices for the two sequences in two separate lists\&.
.TP
\fB::struct::list\fR \fBlcsInvertMerge\fR \fIlcsData\fR \fIlen1\fR \fIlen2\fR
Similar to \fBlcsInvert\fR\&. It returns essentially the same
structure as that command, except that it may contain chunks of type
\fBunchanged\fR too\&.
.sp
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\&.
.sp
.CS


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

.CE
.TP
\fB::struct::list\fR \fBlcsInvertMerge2\fR \fIlcs1\fR \fIlcs2\fR \fIlen1\fR \fIlen2\fR
Similar to \fBlcsInvertMerge\fR\&. Instead of directly taking the
result of a call to \fBlongestCommonSubsequence\fR this subcommand
expects the indices for the two sequences in two separate lists\&.
.TP
\fB::struct::list\fR \fBreverse\fR \fIsequence\fR
The subcommand takes a single \fIsequence\fR as argument and returns a new
sequence containing the elements of the input sequence in reverse
order\&.
.TP
\fB::struct::list\fR \fBshuffle\fR \fIlist\fR
The subcommand takes a \fIlist\fR and returns a copy of that list
with the elements it contains in random order\&. Every possible
ordering of elements is equally likely to be generated\&. The
Fisher-Yates shuffling algorithm is used internally\&.
.TP
\fB::struct::list\fR \fBassign\fR \fIsequence\fR \fIvarname\fR ?\fIvarname\fR?\&.\&.\&.
The subcommand assigns the first \fBn\fR elements of the input
\fIsequence\fR to the one or more variables whose names were listed
after the sequence, where \fBn\fR is the number of specified
variables\&.
.sp
If there are more variables specified than there are elements in the
\fIsequence\fR the empty string will be assigned to the superfluous
variables\&.
.sp
If there are more elements in the \fIsequence\fR than variable names
specified the subcommand returns a list containing the unassigned
elements\&. Else an empty list is returned\&.
.CS


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

.CE
.TP
\fB::struct::list\fR \fBflatten\fR ?\fB-full\fR? ?\fB--\fR? \fIsequence\fR
The subcommand takes a single \fIsequence\fR 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\&.
.sp
The subcommand will remove any nesting it finds if the option
\fB-full\fR is specified\&.
.CS


    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

.CE
.TP
\fB::struct::list\fR \fBmap\fR \fIsequence\fR \fIcmdprefix\fR
The subcommand takes a \fIsequence\fR to operate on and a command
prefix (\fIcmdprefix\fR) specifying an operation, applies the command
prefix to each element of the sequence and returns a sequence
consisting of the results of that application\&.
.sp
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\&.
.sp
.CS


    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

.CE
.TP
\fB::struct::list\fR \fBmapfor\fR \fIvar\fR \fIsequence\fR \fIscript\fR
The subcommand takes a \fIsequence\fR to operate on and a tcl \fIscript\fR,
applies the script to each element of the sequence and returns a sequence
consisting of the results of that application\&.
.sp
The script will be evaluated as is, and has access to the current list element
through the specified iteration variable \fIvar\fR\&. The evaluation takes place
in the context of the caller of the subcommand\&.
.sp
.CS


    tclsh> # squaring all elements in a list

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

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

    tclsh> ::struct::list mapfor x {{a b c} {1 2 3} {d f g}} {
	lindex $x 1
    }
    b 2 f

.CE
.TP
\fB::struct::list\fR \fBfilter\fR \fIsequence\fR \fIcmdprefix\fR
The subcommand takes a \fIsequence\fR to operate on and a command
prefix (\fIcmdprefix\fR) specifying an operation, applies the command
prefix to each element of the sequence and returns a sequence
consisting of all elements of the \fIsequence\fR for which the command
prefix returned \fBtrue\fR\&.
In other words, this command filters out all elements of the input
\fIsequence\fR which fail the test the \fIcmdprefix\fR represents, and
returns the remaining elements\&.
.sp
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\&.
.sp
.CS


    tclsh> # removing all odd numbers from the input

    tclsh> proc even {x} {expr {($x % 2) == 0}}
    tclsh> ::struct::list filter {1 2 3 4 5} even
    2 4

.CE
.sp
\fINote:\fR The \fBfilter\fR is a specialized application of
\fBfold\fR where the result is extended with the current item or
not, depending o nthe result of the test\&.
.TP
\fB::struct::list\fR \fBfilterfor\fR \fIvar\fR \fIsequence\fR \fIexpr\fR
The subcommand takes a \fIsequence\fR to operate on and a tcl expression
(\fIexpr\fR) specifying a condition, applies the conditionto each element
of the sequence and returns a sequence consisting of all elements of the
\fIsequence\fR for which the expression returned \fBtrue\fR\&.
In other words, this command filters out all elements of the input
\fIsequence\fR which fail the test the condition \fIexpr\fR represents, and
returns the remaining elements\&.
.sp
The expression will be evaluated as is, and has access to the current list
element through the specified iteration variable \fIvar\fR\&. The evaluation
takes place in the context of the caller of the subcommand\&.
.sp
.CS


    tclsh> # removing all odd numbers from the input

    tclsh> ::struct::list filterfor x {1 2 3 4 5} {($x % 2) == 0}
    2 4

.CE
.TP
\fB::struct::list\fR \fBsplit\fR \fIsequence\fR \fIcmdprefix\fR ?\fIpassVar\fR \fIfailVar\fR?
This is a variant of method \fBfilter\fR, see above\&. Instead of
returning just the elements passing the test we get lists of both
passing and failing elements\&.
.sp
If no variable names are specified then the result of the command will
be a list containing the list of passing elements, and the list of
failing elements, in this order\&. Otherwise the lists of passing and
failing elements are stored into the two specified variables, and the
result will be a list containing two numbers, the number of elements
passing the test, and the number of elements failing, in this order\&.
.sp
The interface to the test is the same as used by \fBfilter\fR\&.
.TP
\fB::struct::list\fR \fBfold\fR \fIsequence\fR \fIinitialvalue\fR \fIcmdprefix\fR
The subcommand takes a \fIsequence\fR to operate on, an arbitrary
string \fIinitial value\fR and a command prefix (\fIcmdprefix\fR)
specifying an operation\&.
.sp
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\&.
.sp
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
.RS
.TP
\fB1\fR
Application of the command to the initial value and the first element
of the list\&.
.TP
\fB2\fR
Application of the command to the result of the last call and the
second element of the list\&.
.TP
\fB\&.\&.\&.\fR
.TP
\fBi\fR
Application of the command to the result of the last call and the
\fBi\fR'th element of the list\&.
.TP
\fB\&.\&.\&.\fR
.TP
\fBend\fR
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\&.
.RE
.sp
.CS


    tclsh> # summing the elements in a list\&.
    tclsh> proc + {a b} {expr {$a + $b}}
    tclsh> ::struct::list fold {1 2 3 4 5} 0 +
    15

.CE
.TP
\fB::struct::list\fR \fBshift\fR \fIlistvar\fR
The subcommand takes the list contained in the variable named by
\fIlistvar\fR and shifts it down one element\&.
After the call \fIlistvar\fR will contain a list containing the second
to last elements of the input list\&. The first element of the ist is
returned as the result of the command\&. Shifting the empty list does
nothing\&.
.TP
\fB::struct::list\fR \fBiota\fR \fIn\fR
The subcommand returns a list containing the integer numbers
in the range \fB[0,n)\fR\&. The element at index \fBi\fR
of the list contain the number \fBi\fR\&.
.sp
For "\fIn\fR == \fB0\fR" an empty list will be returned\&.
.TP
\fB::struct::list\fR \fBequal\fR ?\fB-simple\fR? ?\fB--\fR? \fIa\fR \fIb\fR
The subcommand compares the two lists \fIa\fR and \fIb\fR for
equality\&. In other words, they have to be of the same length and have
to contain the same elements in the same order\&.
.sp
By default equality checks are applied recursively to list elements which are lists themselves\&.
This behaviour is disabled when specifying the option \fB-simple\fR\&.
.sp
The option \fB--\fR disables option processing even if the following argument looks like such\&.
.sp
A boolean value will be returned as the result of the command\&.
This value will be \fBtrue\fR if the two lists are equal, and
\fBfalse\fR else\&.
.TP
\fB::struct::list\fR \fBrepeat\fR \fIsize\fR \fIelement1\fR ?\fIelement2\fR \fIelement3\fR\&.\&.\&.?
The subcommand creates a list of length
"\fIsize\fR * \fInumber of elements\fR" by repeating \fIsize\fR
times the sequence of elements
\fIelement1\fR \fIelement2\fR \fI\&.\&.\&.\fR\&.
\fIsize\fR must be a positive integer, \fIelement\fR\fBn\fR can be any
Tcl value\&.
Note that \fBrepeat 1 arg \&.\&.\&.\fR  is identical to
\fBlist arg \&.\&.\&.\fR, though the \fIarg\fR is required
with \fBrepeat\fR\&.
.sp
\fIExamples:\fR
.sp
.CS


    tclsh> ::struct::list repeat 3 a
    a a a
    tclsh> ::struct::list repeat 3 [::struct::list repeat 3 0]
    {0 0 0} {0 0 0} {0 0 0}
    tclsh> ::struct::list repeat 3 a b c
    a b c a b c a b c
    tclsh> ::struct::list repeat 3 [::struct::list repeat 2 a] b c
    {a a} b c {a a} b c {a a} b c

.CE
.TP
\fB::struct::list\fR \fBrepeatn\fR \fIvalue\fR \fIsize\fR\&.\&.\&.
The subcommand creates a (nested) list containing the \fIvalue\fR in
all positions\&. The exact size and degree of nesting is determined by
the \fIsize\fR arguments, all of which have to be integer numbers
greater than or equal to zero\&.
.sp
A single argument \fIsize\fR which is a list of more than one element
will be treated as if more than argument \fIsize\fR was specified\&.
.sp
If only one argument \fIsize\fR is present the returned list will not
be nested, of length \fIsize\fR and contain \fIvalue\fR in all
positions\&.
If more than one \fIsize\fR argument is present the returned
list will be nested, and of the length specified by the last
\fIsize\fR argument given to it\&. The elements of that list
are defined as the result of \fBRepeat\fR for the same arguments,
but with the last \fIsize\fR value removed\&.
.sp
An empty list will be returned if no \fIsize\fR arguments are present\&.
.sp
.CS


    tclsh> ::struct::list repeatn  0 3 4
    {0 0 0} {0 0 0} {0 0 0} {0 0 0}
    tclsh> ::struct::list repeatn  0 {3 4}
    {0 0 0} {0 0 0} {0 0 0} {0 0 0}
    tclsh> ::struct::list repeatn  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}}

.CE
.TP
\fB::struct::list\fR \fBdbJoin\fR ?\fB-inner\fR|\fB-left\fR|\fB-right\fR|\fB-full\fR? ?\fB-keys\fR \fIvarname\fR? {\fIkeycol\fR \fItable\fR}\&.\&.\&.
The method performs a table join according to relational algebra\&. The
execution of any of the possible outer join operation is triggered by
the presence of either option \fB-left\fR, \fB-right\fR, or
\fB-full\fR\&. If none of these options is present a regular inner
join will be performed\&. This can also be triggered by specifying
\fB-inner\fR\&. The various possible join operations are explained in
detail in section \fBTABLE JOIN\fR\&.
.sp
If the \fB-keys\fR is present its argument is the name of a
variable to store the full list of found keys into\&. Depending on the
exact nature of the input table and the join mode the output table may
not contain all the keys by default\&. In such a case the caller can
declare a variable for this information and then insert it into the
output table on its own, as she will have more information about the
placement than this command\&.
.sp
What is left to explain is the format of the arguments\&.
.sp
The \fIkeycol\fR arguments are the indices of the columns in the
tables which contain the key values to use for the joining\&. Each
argument applies to the table following immediately after it\&. The
columns are counted from \fB0\fR, which references the first
column\&. The table associated with the column index has to have at
least \fIkeycol\fR+1 columns\&. An error will be thrown if there are
less\&.
.sp
The \fItable\fR arguments represent a table or matrix of rows and
columns of values\&. We use the same representation as generated and
consumed by the methods \fBget rect\fR and \fBset rect\fR of
\fBmatrix\fR objects\&. In other words, each argument is a list,
representing the whole matrix\&.  Its elements are lists too, each
representing a single rows of the matrix\&. The elements of the
row-lists are the column values\&.
.sp
The table resulting from the join operation is returned as the result
of the command\&. We use the same representation as described above for
the input \fItable\fRs\&.
.TP
\fB::struct::list\fR \fBdbJoinKeyed\fR ?\fB-inner\fR|\fB-left\fR|\fB-right\fR|\fB-full\fR? ?\fB-keys\fR \fIvarname\fR? \fItable\fR\&.\&.\&.
The operations performed by this method are the same as described
above for \fBdbJoin\fR\&. The only difference is in the specification
of the keys to use\&. Instead of using column indices separate from the
table here the keys are provided within the table itself\&. The row
elements in each \fItable\fR are not the lists of column values, but a
two-element list where the second element is the regular list of
column values and the first element is the key to use\&.
.TP
\fB::struct::list\fR \fBswap\fR \fIlistvar\fR \fIi\fR \fIj\fR
The subcommand exchanges the elements at the indices \fIi\fR and
\fIj\fR in the list stored in the variable named by \fIlistvar\fR\&. The
list is modified in place, and also returned as the result of the
subcommand\&.
.TP
\fB::struct::list\fR \fBfirstperm\fR \fIlist\fR
This subcommand returns the lexicographically first permutation of the
input \fIlist\fR\&.
.TP
\fB::struct::list\fR \fBnextperm\fR \fIperm\fR
This subcommand accepts a permutation of a set of elements (provided
by \fIperm\fR) and returns the next permutatation in lexicographic
sequence\&.
.sp
The algorithm used here is by Donal E\&. Knuth, see section
\fBREFERENCES\fR for details\&.
.TP
\fB::struct::list\fR \fBpermutations\fR \fIlist\fR
This subcommand returns a list containing all permutations of the
input \fIlist\fR in lexicographic order\&.
.TP
\fB::struct::list\fR \fBforeachperm\fR \fIvar\fR \fIlist\fR \fIbody\fR
This subcommand executes the script \fIbody\fR once for each
permutation of the specified \fIlist\fR\&. The permutations are visited
in lexicographic order, and the variable \fIvar\fR is set to the
permutation for which \fIbody\fR is currently executed\&. The result of
the loop command is the empty string\&.
.PP
.SH "LONGEST COMMON SUBSEQUENCE AND FILE COMPARISON"
.PP
The \fBlongestCommonSubsequence\fR subcommand forms the core of a
flexible system for doing differential comparisons of files, similar
to the capability offered by the Unix command \fBdiff\fR\&.
While this procedure is quite rapid for many tasks of file comparison,
its performance degrades severely if \fIsequence2\fR 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)\&.
.PP
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 \fImaxOccurs\fR 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 \fBlongestCommonSubsequence2\fR implements this
heuristic\&.
It functions as a wrapper around \fBlongestCommonSubsequence\fR; 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\&.
.SH "TABLE JOIN"
This is an operation from relational algebra for relational databases\&.
.PP
The easiest way to understand the regular inner join is that it
creates the cartesian product of all the tables involved first and
then keeps only all those rows in the resulting table for which the
values in the specified key columns are equal to each other\&.
.PP
Implementing this description naively, i\&.e\&. as described above will
generate a \fIhuge\fR intermediate result\&. To avoid this the
cartesian product and the filtering of row are done at the same
time\&. What is required is a fast way to determine if a key is present
in a table\&. In a true database this is done through indices\&. Here we
use arrays internally\&.
.PP
An \fIouter\fR join is an extension of the inner join for two
tables\&. There are three variants of outerjoins, called \fIleft\fR,
\fIright\fR, and \fIfull\fR outer joins\&. Their result always
contains all rows from an inner join and then some additional rows\&.
.IP [1]
For the left outer join the additional rows are all rows from the left
table for which there is no key in the right table\&. They are joined to
an empty row of the right table to fit them into the result\&.
.IP [2]
For the right outer join the additional rows are all rows from the right
table for which there is no key in the left table\&. They are joined to
an empty row of the left table to fit them into the result\&.
.IP [3]
The full outer join combines both left and right outer join\&. In other
words, the additional rows are as defined for left outer join, and
right outer join, combined\&.
.PP
.PP
We extend all the joins from two to \fBn\fR tables (\fBn\fR > 2) by
executing
.CS


    (\&.\&.\&.((table1 join table2) join table3) \&.\&.\&.) join tableN

.CE
.PP
Examples for all the joins:
.CS


    Inner Join

    {0 foo}              {0 bagel}    {0 foo   0 bagel}
    {1 snarf} inner join {1 snatz}  = {1 snarf 1 snatz}
    {2 blue}             {3 driver}

    Left Outer Join

    {0 foo}                   {0 bagel}    {0 foo   0 bagel}
    {1 snarf} left outer join {1 snatz}  = {1 snarf 1 snatz}
    {2 blue}                  {3 driver}   {2 blue  {} {}}

    Right Outer Join

    {0 foo}                    {0 bagel}    {0 foo   0 bagel}
    {1 snarf} right outer join {1 snatz}  = {1 snarf 1 snatz}
    {2 blue}                   {3 driver}   {{} {}   3 driver}

    Full Outer Join

    {0 foo}                   {0 bagel}    {0 foo   0 bagel}
    {1 snarf} full outer join {1 snatz}  = {1 snarf 1 snatz}
    {2 blue}                  {3 driver}   {2 blue  {} {}}
                                           {{} {}   3 driver}

.CE
.SH REFERENCES
.IP [1]
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: \fIhttp://www\&.cs\&.dartmouth\&.edu/~doug/\fR
.IP [2]
Donald E\&. Knuth, "Fascicle 2b of 'The Art of Computer Programming'
volume 4"\&. Available on the Web at the author's personal site:
\fIhttp://www-cs-faculty\&.stanford\&.edu/~knuth/fasc2b\&.ps\&.gz\fR\&.
.PP
.SH "BUGS, IDEAS, FEEDBACK"
This document, and the package it describes, will undoubtedly contain
bugs and other problems\&.
Please report such in the category \fIstruct :: list\fR of the
\fITcllib Trackers\fR [http://core\&.tcl\&.tk/tcllib/reportlist]\&.
Please also report any ideas for enhancements you may have for either
package and/or documentation\&.
.PP
When proposing code changes, please provide \fIunified diffs\fR,
i\&.e the output of \fBdiff -u\fR\&.
.PP
Note further that \fIattachments\fR are strongly preferred over
inlined patches\&. Attachments can be made by going to the \fBEdit\fR
form of the ticket immediately after its creation, and then using the
left-most button in the secondary navigation bar\&.
.SH KEYWORDS
Fisher-Yates, assign, common, comparison, diff, differential, equal, equality, filter, first permutation, flatten, folding, full outer join, generate permutations, inner join, join, left outer join, list, longest common subsequence, map, next permutation, outer join, permutation, reduce, repeating, repetition, reshuffle, reverse, right outer join, shuffle, subsequence, swapping
.SH CATEGORY
Data structures
.SH COPYRIGHT
.nf
Copyright (c) 2003-2005 by Kevin B\&. Kenny\&. All rights reserved
Copyright (c) 2003-2012 Andreas Kupries <andreas_kupries@users\&.sourceforge\&.net>

.fi