home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / OL.LZH / PROCS.LZH / COMPLETE.ICN < prev    next >
Text File  |  1991-09-05  |  6KB  |  158 lines
  1. ############################################################################
  2. #
  3. #    Name:     complete.icn
  4. #
  5. #    Title:     complete partial input string
  6. #
  7. #    Author:     Richard L. Goerwitz
  8. #
  9. #    Version: 1.6
  10. #
  11. #    Date:     June 1, 1991
  12. #
  13. ############################################################################
  14. #
  15. #  This file contains a single procedure, complete(s,st), which
  16. #  completes a string (s) relative to a set or list of strings (st).
  17. #  Put differently, complete() lets you supply a partial string, s,
  18. #  and get back those strings in st that s is either equal to or a
  19. #  substring of.
  20. #
  21. #  Lots of command interfaces allow completion of partial input.
  22. #  Complete() simply represents my personal sentiments about how this
  23. #  might best be done in Icon.  If you strip away the profuse comments
  24. #  below, you end up with only about thirty lines of actual source
  25. #  code.
  26. #
  27. #  I have arranged things so that only that portion of an automaton
  28. #  which is needed to complete a given string is actually created and
  29. #  stored.  Storing automata for later use naturally makes complete()
  30. #  eat up more memory.  The performance gains can make it worth the
  31. #  trouble, though.  If, for some reason, there comes a time when it
  32. #  is advisable to reclaim the space occupied by complete's static
  33. #  structures, you can just call it without arguments.  This
  34. #  "resets" complete() and forces an immediate garbage collection.
  35. #  
  36. # Example code:
  37. #
  38. #      commands := ["run","stop","quit","save","load","continue"]
  39. #      while line := read(&input) do {
  40. #          cmds := list()
  41. #          every put(cmds, complete(line, commands))
  42. #          case *cmds of {
  43. #              0 : input_error(line)
  44. #              1 : do_command(cmds[1])
  45. #              default : display_possible_completions(cmds)
  46. #          }
  47. #          etc...
  48. #
  49. #  More Iconish methods might include displaying successive
  50. #  alternatives each time the user presses the tab key (this would,
  51. #  however, require using the nonportable getch() routine).  Another
  52. #  method might be to use the first string suspended by complete().
  53. #
  54. #  Note: This entire shebang could be replaced with a slightly slower
  55. #  and much smaller program suggested to me by Jerry Nowlin and Bob
  56. #  Alexander.
  57. #
  58. #      procedure terscompl(s, st)
  59. #          suspend match(s, p := !st) & p
  60. #      end
  61. #
  62. #  This program will work fine for lists with just a few members, and
  63. #  also for cases where s is fairly large.  It will also use much less
  64. #  memory.
  65. #
  66. ############################################################################
  67.  
  68. procedure complete(s,st)
  69.  
  70.     local dfstn, c, l, old_char, newtbl, str, strset
  71.     static t
  72.     initial t := table()
  73.  
  74.     # No-arg invocation wipes out static structures & causes an
  75.     # immediate garbage collection.
  76.     if /s & /st then {
  77.     t := table()
  78.     collect()        # do it NOW
  79.     fail
  80.     }
  81.     type(st) == ("list"|"set") |
  82.     stop("error (complete):  list or set expected for arg2")
  83.  
  84.     # Seriously, all that's being done here is that possible states
  85.     # are being represented by sets containing possible completions of
  86.     # s relative to st.  Each time a character is snarfed from s, we
  87.     # check to see what strings in st might represent possible
  88.     # completions, and store these in yet another set.  At some
  89.     # point, we either run into a character in s that makes comple-
  90.     # tion impossible (fail), or we run out of characters in s (in
  91.     # which case we succeed, & suspend each of the possible
  92.     # completions).
  93.  
  94.     # Store any sets we have to create in a static structure for later
  95.     # re-use.
  96.     /t[st] := table()
  97.  
  98.     # We'll call the table entry for the current set dfstn.  (It really
  99.     # does enable us to do things deterministically.)
  100.     dfstn := t[st]
  101.  
  102.     # Snarf one character at a time from s.
  103.     every c := !s do {
  104.  
  105.     # The state we're in is represented by the set of all possible
  106.     # completions before c was read.  If we haven't yet seen char
  107.     # c in this state, run through the current-possible-completion
  108.     # set, popping off the first character of each possible
  109.     # completion, and then construct a table which uses these
  110.     # initial chars as keys, and makes the completions that are
  111.     # possible for each of these characters into the values for
  112.     # those keys.
  113.     if /dfstn[st] then {
  114.  
  115.         # To get strings that start with the same char together,
  116.         # sort the current string set (st).
  117.         l := sort(st)
  118.         newtbl := table()
  119.         old_chr := ""
  120.         # Now pop off each member of the sorted string set.  Use
  121.         # first characters as keys, and then divvy up the full strings
  122.         # into sets of strings having the same initial letter.
  123.         every str := !l do {
  124.         str ? { chr := move(1) | next; str := tab(0) }
  125.         if old_chr ~==:= chr then {
  126.             strset := set([str])
  127.             insert(newtbl, chr, strset)
  128.         }
  129.         else insert(strset, str)
  130.         }
  131.         insert(dfstn, st, newtbl)
  132.     }
  133.  
  134.     # What we've done essentially is to create a table in which
  135.     # the keys represent labeled arcs out of the current state,
  136.     # and the values represent possible completion sets for those
  137.     # paths.  What we need to do now is store that table in dfstn
  138.     # as the value of the current state-set (i.e. the current
  139.     # range of possible completions).  Once stored, we can then
  140.     # see if there is any arc from the current state (dfstn[st])
  141.     # with the label c (dfstn[st][c]).  If so, its value becomes
  142.     # the new current state (st), and we cycle around again for
  143.     # yet another c.
  144.     st := \dfstn[st][c] | fail
  145.     if *st = 1 & match(s,!st)
  146.     then break
  147.     }
  148.  
  149.     # Eventually we run out of characters in c.  The current state
  150.     # (i.e. the set of possible completions) can simply be suspended
  151.     # one element at a time, with s prefixed to each element.  If, for
  152.     # instance, st had contained ["hello","help","hear"] at the outset
  153.     # and s was equal to "hel", we would now be suspending "hel" ||
  154.     # !set(["lo","p"]).
  155.     suspend s || !st
  156.  
  157. end
  158.