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

SCM Repository

[smlnj] Annotation of /sml/trunk/src/MLRISC/library/sortedlist.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/library/sortedlist.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 496 - (view) (download)

1 : monnier 496 (* Copyright 1989 by AT&T Bell Laboratories *)
2 :     structure SortedList =
3 :     struct
4 :    
5 :     fun enter(new:int,l) =
6 :     let fun f [] = [new]
7 :     | f (l as h::t) = if new<h then new::l else if new>h then h::f t else l
8 :     in f l
9 :     end
10 :    
11 :     fun merge(a,[]) = a
12 :     | merge([],a) = a
13 :     | merge(l as (i:int)::a, m as j::b) =
14 :     if j<i then j::merge(l,b) else i::merge(a,if i<j then m else b)
15 :    
16 :     local fun loop (a::b::rest) = loop(merge(a,b)::loop rest)
17 :     | loop l = l
18 :     in fun foldmerge l = hd(loop l) handle Hd => []
19 :     end
20 :    
21 :     fun uniq l =
22 :     let fun split([],l,r) = (l,r)
23 :     | split(h::t,l,r) = split(t,r,h::l)
24 :     fun sort [] = []
25 :     | sort (l as [_]) = l
26 :     | sort (l as [x : int,y : int]) =
27 :     if x = y then [x] else if x < y then l else [y,x]
28 :     | sort l = let val (l,r) = split(l,[],[])
29 :     in merge(sort l, sort r) end
30 :     in sort l
31 :     end
32 :    
33 :     fun remove(x as (xl:int)::xr, y as yl::yr) =
34 :     if xl>yl then yl::remove(x,yr) else remove(xr,if xl<yl then y else yr)
35 :     | remove(_,y) = y
36 :    
37 :     fun rmv (x : int,l) =
38 :     let fun loop nil = nil
39 :     | loop (a::b) = if x=a then b else a::loop b
40 :     in loop l
41 :     end
42 :    
43 :     fun member l (e:int) =
44 :     let fun f [] = false
45 :     | f (h::t) = if h<e then f t else e=h
46 :     in f l
47 :     end
48 :    
49 :     fun intersect(nil,_) = nil
50 :     | intersect(_,nil) = nil
51 :     | intersect(l as (a:int)::b,r as c::d) =
52 :     if a=c then a::intersect(b,d)
53 :     else if a<c then intersect(b,r)
54 :     else intersect(l,d)
55 :    
56 :     fun difference(nil,_) = nil
57 :     | difference(l,nil) = l
58 :     | difference(l as (a:int)::b,r as c::d) =
59 :     if a=c then difference(b,d)
60 :     else if a<c then a::difference(b,r)
61 :     else difference(l,d)
62 :     end
63 :    

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