ツリー構造を作っている。動作確認のためコンソールから操作できるようにしている。
#include <iostream> #include <iomanip> #include <sstream> #include <memory> #include <vector> #include <string> using namespace std::literals::string_literals; template<typename T> concept HasAsString = requires(T a) { { a.asString() } -> std::same_as<std::string>; };
class NodeBase { protected: public: std::shared_ptr<NodeBase> parent; virtual ~NodeBase() = default; virtual std::string asString() const = 0; // 必ず実装させる仮想関数 virtual std::shared_ptr<NodeBase> getParent() const{return parent;} }; template <HasAsString T> class Folder : public NodeBase, public std::enable_shared_from_this < Folder<T> > { std::vector<std::shared_ptr<NodeBase>> children; // 子ノードは NodeBase 型を保持 T value; bool isOpen; public: Folder(const T& data) : value(data), isOpen(false) {} // 子ノードを追加するメソッド void add(const std::shared_ptr<NodeBase>& node) { children.push_back(node); node->parent = std::dynamic_pointer_cast<NodeBase>(this->shared_from_this()); } const T& getName() const { return value; } std::string asString() const override { return value.asString(); } const std::vector<std::shared_ptr<NodeBase>>& getChildren() const { return children; } std::vector<std::shared_ptr<NodeBase>>& getChildren(){ return children; } bool getIsOpen() const { return isOpen; } void setIsOpen(bool open) { isOpen = open; } }; template <HasAsString T> class Item : public NodeBase { T value; public: Item(const T& data) : value(data) {} std::string asString() const override { return value.asString(); } };
///////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////
// ノードの番号を付けて表示するための補助関数 template <HasAsString FT,HasAsString IT> void printTreeHelper(const std::shared_ptr<NodeBase>& node, int& lineNum, int indent = 0, bool open = false) { if (auto folder = std::dynamic_pointer_cast<Folder<FT>>(node)) { // フォルダの場合 std::cout << std::setw(2) << lineNum++ << std::string(indent, ' ') << (folder->getIsOpen() ? "- " : "+ ") << folder->asString() << "\n"; if (open || folder->getIsOpen()) { for (const auto& child : folder->getChildren()) { printTreeHelper<FT, IT>(child, lineNum, indent + 2, open); // ここでテンプレート引数を明示的に指定 } } } else if (auto item = std::dynamic_pointer_cast<Item<IT>>(node)) { // アイテムの場合 std::cout << std::setw(2) << lineNum++ << std::string(indent+1, ' ') << item->asString() << "\n"; } } // 指定したノード以下のツリーを表示する関数 template <HasAsString FT, HasAsString IT> void printTree(const std::shared_ptr<NodeBase>& node, bool open = false) { int lineNum = 1; printTreeHelper<FT,IT>(node, lineNum, 0, open); }
///////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////
// 全てのノードの数をカウントする関数 template <HasAsString FT> int getAllNodeCount(const std::shared_ptr<NodeBase>& node) { int count = 1; // 自分自身をカウント // フォルダの場合は、子ノードも再帰的にカウント if (auto folder = std::dynamic_pointer_cast<Folder<FT>>(node)) { for (const auto& child : folder->getChildren()) { count += getAllNodeCount<FT>(child); } } return count; }
// 開いているノードの数をカウントする関数 template <HasAsString FT> int getOpenNodeCount(const std::shared_ptr<NodeBase>& node) { int count = 1; // 自分自身をカウント // フォルダの場合、開いているかどうかを確認 if (auto folder = std::dynamic_pointer_cast<Folder<FT>>(node)) { if (folder->getIsOpen()) { // 開いている場合、子ノードも再帰的にカウント for (const auto& child : folder->getChildren()) { count += getOpenNodeCount<FT>(child); } } } return count; }
//////////////////////////////////////////////////// //////////////////////////////////////////////////// ////////////////////////////////////////////////////
// 指定した index のノードを取得する関数 template <HasAsString FT> std::shared_ptr<NodeBase> getNodeHelper(const std::shared_ptr<NodeBase>& node, int& currentIndex, int targetIndex, bool open = false) { // 現在のノードをカウント if (++currentIndex == targetIndex) { return node; } // フォルダの場合は、開閉状態を確認し、再帰的に子ノードを探索 if (auto folder = std::dynamic_pointer_cast<Folder<FT>>(node)) { if (open || folder->getIsOpen()) { for (const auto& child : folder->getChildren()) { auto result = getNodeHelper<FT>(child, currentIndex, targetIndex, open); if (result) { return result; } } } } return nullptr; // 見つからなかった場合 } template <HasAsString FT> std::shared_ptr<NodeBase> getNode(const std::shared_ptr<NodeBase>& root, int targetIndex, bool open = false) { int currentIndex = 0; // ノードのカウント用 return getNodeHelper<FT>(root, currentIndex, targetIndex, open); }
//////////////////////////////////////////////////// //////////////////////////////////////////////////// ////////////////////////////////////////////////////
// ノードの親ノードを表示する関数 template <HasAsString FT, HasAsString IT> void printParentChain(const std::shared_ptr<NodeBase>& node) { auto current = node; while (current) { if (auto folder = std::dynamic_pointer_cast<Folder<FT>>(current)) { std::cout << folder->asString() << " -> "; } else if (auto item = std::dynamic_pointer_cast<Item<IT>>(current)) { std::cout << item->asString() << " -> "; } current = current->getParent(); } std::cout << "nullptr\n"; // ルートに到達したら終了 }
//////////////////////////////////////////////////// //////////////////////////////////////////////////// ////////////////////////////////////////////////////
// ノードを削除する関数 template <HasAsString FT> void deleteNode(std::shared_ptr<NodeBase> node) { if (auto parent = node->getParent()) { if (auto parentFolder = std::dynamic_pointer_cast<Folder<FT>>(parent)) { auto& siblings = parentFolder->getChildren(); siblings.erase(std::remove(siblings.begin(), siblings.end(), node), siblings.end()); } } }
//////////////////////////////////////////////////// //////////////////////////////////////////////////// ////////////////////////////////////////////////////
struct FolderData { std::string name; std::string asString() const { return name; } // コンストラクタ FolderData(const std::string& n) : name(n) {} }; struct ItemData { std::string name; std::string asString() const { return name; } // コンストラクタ ItemData(const std::string& n) : name(n) {} };
//////////////////////////////////////////////////// //////////////////////////////////////////////////// //////////////////////////////////////////////////// bool input_command(char* cmd, int* id, std::string* value) { std::string input; std::getline(std::cin, input); if (input.empty()) return false; std::istringstream iss(input); iss >> *cmd >> *id; if (iss >> std::ws && !iss.eof()) { std::getline(iss, *value); *value = value->substr(value->find_first_not_of(" \t")); // 先頭の空白を削除 } else { *value = ""; } return true; }
int main() { // ツリー構造を作成 auto root = std::make_shared<Folder<FolderData>>(FolderData{ "folder1" }); auto folder2 = std::make_shared<Folder<FolderData>>(FolderData{ "folder2" }); auto folder21 = std::make_shared<Folder<FolderData>>(FolderData{ "folder21" }); auto item211 = std::make_shared<Item<ItemData>>(ItemData{ "item211" }); auto folder22 = std::make_shared<Folder<FolderData>>(FolderData{ "folder22" }); auto item221 = std::make_shared<Item<ItemData>>(ItemData{ "item221"}); auto item222 = std::make_shared<Item<ItemData>>(ItemData{ "item222"}); auto item223 = std::make_shared<Item<ItemData>>(ItemData{ "item223"}); auto folder23 = std::make_shared<Folder<FolderData>>(FolderData{ "folder23" }); auto folder24 = std::make_shared<Folder<FolderData>>(FolderData{ "folder24" }); auto item241 = std::make_shared<Item<ItemData>>(ItemData{ "item241" }); auto item242 = std::make_shared<Item<ItemData>>(ItemData{ "item242" }); root->add(folder2); folder2->add(folder21); folder21->add(item211); folder2->add(folder22); folder22->add(item221); folder22->add(item222); folder22->add(item223); folder2->add(folder23); folder2->add(folder24); folder24->add(item241); folder24->add(item242); // フォルダの開閉状態を設定 root->setIsOpen(true); folder2->setIsOpen(true); folder22->setIsOpen(true); folder24->setIsOpen(false); char cmd=' '; int id; std::string value; do { switch (cmd) { case '*': // 開閉 { auto node = getNode<FolderData>(root, id, false); auto folder = std::dynamic_pointer_cast<Folder<FolderData>>(node); folder->setIsOpen(!folder->getIsOpen()); } break; case 'a': // 追加 { auto node = getNode<FolderData>(root, id, false); auto folder = std::dynamic_pointer_cast<Folder<FolderData>>(node); auto item = std::make_shared<Item<ItemData>>(ItemData{ value }); folder->add(item); } break; case 'd': // 削除 { auto node = getNode<FolderData>(root, id, false); deleteNode<FolderData>(node); } break; } printTree<FolderData, ItemData>(root, false); std::cout << "opennodes " << getOpenNodeCount<FolderData>(root) << std::endl; std::cout << "allnodes " << getAllNodeCount<FolderData>(root) << std::endl; } while (input_command(&cmd, &id, &value) == true); }
最初に以下のようにツリーが表示される。フォルダの左側に+,-がついている。+は現在開いている記号、-は現在閉じている記号。
1- folder1 2 - folder2 3 + folder21 4 - folder22 5 item221 6 item222 7 item223 8 + folder23 9 + folder24 opennodes 9 allnodes 12
*でフォルダを開閉する。例えば「* 4」を入力すると以下のように表示される。
1- folder1 2 - folder2 3 + folder21 4 + folder22 5 + folder23 6 + folder24 opennodes 6 allnodes 12
dでフォルダやアイテムを削除。 「d 5」で以下の結果になる
1- folder1 2 - folder2 3 + folder21 4 + folder22 5 + folder24