pystring.cpp

///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2008-2010, Sony Pictures Imageworks Inc
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
// Neither the name of the organization Sony Pictures Imageworks nor the
// names of its contributors
// may be used to endorse or promote products derived from this software
// without specific prior written permission.
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS
// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
// TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
// PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER
// OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
///////////////////////////////////////////////////////////////////////////////

#include "pystring.h"

#include <algorithm>
#include <cctype>
#include <cstring>
#include <iostream>
#include <sstream>

namespace pystring
{

#if defined(_WIN32) || defined(_WIN64) || defined(_WINDOWS) || defined(_MSC_VER)
#ifndef WINDOWS
#define WINDOWS
#endif
#endif

// This definition codes from configure.in in the python src.
// Strictly speaking this limits us to str sizes of 2**31.
// Should we wish to handle this limit, we could use an architecture
// specific #defines and read from ssize_t (unistd.h) if the header exists.
// But in the meantime, the use of int assures maximum arch compatibility.
// This must also equal the size used in the end = MAX_32BIT_INT default arg.

typedef int Py_ssize_t;

/* helper macro to fixup start/end slice values */
#define ADJUST_INDICES(start, end, len)         \
    if (end > len)                          \
        end = len;                          \
    else if (end < 0) {                     \
        end += len;                         \
        if (end < 0)                        \
        end = 0;                        \
    }                                       \
    if (start < 0) {                        \
        start += len;                       \
        if (start < 0)                      \
        start = 0;                      \
    }


	namespace {

		//////////////////////////////////////////////////////////////////////////////////////////////
		/// why doesn't the std::reverse work?
		///
		void reverse_strings( std::vector< std::string > & result)
		{
			for (std::vector< std::string >::size_type i = 0; i < result.size() / 2; i++ )
			{
				std::swap(result[i], result[result.size() - 1 - i]);
			}
		}

		//////////////////////////////////////////////////////////////////////////////////////////////
		///
		///
		void split_whitespace( const std::string & str, std::vector< std::string > & result, int maxsplit )
		{
			std::string::size_type i, j, len = str.size();
			for (i = j = 0; i < len; )
			{

				while ( i < len && ::isspace( str[i] ) ) i++;
				j = i;

				while ( i < len && ! ::isspace( str[i]) ) i++;



				if (j < i)
				{
					if ( maxsplit-- <= 0 ) break;

					result.push_back( str.substr( j, i - j ));

					while ( i < len && ::isspace( str[i])) i++;
					j = i;
				}
			}
			if (j < len)
			{
				result.push_back( str.substr( j, len - j ));
			}
		}


		//////////////////////////////////////////////////////////////////////////////////////////////
		///
		///
		void rsplit_whitespace( const std::string & str, std::vector< std::string > & result, int maxsplit )
		{
			std::string::size_type len = str.size();
			std::string::size_type i, j;
			for (i = j = len; i > 0; )
			{

				while ( i > 0 && ::isspace( str[i - 1] ) ) i--;
				j = i;

				while ( i > 0 && ! ::isspace( str[i - 1]) ) i--;



				if (j > i)
				{
					if ( maxsplit-- <= 0 ) break;

					result.push_back( str.substr( i, j - i ));

					while ( i > 0 && ::isspace( str[i - 1])) i--;
					j = i;
				}
			}
			if (j > 0)
			{
				result.push_back( str.substr( 0, j ));
			}
			//std::reverse( result, result.begin(), result.end() );
			reverse_strings( result );
		}

	} //anonymous namespace


    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    void split( const std::string & str, std::vector< std::string > & result, const std::string & sep, int maxsplit )
    {
        result.clear();

        if ( maxsplit < 0 ) maxsplit = MAX_32BIT_INT;//result.max_size();


        if ( sep.size() == 0 )
        {
            split_whitespace( str, result, maxsplit );
            return;
        }

        std::string::size_type i,j, len = str.size(), n = sep.size();

        i = j = 0;

        while ( i+n <= len )
        {
            if ( str[i] == sep[0] && str.substr( i, n ) == sep )
            {
                if ( maxsplit-- <= 0 ) break;

                result.push_back( str.substr( j, i - j ) );
                i = j = i + n;
            }
            else
            {
                i++;
            }
        }

        result.push_back( str.substr( j, len-j ) );
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    void rsplit( const std::string & str, std::vector< std::string > & result, const std::string & sep, int maxsplit )
    {
        if ( maxsplit < 0 )
        {
            split( str, result, sep, maxsplit );
            return;
        }

        result.clear();

        if ( sep.size() == 0 )
        {
            rsplit_whitespace( str, result, maxsplit );
            return;
        }

        Py_ssize_t i,j, len = (Py_ssize_t) str.size(), n = (Py_ssize_t) sep.size();

        i = j = len;

        while ( i >= n )
        {
            if ( str[i - 1] == sep[n - 1] && str.substr( i - n, n ) == sep )
            {
                if ( maxsplit-- <= 0 ) break;

                result.push_back( str.substr( i, j - i ) );
                i = j = i - n;
            }
            else
            {
                i--;
            }
        }

        result.push_back( str.substr( 0, j ) );
        reverse_strings( result );
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    #define LEFTSTRIP 0
    #define RIGHTSTRIP 1
    #define BOTHSTRIP 2

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string do_strip( const std::string & str, int striptype, const std::string & chars  )
    {
        Py_ssize_t len = (Py_ssize_t) str.size(), i, j, charslen = (Py_ssize_t) chars.size();

        if ( charslen == 0 )
        {
            i = 0;
            if ( striptype != RIGHTSTRIP )
            {
                while ( i < len && ::isspace( str[i] ) )
                {
                    i++;
                }
            }

            j = len;
            if ( striptype != LEFTSTRIP )
            {
                do
                {
                    j--;
                }
                while (j >= i && ::isspace(str[j]));

                j++;
            }


        }
        else
        {
            const char * sep = chars.c_str();

            i = 0;
            if ( striptype != RIGHTSTRIP )
            {
                while ( i < len && memchr(sep, str[i], charslen) )
                {
                    i++;
                }
            }

            j = len;
            if (striptype != LEFTSTRIP)
            {
                do
                {
                    j--;
                }
                while (j >= i &&  memchr(sep, str[j], charslen)  );
                j++;
            }


        }

        if ( i == 0 && j == len )
        {
            return str;
        }
        else
        {
            return str.substr( i, j - i );
        }

    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    void partition( const std::string & str, const std::string & sep, std::vector< std::string > & result )
    {
        result.resize(3);
        int index = find( str, sep );
        if ( index < 0 )
        {
            result[0] = str;
            result[1] = "";
            result[2] = "";
        }
        else
        {
            result[0] = str.substr( 0, index );
            result[1] = sep;
            result[2] = str.substr( index + sep.size(), str.size() );
        }
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    void rpartition( const std::string & str, const std::string & sep, std::vector< std::string > & result )
    {
        result.resize(3);
        int index = rfind( str, sep );
        if ( index < 0 )
        {
            result[0] = "";
            result[1] = "";
            result[2] = str;
        }
        else
        {
            result[0] = str.substr( 0, index );
            result[1] = sep;
            result[2] = str.substr( index + sep.size(), str.size() );
        }
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string strip( const std::string & str, const std::string & chars )
    {
        return do_strip( str, BOTHSTRIP, chars );
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string lstrip( const std::string & str, const std::string & chars )
    {
        return do_strip( str, LEFTSTRIP, chars );
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string rstrip( const std::string & str, const std::string & chars )
    {
        return do_strip( str, RIGHTSTRIP, chars );
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string join( const std::string & str, const std::vector< std::string > & seq )
    {
        std::vector< std::string >::size_type seqlen = seq.size(), i;

        if ( seqlen == 0 ) return "";
        if ( seqlen == 1 ) return seq[0];

        std::string result( seq[0] );

        for ( i = 1; i < seqlen; ++i )
        {
            result += str + seq[i];

        }


        return result;
    }


    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    
    namespace
    {
        /* Matches the end (direction >= 0) or start (direction < 0) of self
         * against substr, using the start and end arguments. Returns
         * -1 on error, 0 if not found and 1 if found.
         */
        
        int _string_tailmatch(const std::string & self, const std::string & substr,
                              Py_ssize_t start, Py_ssize_t end,
                              int direction)
        {
            Py_ssize_t len = (Py_ssize_t) self.size();
            Py_ssize_t slen = (Py_ssize_t) substr.size();
            
            const char* sub = substr.c_str();
            const char* str = self.c_str();
            
            ADJUST_INDICES(start, end, len);
            
            if (direction < 0) {
                // startswith
                if (start+slen > len)
                    return 0;
            } else {
                // endswith
                if (end-start < slen || start > len)
                    return 0;
                if (end-slen > start)
                    start = end - slen;
            }
            if (end-start >= slen)
                return (!std::memcmp(str+start, sub, slen));
            
            return 0;
        }
    }
    
    bool endswith( const std::string & str, const std::string & suffix, int start, int end )
    {
        int result = _string_tailmatch(str, suffix,
                                       (Py_ssize_t) start, (Py_ssize_t) end, +1);
        //if (result == -1) // TODO: Error condition
        
        return static_cast<bool>(result);
    }
    
    
    bool startswith( const std::string & str, const std::string & prefix, int start, int end )
    {
        int result = _string_tailmatch(str, prefix,
                                       (Py_ssize_t) start, (Py_ssize_t) end, -1);
        //if (result == -1) // TODO: Error condition
        
        return static_cast<bool>(result);
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///

    bool isalnum( const std::string & str )
    {
        std::string::size_type len = str.size(), i;
        if ( len == 0 ) return false;


        if( len == 1 )
        {
            return ::isalnum( str[0] );
        }

        for ( i = 0; i < len; ++i )
        {
            if ( !::isalnum( str[i] ) ) return false;
        }
        return true;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    bool isalpha( const std::string & str )
    {
        std::string::size_type len = str.size(), i;
        if ( len == 0 ) return false;
        if( len == 1 ) return ::isalpha( (int) str[0] );

        for ( i = 0; i < len; ++i )
        {
           if ( !::isalpha( (int) str[i] ) ) return false;
        }
        return true;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    bool isdigit( const std::string & str )
    {
        std::string::size_type len = str.size(), i;
        if ( len == 0 ) return false;
        if( len == 1 ) return ::isdigit( str[0] );

        for ( i = 0; i < len; ++i )
        {
           if ( ! ::isdigit( str[i] ) ) return false;
        }
        return true;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    bool islower( const std::string & str )
    {
        std::string::size_type len = str.size(), i;
        if ( len == 0 ) return false;
        if( len == 1 ) return ::islower( str[0] );

        for ( i = 0; i < len; ++i )
        {
           if ( !::islower( str[i] ) ) return false;
        }
        return true;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    bool isspace( const std::string & str )
    {
        std::string::size_type len = str.size(), i;
        if ( len == 0 ) return false;
        if( len == 1 ) return ::isspace( str[0] );

        for ( i = 0; i < len; ++i )
        {
           if ( !::isspace( str[i] ) ) return false;
        }
        return true;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    bool istitle( const std::string & str )
    {
        std::string::size_type len = str.size(), i;

        if ( len == 0 ) return false;
        if ( len == 1 ) return ::isupper( str[0] );

        bool cased = false, previous_is_cased = false;

        for ( i = 0; i < len; ++i )
        {
            if ( ::isupper( str[i] ) )
            {
                if ( previous_is_cased )
                {
                    return false;
                }

                previous_is_cased = true;
                cased = true;
            }
            else if ( ::islower( str[i] ) )
            {
                if (!previous_is_cased)
                {
                    return false;
                }

                previous_is_cased = true;
                cased = true;

            }
            else
            {
                previous_is_cased = false;
            }
        }

        return cased;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    bool isupper( const std::string & str )
    {
        std::string::size_type len = str.size(), i;
        if ( len == 0 ) return false;
        if( len == 1 ) return ::isupper( str[0] );

        for ( i = 0; i < len; ++i )
        {
           if ( !::isupper( str[i] ) ) return false;
        }
        return true;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string capitalize( const std::string & str )
    {
        std::string s( str );
        std::string::size_type len = s.size(), i;

        if ( len > 0)
        {
            if (::islower(s[0])) s[0] = (char) ::toupper( s[0] );
        }

        for ( i = 1; i < len; ++i )
        {
            if (::isupper(s[i])) s[i] = (char) ::tolower( s[i] );
        }

        return s;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string lower( const std::string & str )
    {
        std::string s( str );
        std::string::size_type len = s.size(), i;

        for ( i = 0; i < len; ++i )
        {
            if ( ::isupper( s[i] ) ) s[i] = (char) ::tolower( s[i] );
        }

        return s;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string upper( const std::string & str )
    {
        std::string s( str ) ;
        std::string::size_type len = s.size(), i;

        for ( i = 0; i < len; ++i )
        {
            if ( ::islower( s[i] ) ) s[i] = (char) ::toupper( s[i] );
        }

        return s;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string swapcase( const std::string & str )
    {
        std::string s( str );
        std::string::size_type len = s.size(), i;

        for ( i = 0; i < len; ++i )
        {
            if ( ::islower( s[i] ) ) s[i] = (char) ::toupper( s[i] );
            else if (::isupper( s[i] ) ) s[i] = (char) ::tolower( s[i] );
        }

        return s;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string title( const std::string & str )
    {
        std::string s( str );
        std::string::size_type len = s.size(), i;
        bool previous_is_cased = false;

        for ( i = 0; i < len; ++i )
        {
            int c = s[i];
            if ( ::islower(c) )
            {
                if ( !previous_is_cased )
                {
                    s[i] = (char) ::toupper(c);
                }
                previous_is_cased = true;
            }
            else if ( ::isupper(c) )
            {
                if ( previous_is_cased )
                {
                    s[i] = (char) ::tolower(c);
                }
                previous_is_cased = true;
            }
            else
            {
                previous_is_cased = false;
            }
        }

        return s;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string translate( const std::string & str, const std::string & table, const std::string & deletechars )
    {
        std::string s;
        std::string::size_type len = str.size(), dellen = deletechars.size();

        if ( table.size() != 256 )
        {
            // TODO : raise exception instead
            return str;
        }

        //if nothing is deleted, use faster code
        if ( dellen == 0 )
        {
            s = str;
            for ( std::string::size_type i = 0; i < len; ++i )
            {
                s[i] = table[ s[i] ];
            }
            return s;
        }


        int trans_table[256];
        for ( int i = 0; i < 256; i++)
        {
            trans_table[i] = table[i];
        }

        for ( std::string::size_type i = 0; i < dellen; i++)
        {
            trans_table[(int) deletechars[i] ] = -1;
        }

        for ( std::string::size_type i = 0; i < len; ++i )
        {
            if ( trans_table[ (int) str[i] ] != -1 )
            {
                s += table[ str[i] ];
            }
        }

        return s;

    }


    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string zfill( const std::string & str, int width )
    {
        int len = (int)str.size();

        if ( len >= width )
        {
            return str;
        }

        std::string s( str );

        int fill = width - len;

        s = std::string( fill, '0' ) + s;


        if ( s[fill] == '+' || s[fill] == '-' )
        {
            s[0] = s[fill];
            s[fill] = '0';
        }

        return s;

    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string ljust( const std::string & str, int width )
    {
        std::string::size_type len = str.size();
        if ( (( int ) len ) >= width ) return str;
        return str + std::string( width - len, ' ' );
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string rjust( const std::string & str, int width )
    {
        std::string::size_type len = str.size();
        if ( (( int ) len ) >= width ) return str;
        return std::string( width - len, ' ' ) + str;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string center( const std::string & str, int width )
    {
        int len = (int) str.size();
        int marg, left;

        if ( len >= width ) return str;

        marg = width - len;
        left = marg / 2 + (marg & width & 1);

        return std::string( left, ' ' ) + str + std::string( marg - left, ' ' );

    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string slice( const std::string & str, int start, int end )
    {
        ADJUST_INDICES(start, end, (int) str.size());
        if ( start >= end ) return "";
        return str.substr( start, end - start );
    }
    
    
    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    int find( const std::string & str, const std::string & sub, int start, int end  )
    {
        ADJUST_INDICES(start, end, (int) str.size());
        
        std::string::size_type result = str.find( sub, start );
        
        // If we cannot find the string, or if the end-point of our found substring is past
        // the allowed end limit, return that it can't be found.
        if( result == std::string::npos || 
           (result + sub.size() > (std::string::size_type)end) )
        {
            return -1;
        }
        
        return (int) result;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    int index( const std::string & str, const std::string & sub, int start, int end  )
    {
        return find( str, sub, start, end );
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    int rfind( const std::string & str, const std::string & sub, int start, int end )
    {
        ADJUST_INDICES(start, end, (int) str.size());
        
        std::string::size_type result = str.rfind( sub, end );
        
        if( result == std::string::npos || 
            result < (std::string::size_type)start  || 
           (result + sub.size() > (std::string::size_type)end))
            return -1;
        
        return (int)result;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    int rindex( const std::string & str, const std::string & sub, int start, int end )
    {
        return rfind( str, sub, start, end );
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string expandtabs( const std::string & str, int tabsize )
    {
        std::string s( str );

        std::string::size_type len = str.size(), i = 0;
        int offset = 0;

        int j = 0;

        for ( i = 0; i < len; ++i )
        {
            if ( str[i] == '\t' )
            {

                if ( tabsize > 0 )
                {
                    int fillsize = tabsize - (j % tabsize);
                    j += fillsize;
                    s.replace( i + offset, 1, std::string( fillsize, ' ' ));
                    offset += fillsize - 1;
                }
                else
                {
                    s.replace( i + offset, 1, "" );
                    offset -= 1;
                }

            }
            else
            {
                j++;

                if (str[i] == '\n' || str[i] == '\r')
                {
                    j = 0;
                }
            }
        }

        return s;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    int count( const std::string & str, const std::string & substr, int start, int end )
    {
        int nummatches = 0;
        int cursor = start;

        while ( 1 )
        {
            cursor = find( str, substr, cursor, end );

            if ( cursor < 0 ) break;

            cursor += (int) substr.size();
            nummatches += 1;
        }

        return nummatches;


    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    
    std::string replace( const std::string & str, const std::string & oldstr, const std::string & newstr, int count )
    {
        int sofar = 0;
        int cursor = 0;
        std::string s( str );

        std::string::size_type oldlen = oldstr.size(), newlen = newstr.size();
        
        cursor = find( s, oldstr, cursor );

        while ( cursor != -1 && cursor <= (int)s.size() )
        {
            if ( count > -1 && sofar >= count )
            {
                break;
            }

            s.replace( cursor, oldlen, newstr );
            cursor += (int) newlen;

            if ( oldlen != 0)
            {
                cursor = find( s, oldstr, cursor );
            }
            else
            {
                ++cursor;
            }

            ++sofar;
        }

        return s;

    }
    
    
    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    void splitlines(  const std::string & str, std::vector< std::string > & result, bool keepends )
    {
        result.clear();
        std::string::size_type len = str.size(), i, j, eol;

         for (i = j = 0; i < len; )
         {
            while (i < len && str[i] != '\n' && str[i] != '\r') i++;

            eol = i;
            if (i < len)
            {
                if (str[i] == '\r' && i + 1 < len && str[i+1] == '\n')
                {
                    i += 2;
                }
                else
                {
                    i++;
                }
                if (keepends)
                eol = i;

            }

            result.push_back( str.substr( j, eol - j ) );
            j = i;

        }

        if (j < len)
        {
            result.push_back( str.substr( j, len - j ) );
        }

    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    std::string mul( const std::string & str, int n )
    {
        // Early exits
        if (n <= 0) return "";
        if (n == 1) return str;
        
        std::ostringstream os;
        for(int i=0; i<n; ++i)
        {
            os << str;
        }
        return os.str();
    }



namespace os
{
namespace path
{
    
    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    /// These functions are C++ ports of the python2.6 versions of os.path,
    /// and come from genericpath.py, ntpath.py, posixpath.py

    /// Split a pathname into drive and path specifiers.
    /// Returns drivespec, pathspec. Either part may be empty.
    void splitdrive_nt(std::string & drivespec, std::string & pathspec,
                       const std::string & p)
    {
        if(pystring::slice(p, 1, 2) == ":")
        {
            std::string path = p; // In case drivespec == p
            drivespec = pystring::slice(path, 0, 2);
            pathspec = pystring::slice(path, 2);
        }
        else
        {
            drivespec = "";
            pathspec = p;
        }
    }

    // On Posix, drive is always empty
    void splitdrive_posix(std::string & drivespec, std::string & pathspec,
                          const std::string & path)
    {
        drivespec = "";
        pathspec = path;
    }

    void splitdrive(std::string & drivespec, std::string & pathspec,
                    const std::string & path)
    {
#ifdef WINDOWS
        return splitdrive_nt(drivespec, pathspec, path);
#else
        return splitdrive_posix(drivespec, pathspec, path);
#endif
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///

    // Test whether a path is absolute
    // In windows, if the character to the right of the colon
    // is a forward or backslash it's absolute.
    bool isabs_nt(const std::string & path)
    {
        std::string drivespec, pathspec;
        splitdrive_nt(drivespec, pathspec, path);
        if(pathspec.empty()) return false;
        return ((pathspec[0] == '/') || (pathspec[0] == '\\'));
    }

    bool isabs_posix(const std::string & s)
    {
        return pystring::startswith(s, "/");
    }

    bool isabs(const std::string & path)
    {
#ifdef WINDOWS
        return isabs_nt(path);
#else
        return isabs_posix(path);
#endif
    }


    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///
    
    std::string abspath_nt(const std::string & path, const std::string & cwd)
    {
        std::string p = path;
        if(!isabs_nt(p)) p = join_nt(cwd, p);
        return normpath_nt(p);
    }
    
    std::string abspath_posix(const std::string & path, const std::string & cwd)
    {
        std::string p = path;
        if(!isabs_posix(p)) p = join_posix(cwd, p);
        return normpath_posix(p);
    }
    
    std::string abspath(const std::string & path, const std::string & cwd)
    {
#ifdef WINDOWS
        return abspath_nt(path, cwd);
#else
        return abspath_posix(path, cwd);
#endif
    }
    

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///

    std::string join_nt(const std::vector< std::string > & paths)
    {
        if(paths.empty()) return "";
        if(paths.size() == 1) return paths[0];
        
        std::string path = paths[0];
        
        for(unsigned int i=1; i<paths.size(); ++i)
        {
            std::string b = paths[i];
            
            bool b_nts = false;
            if(path.empty())
            {
                b_nts = true;
            }
            else if(isabs_nt(b))
            {
                // This probably wipes out path so far.  However, it's more
                // complicated if path begins with a drive letter:
                //     1. join('c:', '/a') == 'c:/a'
                //     2. join('c:/', '/a') == 'c:/a'
                // But
                //     3. join('c:/a', '/b') == '/b'
                //     4. join('c:', 'd:/') = 'd:/'
                //     5. join('c:/', 'd:/') = 'd:/'
                
                if( (pystring::slice(path, 1, 2) != ":") ||
                    (pystring::slice(b, 1, 2) == ":") )
                {
                    // Path doesnt start with a drive letter
                    b_nts = true;
                }
                // Else path has a drive letter, and b doesn't but is absolute.
                else if((path.size()>3) || 
                        ((path.size()==3) && !pystring::endswith(path, "/") && !pystring::endswith(path, "\\")))
                {
                    b_nts = true;
                }
            }
            
            if(b_nts)
            {
                path = b;
            }
            else
            {
                // Join, and ensure there's a separator.
                // assert len(path) > 0
                if( pystring::endswith(path, "/") || pystring::endswith(path, "\\"))
                {
                    if(pystring::startswith(b,"/") || pystring::startswith(b,"\\"))
                    {
                        path += pystring::slice(b, 1);
                    }
                    else
                    {
                        path += b;
                    }
                }
                else if(pystring::endswith(path, ":"))
                {
                    path += b;
                }
                else if(!b.empty())
                {
                    if(pystring::startswith(b,"/") || pystring::startswith(b,"\\"))
                    {
                        path += b;
                    }
                    else
                    {
                        path += "\\" + b;
                    }
                }
                else
                {
                    // path is not empty and does not end with a backslash,
                    // but b is empty; since, e.g., split('a/') produces
                    // ('a', ''), it's best if join() adds a backslash in
                    // this case.
                    path += "\\";
                }
            }
        }
        
        return path;
    }
    
    // Join two or more pathname components, inserting "\\" as needed.
    std::string join_nt(const std::string & a, const std::string & b)
    {
        std::vector< std::string > paths(2);
        paths[0] = a;
        paths[1] = b;
        return join_nt(paths);
    }

    // Join pathnames.
    // If any component is an absolute path, all previous path components
    // will be discarded.
    // Ignore the previous parts if a part is absolute.
    // Insert a '/' unless the first part is empty or already ends in '/'.

    std::string join_posix(const std::vector< std::string > & paths)
    {
        if(paths.empty()) return "";
        if(paths.size() == 1) return paths[0];
        
        std::string path = paths[0];
        
        for(unsigned int i=1; i<paths.size(); ++i)
        {
            std::string b = paths[i];
            if(pystring::startswith(b, "/"))
            {
                path = b;
            }
            else if(path.empty() || pystring::endswith(path, "/"))
            {
                path += b;
            }
            else
            {
                path += "/" + b;
            }
        }
        
        return path;
    }

    std::string join_posix(const std::string & a, const std::string & b)
    {
        std::vector< std::string > paths(2);
        paths[0] = a;
        paths[1] = b;
        return join_posix(paths);
    }
    
    std::string join(const std::string & path1, const std::string & path2)
    {
#ifdef WINDOWS
        return join_nt(path1, path2);
#else
        return join_posix(path1, path2);
#endif
    }


    std::string join(const std::vector< std::string > & paths)
    {
#ifdef WINDOWS
        return join_nt(paths);
#else
        return join_posix(paths);
#endif
    }
    
    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///

        
    // Split a pathname.
    // Return (head, tail) where tail is everything after the final slash.
    // Either part may be empty

    void split_nt(std::string & head, std::string & tail, const std::string & path)
    {
        std::string d, p;
        splitdrive_nt(d, p, path);
        
        // set i to index beyond p's last slash
        int i = (int)p.size();

        // walk back to find the index of the first slash from the end       
        while(i>0 && (p[i-1] != '\\') && (p[i-1] != '/'))
        {
            i = i - 1;
        }

        head = pystring::slice(p,0,i);
        tail = pystring::slice(p,i); // now tail has no slashes
        
        // remove trailing slashes from head, unless it's all slashes
        std::string head2 = head;
        while(!head2.empty() && ((pystring::slice(head2,-1) == "/") ||
                                 (pystring::slice(head2,-1) == "\\")))
        {
            head2 = pystring::slice(head2,0,-1);
        }
        
        if(!head2.empty()) head = head2;
        head = d + head;
    }


    // Split a path in head (everything up to the last '/') and tail (the
    // rest).  If the path ends in '/', tail will be empty.  If there is no
    // '/' in the path, head  will be empty.
    // Trailing '/'es are stripped from head unless it is the root.

    void split_posix(std::string & head, std::string & tail, const std::string & p)
    {
        int i = pystring::rfind(p, "/") + 1;
        
        head = pystring::slice(p,0,i);
        tail = pystring::slice(p,i);
        
        if(!head.empty() && (head != pystring::mul("/", (int) head.size())))
        {
            head = pystring::rstrip(head, "/");
        }
    }

    void split(std::string & head, std::string & tail, const std::string & path)
    {
#ifdef WINDOWS
        return split_nt(head, tail, path);
#else
        return split_posix(head, tail, path);
#endif
    }


    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///

    std::string basename_nt(const std::string & path)
    {
        std::string head, tail;
        split_nt(head, tail, path);
        return tail;
    }

    std::string basename_posix(const std::string & path)
    {
        std::string head, tail;
        split_posix(head, tail, path);
        return tail;
    }

    std::string basename(const std::string & path)
    {
#ifdef WINDOWS
        return basename_nt(path);
#else
        return basename_posix(path);
#endif
    }

    std::string dirname_nt(const std::string & path)
    {
        std::string head, tail;
        split_nt(head, tail, path);
        return head;
    }
    
    std::string dirname_posix(const std::string & path)
    {
        std::string head, tail;
        split_posix(head, tail, path);
        return head;
    }
    
    std::string dirname(const std::string & path)
    {
#ifdef WINDOWS
        return dirname_nt(path);
#else
        return dirname_posix(path);
#endif
    }


    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///

    // Normalize a path, e.g. A//B, A/./B and A/foo/../B all become A\B.
    std::string normpath_nt(const std::string & p)
    {
        std::string path = p;
        path = pystring::replace(path, "/","\\");
        
        std::string prefix;
        splitdrive_nt(prefix, path, path);
        
        // We need to be careful here. If the prefix is empty, and the path starts
        // with a backslash, it could either be an absolute path on the current
        // drive (\dir1\dir2\file) or a UNC filename (\\server\mount\dir1\file). It
        // is therefore imperative NOT to collapse multiple backslashes blindly in
        // that case.
        // The code below preserves multiple backslashes when there is no drive
        // letter. This means that the invalid filename \\\a\b is preserved
        // unchanged, where a\\\b is normalised to a\b. It's not clear that there
        // is any better behaviour for such edge cases.
        
        if(prefix.empty())
        {
            // No drive letter - preserve initial backslashes
            while(pystring::slice(path,0,1) == "\\")
            {
                prefix = prefix + "\\";
                path = pystring::slice(path,1);
            }
        }
        else
        {
            // We have a drive letter - collapse initial backslashes
            if(pystring::startswith(path, "\\"))
            {
                prefix = prefix + "\\";
                path = pystring::lstrip(path, "\\");
            }
        }
        
        std::vector<std::string> comps;
        pystring::split(path, comps, "\\");
        
        int i = 0;
        
        while(i<(int)comps.size())
        {
            if(comps[i].empty() || comps[i] == ".")
            {
                comps.erase(comps.begin()+i);
            }
            else if(comps[i] == "..")
            {
                if(i>0 && comps[i-1] != "..")
                {
                    comps.erase(comps.begin()+i-1, comps.begin()+i+1);
                    i -= 1;
                }
                else if(i == 0 && pystring::endswith(prefix, "\\"))
                {
                    comps.erase(comps.begin()+i);
                }
                else
                {
                    i += 1;
                }
            }
            else
            {
                i += 1;
            }
        }
        
        // If the path is now empty, substitute '.'
        if(prefix.empty() && comps.empty())
        {
            comps.push_back(".");
        }
        
        return prefix + pystring::join("\\", comps);
    }

    // Normalize a path, e.g. A//B, A/./B and A/foo/../B all become A/B.
    // It should be understood that this may change the meaning of the path
    // if it contains symbolic links!
    // Normalize path, eliminating double slashes, etc.

    std::string normpath_posix(const std::string & p)
    {
        if(p.empty()) return ".";
        
        std::string path = p;
        
        int initial_slashes = pystring::startswith(path,"/") ? 1 : 0;
        
        // POSIX allows one or two initial slashes, but treats three or more
        // as single slash.
        
        if (initial_slashes && pystring::startswith(path,"//")
            && !pystring::startswith(path,"///"))
            initial_slashes = 2;
        
        std::vector<std::string> comps, new_comps;
        pystring::split(path, comps, "/");
        
        for(unsigned int i=0; i<comps.size(); ++i)
        {
            std::string comp = comps[i];
            if(comp.empty() || comp == ".")
                continue;
            
            if( (comp != "..") || ((initial_slashes == 0) && new_comps.empty()) ||
                (!new_comps.empty() && new_comps[new_comps.size()-1] == ".."))
            {
                new_comps.push_back(comp);
            }
            else if (!new_comps.empty())
            {
                new_comps.pop_back();
            }
        }
        
        path = pystring::join("/", new_comps);
        
        if (initial_slashes > 0)
            path = pystring::mul("/",initial_slashes) + path;
        
        if(path.empty()) return ".";
        return path;
    }
    
    std::string normpath(const std::string & path)
    {
#ifdef WINDOWS
        return normpath_nt(path);
#else
        return normpath_posix(path);
#endif
    }

    //////////////////////////////////////////////////////////////////////////////////////////////
    ///
    ///

    // Split the extension from a pathname.
    // Extension is everything from the last dot to the end, ignoring
    // leading dots.  Returns "(root, ext)"; ext may be empty.
    // It is always true that root + ext == p

    void splitext_generic(std::string & root, std::string & ext,
                          const std::string & p,
                          const std::string & sep,
                          const std::string & altsep,
                          const std::string & extsep)
    {
        int sepIndex = pystring::rfind(p, sep);
        if(!altsep.empty())
        {
            int altsepIndex = pystring::rfind(p, altsep);
            sepIndex = std::max(sepIndex, altsepIndex);
        }

        int dotIndex = pystring::rfind(p, extsep);
        if(dotIndex > sepIndex)
        {
            // Skip all leading dots
            int filenameIndex = sepIndex + 1;

            while(filenameIndex < dotIndex)
            {
                if(pystring::slice(p,filenameIndex) != extsep)
                {
                    root = pystring::slice(p, 0, dotIndex);
                    ext = pystring::slice(p, dotIndex);
                    return;
                }

                filenameIndex += 1;
            }
        }

        root = p;
        ext = "";
    }

    void splitext_nt(std::string & root, std::string & ext, const std::string & path)
    {
        return splitext_generic(root, ext, path,
                                "\\", "/", ".");
    }

    void splitext_posix(std::string & root, std::string & ext, const std::string & path)
    {
        return splitext_generic(root, ext, path,
                                "/", "", ".");
    }

    void splitext(std::string & root, std::string & ext, const std::string & path)
    {
#ifdef WINDOWS
        return splitext_nt(root, ext, path);
#else
        return splitext_posix(root, ext, path);
#endif
    }

} // namespace path
} // namespace os


}//namespace pystring