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