root/trunk/tango/text/Util.d

/*******************************************************************************

        copyright:      Copyright (c) 2004 Kris Bell. All rights reserved

        license:        BSD style: $(LICENSE)

        version:        Apr 2004: Initial release
                        Dec 2006: South Seas version

        author:         Kris


        Placeholder for a variety of wee functions. These functions are all
        templated with the intent of being used for arrays of char, wchar,
        and dchar. However, they operate correctly with other array types
        also.

        Several of these functions return an index value, representing where
        some criteria was identified. When said criteria is not matched, the
        functions return a value representing the array length provided to
        them. That is, for those scenarios where C functions might typically
        return -1 these functions return length instead. This operate nicely
        with D slices:
        ---
        auto text = "happy:faces";
        
        assert (text[0 .. locate (text, ':')] == "happy");
        
        assert (text[0 .. locate (text, '!')] == "happy:faces");
        ---

        The contains() function is more convenient for trivial lookup
        cases:
        ---
        if (contains ("fubar", '!'))
            ...
        ---

        Note that where some functions expect a uint as an argument, the
        D template-matching algorithm will fail where an int is provided
        instead. This is the typically the cause of "template not found"
        errors. Also note that name overloading is not supported cleanly
        by IFTI at this time, so is not applied here.


        Applying the D "import alias" mechanism to this module is highly
        recommended, in order to limit namespace pollution:
        ---
        import Util = tango.text.Util;

        auto s = Util.trim ("  foo ");
        ---
                

        Function templates:
        ---
        trim (source)                               // trim whitespace
        triml (source)                              // trim whitespace
        trimr (source)                              // trim whitespace
        strip (source, match)                       // trim elements
        stripl (source, match)                      // trim elements
        stripr (source, match)                      // trim elements
        chopl (source, match)                       // trim pattern match
        chopr (source, match)                       // trim pattern match
        delimit (src, set)                          // split on delims
        split (source, pattern)                     // split on pattern
        splitLines (source);                        // split on lines
        head (source, pattern, tail)                // split to head & tail
        join (source, postfix, output)              // join text segments
        prefix (dst, prefix, content...)            // prefix text segments
        postfix (dst, postfix, content...)          // postfix text segments
        combine (dst, prefix, postfix, content...)  // combine lotsa stuff
        repeat (source, count, output)              // repeat source 
        replace (source, match, replacement)        // replace chars
        substitute (source, match, replacement)     // replace/remove matches
        count (source, match)                       // count instances
        contains (source, match)                    // has char?
        containsPattern (source, match)             // has pattern?
        locate (source, match, start)               // find char
        locatePrior (source, match, start)          // find prior char
        locatePattern (source, match, start);       // find pattern
        locatePatternPrior (source, match, start);  // find prior pattern
        indexOf (s*, match, length)                 // low-level lookup
        mismatch (s1*, s2*, length)                 // low-level compare
        matching (s1*, s2*, length)                 // low-level compare
        isSpace (match)                             // is whitespace?
        unescape(source, output)                    // convert '\' prefixes
        layout (destination, format ...)            // featherweight printf
        lines (str)                                 // foreach lines
        quotes (str, set)                           // foreach quotes
        delimiters (str, set)                       // foreach delimiters
        patterns (str, pattern)                     // foreach patterns
        ---

        Please note that any 'pattern' referred to within this module
        refers to a pattern of characters, and not some kind of regex
        descriptor. Use the Regex module for regex operation.

*******************************************************************************/

module tango.text.Util;

/******************************************************************************

        Trim the provided array by stripping whitespace from both
        ends. Returns a slice of the original content

******************************************************************************/

T[] trim(T) (T[] source)
{
        T*   head = source.ptr,
             tail = head + source.length;

        while (head < tail && isSpace(*head))
               ++head;

        while (tail > head && isSpace(*(tail-1)))
               --tail;

        return head [0 .. tail - head];
}

/******************************************************************************

        Trim the provided array by stripping whitespace from the left.
        Returns a slice of the original content

******************************************************************************/

T[] triml(T) (T[] source)
{
        T*   head = source.ptr,
             tail = head + source.length;

        while (head < tail && isSpace(*head))
               ++head;

        return head [0 .. tail - head];
}

/******************************************************************************

        Trim the provided array by stripping whitespace from the right.
        Returns a slice of the original content

******************************************************************************/

T[] trimr(T) (T[] source)
{
        T*   head = source.ptr,
             tail = head + source.length;

        while (tail > head && isSpace(*(tail-1)))
               --tail;

        return head [0 .. tail - head];
}

/******************************************************************************

        Trim the given array by stripping the provided match from
        both ends. Returns a slice of the original content

******************************************************************************/

T[] strip(T) (T[] source, T match)
{
        T*   head = source.ptr,
             tail = head + source.length;

        while (head < tail && *head is match)
               ++head;

        while (tail > head && *(tail-1) is match)
               --tail;

        return head [0 .. tail - head];
}

/******************************************************************************

        Trim the given array by stripping the provided match from
        the left hand side. Returns a slice of the original content

******************************************************************************/

T[] stripl(T) (T[] source, T match)
{
        T*   head = source.ptr,
             tail = head + source.length;

        while (head < tail && *head is match)
               ++head;

        return head [0 .. tail - head];
}

/******************************************************************************

        Trim the given array by stripping the provided match from
        the right hand side. Returns a slice of the original content

******************************************************************************/

T[] stripr(T) (T[] source, T match)
{
        T*   head = source.ptr,
             tail = head + source.length;

        while (tail > head && *(tail-1) is match)
               --tail;

        return head [0 .. tail - head];
}

/******************************************************************************

        Chop the given source by stripping the provided match from
        the left hand side. Returns a slice of the original content

******************************************************************************/

T[] chopl(T) (T[] source, T[] match)
{
        if (match.length <= source.length)
            if (source[0 .. match.length] == match)
                source = source [match.length .. $];

        return source;
}

/******************************************************************************

        Chop the given source by stripping the provided match from
        the right hand side. Returns a slice of the original content

******************************************************************************/

T[] chopr(T) (T[] source, T[] match)
{
        if (match.length <= source.length)
            if (source[$-match.length .. $] == match)
                source = source [0 .. $-match.length];

        return source;
}

/******************************************************************************

        Replace all instances of one element with another (in place)

******************************************************************************/

T[] replace(T) (T[] source, T match, T replacement)
{
        foreach (inout c; source)
                 if (c is match)
                     c = replacement;
        return source;
}

/******************************************************************************

        Substitute all instances of match from source. Set replacement
        to null in order to remove instead of replace

******************************************************************************/

T[] substitute(T) (T[] source, T[] match, T[] replacement)
{
        T[] output;

        foreach (s; patterns (source, match, replacement))
                    output ~= s;
        return output;
}

/******************************************************************************

        Count all instances of match within source 

******************************************************************************/

uint count(T) (T[] source, T[] match)
{
        uint c;

        foreach (s; patterns (source, match))
                    ++c;
        return c;
}

/******************************************************************************

        Returns whether or not the provided array contains an instance
        of the given match
        
******************************************************************************/

bool contains(T) (T[] source, T match)
{
        return indexOf (source.ptr, match, source.length) != source.length;
}

/******************************************************************************

        Returns whether or not the provided array contains an instance
        of the given match
        
******************************************************************************/

bool containsPattern(T) (T[] source, T[] match)
{
        return locatePattern (source, match) != source.length;
}

/******************************************************************************

        Return the index of the next instance of 'match' starting at
        position 'start', or source.length where there is no match.

        Parameter 'start' defaults to 0

******************************************************************************/

uint locate(T, U=uint) (T[] source, T match, U start=0)
{return locate!(T) (source, match, start);}

uint locate(T) (T[] source, T match, uint start=0)
{
        if (start > source.length)
            start = source.length;
        
        return indexOf (source.ptr+start, match, source.length - start) + start;
}

/******************************************************************************

        Return the index of the prior instance of 'match' starting
        just before 'start', or source.length where there is no match.

        Parameter 'start' defaults to source.length

******************************************************************************/

uint locatePrior(T, U=uint) (T[] source, T match, U start=uint.max)
{return locatePrior!(T)(source, match, start);}

uint locatePrior(T) (T[] source, T match, uint start=uint.max)
{
        if (start > source.length)
            start = source.length;

        while (start > 0)
               if (source[--start] is match)
                   return start;
        return source.length;
}

/******************************************************************************

        Return the index of the next instance of 'match' starting at
        position 'start', or source.length where there is no match. 

        Parameter 'start' defaults to 0

******************************************************************************/

uint locatePattern(T, U=uint) (T[] source, T[] match, U start=0)
{return locatePattern!(T) (source, match, start);}

uint locatePattern(T) (T[] source, T[] match, uint start=0)
{
        uint    idx;
        T*      p = source.ptr + start;
        uint    extent = source.length - start - match.length + 1;

        if (match.length && extent <= source.length)
            while (extent)
                   if ((idx = indexOf (p, match[0], extent)) is extent)
                        break;
                   else
                      if (matching (p+=idx, match.ptr, match.length))
                          return p - source.ptr;
                      else
                         {
                         extent -= (idx+1);
                         ++p;
                         }

        return source.length;
}
   
/******************************************************************************

        Return the index of the prior instance of 'match' starting
        just before 'start', or source.length where there is no match.

        Parameter 'start' defaults to source.length

******************************************************************************/

uint locatePatternPrior(T, U=uint) (T[] source, T[] match, U start=uint.max)
{return locatePatternPrior!(T)(source, match, start);}

uint locatePatternPrior(T) (T[] source, T[] match, uint start=uint.max)
{
        auto len = source.length;
        
        if (start > len)
            start = len;

        if (match.length && match.length <= len)
            while (start)
                  {
                  start = locatePrior (source, match[0], start);
                  if (start is len)
                      break;
                  else
                     if ((start + match.length) <= len)
                          if (matching (source.ptr+start, match.ptr, match.length))
                              return start;
                  }

        return len;
}

/******************************************************************************

        Split the provided array on the first pattern instance, and 
        return the resultant head and tail. The pattern is excluded 
        from the two segments. 

        Where a segment is not found, tail will be null and the return
        value will be the original array.
        
******************************************************************************/

T[] head(T) (T[] src, T[] pattern, out T[] tail)
{
        auto i = locatePattern (src, pattern);
        if (i != src.length)
           {
           tail = src [i + pattern.length .. $];
           src = src [0 .. i];
           }
        return src;
}

/******************************************************************************

        Split the provided array on the last pattern instance, and 
        return the resultant head and tail. The pattern is excluded 
        from the two segments. 

        Where a segment is not found, head will be null and the return
        value will be the original array.
        
******************************************************************************/

T[] tail(T) (T[] src, T[] pattern, out T[] head)
{
        auto i = locatePatternPrior (src, pattern);
        if (i != src.length)
           {
           head = src [0 .. i];
           src = src [i + pattern.length .. $];
           }
        return src;
}

/******************************************************************************

        Split the provided array wherever a delimiter-set instance is
        found, and return the resultant segments. The delimiters are
        excluded from each of the segments. Note that delimiters are
        matched as a set of alternates rather than as a pattern.

        Splitting on a single delimiter is considerably faster than
        splitting upon a set of alternatives. 

        Note that the src content is not duplicated by this function, 
        but is sliced instead.

******************************************************************************/

T[][] delimit(T) (T[] src, T[] set)
{
        T[][] result;

        foreach (segment; delimiters (src, set))
                 result ~= segment;
        return result;
}

/******************************************************************************

        Split the provided array wherever a pattern instance is
        found, and return the resultant segments. The pattern is
        excluded from each of the segments.
        
        Note that the src content is not duplicated by this function, 
        but is sliced instead.

******************************************************************************/

T[][] split(T) (T[] src, T[] pattern)
{
        T[][] result;

        foreach (segment; patterns (src, pattern))
                 result ~= segment;
        return result;
}

/******************************************************************************

        Convert text into a set of lines, where each line is identified
        by a \n or \r\n combination. The line terminator is stripped from
        each resultant array

        Note that the src content is not duplicated by this function, but
        is sliced instead.

******************************************************************************/

T[][] splitLines(T) (T[] src)
{
        int count;
        
        foreach (line; lines (src))
                 ++count;
        
        T[][] result = new T[][count];

        count = 0;
        foreach (line; lines (src))
                 result [count++] = line;

        return result;
}

/******************************************************************************

        Combine a series of text segments together, each appended with 
        a postfix pattern. An optional output buffer can be provided to
        avoid heap activity - it should be large enough to contain the 
        entire output, otherwise the heap will be used instead.

        Returns a valid slice of the output, containing the concatenated
        text.

******************************************************************************/

T[] join(T) (T[][] src, T[] postfix=null, T[] dst=null)
{
        return combine!(T) (dst, null, postfix, src);
}

/******************************************************************************

        Combine a series of text segments together, each prepended with 
        a prefix pattern. An optional output buffer can be provided to 
        avoid heap activity - it should be large enough to contain the 
        entire output, otherwise the heap will be used instead.

        Note that, unlike join(), the output buffer is specified first
        such that a set of trailing strings can be provided. 

        Returns a valid slice of the output, containing the concatenated
        text.

******************************************************************************/

T[] prefix(T) (T[] dst, T[] prefix, T[][] src...)
{
        return combine!(T) (dst, prefix, null, src);
}

/******************************************************************************

        Combine a series of text segments together, each appended with an 
        optional postfix pattern. An optional output buffer can be provided
        to avoid heap activity - it should be large enough to contain the 
        entire output, otherwise the heap will be used instead.

        Note that, unlike join(), the output buffer is specified first
        such that a set of trailing strings can be provided. 

        Returns a valid slice of the output, containing the concatenated
        text.

******************************************************************************/

T[] postfix(T) (T[] dst, T[] postfix, T[][] src...)
{
        return combine!(T) (dst, null, postfix, src);
}

/******************************************************************************

        Combine a series of text segments together, each prefixed and/or 
        postfixed with optional strings. An optional output buffer can be 
        provided to avoid heap activity - which should be large enough to 
        contain the entire output, otherwise the heap will be used instead.

        Note that, unlike join(), the output buffer is specified first
        such that a set of trailing strings can be provided. 

        Returns a valid slice of the output, containing the concatenated
        text.

******************************************************************************/

T[] combine(T) (T[] dst, T[] prefix, T[] postfix, T[][] src ...)
{
        uint len = src.length * prefix.length + 
                   src.length * postfix.length;

        foreach (segment; src)
                 len += segment.length;
               
        if (dst.length < len)
            dst.length = len;
            
        T* p = dst.ptr;
        foreach (segment; src)
                {
                p[0 .. prefix.length] = prefix;
                p += prefix.length;
                p[0 .. segment.length] = segment;
                p += segment.length;
                p[0 .. postfix.length] = postfix;
                p += postfix.length;
                }

        // remove trailing seperator
        if (len)
            len -= postfix.length;
        return dst [0 .. len];       
}

/******************************************************************************

        Repeat an array for a specific number of times. An optional output 
        buffer can be provided to avoid heap activity - it should be large 
        enough to contain the entire output, otherwise the heap will be used 
        instead.

        Returns a valid slice of the output, containing the concatenated
        text.

******************************************************************************/

T[] repeat(T, U=uint) (T[] src, U count, T[] dst=null)
{return repeat!(T)(src, count, dst);}

T[] repeat(T) (T[] src, uint count, T[] dst=null)
{
        uint len = src.length * count;
        if (len is 0)
            return null;

        if (dst.length < len)
            dst.length = len;
            
        for (auto p = dst.ptr; count--; p += src.length)
             p[0 .. src.length] = src;

        return dst [0 .. len];
}

/******************************************************************************

        Is the argument a whitespace character?

******************************************************************************/