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