/* tree.cpp - Matt Mahoney, mmahoney@cs.fit.edu

This program reads a file (specified on the command line, or from
standard input if no file name is given) and for each word, prints
the first 10 line numbers on which it is found at least once.  A word
is any sequence of letters (a-z).  Upper and lower case are equivalent.
The index is printed to standard output with the words in lower
case, listed alphabetically, one word per line, followed by a list
of up to 10 line numbers (separated by spaces), and ... if the word
appears on more than 10 lines.

This program behaves identical to index.cpp (homework 4), but uses
a Tree<K,V> instead of a map<K,V> for the index.  A Tree is a binary
tree with an index operator like a map, and a method transform(f) which
calls the function f on each key-value pair in order.

To compile: gxx tree.cpp     (g++ 2.95.2)
Or:         bcc32 tree.cpp   (Borland 5.5.1)
*/

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


// A Tree<K,V> associates values of type V with keys of type K like
// a map<K,V>.  The index operator works identically, but the only other
// method is transform(f) which calls a function f(const K&, V&) on each
// key-value pair in order of the keys (ordered by < ).  Trees may not
// be copied or assigned.  A tree is implemented as a binary tree sorted
// by key.

template <class K, class V>
class Tree {
private:
	struct Node {  // Node in a binary tree sorted by key
		K key;  // Data visible to user
		V value;
		Node *left, *right;  // Child pointers (<key, >key)
		Node(const K& k): key(k), value(V()), left(0), right(0) {}
	};
	Node* root;  // Root of the tree
	Tree<K,V>& operator=(const Tree<K,V>&);  // Assignment not allowed
	Tree(const Tree<K,V>&);  // Copy not allowed
	void transform(void f(const K&, V&), Node* branch);
    // Recursively call f on a branch of the tree
	void del(Node* branch);  // Recursively delete branch and it's children
	public:
		Tree(): root(0) {}  // Empty tree
		void transform(void f(const K&, V&)) {transform(f, root);}
		// call f(k,v) on each key k and value v in the Tree, lowest key first
		V& operator[](const K& k);  // Return value with key k, create if needed
		~Tree() {del(root);}  // Delete memory
};

// t[k] returns a value of type V associated with the unique key K in Tree t.
// If no value is associated, a new one is created.  The value may be
// assigned to (like in a map).
template<class K, class V>
V& Tree<K,V>::operator[](const K& k) {
	Node** p=&root;  // Pointer to pointer to current Node being searched
	while (*p) {  // Descend tree searching for k
		if (k < (*p)->key)
			p=&((*p)->left);
		else if ((*p)->key < k)
			p=&((*p)->right);
		else
			return (*p)->value;  // found
	}
	*p=new Node(k);  // not found, create
	return (*p)->value;
}

// Private method to call f(k,v) on branch and its chidren from left to right
template<class K, class V>
void Tree<K,V>::transform(void f(const K&, V&), Node* branch) {
	if (branch) {
		transform(f, branch->left);
		f(branch->key, branch->value);
		transform(f, branch->right);
	}
}

// Private method to recursively delete a branch and its children
template<class K, class V>
void Tree<K,V>::del(Node* branch) {
	if (branch) {
		del(branch->left);
		del(branch->right);
		delete branch;
	}
}

typedef Tree<string, vector<int> > Index;  // Maps words to line numbers

// make_index(in, m) reads from the open istream in until EOF and
// constructs an index into the initialy empty Index m.
// Each entry is a lowercase word mapped to a list of up to 11 unique line
// numbers in ascending order.  (Identical to homework 4).
void make_index(istream& in, Index& m) {
	string word;  // Current word
	char c;       // Current char
	int line=1;   // Line number
	while (in.get(c)) {
		if (isalpha(c))
			word+=tolower(c);
		else if (word.size()>0) {  // End of word?  Store line number.
			vector<int>& v=m[word];
			if (v.size()<11 && (v.size()==0 || v.back()!=line))
				v.push_back(line);
			word="";
		}
		if (c=='\n')
			++line;
	}
}

// Print string s and first 10 elements of vector v (with ... if > 10)
// Replaces the print code in main() from homework 4.
void print(const string& s, vector<int>& v) {
	cout << s;
	for (int i=0; i<int(v.size()) && i<10; ++i)
		cout << " " << v[i];
	if (int(v.size()) >= 10)
		cout << "...";
	cout << "\n";
}

// Identical to homework 4 until the call to m.transform()
int main(int argc, char** argv) {
	
	// Open argv[1] or use cin if absent, and pass to make_index()
	Index m;  // Maps words to a vector of up to 11 unique line numbers
	if (argc>1) {
		ifstream in(argv[1]);
		if (!in) {
			cerr << "File not found: " << argv[1] << endl;
			return 1;
		}
		make_index(in, m);
	}
	else
		make_index(cin, m);
	m.transform(print);  // Print the index
	return 0;
}