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

SCM Repository

[smlnj] Diff of /sml/trunk/src/system/smlnj/init/substring.sml
ViewVC logotype

Diff of /sml/trunk/src/system/smlnj/init/substring.sml

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1154, Wed Mar 20 20:44:43 2002 UTC revision 1155, Wed Mar 20 20:52:51 2002 UTC
# Line 132  Line 132 
132      fun isPrefix s1 (SS(s2, i2, n2)) = PreString.isPrefix (s1, s2, i2, n2)      fun isPrefix s1 (SS(s2, i2, n2)) = PreString.isPrefix (s1, s2, i2, n2)
133      fun isSuffix s1 (SS(s2, i2, n2)) =      fun isSuffix s1 (SS(s2, i2, n2)) =
134          PreString.isPrefix (s1, s2, i2 + n2 - stringSize s1, n2)          PreString.isPrefix (s1, s2, i2 + n2 - stringSize s1, n2)
135      fun isSubstring s1 (SS(s2, i2, n2)) = (* FIXME: KMP or BM (?) *)      fun isSubstring s = let
136          let val stop = i2 + n2 - stringSize s1          val stringsearch = PreString.kmp s
137              fun matches_at_or_after i =          fun search (SS (s', i, n)) = stringsearch (s', i, i + n) >= 0
                 i < stop andalso  
                 (PreString.isPrefix (s1, s2, i, n2) orelse  
                  matches_at_or_after (i + 1))  
138          in          in
139              matches_at_or_after i2          search
140          end          end
141      fun compare (SS(s1, i1, n1), SS(s2, i2, n2)) =      fun compare (SS(s1, i1, n1), SS(s2, i2, n2)) =
142            PreString.cmp (s1, i1, n1, s2, i2, n2)            PreString.cmp (s1, i1, n1, s2, i2, n2)
# Line 177  Line 174 
174      val taker  = scanr (fn (s, i, n, k) => SS(s, i+k, n-k))      val taker  = scanr (fn (s, i, n, k) => SS(s, i+k, n-k))
175      end (* local *)      end (* local *)
176    
177    (* find the position of the first occurrence of s in the substring.      (* This is using the KMP matcher from PreString. *)
178     * NOTE: some day we might want to implement KMP matching for this      fun position s = let
179     *)          val stringsearch = PreString.kmp s
180      fun position s (SS (s', i, n)) = let          fun search (ss as SS (s', i, n)) = let
181            val len = stringSize s              val match = stringsearch (s', i, n - i)
           fun eq (j, k) = (j >= len) orelse  
                 ((unsafeSub(s, j) = unsafeSub(s', k)) andalso eq (j+1, k+1))  
           val stop = i+n-len  
           fun cmp k =  
                 if (k > stop) then i+n (* failure *)  
                 else if eq(0, k) then k  
                 else cmp(k+1)  
           val indx = cmp i  
182            in            in
183              (SS(s', i, indx-i), SS(s', indx, i+n-indx))              if match < 0 then (ss, SS (s', i + n, 0))
184                else (SS (s', i, match - i), SS (s', match, i + n - match))
185            end
186        in
187            search
188            end            end
189    
190      fun span (SS(s1, i1, n1), SS(s2, i2, n2)) =      fun span (SS(s1, i1, n1), SS(s2, i2, n2)) =

Legend:
Removed from v.1154  
changed lines
  Added in v.1155

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