#ifndef PIAZZA_H
#define PIAZZA_H
#include <string>
#include <iostream>
#include <sstream>
#include <vector>
// You may add additional headers here
#include <map>
#include <set>


// A single post that can form a linked list
struct Post {
  Post(const std::string& val, Post* nxt) : text(val), next(nxt)
  {}
  
  std::string text;
  Post* next;
  // You may add other data members here (recall they are public)
  std::set<std::string> termIndex;
};

// A linked list of posts with limited capabilities
// You MAY NOT ALTER THIS CLASS. IT IS COMPLETE.
class PostList {
 public:
  PostList() { size = 0; head = NULL; }
  ~PostList() {
    while(head) { Post* cursor = head->next; delete head; head = cursor; }
  }
  void push_front(const std::string& val){
    head = new Post(val, head);
    size++;
  }
 protected:
  size_t size;
  Post* head;
};

//
// You may choose the kind of inheritance and/or data members of this class
// as well as adding private helper functions if you so choose.

class Piazza : private PostList /* or protected */
               // we don't want clients to be able to call push_front()
{
 public:
  Piazza();  // Constructor
  ~Piazza(); // Destructor - Clean up any necessary memory

  /// Adds a new post with the given string and performs any preprocessing
  /// necessary to support case-sensitive searches for individual words.
  ///  @param[in] data - text of the post to add
  ///  @param[in] pinned - true if this post should be pinned
  /// Assuming n >> t, runs in O(log(n)) where
  /// n is the number of existing posts and t is the average words per post 
  void addPost(const std::string& data, bool pinned);

  /// Returns the number of posts that contains the given term in their index.
  /// To make your life easier, you may perform case-sensitive searches
  ///  so that no extra processing is needed.
  /// Runs in O(n*log(t)) where n is the number of posts and t is the number
  ///  words in each post.
  size_t numMatches(const std::string& term);
  
  /// Returns the text of the i-th most recent post (includes all posts,
  /// pinned or not).  Indexing is 0-based, so i=0 indicates the most
  /// recent post. If i is an invalid index, throw std::out_of_range.
  /// Runs in O(i) where is is the input argument.
  const std::string& getIthMostRecentPost(size_t i);
  
  /// Returns the text of the i-th most recent pinned post (and does
  /// not include non-pinned posts. Indexing is 0-based, so i=0
  /// indicates the most recent pinned post. 
  /// If i is an invalid index, throw std::out_of_range.
  /// Runs in O(i) where is is the input argument.
  const std::string& getIthMostRecentPinnedPost(size_t i);

 private:
  // Add appropriate data members
  // You may use `std::vector`, `std::set`, and `std::map`.
  // You may not use `std::list`. If you want a linked-list you will
  // need to use code provided or write code to manage it yourelf.
  
  Post* pinnedHead;
  std::map<Post*, Post*> pinnedMap;

};

#endif

#include "piazza.h"
using namespace std;

// Helper function to convert a string of text to individual words
std::vector<std::string> makeWords(const std::string& s)
{
  std::vector<std::string> words;
  std::stringstream ss(s);
  std::string temp;
  while(ss >> temp){
    words.push_back(temp);
  }
  return words;
}


// Complete the constructor below
Piazza::Piazza() {
  pinned_head = NULL;
}

// Complete the destructor below as needed
Piazza::~Piazza()
{ }



// Runs in O(log(n)), assuming n >> t where n is the number  
// of existing posts and t is the number of words in the post.
void Piazza::addPost(const std::string& data, bool pinned)
{
  // You may change this line and add the remainder of your
  // implementation
  std::vector<std::string> words = makeWords(data);

  this->push_front(data);
  if(pinned){
    this->pinnedMap.insert(std::make_pair(head, pinned_head));
    this->pinned_head = this->head;
  }

  for(unsigned int i = 0; i < words.size(); i++) {
    head->termIndex.insert(words[i]);
  }
}

// Complete the code below.
// Remember this must run in O(n*log(t)) where n is the number
// of posts and t is the number of words per post
size_t Piazza::numMatches(const std::string& term)
{
  Post* cursor = head;
  size_t val = 0;
  while(cursor){
    if(cursor->termIndex.find(term) != cursor->termIndex.end()){
      val++;
    }
    cursor = cursor->next;
  }
  return val;
}

// Complete the code below.
// Must run in O(i)
const std::string& Piazza::getIthMostRecentPost(size_t i)
{
  if(i >= this->size){
    throw std::out_of_range("bad location");
  }
  Post* cursor = head;
  while(i-- != 0U) cursor = cursor->next;
  return cursor->text;
}

// Complete the code below.
// Must run in O(i)
const std::string& Piazza::getIthMostRecentPinnedPost(size_t i)
{
  if(i >= this->pinnedMap.size()){
    throw std::out_of_range("bad location");
  }
  Post* cursor = pinned_head;
  while(i-- != 0U) cursor = pinnedMap[cursor];
  return cursor->text;

}