1[comment {-*- tcl -*- doctools manpage}] 2[comment {$Id: struct_list.man,v 1.23 2009/01/29 06:16:20 andreas_kupries Exp $}] 3[manpage_begin struct::list n 1.7] 4[copyright {2003-2005 by Kevin B. Kenny. All rights reserved}] 5[copyright {2003-2008 Andreas Kupries <andreas_kupries@users.sourceforge.net>}] 6[moddesc {Tcl Data Structures}] 7[titledesc {Procedures for manipulating lists}] 8[category {Data structures}] 9[require Tcl 8.0] 10[require struct::list [opt 1.7]] 11[description] 12 13[para] 14 15The [cmd ::struct::list] namespace contains several useful commands 16for processing Tcl lists. Generally speaking, they implement 17algorithms more complex or specialized than the ones provided by Tcl 18itself. 19 20[para] 21 22It exports only a single command, [cmd struct::list]. All 23functionality provided here can be reached through a subcommand of 24this command. 25 26[section COMMANDS] 27[list_begin definitions] 28 29[call [cmd ::struct::list] [method longestCommonSubsequence] \ 30 [arg sequence1] [arg sequence2] [opt [arg maxOccurs]]] 31 32Returns the longest common subsequence of elements in the two lists 33[arg sequence1] and [arg sequence2]. If the [arg maxOccurs] parameter 34is provided, the common subsequence is restricted to elements that 35occur no more than [arg maxOccurs] times in [arg sequence2]. 36 37[para] 38 39The return value is a list of two lists of equal length. The first 40sublist is of indices into [arg sequence1], and the second sublist is 41of indices into [arg sequence2]. Each corresponding pair of indices 42corresponds to equal elements in the sequences; the sequence returned 43is the longest possible. 44 45[call [cmd ::struct::list] [method longestCommonSubsequence2] \ 46 [arg {sequence1 sequence2}] [opt [arg maxOccurs]]] 47 48Returns an approximation to the longest common sequence of elements in 49the two lists [arg sequence1] and [arg sequence2]. 50 51If the [arg maxOccurs] parameter is omitted, the subsequence computed 52is exactly the longest common subsequence; otherwise, the longest 53common subsequence is approximated by first determining the longest 54common sequence of only those elements that occur no more than 55 56[arg maxOccurs] times in [arg sequence2], and then using that result 57to align the two lists, determining the longest common subsequences of 58the sublists between the two elements. 59 60[para] 61 62As with [method longestCommonSubsequence], the return value is a list 63of two lists of equal length. The first sublist is of indices into 64[arg sequence1], and the second sublist is of indices into 65 66[arg sequence2]. Each corresponding pair of indices corresponds to 67equal elements in the sequences. The sequence approximates the 68longest common subsequence. 69 70 71[call [cmd ::struct::list] [method lcsInvert] [arg lcsData] [arg len1] [arg len2]] 72 73This command takes a description of a longest common subsequence 74 75([arg lcsData]), inverts it, and returns the result. Inversion means 76here that as the input describes which parts of the two sequences are 77identical the output describes the differences instead. 78 79[para] 80 81To be fully defined the lengths of the two sequences have to be known 82and are specified through [arg len1] and [arg len2]. 83 84[para] 85 86The result is a list where each element describes one chunk of the 87differences between the two sequences. This description is a list 88containing three elements, a type and two pairs of indices into 89 90[arg sequence1] and [arg sequence2] respectively, in this order. 91 92The type can be one of three values: 93 94[list_begin definitions] 95[def [const added]] 96 97Describes an addition. I.e. items which are missing in [arg sequence1] 98can be found in [arg sequence2]. 99 100The pair of indices into [arg sequence1] describes where the added 101range had been expected to be in [arg sequence1]. The first index 102refers to the item just before the added range, and the second index 103refers to the item just after the added range. 104 105The pair of indices into [arg sequence2] describes the range of items 106which has been added to it. The first index refers to the first item 107in the range, and the second index refers to the last item in the 108range. 109 110[def [const deleted]] 111 112Describes a deletion. I.e. items which are in [arg sequence1] are 113missing from [arg sequence2]. 114 115The pair of indices into [arg sequence1] describes the range of items 116which has been deleted. The first index refers to the first item in 117the range, and the second index refers to the last item in the range. 118 119The pair of indices into [arg sequence2] describes where the deleted 120range had been expected to be in [arg sequence2]. The first index 121refers to the item just before the deleted range, and the second index 122refers to the item just after the deleted range. 123 124[def [const changed]] 125 126Describes a general change. I.e a range of items in [arg sequence1] 127has been replaced by a different range of items in [arg sequence2]. 128 129The pair of indices into [arg sequence1] describes the range of items 130which has been replaced. The first index refers to the first item in 131the range, and the second index refers to the last item in the range. 132 133The pair of indices into [arg sequence2] describes the range of items 134replacing the original range. Again the first index refers to the 135first item in the range, and the second index refers to the last item 136in the range. 137 138[list_end] 139 140[para] 141[example { 142 sequence 1 = {a b r a c a d a b r a} 143 lcs 1 = {1 2 4 5 8 9 10} 144 lcs 2 = {0 1 3 4 5 6 7} 145 sequence 2 = {b r i c a b r a c} 146 147 Inversion = {{deleted {0 0} {-1 0}} 148 {changed {3 3} {2 2}} 149 {deleted {6 7} {4 5}} 150 {added {10 11} {8 8}}} 151}] 152 153[emph Notes:] 154[para] 155[list_begin itemized] 156[item] 157An index of [const -1] in a [term deleted] chunk refers to just before 158the first element of the second sequence. 159 160[item] 161Also an index equal to the length of the first sequence in an 162[term added] chunk refers to just behind the end of the sequence. 163 164[list_end] 165 166 167[call [cmd ::struct::list] [method lcsInvert2] [arg lcs1] [arg lcs2] [arg len1] [arg len2]] 168 169Similar to [method lcsInvert]. Instead of directly taking the result 170of a call to [method longestCommonSubsequence] this subcommand expects 171the indices for the two sequences in two separate lists. 172 173 174[call [cmd ::struct::list] [method lcsInvertMerge] [arg lcsData] [arg len1] [arg len2]] 175 176Similar to [method lcsInvert]. It returns essentially the same 177structure as that command, except that it may contain chunks of type 178[const unchanged] too. 179 180[para] 181 182These new chunks describe the parts which are unchanged between the 183two sequences. This means that the result of this command describes 184both the changed and unchanged parts of the two sequences in one 185structure. 186 187[para] 188[example { 189 sequence 1 = {a b r a c a d a b r a} 190 lcs 1 = {1 2 4 5 8 9 10} 191 lcs 2 = {0 1 3 4 5 6 7} 192 sequence 2 = {b r i c a b r a c} 193 194 Inversion/Merge = {{deleted {0 0} {-1 0}} 195 {unchanged {1 2} {0 1}} 196 {changed {3 3} {2 2}} 197 {unchanged {4 5} {3 4}} 198 {deleted {6 7} {4 5}} 199 {unchanged {8 10} {5 7}} 200 {added {10 11} {8 8}}} 201}] 202 203 204[call [cmd ::struct::list] [method lcsInvertMerge2] [arg lcs1] [arg lcs2] [arg len1] [arg len2]] 205 206Similar to [method lcsInvertMerge]. Instead of directly taking the 207result of a call to [method longestCommonSubsequence] this subcommand 208expects the indices for the two sequences in two separate lists. 209 210 211 212[call [cmd ::struct::list] [method reverse] [arg sequence]] 213 214The subcommand takes a single [arg sequence] as argument and returns a new 215sequence containing the elements of the input sequence in reverse 216order. 217 218 219[call [cmd ::struct::list] [method assign] [arg sequence] [arg varname] [opt [arg varname]]...] 220 221The subcommand assigns the first [var n] elements of the input 222 223[arg sequence] to the one or more variables whose names were listed 224after the sequence, where [var n] is the number of specified 225variables. 226 227[para] 228 229If there are more variables specified than there are elements in the 230[arg sequence] the empty string will be assigned to the superfluous 231variables. 232 233[para] 234 235If there are more elements in the [arg sequence] than variable names 236specified the subcommand returns a list containing the unassigned 237elements. Else an empty list is returned. 238 239[example { 240 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}] 247 248 249[call [cmd ::struct::list] [method flatten] [opt [option -full]] [opt [option --]] [arg sequence]] 250 251The subcommand takes a single [arg sequence] and returns a new 252sequence where one level of nesting was removed from the input 253sequence. In other words, the sublists in the input sequence are 254replaced by their elements. 255 256[para] 257 258The subcommand will remove any nesting it finds if the option 259[option -full] is specified. 260 261[example { 262 tclsh> ::struct::list flatten {1 2 3 {4 5} {6 7} {{8 9}} 10} 263 1 2 3 4 5 6 7 {8 9} 10 264 tclsh> ::struct::list flatten -full {1 2 3 {4 5} {6 7} {{8 9}} 10} 265 1 2 3 4 5 6 7 8 9 10 266}] 267 268 269[call [cmd ::struct::list] [method map] [arg sequence] [arg cmdprefix]] 270 271The subcommand takes a [arg sequence] to operate on and a command 272prefix ([arg cmdprefix]) specifying an operation, applies the command 273prefix to each element of the sequence and returns a sequence 274consisting of the results of that application. 275 276[para] 277 278The command prefix will be evaluated with a single word appended to 279it. The evaluation takes place in the context of the caller of the 280subcommand. 281 282[para] 283 284[example { 285 tclsh> # squaring all elements in a list 286 287 tclsh> proc sqr {x} {expr {$x*$x}} 288 tclsh> ::struct::list map {1 2 3 4 5} sqr 289 1 4 9 16 25 290 291 tclsh> # Retrieving the second column from a matrix 292 tclsh> # given as list of lists. 293 294 tclsh> proc projection {n list} {::lindex $list $n} 295 tclsh> ::struct::list map {{a b c} {1 2 3} {d f g}} {projection 1} 296 b 2 f 297}] 298 299 300[call [cmd ::struct::list] [method mapfor] [arg var] [arg sequence] [arg script]] 301 302The subcommand takes a [arg sequence] to operate on and a tcl [arg script], 303applies the script to each element of the sequence and returns a sequence 304consisting of the results of that application. 305 306[para] 307 308The script will be evaluated as is, and has access to the current list element 309through the specified iteration variable [arg var]. The evaluation takes place 310in the context of the caller of the subcommand. 311 312[para] 313 314[example { 315 tclsh> # squaring all elements in a list 316 317 tclsh> ::struct::list mapfor x {1 2 3 4 5} { 318 expr {$x * $x} 319 } 320 1 4 9 16 25 321 322 tclsh> # Retrieving the second column from a matrix 323 tclsh> # given as list of lists. 324 325 tclsh> ::struct::list mapfor x {{a b c} {1 2 3} {d f g}} { 326 lindex $x 1 327 } 328 b 2 f 329}] 330 331 332[call [cmd ::struct::list] [method filter] [arg sequence] [arg cmdprefix]] 333 334The subcommand takes a [arg sequence] to operate on and a command 335prefix ([arg cmdprefix]) specifying an operation, applies the command 336prefix to each element of the sequence and returns a sequence 337consisting of all elements of the [arg sequence] for which the command 338prefix returned [const true]. 339 340In other words, this command filters out all elements of the input 341[arg sequence] which fail the test the [arg cmdprefix] represents, and 342returns the remaining elements. 343 344[para] 345 346The command prefix will be evaluated with a single word appended to 347it. The evaluation takes place in the context of the caller of the 348subcommand. 349 350[para] 351 352[example { 353 tclsh> # removing all odd numbers from the input 354 355 tclsh> proc even {x} {expr {($x % 2) == 0}} 356 tclsh> ::struct::list filter {1 2 3 4 5} even 357 2 4 358}] 359 360[para] 361 362[emph Note:] The [method filter] is a specialized application of 363[method fold] where the result is extended with the current item or 364not, depending o nthe result of the test. 365 366 367[call [cmd ::struct::list] [method filterfor] [arg var] [arg sequence] [arg expr]] 368 369The subcommand takes a [arg sequence] to operate on and a tcl expression 370([arg expr]) specifying a condition, applies the conditionto each element 371of the sequence and returns a sequence consisting of all elements of the 372[arg sequence] for which the expression returned [const true]. 373 374In other words, this command filters out all elements of the input 375[arg sequence] which fail the test the condition [arg expr] represents, and 376returns the remaining elements. 377 378[para] 379 380The expression will be evaluated as is, and has access to the current list 381element through the specified iteration variable [arg var]. The evaluation 382takes place in the context of the caller of the subcommand. 383 384[para] 385 386[example { 387 tclsh> # removing all odd numbers from the input 388 389 tclsh> ::struct::list filterfor x {1 2 3 4 5} {($x % 2) == 0} 390 2 4 391}] 392 393 394[call [cmd ::struct::list] [method split] [arg sequence] [arg cmdprefix] [opt "[arg passVar] [arg failVar]"]] 395 396This is a variant of method [method filter], see above. Instead of 397returning just the elements passing the test we get lists of both 398passing and failing elements. 399 400[para] 401 402If no variable names are specified then the result of the command will 403be a list containing the list of passing elements, and the list of 404failing elements, in this order. Otherwise the lists of passing and 405failing elements are stored into the two specified variables, and the 406result will be a list containing two numbers, the number of elements 407passing the test, and the number of elements failing, in this order. 408 409[para] 410 411The interface to the test is the same as used by [method filter]. 412 413 414[call [cmd ::struct::list] [method fold] [arg sequence] [arg initialvalue] [arg cmdprefix]] 415 416The subcommand takes a [arg sequence] to operate on, an arbitrary 417string [arg {initial value}] and a command prefix ([arg cmdprefix]) 418specifying an operation. 419 420[para] 421 422The command prefix will be evaluated with two words appended to 423it. The second of these words will always be an element of the 424sequence. The evaluation takes place in the context of the caller of 425the subcommand. 426 427[para] 428 429It then reduces the sequence into a single value through repeated 430application of the command prefix and returns that value. This 431reduction is done by 432 433[list_begin definitions] 434[def [const 1]] 435 436Application of the command to the initial value and the first element 437of the list. 438 439[def [const 2]] 440 441Application of the command to the result of the last call and the 442second element of the list. 443 444[def [const ...]] 445[def [const i]] 446 447Application of the command to the result of the last call and the 448[var i]'th element of the list. 449 450[def [const ...]] 451[def [const end]] 452 453Application of the command to the result of the last call and the last 454element of the list. The result of this call is returned as the result 455of the subcommand. 456 457[list_end] 458[para] 459[example { 460 tclsh> # summing the elements in a list. 461 tclsh> proc + {a b} {expr {$a + $b}} 462 tclsh> ::struct::list fold {1 2 3 4 5} 0 + 463 15 464}] 465 466 467[call [cmd ::struct::list] [method shift] [arg listvar]] 468 469The subcommand takes the list contained in the variable named by 470 471[arg listvar] and shifts it down one element. 472 473After the call [arg listvar] will contain a list containing the second 474to last elements of the input list. The first element of the ist is 475returned as the result of the command. Shifting the empty list does 476nothing. 477 478 479[call [cmd ::struct::list] [method iota] [arg n]] 480 481The subcommand returns a list containing the integer numbers 482in the range [const {[0,n)}]. The element at index [var i] 483of the list contain the number [const i]. 484 485[para] 486 487For "[arg n] == [const 0]" an empty list will be returned. 488 489 490[call [cmd ::struct::list] [method equal] [arg a] [arg b]] 491 492The subcommand compares the two lists [arg a] and [arg b] for 493equality. In other words, they have to be of the same length and have 494to contain the same elements in the same order. If an element is a 495list the same definition of equality applies recursively. 496 497[para] 498 499A boolean value will be returned as the result of the command. 500This value will be [const true] if the two lists are equal, and 501[const false] else. 502 503 504[call [cmd ::struct::list] [method repeat] [arg size] [arg element1] [opt "[arg element2] [arg element3]..."]] 505 506The subcommand creates a list of length 507 508"[arg size] * [emph {number of elements}]" by repeating [arg size] 509times the sequence of elements 510[arg element1] [arg element2] [arg ...]. 511 512[arg size] must be a positive integer, [arg element][var n] can be any 513Tcl value. 514 515Note that [cmd {repeat 1 arg ...}] is identical to 516[cmd {list arg ...}], though the [arg arg] is required 517with [method repeat]. 518 519[para] 520[emph Examples:] 521[para] 522[example { 523 tclsh> ::struct::list repeat 3 a 524 a a a 525 tclsh> ::struct::list repeat 3 [::struct::list repeat 3 0] 526 {0 0 0} {0 0 0} {0 0 0} 527 tclsh> ::struct::list repeat 3 a b c 528 a b c a b c a b c 529 tclsh> ::struct::list repeat 3 [::struct::list repeat 2 a] b c 530 {a a} b c {a a} b c {a a} b c 531}] 532 533[call [cmd ::struct::list] [method repeatn] [arg value] [arg size]...] 534 535The subcommand creates a (nested) list containing the [arg value] in 536all positions. The exact size and degree of nesting is determined by 537the [arg size] arguments, all of which have to be integer numbers 538greater than or equal to zero. 539 540[para] 541 542A single argument [arg size] which is a list of more than one element 543will be treated as if more than argument [arg size] was specified. 544 545[para] 546 547If only one argument [arg size] is present the returned list will not 548be nested, of length [arg size] and contain [arg value] in all 549positions. 550 551If more than one [arg size] argument is present the returned 552list will be nested, and of the length specified by the last 553[arg size] argument given to it. The elements of that list 554are defined as the result of [cmd Repeat] for the same arguments, 555but with the last [arg size] value removed. 556 557[para] 558 559An empty list will be returned if no [arg size] arguments are present. 560 561[para] 562[example { 563 tclsh> ::struct::list repeatn 0 3 4 564 {0 0 0} {0 0 0} {0 0 0} {0 0 0} 565 tclsh> ::struct::list repeatn 0 {3 4} 566 {0 0 0} {0 0 0} {0 0 0} {0 0 0} 567 tclsh> ::struct::list repeatn 0 {3 4 5} 568 {{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}} 569}] 570 571 572[call [cmd ::struct::list] [method dbJoin] [opt [option -inner]|[option -left]|[option -right]|[option -full]] [opt "[option -keys] [arg varname]"] \{[arg keycol] [arg table]\}...] 573 574The method performs a table join according to relational algebra. The 575execution of any of the possible outer join operation is triggered by 576the presence of either option [option -left], [option -right], or 577[option -full]. If none of these options is present a regular inner 578join will be performed. This can also be triggered by specifying 579[option -inner]. The various possible join operations are explained in 580detail in section [sectref {TABLE JOIN}]. 581 582[para] 583 584If the [option -keys] is present its argument is the name of a 585variable to store the full list of found keys into. Depending on the 586exact nature of the input table and the join mode the output table may 587not contain all the keys by default. In such a case the caller can 588declare a variable for this information and then insert it into the 589output table on its own, as she will have more information about the 590placement than this command. 591 592[para] 593 594What is left to explain is the format of the arguments. 595 596[para] 597 598The [arg keycol] arguments are the indices of the columns in the 599tables which contain the key values to use for the joining. Each 600argument applies to the table following immediately after it. The 601columns are counted from [const 0], which references the first 602column. The table associated with the column index has to have at 603least [arg keycol]+1 columns. An error will be thrown if there are 604less. 605 606[para] 607 608The [arg table] arguments represent a table or matrix of rows and 609columns of values. We use the same representation as generated and 610consumed by the methods [method {get rect}] and [method {set rect}] of 611[cmd matrix] objects. In other words, each argument is a list, 612representing the whole matrix. Its elements are lists too, each 613representing a single rows of the matrix. The elements of the 614row-lists are the column values. 615 616[para] 617 618The table resulting from the join operation is returned as the result 619of the command. We use the same representation as described above for 620the input [arg table]s. 621 622 623 624[call [cmd ::struct::list] [method dbJoinKeyed] [opt [option -inner]|[option -left]|[option -right]|[option -full]] [opt "[option -keys] [arg varname]"] [arg table]...] 625 626The operations performed by this method are the same as described 627above for [method dbJoin]. The only difference is in the specification 628of the keys to use. Instead of using column indices separate from the 629table here the keys are provided within the table itself. The row 630elements in each [arg table] are not the lists of column values, but a 631two-element list where the second element is the regular list of 632column values and the first element is the key to use. 633 634[call [cmd ::struct::list] [method swap] [arg listvar] [arg i] [arg j]] 635 636The subcommand exchanges the elements at the indices [arg i] and 637[arg j] in the list stored in the variable named by [arg listvar]. The 638list is modified in place, and also returned as the result of the 639subcommand. 640 641 642[call [cmd ::struct::list] [method firstperm] [arg list]] 643 644This subcommand returns the lexicographically first permutation of the 645input [arg list]. 646 647 648[call [cmd ::struct::list] [method nextperm] [arg perm]] 649 650This subcommand accepts a permutation of a set of elements (provided 651by [arg perm]) and returns the next permutatation in lexicographic 652sequence. 653 654[para] 655The algorithm used here is by Donal E. Knuth, see section 656[sectref REFERENCES] for details. 657 658 659[call [cmd ::struct::list] [method permutations] [arg list]] 660 661This subcommand returns a list containing all permutations of the 662input [arg list] in lexicographic order. 663 664 665[call [cmd ::struct::list] [method foreachperm] [arg var] [arg list] [arg body]] 666 667This subcommand executes the script [arg body] once for each 668permutation of the specified [arg list]. The permutations are visited 669in lexicographic order, and the variable [arg var] is set to the 670permutation for which [arg body] is currently executed. The result of 671the loop command is the empty string. 672 673[list_end] 674 675[section {LONGEST COMMON SUBSEQUENCE AND FILE COMPARISON}] 676 677[para] 678 679The [method longestCommonSubsequence] subcommand forms the core of a 680flexible system for doing differential comparisons of files, similar 681to the capability offered by the Unix command [syscmd diff]. 682 683While this procedure is quite rapid for many tasks of file comparison, 684its performance degrades severely if [arg sequence2] contains many 685equal elements (as, for instance, when using this procedure to compare 686two files, a quarter of whose lines are blank. This drawback is 687intrinsic to the algorithm used (see the Reference for details). 688 689[para] 690 691One approach to dealing with the performance problem that is sometimes 692effective in practice is arbitrarily to exclude elements that appear 693more than a certain number of times. 694 695This number is provided as the [arg maxOccurs] parameter. If frequent 696lines are excluded in this manner, they will not appear in the common 697subsequence that is computed; the result will be the longest common 698subsequence of infrequent elements. 699 700The procedure [method longestCommonSubsequence2] implements this 701heuristic. 702 703It functions as a wrapper around [method longestCommonSubsequence]; it 704computes the longest common subsequence of infrequent elements, and 705then subdivides the subsequences that lie between the matches to 706approximate the true longest common subsequence. 707 708 709[section {TABLE JOIN}] 710 711This is an operation from relational algebra for relational databases. 712 713[para] 714 715The easiest way to understand the regular inner join is that it 716creates the cartesian product of all the tables involved first and 717then keeps only all those rows in the resulting table for which the 718values in the specified key columns are equal to each other. 719 720[para] 721 722Implementing this description naively, i.e. as described above will 723generate a [emph huge] intermediate result. To avoid this the 724cartesian product and the filtering of row are done at the same 725time. What is required is a fast way to determine if a key is present 726in a table. In a true database this is done through indices. Here we 727use arrays internally. 728 729[para] 730 731An [term outer] join is an extension of the inner join for two 732tables. There are three variants of outerjoins, called [term left], 733[term right], and [term full] outer joins. Their result always 734contains all rows from an inner join and then some additional rows. 735 736[list_begin enumerated] 737[enum] 738 739For the left outer join the additional rows are all rows from the left 740table for which there is no key in the right table. They are joined to 741an empty row of the right table to fit them into the result. 742 743[enum] 744 745For the right outer join the additional rows are all rows from the right 746table for which there is no key in the left table. They are joined to 747an empty row of the left table to fit them into the result. 748 749 750[enum] 751 752The full outer join combines both left and right outer join. In other 753words, the additional rows are as defined for left outer join, and 754right outer join, combined. 755 756[list_end] 757 758[para] 759 760We extend all the joins from two to [var n] tables ([var n] > 2) by 761executing 762 763[example { 764 (...((table1 join table2) join table3) ...) join tableN 765}] 766 767[para] 768 769Examples for all the joins: 770 771[example { 772 Inner Join 773 774 {0 foo} {0 bagel} {0 foo 0 bagel} 775 {1 snarf} inner join {1 snatz} = {1 snarf 1 snatz} 776 {2 blue} {3 driver} 777 778 Left Outer Join 779 780 {0 foo} {0 bagel} {0 foo 0 bagel} 781 {1 snarf} left outer join {1 snatz} = {1 snarf 1 snatz} 782 {2 blue} {3 driver} {2 blue {} {}} 783 784 Right Outer Join 785 786 {0 foo} {0 bagel} {0 foo 0 bagel} 787 {1 snarf} right outer join {1 snatz} = {1 snarf 1 snatz} 788 {2 blue} {3 driver} {{} {} 3 driver} 789 790 Full Outer Join 791 792 {0 foo} {0 bagel} {0 foo 0 bagel} 793 {1 snarf} full outer join {1 snatz} = {1 snarf 1 snatz} 794 {2 blue} {3 driver} {2 blue {} {}} 795 {{} {} 3 driver} 796}] 797 798 799 800 801[section REFERENCES] 802 803[list_begin enumerated] 804 805[enum] 806J. W. Hunt and M. D. McIlroy, "An algorithm for differential 807file comparison," Comp. Sci. Tech. Rep. #41, Bell Telephone 808Laboratories (1976). Available on the Web at the second 809author's personal site: [uri http://www.cs.dartmouth.edu/~doug/] 810 811[enum] 812Donald E. Knuth, "Fascicle 2b of 'The Art of Computer Programming' 813volume 4". Available on the Web at the author's personal site: 814[uri http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz]. 815 816[list_end] 817 818[section {BUGS, IDEAS, FEEDBACK}] 819 820This document, and the package it describes, will undoubtedly contain 821bugs and other problems. 822 823Please report such in the category [emph {struct :: list}] of the 824[uri {http://sourceforge.net/tracker/?group_id=12883} {Tcllib SF Trackers}]. 825 826Please also report any ideas for enhancements you may have for either 827package and/or documentation. 828 829 830[keywords list diff differential comparison common subsequence] 831[keywords {longest common subsequence}] 832[keywords reverse] 833[keywords assign] 834[keywords flatten] 835[keywords map filter] 836[keywords folding reduce] 837[keywords equality equal repetition repeating] 838[keywords {inner join} {left outer join} {right outer join} {full outer join} {outer join} join] 839[keywords swapping permutation {first permutation} {next permutation} {generate permutations}] 840[manpage_end] 841