БлогNot. Два маленьких класса для дерева строк на стандартных алгоритмах

Два маленьких класса для дерева строк на стандартных алгоритмах

Небольшой код на представление деревьев в C++ с помощью стандартной библиотеки алгоритмов.

Класс nestTree выводит форму представления с вложенностью узлов, показанной строчным отступом, а экземпляр класса indentTree, который может быть создан из nestTree, делает это с помощью нумерации уровней вложенности узлов. Объект класса indentTree можно преобразовать обратно к nestTree с помощью метода indentToNest, также определён оператор == для сравнения объектов nestTree.

Ниже показаны консольный листинг на C++, выполненный в актуальной сборке Visual Studio 2019 и результаты вывода программы.

#include <iostream>
#include <iomanip>
#include <vector>
#include <list>
#include <string>
#include <utility>

class nestTree;
bool operator == (const nestTree&, const nestTree&);

class nestTree {
public:
 explicit nestTree(const std::string& name) : name_(name) {}
 nestTree& add_child(const std::string& name) {
  children_.emplace_back(name);
  return children_.back();
 }
 void print(std::ostream& out) const {
  print(out, 0);
 }
 const std::string& name() const { return name_; }
 const std::list<nestTree>& children() const { return children_; }
 bool equals(const nestTree& n) const {
  return name_ == n.name_ && children_ == n.children_;
 }
private:
 void print (std::ostream& out, int level) const {
  std::string indent(level * 4, ' ');
  out << indent << name_ << std::endl;
  for (const nestTree& child : children_)
   child.print(out, level + 1);
 }
 std::string name_;
 std::list <nestTree> children_;
};

bool operator == (const nestTree& a, const nestTree& b) { return a.equals(b); }

class indentTree {
public:
 explicit indentTree (const nestTree& n) {
  items_.emplace_back(0, n.name());
  indentFromNest(n, 0);
 }
 void print (std::ostream& out) const {
  for (const auto& item : items_)
   std::cout << item.first << ' ' << item.second << std::endl;
 }
 nestTree indentToNest() const {
  nestTree n (items_[0].second);
  indentToNestProc(n, 1, 0);
  return n;
 }
private:
 void indentFromNest (const nestTree& n, int level) {
  for (const nestTree& child : n.children()) {
   items_.emplace_back(level + 1, child.name());
   indentFromNest (child, level + 1);
  }
 }
 size_t indentToNestProc (nestTree& n, size_t pos, int level) const {
  while (pos < items_.size() && items_[pos].first == level + 1) {
   nestTree& child = n.add_child(items_[pos].second);
   pos = indentToNestProc (child, pos + 1, level + 1);
  }
  return pos;
 }
 std::vector<std::pair<int, std::string>> items_;
};

int main() {
 nestTree n ("My tree");
 auto& child1 = n.add_child("Node 1");
 auto& child2 = n.add_child("Node 2");
 child1.add_child("Node 1-1");
 child1.add_child("Node 1-2");
 auto& child13 = child1.add_child("Node 1-3");
 child13.add_child("Node 1-3-1");
 child2.add_child("Node 2-1");

 std::cout << "Nest tree (n):" << std::endl;
 n.print (std::cout);

 indentTree i(n);
 std::cout << "Indent from nest (i):" << std::endl;
 i.print(std::cout);

 nestTree n2(i.indentToNest());
 std::cout << "Indent to nest (i->n2):" << std::endl;
 n2.print(std::cout);

 std::cout << "n==n2? " << std::boolalpha << (n==n2) << std::endl;

 return 0;
}
Nest tree (n):
My tree
    Node 1
        Node 1-1
        Node 1-2
        Node 1-3
            Node 1-3-1
    Node 2
        Node 2-1
Indent from nest (i):
0 My tree
1 Node 1
2 Node 1-1
2 Node 1-2
2 Node 1-3
3 Node 1-3-1
1 Node 2
2 Node 2-1
Indent to nest (i->n2):
My tree
    Node 1
        Node 1-1
        Node 1-2
        Node 1-3
            Node 1-3-1
    Node 2
        Node 2-1
n==n2? true

18.12.2021, 11:57 [619 просмотров]


теги: textprocessing c++ программирование

К этой статье пока нет комментариев, Ваш будет первым