Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!ceres.physics.uiowa.edu!news.iastate.edu!ux1.cso.uiuc.edu!midway!ellis.uchicago.edu!goer
From: goer@ellis.uchicago.edu (Richard L. Goerwitz)
Newsgroups: comp.lang.icon
Subject: terrible code
Message-ID: <1991Mar18.043948.11527@midway.uchicago.edu>
Date: 18 Mar 91 04:39:48 GMT
Sender: goer@midway.uchicago.edu (Richard L. Goerwitz)
Organization: University of Chicago
Lines: 95


I wrote the following code because I figured that using sets or
lists alone to accomplish what it does would be inefficient.  It
turns out that, even though the code below produces a determinis-
tic automaton (with some small cheating in one spot), it's about
a third as fast as just using a set or list all by itself to do
the same thing.

If there are any wizards online, who feel like bending their minds
over some obscure code, I wouldn't mind a bit if they'd comment
on how this might be done more efficiently.  Non-wizards beware
:-).

-Richard


------------------------------------------------------------------

procedure anystr(l,s,i,j)

    static done_tbl
    initial done_tbl := table()

    #
    # Make defaults work like those for built-in string-handling
    # functions.
    #
    /s := &subject
    if \i then {
	if i < 1 then
	    i := *s + (i+1)
    }
    else i := \&pos | 1
    if \j then {
	if j < 1 then
	    j := *s + (j+1)
    }
    else j := *s+1

    #
    # Create table to sort and hold characters for list l (if it
    # does not already exist.  Then return the position in s of
    # the longest string in l that matches at position i.
    #
    /done_tbl[l] := table(sort(set(l)))
    return (i-1) + (s[i:j] ? walk_table(done_tbl[l]))

    # NB:  longest possible match approach!

end


procedure walk_table(t)

    local val, chr, ntbl, nlst, empty_string_present

    while val := t[move(1)] do {

	case type(val) of {
	    "table" : {
		if "" == key(val) then {
		    POS := &pos
		    return (walk_table(val) | POS)
		}
		else return walk_table(val)
	    }
	    "list"  : {
		case *val of {
		    0      : fail
		    1      : if (move(-1),=val[1]) then return .&pos else fail
		    default: {
			nkey := "impossible key"
			while pop(val) ? {
			    empty_string_present := pos(0)
			    chr := move(1) | ""
			    if nkey ~==:= chr then {
				nlst := list()
				ntbl := table(nlst)
				insert(t, nkey, ntbl)
			    }
			    put(nlst, tab(0))
			}
			move(-1)
			if \empty_string_present then {
			    POS := &pos
			    return (walk_table(t) | POS)
			}
			else return walk_table(t)
		    }
		}
	    }
	}
    }

end