//=-- String.cpp - Play with String objects... -------------------------------=
//
//  This class implements a bunch of useful and fast little String manipulation
//    routines.
//
//=---------------------------------------------------------------------------=
//  This file is copyright (c) 1997-2000 Chris Lattner
//=---------------------------------------------------------------------------=

#include <malloc.h>
#include <memory.h>
#include <ctype.h>
#include <assert.h>
#include <string.h>                  // We use memcpy for performance

#include "Serialize.h"
#include "MSString.h"
#include "PlatformAbstraction.h"

// SCSIZE - Size of the string chunk header (minus one for 1 element data)
//
#define SCSIZE (sizeof(struct StringChunk)-1)

String::StringChunk *String::GetEmptyStringChunk() {
  static StringChunk EmptyString = { 
    0, // length
    1, // AllocLength
    1, // RefCount    - Never go away
    "" // Data
  };

  // Make sure nobody is playing with EmptyString!!!
  assert(EmptyString.length == 0 &&
         EmptyString.AllocLength == 1 &&
         EmptyString.Data[0] == 0);

  return &EmptyString;
}

String::String() {
  Chunk = GetEmptyStringChunk();
  Chunk->RefCount++;
}


// Mutate - Call this before you modify a string to make sure you have a private
// copy of the string chunk.
//
void String::mutate(int NewLen) {
  StringChunk *Old = Chunk;
  if (NewLen < 0) NewLen = Old->length + 1;

  if (Chunk->RefCount == 1) {
    if (NewLen <= Chunk->length) {
      Chunk->length = NewLen-1;
      Chunk->Data[NewLen-1] = 0;
    }
    return;
  }
  
  Chunk = (StringChunk*)malloc(SCSIZE + NewLen);

  if (NewLen >= Old->length) 
    Chunk->length = Old->length;
  else
    Chunk->length = NewLen-1;

  Chunk->AllocLength = NewLen;
  Chunk->RefCount = 1;
  Old->RefCount--;      // Can't reach zero here...
  memcpy(Chunk->Data, Old->Data, Chunk->length+1);  // Copy null also

  if (NewLen <= Old->length) 
    Chunk->Data[NewLen-1] = 0;
}

// Create a String, putting the String representation of n into it.
String String::IntToStr(const int n) {
  char Buffer[20];
  int Length = 0;
  int i;

  for (i = n; i > 0; i /= 10) {
    memmove(Buffer+1, Buffer, Length);
    Buffer[0] = (i % 10)+'0';
    Length++;
  }

  if (Length == 0)                   // If passed in value is zero, don't
    Buffer[Length++] = '0';          //    create an empty String

  Buffer[Length] = 0;
  return String(Buffer);
}


// Not very pretty or fast, but it works for now.
//
String String::DoubleToStr(const double d, int Prec) {
  int Whole = (int)d;
  double Frac  = (d - (double)Whole);

  for (int i = 0; i < Prec; i++)
    Frac *= 10.0;

  return String::IntToStr(Whole) + "." + String::IntToStr((int)Frac);
}

String::String(const String &S) : Object(S) {
  Chunk = S.Chunk;    // Pointer copy!
  Chunk->RefCount++;
}

String::String(const char *str) {
  int length;

  if ((str != 0) && (str[0] != 0)) {
    length = strlen(str);

    Chunk = (StringChunk*)malloc(SCSIZE + length + 1);
    Chunk->length = length;
    Chunk->AllocLength = length + 1;
    Chunk->RefCount = 1;
    memcpy(Chunk->Data, str, length+1);  // Copy null
  } else {
    Chunk = GetEmptyStringChunk();
    Chunk->RefCount++;
  }
}

String::String(const char C) {
  Chunk = (StringChunk*)malloc(SCSIZE + 2);
  Chunk->length = 1;
  Chunk->AllocLength = 2;
  Chunk->RefCount = 1;
  Chunk->Data[0] = C;
  Chunk->Data[1] = 0;
}

void String::ValidateLength(int Len, int Preserve) {
  StringChunk *New;
  assert(Chunk->Data[Chunk->length] == 0 && "Check for null");

  if (Chunk->AllocLength < Len) {
    New = (StringChunk*)malloc(SCSIZE + Len);
    New->AllocLength = Len;
    New->RefCount = 1;

    if (Preserve) {
      New->length = Chunk->length;
      memcpy(New->Data, Chunk->Data, Chunk->length+1); // Copy Null
    } else {
      New->length = 0;
      New->Data[0] = 0;
    }

    if (--Chunk->RefCount == 0) 
      free(Chunk);
    Chunk = New;

  } else {
    if (Chunk->RefCount > 1) {
      //      int OldLen = Chunk->length;
      //      StringChunk *OldChunk = Chunk;
      // Make sure mutate realloc's right amount of space...
      //      Chunk->length = Len-1;  
      mutate(Len);
      //      Chunk->length = OldLen;
      //OldChunk->length = OldLen;
    }
  }
}

// Hash - Returns a hashvalue for the string below TableSize.
//
// This routine is the single biggest bottleneck in MagicStats, which, as you 
// can imagine, annoys me to no end.  Especially with long strings, we try to 
// take measures that allows us to not look at EVERY character in the string.
// 
unsigned int String::Hash(const String &S, int TableSize) {
  unsigned int Return = 1;
  StringChunk *C = S.Chunk;;
  unsigned char *P = (unsigned char *)C->Data;

  assert(C->RefCount);

  if (C->length < 60) {
    for (int i = 0; i < C->length; i++) {
      Return = (Return << 6) + *P++;
      Return %= TableSize;
    }
    return Return;
  } else {
    // Hash in the first and last 20 characters...
    unsigned char *P2 = (unsigned char *)C->Data+C->length-21;
    int i = 0;

    for (i = 0; i < 10; i++) {
      Return = (Return << 8) + *P++;
      Return = (Return << 7) + *P2++;
      Return %= TableSize;

      Return = (Return << 8) + *P++;
      Return = (Return << 7) + *P2++;
      Return %= TableSize;
    }

    int Inc = 4;
    P2 = (unsigned char *)C->Data+C->length-21;

    // Hash in a few characters in between...
    while (((unsigned long)P)+8*Inc < (unsigned long)P2) {
      for (int j = 0; j < 8; j++) {
        Return = (Return << 8) + *P;
        Return %= TableSize;
        P += Inc;
      }

      Inc *= 2;
    }
  }
  return Return;
}

// Fill - Fills the String with "Length" chars...
void String::Fill(char c, int Length) {
  if (Length < 0) Length = 0;
  ValidateLength(Length+1, 0);

  memset(Chunk->Data, c, Length);
  Chunk->Data[Length] = 0;

  if (c != 0)
    Chunk->length = Length;
  else
    Chunk->length = 0;
}

void String::cat(const String &S, const int Num) {
  if (this == &S) return;   // What are you doing to me!??!
  if (S.Chunk == GetEmptyStringChunk()) return;  // Appending an empty string.

  if ((Num < 0) || (Num >= S.Length())) {
    ValidateLength(S.Chunk->length+Chunk->length+1);
    memcpy(Chunk->Data+Chunk->length, S.Chunk->Data, S.Chunk->length+1);
    Chunk->length += S.Chunk->length;
  } else {
    ValidateLength(Chunk->length+Num+1);
    memcpy(Chunk->Data+Chunk->length, S.Chunk->Data, Num);
    Chunk->length += Num;
    Chunk->Data[Chunk->length] = 0;
  }
}
  
void String::cpy(const String &Str) {
  if (Chunk == Str.Chunk) return;

  if (--Chunk->RefCount == 0)
    free(Chunk);

  Chunk = Str.Chunk;
  Chunk->RefCount++;
}

int String::strchr(const char C, const int Start) const {
  if (Chunk == GetEmptyStringChunk()) return -1;  // Zero length string...
  const char *c = Chunk->Data+Start;
  int i = Start;
  int len = Chunk->length;

  while ((*c != C) && (i < len)) {
    c++; i++;
  }

  if (i == len)
    return -1;

  return i;
}

int String::strrchr(const char c, const int StartIdx) const {
  const char *e = Chunk->Data, *StartPtr = Chunk->Data;
  if (StartIdx < 0)
    e += Chunk->length-1;
  else
    e += StartIdx;
  
  while (e >= StartPtr) {
    if (*e-- == c) return (int)(e-StartPtr)+1;
  }
  return -1;
}

int String::substr(const String &Sub, const int Start) const {
  int Found = Start;
  int i, len = Chunk->length, sublen = Sub.Chunk->length;
  const char *Data = Chunk->Data, *SubData = Sub.Chunk->Data;
  
  if ((Start >= len) || (sublen > len))
     return -1;

  if (sublen == 0) return Start;

  Found = strchr(SubData[0], Found);
  while ((Found != -1) && (Found+sublen <= len)) {
    if (Found != -1) {
      for (i = Found; i < Found+sublen; i++)
        if (Data[i] != SubData[i-Found]) break;
      if (i == Found+sublen)
        return Found;
      Found++;
    }

    Found = strchr(SubData[0], Found);
  }

  return -1;
}

// ReplaceSubString - Replace all occurrances of "Old" with "New".
//
int String::ReplaceSubString(const String &Old, const String &New) {
  String Left, Right;
  int i;

  i = substr(Old, 0);
  if (i == -1) return 0;

  while (i != -1) {
    Right = Left = *this;
    Left.Left(i);
    Right.Right(Chunk->length - i-Old.Chunk->length);
    *this = Left + New + Right;

    i = substr(Old, i+New.Chunk->length);
  }

  return 1;
}

int String::Compare(const String &S) const {
  if (Chunk == S.Chunk) return 0;  // Equal!
  return ::strcmp(Chunk->Data, S.Chunk->Data);
}

int String::nCompare(const String &S, int N) const {
  if (Chunk == S.Chunk) return 0;  // Equal!
  if (N < 0) N = (S.Length() < Length() ? S.Length() : Length()); // minlength
  return ::strncmp(Chunk->Data, S.Chunk->Data, N);
}

int String::iCompare(const String &S) const {
  if (Chunk == S.Chunk) return 0;  // Equal!
  return PlatformAbstraction::strcasecmp(Chunk->Data, S.Chunk->Data);
}

int String::atoi(const int Base) const {
  int i, Return = 0, len = Chunk->length;

  for (i = 0; i < len; i++) {
    if (Chunk->Data[i] > '9' || Chunk->Data[i] < '0') break;
    Return *= Base;
    Return += Hex2Int(Chunk->Data[i]);
  }
  return Return;
}

int String::Tokenize(const String &Token, String &Return) {
  int i, DidLeftReduction = 0;

  do {
    for (i = 0; (i < Length()) && (Token.strchr(Chunk->Data[i]) == -1); i++)
      ;
    if (i == Length()) i = -1;
    
    if (i == 0) {                       // If leading char is token, strip off
      DidLeftReduction = 1;
      while ((Chunk->Data[0] != 0)      // all leading tokens and return zero
        &&  (Token.strchr(Chunk->Data[0]) != -1)) 
        Right(Length()-1);
    }
  } while (i == 0);

  Return = *this;

  mutate();

  if (i < 0) {
    Chunk->length = 0;
    Chunk->Data[0] = 0;

    if (DidLeftReduction)
      return 0;
    return i;
  } 
  
  Return.Left(i);
  Right(Length()-i-1);

  return i;
}

// GetParameter - Takes a comma delimited String of parameters and returns the
//   first one in the Return variable.  It then strips the first variable from
//   the Str variable.                                                      
//
int String::GetParameter(String &Return) {
  if (Length() == 0) 
     return -1;               // Error, nothing left

  Tokenize(",", Return);
  return 0;
}

int String::GetParameter(int &Return) {
  String RetStr;
  if (Length() == 0) 
     return -1;               // Error, nothing left

  Tokenize(",", RetStr);
  Return = RetStr.atoi();
  return 0;
}

int String::Left(const int X) {
  if (X == Length()) return 0;

  if ((X <= Chunk->length) && (X > 0)) {
    mutate(X+1);  // Only retain X Chars...
    return 0;
  } else if (X == 0) {
    if (--Chunk->RefCount == 0)
      free(Chunk);

    Chunk = GetEmptyStringChunk();
    Chunk->RefCount++;
    return 0;
  } else {
    return -1;
  }
}

int String::Right(const int X) {
  if (X == Length()) return 0;

  if (X == 0) {
    if (--Chunk->RefCount == 0)
      free(Chunk);

    Chunk = GetEmptyStringChunk();
    Chunk->RefCount++;
    return 0;
  }

  mutate();

  if ((X <= Chunk->length) && (X >= 0)) {
    memmove(Chunk->Data, &Chunk->Data[Length()-X], X+1); // Copy the NULL too.
    Chunk->length = X;
    return 0;
  } 

  return -1;
}

void String::ToUpper() {
  mutate();
  for (int i=0; i < Length(); i++)
    Chunk->Data[i] = toupper(Chunk->Data[i]);
}

void String::ToLower() {
  mutate();
  for (int i=0; i < Length(); i++)
    Chunk->Data[i] = tolower(Chunk->Data[i]);
}

istream &String::ReadLine(istream &I) {
  const int Bytes = 400;
  char Buffer[Bytes], c;

  while (isspace(I.peek()) && (!I.eof())) 
    I.get(c);

  if (I.eof()) return I;

  mutate();
  Chunk->Data[0] = 0;   // Clear the String
  Chunk->length = 0;

  while ((I.peek() != '\n') && (!I.eof())) {
    I.get(Buffer, Bytes-1, '\n');
    cat(Buffer);
  }

  // Okay, if we hit a '\n' grab and ignore it so we don't get it next time...
  if (!I.eof()) I.get(c);

  return I;
}

Serialize &String::SaveState(Serialize &O) const {
  return O << Chunk->Data;
}

Serialize &String::RestoreState(Serialize &I) {
  int Len = I.PeekLength();
  ValidateLength(Len, 0);
  Chunk->length = Len-1;
  return I >> Chunk->Data;
}
