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.5?
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 a list of indices into sequence1 and a corresponding
87 list where each item is an index into sequence2 of the matching
88 value according to the longest common subsequences algorithm.
89 If maxOccurs is provided, the common subsequence is restricted
90 to elements that occur no more than maxOccurs times in se‐
91 quence2.
92 ::struct::list longestCommonSubsequence2 sequence1 sequence2 ?maxOc‐
95 curs?
96 Returns the longest common subsequence of elements in the two
97 lists sequence1 and sequence2. If maxOccurs is provided, the
98 result is only an approximation, where the longest common subse‐
99 quence is approximated by first determining the longest common
100 sequence of only those elements that occur no more than maxOc‐
101 curs times in sequence2, and then using that result to align the
102 two lists, determining the longest common subsequences of the
103 sublists between the two elements.
104 The result is the same as for longestCommonSubsequence.
106 ::struct::list lcsInvert lcsData len1 len2
108 Takes a description of a longest common subsequence (lcsData),
109 inverts it, and returns the result. Inversion means here that as
110 the input describes which parts of the two sequences are identi‐
111 cal the output describes the differences instead.
112 To be fully defined the lengths of the two sequences have to be
114 known and are specified through len1 and len2.
115 The result is a list where each element describes one chunk of
117 the differences between the two sequences. This description is a
118 list containing three elements, a type and two pairs of indices
119 into sequence1 and sequence2 respectively, in this order. The
120 type can be one of three values:
121 added Describes an addition. I.e. items which are missing in
123 sequence1 can be found in sequence2. The pair of indices
124 into sequence1 describes where the added range had been
125 expected to be in sequence1. The first index refers to
126 the item just before the added range, and the second in‐
127 dex refers to the item just after the added range. The
128 pair of indices into sequence2 describes the range of
129 items which has been added to it. The first index refers
130 to the first item in the range, and the second index
131 refers to the last item in the range.
132 deleted
134 Describes a deletion. I.e. items which are in sequence1
135 are missing from sequence2. The pair of indices into se‐
136 quence1 describes the range of items which has been
137 deleted. The first index refers to the first item in the
138 range, and the second index refers to the last item in
139 the range. The pair of indices into sequence2 describes
140 where the deleted range had been expected to be in se‐
141 quence2. The first index refers to the item just before
142 the deleted range, and the second index refers to the
143 item just after the deleted range.
144 changed
146 Describes a general change. I.e a range of items in se‐
147 quence1 has been replaced by a different range of items
148 in sequence2. The pair of indices into sequence1 de‐
149 scribes the range of items which has been replaced. The
150 first index refers to the first item in the range, and
151 the second index refers to the last item in the range.
152 The pair of indices into sequence2 describes the range of
153 items replacing the original range. Again the first index
154 refers to the first item in the range, and the second in‐
155 dex refers to the last item in the range.
156 sequence 1 = {a b r a c a d a b r a}
160 lcs 1 = {1 2 4 5 8 9 10}
161 lcs 2 = {0 1 3 4 5 6 7}
162 sequence 2 = {b r i c a b r a c}
163 Inversion = {{deleted {0 0} {-1 0}}
165 {changed {3 3} {2 2}}
166 {deleted {6 7} {4 5}}
167 {added {10 11} {8 8}}}
168 Notes:
171 • An index of -1 in a deleted chunk refers to just before
174 the first element of the second sequence.
175 • Also an index equal to the length of the first sequence
177 in an added chunk refers to just behind the end of the
178 sequence.
179 ::struct::list lcsInvert2 lcs1 lcs2 len1 len2
181 Similar to lcsInvert. Instead of directly taking the result of a
182 call to longestCommonSubsequence this subcommand expects the in‐
183 dices for the two sequences in two separate lists.
184 ::struct::list lcsInvertMerge lcsData len1 len2
186 Similar to lcsInvert. It returns essentially the same structure
187 as that command, except that it may contain chunks of type un‐
188 changed too.
189 These new chunks describe the parts which are unchanged between
191 the two sequences. This means that the result of this command
192 describes both the changed and unchanged parts of the two se‐
193 quences in one structure.
194 sequence 1 = {a b r a c a d a b r a}
198 lcs 1 = {1 2 4 5 8 9 10}
199 lcs 2 = {0 1 3 4 5 6 7}
200 sequence 2 = {b r i c a b r a c}
201 Inversion/Merge = {{deleted {0 0} {-1 0}}
203 {unchanged {1 2} {0 1}}
204 {changed {3 3} {2 2}}
205 {unchanged {4 5} {3 4}}
206 {deleted {6 7} {4 5}}
207 {unchanged {8 10} {5 7}}
208 {added {10 11} {8 8}}}
209 ::struct::list lcsInvertMerge2 lcs1 lcs2 len1 len2
212 Similar to lcsInvertMerge. Instead of directly taking the result
213 of a call to longestCommonSubsequence this subcommand expects
214 the indices for the two sequences in two separate lists.
215 ::struct::list reverse sequence
217 The subcommand takes a single sequence as argument and returns a
218 new sequence containing the elements of the input sequence in
219 reverse order.
220 ::struct::list shuffle list
222 The subcommand takes a list and returns a copy of that list with
223 the elements it contains in random order. Every possible order‐
224 ing of elements is equally likely to be generated. The Fisher-
225 Yates shuffling algorithm is used internally.
226 ::struct::list assign sequence varname ?varname?...
228 The subcommand assigns the first n elements of the input se‐
229 quence to the one or more variables whose names were listed af‐
230 ter the sequence, where n is the number of specified variables.
231 If there are more variables specified than there are elements in
233 the sequence the empty string will be assigned to the superflu‐
234 ous variables.
235 If there are more elements in the sequence than variable names
237 specified the subcommand returns a list containing the unas‐
238 signed elements. Else an empty list is returned.
239 tclsh> ::struct::list assign {a b c d e} foo bar
242 c d e
243 tclsh> set foo
244 a
245 tclsh> set bar
246 b
247 ::struct::list flatten ?-full? ?--? sequence
250 The subcommand takes a single sequence and returns a new se‐
251 quence where one level of nesting was removed from the input se‐
252 quence. In other words, the sublists in the input sequence are
253 replaced by their elements.
254 The subcommand will remove any nesting it finds if the option
256 -full is specified.
257 tclsh> ::struct::list flatten {1 2 3 {4 5} {6 7} {{8 9}} 10}
260 1 2 3 4 5 6 7 {8 9} 10
261 tclsh> ::struct::list flatten -full {1 2 3 {4 5} {6 7} {{8 9}} 10}
262 1 2 3 4 5 6 7 8 9 10
263 ::struct::list map sequence cmdprefix
266 The subcommand takes a sequence to operate on and a command pre‐
267 fix (cmdprefix) specifying an operation, applies the command
268 prefix to each element of the sequence and returns a sequence
269 consisting of the results of that application.
270 The command prefix will be evaluated with a single word appended
272 to it. The evaluation takes place in the context of the caller
273 of the subcommand.
274 tclsh> # squaring all elements in a list
278 tclsh> proc sqr {x} {expr {$x*$x}}
280 tclsh> ::struct::list map {1 2 3 4 5} sqr
281 1 4 9 16 25
282 tclsh> # Retrieving the second column from a matrix
284 tclsh> # given as list of lists.
285 tclsh> proc projection {n list} {::lindex $list $n}
287 tclsh> ::struct::list map {{a b c} {1 2 3} {d f g}} {projection 1}
288 b 2 f
289 ::struct::list mapfor var sequence script
292 The subcommand takes a sequence to operate on and a tcl script,
293 applies the script to each element of the sequence and returns a
294 sequence consisting of the results of that application.
295 The script will be evaluated as is, and has access to the cur‐
297 rent list element through the specified iteration variable var.
298 The evaluation takes place in the context of the caller of the
299 subcommand.
300 tclsh> # squaring all elements in a list
304 tclsh> ::struct::list mapfor x {1 2 3 4 5} {
306 expr {$x * $x}
307 }
308 1 4 9 16 25
309 tclsh> # Retrieving the second column from a matrix
311 tclsh> # given as list of lists.
312 tclsh> ::struct::list mapfor x {{a b c} {1 2 3} {d f g}} {
314 lindex $x 1
315 }
316 b 2 f
317 ::struct::list filter sequence cmdprefix
320 The subcommand takes a sequence to operate on and a command pre‐
321 fix (cmdprefix) specifying an operation, applies the command
322 prefix to each element of the sequence and returns a sequence
323 consisting of all elements of the sequence for which the command
324 prefix returned true. In other words, this command filters out
325 all elements of the input sequence which fail the test the cmd‐
326 prefix represents, and returns the remaining elements.
327 The command prefix will be evaluated with a single word appended
329 to it. The evaluation takes place in the context of the caller
330 of the subcommand.
331 tclsh> # removing all odd numbers from the input
335 tclsh> proc even {x} {expr {($x % 2) == 0}}
337 tclsh> ::struct::list filter {1 2 3 4 5} even
338 2 4
339 Note: The filter is a specialized application of fold where the result
342 is extended with the current item or not, depending o nthe result of
343 the test.
344 ::struct::list filterfor var sequence expr
346 The subcommand takes a sequence to operate on and a tcl expres‐
347 sion (expr) specifying a condition, applies the conditionto each
348 element of the sequence and returns a sequence consisting of all
349 elements of the sequence for which the expression returned true.
350 In other words, this command filters out all elements of the in‐
351 put sequence which fail the test the condition expr represents,
352 and returns the remaining elements.
353 The expression will be evaluated as is, and has access to the
355 current list element through the specified iteration variable
356 var. The evaluation takes place in the context of the caller of
357 the subcommand.
358 tclsh> # removing all odd numbers from the input
362 tclsh> ::struct::list filterfor x {1 2 3 4 5} {($x % 2) == 0}
364 2 4
365 ::struct::list split sequence cmdprefix ?passVar failVar?
368 This is a variant of method filter, see above. Instead of re‐
369 turning just the elements passing the test we get lists of both
370 passing and failing elements.
371 If no variable names are specified then the result of the com‐
373 mand will be a list containing the list of passing elements, and
374 the list of failing elements, in this order. Otherwise the lists
375 of passing and failing elements are stored into the two speci‐
376 fied variables, and the result will be a list containing two
377 numbers, the number of elements passing the test, and the number
378 of elements failing, in this order.
379 The interface to the test is the same as used by filter.
381 ::struct::list fold sequence initialvalue cmdprefix
383 The subcommand takes a sequence to operate on, an arbitrary
384 string initial value and a command prefix (cmdprefix) specifying
385 an operation.
386 The command prefix will be evaluated with two words appended to
388 it. The second of these words will always be an element of the
389 sequence. The evaluation takes place in the context of the
390 caller of the subcommand.
391 It then reduces the sequence into a single value through re‐
393 peated application of the command prefix and returns that value.
394 This reduction is done by
395 1 Application of the command to the initial value and the
397 first element of the list.
398 2 Application of the command to the result of the last call
400 and the second element of the list.
401 ...
403 i Application of the command to the result of the last call
405 and the i'th element of the list.
406 ...
408 end Application of the command to the result of the last call
410 and the last element of the list. The result of this call
411 is returned as the result of the subcommand.
412 tclsh> # summing the elements in a list.
416 tclsh> proc + {a b} {expr {$a + $b}}
417 tclsh> ::struct::list fold {1 2 3 4 5} 0 +
418 15
419 ::struct::list shift listvar
422 The subcommand takes the list contained in the variable named by
423 listvar and shifts it down one element. After the call listvar
424 will contain a list containing the second to last elements of
425 the input list. The first element of the ist is returned as the
426 result of the command. Shifting the empty list does nothing.
427 ::struct::list iota n
429 The subcommand returns a list containing the integer numbers in
430 the range [0,n). The element at index i of the list contain the
431 number i.
432 For "n == 0" an empty list will be returned.
434 ::struct::list equal a b
436 The subcommand compares the two lists a and b for equality. In
437 other words, they have to be of the same length and have to con‐
438 tain the same elements in the same order. If an element is a
439 list the same definition of equality applies recursively.
440 A boolean value will be returned as the result of the command.
442 This value will be true if the two lists are equal, and false
443 else.
444 ::struct::list repeat size element1 ?element2 element3...?
446 The subcommand creates a list of length "size * number of ele‐
447 ments" by repeating size times the sequence of elements element1
448 element2 .... size must be a positive integer, elementn can be
449 any Tcl value. Note that repeat 1 arg ... is identical to list
450 arg ..., though the arg is required with repeat.
451 Examples:
453 tclsh> ::struct::list repeat 3 a
457 a a a
458 tclsh> ::struct::list repeat 3 [::struct::list repeat 3 0]
459 {0 0 0} {0 0 0} {0 0 0}
460 tclsh> ::struct::list repeat 3 a b c
461 a b c a b c a b c
462 tclsh> ::struct::list repeat 3 [::struct::list repeat 2 a] b c
463 {a a} b c {a a} b c {a a} b c
464 ::struct::list repeatn value size...
467 The subcommand creates a (nested) list containing the value in
468 all positions. The exact size and degree of nesting is deter‐
469 mined by the size arguments, all of which have to be integer
470 numbers greater than or equal to zero.
471 A single argument size which is a list of more than one element
473 will be treated as if more than argument size was specified.
474 If only one argument size is present the returned list will not
476 be nested, of length size and contain value in all positions.
477 If more than one size argument is present the returned list will
478 be nested, and of the length specified by the last size argument
479 given to it. The elements of that list are defined as the result
480 of Repeat for the same arguments, but with the last size value
481 removed.
482 An empty list will be returned if no size arguments are present.
484 tclsh> ::struct::list repeatn 0 3 4
488 {0 0 0} {0 0 0} {0 0 0} {0 0 0}
489 tclsh> ::struct::list repeatn 0 {3 4}
490 {0 0 0} {0 0 0} {0 0 0} {0 0 0}
491 tclsh> ::struct::list repeatn 0 {3 4 5}
492 {{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}}
493 ::struct::list dbJoin ?-inner|-left|-right|-full? ?-keys varname? {key‐
496 col table}...
497 The method performs a table join according to relational alge‐
498 bra. The execution of any of the possible outer join operation
499 is triggered by the presence of either option -left, -right, or
500 -full. If none of these options is present a regular inner join
501 will be performed. This can also be triggered by specifying -in‐
502 ner. The various possible join operations are explained in de‐
503 tail in section TABLE JOIN.
504 If the -keys is present its argument is the name of a variable
506 to store the full list of found keys into. Depending on the ex‐
507 act nature of the input table and the join mode the output table
508 may not contain all the keys by default. In such a case the
509 caller can declare a variable for this information and then in‐
510 sert it into the output table on its own, as she will have more
511 information about the placement than this command.
512 What is left to explain is the format of the arguments.
514 The keycol arguments are the indices of the columns in the ta‐
516 bles which contain the key values to use for the joining. Each
517 argument applies to the table following immediately after it.
518 The columns are counted from 0, which references the first col‐
519 umn. The table associated with the column index has to have at
520 least keycol+1 columns. An error will be thrown if there are
521 less.
522 The table arguments represent a table or matrix of rows and col‐
524 umns of values. We use the same representation as generated and
525 consumed by the methods get rect and set rect of matrix objects.
526 In other words, each argument is a list, representing the whole
527 matrix. Its elements are lists too, each representing a single
528 rows of the matrix. The elements of the row-lists are the column
529 values.
530 The table resulting from the join operation is returned as the
532 result of the command. We use the same representation as de‐
533 scribed above for the input tables.
534 ::struct::list dbJoinKeyed ?-inner|-left|-right|-full? ?-keys varname?
536 table...
537 The operations performed by this method are the same as de‐
538 scribed above for dbJoin. The only difference is in the specifi‐
539 cation of the keys to use. Instead of using column indices sepa‐
540 rate from the table here the keys are provided within the table
541 itself. The row elements in each table are not the lists of col‐
542 umn values, but a two-element list where the second element is
543 the regular list of column values and the first element is the
544 key to use.
545 ::struct::list swap listvar i j
547 The subcommand exchanges the elements at the indices i and j in
548 the list stored in the variable named by listvar. The list is
549 modified in place, and also returned as the result of the sub‐
550 command.
551 ::struct::list firstperm list
553 This subcommand returns the lexicographically first permutation
554 of the input list.
555 ::struct::list nextperm perm
557 This subcommand accepts a permutation of a set of elements (pro‐
558 vided by perm) and returns the next permutatation in lexico‐
559 graphic sequence.
560 The algorithm used here is by Donal E. Knuth, see section REFER‐
562 ENCES for details.
563 ::struct::list permutations list
565 This subcommand returns a list containing all permutations of
566 the input list in lexicographic order.
567 ::struct::list foreachperm var list body
569 This subcommand executes the script body once for each permuta‐
570 tion of the specified list. The permutations are visited in lex‐
571 icographic order, and the variable var is set to the permutation
572 for which body is currently executed. The result of the loop
573 command is the empty string.
574
576 The longestCommonSubsequence subcommand forms the core of a flexible
577 system for doing differential comparisons of files, similar to the ca‐
578 pability offered by the Unix command diff. While this procedure is
579 quite rapid for many tasks of file comparison, its performance degrades
580 severely if sequence2 contains many equal elements (as, for instance,
581 when using this procedure to compare two files, a quarter of whose
582 lines are blank. This drawback is intrinsic to the algorithm used (see
583 the Reference for details).
584 One approach to dealing with the performance problem that is sometimes
586 effective in practice is arbitrarily to exclude elements that appear
587 more than a certain number of times. This number is provided as the
588 maxOccurs parameter. If frequent lines are excluded in this manner,
589 they will not appear in the common subsequence that is computed; the
590 result will be the longest common subsequence of infrequent elements.
591 The procedure longestCommonSubsequence2 implements this heuristic. It
592 functions as a wrapper around longestCommonSubsequence; it computes the
593 longest common subsequence of infrequent elements, and then subdivides
594 the subsequences that lie between the matches to approximate the true
595 longest common subsequence.
596
598 This is an operation from relational algebra for relational databases.
599 The easiest way to understand the regular inner join is that it creates
601 the cartesian product of all the tables involved first and then keeps
602 only all those rows in the resulting table for which the values in the
603 specified key columns are equal to each other.
604 Implementing this description naively, i.e. as described above will
606 generate a huge intermediate result. To avoid this the cartesian prod‐
607 uct and the filtering of row are done at the same time. What is re‐
608 quired is a fast way to determine if a key is present in a table. In a
609 true database this is done through indices. Here we use arrays inter‐
610 nally.
611 An outer join is an extension of the inner join for two tables. There
613 are three variants of outerjoins, called left, right, and full outer
614 joins. Their result always contains all rows from an inner join and
615 then some additional rows.
616 [1] For the left outer join the additional rows are all rows from
618 the left table for which there is no key in the right table.
619 They are joined to an empty row of the right table to fit them
620 into the result.
621 [2] For the right outer join the additional rows are all rows from
623 the right table for which there is no key in the left table.
624 They are joined to an empty row of the left table to fit them
625 into the result.
626 [3] The full outer join combines both left and right outer join. In
628 other words, the additional rows are as defined for left outer
629 join, and right outer join, combined.
630 We extend all the joins from two to n tables (n > 2) by executing
632 (...((table1 join table2) join table3) ...) join tableN
635 Examples for all the joins:
638 Inner Join
641 {0 foo} {0 bagel} {0 foo 0 bagel}
643 {1 snarf} inner join {1 snatz} = {1 snarf 1 snatz}
644 {2 blue} {3 driver}
645 Left Outer Join
647 {0 foo} {0 bagel} {0 foo 0 bagel}
649 {1 snarf} left outer join {1 snatz} = {1 snarf 1 snatz}
650 {2 blue} {3 driver} {2 blue {} {}}
651 Right Outer Join
653 {0 foo} {0 bagel} {0 foo 0 bagel}
655 {1 snarf} right outer join {1 snatz} = {1 snarf 1 snatz}
656 {2 blue} {3 driver} {{} {} 3 driver}
657 Full Outer Join
659 {0 foo} {0 bagel} {0 foo 0 bagel}
661 {1 snarf} full outer join {1 snatz} = {1 snarf 1 snatz}
662 {2 blue} {3 driver} {2 blue {} {}}
663 {{} {} 3 driver}
664
667 [1] J. W. Hunt and M. D. McIlroy, "An algorithm for differential
668 file comparison," Comp. Sci. Tech. Rep. #41, Bell Telephone Lab‐
669 oratories (1976). Available on the Web at the second author's
670 personal site: http://www.cs.dartmouth.edu/~doug/
671 [2] Donald E. Knuth, "Fascicle 2b of 'The Art of Computer Program‐
673 ming' volume 4". Available on the Web at the author's personal
674 site: http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz.
675
677 This document, and the package it describes, will undoubtedly contain
678 bugs and other problems. Please report such in the category struct ::
679 list of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist].
680 Please also report any ideas for enhancements you may have for either
681 package and/or documentation.
682 When proposing code changes, please provide unified diffs, i.e the out‐
684 put of diff -u.
685 Note further that attachments are strongly preferred over inlined
687 patches. Attachments can be made by going to the Edit form of the
688 ticket immediately after its creation, and then using the left-most
689 button in the secondary navigation bar.
690
692 Fisher-Yates, assign, common, comparison, diff, differential, equal,
693 equality, filter, first permutation, flatten, folding, full outer join,
694 generate permutations, inner join, join, left outer join, list, longest
695 common subsequence, map, next permutation, outer join, permutation, re‐
696 duce, repeating, repetition, reshuffle, reverse, right outer join,
697 shuffle, subsequence, swapping
698
700 Data structures
701
703 Copyright (c) 2003-2005 by Kevin B. Kenny. All rights reserved
704 Copyright (c) 2003-2012 Andreas Kupries <andreas_kupries@users.sourceforge.net>
705tcllib 1.8.5 struct::list(n)