/**
 * Nathan Moreau  nmoreau@fit.edu
 * gcc version 2.95.3 20010315 (release)
 * Tested with SunOS 5.8 on olin.fit.edu with g++
 *
 * ANALYSIS:
 * Chronicle will read a text file (named in the first command line argument) 
 * and print a frequency histogram for the words in that file. The output 
 * will be in the form: 
 *
 *    m words occur n times: word1 word2 ... wordm
 *
 *  more < test
 * This is a test.  This is another test.
 *   This and this and this too.
 * 
 *   ./a.out test
 *   1 word occurs 5 times: this
 *   3 words occur 2 times: is test and
 *   3 words occur 1 time: a another too
 *   test has 14 instances of 7 words.
 * If m > 5, then print any 5 words followed by "...", 
 */ 

#include <iterator>
#include <iostream>
#include <map>
#include <vector>
#include <fstream>
#include <string>
using namespace std; 

/**
 * A class tree that is a binary search tree.
 */
template <class K, class V>
class Tree {
private:
  struct Node {   //Internal node structure.
    pair<const K,V> data;
    Node *left, *right, *parent;  
    Node(const K& k): data(k, V()), left(0), right(0), parent(0) {}
  };
  
  Node* root;    
  int treeSize;              
  Tree<const K,V>& operator= (const Tree<const K,V>&); // Assignment 
                                                       // not allowed
  Tree(const Tree<K,V>&);                              // Copy not allowed
  void del(Node* branchPtr);
  
public:
  Tree(): root(0), treeSize(0) {}    //Default Constructor.
  V& operator[](const K& k);         //Bracket Operator. 
  int size() { return treeSize; }    //Find the size of the tree.
  ~Tree() {del(root);}               //Destroy tree.    
  
  /**
   * An iterator class for the tree class.
   */
   class iterator {
      friend class Tree<K,V>;
      private:
         Node* ptr;                    // Pointer to current node
         iterator(Node* p): ptr(p) {}  // Used by begin     
      public: 
      
         //Standard library requirements
         typedef std::forward_iterator_tag iterator_category;
         typedef pair<const K, V> value_type;      
         typedef ptrdiff_t difference_type;  
         typedef pair<const K, V>* pointer;
         typedef pair<const K, V>& reference;
         
         iterator(): ptr(0) {}
      
         //Standard iterator comp and access operations.
         pointer operator->() {return &ptr->data;}
         reference operator*() const {return ptr->data;}
         bool operator!=(const iterator &i) const {return ptr != i.ptr;}
         bool operator==(const iterator &i) const {return ptr == i.ptr;}
         
         /**
          *  The ++ operator (post) returns the next node in the tree.
          */        
         iterator operator++(int dummy) {
            iterator iterNext=*this;
            ++(*this);
            return iterNext;
         }
         
         /**
          * The ++ operator (pre) returns the next node in the tree.
          */         
         iterator& operator++() {
            if (!ptr) {
               return *this;
            }
            if (ptr->right) {
               ptr = ptr->right;
               while (ptr->left) {
                  ptr = ptr->left;
               }
               return *this;
            } else {
            Node *current = ptr;
               while (ptr->parent) {
                  ptr = ptr->parent;
                  if (ptr->data.first > current->data.first) {
                     return *this;
                  }
               }
               ptr = current->right;
               return *this;
            }
         }
   };
   
   /**
    *  The begin function returns a pointer to the left most node in the tree.
    */
   iterator begin() const {
      Node *p= root;
      while(p->left) {
         p= p->left;
      }
      return iterator(p);
   }
  iterator end () const { return iterator (); }

  /**
   *  The find function.
   */
  iterator find(const K& k) const {
    Node *p=root;   // Pointer to pointer to the current node being inspected.
    while (p) {     // Descend tree searching for k
      if (k < p->data.first)
        p= p->left;
      else if (k > p->data.first)
        p=p->right;
      else
        return iterator(p);  
    }
    return iterator();
  }
};

/**
  * del allows each branch of the tree to be deleted and the memory to be
  * returned to the heap.
  */
template<class K, class V>
void Tree<K,V>::del (Node* branchPtr) {

  //Check to see if the branchPtr exists.
  if (branchPtr) {
    del(branchPtr->left);    //Call the del function on the left branch
    del(branchPtr->right);   //Call the del function on the right branch
    delete branchPtr;
  }
}

/**
 * The [] operator for the class tree.  This returns a reference to 
 * the value that is associated with the passed key: K.
 */
template<class K, class V>
V& Tree<K,V>::operator[] (const K& k) {
  Node** p= &root;  
  Node*  ptrParent= 0;
  
  while (*p) {  // Descend tree searching for k
    if (k < (*p)->data.first) {
       ptrParent= *p;   // Save pointer for parent
       p= &((*p)->left);
    }
    else {
       if ((*p)->data.first < k) {
         ptrParent= *p;   // Save pointer for parent
         p= &((*p)->right);
       }
       else
          return (*p)->data.second; 
    } 
  }
  
  //If the Node does not exist then create it and return the proper value.
  *p= new Node(k);  
  ++treeSize;            //Save the size of the tree
  (**p).parent = ptrParent; //Assign the node a parent
  return (*p)->data.second;
} 

//Structure to hold histogram vector.
struct HistInfo {
  vector<string> words;  // maximum of 5
  int m;  // actual number of words
  HistInfo(): m(0) {}
};

/****************************************************************************/
/*********************Mahoney's Code Below this line*************************/
/****************************************************************************/

// tree2 filename word -- Print number of times word occurs in file
int main(int argc, char** argv) {

  // Open input file, fail if not specified or not found
  if (argc < 2) {
    cerr << "Usage: tree1 file [word]\n";
    return 1;
  }
  ifstream f(argv[1]);
  if (!f) {
    cerr << "File not found: " << argv[1] << endl;
    return 1;
  }

  // Count words
  Tree<string, int> count;  // count[s] is number of occurrences of word s
  int wordcount = 0;  // Number of word instances
  string s;  // Current input word
  char c;
  while (f.get(c)) {
    if (isalpha(c))
      s+=char(tolower(c));
    else if (s != "") {
      ++wordcount;
      ++count[s];
      s="";
    }
  }

  // If there is a word, report its count
  Tree<string, int>::iterator p;
  if (argc>2) {
    string word = argv[2];
    for (int i=0; i<int(word.size()); ++i)  // Convert word to lower case
      word[i] = tolower(word[i]);
    p=count.find(word);
    if (p == count.end())
      cout << word << " occurs 0 times\n";
    else
      cout << word << " occurs " << p->second << " times\n";
  }

  // Otherwise, print a histogram: m words occur n times... by decreasing n
  else {
    map<int, vector<string> > hist;  // hist[-n] is words occurring n times
    for (p=count.begin(); !(p==count.end()); ++p)
      hist[-(*p).second].push_back(p->first);
    for (map<int, vector<string> >::iterator q=hist.begin();
        q!=hist.end(); q++) {
      const int m = (*q).second.size();
      const int n = -q->first;
      if (m==1)
        cout << "1 word occurs ";
      else
        cout << m << " words occur ";
      if (n==1)
        cout << "1 time:";
      else
        cout << n << " times:";
      for (int i=0; i<5 && i<m; ++i)
        cout << " " << q->second[i];
      if (m > 5)
        cout << " ...";
      cout << endl;
    }
  }

  // Print overall statistics
  cout << argv[1] << " has " << wordcount << " instances of "
       << int(count.size()) << " words\n";
  return 0;
}
/*
http://www.chris.com/ascii/
                ._,.
           "..-..pf.
          -L   ..#'
        .+_L  ."]#
        ,'j' .+.j`                 -'.__..,.,p.
       _~ #..<..0.                 .J-.``..._f.
      .7..#_.. _f.                .....-..,`4'
      ;` ,#j.  T'      ..         ..J....,'.j`
     .` .."^.,-0.,,,,yMMMMM,.    ,-.J...+`.j@
    .'.`...' .yMMMMM0M@^=`""g.. .'..J..".'.jH
    j' .'1`  q'^)@@#"^".`"='BNg_...,]_)'...0-
   .T ...I. j"    .'..+,_.'3#MMM0MggCBf....F.
   j/.+'.{..+       `^~'-^~~""""'"""?'"``'1`
   .... .y.}                  `.._-:`_...jf
   g-.  .Lg'                 ..,..'-....,'.
  .'.   .Y^                  .....',].._f
  ......-f.                 .-,,.,.-:--&`
                            .`...'..`_J`
                            .~......'#'
  Ray Brunner               '..,,.,_]`     Sienar Fleet Systems' TIE/In
                            .L..`..``.     Space Superiority Starfighter (2)
*/