home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Moscow ML 1.42 / lib / Substring.sig < prev    next >
Encoding:
Text File  |  1997-08-18  |  9.8 KB  |  221 lines  |  [TEXT/Moml]
  1. (* Substring -- SML Basis Library *)
  2.  
  3. type substring
  4.  
  5. val substring : string * int * int -> substring
  6. val extract   : string * int * int option -> substring
  7. val all       : string -> substring
  8. val string    : substring -> string
  9. val base      : substring -> (string * int * int)
  10.  
  11. val isEmpty   : substring -> bool
  12. val getc      : substring -> (char * substring) option
  13. val first     : substring -> char option
  14. val triml     : int -> substring -> substring
  15. val trimr     : int -> substring -> substring
  16. val sub       : substring * int -> char
  17. val size      : substring -> int
  18. val slice     : substring * int * int option -> substring
  19. val concat    : substring list -> string
  20. val explode   : substring -> char list
  21. val isPrefix  : string -> substring -> bool
  22. val compare   : substring * substring -> order
  23. val collate   : (char * char -> order) -> substring * substring -> order
  24.  
  25. val dropl     : (char -> bool) -> substring -> substring
  26. val dropr     : (char -> bool) -> substring -> substring
  27. val takel     : (char -> bool) -> substring -> substring
  28. val taker     : (char -> bool) -> substring -> substring
  29. val splitl    : (char -> bool) -> substring -> substring * substring
  30. val splitr    : (char -> bool) -> substring -> substring * substring
  31. val splitAt   : substring * int -> substring * substring
  32.  
  33. val position  : string -> substring -> substring * substring
  34.  
  35. exception Span
  36. val span      : substring * substring -> substring
  37.  
  38. val translate : (char -> string) -> substring -> string
  39.  
  40. val tokens    : (char -> bool) -> substring -> substring list
  41. val fields    : (char -> bool) -> substring -> substring list
  42.  
  43. val foldl     : (char * 'a -> 'a) -> 'a -> substring -> 'a
  44. val foldr     : (char * 'a -> 'a) -> 'a -> substring -> 'a
  45. val app       : (char -> unit) -> substring -> unit
  46.  
  47. (* A substring is an abstract representation of a piece of a string.
  48.    The type [substring] is the abstract type of substrings of a basestring.
  49.    A substring (s,i,n) is valid if 0 <= i <= i+n <= size s, 
  50.                   or equivalently, 0 <= i and 0 <= n and i+n <= size s.  
  51.    A valid substring (s, i, n) represents the string s[i...i+n-1].  
  52.    Invariant in the implementation: Any value of type substring is valid.
  53.  
  54.    [substring(s, i, n)] creates the substring (s, i, n), consisting of
  55.    the substring of s with length n starting at i.  Raises Subscript
  56.    if i<0 or n<0 or i+n > size s.  Equivalent to extract(s, i, SOME n).
  57.  
  58.    [extract(s, i, NONE)] creates the substring (s, i, size s-i)
  59.    consisting of the tail of s starting at i.  
  60.    Raises Subscript if i<0 or i > size s.
  61.  
  62.    [extract(s, i, SOME n)] creates the substring (s, i, n),
  63.    consisting of the substring of s with length n starting at i.
  64.    Raises Subscript if i<0 or n<0 or i+n > size s.
  65.  
  66.    [all s] is the substring (s, 0, size s).
  67.  
  68.    [string sus] is the string s[i..i+n-1] represented by sus = (s, i, n).
  69.  
  70.    [base sus] is the concrete triple (s, i, n), where sus = (s, i, n).
  71.  
  72.    [isEmpty (s, i, n)] true if the substring is empty (that is, n = 0).
  73.  
  74.    [getc sus] returns SOME(c, rst) where c is the first character and
  75.    rst the remainder of sus, if sus is non-empty; otherwise returns
  76.    NONE.  Note that 
  77.     #1 o valOf o scanFn Substring.getc
  78.    is equivalent to, but more efficient than, 
  79.     valOf o StringCvt.scanString scanFn o Substring.string
  80.  
  81.    [first sus] returns SOME c where c is the first character in sus,
  82.    if sus is non-empty; otherwise returns NONE.
  83.  
  84.    [triml k sus] returns sus less its leftmost k characters; or the empty 
  85.    string at the end of sus if it has less than k characters.
  86.  
  87.    [trimr k sus] returns sus less its rightmost k characters; or the empty 
  88.    string at the beginning of sus if it has less than k characters.
  89.  
  90.    [sub (sus, k)] returns the k'th character of the substring; that is,
  91.    s(i+k) where sus = (s, i, n).  Raises Subscript if k<0 or k>=n.
  92.  
  93.    [size (s, i, n)] returns the size of the substring, that is, n.
  94.  
  95.    [slice (sus, i', NONE)] returns the substring (s, i+i', n-i'), where
  96.    sus = (s, i, n).  Raises Subscript if i' < 0 or i' > n.
  97.  
  98.    [slice (sus, i', SOME n')] returns the substring (s, i+i', n'), where
  99.    sus = (s, i, n).  Raises Subscript if i' < 0 or n' < 0 or i'+n' >= n.
  100.  
  101.    [concat suss] returns a string consisting of the concatenation of
  102.    the substrings.  Equivalent to String.concat (List.map string suss).
  103.  
  104.    [explode sus] returns the list of characters of sus, that is,
  105.        [s(i), s(i+1), ..., s(i+n-1)]
  106.    where sus = (s, i, n).  Equivalent to String.explode(string ss).
  107.  
  108.    [isPrefix s1 s2] is true if s1 is a prefix of s2. That is, if there 
  109.    exists a string t such that string s1 ^ t = string s2.
  110.  
  111.    [compare (sus1, sus2)] performs lexicographic comparison, using the
  112.    standard ordering Char.compare on the characters.  Returns LESS,
  113.    EQUAL, or GREATER, according as sus1 is less than, equal to, or
  114.    greater than sus2.  Equivalent to, but more efficient than,
  115.        String.compare(string sus1, string sus2).
  116.  
  117.    [collate cmp (sus1, sus2)] performs lexicographic comparison, using the 
  118.    given ordering cmp on characters.  Equivalent to, but more efficient 
  119.    than, String.collate cmp (string sus1, string sus2).
  120.  
  121.    [dropl p sus] drops the longest prefix (left substring) of sus all
  122.    of whose characters satisfy predicate p.  If all characters do, it
  123.    returns the empty substring (s, i+n, 0) where sus = (s, i, n).
  124.  
  125.    [dropr p sus] drops the longest suffix (right substring) of sus all
  126.    of whose characters satisfy predicate p.  If all characters do, it
  127.    returns the empty substring (s, i, 0) where sus = (s, i, n).
  128.  
  129.    [takel p sus] returns the longest prefix (left substring) of sus
  130.    all of whose characters satisfy predicate p.  That is, if the
  131.    left-most character does not satisfy p, returns the empty (s, i, 0)
  132.    where sus = (s, i, n).
  133.  
  134.    [taker p sus] returns the longest suffix (right substring) of sus
  135.    all of whose characters satisfy predicate p.  That is, if the
  136.    right-most character satisfies p, returns the empty (s, i+n, 0)
  137.    where sus = (s, i, n).
  138.  
  139.    Let p be a predicate and xxxxfyyyyfzzzz a string where all
  140.    characters in xxxx and zzzz satisfy p, and f a is character
  141.    not satisfying p.  Then
  142.  
  143.                 sus = xxxxfyyyyfzzzz         sus = xxxxzzzz
  144.         ------------------------------------------------------
  145.         dropl p sus =     fyyyyfzzzz               
  146.         dropr p sus = xxxxfyyyyf       
  147.         takel p sus = xxxx                         xxxxzzzz
  148.         taker p sus =           zzzz               xxxxzzzz
  149.  
  150.    It also holds that 
  151.         concat[takel p sus, dropl p sus] = string sus
  152.         concat[dropr p sus, taker p sus] = string sus 
  153.  
  154.    [splitl p sus] splits sus into a pair (sus1, sus2) of substrings
  155.    where sus1 is the longest prefix (left substring) all of whose
  156.    characters satisfy p, and sus2 is the rest.  That is, sus2 begins
  157.    with the leftmost character not satisfying p.  Disregarding
  158.    sideeffects, we have: 
  159.     splitl p sus = (takel p sus, dropl p sus).
  160.  
  161.    [splitr p sus] splits sus into a pair (sus1, sus2) of substrings
  162.    where sus2 is the longest suffix (right substring) all of whose
  163.    characters satisfy p, and sus1 is the rest.  That is, sus1 ends
  164.    with the rightmost character not satisfying p.  Disregarding
  165.    sideeffects, we have:
  166.     splitr p sus = (dropr p sus, taker p sus)
  167.  
  168.    [splitAt (sus, k)] returns the pair (sus1, sus2) of substrings,
  169.    where sus1 contains the first k characters of sus, and sus2
  170.    contains the rest.  Raises Subscript if k < 0 or k > size sus.
  171.  
  172.    [position s (s',i,n)] splits the substring into a pair (pref, suff)
  173.    of substrings, where suff the longest suffix of (s', i, n) which
  174.    has s as a prefix.  More precisely, let m = size s.  If there is a
  175.    least index k in i..i+n-m for which s = s'[k..k+m-1], 
  176.    then the result is       pref = (s', i, k-i) and suff = (s', k, n-(k-i)); 
  177.    otherwise the result is  pref = (s', i, n)   and suff = (s', i+n, 0).
  178.  
  179.    [span (sus1, sus2)] returns a substring spanning from the start of
  180.    sus1 to the end of sus2, provided this is well-defined: sus1 and
  181.    sus2 must have the same underlying string, and the start of sus1
  182.    must not be to the right of the end of sus2; otherwise raises Span.
  183.  
  184.    More precisely, if base(sus1) = (s,i,n) and base(sus2) = (s',i',n') 
  185.    and s = s' and i <= i'+n', then base(join(sus1, sus2)) = (s, i, i'+n'-i).
  186.    This may be used to compute `span', `union', and `intersection'.
  187.  
  188.    [translate f sus] applies f to every character of sus, from left to
  189.    right, and returns the concatenation of the results.  Raises Size
  190.    if the sum of their sizes is greater than String.maxSize.
  191.    Equivalent to String.concat(List.map f (explode sus)).
  192.  
  193.    [tokens p sus] returns the list of tokens in sus, from left to right, 
  194.    where a token is a non-empty maximal substring of sus not containing 
  195.    any delimiter, and a delimiter is a character satisfying p.
  196.  
  197.    [fields p sus] returns the list of fields in sus, from left to right, 
  198.    where a field is a (possibly empty) maximal substring of sus not 
  199.    containing any delimiter, and a delimiter is a character satisfying p.
  200.  
  201.    Two tokens may be separated by more than one delimiter, whereas two
  202.    fields are separated by exactly one delimiter.  If the only delimiter 
  203.    is the character #"|", then
  204.        "abc||def" contains two tokens:   "abc" and "def"
  205.        "abc||def" contains three fields: "abc" and "" and "def"
  206.  
  207.    [foldl f e sus] folds f over sus from left to right.  That is, 
  208.    evaluates f(s[i+n-1], f( ... f(s[i+1], f(s[i] % e)) ...)) 
  209.    tail-recursively, where sus = (s, i, n).  
  210.    Equivalent to List.foldl f e (explode sus).
  211.  
  212.    [foldr f e sus] folds f over sus from right to left.  That is, 
  213.    evaluates f(s[i], f(s[i+1], f(... f(s[i+n-1] % e) ...)))
  214.    tail-recursively, where sus = (s, i, n).
  215.    Equivalent to List.foldr f e (explode sus).
  216.  
  217.    [app f sus] applies f to all characters of sus, from left to right.
  218.    Equivalent to List.app f (explode sus).
  219.  
  220. *)
  221.