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 /smlnj-lib/trunk/HashCons/hash-cons-set.sml
ViewVC logotype

Annotation of /smlnj-lib/trunk/HashCons/hash-cons-set.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 967 - (view) (download)
Original Path: sml/trunk/src/smlnj-lib/HashCons/hash-cons-set.sml

1 : jhr 967 (* hash-cons-set.sml
2 :     *
3 :     * COPYRIGHT (c) 2001 Bell Labs, Lucent Technologies
4 :     *
5 :     * This is an implementation of the HASH_CONS_SET signature that is built
6 :     * on top of the WordRedBlackMap structure. Eventually, it will be replaced
7 :     * by an implmementation that uses Patricia trees.
8 :     *)
9 :    
10 :     structure HashConsSet : HASH_CONS_SET =
11 :     struct
12 :    
13 :     structure HC = HashCons
14 :     structure Map = WordRedBlackMap
15 :    
16 :     type 'a obj = 'a HC.obj
17 :     type 'a set = 'a obj Map.map
18 :    
19 :     val empty = Map.empty
20 :     fun singleton obj = Map.singleton(HC.tag obj, obj)
21 :     fun add (set, obj) = Map.insert (set, HC.tag obj, obj)
22 :     fun add' (obj, set) = Map.insert (set, HC.tag obj, obj)
23 :     fun addList (set, l) = List.foldl add' set l
24 :     fun delete (set : 'a set, obj) = #1(Map.remove(set, HC.tag obj))
25 :     fun member (set, obj) = Map.inDomain(set, HC.tag obj)
26 :     val isEmpty = Map.isEmpty
27 :     fun equal (set1, set2) = (case Map.collate (fn _ => EQUAL) (set1, set2)
28 :     of EQUAL => true
29 :     | _ => false
30 :     (* end case *))
31 :     fun compare arg = Map.collate (fn _ => EQUAL) arg
32 :    
33 :     fun isSubset _ = raise Fail "isSubset"
34 :    
35 :     val numItems = Map.numItems
36 :     val listItems = Map.listItems
37 :     fun union arg = Map.unionWith (fn (a, _) => a) arg
38 :     fun intersection arg = Map.intersectWith (fn (a, _) => a) arg
39 :    
40 :     fun difference _ = raise Fail "difference"
41 :    
42 :     val map = Map.map
43 :     val mapPartial = Map.mapPartial
44 :     val app = Map.app
45 :     val foldl = Map.foldl
46 :     val foldr = Map.foldr
47 :    
48 :     fun partition _ = raise Fail "partition"
49 :    
50 :     val filter = Map.filter
51 :     fun exists pred set = List.exists pred (listItems set)
52 :     fun find pred set = List.find pred (listItems set)
53 :    
54 :     end

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