Projects/BSTPrinter.h at main · hannahCapone/Projects · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#ifndef __BSTPRINTER_H__
#define __BSTPRINTER_H__

#include "BSTMap.h"
#include <cmath>
#include <cstddef>
#include <ostream>
#include <string>
#include <vector>

using namespace std;

namespace ds {

class BSTPrinter {
public:
  /**
   * Print the BST level by level, from top to bottom and left to right.
   */
  template <typename Key, typename Value>
  static void print(const BSTMap<Key, Value> &bst, ostream &os) {
    vector<vector<string>> lines;
    vector<BSTMapNode<Key, Value> *> level;
    vector<BSTMapNode<Key, Value> *> next;
    level.push_back(bst.root);
    int nn = 1;
    size_t widest = 0;

    while (nn != 0) {
      vector<string> line;
      nn = 0;

      for (BSTMapNode<Key, Value> *n : level) {
        if (n == nullptr) {
          line.push_back("");

          next.push_back(nullptr);
          next.push_back(nullptr);
        } else {
          std::stringstream ss;
          ss << n->key << ":" << n->value;
          string aa = ss.str();
          line.push_back(aa);
          if (aa.length() > widest)
            widest = aa.length();

          next.push_back(n->left);
          next.push_back(n->right);

          if (n->left != nullptr)
            nn++;
          if (n->right != nullptr)
            nn++;
        }
      }

      if (widest % 2 == 1)
        widest++;

      lines.push_back(line);

      vector<BSTMapNode<Key, Value> *> tmp = level;
      level = next;
      next = tmp;
      next.clear();
    }

    int perpiece = lines.at(lines.size() - 1).size() * (widest + 4);
    for (size_t i = 0; i < lines.size(); i++) {
      vector<string> line = lines.at(i);
      int hpw = (int)floor(perpiece / 2.f) - 1;

      if (i > 0) {
        for (size_t j = 0; j < line.size(); j++) {
          // split node
          char c = ' ';
          if (j % 2 == 1) {
            if (line.at(j - 1) != "") {
              c = '+';
            } else if (j < line.size() && line.at(j) != "") {
              c = '+';
            }
          }
          os << c;

          // lines and spaces
          if (line.at(j) == "") {
            for (int k = 0; k < perpiece - 1; k++) {
              os << " ";
            }
          } else {
            for (int k = 0; k < hpw; k++) {
              os << (j % 2 == 0 ? " " : "─");
            }
            os << (j % 2 == 0 ? "┌" : "┐");
            for (int k = 0; k < hpw; k++) {
              os << (j % 2 == 0 ? "─" : " ");
            }
          }
        }
        // os << "\\n\"\n";
        os << "\n";
      }

      for (size_t j = 0; j < line.size(); j++) {
        string f = line.at(j);
        int gap1 = (int)ceil(perpiece / 2.f - f.length() / 2.f);
        int gap2 = (int)floor(perpiece / 2.f - f.length() / 2.f);
        for (int k = 0; k < gap1; k++) {
          os << " ";
        }
        os << f;
        for (int k = 0; k < gap2; k++) {
          os << " ";
        }
      }
      // os << "\\n\"\n";
      os << "\n";

      perpiece /= 2;
    }
  }
};

} // namespace ds

#endif // __BSTPRINTER_H__