// -*- mode: c++ -*-
//-----------------------------------------------------------------------------
//
// Copyright(C) 2016 Zohar Malamant
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
// 02111-1307, USA.
//
//-----------------------------------------------------------------------------

#ifndef __IMP_STRINGVIEW__523920528
#define __IMP_STRINGVIEW__523920528

#include <string>
#include "MurmurHash3"

namespace imp {
  /**
   * \brief A constexpr std::strlen
   *
   * The current implementations of std::char_traits<T>::length and std::char_traits<T>::compare
   * aren't constexpr, so we create our own.
   * This should be replaced when C++17 is fully supported by compilers.
   */
  template <class CharT>
  constexpr size_t __h_constexpr_strlen(const CharT *str) noexcept
  {
      if (!str) return 0;
      size_t len = 0;
      while (str[len++]);
      return len ? len - 1 : 0; // We don't like '\0', so decrement
  }

  /**
   * \brief A constexpr std::strncmp
   *
   * Should be replaced when C++17 is out. See {\ref __h_constexpr_strlen}.
   */
  template <class CharT>
  constexpr int __h_constexpr_strcmp(const CharT *a, size_t a_len, const CharT *b, size_t b_len) noexcept
  {
      auto len = std::min(a_len, b_len);
      for (size_t i = 0; i < len; i++)
      {
          if (a[i] < b[i])
              return -1;
          else if (a[i] > b[i])
              return 1;
      }
      return (a_len < b_len) ? -1 : (a_len > b_len) ? 1 : 0;
  }

  template <class CharT>
  constexpr bool __h_constexpr_isspace(CharT c) noexcept
  {
      return c == ' ' || c == '\f' || c == '\n' || c == '\r' || c == '\t' || c == '\v';
  }

  /**
   * \brief A constexpr std::strnicmp
   *
   * Should be replaced when C++17 is out. See {\ref __h_constexpr_strlen}.
   */
  template <class CharT>
  constexpr int __h_constexpr_stricmp(const CharT *a, size_t a_len, const CharT *b, size_t b_len) noexcept
  {
      auto len = std::min(a_len, b_len);
      for (size_t i = 0; i < len; i++)
      {
          auto a_lwr = tolower(a[i]);
          auto b_lwr = tolower(b[i]);
          if (a_lwr < b_lwr)
              return -1;
          else if (a_lwr > b_lwr)
              return 1;
      }
      return (a_len < b_len) ? -1 : (a_len > b_len) ? 1 : 0;
  }

  /**
   * \class BasicStringView <imp/util/StringView>
   * \brief A non-owning string container
   *
   * \tparam CharT Type of character
   * \tparam Traits Traits for character type
   *
   * This is an implementation of C++17's std::basic_string_view for C++14.
   * Currently it's missing copy, substr and find methods.
   */
  template <class CharT, class Traits = std::char_traits<CharT>>
  class BasicStringView
  {
      static constexpr auto sso_maxsize = 24; // Including one element at the end for size

      const CharT *mData { nullptr };
      std::size_t mLength { 0 };
      std::size_t mHash { 0 };

      static constexpr std::size_t calc_hash(const CharT *data, std::size_t length) noexcept
      {
          return hashing::murmur3_32(data, length);
      }

  public:
      using traits_type = Traits;
      using value_type = CharT;
      using pointer = CharT*;
      using const_pointer = const CharT*;
      using reference = CharT&;
      using const_reference = const CharT&;
      using const_iterator = const_pointer;
      using iterator = const_iterator;
      using const_reverse_iterator = std::reverse_iterator<const_iterator>;
      using reverse_iterator = const_reverse_iterator;
      using size_type = std::size_t;
      using difference_type = std::ptrdiff_t;

      static constexpr size_type npos = size_type(-1);

      constexpr BasicStringView() = default;

      constexpr BasicStringView(const BasicStringView &) = default;

      template <class Allocator>
      BasicStringView(const std::basic_string<CharT, Traits, Allocator> &str) noexcept:
          mData(str.data()),
          mLength(str.size()),
          mHash(calc_hash(mData, mLength))
      {
      }


      constexpr BasicStringView(const CharT *s, size_type length) noexcept:
          mData(s),
          mLength(length),
          mHash(calc_hash(mData, mLength))
      {
      }

      /*
       * We're using our own strlen function instead of Traits::length, because ours is constexpr.
       */
      constexpr BasicStringView(const CharT *str) noexcept:
          mData(str),
          mLength(__h_constexpr_strlen(str)),
          mHash(calc_hash(mData, mLength))
      {
      }

      BasicStringView &operator=(const BasicStringView &) = default;

      constexpr const_iterator begin() const noexcept
      { return cbegin(); }

      constexpr const_iterator cbegin() const noexcept
      { return mData; }

      constexpr const_reverse_iterator rbegin() const noexcept
      { return crbegin(); }

      constexpr const_reverse_iterator crbegin() const noexcept
      { return const_reverse_iterator(cbegin()); }

      constexpr const_iterator end() const noexcept
      { return cend(); }

      constexpr const_iterator cend() const noexcept
      { return mData + mLength; }

      constexpr const_reverse_iterator rend() const noexcept
      { return crend(); }

      constexpr const_reverse_iterator crend() const noexcept
      { return const_reverse_iterator(cend()); }

      constexpr const_reference operator[](size_type idx) const noexcept
      { return mData[idx]; }

      constexpr const_reference at(size_type idx) const noexcept
      { return mData[idx]; }

      constexpr const_reference front() const noexcept
      { return mData[0]; }

      constexpr const_reference back() const noexcept
      { return mData[mLength - 1]; }

      constexpr const_pointer data() const noexcept
      { return mData; }

      constexpr size_type length() const noexcept
      { return mLength; }

      constexpr bool empty() const noexcept
      { return mLength == 0; }

      constexpr void remove_prefix(size_type n) noexcept
      {
          mData += n;
          mLength -= n;
      }

      constexpr void remove_suffix(size_type n) noexcept
      { mLength -= n; }

      constexpr BasicStringView substr(size_type len) const noexcept
      {
          return { mData, len };
      }

      constexpr BasicStringView substr(size_type off, size_type len) const noexcept
      {
          return { mData + off, len };
      }

      constexpr BasicStringView trim(bool (*pred)(CharT) = __h_constexpr_isspace) const
      {
          size_t left = 0, right = mLength;
          for (; left < right && pred(mData[left]); ++left);
          for (; left < right && pred(mData[right]); --right);
          return substr(left, right - left);
      }

      constexpr void swap(BasicStringView &other) noexcept
      {
          std::swap(mLength, other.mLength);
          std::swap(mData, other.mData);
          std::swap(mHash, other.mHash);
      }

      template <class Allocator = std::allocator<CharT>>
      std::basic_string<CharT, Traits, Allocator> to_string(const Allocator &a = Allocator()) const
      { return { mData, mLength, a }; }

      template <class Allocator = std::allocator<CharT>>
      operator std::basic_string<CharT, Traits, Allocator>() const
      { return { mData, mLength }; }

      constexpr int compare(const BasicStringView &other) const
      {
          return __h_constexpr_strcmp(mData, mLength, other.mData, other.mLength);
      }

      /*! Case insensitive (Latin-1 only) comparison */
      constexpr int icompare(const BasicStringView &other) const
      {
          return __h_constexpr_stricmp(mData, mLength, other.mData, other.mLength);
      }

      constexpr std::size_t hash() const noexcept
      {
          return mHash;
      }
  };

  template <class T = void>
  struct __h_identity {
      using type = T;
  };

  template <>
  struct __h_identity<void>;

  template <class T>
  using __h_id = typename __h_identity<T>::type;

#define __IMP_OPERATOR(Op)                                              \
  template <class CharT, class Traits>                                  \
  constexpr bool operator Op(BasicStringView<CharT, Traits> lhs, BasicStringView<CharT, Traits> rhs) \
  { return lhs.compare(rhs) Op 0; }                                     \
  template <class CharT, class Traits>                                  \
  constexpr bool operator Op(__h_id<BasicStringView<CharT, Traits>> lhs, BasicStringView<CharT, Traits> rhs) \
  { return lhs.compare(rhs) Op 0; }                                     \
  template <class CharT, class Traits>                                  \
  constexpr bool operator Op(BasicStringView<CharT, Traits> lhs, __h_id<BasicStringView<CharT, Traits>> rhs) \
  { return lhs.compare(rhs) Op 0; }

  __IMP_OPERATOR(==)
  __IMP_OPERATOR(!=)
  __IMP_OPERATOR(<)
  __IMP_OPERATOR(<=)
  __IMP_OPERATOR(>)
  __IMP_OPERATOR(>=)

#undef __IMP_OPERATOR

  using StringView = BasicStringView<char>;
  using WStringView = BasicStringView<wchar_t>;
  using U16StringView = BasicStringView<char16_t>;
  using U32StringView = BasicStringView<char32_t>;

  namespace string_view_literals {
#define __IMP_STRING_LITERAL(CharT)                                     \
    constexpr BasicStringView<CharT> operator"" _sv(const CharT *str, size_t len) \
    { return { str, len }; }

    __IMP_STRING_LITERAL(char)
    __IMP_STRING_LITERAL(char16_t)
    __IMP_STRING_LITERAL(char32_t)
    __IMP_STRING_LITERAL(wchar_t)

#undef __IMP_STRING_LITERAL
  }
}

namespace std {
  template <class CharT, class Traits>
  struct hash<::imp::BasicStringView<CharT, Traits>> {
      std::size_t operator()(::imp::BasicStringView<CharT, Traits> sv) const noexcept
      {
          return sv.hash();
      }
  };
}

#ifndef IMP_DONT_POLLUTE_GLOBAL_NAMESPACE
using namespace imp::string_view_literals;
#endif

#endif //__IMP_STRINGVIEW__523920528
