home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / OL.LZH / PROCS.LZH / DIF.ICN < prev    next >
Text File  |  1991-07-13  |  7KB  |  230 lines
  1.  
  2. ############################################################################
  3. #
  4. #    Name:    dif.icn
  5. #
  6. #    Title:    "Diff" Engine
  7. #
  8. #    Author:    Robert J. Alexander
  9. #
  10. #    Date:    May 15, 1990
  11. #
  12. ############################################################################
  13. #
  14. #  The procedure dif() is a generator that produces a sequence of
  15. #  differences between an arbitrary number of input streams.  Each result
  16. #  is returned as a list of diff_recs, one for each input stream, with
  17. #  each diff_rec containing a list of items that differ and their position
  18. #  in the input stream.  The diff_rec type is declared as:
  19. #
  20. #        record diff_rec(pos,diffs)
  21. #
  22. #  Dif fails if there are no differences, i.e. it produces an empty
  23. #  result sequence.
  24. #
  25. #  For example, if two input streams are:
  26. #
  27. #    a b c d e f g h
  28. #    a b d e f i j
  29. #
  30. #  the output sequence would be:
  31. #
  32. #    [diff_rec(3,[c]),diff_rec(3,[])]
  33. #    [diff_rec(7,[g,h]),diff_rec(6,[i,j])
  34. #
  35. #  The arguments to dif(stream,compare,eof,group) are:
  36. #
  37. #    stream        A list of data objects that represent input streams
  38. #            from which dif will extract its input "records".
  39. #            The elements can be of several different types which
  40. #            result in different actions, as follows:
  41. #
  42. #               Type               Action
  43. #            ===========    =============================
  44. #            file        file is "read" to get records
  45. #
  46. #            co-expression    co-expression is activated to
  47. #                    get records
  48. #
  49. #            list        records are "gotten" (get()) from
  50. #                    the list
  51. #
  52. #            diff_proc    a record type defined in "dif" to
  53. #                    allow a procedure (or procedures)
  54. #                    suppled by dif's caller to be called
  55. #                    to get records.  Diff_proc has two
  56. #                    fields, the procedure to call and the
  57. #                    argument to call it with.  Its
  58. #                    definition looks like this:
  59. #
  60. #                       record diff_proc(proc,arg)
  61. #            
  62. #
  63. #  Optional arguments:
  64. #
  65. #    compare        Item comparison procedure -- succeeds if
  66. #            "equal", otherwise fails (default is the
  67. #            identity "===" comparison).  The comparison
  68. #            must allow for the fact that the eof object
  69. #            (see next) might be an argument, and a pair of
  70. #            eofs must compare equal.
  71. #
  72. #    eof        An object that is distinguishable from other
  73. #            objects in the stream.  Default is &null.
  74. #
  75. #    group        A procedure that is called with the current number
  76. #            of unmatched items as its argument.  It must
  77. #            return the number of matching items required
  78. #            for file synchronization to occur.  Default is
  79. #            the formula Trunc((2.0 * Log(M)) + 2.0) where
  80. #            M is the number of unmatched items.
  81. #
  82. ############################################################################
  83.  
  84.  
  85. record diff_rec(pos,diffs)
  86. record diff_proc(proc,arg)
  87. record diff_file(stream,queue)
  88.  
  89.  
  90. procedure dif(stream,compare,eof,group)
  91.   local f,linenbr,line,difflist,gf,i,j,k,l,m,n,x,test,
  92.     result,synclist,nsyncs,syncpoint
  93.   #
  94.   #  Provide default arguments and initialize data.
  95.   #
  96.   /compare := proc("===",2)
  97.   /group := groupfactor
  98.   f := []
  99.   every put(f,diff_file(!stream,[]))
  100.   linenbr := list(*stream,0)
  101.   line := list(*stream)
  102.   test := list(*stream)
  103.   difflist := list(*stream)
  104.   every !difflist := []
  105.   #
  106.   #  Loop to process all records of all input streams.
  107.   #
  108.   repeat {
  109.     #
  110.     #  This is the "idle loop" where we spin until we find a discrepancy
  111.     #  among the data streams.  A line is read from each stream, with a
  112.     #  check for eof on all streams.  Then the line from the first
  113.     #  stream is compared to the lines from all the others.
  114.     #
  115.     repeat {
  116.       every i := 1 to *stream do
  117.         line[i] := diffread(f[i]) | eof
  118.       if not (every x := !line do
  119.         (x === eof) | break) then break break
  120.       every !linenbr +:= 1
  121.       if (every x := !line[2:0] do
  122.         compare(x,line[1]) | break) then break
  123.     }
  124.     #
  125.     #  Aha!  We have found a difference.  Create a difference list,
  126.     #  one entry per stream, primed with the differing line we just found.
  127.     #
  128.     every i := 1 to *stream do
  129.       difflist[i] := [line[i]]
  130.     repeat {
  131.       #
  132.       #  Add a new input line from each stream to the difference list.
  133.       #  Then build lists of the subset of different lines we need to
  134.       #  actually compare.
  135.       #
  136.       every i := 1 to *stream do
  137.         put(difflist[i],diffread(f[i]) | eof)
  138.       gf := group(*difflist[1])
  139.       every i := 1 to *stream do
  140.         test[i] := difflist[i][-gf:0]
  141.       #
  142.       #  Create a "synchronization matrix", with a row and column for
  143.       #  each input stream.  The entries will be initially &null, then
  144.       #  will be set to the synchronization position if sync is
  145.       #  achieved between the two streams.  Another list is created to
  146.       #  keep track of how many syncs have been achieved for each stream.
  147.       #
  148.       j := *difflist[1] - gf + 1
  149.       synclist := list(*stream)
  150.       every !synclist := list(*stream)
  151.       every k := 1 to *stream do
  152.         synclist[k][k] := j
  153.       nsyncs := list(*stream,1)
  154.       #
  155.       #  Loop through positions to start comparing lines.  This set of
  156.       #  nested loops will be exited when a stream achieves sync with
  157.       #  all other streams.
  158.       #
  159.       every i := 1 to j do {
  160.         #
  161.         #  Loop through all streams.
  162.         #
  163.         every k := 1 to *stream do {
  164.           #
  165.           #  Loop through all streams.
  166.           #
  167.       every l := 1 to *stream do {
  168.         if /synclist[k][l] then {    # avoid unnecessary comparisons
  169.           #
  170.               #  Compare items of the test list to the differences list
  171.               #  at all possible positions.  If they compare, store the
  172.               #  current position in the sync matrix and bump the count
  173.               #  of streams sync'd to this stream.  If all streams are in
  174.           #  sync, exit all loops but the outer one.
  175.           #
  176.           m := i - 1
  177.           if not every n := 1 to gf do {
  178.             if not compare(test[k][n],difflist[l][m +:= 1]) then break
  179.           } then {
  180.             synclist[k][l] := i    # store current position
  181.             if (nsyncs[k] +:= 1) = *stream then break break break break
  182.           }
  183.         }
  184.       }
  185.     }
  186.       }
  187.     }
  188.     #
  189.     #  Prepare an output set.  Since we have read the input streams past
  190.     #  the point of synchronization, we must queue those lines before their
  191.     #  input streams. 
  192.     #
  193.     synclist := synclist[k]
  194.     result := list(*stream)
  195.     every i := 1 to *stream do {
  196.       j := synclist[i]
  197.       while difflist[i][j -:= 1] === eof    # trim past eof
  198.       result[i] := diff_rec(linenbr[i],difflist[i][1:j + 1])
  199.       f[i].queue := difflist[i][synclist[i] + gf:0] ||| f[i].queue
  200.       linenbr[i] +:= synclist[i] + gf - 2
  201.       difflist[i] := []
  202.     }
  203.     suspend result
  204.   }
  205. end
  206.  
  207. #
  208. #  diffread() -- Read a line from an input stream.
  209. #
  210. procedure diffread(f)
  211.   local x
  212.   return get(f.queue) | case type(x := f.stream) of {
  213.     "file": read(x)
  214.     "co-expression": @x
  215.     "diff_proc": x.proc(x.arg)
  216.     "list": get(x)
  217.   }
  218. end
  219.  
  220. #
  221. #  groupfactor() -- Determine how many like lines we need to close
  222. #  off a group of differences.  This is the default routine -- the
  223. #  caller may provide his own.
  224. #
  225. procedure groupfactor(m)  # Compute: Trunc((2.0 * Log(m)) + 2.0)
  226.   m := string(m)
  227.   return 2 * *m + if m <<= "316227766"[1+:*m] then 0 else 1
  228. end
  229.  
  230.