/// \file   String.cpp
/// \author	Randall Knapp
/// \date   December 12, 2009 - 22:21
/// \par    © Randall Knapp 2009-2010
/// \par    Email: randall\@randallknapp.com
/// \brief  Implementation for string class
#include "String.h"

// For floating point to string conversion
#include <cfloat>
#include <cmath>

namespace R
{

  // Constructors
  //////////////////////////////////////////////////////////////////////////
  
  /// Creates an empty string
  String::String()
    : m_Data( 0 ), m_Length( 0 )
  {
    MakeEmpty();
  }

  /// Initialize the string from a string literal with a given length (speed and code reuse)
  /// \param c String literal to initialize with
  /// \param length Length of c
  void String::InitFromStringLiteral( const char* c, int length )
  {
    // Set the length
    m_Length = length;

    // Allocate the memory
    m_Data = new char[ m_Length + 1 ];

    // Copy the data
    StrCopy( m_Data, c );
  }

  /// Creates a String from a string literal
  /// \param Str Null-terminated string literal to copy from
  String::String( const char* Str )
    : m_Data( 0 ), m_Length( 0 )
  {
    InitFromStringLiteral( Str, StrLen( Str ) );
  }

  /// Initialize the string from a another string
  /// \param Str String to initialize with
  void String::InitFromString( const String& Str )
  {
    // Copy the length
    m_Length = Str.m_Length;

    // Allocate the memory
    m_Data = new char[ m_Length + 1 ];

    // Copy the data
    StrCopy( m_Data, Str.m_Data );
  }

  /// Creates a copy of a String (Copy Constructor)
  /// \param Str String to copy from
  String::String( const String& Str )
    : m_Data( 0 ), m_Length( Str.m_Length )
  {
    // Allocate the memory
    m_Data = new char[ m_Length + 1 ];

    // Copy the data
    StrCopy( m_Data, Str.m_Data );
  }

  void String::InitFromInt( int Number )
  {
    // Special case: zero
    if( Number == 0 )
    {
      InitFromStringLiteral( "0", 1 );
      return;
    }

    // Convert the integer to a string
    char* Buffer = new char[32];
    char* pBuffer = Buffer;
    int Value = Number;

    if( Number < 0 )
    {
      Number = -Number;
    }

    // Convert the int to a char buffer
    while( Number > 0 )
    {
      *pBuffer = '0' + (Number % 10);
      Number /= 10;
      ++pBuffer;
    }
    *pBuffer = 0;

    // Copy the buffer into our new correctly sized buffer
    m_Length = StrLen( Buffer );
    Allocate( m_Length + 1 );
    StrCopy( m_Data, Buffer );

    // Free our memory
    delete [] Buffer;

    // Reverse the value
    Reverse();

    if( Value < 0 )
    {
      *this = String( "-" ) + *this;
    }
  }

  void String::InitFromUnsignedInt( unsigned int Number )
  {
    // Special case: zero
    if( Number == 0 )
    {
      InitFromStringLiteral( "0", 1 );
      return;
    }

    // Convert the integer to a string
    char* Buffer = new char[32];
    char* pBuffer = Buffer;

    // Convert the int to a char buffer
    while( Number > 0 )
    {
      *pBuffer = '0' + (Number % 10);
      Number /= 10;
      ++pBuffer;
    }
    *pBuffer = 0;

    // Copy the buffer into our new correctly sized buffer
    m_Length = StrLen( Buffer );
    Allocate( m_Length + 1 );
    StrCopy( m_Data, Buffer );

    // Free our memory
    delete [] Buffer;

    // Reverse the value
    Reverse();
  }

  /// Creates a string from a number
  /// \param Number Number to convert
  String::String( char Number )
    : m_Data( 0 ), m_Length( 0 )
  {
    InitFromInt( (int)Number );
  }

  /// Creates a string from a number
  /// \param Number Number to convert
  String::String( unsigned char Number )
    : m_Data( 0 ), m_Length( 0 )
  {
    InitFromUnsignedInt( (unsigned int)Number );
  }

  /// Creates a string from a number
  /// \param Number Number to convert
  String::String( short Number )
    : m_Data( 0 ), m_Length( 0 )
  {
    InitFromInt( (int)Number );
  }

  /// Creates a string from a number
  /// \param Number Number to convert
  String::String( unsigned short Number )
    : m_Data( 0 ), m_Length( 0 )
  {
    InitFromUnsignedInt( Number );
  }

  /// Creates a string from a number
  /// \param Number Number to convert
  String::String( long Number )
    : m_Data( 0 ), m_Length( 0 )
  {
    InitFromInt( (int)Number );
  }

  /// Creates a string from a number
  /// \param Number Number to convert
  String::String( unsigned long Number )
    : m_Data( 0 ), m_Length( 0 )
  {
    InitFromUnsignedInt( Number );
  }

  /// Creates a string from a number
  /// \param Number Number to convert
  String::String( int Number )
    : m_Data( 0 ), m_Length( 0 )
  {
    InitFromInt( Number );
  }

  /// Creates a string from a number
  /// \param Number Number to convert
  String::String( unsigned int Number )
    : m_Data( 0 ), m_Length( 0 )
  {
    InitFromUnsignedInt( Number );
  }

  /// Creates a string from a number
  /// \param Number Number to convert
  String::String( float Number )
  {
    // If Number is NaN, return the string "NaN".
    volatile float t = Number;
    if( t != t ) // Number is NaN
    {
      InitFromStringLiteral( "#NaN", 3 );
      return;
    }

    // If Number is +0 or -0, return "0"
    if( Number == +0 || Number == -0 )
    {
      InitFromStringLiteral( "0", 1 );
      return;
    }

    // If Number is less than zero, return "-" + String( -Number )
    if( Number < 0 )
    {
      InitFromString( String( "-" ) + String( -Number ) );
      return;
    }

    // If Number is infinity, return the string "infinity"
    if( Number == -FLT_MAX || Number == FLT_MAX )
    {
      InitFromStringLiteral( "#Infinity", 8 );
      return;
    }

    // Get the digits above and below the decimal point
    const float Shift = 1000000.0;
    int Above = (int)Number;
    int Below = (int)((Number - Above) * Shift);

    // Calculate the number of zeros to the left
    float ChangeBase	= 1.0f / log( 10.0f ); // Pre-calculate the change to base 10 (Decimal)
    int AboveBase	= (int)( log( (float)Above ) * ChangeBase ); // Calculate the length of the above part
    int BelowBase	= (int)( log( (float)Below ) * ChangeBase ); // Calculate the length of the below part
    int ZeroCount	= (AboveBase + 6) - (BelowBase + 2); // Calculate the number of zeros

    // Remove any zeros to the right
    while( Below && Below % 10 == 0 )
      Below /= 10;

    // Create the above portion of the number
    String Float( String( Above ) + "." );

    // Add the zeros into the number
    for( int i = 0; i < ZeroCount; ++i )
      Float += "0";

    // Add the below portion of the number
    Float += String( Below );

    // Copy the string
    InitFromString( Float );
  }

  /// Creates a string from a number
  /// \param Number Number to convert
  String::String( double Number )
  {
    // If Number is NaN, return the string "NaN".
    volatile double t = Number;
    if( t != t ) // Number is NaN
    {
      InitFromStringLiteral( "#NaN", 3 );
      return;
    }

    // If Number is +0 or -0, return "0"
    if( Number == +0 || Number == -0 )
    {
      InitFromStringLiteral( "0", 1 );
      return;
    }

    // If Number is less than zero, return "-" + String( -Number )
    if( Number < 0 )
    {
      InitFromString( String( "-" ) + String( -Number ) );
      return;
    }

    // If Number is infinity, return the string "infinity"
    if( Number == -DBL_MAX || Number == DBL_MAX )
    {
      InitFromStringLiteral( "#Infinity", 8 );
      return;
    }

    // Get the digits above and below the decimal point
    const double Shift = 1000000000.0;
    int Above = (int)Number;
    int Below = (int)((Number - Above) * Shift);

    // Calculate the number of zeros to the left
    double ChangeBase	= 1.0 / log( 10.0 ); // Pre-calculate the change to base 10 (Decimal)
    int AboveBase	= (int)( log( (double)Above ) * ChangeBase ); // Calculate the length of the above part
    int BelowBase	= (int)( log( (double)Below ) * ChangeBase ); // Calculate the length of the below part
    int ZeroCount	= (AboveBase + 6) - (BelowBase + 1); // Calculate the number of zeros

    // Remove any zeros to the right
    while( Below && Below % 10 == 0 )
      Below /= 10;

    // Create the above portion of the number
    String Double( String( Above ) + "." );

    // Add the zeros into the number
    for( int i = 0; i < ZeroCount; ++i )
      Double += "0";

    // Add the below portion of the number
    Double += String( Below );

    // Copy the string
    InitFromString( Double );
  }

  /// Creates a string from a boolean value
  /// \param Value Boolean value to convert
  String::String( bool Value )
  {
    if( Value )
    {
      m_Data = new char[5];
      m_Length = 4;
      StrCopy( m_Data, "true" );
    }
    else
    {
      m_Data = new char[6];
      m_Length = 5;
      StrCopy( m_Data, "false" );
    }
  }

  // Destructor
  //////////////////////////////////////////////////////////////////////////

  /// Destructor. Frees allocated memory
  String::~String()
  {
    Free();
  }

  // Private Methods
  //////////////////////////////////////////////////////////////////////////

  /// Simple string length function
  /// \param Str Null-terminated string to read from
  /// \return Number of characters before null-terminator
  int String::StrLen( const char* Str ) const
  {
    if( !Str )
      return 0;

    // Count each character until it null-terminates
    int Count = 0;
    for( ; *Str != 0; ++Str, ++Count );
    return Count;
  }

  /// Simple string copy function
  /// \param Dest Destination memory
  /// \param Src Source null-terminated string
  void String::StrCopy( char* Dest, const char* Src ) const
  {
    if( !Dest || !Src )
      return;

    // Copy each character from Src to Dest
    for( ; *Src != 0; ++Src, ++Dest )
      *Dest = *Src;
    *Dest = 0;
  }

  /// Allocates a block of memory for the string
  /// \param Size Number of bytes to allocate
  void String::Allocate( int Size )
  {
    Free();
    m_Data = new char[Size];
  }

  /// Deletes a previously allocated memory block
  void String::Free()
  {
    if( m_Data )
    {
      delete[] m_Data;
      m_Data = 0;
    }
  }

  /// Creates the empty string
  void String::MakeEmpty()
  {
    m_Length = 0;
    Allocate(1);
    m_Data[0] = 0;
  }

  /// Takes a character, and if uppercase, makes it lowercase
  /// \param c Character to modify
  void String::MakeCharLower( char& c ) const
  {
    // If c is an uppercase letter
    if( c >= 'A' && c <= 'Z' )
      c += ( 'a' - 'A' );	// Convert to lowercase
  }

  /// Takes a character, and if lowercase, makes it uppercase
  /// \param c Character to modify
  void String::MakeCharUpper( char& c ) const
  {
    // If c is an uppercase letter
    if( c >= 'a' && c <= 'z' )
      c -= ( 'a' - 'A' );	// Convert to lowercase
  }

  /// Given any character, get the lowercase version
  /// \param c Character to modify
  /// \return Modified character
  char String::GetCharLower( char c ) const
  {
    MakeCharLower( c );
    return c;
  }

  /// Given any character, get the uppercase version
  /// \param c Character to modify
  /// \return Modified character
  char String::GetCharUpper( char c ) const
  {
    MakeCharUpper( c );
    return c;
  }

  /// Checks if a character is alphanumeric ( a-z, A-Z, 0-9 )
  /// \param c Character to check
  /// \return true if alphanumeric, false otherwise
  bool String::IsAlphaNumeric( char c ) const
  {
    return ( c >= 'a' && c <= 'z' ) || ( c >= 'A' && c <= 'Z' ) || ( c >= '0' && c <= '9' );
  }

  // Operators
  //////////////////////////////////////////////////////////////////////////
  
  /// Assignment operator
  /// \param rhs String to assign
  /// \return Reference to the string after modification
  String& String::operator=( const String& rhs )
  {
    if( rhs.IsEmpty() )
    {
      Clear();
      return *this;
    }

    // Deep copy
    if( m_Length != rhs.m_Length )
    {
      m_Length = rhs.m_Length;
      Allocate( m_Length + 1 );
    }

    StrCopy( m_Data, rhs.m_Data );

    return *this;
  }

  /// String concatenation operator
  /// \param rhs String to concatenate
  /// \return New string after concatenation
  String String::operator+( const String& rhs ) const
  {
    String RetVal;

    // Create a new string of combined length
    RetVal.m_Length = m_Length + rhs.m_Length;
    RetVal.Allocate( RetVal.m_Length + 1 );

    // Copy data first from this string, then from the rhs string
    StrCopy( RetVal.m_Data, m_Data );
    StrCopy( RetVal.m_Data + m_Length, rhs.m_Data );

    return RetVal;
  }

  /// String literal concatenation operator
  /// \param rhs String literal to concatenate
  /// \return New string after concatenation
  String String::operator+( const char* rhs ) const
  {
    String RetVal;

    int Length = StrLen( rhs );

    // Create a new string of combined length
    RetVal.m_Length = m_Length + Length;
    RetVal.Allocate( RetVal.m_Length + 1 );

    // Copy data first from this string, then from the rhs string
    StrCopy( RetVal.m_Data, m_Data );
    StrCopy( RetVal.m_Data + m_Length, rhs );

    return RetVal;
  }

  /// Get a character reference from the string by index
  /// \param index 0-indexed position of character. THIS IS UNSAFE AND MAY CAUSE BUFFER OVERRUN
  /// \return Reference to requested character
  char& String::operator[]( int index )
  {
    return m_Data[index];
  }

  /// Concatenation assignment operator
  /// \param rhs String to concatenate with
  /// \return Reference to the string after modification
  String& String::operator+=( const String& rhs )
  {
    *this = *this + rhs;
    return *this;
  }

  /// Concatenation assignment with string literal operator
  /// \param rhs String literal to concatenate with
  /// \return Reference to the string after modification
  String& String::operator+=( const char* rhs )
  {
    *this = *this + rhs;
    return *this;
  }

  // Logical Operators
  //////////////////////////////////////////////////////////////////////////

  /// Equality operator, all characters must be equal
  /// \param rhs String to test with
  bool String::operator==( const String& rhs ) const
  {
    // If the lengths aren't the same, return false
    if( m_Length != rhs.m_Length )
      return false;

    // Check each character
    for( int i = 0; i < m_Length; ++i )
    {
      if( m_Data[i] != rhs.m_Data[i] )
        return false;
    }

    return true;
  }

  /// Equality with string literal
  /// \param rhs The string literal to compare with
  bool String::operator==( const char* rhs ) const
  {
    // If the lengths aren't the same, return false
    int Length = StrLen( rhs );
    if( m_Length != Length )
      return false;

    // Check each character
    for( int i = 0; i < m_Length; ++i )
    {
      if( m_Data[i] != rhs[i] )
        return false;
    }

    return true;
  }

  /// Alphabetical less-than
  /// \param rhs String to compare
  bool String::operator<( const String& rhs ) const
  {
    const char* DataIter = m_Data;
    const char* RhsIter = rhs.m_Data;

    // while the value of both pointers are not zero, and they are equal to one another
    while( *DataIter && *RhsIter && GetCharLower(*DataIter) == GetCharLower(*RhsIter) )
    {
      // Goto the next char
      ++DataIter;
      ++RhsIter;
    }

    if( GetCharLower(*DataIter) < GetCharLower(*RhsIter) )
      return true;

    return false;
  }

  /// Alphabetical greater-than
  /// \param rhs String to compare
  bool String::operator>( const String& rhs ) const
  {
    const char* DataIter = m_Data;
    const char* RhsIter = rhs.m_Data;

    // while the value of both pointers are not zero, and they are equal to one another
    while( *DataIter && *RhsIter && GetCharLower(*DataIter) == GetCharLower(*RhsIter) )
    {
      // Goto the next char
      ++DataIter;
      ++RhsIter;
    }

    if( GetCharLower(*DataIter) > GetCharLower(*RhsIter) )
      return true;

    return false;
  }

  // Public Methods
  //////////////////////////////////////////////////////////////////////////
  
  /// Erase the string
  void String::Clear()
  {
    Free();
    MakeEmpty();
  }

  /// Get the length of the string
  /// \return Length of string
  int String::Length() const
  {
    return m_Length;
  }

  /// Check if the string is the empty string
  /// \return true if string is empty, false if otherwise
  bool String::IsEmpty() const
  {
    return m_Length == 0;
  }

  /// Make this string all lowercase
  /// \return Reference to the string after modification
  String& String::MakeLower()
  {
    for( char* c = m_Data; *c; ++c )
    {
      MakeCharLower( *c );
    }
    return *this;
  }

  /// Get a copy of this string, all lowercase
  /// \return Lowercase copy of this string
  String String::ToLower() const
  {
    String RetVal( *this );
    return RetVal.MakeLower();
  }

  /// Make this string all uppercase
  /// \return Reference to the string after modification
  String& String::MakeUpper()
  {
    for( char* c = m_Data; *c; ++c )
    {
      MakeCharUpper( *c );
    }
    return *this;
  }

  /// Get a copy of this string, all uppercase
  /// \return Uppercase copy of this string
  String String::ToUpper() const
  {
    String RetVal( *this );
    return RetVal.MakeUpper();
  }

  /// Make this string Capital Case. That means that each alphabet character
  ///   preceded by a non-alphanumeric character becomes uppercase, and all
  ///   other alphabet characters become lowercase.
  /// \return Reference to the string after modification
  String& String::MakeCapitalCase()
  {
    char temp = '\0';
    char* prev = &temp;
    for( char* c = m_Data ; *c; prev = c++ )
    {
      if( !IsAlphaNumeric( *prev ) )
        MakeCharUpper( *c );
      else
        MakeCharLower( *c );
    }
    return *this;
  }

  /// Get a copy of this string in Capital Case
  /// \return Capital Case copy of this string
  String String::ToCapitalCase() const
  {
    String RetVal( *this );
    return RetVal.MakeCapitalCase();
  }

  /// Reverse this string
  /// \return Reference to the string after modification
  String& String::Reverse()
  {
    char* Begin = m_Data;
    char* End = m_Data + m_Length - 1;
    char temp;
    for( ; Begin < End; ++Begin, --End )
    {
      temp = *Begin;
      *Begin = *End;
      *End = temp;
    }

    return *this;
  }

  /// Get a reversed copy of this string
  /// \return Reversed copy
  String String::GetReversed() const
  {
    String RetVal( *this );
    return RetVal.Reverse();
  }

  /// Delete a character from the string
  /// \param Index Location in string to delete
  /// \return Reference to the string after modification
  String& String::DeleteChar( int Index )
  {
    // Make a new buffer for the string that is slightly shorter
    // m_Length is used because we usually allocate m_Length + 1 (for the
    // null terminator). This is essentially (m_Length + 1 - 1).
    char* Buffer = new char[ m_Length ];
    
    // Zero out the deleted character (this works nice with StrCopy)
    m_Data[Index] = 0;

    // Copy the first part and the last part to the buffer
    StrCopy( Buffer, m_Data );
    StrCopy( Buffer + Index, m_Data + Index + 1 );

    // Destroy the old string and keep the Buffer
    Free();
    m_Data = Buffer;

    return *this;
  }

  /// Deletes the last character in a string, does not reallocate memory
  /// \return Reference to the string after modification
  String& String::Backspace()
  {
    m_Data[ m_Length - 1 ] = 0;
    m_Length -= 1;

    return *this;
  }

  /// Gets a new string between two indices (inclusive)
  /// \param Start Index to first character of substring (inclusive)
  /// \param End Index to last character of substring (inclusive)
  String String::SubString( int Start, int End ) const
  {
    // Make sure our string indices are valid
    if( Start < 0 || Start > m_Length )
      return String();
    if( End < Start || End > m_Length )
      return String();

    // Create our new string
    String RetVal;
    RetVal.m_Length = ( End - Start + 1 );
    RetVal.Allocate( RetVal.m_Length + 1 );

    // Copy the substring
    for( int i = Start, c = 0; i <= End; ++i, ++c )
      RetVal.m_Data[c] = m_Data[i];

    // Set null terminator
    RetVal.m_Data[RetVal.m_Length] = 0;

    // Return the substring
    return RetVal;
  }

#ifdef R_USING_STL
  void String::GetTokens( const String& Delimiters, std::vector<String>& Out ) const
  {
    if( IsEmpty() )
      return;

    //Pointer to our delimiters
    const char* d = Delimiters.m_Data;

    // Number of delimiters
    int NumDelims = Delimiters.m_Length;

    bool WasDelim = true;
    bool IsDelim = true;
    int TokenBegin = 0;

    // For all of the characters in the string
    for( int i = 0; i < m_Length; ++i )
    {
      // For each of the delimiters
      WasDelim = IsDelim;
      IsDelim = false;

      for( int k = 0; k < NumDelims; ++k )
      {
        if( m_Data[i] == d[k] )
          IsDelim = true;
      }

      // Begin a token when we go from delimiter to non-delimiter
      if( WasDelim && !IsDelim )
      {
        TokenBegin = i;
      }

      // End a token when we go from non-delimiter to delimiter
      else if( !WasDelim && IsDelim )
      {
        Out.push_back( SubString( TokenBegin, i - 1 ) );
      }
    }

    // If the last character was not a delimiter, add the last substring as a token
    if( !IsDelim )
    {
      Out.push_back( SubString( TokenBegin, m_Length - 1 ) );
    }

  }
#endif

  const char* String::ToCString() const
  {
    return m_Data;
  }

}