Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] View of /archive/mlprof.1/basics/table.sml
ViewVC logotype

View of /archive/mlprof.1/basics/table.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4054 - (download) (annotate)
Wed Feb 4 20:42:42 2015 UTC (4 years, 5 months ago) by dbm
File size: 1921 byte(s)
Initial import of archive (of early versions of sml/nj)
(* table.sml *)

signature TABLE = sig
    structure Symbol : SYMBOL
    type 'a table
    exception Notfound_Table
    exception Next
    val new : unit -> 'a table
    val add : 'a table * (Symbol.symbol * 'a) -> int
    val look : ('a -> 'b) -> ('a table * Symbol.symbol) -> 'b
    val push : 'a table * int * (Symbol.symbol * 'a) -> unit
    val pop : 'a table * int -> (Symbol.symbol * 'a)
    val merge : 'a table * 'a table -> unit
    val app: 'a table * ((Symbol.symbol * 'a) -> unit) -> unit
    val list: 'a table -> (Symbol.symbol * 'a) list
end

structure Table : TABLE = struct

    (* table -- symbol table hash tables *)

    structure Symbol = Symbol

    type 'a table = (Symbol.symbol * 'a) list array

    exception Notfound_Table
	  and Next

    val tableSize = 103  (* size of hash array *)

    fun new () =
	array(tableSize,nil)

    fun add (s: 'a table, binder as (id,_)): int =
	let val index = Symbol.number id mod tableSize
	 in update(s, index, binder::(s sub index));
	    index
	end

    fun look test (s, id) =
	let fun look1 ((i,b)::e) =
		  if Symbol.eq(i,id)
		  then (test b handle Next => look1 e)
		  else look1 e
	      | look1 nil = raise Notfound_Table
	 in look1(s sub (Symbol.number id mod tableSize))
	end

    fun push(s,i,x) =
	update(s,i,x::(s sub i))

    fun pop(s,i) =
	let val x::b = s sub i
	 in update(s,i,b); x
	end

    fun merge(s,t) =
	   let fun index i = (update(t,i,(s sub i)@(t sub i)); index(i+1))
	    in index 0 handle Subscript => ()
	   end

    fun app(s,f) =
	(* applies f in the order in which elements were entered into bucket *)
        let fun bucket (elem::rest) = (bucket rest; f(elem))
	      | bucket nil = ()
	    fun table i = (bucket(s sub i); table(i+1))
         in table 0 handle Subscript => ()
        end

    fun list t =
        let fun f i = if i<0 then nil else (t sub i) @ f (i-1)
         in f (tableSize - 1)
        end

end;

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0