1struct::list(n)               Tcl Data Structures              struct::list(n)
2
3
4
5______________________________________________________________________________
6

NAME

8       struct::list - Procedures for manipulating lists
9

SYNOPSIS

11       package require Tcl  8.4
12
13       package require struct::list  ?1.8.3?
14
15       ::struct::list longestCommonSubsequence sequence1 sequence2 ?maxOccurs?
16
17       ::struct::list  longestCommonSubsequence2  sequence1  sequence2 ?maxOc‐
18       curs?
19
20       ::struct::list lcsInvert lcsData len1 len2
21
22       ::struct::list lcsInvert2 lcs1 lcs2 len1 len2
23
24       ::struct::list lcsInvertMerge lcsData len1 len2
25
26       ::struct::list lcsInvertMerge2 lcs1 lcs2 len1 len2
27
28       ::struct::list reverse sequence
29
30       ::struct::list shuffle list
31
32       ::struct::list assign sequence varname ?varname?...
33
34       ::struct::list flatten ?-full? ?--? sequence
35
36       ::struct::list map sequence cmdprefix
37
38       ::struct::list mapfor var sequence script
39
40       ::struct::list filter sequence cmdprefix
41
42       ::struct::list filterfor var sequence expr
43
44       ::struct::list split sequence cmdprefix ?passVar failVar?
45
46       ::struct::list fold sequence initialvalue cmdprefix
47
48       ::struct::list shift listvar
49
50       ::struct::list iota n
51
52       ::struct::list equal a b
53
54       ::struct::list repeat size element1 ?element2 element3...?
55
56       ::struct::list repeatn value size...
57
58       ::struct::list dbJoin ?-inner|-left|-right|-full? ?-keys varname? {key‐
59       col table}...
60
61       ::struct::list  dbJoinKeyed ?-inner|-left|-right|-full? ?-keys varname?
62       table...
63
64       ::struct::list swap listvar i j
65
66       ::struct::list firstperm list
67
68       ::struct::list nextperm perm
69
70       ::struct::list permutations list
71
72       ::struct::list foreachperm var list body
73
74______________________________________________________________________________
75

DESCRIPTION

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
81       It exports only a single command, struct::list. All functionality  pro‐
82       vided here can be reached through a subcommand of this command.
83

COMMANDS

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
91              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
97       ::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
109              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
116       ::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
123              To be fully defined the lengths of the two sequences have to  be
124              known and are specified through len1 and len2.
125
126              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
132              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
143              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
155              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
167
168
169                  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
174                  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
179
180              Notes:
181
182
183              ·      An index of -1 in a deleted chunk refers to  just  before
184                     the first element of the second sequence.
185
186              ·      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
190       ::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
195       ::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
200              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
205
206
207                  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
212                  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
220
221       ::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
226       ::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
231       ::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
237       ::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
243              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
247              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
251
252                  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
259
260       ::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
266              The  subcommand  will  remove any nesting it finds if the option
267              -full is specified.
268
269
270                  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
275
276       ::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
282              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
286
287
288                  tclsh> # squaring all elements in a list
289
290                  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
294                  tclsh> # Retrieving the second column from a matrix
295                  tclsh> # given as list of lists.
296
297                  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
301
302       ::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
307              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
312
313
314                  tclsh> # squaring all elements in a list
315
316                  tclsh> ::struct::list mapfor x {1 2 3 4 5} {
317                expr {$x * $x}
318                  }
319                  1 4 9 16 25
320
321                  tclsh> # Retrieving the second column from a matrix
322                  tclsh> # given as list of lists.
323
324                  tclsh> ::struct::list mapfor x {{a b c} {1 2 3} {d f g}} {
325                lindex $x 1
326                  }
327                  b 2 f
328
329
330       ::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
339              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
343
344
345                  tclsh> # removing all odd numbers from the input
346
347                  tclsh> proc even {x} {expr {($x % 2) == 0}}
348                  tclsh> ::struct::list filter {1 2 3 4 5} even
349                  2 4
350
351
352       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
356       ::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
365              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
370
371
372                  tclsh> # removing all odd numbers from the input
373
374                  tclsh> ::struct::list filterfor x {1 2 3 4 5} {($x % 2) == 0}
375                  2 4
376
377
378       ::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
383              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
391              The interface to the test is the same as used by filter.
392
393       ::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
398              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
403              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
407              1      Application of the command to the initial value  and  the
408                     first element of the list.
409
410              2      Application of the command to the result of the last call
411                     and the second element of the list.
412
413              ...
414
415              i      Application of the command to the result of the last call
416                     and the i'th element of the list.
417
418              ...
419
420              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
424
425
426                  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
431
432       ::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
439       ::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
444              For "n == 0" an empty list will be returned.
445
446       ::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
452              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
456       ::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
463              Examples:
464
465
466
467                  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
476
477       ::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
483              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
486              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
494              An empty list will be returned if no size arguments are present.
495
496
497
498                  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
505
506       ::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
516              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
524              What is left to explain is the format of the arguments.
525
526              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
534              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
542              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
546       ::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
557       ::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
563       ::struct::list firstperm list
564              This subcommand returns the lexicographically first  permutation
565              of the input list.
566
567       ::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
572              The algorithm used here is by Donal E. Knuth, see section REFER‐
573              ENCES for details.
574
575       ::struct::list permutations list
576              This subcommand returns a list containing  all  permutations  of
577              the input list in lexicographic order.
578
579       ::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

LONGEST COMMON SUBSEQUENCE AND FILE COMPARISON

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

TABLE JOIN

609       This is an operation from relational algebra for relational databases.
610
611       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
616       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
623       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
628       [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
633       [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
638       [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
642       We extend all the joins from two to n tables (n > 2) by executing
643
644
645                  (...((table1 join table2) join table3) ...) join tableN
646
647
648       Examples for all the joins:
649
650
651                  Inner Join
652
653                  {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
657                  Left Outer Join
658
659                  {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
663                  Right Outer Join
664
665                  {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
669                  Full Outer Join
670
671                  {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
676

REFERENCES

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
683       [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

BUGS, IDEAS, FEEDBACK

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
694       When proposing code changes, please provide unified diffs, i.e the out‐
695       put of diff -u.
696
697       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

KEYWORDS

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

CATEGORY

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>
716
717
718
719
720tcllib                               1.8.3                     struct::list(n)
Impressum