#pragma once

#include <functional>
#include <memory>
#include <queue>
#include <vector>

namespace csc280
{
  template <typename Data, typename Comparator = std::less<Data>>
  class SplayTree
  {
    struct Node;

  public:
#include "private/STIterator.h"

    using iterator = STIterator<Data,Comparator>;
    using const_iterator = STIterator<Data const,Comparator>;

    SplayTree() = default;

    const Data& root();
    const Data& root() const
    {
      return const_cast<SplayTree*>( this )->root();
    }

    bool empty() const noexcept { return !rootNode; }
    bool empty() noexcept { return !rootNode; }

    bool exists( const Data& data ) noexcept
    {
      return exists( data, rootNode.get() );
    }

    bool exists( const Data& data ) const noexcept
    {
      return const_cast<SplayTree*>( this )->exists( data );
    }

    iterator find( const Data& data ) noexcept
    {
      return find( data, rootNode.get() );
    }

    const_iterator find( const Data& data ) const noexcept
    {
      auto iter = const_cast<SplayTree*>( this )->find( data );
      return const_iterator{ iter.node };
    }

    std::size_t size() const noexcept { return count; }
    std::size_t size() noexcept { return count; }

    auto emplace( Data&& data ) noexcept -> iterator;

    auto remove( const Data& data ) -> iterator { return remove( data, rootNode.get() ); }

    iterator begin() noexcept { return iterator{ rootNode.get(), rootNode.get(), count }; };
    const_iterator cbegin() const noexcept { return const_iterator{ rootNode.get(), rootNode.get(), count }; };

    iterator end() noexcept { return iterator{ nullptr }; }
    const_iterator cend() const noexcept { return const_iterator{ nullptr }; }

  private:
#include "private/Node.h"

    bool exists( const Data& data, const Node* node ) noexcept;
    auto find( const Data& data, Node* node ) noexcept -> iterator;
    auto emplace( Node* parent, typename Node::Ptr node ) noexcept -> iterator;
    auto remove( const Data& data, Node* node ) -> iterator;

    void rotateLeft( Node* node );
    void rotateRight( Node* node );
    void splay( Node* node );

    Comparator comparator;
    typename Node::Ptr rootNode;
    std::size_t count = 0;
  };

#include "private/STImpl.h"
}

template <typename T, typename C>
struct STIterator : std::iterator<std::bidirectional_iterator_tag, T>
{
  STIterator() = delete;
  STIterator( const STIterator& ) = default;

  STIterator& operator++()
  {
    if ( nodes->size() - 1 > position ) node = nodes->at( ++position );
    else node = nullptr;
    return *this;
  }
  
  STIterator& operator--()
  {
    if ( position ) node = nodes->at( --position );
    else node = nullptr;
    return *this;
  }

  bool operator==( const STIterator& rhs ) { return node == rhs.node; }
  bool operator!=( const STIterator& rhs ) { return !operator==( rhs ); }

  T& operator*() { return node->data; }
  T* operator->() { return &( node->data ); }

private:
  explicit STIterator( Node* node ) : node{ node } {}

  STIterator( Node* const root, Node* node, const std::size_t count ) : node{ node }, nodes{ std::make_shared<std::vector<Node*>>() }
  {
    nodes->reserve( count );
    std::queue<Node*> queue;
    queue.push( root );

    while ( !queue.empty() )
    {
      Node* n = queue.front();

      nodes->push_back( n );
      if ( n == node ) position = nodes->size() - 1;

      if ( n->left ) queue.push( n->left.get() );
      if ( n->right ) queue.push( n->right.get() );
      queue.pop();
    }
  }

  using Nodes = std::shared_ptr<std::vector<Node*>>;

  Node* node;
  Nodes nodes;
  std::size_t position = 0;

  friend class SplayTree<Data,Comparator>;
};

template <typename Data, typename Comparator>
const Data& SplayTree<Data, Comparator>::root()
{
  if ( ! rootNode ) throw std::out_of_range( "Empty tree!" );
  return rootNode.get()->data;
}

template <typename Data, typename Comparator>
auto SplayTree<Data, Comparator>::emplace( Data&& data ) noexcept -> iterator
{
  auto node = std::make_unique<Node>( std::move( data ) );

  if ( ! rootNode )
  {
    rootNode = std::move( node );
    ++count;
    return iterator{ rootNode.get(), rootNode.get(), count };
  }

  return emplace( rootNode.get(), std::move( node ) );
}

template <typename Data, typename Comparator>
bool SplayTree<Data, Comparator>::exists( const Data& data, const Node* node ) noexcept
{
  if ( ! node ) return false;
  if ( node->data == data ) return true;

  return ( comparator( data, node->data ) ) ?
    exists( data, node->left.get() ) : exists( data, node->right.get() );
}

template <typename Data, typename Comparator>
auto SplayTree<Data, Comparator>::find( const Data& data, Node* node ) noexcept -> iterator
{
  if ( ! node ) return end();
  if ( node->data == data )
  {
    splay( node );
    return iterator{ rootNode.get(), node, count };
  }

  return ( comparator( data, node->data ) ) ?
    find( data, node->left.get() ) : find( data, node->right.get() );
}

template <typename Data, typename Comparator>
auto SplayTree<Data, Comparator>::emplace( Node* parent, typename Node::Ptr node ) noexcept -> iterator
{
  if ( parent->data == node->data )
  {
    splay( parent );
    return iterator{ rootNode.get(), parent, count };
  }

  node->parent = parent;

  Node* temp = node.get();

  if ( comparator( parent->data, node->data ) )
  {
    if ( parent->right ) return emplace( parent->right.get(), std::move( node ) );
    parent->right = std::move( node );
    splay( parent->right.get() );
  }
  else
  {
    if ( parent->left ) return emplace( parent->left.get(), std::move( node ) );
    parent->left = std::move( node );
    splay( parent->left.get() );
  }

  ++count;
  return iterator{ rootNode.get(), temp, count };
}

template <typename Data, typename Comparator>
auto SplayTree<Data, Comparator>::remove( const Data& data, Node* node ) -> iterator
{
  if ( ! node ) return end();

  if ( node->data != data )
  {
    return ( comparator( data, node->data ) ) ?
      remove( data, node->left.get() ) : remove( data, node->right.get() );
  }

  Node* parent = node->parent;

  if ( node->left && node->right )
  {
    Node* min = node->right.get();
    while ( min->left ) min = min->left.get();
    node->data = std::move( min->data );
    min->parent->left = nullptr;
  }
  else if ( ! parent )
  {
    if ( count == 1 ) rootNode = nullptr;
    else
    {
      rootNode = std::move( ( node->left ) ? node->left : node->right );
      rootNode->parent = nullptr;
    }
  }
  else if ( parent->left && parent->left.get() == node )
  {
    parent->left = std::move( ( node->left ) ? node->left : node->right );
  }
  else if ( parent->right && parent->right.get() == node )
  {
    parent->right = std::move( ( node->left ) ? node->left : node->right );
  }

  --count;
  splay( parent );
  return ( parent ) ? iterator{ rootNode.get(), parent, count } : begin();
}

template <typename Data, typename Comparator>
void SplayTree<Data, Comparator>::rotateLeft( Node* node )
{
  if ( !node ) return;
  auto right = std::move( node->right );
  auto rightPtr = right.get();

  if ( right )
  {
    node->right = std::move( right->left );
    if ( node->right ) node->right->parent = node;
    right->parent = node->parent;
  }

  if ( node->parent )
  {
    if ( node == node->parent->left.get() )
    {
      auto temp = std::move( node->parent->left );
      if ( right ) right->left = std::move( temp );
      node->parent->left = std::move( right );
    }
    else
    {
      auto temp = std::move( node->parent->right );
      if ( right ) right->left = std::move( temp );
      node->parent->right = std::move( right );
    }
  }
  else
  {
    right->left = std::move( rootNode );
    rootNode = std::move( right );
  }

  node->parent = rightPtr;
}

template <typename Data, typename Comparator>
void SplayTree<Data, Comparator>::rotateRight( Node* node )
{
  if ( !node ) return;
  auto left = std::move( node->left );
  auto leftPtr = left.get();

  if ( left )
  {
    node->left = std::move( left->right );
    if ( node->left ) node->left->parent = node;
    left->parent = node->parent;
  }

  if ( node->parent )
  {
    if ( node == node->parent->left.get()  )
    {
      auto temp = std::move( node->parent->left );
      if ( left ) left->right = std::move( temp );
      node->parent->left = std::move( left );
    }
    else
    {
      auto temp = std::move( node->parent->right );
      if ( left ) left->right = std::move( temp );
      node->parent->right = std::move( left );
    }
  }
  else
  {
    left->right = std::move( rootNode );
    rootNode = std::move( left );
  }

  node->parent = leftPtr;
}

template <typename Data, typename Comparator>
void SplayTree<Data, Comparator>::splay( Node* node )
{
  if ( !node || node == rootNode.get() ) return;

  if ( !node->parent->parent )
  {
    if ( node == node->parent->left.get() ) rotateRight( node->parent );
    else rotateLeft( node->parent );
  }
  else if ( node == node->parent->left.get() && 
    node->parent->parent->left.get() == node->parent )
  {
    rotateRight( node->parent->parent );
    rotateRight( node->parent );
  }
  else if ( node == node->parent->right.get() && 
    node->parent->parent->right.get() == node->parent )
  {
    rotateLeft( node->parent->parent );
    rotateLeft( node->parent );
  }
  else if ( node == node->parent->left.get() &&
    node->parent->parent->right.get() == node->parent )
  {
    rotateRight( node->parent );
    rotateLeft( node->parent );
  }
  else
  {
    rotateLeft( node->parent );
    rotateRight( node->parent );
  }
}

#include "catch.hpp"
#include "../main/SplayTree.h"
#include <algorithm>
#include <unordered_set>

SCENARIO( "Splay tree can be used to order words by frequency" )
{
  GIVEN( "A splay tree of strings" )
  {
    csc280::SplayTree<std::string> stree;

    WHEN( "A words with known occurrance frequency are added" )
    {
      stree.emplace( "used" );
      stree.emplace( "most" );
      stree.emplace( "words" );
      stree.emplace( "most" );
      stree.emplace( "used" );
      stree.emplace( "most" );
      stree.emplace( "used" );
      stree.emplace( "most" );

      THEN( "Root node contains most common word" )
      {
        REQUIRE( "most" == stree.root() );
      }

      AND_THEN( "Iteration over tree works" )
      {
        for ( auto iter = stree.cbegin(); iter != stree.cend(); ++iter ) {}
        for ( const auto& word : stree ) {}
      }

      AND_THEN( "Tree size does not include duplicates" )
      {
        REQUIRE( 3 == stree.size() );
      }

      AND_THEN( "Invalid words are not found in tree" )
      {
        REQUIRE_FALSE( stree.exists( "something" ) );
        auto iter = stree.find( "something" );
        REQUIRE( iter == stree.end() );
      }
    }
  }
}

SCENARIO( "Splay tree can be used to quickly retrieve most frequently occurring words from input text" )
{
  GIVEN( "Some standard text from which the most frequent words are to be extracted" )
  {
    std::string text = R"(
      A splay tree is a self - adjusting binary search tree with the additional property that recently accessed elements are quick to access again.It performs basic operations such as insertion, look - up and removal in O( log n ) amortized time.For many sequences of non - random operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown.The splay tree was invented by Daniel Sleator and Robert Tarjan in 1985.

      All normal operations on a binary search tree are combined with one basic operation, called splaying.Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree.One way to do this is to first perform a standard binary tree search for the element in question, and then use tree rotations in a specific fashion to bring the element to the top.Alternatively, a top - down algorithm can combine the search and the tree reorganization into a single phase.

      Good performance for a splay tree depends on the fact that it is self-optimizing, in that frequently accessed nodes will move nearer to the root where they can be accessed more quickly. The worst-case height—though unlikely—is O(n), with the average being O(log n). Having frequently used nodes near the root is an advantage for many practical applications (also see Locality of reference), and is particularly useful for implementing caches and garbage collection algorithms.
    )";
    std::transform( text.begin(), text.end(), text.begin(), ::tolower );

    csc280::SplayTree<std::string> stree;

    std::string word;
    for ( std::stringstream ss{ text }; ss >> word; )
    {
      stree.emplace( std::move( word ) );
    }

    THEN( "Root node contains the most frequent word" )
    {
      REQUIRE( "the" == stree.root() );
    }

    AND_THEN( "Finding data in root node leave root node unaffected" )
    {
      stree.find( "the" );
      REQUIRE( "the" == stree.root() );
    }

    AND_THEN( "Most frequently recurring words are near top of tree" )
    {
      std::unordered_set<std::string> words;
      auto iter = stree.cbegin();
      for ( auto i = 0; i < 7; ++i )
      {
        words.insert( *iter );
        std::advance( iter, 1 );
      }

      auto found = words.find( "the" );
      REQUIRE( found != words.cend() );
      found = words.find( "tree" );
      REQUIRE( found != words.cend() );
      found = words.find( "a" );
      REQUIRE( found != words.cend() );
    }

    AND_THEN( "Reading second entry in tree moves it to the root" )
    {
      auto iter = stree.cbegin();
      std::advance( iter, 1 );
      stree.find( *iter );
      REQUIRE( stree.root() == *iter );
    }
  }
}