#include <string>

// Wrapper around tolower().
inline char ToLowerCopy(char value);
// Similar.
inline char ToUpperCopy(char value);

/* Destructively applies ToLowerCopy() to each character in given string.
 * @param str
 *        String which to modify.
 * @param T
 *        Any character type for which ToLowerCopy() is defined. Examples: char, wchar_t. */
template<typename T>
inline void ToLower(std::basic_string<T>& str);

// Same, but using T* as the string type (e.g., char*).
template<typename T>
inline void ToLower(T* str);
// Same, but for any string type T that supports operator[] (e.g., char*, string).
template<typename T>
inline void ToLower(T& str, size_t len);

// Like the above, but the opposite.
template<typename T>
inline void ToUpper(std::basic_string<T>& str);
template<typename T>
inline void ToUpper(T* str);
template<typename T>
inline void ToUpper(T& str, size_t len);

// A non-destructive version of ToLower() which returns a modified copy of the input string.
template<typename T>
inline std::basic_string<T> ToLowerCopy(std::basic_string<T> const& str);

// A non-destructive version of ToLower() which returns a modified copy of the input string.
template<typename T>
inline std::basic_string<T> ToUpperCopy(std::basic_string<T> const& str);

/* Returns true if and only if the two given strings are equal, ignoring case.
 * @param s1
 *        String 1.
 * @param s2
 *        String 2.
 * @param T
 *        Any character type for which ToLowerCopy() is defined. Examples: char, wchar_t.
 * @return See above. */
template<typename T>
inline bool EqualsI(std::basic_string<T> const& s1, std::basic_string<T> const& s2);

// Same, but using T* as the string type (e.g., char*). This allows for faster comparison against C-string literals.
template<typename T>
inline bool EqualsI(std::basic_string<T> const& s1, T const* s2);
template<typename T>
inline bool EqualsI(T const* s1, std::basic_string<T> const& s2);
template<typename T>
inline bool EqualsI(T const* s1, T const* s2);
// Same, but uses T[] arrays of given length.
template<typename T>
inline bool EqualsI(T const* s1, size_t size1, T const* s2, size_t size2);
// Same, but both arrays are assumed to be of the same given size.
template<typename T>
inline bool EqualsI(T const* s1, size_t size, T const* s2);

/* Returns true if and only if the needle is contained in the haystack. CASE-SENSITIVE!
 * @param haystack
 *        String to search.
 * @param needle
 *        String for which to search. 
 * @param T
 *        Character type. Examples: char, wchar_t. */
template<typename T>
inline bool Contains(std::basic_string<T> const& haystack, std::basic_string<T> const& needle);

// Same, but using T* as the string type (e.g., char*). This allows for faster comparison against C-string literal.
template<typename T>
inline bool Contains(std::basic_string<T> const& haystack, T const* needle);
// Same, but uses T[] arrays of given length.
template<typename T>
inline bool Contains(std::basic_string<T> const& haystack, T const* needle, size_t needleSize);

// Same as above, but case-insensitive versions.
template<typename T>
inline bool ContainsI(std::basic_string<T> const& haystack, std::basic_string<T> const& needle);
template<typename T>
inline bool ContainsI(std::basic_string<T> const& haystack, T const* needle);
template<typename T>
inline bool ContainsI(std::basic_string<T> const& haystack, T const* needle, size_t needleSize);

/* Returns true if and only if the first needle.size() characters of haystack exist and are equal to needle.
 * CASE-SENSITIVE!
 * @param haystack
 *        String to search.
 * @param needle
 *        Prefix for which to search.
 * @param T
 *        Character type. Examples: char, wchar_t. */
template<typename T>
inline bool StartsWith(std::basic_string<T> const& haystack, std::basic_string<T> const& needle);

// Same, but using T* as the string type (e.g., char*). This allows for faster comparison against C-string literal.
template<typename T>
inline bool StartsWith(std::basic_string<T> const& haystack, T const* needle);
// Same, but uses T[] arrays of given length.
template<typename T>
inline bool StartsWith(std::basic_string<T> const& haystack, T const* needle, size_t needleSize);

// Same as above, but case-insensitive versions.
template<typename T>
inline bool StartsWithI(std::basic_string<T> const& haystack, std::basic_string<T> const& needle);
template<typename T>
inline bool StartsWithI(std::basic_string<T> const& haystack, T const* needle);
template<typename T>
inline bool StartsWithI(std::basic_string<T> const& haystack, T const* needle, size_t needleSize);

// Same as above, but compares the end of the haystack instead of the beginning.
template<typename T>
inline bool EndsWith(std::basic_string<T> const& haystack, std::basic_string<T> const& needle);
template<typename T>
inline bool EndsWith(std::basic_string<T> const& haystack, T const* needle);
template<typename T>
inline bool EndsWith(std::basic_string<T> const& haystack, T const* needle, size_t needleSize);
template<typename T>
inline bool EndsWithI(std::basic_string<T> const& haystack, std::basic_string<T> const& needle);
template<typename T>
inline bool EndsWithI(std::basic_string<T> const& haystack, T const* needle);
template<typename T>
inline bool EndsWithI(std::basic_string<T> const& haystack, T const* needle, size_t needleSize);

/* Replaces every occurrence of the given character with the other given character.
 * @param haystack
 *        String to possibly modify.
 * @param needle
 *        Character to possibly replace. If haystack is UTF-8 (char) or UTF-16 (wchar_t), this should be ASCII.
 * @param rep
 *        Replacement character. Same UTF-8/16 guidelines as needle.
 * @param T
 *        Character type. Examples: char, wchar_t. */
template<typename T>
inline void ReplaceAll(std::basic_string<T>& haystack, T const& needle, T const& rep);

// Non-destructive version that returns a possibly modified copy of the haystack.
template<typename T>
inline std::basic_string<T> ReplaceAllCopy(std::basic_string<T> const& haystack, T const& needle, T const& rep);

/* Removes every occurrence within the haystack string of any of the characters in the needleSet string.
 * This is CASE-SENSITIVE.
 * @param haystack
 *        The string to potentially modify.
 * @param needleSet
 *        The set of characters each of which to remove. If haystack is in UTF-8 (char) or UTF-16 (wchar_t), each
 *        character here should be ASCII.
 * @param T
 *        A character type. Examples: char, wchar_t. */
template<typename T>
inline void StripChars(std::basic_string<T>& haystack, std::basic_string<T> const& needleSet);

// Same, but using T* as the string type (e.g., char*). This allows for faster comparison against C-string literal.
template<typename T, typename NeedleString>
inline void StripChars(std::basic_string<T>& haystack, T const* needleSet);

// Same, but uses T[] arrays of given length.
template<typename T>
inline void StripChars(std::basic_string<T>& haystack, T const* needleSet, size_t needleSetSize);

// Non-destructive versions of the above strip functions (returning possibly modified copies of the input strings).
template<typename T, typename NeedleString>
inline std::basic_string<T> StripCharsCopy(std::basic_string<T> const& haystack, NeedleString const& needleSet);
template<typename T>
inline std::basic_string<T> StripCharsCopy(std::basic_string<T> const& haystack,
                                             T const* needleSet, size_t needleSetSize);

// Inline/template implementations.

char ToLowerCopy(char value)
{ 
  return 
#if 1
    tolower(value);
#else    
    (('A' < value) && (value < 'Z')) ? (value - 'A' + 'a') : value;
#endif
}

char ToUpperCopy(char value)
{
#if 1 
  return 
    toupper(value);
#else
    (('a' < value) && (value < 'z')) ? (value - 'a' + 'A') : value;
#endif
}

template<typename T>
void ToLower(T& str, size_t len)
{
  for (size_t i = 0; i != len; ++i)
  {
    str[i] = ToLowerCopy(str[i]);
  }
}

template<typename T>
void ToLower(std::basic_string<T>& str)
{
  ToLower(str, str.size());
}

template<typename T>
void ToLower(T* str)
{
  ToLower(str, std::char_traits<T>::length(str));
}

template<typename T>
void ToUpper(T& str, size_t len)
{
  for (size_t i = 0; i != len; ++i)
  {
    str[i] = ToUpperCopy(str[i]);
  }
}

template<typename T>
void ToUpper(std::basic_string<T>& str)
{
  ToUpper(str, str.size());
}

template<typename T>
void ToUpper(T* str)
{
  ToUpper(str, std::char_traits<T>::length(str));
}

template<typename T>
std::basic_string<T> ToLowerCopy(std::basic_string<T> const& str)
{
  std::basic_string<T> str2 = str;
  ToLower(str2);
  return str2;
}

template<typename T>
std::basic_string<T> ToUpperCopy(std::basic_string<T> const& str)
{
  std::basic_string<T> str2 = str;
  ToUpper(str2);
  return str2;
}

template<typename T>
bool EqualsI(T const* s1, size_t size, T const* s2)
{
  for (size_t i = 0; i != size; ++i)
  {
    if (ToLowerCopy(s1[i]) != ToLowerCopy(s2[i]))
    {
      return false;
    }
  }
  return true;
}

template<typename T>
bool EqualsI(T const* s1, size_t size1, T const* s2, size_t size2)
{
  return (size1 == size2) ? EqualsI(s1, size1, s2) : false;
}

template<typename T>
bool EqualsI(std::basic_string<T> const& s1, std::basic_string<T> const& s2)
{
  return EqualsI(s1.data(), s1.size(), s2.data(), s2.size());
}

template<typename T>
bool EqualsI(std::basic_string<T> const& s1, T const* s2)
{
  return EqualsI(s1.data(), s1.size(), s2, std::char_traits<T>::length(s2));
}
template<typename T>
bool EqualsI(T const* s1, std::basic_string<T> const& s2)
{
  return EqualsI(s2, s1);
}
template<typename T>
bool EqualsI(T const* s1, T const* s2)
{
  return EqualsI(s1, std::char_traits<T>::length(s1), s2, std::char_traits<T>::length(s2));
}

template<typename T>
bool Contains(std::basic_string<T> const& haystack, T const* needle, size_t needleSize)
{
  return haystack.find(needle, 0, needleSize) != std::basic_string<T>::npos;
}

template<typename T>
bool Contains(std::basic_string<T> const& haystack, T const* needle)
{
  return Contains(haystack, needle, std::char_traits<T>::length(needle));
}

template<typename T>
bool Contains(std::basic_string<T> const& haystack, std::basic_string<T> const& needle)
{
  return Contains(haystack, needle.data(), needle.size());
}

template<typename T>
bool ContainsI(std::basic_string<T> const& haystack, T const* needle, size_t needleSize)
{
  // For performance, avoid simply making lower-case versions of both strings.
  if (needleSize <= haystack.size())
  {
    /* Go along the haystack. Each time we see a matching character, increase charsMatched; each time we see
     * a non-matching one, we start over (reset charsMatched). Stop once we've either matched the entire needle,
     * or there are too few characters remaining in the haystack to match all of the rest of the needle. */
    size_t charsMatched = 0;
    for (size_t i = 0;
         (charsMatched != needleSize) && (i < haystack.size() - (needleSize - charsMatched) + 1);
         ++i)
    {
      if (ToLowerCopy(haystack[i]) == ToLowerCopy(needle[charsMatched]))
      {
        ++charsMatched;
      }
      else
      {
        charsMatched = 0;
      }
    }
    if (charsMatched == needleSize)
    {
      return true;
    }
  }
  return false;
}

template<typename T>
bool ContainsI(std::basic_string<T> const& haystack, std::basic_string<T> const& needle)
{
  return ContainsI(haystack, needle.data(), needle.size());
}
template<typename T>
bool ContainsI(std::basic_string<T> const& haystack, T const* needle)
{
  return ContainsI(haystack, needle, std::char_traits<T>::length(needle));
}

template<typename T>
bool StartsWith(std::basic_string<T> const& haystack, T const* needle, size_t needleSize)
{
  if (needleSize > haystack.size())
  {
    return false;
  }
  for (size_t i = 0; i != needleSize; ++i)
  {
    if (haystack[i] != needle[i])
    {
      return false;
    }
  }
  return true;
}

template<typename T>
bool StartsWith(std::basic_string<T> const& haystack, std::basic_string<T> const& needle)
{
  return StartsWith(haystack, needle.data(), needle.size());
}

// Same, but using T* as the string type (e.g., char*). This allows for faster comparison against C-string literal.
template<typename T>
bool StartsWith(std::basic_string<T> const& haystack, T const* needle)
{
  return StartsWith(haystack, needle, std::char_traits<T>::length(needle));
}

template<typename T>
bool StartsWithI(std::basic_string<T> const& haystack, T const* needle, size_t needleSize)
{
  return (needleSize > haystack.size()) ?
           false :
           EqualsI(haystack.data(), needleSize, needle);
}

template<typename T>
bool StartsWithI(std::basic_string<T> const& haystack, std::basic_string<T> const& needle)
{
  return StartsWithI(haystack, needle.data(), needle.size());
}

template<typename T>
bool StartsWithI(std::basic_string<T> const& haystack, T const* needle)
{
  return StartsWithI(haystack, needle, std::char_traits<T>::length(needle));
}

template<typename T>
bool EndsWith(std::basic_string<T> const& haystack, T const* needle, size_t needleSize)
{
  if (needleSize > haystack.size())
  {
    return false;
  }
  const size_t offset = haystack.size() - needleSize;
  for (size_t i = 0; i != needleSize; ++i)
  {
    if (haystack[i + offset] != needle[i])
    {
      return false;
    }
  }
  return true;
}

template<typename T>
bool EndsWith(std::basic_string<T> const& haystack, std::basic_string<T> const& needle)
{
  return EndsWith(haystack, needle.data(), needle.size());
}

template<typename T>
bool EndsWith(std::basic_string<T> const& haystack, T const* needle)
{
  return EndsWith(haystack, needle, std::char_traits<T>::length(needle));
}

template<typename T>
bool EndsWithI(std::basic_string<T> const& haystack, T const* needle, size_t needleSize)
{
  return (needleSize > haystack.size()) ?
           false :
           EqualsI(haystack.data() + haystack.size() - needleSize, needleSize, needle);
}

template<typename T>
bool EndsWithI(std::basic_string<T> const& haystack, std::basic_string<T> const& needle)
{
  return EndsWithI(haystack, needle.data(), needle.size());
}

template<typename T>
bool EndsWithI(std::basic_string<T> const& haystack, T const* needle)
{
  return EndsWithI(haystack, needle, std::char_traits<T>::length(needle));
}

template<typename T>
void StripChars(std::basic_string<T>& haystack, T const* needleSet, size_t needleSetSize)
{
  /* Could try to use std::remove_if() algorithm here (the below is basically a string-specific reimplementation of it).
   * However, then we'd need to provide a predicate object for "is ch in needleSet?". It's possible but hairy syntax
   * (though nicely generic), and I'm worried about performance in Windows as well as gcc memory usage. */
  const size_t npos = std::basic_string<T>::npos;

  /* We must go through the string, writing each character not in needleSet to the beginning of the string (always
   * following the last character written there). replacedPos is that next following position at the start of each loop
   * iteration. An added optimization is that we need not write anything before the first "bad" character, since then
   * we'd just be writing characters onto themselves. So, find the first bad character first, then start the
   * overwriting. */
  size_t pos = haystack.find_first_of(needleSet, 0, needleSetSize);
  if (pos == npos)
  {
    return; // All character are good, so nothing to do.
  }
  size_t replacedPos = pos;
  for (++pos; pos != haystack.size(); ++pos)
  {
    const T& ch = haystack[pos];
    // Use the uber-fast implementation of find for char type T (probably memchr() or wchar_t equivalent).
    if (!(std::char_traits<T>::find(needleSet, needleSetSize, ch)))
    {
      haystack[replacedPos++] = ch; // It's a good character, so copy it earlier in string.
    }
  }

  // Done moving all the good characters to the start of the string. Hack off the garbage following that.
  haystack.resize(replacedPos);
}

template<typename T>
void StripChars(std::basic_string<T>& haystack, std::basic_string<T> const& needleSet)
{
  StripChars(haystack, needleSet.data(), needleSet.size());
}

template<typename T>
void StripChars(std::basic_string<T>& haystack, T const* needleSet)
{
  StripChars(haystack, needleSet, std::char_traits<T>::length(needleSet));
}

template<typename T, typename NeedleString>
std::basic_string<T> StripCharsCopy(std::basic_string<T> const& haystack, NeedleString const& needleSet)
{
  std::basic_string<T> haystack2 = haystack;
  StripChars(haystack2, needleSet);
  return haystack2;
}

template<typename T>
std::basic_string<T> StripCharsCopy(std::basic_string<T> const& haystack,
                                      T const* needleSet, size_t needleSetSize)
{
  std::basic_string<T> haystack2 = haystack;
  StripChars(haystack2, needleSet, needleSetSize);
  return haystack2;
}

template<typename T>
void ReplaceAll(std::basic_string<T>& haystack, T const& needle, T const& rep)
{
  // Just use the standard algorithm, as a basic_string<T> is a sequence of Ts.
  std::replace(haystack.begin(), haystack.end(), needle, rep);
}

// Non-destructive version that returns a possibly modified copy of the haystack.
template<typename T>
std::basic_string<T> ReplaceAllCopy(std::basic_string<T> const& haystack, T const& needle, T const& rep)
{
  std::basic_string<T> haystack2 = haystack;
  RSReplaceAll(haystack2, needle, rep);
  return haystack2;
}