1struct::list(n) Tcl Data Structures struct::list(n)
2______________________________________________________________________________
6
8 struct::list - Procedures for manipulating lists
9
11 package require Tcl 8.0
12 package require struct::list ?1.6?
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 assign sequence varname ?varname?...
31 ::struct::list flatten ?-full? ?--? sequence
33 ::struct::list map sequence cmdprefix
35 ::struct::list mapfor var sequence script
37 ::struct::list filter sequence cmdprefix
39 ::struct::list filterfor var sequence expr
41 ::struct::list split sequence cmdprefix ?passVar failVar?
43 ::struct::list fold sequence initialvalue cmdprefix
45 ::struct::list shift listvar
47 ::struct::list iota n
49 ::struct::list equal a b
51 ::struct::list repeat size element1 ?element2 element3...?
53 ::struct::list repeatn value size...
55 ::struct::list dbJoin ?-inner|-left|-right|-full? ?-keys varname? {key‐
57 col table}...
58 ::struct::list dbJoinKeyed ?-inner|-left|-right|-full? ?-keys varname?
60 table...
61 ::struct::list swap listvar i j
63 ::struct::list firstperm list
65 ::struct::list nextperm perm
67 ::struct::list permutations list
69 ::struct::list foreachperm var list body
71_________________________________________________________________
73
75 The ::struct::list namespace contains several useful commands for pro‐
76 cessing Tcl lists. Generally speaking, they implement algorithms more
77 complex or specialized than the ones provided by Tcl itself.
78 It exports only a single command, struct::list. All functionality pro‐
80 vided here can be reached through a subcommand of this command.
81
83 ::struct::list longestCommonSubsequence sequence1 sequence2 ?maxOccurs?
84 Returns the longest common subsequence of elements in the two
85 lists sequence1 and sequence2. If the maxOccurs parameter is
86 provided, the common subsequence is restricted to elements that
87 occur no more than maxOccurs times in sequence2.
88 The return value is a list of two lists of equal length. The
90 first sublist is of indices into sequence1, and the second sub‐
91 list is of indices into sequence2. Each corresponding pair of
92 indices corresponds to equal elements in the sequences; the
93 sequence returned is the longest possible.
94 ::struct::list longestCommonSubsequence2 sequence1 sequence2 ?maxOc‐
96 curs?
97 Returns an approximation to the longest common sequence of ele‐
98 ments in the two lists sequence1 and sequence2. If the maxOc‐
99 curs parameter is omitted, the subsequence computed is exactly
100 the longest common subsequence; otherwise, the longest common
101 subsequence is approximated by first determining the longest
102 common sequence of only those elements that occur no more than
103 maxOccurs times in sequence2, and then using that result to
104 align the two lists, determining the longest common subsequences
105 of the sublists between the two elements.
106 As with longestCommonSubsequence, the return value is a list of
108 two lists of equal length. The first sublist is of indices into
109 sequence1, and the second sublist is of indices into sequence2.
110 Each corresponding pair of indices corresponds to equal elements
111 in the sequences. The sequence approximates the longest common
112 subsequence.
113 ::struct::list lcsInvert lcsData len1 len2
115 This command takes a description of a longest common subsequence
116 (lcsData), inverts it, and returns the result. Inversion means
117 here that as the input describes which parts of the two
118 sequences are identical the output describes the differences
119 instead.
120 To be fully defined the lengths of the two sequences have to be
122 known and are specified through len1 and len2.
123 The result is a list where each element describes one chunk of
125 the differences between the two sequences. This description is a
126 list containing three elements, a type and two pairs of indices
127 into sequence1 and sequence2 respectively, in this order. The
128 type can be one of three values:
129 added Describes an addition. I.e. items which are missing in
131 sequence1 can be found in sequence2. The pair of indices
132 into sequence1 describes where the added range had been
133 expected to be in sequence1. The first index refers to
134 the item just before the added range, and the second
135 index refers to the item just after the added range. The
136 pair of indices into sequence2 describes the range of
137 items which has been added to it. The first index refers
138 to the first item in the range, and the second index
139 refers to the last item in the range.
140 deleted
142 Describes a deletion. I.e. items which are in sequence1
143 are missing from sequence2. The pair of indices into
144 sequence1 describes the range of items which has been
145 deleted. The first index refers to the first item in the
146 range, and the second index refers to the last item in
147 the range. The pair of indices into sequence2 describes
148 where the deleted range had been expected to be in
149 sequence2. The first index refers to the item just before
150 the deleted range, and the second index refers to the
151 item just after the deleted range.
152 changed
154 Describes a general change. I.e a range of items in
155 sequence1 has been replaced by a different range of items
156 in sequence2. The pair of indices into sequence1
157 describes the range of items which has been replaced. The
158 first index refers to the first item in the range, and
159 the second index refers to the last item in the range.
160 The pair of indices into sequence2 describes the range of
161 items replacing the original range. Again the first index
162 refers to the first item in the range, and the second
163 index refers to the last item in the range.
164 sequence 1 = {a b r a c a d a b r a}
167 lcs 1 = {1 2 4 5 8 9 10}
168 lcs 2 = {0 1 3 4 5 6 7}
169 sequence 2 = {b r i c a b r a c}
170 Inversion = {{deleted {0 0} {-1 0}}
172 {changed {3 3} {2 2}}
173 {deleted {6 7} {4 5}}
174 {added {10 11} {8 8}}}
175 Notes:
177 · An index of -1 in a deleted chunk refers to just before
180 the first element of the second sequence.
181 · Also an index equal to the length of the first sequence
183 in an added chunk refers to just behind the end of the
184 sequence.
185 ::struct::list lcsInvert2 lcs1 lcs2 len1 len2
187 Similar to lcsInvert. Instead of directly taking the result of a
188 call to longestCommonSubsequence this subcommand expects the
189 indices for the two sequences in two separate lists.
190 ::struct::list lcsInvertMerge lcsData len1 len2
192 Similar to lcsInvert. It returns essentially the same structure
193 as that command, except that it may contain chunks of type
194 unchanged too.
195 These new chunks describe the parts which are unchanged between
197 the two sequences. This means that the result of this command
198 describes both the changed and unchanged parts of the two
199 sequences in one structure.
200 sequence 1 = {a b r a c a d a b r a}
203 lcs 1 = {1 2 4 5 8 9 10}
204 lcs 2 = {0 1 3 4 5 6 7}
205 sequence 2 = {b r i c a b r a c}
206 Inversion/Merge = {{deleted {0 0} {-1 0}}
208 {unchanged {1 2} {0 1}}
209 {changed {3 3} {2 2}}
210 {unchanged {4 5} {3 4}}
211 {deleted {6 7} {4 5}}
212 {unchanged {8 10} {5 7}}
213 {added {10 11} {8 8}}}
214 ::struct::list lcsInvertMerge2 lcs1 lcs2 len1 len2
217 Similar to lcsInvertMerge. Instead of directly taking the result
218 of a call to longestCommonSubsequence this subcommand expects
219 the indices for the two sequences in two separate lists.
220 ::struct::list reverse sequence
222 The subcommand takes a single sequence as argument and returns a
223 new sequence containing the elements of the input sequence in
224 reverse order.
225 ::struct::list assign sequence varname ?varname?...
227 The subcommand assigns the first n elements of the input
228 sequence to the one or more variables whose names were listed
229 after the sequence, where n is the number of specified vari‐
230 ables.
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
241 c d e
242 tclsh> set foo
243 a
244 tclsh> set bar
245 b
246 ::struct::list flatten ?-full? ?--? sequence
249 The subcommand takes a single sequence and returns a new
250 sequence where one level of nesting was removed from the input
251 sequence. In other words, the sublists in the input sequence are
252 replaced by their elements.
253 The subcommand will remove any nesting it finds if the option
255 -full is specified.
256 tclsh> ::struct::list flatten {1 2 3 {4 5} {6 7} {{8 9}} 10}
258 1 2 3 4 5 6 7 {8 9} 10
259 tclsh> ::struct::list flatten -full {1 2 3 {4 5} {6 7} {{8 9}} 10}
260 1 2 3 4 5 6 7 8 9 10
261 ::struct::list map sequence cmdprefix
264 The subcommand takes a sequence to operate on and a command pre‐
265 fix (cmdprefix) specifying an operation, applies the command
266 prefix to each element of the sequence and returns a sequence
267 consisting of the results of that application.
268 The command prefix will be evaluated with a single word appended
270 to it. The evaluation takes place in the context of the caller
271 of the subcommand.
272 tclsh> # squaring all elements in a list
275 tclsh> proc sqr {x} {expr {$x*$x}}
277 tclsh> ::struct::list map {1 2 3 4 5} sqr
278 1 4 9 16 25
279 tclsh> # Retrieving the second column from a matrix
281 tclsh> # given as list of lists.
282 tclsh> proc projection {n list} {::lindex $list $n}
284 tclsh> ::struct::list map {{a b c} {1 2 3} {d f g}} {projection 1}
285 b 2 f
286 ::struct::list mapfor var sequence script
289 The subcommand takes a sequence to operate on and a tcl script,
290 applies the script to each element of the sequence and returns a
291 sequence consisting of the results of that application.
292 The script will be evaluated as is, and has access to the cur‐
294 rent list element through the specified iteration variable var.
295 The evaluation takes place in the context of the caller of the
296 subcommand.
297 tclsh> # squaring all elements in a list
300 tclsh> ::struct::list mapfor x {1 2 3 4 5} {
302 expr {$x * $x}
303 }
304 1 4 9 16 25
305 tclsh> # Retrieving the second column from a matrix
307 tclsh> # given as list of lists.
308 tclsh> ::struct::list mapfor x {{a b c} {1 2 3} {d f g}} {
310 lindex $x 1
311 }
312 b 2 f
313 ::struct::list filter sequence cmdprefix
316 The subcommand takes a sequence to operate on and a command pre‐
317 fix (cmdprefix) specifying an operation, applies the command
318 prefix to each element of the sequence and returns a sequence
319 consisting of all elements of the sequence for which the command
320 prefix returned true. In other words, this command filters out
321 all elements of the input sequence which fail the test the cmd‐
322 prefix represents, and returns the remaining elements.
323 The command prefix will be evaluated with a single word appended
325 to it. The evaluation takes place in the context of the caller
326 of the subcommand.
327 tclsh> # removing all odd numbers from the input
330 tclsh> proc even {x} {expr {($x % 2) == 0}}
332 tclsh> ::struct::list filter {1 2 3 4 5} even
333 2 4
334 Note: The filter is a specialized application of fold where the
337 result is extended with the current item or not, depending o
338 nthe result of the test.
339 ::struct::list filterfor var sequence expr
341 The subcommand takes a sequence to operate on and a tcl expres‐
342 sion (expr) specifying a condition, applies the conditionto each
343 element of the sequence and returns a sequence consisting of all
344 elements of the sequence for which the expression returned true.
345 In other words, this command filters out all elements of the
346 input sequence which fail the test the condition expr repre‐
347 sents, and returns the remaining elements.
348 The expression will be evaluated as is, and has access to the
350 current list element through the specified iteration variable
351 var. The evaluation takes place in the context of the caller of
352 the subcommand.
353 tclsh> # removing all odd numbers from the input
356 tclsh> ::struct::list filterfor x {1 2 3 4 5} {expr {($x % 2) == 0}}
358 2 4
359 ::struct::list split sequence cmdprefix ?passVar failVar?
362 This is a variant of method filter, see above. Instead of
363 returning just the elements passing the test we get lists of
364 both passing and failing elements.
365 If no variable names are specified then the result of the com‐
367 mand will be a list containing the list of passing elements, and
368 the list of failing elements, in this order. Otherwise the lists
369 of passing and failing elements are stored into the two speci‐
370 fied variables, and the result will be a list containing two
371 numbers, the number of elements passing the test, and the number
372 of elements failing, in this order.
373 The interface to the test is the same as used by filter.
375 ::struct::list fold sequence initialvalue cmdprefix
377 The subcommand takes a sequence to operate on, an arbitrary
378 string initial value and a command prefix (cmdprefix) specifying
379 an operation.
380 The command prefix will be evaluated with two words appended to
382 it. The second of these words will always be an element of the
383 sequence. The evaluation takes place in the context of the call‐
384 er of the subcommand.
385 It then reduces the sequence into a single value through
387 repeated application of the command prefix and returns that
388 value. This reduction is done by
389 1 Application of the command to the initial value and the
391 first element of the list.
392 2 Application of the command to the result of the last call
394 and the second element of the list.
395 i
398 Application of the command to the result of the
399 last call and the i'th element of the list.
400 end
403 Application of the command to the
404 result of the last call and the last
405 element of the list. The result of
406 this call is returned as the result
407 of the subcommand.
408 tclsh> # summing the elements in a list.
411 tclsh> proc + {a b} {expr {$a + $b}}
412 tclsh> ::struct::list fold {1 2 3 4 5} 0 +
413 15
414 ::struct::list shift listvar
417 The subcommand takes the list con‐
418 tained in the variable named by
419 listvar and shifts it down one ele‐
420 ment. After the call listvar will
421 contain a list containing the second
422 to last elements of the input list.
423 The first element of the ist is
424 returned as the result of the com‐
425 mand. Shifting the empty list does
426 nothing.
427 ::struct::list iota n
429 The subcommand returns a list con‐
430 taining the integer numbers in the
431 range [0,n). The element at index i
432 of the list contain the number i.
433 For "n == 0" an empty list will be
435 returned.
436 ::struct::list equal a b
438 The subcommand compares the two
439 lists a and b for equality. In other
440 words, they have to be of the same
441 length and have to contain the same
442 elements in the same order. If an
443 element is a list the same defini‐
444 tion of equality applies recur‐
445 sively.
446 A boolean value will be returned as
448 the result of the command. This
449 value will be true if the two lists
450 are equal, and false else.
451 ::struct::list repeat size element1 ?ele‐
453 ment2 element3...?
454 The subcommand creates a list of
455 length "size * number of elements"
456 by repeating size times the sequence
457 of elements element1 element2 ....
458 size must be a positive integer,
459 elementn can be any Tcl value. Note
460 that repeat 1 arg ... is identical
461 to list arg ..., though the arg is
462 required with repeat.
463 Examples:
465 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)
479 list containing the value in all
480 positions. The exact size and degree
481 of nesting is determined by the size
482 arguments, all of which have to be
483 integer numbers greater than or
484 equal to zero.
485 A single argument size which is a
487 list of more than one element will
488 be treated as if more than argument
489 size was specified.
490 If only one argument size is present
492 the returned list will not be
493 nested, of length size and contain
494 value in all positions. If more
495 than one size argument is present
496 the returned list will be nested,
497 and of the length specified by the
498 last size argument given to it. The
499 elements of that list are defined as
500 the result of Repeat for the same
501 arguments, but with the last size
502 value removed.
503 An empty list will be returned if no
505 size arguments are present.
506 tclsh> ::struct::list repeatn 0 3 4
509 {0 0 0} {0 0 0} {0 0 0} {0 0 0}
510 tclsh> ::struct::list repeatn 0 {3 4}
511 {0 0 0} {0 0 0} {0 0 0} {0 0 0}
512 tclsh> ::struct::list repeatn 0 {3 4 5}
513 {{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}}
514 ::struct::list dbJoin
517 ?-inner|-left|-right|-full? ?-keys varname?
518 {keycol table}...
519 The method performs a table join
520 according to relational algebra. The
521 execution of any of the possible
522 outer join operation is triggered by
523 the presence of either option -left,
524 -right, or -full. If none of these
525 options is present a regular inner
526 join will be performed. This can
527 also be triggered by specifying
528 -inner. The various possible join
529 operations are explained in detail
530 in section TABLE JOIN.
531 If the -keys is present its argument
533 is the name of a variable to store
534 the full list of found keys into.
535 Depending on the exact nature of the
536 input table and the join mode the
537 output table may not contain all the
538 keys by default. In such a case the
539 caller can declare a variable for
540 this information and then insert it
541 into the output table on its own, as
542 she will have more information about
543 the placement than this command.
544 What is left to explain is the for‐
546 mat of the arguments.
547 The keycol arguments are the indices
549 of the columns in the tables which
550 contain the key values to use for
551 the joining. Each argument applies
552 to the table following immediately
553 after it. The columns are counted
554 from 0, which references the first
555 column. The table associated with
556 the column index has to have at
557 least keycol+1 columns. An error
558 will be thrown if there are less.
559 The table arguments represent a ta‐
561 ble or matrix of rows and columns of
562 values. We use the same representa‐
563 tion as generated and consumed by
564 the methods get rect and set rect of
565 matrix objects. In other words, each
566 argument is a list, representing the
567 whole matrix. Its elements are
568 lists too, each representing a sin‐
569 gle rows of the matrix. The elements
570 of the row-lists are the column val‐
571 ues.
572 The table resulting from the join
574 operation is returned as the result
575 of the command. We use the same rep‐
576 resentation as described above for
577 the input tables.
578 ::struct::list dbJoinKeyed
580 ?-inner|-left|-right|-full? ?-keys varname?
581 table...
582 The operations performed by this
583 method are the same as described
584 above for dbJoin. The only differ‐
585 ence is in the specification of the
586 keys to use. Instead of using column
587 indices separate from the table here
588 the keys are provided within the ta‐
589 ble itself. The row elements in each
590 table are not the lists of column
591 values, but a two-element list where
592 the second element is the regular
593 list of column values and the first
594 element is the key to use.
595 ::struct::list swap listvar i j
597 The subcommand exchanges the ele‐
598 ments at the indices i and j in the
599 list stored in the variable named by
600 listvar. The list is modified in
601 place, and also returned as the
602 result of the subcommand.
603 ::struct::list firstperm list
605 This subcommand returns the lexico‐
606 graphically first permutation of the
607 input list.
608 ::struct::list nextperm perm
610 This subcommand accepts a permuta‐
611 tion of a set of elements (provided
612 by perm) and returns the next permu‐
613 tatation in lexicographic sequence.
614 The algorithm used here is by Donal
616 E. Knuth, see section REFERENCES for
617 details.
618 ::struct::list permutations list
620 This subcommand returns a list con‐
621 taining all permutations of the
622 input list in lexicographic order.
623 ::struct::list foreachperm var list body
625 This subcommand executes the script
626 body once for each permutation of
627 the specified list. The permutations
628 are visited in lexicographic order,
629 and the variable var is set to the
630 permutation for which body is cur‐
631 rently executed. The result of the
632 loop command is the empty string.
633
635 The longestCommonSubsequence subcommand
636 forms the core of a flexible system for
637 doing differential comparisons of files,
638 similar to the capability offered by the
639 Unix command diff. While this procedure is
640 quite rapid for many tasks of file compari‐
641 son, its performance degrades severely if
642 sequence2 contains many equal elements (as,
643 for instance, when using this procedure to
644 compare two files, a quarter of whose lines
645 are blank. This drawback is intrinsic to
646 the algorithm used (see the Reference for
647 details).
648 One approach to dealing with the perfor‐
650 mance problem that is sometimes effective
651 in practice is arbitrarily to exclude ele‐
652 ments that appear more than a certain num‐
653 ber of times. This number is provided as
654 the maxOccurs parameter. If frequent lines
655 are excluded in this manner, they will not
656 appear in the common subsequence that is
657 computed; the result will be the longest
658 common subsequence of infrequent elements.
659 The procedure longestCommonSubsequence2
660 implements this heuristic. It functions as
661 a wrapper around longestCommonSubsequence;
662 it computes the longest common subsequence
663 of infrequent elements, and then subdivides
664 the subsequences that lie between the
665 matches to approximate the true longest
666 common subsequence.
667
669 This is an operation from relational alge‐
670 bra for relational databases.
671 The easiest way to understand the regular
673 inner join is that it creates the cartesian
674 product of all the tables involved first
675 and then keeps only all those rows in the
676 resulting table for which the values in the
677 specified key columns are equal to each
678 other.
679 Implementing this description naively, i.e.
681 as described above will generate a huge
682 intermediate result. To avoid this the
683 cartesian product and the filtering of row
684 are done at the same time. What is required
685 is a fast way to determine if a key is
686 present in a table. In a true database this
687 is done through indices. Here we use arrays
688 internally.
689 An outer join is an extension of the inner
691 join for two tables. There are three vari‐
692 ants of outerjoins, called left, right, and
693 full outer joins. Their result always con‐
694 tains all rows from an inner join and then
695 some additional rows.
696 [1] For the left outer join the addi‐
698 tional rows are all rows from the
699 left table for which there is no key
700 in the right table. They are joined
701 to an empty row of the right table
702 to fit them into the result.
703 [2] For the right outer join the addi‐
705 tional rows are all rows from the
706 right table for which there is no
707 key in the left table. They are
708 joined to an empty row of the left
709 table to fit them into the result.
710 [3] The full outer join combines both
712 left and right outer join. In other
713 words, the additional rows are as
714 defined for left outer join, and
715 right outer join, combined.
716 We extend all the joins from two to n
718 tables (n > 2) by executing
719 (...((table1 join table2) join table3) ...) join tableN
721 Examples for all the joins:
724 Inner Join
726 {0 foo} {0 bagel} {0 foo 0 bagel}
728 {1 snarf} inner join {1 snatz} = {1 snarf 1 snatz}
729 {2 blue} {3 driver}
730 Left Outer Join
732 {0 foo} {0 bagel} {0 foo 0 bagel}
734 {1 snarf} left outer join {1 snatz} = {1 snarf 1 snatz}
735 {2 blue} {3 driver} {2 blue {} {}}
736 Right Outer Join
738 {0 foo} {0 bagel} {0 foo 0 bagel}
740 {1 snarf} right outer join {1 snatz} = {1 snarf 1 snatz}
741 {2 blue} {3 driver} {{} {} 3 driver}
742 Full Outer Join
744 {0 foo} {0 bagel} {0 foo 0 bagel}
746 {1 snarf} full outer join {1 snatz} = {1 snarf 1 snatz}
747 {2 blue} {3 driver} {2 blue {} {}}
748 {{} {} 3 driver}
749
752 [1] J. W. Hunt and M. D. McIlroy, "An
753 algorithm for differential file com‐
754 parison," Comp. Sci. Tech. Rep. #41,
755 Bell Telephone Laboratories (1976).
756 Available on the Web at the second
757 author's personal site:
758 http://www.cs.dartmouth.edu/~doug/
759 [2] Donald E. Knuth, "Fascicle 2b of
761 'The Art of Computer Programming'
762 volume 4". Available on the Web at
763 the author's personal site:
764 http://www-cs-faculty.stan‐
765 ford.edu/~knuth/fasc2b.ps.gz.
766
768 assign, common, comparison, diff, differen‐
769 tial, equal, equality, filter, first permu‐
770 tation, flatten, folding, full outer join,
771 generate permutations, inner join, join,
772 left outer join, list, longest common sub‐
773 sequence, map, next permutation, outer
774 join, permutation, reduce, repeating, repe‐
775 tition, reverse, right outer join, subse‐
776 quence, swapping
777
779 Copyright (c) 2003-2005 by Kevin B. Kenny. All rights reserved
780 Copyright (c) 2003-2006 Andreas Kupries <andreas_kupries@users.sourceforge.net>
781struct 1.6 struct::list(n)