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/smlnj-lib/Util/int-list-set.sml
ViewVC logotype

Annotation of /sml/trunk/src/smlnj-lib/Util/int-list-set.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 30 - (view) (download)

1 : monnier 2 (* int-list-set.sml
2 :     *
3 :     * COPYRIGHT (c) 1996 by AT&T Research. See COPYRIGHT file for details.
4 :     *
5 :     * An implementation of finite sets of integers, which uses a sorted list
6 :     * representation.
7 :     *)
8 :    
9 :     structure IntListSet :> ORD_SET where type Key.ord_key = Int.int =
10 :     struct
11 :    
12 :     structure Key =
13 :     struct
14 :     type ord_key = int
15 :     val compare = Int.compare
16 :     end
17 :    
18 :     (* sets are represented as ordered lists of integers *)
19 :     type item = Key.ord_key
20 :     type set = item list
21 :    
22 :     val empty = []
23 :    
24 :     fun singleton x = [x]
25 :    
26 :     fun add (l, item) = let
27 :     fun f [] = [item]
28 :     | f (elem::r) = (case Key.compare(item, elem)
29 :     of LESS => item :: elem :: r
30 :     | EQUAL => item :: r
31 :     | GREATER => elem :: (f r)
32 :     (* end case *))
33 :     in
34 :     f l
35 :     end
36 : monnier 29 fun add' (s, x) = add(x, s)
37 : monnier 2
38 :     fun union (s1, s2) = let
39 :     fun merge ([], l2) = l2
40 :     | merge (l1, []) = l1
41 :     | merge (x::r1, y::r2) = (case Key.compare(x, y)
42 :     of LESS => x :: merge(r1, y::r2)
43 :     | EQUAL => x :: merge(r1, r2)
44 :     | GREATER => y :: merge(x::r1, r2)
45 :     (* end case *))
46 :     in
47 :     merge (s1, s2)
48 :     end
49 :    
50 :     fun intersection (s1, s2) = let
51 :     fun merge ([], l2) = []
52 :     | merge (l1, []) = []
53 :     | merge (x::r1, y::r2) = (case Key.compare(x, y)
54 :     of LESS => merge(r1, y::r2)
55 :     | EQUAL => x :: merge(r1, r2)
56 :     | GREATER => merge(x::r1, r2)
57 :     (* end case *))
58 :     in
59 :     merge (s1, s2)
60 :     end
61 :    
62 :     fun difference (s1, s2) = let
63 :     fun merge ([], l2) = []
64 :     | merge (l1, []) = l1
65 :     | merge (x::r1, y::r2) = (case Key.compare(x, y)
66 :     of LESS => x :: merge(r1, y::r2)
67 :     | EQUAL => merge(r1, r2)
68 :     | GREATER => merge(x::r1, r2)
69 :     (* end case *))
70 :     in
71 :     merge (s1, s2)
72 :     end
73 :    
74 :     fun addList (l, items) = let
75 :     val items' = List.foldl (fn (x, set) => add(set, x)) [] items
76 :     in
77 :     union (l, items')
78 :     end
79 :    
80 :     (* Remove an item, returning new map and value removed.
81 :     * Raise LibBase.NotFound if not found.
82 :     *)
83 :     fun delete (l, elem) = let
84 :     fun f (_, []) = raise LibBase.NotFound
85 :     | f (prefix, elem' :: r) = (case Key.compare(elem, elem')
86 :     of LESS => raise LibBase.NotFound
87 :     | EQUAL => List.revAppend(prefix, r)
88 :     | GREATER => f(elem' :: prefix, r)
89 :     (* end case *))
90 :     in
91 :     f ([], l)
92 :     end
93 :    
94 :     fun member (l, item) = let
95 :     fun f [] = false
96 :     | f (elem :: r) = (case Key.compare(item, elem)
97 :     of LESS => false
98 :     | EQUAL => true
99 :     | GREATER => f r
100 :     (* end case *))
101 :     in
102 :     f l
103 :     end
104 :    
105 :     fun isEmpty [] = true
106 :     | isEmpty _ = false
107 :    
108 :     fun equal (s1, s2) = let
109 :     fun f ([], []) = true
110 :     | f ((x : int)::r1, y::r2) = (x = y) andalso f (r1, r2)
111 :     | f _ = false
112 :     in
113 :     f (s1, s2)
114 :     end
115 :    
116 :     fun compare ([], []) = EQUAL
117 :     | compare ([], _) = LESS
118 :     | compare (_, []) = GREATER
119 :     | compare (x1::r1, x2::r2) = (case Key.compare(x1, x2)
120 :     of EQUAL => compare (r1, r2)
121 :     | order => order
122 :     (* end case *))
123 :    
124 :     (* Return true if and only if the first set is a subset of the second *)
125 :     fun isSubset (s1, s2) = let
126 :     fun f ([], _) = true
127 :     | f (_, []) = false
128 :     | f (x::r1, y::r2) = (case Key.compare(x, y)
129 :     of LESS => false
130 :     | EQUAL => f (r1, r2)
131 :     | GREATER => f (x::r1, r2)
132 :     (* end case *))
133 :     in
134 :     f (s1, s2)
135 :     end
136 :    
137 :     (* Return the number of items in the set *)
138 :     fun numItems l = List.length l
139 :    
140 :     (* Return a list of the items in the set *)
141 :     fun listItems l = l
142 :    
143 :     val app = List.app
144 :     fun map f s1 = List.foldl (fn (x, s) => add(s, f x)) [] s1
145 :     val foldr = List.foldr
146 :     val foldl = List.foldl
147 :     val filter = List.filter
148 :     val exists = List.exists
149 :     val find = List.find
150 :    
151 :     end (* IntListMap *)
152 :    

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