#include <cctype>
#include <cmath>
#include <iostream>
#include <fstream>
#include <stdexcept>
#include <string>

class Node
{
public:
	/* constructors */
	Node();
	Node(char newChar, unsigned short newDepth);

	/* accessors */
	char getChar() const {return character;}
	unsigned short getDepth() const {return depth;}
	bool isRoot() const {return (character == '\0');}

	/* node accessors */
	Node *getLeft() const {return left;}
	Node *getCenter() const {return center;}
	Node *getRight() const {return right;}

	/* mutators */
	bool setChar(char newChar);
	bool setDepth(unsigned short newDepth);

	/* node mutators */
	void setLeft(Node *newLeft) {left = newLeft;}
	void setCenter(Node *newCenter) {center = newCenter;}
	void setRight(Node *newRight) {right = newRight;}

	const static unsigned short MAX_DEPTH = 7;
private:
	char character; /* '\0' if root node */
	unsigned short depth;
	Node *left, *center, *right;
};

class Tree
{
public:
	/* constructors */
	Tree();
	Tree(unsigned int newNumber);
	~Tree();

	/* maintenance operations */
	void clear();
	void expand();
	void expand(Node *start);
	bool isEmpty() const;
	void print(std::ostream &output) const;
	void print(Node *start, std::string word, std::ostream &output) const;

	/* accessor/mutator for the phone number */
	unsigned int getNumber() const {return phoneNumber;}
	bool setNumber(unsigned int newNumber);

private:
	enum directions {LEFT, CENTER, RIGHT};
	char translate(unsigned short number, unsigned short direction);
	unsigned short digit(unsigned short index);
	void remove(Node *start);

	unsigned int phoneNumber;
	Node *root;
};

int main(int argc, char **argv)
{
	unsigned int currNumber = 2222222; /* smallest number possible */
	unsigned int highestNumber = pow(10.0, Node::MAX_DEPTH);
	std::ofstream fd;
	Tree t;

	/* check for operator error */
	if (argc < 2)
	{
		std::cerr << "Usage: " << argv[0] << " <output file" << std::endl;
		return 1;
	}

	/* open the output file */
	fd.open(argv[1]);
	if (!fd.good())
	{
		std::cerr << "Unable to open output file." << std::endl;
		return 1;
	}

	/* try every possible number */
	while (currNumber < highestNumber)
	{
		/* if this is a valid number, print it */
		if (t.setNumber(currNumber))
		{
			t.clear();
			t.expand();
			t.print(fd);
		}
		currNumber++;
	}

	fd.close();
	return 0;
}

/* create a root node */
Node::Node()
{
	character = '\0';
	depth = 0;
	left = center = right = NULL;
}

/* create a node with full information */
Node::Node(char newChar, unsigned short newDepth)
{
	bool ok;

	character = '\0';
	depth = 0;
	left = center = right = NULL;

	ok = setChar(newChar) && setDepth(newDepth);
	if (!ok)
		throw (std::invalid_argument("Invalid Node Initialisation"));
}

/* change the character on the node */
bool Node::setChar(char newChar)
{
	/* convert uppercase to lowercase */
	if (isupper(newChar))
		newChar = tolower(newChar);
	
	/* now assign it */
	if ((islower(newChar)) && (newChar != 'q') && (newChar != 'z'))
	{
		character = newChar;
		return true;
	}
	else
		return false;
}

/* change the depth of the node */
bool Node::setDepth(unsigned short newDepth)
{
	if (newDepth <= MAX_DEPTH)
	{
		depth = newDepth;
		return true;
	}
	else
		return false;
}

/* create an empty tree */
Tree::Tree()
{
	phoneNumber = 0;
	root = new Node();
}

/* create a root node with a phone number */
Tree::Tree(unsigned int newNumber)
{
	if (!setNumber(newNumber))
		throw (std::invalid_argument("Invalid Node Initialisation"));
	root = new Node();
}

/* chop down a tree */
Tree::~Tree()
{
	remove(root);
	root = NULL;
	phoneNumber = 0;
}

/* change the phone number of the node */
bool Tree::setNumber(unsigned int newNumber)
{
	unsigned short i;
	unsigned int thisDigit;

	/* too short */
	if (newNumber < (2 * pow(10.0, (Node::MAX_DEPTH - 1))))
		return false;
	/* too long */
	else if (newNumber >= (pow(10.0, Node::MAX_DEPTH)))
		return false;

	/* check that each digit is in [2, 9] */
	for (i = 0; i < Node::MAX_DEPTH; i++)
	{
		thisDigit = (newNumber % (unsigned int)(pow(10.0, (i + 1)))) / (pow(10.0, i));
		if (thisDigit == 0 || thisDigit == 1)
			return false;
	}

	/* we passed the test :) */
	phoneNumber = newNumber;
	return true;
}

/* prunes everything except the root from the tree */
void Tree::clear()
{
	remove(root);
	root = new Node();
}

/* returns true if the tree is empty, false otherwise */
bool Tree::isEmpty() const
{
	return ((root == NULL) ||
		((root->getLeft() == NULL) && (root->getCenter() == NULL) && (root->getRight() == NULL)));
}

/* return the index-th digit of the phone number as an int */
unsigned short Tree::digit(unsigned short index)
{
	unsigned short thisDigit;
       
	if (index != Node::MAX_DEPTH)
		index = Node::MAX_DEPTH - (index + 1);
	thisDigit = (phoneNumber % (unsigned int)(pow(10.0, (index + 1)))) / (pow(10.0, index));
	return thisDigit;
}

/* starts the expansion process */
void Tree::expand()
{
	if (!isEmpty())
		clear();
	expand(root);
}

/* expands the tree to the full possibilites of words */
void Tree::expand(Node *start)
{
	unsigned short currDepth = start->getDepth(), thisDigit = digit(currDepth), nextDepth = currDepth + 1;
	Node *newNode;

	if (currDepth < Node::MAX_DEPTH)
	{
		/* make the nodes */
		newNode = new Node(translate(thisDigit, LEFT), nextDepth);
		start->setLeft(newNode);
		newNode = new Node(translate(thisDigit, CENTER), nextDepth);
		start->setCenter(newNode);
		newNode = new Node(translate(thisDigit, RIGHT), nextDepth);
		start->setRight(newNode);

		/* now expand those nodes */
		expand(start->getLeft());
		expand(start->getCenter());
		expand(start->getRight());
	}
}

/* starts the printing process */
void Tree::print(std::ostream &output) const
{
	std::string empty;
	if (!isEmpty())
		print(root, empty, output);
}

/* recursively prints the entire tree */
void Tree::print(Node *start, std::string word, std::ostream &output) const
{
	/* append the character to the word */
	if (start->getDepth() != 0)
		word.append(1, start->getChar());

	/* if we're at the end, print */
	if (start->getDepth() == Node::MAX_DEPTH)
		output << phoneNumber << '\t' << word << std::endl;
	/* recursively build the word */
	else
	{
		if (start->getLeft())
			print(start->getLeft(), word, output);
		if (start->getCenter())
			print(start->getCenter(), word, output);
		if (start->getRight())
			print(start->getRight(), word, output);
	}
}

/* deletes the start node and all its descendants */
void Tree::remove(Node *start)
{
	if (start)
	{
		remove(start->getLeft());
		remove(start->getCenter());
		remove(start->getRight());
		delete start;
		start = NULL;
	}
}

/* translates a number & branching direction to a character */
char Tree::translate(unsigned short number, unsigned short direction)
{
	char newChar;

	/* in general, c(n, d) = 3 * (n - 2) + d + 97 */
	newChar = (3 * (number - 2)) + direction + 'a';

	/* skip over q for higher numbers */
	if ((number == 7) && ((direction == CENTER) || (direction == RIGHT)))
		newChar++;
	else if ((number == 8) || (number == 9))
		newChar++;

	return newChar;
}