/*
 * Copyright (C) 2009 The Android Open Source Project
 * 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.
 *
 * 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 <string>
#include <algorithm>
#include <climits>
#include <cstddef>
#include <cstring>
#include <malloc.h>
#include <ostream>

#ifndef MAX_SIZE_T
#define MAX_SIZE_T           (~(size_t)0)
#endif

namespace {
char kEmptyString[1] = { '\0' };
// Dummy char used in the 'at' accessor when the index is out of
// range.
char sDummy;
}

namespace std {
// Implementation of the std::string class.
//
// mData points either to a heap allocated array of bytes or the constant
// kEmptyString when empty and reserve has not been called.
//
// The size of the buffer pointed by mData is mCapacity + 1.
// The extra byte is need to store the '\0'.
//
// mCapacity is either mLength or the number of bytes reserved using
// reserve(int)).
//
// mLength is the number of char in the string, excluding the terminating '\0'.
//
// TODO: replace the overflow checks with some better named macros.
//
// Allocate n + 1 number of bytes for the string. Update mCapacity.
// Ensure that mCapacity + 1 and mLength + 1 is accessible.
// In case of error the original state of the string is restored.
// @param n Number of bytes requested. String allocate n + 1 to hold
//            the terminating '\0'.
// @return true if the buffer could be allocated, false otherwise.
bool string::SafeMalloc(size_type n)
{
    // Not empty and no overflow
    if (n > 0 && n + 1 > n)
    {
        value_type *oldData = mData;

        mData = static_cast<value_type *>(::malloc(n + 1));
        if (NULL != mData)
        {
            mCapacity = n;
            return true;
        }
        mData = oldData;  // roll back
    }
    return false;
}

// Resize the buffer pointed by mData if n >= mLength.
// mData points to an allocated buffer or the empty string.
// @param n The number of bytes for the internal buffer.
//            Must be > mLength and > 0.
void string::SafeRealloc(size_type n)
{
    // truncation or nothing to do or n too big (overflow)
    if (n < mLength || n == mCapacity || n + 1 < n) {
        return;
    }

    if (kEmptyString == mData)
    {
        if (SafeMalloc(n)) {
            *mData = '\0';
        }
        return;
    }

    value_type *oldData = mData;

    mData = static_cast<char*>(::realloc(mData, n + 1));
    if (NULL == mData) // reallocate failed.
    {
        mData = oldData;
    }
    else
    {
        mCapacity = n;
    }
}

void string::SafeFree(value_type *buffer)
{
    if (buffer != kEmptyString)
    {
        ::free(buffer);
    }
}

// If the memory is on the heap, release it. Do nothing we we point at the empty
// string. On return mData points to str.
void string::ResetTo(value_type *str)
{
    SafeFree(mData);
    mData = str;
}

void string::ConstructEmptyString()
{
    mData = kEmptyString;
    mLength = 0;
    mCapacity = 0;
}

void string::Constructor(const value_type *str, size_type n)
{
    Constructor(str, 0, n);
}


void string::Constructor(const value_type *str, size_type pos, size_type n)
{
    // Enough data and no overflow
    if (SafeMalloc(n))
    {
        memcpy(mData, str + pos, n);
        mLength = n;
        mData[mLength] = '\0';
        return;  // Success
    }
    ConstructEmptyString();
}

void string::Constructor(size_type n, char c)
{
    // Enough data and no overflow

    if (SafeMalloc(n))
    {
        memset(mData, c, n);
        mLength = n;
        mData[mLength] = '\0';
        return;  // Success
    }
    ConstructEmptyString();
}

string::string()
{
    ConstructEmptyString();
}

string::string(const string& str)
{
    Constructor(str.mData, str.mLength);
}

string::string(const string& str, size_type pos, size_type n)
{
    if (pos < str.mLength)
    {
        if (n > (str.mLength - pos)) {
            n = str.mLength - pos;
        }
        Constructor(str.mData + pos , n);
    }
    else
    {
        ConstructEmptyString();
    }
}

string::string(const string& str, size_type pos)
{
    if (pos < str.mLength)
    {
        Constructor(str.mData, pos, str.mLength - pos);
    }
    else
    {
        ConstructEmptyString();
    }
}

string::string(const value_type *str)
{
    if (NULL != str)
    {
        Constructor(str, traits_type::length(str));
    }
    else
    {
        ConstructEmptyString();
    }
}

string::string(const value_type *str, size_type n)
{
    Constructor(str, n);
}

// Char repeat constructor.
string::string(size_type n, char c)
{
    Constructor(n, c);
}

string::string(const value_type *begin, const value_type *end)
{
    if (begin < end)
    {
        Constructor(begin, end - begin);
    }
    else
    {
        ConstructEmptyString();
    }
}

string::~string()
{
    clear();  // non virtual, ok to call.
}

void string::clear()
{
    mCapacity = 0;
    mLength = 0;
    ResetTo(kEmptyString);
}

string& string::erase(size_type pos, size_type n)
{
    if (pos >= mLength || 0 == n)
    {
        return *this;
    }
    // start of the characters left which need to be moved down.
    const size_t remainder = pos + n;

    // Truncate, even if there is an overflow.
    if (remainder >= mLength || remainder < pos)
    {
        *(mData + pos) = '\0';
        mLength = pos;
        return *this;
    }
    // remainder < mLength and allocation guarantees to be at least
    // mLength + 1
    size_t left = mLength - remainder + 1;
    value_type *d = mData + pos;
    value_type *s = mData + remainder;
    memmove(d, s, left);
    mLength -= n;
    return *this;
}

void string::Append(const value_type *str, size_type n)
{
    const size_type total_len = mLength + n;

    // n > 0 and no overflow for the string length + terminating null.
    if (n > 0 && (total_len + 1) > mLength)
    {
        if (total_len > mCapacity)
        {
            reserve(total_len);
            if (total_len > mCapacity)
            {  // something went wrong in the reserve call.
                return;
            }
        }
        memcpy(mData + mLength, str, n);
        mLength = total_len;
        mData[mLength] = '\0';
    }
}

string& string::append(const value_type *str)
{
    if (NULL != str)
    {
        Append(str, traits_type::length(str));
    }
    return *this;
}

string& string::append(const value_type *str, size_type n)
{
    if (NULL != str)
    {
        Append(str, n);
    }
    return *this;
}

string& string::append(const value_type *str, size_type pos, size_type n)
{
    if (NULL != str)
    {
        Append(str + pos, n);
    }
    return *this;
}

string& string::append(const string& str)
{
    Append(str.mData, str.mLength);
    return *this;
}

// Specialization to append from other strings' iterators.
template<>
string& string::append<__wrapper_iterator<const char *,string> >(
    __wrapper_iterator<const char *,string> first,
    __wrapper_iterator<const char *,string> last) {
    Append(&*first, std::distance(first, last));
    return *this;
}
template<>
string& string::append<__wrapper_iterator<char *,string> >(
    __wrapper_iterator<char *,string> first,
    __wrapper_iterator<char *,string> last) {
    Append(&*first, std::distance(first, last));
    return *this;
}

void string::push_back(const char c)
{
    // Check we don't overflow.
    if (mLength + 2 > mLength)
    {
        const size_type total_len = mLength + 1;

        if (total_len > mCapacity)
        {
            reserve(total_len);
            if (total_len > mCapacity)
            {  // something went wrong in the reserve call.
                return;
            }
        }
        *(mData + mLength) = c;
        ++mLength;
        mData[mLength] = '\0';
    }
}


int string::compare(const string& other) const
{
    if (this == &other)
    {
        return 0;
    }
    else if (mLength == other.mLength)
    {
        return memcmp(mData, other.mData, mLength);
    }
    else
    {
        return mLength < other.mLength ? -1 : 1;
    }
}

int string::compare(const value_type *other) const
{
    if (NULL == other)
    {
        return 1;
    }
    return strcmp(mData, other);
}

bool operator==(const string& left, const string& right)
{
    if (&left == &right) {
        return true;
    }
    return (left.size() == right.size() &&
            !char_traits<char>::compare(left.mData, right.mData, left.size()));
}

bool operator==(const string& left, const string::value_type *right)
{
    if (NULL == right) {
        return false;
    }
    // We can use strcmp here because even when the string is build from an
    // array of char we insert the terminating '\0'.
    return std::strcmp(left.mData, right) == 0;
}

void string::reserve(size_type size)
{
    if (0 == size)
    {
        if (0 == mCapacity)
        {
            return;
        }
        else if (0 == mLength)
        {  // Shrink to fit an empty string.
            mCapacity = 0;
            ResetTo(kEmptyString);
        }
        else
        {  // Shrink to fit a non empty string
            SafeRealloc(mLength);
        }
    }
    else if (size > mLength)
    {
        SafeRealloc(size);
    }
}

void string::swap(string& other)
{
    if (this == &other) return;
    value_type *const tmp_mData = mData;
    const size_type tmp_mCapacity = mCapacity;
    const size_type tmp_mLength = mLength;

    mData = other.mData;
    mCapacity = other.mCapacity;
    mLength = other.mLength;

    other.mData = tmp_mData;
    other.mCapacity = tmp_mCapacity;
    other.mLength = tmp_mLength;
}

const char& string::operator[](const size_type pos) const
{
    return mData[pos];
}

char& string::operator[](const size_type pos)
{
    return mData[pos];
}

const char& string::at(const size_type pos) const
{
    if (pos < mLength) {
        return mData[pos];
    } else {
        sDummy = 'X';
        return sDummy;
    }
}

char& string::at(const size_type pos)
{
    if (pos < mLength) {
        return mData[pos];
    } else {
        sDummy = 'X';
        return sDummy;
    }
}

string& string::assign(const string& str)
{
    clear();
    Constructor(str.mData, str.mLength);
    return *this;
}

string& string::assign(const string& str, size_type pos, size_type n)
{
    if (pos >= str.mLength)
    {  // pos is out of bound
        return *this;
    }
    if (n <= str.mLength - pos)
    {
        clear();
        Constructor(str.mData, pos, n);
    }
    return *this;
}

string& string::assign(const value_type *str)
{
    if (NULL == str)
    {
        return *this;
    }
    clear();
    Constructor(str, traits_type::length(str));
    return *this;
}

string& string::assign(const value_type *array, size_type n)
{
    if (NULL == array || 0 == n)
    {
        return *this;
    }
    clear();
    Constructor(array, n);
    return *this;
}

string::iterator string::insert(iterator iter, char c) {
    const size_type new_len = mLength + 1;
    char *base = iter.base();

    if (base < mData || base > mData + mLength || new_len < mLength) {
        return iterator(&sDummy);  // out of bound || overflow
    }

    const size_type pos = base - mData;
    if (new_len > mCapacity) {
        reserve(new_len);
        if (new_len > mCapacity) {
            return iterator(&sDummy);  // not enough memory?
        }
    }
    // At this point 'iter' and 'base' are not valid anymore since
    // realloc could have taken place.
    base = mData + pos;
    std::memmove(base + 1, base, mLength - pos);
    *base = c;
    mLength = new_len;
    mData[mLength] = 0;
    return iterator(base);
}

string& string::operator=(char c)
{
    clear();
    Constructor(1, c);
    return *this;
}

string::size_type string::find(const value_type *str, size_type pos) const
{

    if (NULL == str)
    {
        return string::npos;
    }

    // Empty string is found everywhere except beyond the end. It is
    // possible to find the empty string right after the last char,
    // hence we used mLength and not mLength - 1 in the comparison.
    if (*str == '\0')
    {
        return pos > mLength ? string::npos : pos;
    }

    if (mLength == 0 || pos > mLength - 1)
    {
        return string::npos;
    }

    value_type *idx = std::strstr(mData + pos, str);

    if (NULL == idx)
    {
        return string::npos;
    }

    const std::ptrdiff_t delta = idx - mData;

    return static_cast<size_type>(delta);
}

string string::substr(size_type pos, size_type n) const {
    return string(*this, pos, n);
}

string::size_type string::find_first_of(value_type c, size_type pos) const {
    if (pos >= mLength) {
        return npos;
    }
    const char *res;
    // The last parameter represents a number of chars, not a index.
    res = static_cast<const char *>(std::memchr(mData + pos, c, mLength - pos));
    return res != NULL ? res - mData : npos;
}

string::size_type string::find_last_of(value_type c, size_type pos) const {
    if (mLength == 0) {
        return npos;
    } else if (pos >= mLength) {
        pos = mLength - 1;  // >= 0
    }

    const char *res;
    // Note:memrchr is not in the std namepace.
    // The last parameter represents a number of chars, not a index.
    res = static_cast<const char *>(memrchr(mData, c, pos + 1));
    return res != NULL ? res - mData : npos;
}

string::size_type string::find_first_not_of(value_type c, size_type pos) const {
    char *curr = mData + pos;
    for (size_type i = pos; i < mLength; ++i, ++curr) {
        if (c != *curr) {
            return i;
        }
    }
    return npos;
}

string::size_type string::find_last_not_of(value_type c, size_type pos) const {
    if (mLength == 0) {
        return npos;
    } else if (pos >= mLength) {
        pos = mLength - 1;  // >= 0
    }

    char *curr = mData + pos;
    size_type i = pos;

    for (;; --i, --curr) {
        if (c != *curr) {
            return i;
        } else if (i == 0) {
            return npos;
        }
    }
}

bool operator<(const string& lhs, const string& rhs) {
    return lhs.compare(rhs) < 0;
}

bool operator<=(const string& lhs, const string& rhs) {
    return lhs.compare(rhs) <= 0;
}

bool operator>(const string& lhs, const string& rhs) {
    return lhs.compare(rhs) > 0;
}

bool operator>=(const string& lhs, const string& rhs) {
    return lhs.compare(rhs) >= 0;
}

void swap(string& lhs, string& rhs) {
    lhs.swap(rhs);
}

ostream& operator<<(ostream& os, const string& str) {
    return os.write_formatted(str.data(), str.size());
}

}  // namespace std