/* tree2.cpp - Spring 2003 CSE2050 Homework 6 part 2
   Matt Mahoney, mmahoney@cs.fit.edu

This program takes a file name and a word as arguments, then prints
the number of times the word occurs in the file.  Then it prints the
number of different words and number of word instances.

For example:

  more < test
  This is a test.  This is another test.
  This and this and this too.

  tree2 test THIS
  this occurs 4 times.
  test has 14 instances of 7 words.

Input is not case sensitive.  A word is considered to be any sequence
of letters (a-z).  Thus, "IT'S" and "it s" are equivalent (both are 2
words).

This code is like part 1 but uses a binary tree instead of a map.
The tree has the following properties:

  Tree<K,V> t;  // Like a map<K,V>
  t[k] = v;     // Associates value v (type V) with unique key k (type K)
  t[k];         // Returns associated value v, or V() if no value associated
  t.size()      // Number of different keys stored or referenced
*/

#include <iostream>
#include <fstream>
#include <cctype>
#include <string>
#include <vector>
#include <utility>
using namespace std;

// Binary tree, like a map<K,V> with [] and size() only
template <class K, class V> class Tree {
private:
  struct Node {  // Node of a sorted binary tree
    pair<K,V> data;  // key, value
    Node *left, *right;  // Children
    Node(const K& k): data(k, V()), left(0), right(0) {}
  } *root;
  V& get(const K& key, Node*&);  // find/insert key in subtree, return value
  int size(Node*) const;  // Size of subtree
  void destroy(Node*);  // Delete subtree
  Tree(const Tree&);  // No copy constructor
  Tree& operator=(const Tree&);  // No assignment
public:
  Tree(): root(0) {}
  V& operator[](const K& k) {return get(k, root);}
  int size() const {return size(root);}
  ~Tree() {}
};

// Size of subtree at p
template<class K, class V>
int Tree<K,V>::size(Node* p) const {
  return p ? 1+size(p->left)+size(p->right) : 0;
}

// Find or insert key k at subtree rooted at p, return associated value
template<class K, class V>
V& Tree<K,V>::get(const K& k, Node* &p) {
  if (!p)
    p=new Node(k);
  if (p->data.first < k)
    return get(k, p->right);
  else if (k < p->data.first)
    return get(k, p->left);
  else
    return p->data.second;
}

// Delete subtree rooted at p
template<class K, class V>
void Tree<K,V>::destroy(Node* p) {
  if (p) {
    destroy(p->left);
    destroy(p->right);
    delete p;
  }
}

// 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: tree2 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
  int size=count.size();
  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]);
    cout << word << " occurs " << count[word] << " times\n";
  }

  // Print overall statistics
  cout << argv[1] << " has " << wordcount << " instances of "
       << size << " words\n";
  return 0;
}