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/eXene/widgets/composite/index.sml
ViewVC logotype

Annotation of /sml/trunk/src/eXene/widgets/composite/index.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2 - (view) (download)

1 : monnier 2 (* index.sml
2 :     *
3 :     * COPYRIGHT (c) 1992 by AT&T Bell Laboratories See COPYRIGHT file for details.
4 :     *
5 :     * Utility functions for managing lists indexed by integers.
6 :     *)
7 :    
8 :     signature INDEX =
9 :     sig
10 :    
11 :     exception BadIndex
12 :    
13 :     val find : (int * 'a -> 'b option) -> 'a list -> 'b list
14 :     val findi : 'a list * int -> 'a
15 :     val isValid : 'a list * int -> bool
16 :     val chkSort : int list -> int list
17 :     val chkUSort : int list -> int list
18 :     val doMap : 'a list * ('a -> 'a) * int list -> 'a list
19 :     val delete : 'a list * int list -> 'a list * 'a list
20 :     val insert : 'a list * int * 'a list -> 'a list
21 :     val preIndices : int * int list -> int option
22 :    
23 :     end (* INDEX *)
24 :    
25 :     structure Index : INDEX =
26 :     struct
27 :    
28 :     exception BadIndex
29 :    
30 :     fun find pred cl = let
31 :     fun gv (_,[]) = []
32 :     | gv (i,w::rest) =
33 :     case pred (i,w) of
34 :     NONE => gv (i+1,rest)
35 :     | SOME v => v::(gv (i+1,rest))
36 :     in gv (0,cl) end
37 :    
38 :     fun isValid (l, index) = let
39 :     fun chk(j,[]) = j = index
40 :     | chk(j,_::rest) = j = index orelse chk(j+1,rest)
41 :     in
42 :     if index < 0 then false else chk (0,l)
43 :     end
44 :    
45 :     fun findi (l, i) = let
46 :     fun f([], _) = raise BadIndex
47 :     | f(a::rest, j) = if i = j then a else f(rest, j+1)
48 :     in f(l,0) end
49 :    
50 :     fun cmp (i,j : int) = if i < j then LESS
51 :     else if i = j then EQUAL
52 :     else GREATER
53 :     val sort = ListMergeSort.sort Int.>
54 :     val sorted = ListMergeSort.sorted Int.>
55 :     val usort = ListMergeSort.uniqueSort cmp
56 :    
57 :     fun usorted [] = true
58 :     | usorted [_ : int] = true
59 :     | usorted (x::(rest as (y::_))) = x < y andalso usorted rest
60 :    
61 :     fun chkSort [] = []
62 :     | chkSort (l as [_]) = l
63 :     | chkSort (l as [i,j]) = if i <= j then l else [j,i]
64 :     | chkSort l = if sorted l then l else sort l
65 :    
66 :     fun chkUSort [] = []
67 :     | chkUSort (l as [_]) = l
68 :     | chkUSort (l as [i,j]) = if i < j then l
69 :     else if i = j then [i]
70 :     else [j,i]
71 :     | chkUSort l = if usorted l then l else usort l
72 :    
73 :     (* doMap: 'a list * ('a -> 'a) * int list -> 'a list
74 :     * Applies mapfn to items whose index is in index list
75 :     * Assume il is sorted in non-decreasing order
76 :     *)
77 :     fun doMap (cl, mapfn, il) = let
78 :     fun domap(_, l, []) = l
79 :     | domap(_, [], _) = raise BadIndex
80 :     | domap(j, c::cl', il as i::il') =
81 :     if i < j then raise BadIndex
82 :     else if i = j then (mapfn c)::(domap(j+1,cl',il'))
83 :     else c::(domap(j+1,cl',il))
84 :     in
85 :     domap (0, cl, il)
86 :     end
87 :    
88 :     (* delete: 'a list * int list -> 'a list * 'a list
89 :     * Remove all items whose index appears in the
90 :     * list of integers.
91 :     *)
92 :     fun delete (cl, il) = let
93 :     fun del(_, l, []) = (l, [])
94 :     | del(_, [], _) = raise BadIndex
95 :     | del(j, c::cl', il as i::il') =
96 :     if i < j then raise BadIndex
97 :     else if i = j then let
98 :     val (l,d) = del(j+1,cl',il')
99 :     in
100 :     (l,c::d)
101 :     end
102 :     else let
103 :     val (l,d) = del(j+1,cl',il)
104 :     in
105 :     (c::l,d)
106 :     end
107 :     in
108 :     del (0, cl, il)
109 :     end
110 :    
111 :     fun insert (cl, index, boxel) = let
112 :     fun ins (0, l) = boxel @ l
113 :     | ins (i, x::r) = x::(ins(i-1,r))
114 :     | ins (i, []) = raise BadIndex
115 :     in
116 :     if index < 0 then raise BadIndex
117 :     else ins(index, cl)
118 :     end
119 :    
120 :     fun preIndices (index : int, il) = let
121 :     fun loop (cnt, []) = SOME cnt
122 :     | loop (cnt, i::l) =
123 :     if i < index then loop(cnt+1,l)
124 :     else if i = index then NONE
125 :     else SOME cnt
126 :     in loop(0,il) end
127 :     end

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