1struct::list(n) Tcl Data Structures struct::list(n)
2______________________________________________________________________________
6
8 struct::list - Procedures for manipulating lists
9
11 package require Tcl 8.4
12 package require struct::list ?1.8.3?
14 ::struct::list longestCommonSubsequence sequence1 sequence2 ?maxOccurs?
16 ::struct::list longestCommonSubsequence2 sequence1 sequence2 ?maxOc‐
18 curs?
19 ::struct::list lcsInvert lcsData len1 len2
21 ::struct::list lcsInvert2 lcs1 lcs2 len1 len2
23 ::struct::list lcsInvertMerge lcsData len1 len2
25 ::struct::list lcsInvertMerge2 lcs1 lcs2 len1 len2
27 ::struct::list reverse sequence
29 ::struct::list shuffle list
31 ::struct::list assign sequence varname ?varname?...
33 ::struct::list flatten ?-full? ?--? sequence
35 ::struct::list map sequence cmdprefix
37 ::struct::list mapfor var sequence script
39 ::struct::list filter sequence cmdprefix
41 ::struct::list filterfor var sequence expr
43 ::struct::list split sequence cmdprefix ?passVar failVar?
45 ::struct::list fold sequence initialvalue cmdprefix
47 ::struct::list shift listvar
49 ::struct::list iota n
51 ::struct::list equal a b
53 ::struct::list repeat size element1 ?element2 element3...?
55 ::struct::list repeatn value size...
57 ::struct::list dbJoin ?-inner|-left|-right|-full? ?-keys varname? {key‐
59 col table}...
60 ::struct::list dbJoinKeyed ?-inner|-left|-right|-full? ?-keys varname?
62 table...
63 ::struct::list swap listvar i j
65 ::struct::list firstperm list
67 ::struct::list nextperm perm
69 ::struct::list permutations list
71 ::struct::list foreachperm var list body
73______________________________________________________________________________
75
77 The ::struct::list namespace contains several useful commands for pro‐
78 cessing Tcl lists. Generally speaking, they implement algorithms more
79 complex or specialized than the ones provided by Tcl itself.
80 It exports only a single command, struct::list. All functionality pro‐
82 vided here can be reached through a subcommand of this command.
83
85 ::struct::list longestCommonSubsequence sequence1 sequence2 ?maxOccurs?
86 Returns the longest common subsequence of elements in the two
87 lists sequence1 and sequence2. If the maxOccurs parameter is
88 provided, the common subsequence is restricted to elements that
89 occur no more than maxOccurs times in sequence2.
90 The return value is a list of two lists of equal length. The
92 first sublist is of indices into sequence1, and the second sub‐
93 list is of indices into sequence2. Each corresponding pair of
94 indices corresponds to equal elements in the sequences; the
95 sequence returned is the longest possible.
96 ::struct::list longestCommonSubsequence2 sequence1 sequence2 ?maxOc‐
98 curs?
99 Returns an approximation to the longest common sequence of ele‐
100 ments in the two lists sequence1 and sequence2. If the maxOc‐
101 curs parameter is omitted, the subsequence computed is exactly
102 the longest common subsequence; otherwise, the longest common
103 subsequence is approximated by first determining the longest
104 common sequence of only those elements that occur no more than
105 maxOccurs times in sequence2, and then using that result to
106 align the two lists, determining the longest common subsequences
107 of the sublists between the two elements.
108 As with longestCommonSubsequence, the return value is a list of
110 two lists of equal length. The first sublist is of indices into
111 sequence1, and the second sublist is of indices into sequence2.
112 Each corresponding pair of indices corresponds to equal elements
113 in the sequences. The sequence approximates the longest common
114 subsequence.
115 ::struct::list lcsInvert lcsData len1 len2
117 This command takes a description of a longest common subsequence
118 (lcsData), inverts it, and returns the result. Inversion means
119 here that as the input describes which parts of the two
120 sequences are identical the output describes the differences
121 instead.
122 To be fully defined the lengths of the two sequences have to be
124 known and are specified through len1 and len2.
125 The result is a list where each element describes one chunk of
127 the differences between the two sequences. This description is a
128 list containing three elements, a type and two pairs of indices
129 into sequence1 and sequence2 respectively, in this order. The
130 type can be one of three values:
131 added Describes an addition. I.e. items which are missing in
133 sequence1 can be found in sequence2. The pair of indices
134 into sequence1 describes where the added range had been
135 expected to be in sequence1. The first index refers to
136 the item just before the added range, and the second
137 index refers to the item just after the added range. The
138 pair of indices into sequence2 describes the range of
139 items which has been added to it. The first index refers
140 to the first item in the range, and the second index
141 refers to the last item in the range.
142 deleted
144 Describes a deletion. I.e. items which are in sequence1
145 are missing from sequence2. The pair of indices into
146 sequence1 describes the range of items which has been
147 deleted. The first index refers to the first item in the
148 range, and the second index refers to the last item in
149 the range. The pair of indices into sequence2 describes
150 where the deleted range had been expected to be in
151 sequence2. The first index refers to the item just before
152 the deleted range, and the second index refers to the
153 item just after the deleted range.
154 changed
156 Describes a general change. I.e a range of items in
157 sequence1 has been replaced by a different range of items
158 in sequence2. The pair of indices into sequence1
159 describes the range of items which has been replaced. The
160 first index refers to the first item in the range, and
161 the second index refers to the last item in the range.
162 The pair of indices into sequence2 describes the range of
163 items replacing the original range. Again the first index
164 refers to the first item in the range, and the second
165 index refers to the last item in the range.
166 sequence 1 = {a b r a c a d a b r a}
170 lcs 1 = {1 2 4 5 8 9 10}
171 lcs 2 = {0 1 3 4 5 6 7}
172 sequence 2 = {b r i c a b r a c}
173 Inversion = {{deleted {0 0} {-1 0}}
175 {changed {3 3} {2 2}}
176 {deleted {6 7} {4 5}}
177 {added {10 11} {8 8}}}
178 Notes:
181 · An index of -1 in a deleted chunk refers to just before
184 the first element of the second sequence.
185 · Also an index equal to the length of the first sequence
187 in an added chunk refers to just behind the end of the
188 sequence.
189 ::struct::list lcsInvert2 lcs1 lcs2 len1 len2
191 Similar to lcsInvert. Instead of directly taking the result of a
192 call to longestCommonSubsequence this subcommand expects the
193 indices for the two sequences in two separate lists.
194 ::struct::list lcsInvertMerge lcsData len1 len2
196 Similar to lcsInvert. It returns essentially the same structure
197 as that command, except that it may contain chunks of type
198 unchanged too.
199 These new chunks describe the parts which are unchanged between
201 the two sequences. This means that the result of this command
202 describes both the changed and unchanged parts of the two
203 sequences in one structure.
204 sequence 1 = {a b r a c a d a b r a}
208 lcs 1 = {1 2 4 5 8 9 10}
209 lcs 2 = {0 1 3 4 5 6 7}
210 sequence 2 = {b r i c a b r a c}
211 Inversion/Merge = {{deleted {0 0} {-1 0}}
213 {unchanged {1 2} {0 1}}
214 {changed {3 3} {2 2}}
215 {unchanged {4 5} {3 4}}
216 {deleted {6 7} {4 5}}
217 {unchanged {8 10} {5 7}}
218 {added {10 11} {8 8}}}
219 ::struct::list lcsInvertMerge2 lcs1 lcs2 len1 len2
222 Similar to lcsInvertMerge. Instead of directly taking the result
223 of a call to longestCommonSubsequence this subcommand expects
224 the indices for the two sequences in two separate lists.
225 ::struct::list reverse sequence
227 The subcommand takes a single sequence as argument and returns a
228 new sequence containing the elements of the input sequence in
229 reverse order.
230 ::struct::list shuffle list
232 The subcommand takes a list and returns a copy of that list with
233 the elements it contains in random order. Every possible order‐
234 ing of elements is equally likely to be generated. The Fisher-
235 Yates shuffling algorithm is used internally.
236 ::struct::list assign sequence varname ?varname?...
238 The subcommand assigns the first n elements of the input
239 sequence to the one or more variables whose names were listed
240 after the sequence, where n is the number of specified vari‐
241 ables.
242 If there are more variables specified than there are elements in
244 the sequence the empty string will be assigned to the superflu‐
245 ous variables.
246 If there are more elements in the sequence than variable names
248 specified the subcommand returns a list containing the unas‐
249 signed elements. Else an empty list is returned.
250 tclsh> ::struct::list assign {a b c d e} foo bar
253 c d e
254 tclsh> set foo
255 a
256 tclsh> set bar
257 b
258 ::struct::list flatten ?-full? ?--? sequence
261 The subcommand takes a single sequence and returns a new
262 sequence where one level of nesting was removed from the input
263 sequence. In other words, the sublists in the input sequence are
264 replaced by their elements.
265 The subcommand will remove any nesting it finds if the option
267 -full is specified.
268 tclsh> ::struct::list flatten {1 2 3 {4 5} {6 7} {{8 9}} 10}
271 1 2 3 4 5 6 7 {8 9} 10
272 tclsh> ::struct::list flatten -full {1 2 3 {4 5} {6 7} {{8 9}} 10}
273 1 2 3 4 5 6 7 8 9 10
274 ::struct::list map sequence cmdprefix
277 The subcommand takes a sequence to operate on and a command pre‐
278 fix (cmdprefix) specifying an operation, applies the command
279 prefix to each element of the sequence and returns a sequence
280 consisting of the results of that application.
281 The command prefix will be evaluated with a single word appended
283 to it. The evaluation takes place in the context of the caller
284 of the subcommand.
285 tclsh> # squaring all elements in a list
289 tclsh> proc sqr {x} {expr {$x*$x}}
291 tclsh> ::struct::list map {1 2 3 4 5} sqr
292 1 4 9 16 25
293 tclsh> # Retrieving the second column from a matrix
295 tclsh> # given as list of lists.
296 tclsh> proc projection {n list} {::lindex $list $n}
298 tclsh> ::struct::list map {{a b c} {1 2 3} {d f g}} {projection 1}
299 b 2 f
300 ::struct::list mapfor var sequence script
303 The subcommand takes a sequence to operate on and a tcl script,
304 applies the script to each element of the sequence and returns a
305 sequence consisting of the results of that application.
306 The script will be evaluated as is, and has access to the cur‐
308 rent list element through the specified iteration variable var.
309 The evaluation takes place in the context of the caller of the
310 subcommand.
311 tclsh> # squaring all elements in a list
315 tclsh> ::struct::list mapfor x {1 2 3 4 5} {
317 expr {$x * $x}
318 }
319 1 4 9 16 25
320 tclsh> # Retrieving the second column from a matrix
322 tclsh> # given as list of lists.
323 tclsh> ::struct::list mapfor x {{a b c} {1 2 3} {d f g}} {
325 lindex $x 1
326 }
327 b 2 f
328 ::struct::list filter sequence cmdprefix
331 The subcommand takes a sequence to operate on and a command pre‐
332 fix (cmdprefix) specifying an operation, applies the command
333 prefix to each element of the sequence and returns a sequence
334 consisting of all elements of the sequence for which the command
335 prefix returned true. In other words, this command filters out
336 all elements of the input sequence which fail the test the cmd‐
337 prefix represents, and returns the remaining elements.
338 The command prefix will be evaluated with a single word appended
340 to it. The evaluation takes place in the context of the caller
341 of the subcommand.
342 tclsh> # removing all odd numbers from the input
346 tclsh> proc even {x} {expr {($x % 2) == 0}}
348 tclsh> ::struct::list filter {1 2 3 4 5} even
349 2 4
350 Note: The filter is a specialized application of fold where the result
353 is extended with the current item or not, depending o nthe result of
354 the test.
355 ::struct::list filterfor var sequence expr
357 The subcommand takes a sequence to operate on and a tcl expres‐
358 sion (expr) specifying a condition, applies the conditionto each
359 element of the sequence and returns a sequence consisting of all
360 elements of the sequence for which the expression returned true.
361 In other words, this command filters out all elements of the
362 input sequence which fail the test the condition expr repre‐
363 sents, and returns the remaining elements.
364 The expression will be evaluated as is, and has access to the
366 current list element through the specified iteration variable
367 var. The evaluation takes place in the context of the caller of
368 the subcommand.
369 tclsh> # removing all odd numbers from the input
373 tclsh> ::struct::list filterfor x {1 2 3 4 5} {($x % 2) == 0}
375 2 4
376 ::struct::list split sequence cmdprefix ?passVar failVar?
379 This is a variant of method filter, see above. Instead of
380 returning just the elements passing the test we get lists of
381 both passing and failing elements.
382 If no variable names are specified then the result of the com‐
384 mand will be a list containing the list of passing elements, and
385 the list of failing elements, in this order. Otherwise the lists
386 of passing and failing elements are stored into the two speci‐
387 fied variables, and the result will be a list containing two
388 numbers, the number of elements passing the test, and the number
389 of elements failing, in this order.
390 The interface to the test is the same as used by filter.
392 ::struct::list fold sequence initialvalue cmdprefix
394 The subcommand takes a sequence to operate on, an arbitrary
395 string initial value and a command prefix (cmdprefix) specifying
396 an operation.
397 The command prefix will be evaluated with two words appended to
399 it. The second of these words will always be an element of the
400 sequence. The evaluation takes place in the context of the call‐
401 er of the subcommand.
402 It then reduces the sequence into a single value through
404 repeated application of the command prefix and returns that
405 value. This reduction is done by
406 1 Application of the command to the initial value and the
408 first element of the list.
409 2 Application of the command to the result of the last call
411 and the second element of the list.
412 ...
414 i Application of the command to the result of the last call
416 and the i'th element of the list.
417 ...
419 end Application of the command to the result of the last call
421 and the last element of the list. The result of this call
422 is returned as the result of the subcommand.
423 tclsh> # summing the elements in a list.
427 tclsh> proc + {a b} {expr {$a + $b}}
428 tclsh> ::struct::list fold {1 2 3 4 5} 0 +
429 15
430 ::struct::list shift listvar
433 The subcommand takes the list contained in the variable named by
434 listvar and shifts it down one element. After the call listvar
435 will contain a list containing the second to last elements of
436 the input list. The first element of the ist is returned as the
437 result of the command. Shifting the empty list does nothing.
438 ::struct::list iota n
440 The subcommand returns a list containing the integer numbers in
441 the range [0,n). The element at index i of the list contain the
442 number i.
443 For "n == 0" an empty list will be returned.
445 ::struct::list equal a b
447 The subcommand compares the two lists a and b for equality. In
448 other words, they have to be of the same length and have to con‐
449 tain the same elements in the same order. If an element is a
450 list the same definition of equality applies recursively.
451 A boolean value will be returned as the result of the command.
453 This value will be true if the two lists are equal, and false
454 else.
455 ::struct::list repeat size element1 ?element2 element3...?
457 The subcommand creates a list of length "size * number of ele‐
458 ments" by repeating size times the sequence of elements element1
459 element2 .... size must be a positive integer, elementn can be
460 any Tcl value. Note that repeat 1 arg ... is identical to list
461 arg ..., though the arg is required with repeat.
462 Examples:
464 tclsh> ::struct::list repeat 3 a
468 a a a
469 tclsh> ::struct::list repeat 3 [::struct::list repeat 3 0]
470 {0 0 0} {0 0 0} {0 0 0}
471 tclsh> ::struct::list repeat 3 a b c
472 a b c a b c a b c
473 tclsh> ::struct::list repeat 3 [::struct::list repeat 2 a] b c
474 {a a} b c {a a} b c {a a} b c
475 ::struct::list repeatn value size...
478 The subcommand creates a (nested) list containing the value in
479 all positions. The exact size and degree of nesting is deter‐
480 mined by the size arguments, all of which have to be integer
481 numbers greater than or equal to zero.
482 A single argument size which is a list of more than one element
484 will be treated as if more than argument size was specified.
485 If only one argument size is present the returned list will not
487 be nested, of length size and contain value in all positions.
488 If more than one size argument is present the returned list will
489 be nested, and of the length specified by the last size argument
490 given to it. The elements of that list are defined as the result
491 of Repeat for the same arguments, but with the last size value
492 removed.
493 An empty list will be returned if no size arguments are present.
495 tclsh> ::struct::list repeatn 0 3 4
499 {0 0 0} {0 0 0} {0 0 0} {0 0 0}
500 tclsh> ::struct::list repeatn 0 {3 4}
501 {0 0 0} {0 0 0} {0 0 0} {0 0 0}
502 tclsh> ::struct::list repeatn 0 {3 4 5}
503 {{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}}
504 ::struct::list dbJoin ?-inner|-left|-right|-full? ?-keys varname? {key‐
507 col table}...
508 The method performs a table join according to relational alge‐
509 bra. The execution of any of the possible outer join operation
510 is triggered by the presence of either option -left, -right, or
511 -full. If none of these options is present a regular inner join
512 will be performed. This can also be triggered by specifying
513 -inner. The various possible join operations are explained in
514 detail in section TABLE JOIN.
515 If the -keys is present its argument is the name of a variable
517 to store the full list of found keys into. Depending on the
518 exact nature of the input table and the join mode the output ta‐
519 ble may not contain all the keys by default. In such a case the
520 caller can declare a variable for this information and then
521 insert it into the output table on its own, as she will have
522 more information about the placement than this command.
523 What is left to explain is the format of the arguments.
525 The keycol arguments are the indices of the columns in the
527 tables which contain the key values to use for the joining. Each
528 argument applies to the table following immediately after it.
529 The columns are counted from 0, which references the first col‐
530 umn. The table associated with the column index has to have at
531 least keycol+1 columns. An error will be thrown if there are
532 less.
533 The table arguments represent a table or matrix of rows and col‐
535 umns of values. We use the same representation as generated and
536 consumed by the methods get rect and set rect of matrix objects.
537 In other words, each argument is a list, representing the whole
538 matrix. Its elements are lists too, each representing a single
539 rows of the matrix. The elements of the row-lists are the column
540 values.
541 The table resulting from the join operation is returned as the
543 result of the command. We use the same representation as
544 described above for the input tables.
545 ::struct::list dbJoinKeyed ?-inner|-left|-right|-full? ?-keys varname?
547 table...
548 The operations performed by this method are the same as
549 described above for dbJoin. The only difference is in the speci‐
550 fication of the keys to use. Instead of using column indices
551 separate from the table here the keys are provided within the
552 table itself. The row elements in each table are not the lists
553 of column values, but a two-element list where the second ele‐
554 ment is the regular list of column values and the first element
555 is the key to use.
556 ::struct::list swap listvar i j
558 The subcommand exchanges the elements at the indices i and j in
559 the list stored in the variable named by listvar. The list is
560 modified in place, and also returned as the result of the sub‐
561 command.
562 ::struct::list firstperm list
564 This subcommand returns the lexicographically first permutation
565 of the input list.
566 ::struct::list nextperm perm
568 This subcommand accepts a permutation of a set of elements (pro‐
569 vided by perm) and returns the next permutatation in lexico‐
570 graphic sequence.
571 The algorithm used here is by Donal E. Knuth, see section REFER‐
573 ENCES for details.
574 ::struct::list permutations list
576 This subcommand returns a list containing all permutations of
577 the input list in lexicographic order.
578 ::struct::list foreachperm var list body
580 This subcommand executes the script body once for each permuta‐
581 tion of the specified list. The permutations are visited in lex‐
582 icographic order, and the variable var is set to the permutation
583 for which body is currently executed. The result of the loop
584 command is the empty string.
585
587 The longestCommonSubsequence subcommand forms the core of a flexible
588 system for doing differential comparisons of files, similar to the
589 capability offered by the Unix command diff. While this procedure is
590 quite rapid for many tasks of file comparison, its performance degrades
591 severely if sequence2 contains many equal elements (as, for instance,
592 when using this procedure to compare two files, a quarter of whose
593 lines are blank. This drawback is intrinsic to the algorithm used (see
594 the Reference for details).
595 One approach to dealing with the performance problem that is sometimes
597 effective in practice is arbitrarily to exclude elements that appear
598 more than a certain number of times. This number is provided as the
599 maxOccurs parameter. If frequent lines are excluded in this manner,
600 they will not appear in the common subsequence that is computed; the
601 result will be the longest common subsequence of infrequent elements.
602 The procedure longestCommonSubsequence2 implements this heuristic. It
603 functions as a wrapper around longestCommonSubsequence; it computes the
604 longest common subsequence of infrequent elements, and then subdivides
605 the subsequences that lie between the matches to approximate the true
606 longest common subsequence.
607
609 This is an operation from relational algebra for relational databases.
610 The easiest way to understand the regular inner join is that it creates
612 the cartesian product of all the tables involved first and then keeps
613 only all those rows in the resulting table for which the values in the
614 specified key columns are equal to each other.
615 Implementing this description naively, i.e. as described above will
617 generate a huge intermediate result. To avoid this the cartesian prod‐
618 uct and the filtering of row are done at the same time. What is
619 required is a fast way to determine if a key is present in a table. In
620 a true database this is done through indices. Here we use arrays inter‐
621 nally.
622 An outer join is an extension of the inner join for two tables. There
624 are three variants of outerjoins, called left, right, and full outer
625 joins. Their result always contains all rows from an inner join and
626 then some additional rows.
627 [1] For the left outer join the additional rows are all rows from
629 the left table for which there is no key in the right table.
630 They are joined to an empty row of the right table to fit them
631 into the result.
632 [2] For the right outer join the additional rows are all rows from
634 the right table for which there is no key in the left table.
635 They are joined to an empty row of the left table to fit them
636 into the result.
637 [3] The full outer join combines both left and right outer join. In
639 other words, the additional rows are as defined for left outer
640 join, and right outer join, combined.
641 We extend all the joins from two to n tables (n > 2) by executing
643 (...((table1 join table2) join table3) ...) join tableN
646 Examples for all the joins:
649 Inner Join
652 {0 foo} {0 bagel} {0 foo 0 bagel}
654 {1 snarf} inner join {1 snatz} = {1 snarf 1 snatz}
655 {2 blue} {3 driver}
656 Left Outer Join
658 {0 foo} {0 bagel} {0 foo 0 bagel}
660 {1 snarf} left outer join {1 snatz} = {1 snarf 1 snatz}
661 {2 blue} {3 driver} {2 blue {} {}}
662 Right Outer Join
664 {0 foo} {0 bagel} {0 foo 0 bagel}
666 {1 snarf} right outer join {1 snatz} = {1 snarf 1 snatz}
667 {2 blue} {3 driver} {{} {} 3 driver}
668 Full Outer Join
670 {0 foo} {0 bagel} {0 foo 0 bagel}
672 {1 snarf} full outer join {1 snatz} = {1 snarf 1 snatz}
673 {2 blue} {3 driver} {2 blue {} {}}
674 {{} {} 3 driver}
675
678 [1] J. W. Hunt and M. D. McIlroy, "An algorithm for differential
679 file comparison," Comp. Sci. Tech. Rep. #41, Bell Telephone Lab‐
680 oratories (1976). Available on the Web at the second author's
681 personal site: http://www.cs.dartmouth.edu/~doug/
682 [2] Donald E. Knuth, "Fascicle 2b of 'The Art of Computer Program‐
684 ming' volume 4". Available on the Web at the author's personal
685 site: http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz.
686
688 This document, and the package it describes, will undoubtedly contain
689 bugs and other problems. Please report such in the category struct ::
690 list of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist].
691 Please also report any ideas for enhancements you may have for either
692 package and/or documentation.
693 When proposing code changes, please provide unified diffs, i.e the out‐
695 put of diff -u.
696 Note further that attachments are strongly preferred over inlined
698 patches. Attachments can be made by going to the Edit form of the
699 ticket immediately after its creation, and then using the left-most
700 button in the secondary navigation bar.
701
703 Fisher-Yates, assign, common, comparison, diff, differential, equal,
704 equality, filter, first permutation, flatten, folding, full outer join,
705 generate permutations, inner join, join, left outer join, list, longest
706 common subsequence, map, next permutation, outer join, permutation,
707 reduce, repeating, repetition, reshuffle, reverse, right outer join,
708 shuffle, subsequence, swapping
709
711 Data structures
712
714 Copyright (c) 2003-2005 by Kevin B. Kenny. All rights reserved
715 Copyright (c) 2003-2012 Andreas Kupries <andreas_kupries@users.sourceforge.net>
716tcllib 1.8.3 struct::list(n)