#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <cmath> // pow
#include <set>
#include <stack> // used in get_max_elt_width()
static const char* const c_leaf_branch_special = "/\\";
/*
* A class to represent the non-whitespace squares of output using a
* grid-based tree printing scheme.
* Holds x and y coordinates and a value, which could be either the
* value held by a particular tree node or one of / or \ to improve
* readability of the printed tree.
*/
template <typename U, typename C>
class BinarySearchTree<U, C>::Tree_grid_square {
public:
template<typename T>
Tree_grid_square(int x_, int y_, T value_) : x(x_), y(y_) {
std::ostringstream oss;
oss << value_;
value = oss.str();
}
// Probe ctor
Tree_grid_square(int x_, int y_) : x(x_), y(y_) { }
/*
* A square is considered less than another if it is closer to the
* root of the tree. If two squares are at the same y coordinate,
* whichever one is farthest left is considered less.
* This ordering is solely for the purpose of storing in a sorted
* container.
*/
bool operator<(const Tree_grid_square& rhs) const {
if (y < rhs.y) {
return true;
}
if (y == rhs.y) {
return x < rhs.x;
}
return false;
}
/*
* Sends the value held at this coordinate to the given string
* stream.
*/
std::string get_value() const {
return value;
}
int get_x() const {
return x;
}
int get_y() const {
return y;
}
private:
int x;
int y;
std::string value;
};
/*
* Container to build and hold a set of Tree_grid_squares.
*/
template <typename U, typename C>
class BinarySearchTree<U, C>::Tree_grid {
public:
Tree_grid(const BinarySearchTree& tree) :
num_levels(static_cast<int>(tree.height())), leftmost_x(0),
rightmost_x(0) {
build(tree.root);
}
/*
* Convenience wrapper of set::find(). Returns a pointer to the
* Tree_grid_square in the set or 0 if not found.
*/
const Tree_grid_square* find(const Tree_grid_square& coordinate) const {
typename std::set<Tree_grid_square>::iterator it =
coordinates.find(coordinate);
if (it == coordinates.end()) {
return 0;
}
return &*it;
} // find wrapper
/*
* Returns the number of levels in the traversed tree.
*/
int get_num_levels() const {
return num_levels;
} // get_num_levels
/*
* Returns the leftmost x coordinate in the traversed tree.
*/
int get_leftmost_x() const {
return leftmost_x;
} // get_lowest_x
/*
* Returns the rightmost x coordinate in the traversed tree.
*/
int get_rightmost_x() const {
return rightmost_x;
}
private:
std::set<Tree_grid_square> coordinates;
int num_levels;
int leftmost_x;
int rightmost_x;
/*
* Given the height of a tree and the index of the current level (0
* being the root level), returns the horizontal distance (number of
* grid squares) between the current node and one of its two
* children.
*
* Note that in order for the tree to be printed elegantly, the
* horizontal distance between nodes must increase as the tree
* becomes taller.
*/
static int calculate_x_offset(int tree_height, int current_level) {
return int(std::pow(2, tree_height) / std::pow(2, current_level + 2));
}
/*
* Recursively fills the set of Node_coordinates
*/
void build(const Node* root_node, int cur_x = 0, int cur_y = 0) {
if (!root_node) {
return;
}
coordinates.insert(Tree_grid_square(cur_x, cur_y,
root_node->datum));
if (cur_x < leftmost_x) {
leftmost_x = cur_x;
}
if (cur_x > rightmost_x) {
rightmost_x = cur_x;
}
int x_offset = calculate_x_offset(num_levels, cur_y / 2);
// Slashes indicating parent-child relationships.
int branch_x_offset = (x_offset) <= 1 ? 1 : x_offset / 2;
int left_branch_x = cur_x - branch_x_offset;
int left_branch_y = cur_y + 1;
Tree_grid_square left_branch(left_branch_x, left_branch_y, "/");
int right_branch_x = cur_x + branch_x_offset;
int right_branch_y = cur_y + 1;
Tree_grid_square right_branch(right_branch_x, right_branch_y, "\\");
// Special case where leaf branches collide.
typename std::set<Tree_grid_square>::iterator collision_iter =
coordinates.find(left_branch);
if (collision_iter != coordinates.end()) {
coordinates.erase(collision_iter);
coordinates.insert( Tree_grid_square(left_branch.get_x(),
left_branch.get_y(),
c_leaf_branch_special));
} else {
coordinates.insert(left_branch);
}
coordinates.insert(right_branch);
build(root_node->left, cur_x - x_offset, cur_y + 2);
build(root_node->right, cur_x + x_offset, cur_y + 2);
} // build
};
//--------------------------------------------------------------------
/*
* Returns an (actually) human-readable string representation of the
* tree
*/
template <typename U, typename C>
std::string BinarySearchTree<U, C>::to_string() const {
if (!root) {
return "( )";
}
int node_width = get_max_elt_width();
Tree_grid coordinates(*this);
std::ostringstream oss;
std::string padding(size_t(node_width), ' ');
int farthest_left = coordinates.get_leftmost_x() - node_width;
int farthest_right = coordinates.get_rightmost_x() + node_width;
// Two printed lines per tree level: one for the values, one for the
// slash characters (branches).
for (int y = 0; y <= coordinates.get_num_levels() * 2; ++y) {
oss << "\n";
for (int x = farthest_left; x <= farthest_right; ++x) {
const Tree_grid_square* tgs_ptr =
coordinates.find( Tree_grid_square(x, y));
if (tgs_ptr) {
// TODO width field in square?
if (tgs_ptr->get_value() == "/") {
oss << std::right;
oss << std::setw(node_width);
oss << tgs_ptr->get_value();
} else if (tgs_ptr->get_value() == "\\") {
oss << std::left;
oss << std::setw(node_width);
oss << tgs_ptr->get_value();
} else if (tgs_ptr->get_value() == c_leaf_branch_special) {
oss << '\\' << std::string(size_t(node_width - 2), ' ') << '/';
} else {
oss << std::setw(node_width);
oss << tgs_ptr->get_value();
}
} else {
oss << padding;
}
} // for x
// oss << "\n";
} // for y
return oss.str();
} // to_string
static const int c_min_elt_width = 2;
/*
* Returns the width of the widest elt in this tree.
*/
template <typename U, typename C>
int BinarySearchTree<U, C>::get_max_elt_width() const {
int current_max = c_min_elt_width;
std::stack<Node*> nodes;
nodes.push(root);
while (!nodes.empty()) {
Node* current = nodes.top();
nodes.pop();
if (!current) {
continue;
}
std::ostringstream oss;
oss << current->datum;
int width = int(oss.str().length());
if (width > current_max) {
current_max = width;
}
nodes.push(current->left);
nodes.push(current->right);
} // while
return current_max;
} // get_max_elt_width