いろいろ機能を追加した。
p 番号 ... ノード表示
s 番号 ... ツリーの一部を表示
afh 番号 フォルダ名 ... 指定した番号の位置にフォルダを追加
aih 番号 アイテム名 ... 指定した番号の位置にアイテムを追加
afu 番号 フォルダ名 ... 指定した番号のフォルダの子要素としてフォルダを追加
aif 番号 アイテム名 ... 指定した番号のフォルダの子要素としてアイテムを追加
#ifndef TREE_H #define TREE_H #endif //TREE_H #include <algorithm> using namespace std::literals::string_literals;
// ノードを継承したクラスに asString() メンバ関数があるかを判定するコンセプト 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, public std::enable_shared_from_this < Item<T> > { T value; public: Item(const T& data) : value(data) {} std::string asString() const override { return value.asString(); } };
///////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////// // 全てのノードの数をカウントする関数 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; } currentIndex++; // フォルダの場合は、開閉状態を確認し、再帰的に子ノードを探索 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; // 見つからなかった場合 }
// 指定した index のノードを取得する関数 // ここでの index は、開いているノードのみでカウントする template <HasAsString FT> std::shared_ptr<NodeBase> getNodeOnlyOpen(const std::shared_ptr<NodeBase>& root, int targetIndex) { int currentIndex = 0; // ノードのカウント用 return getNodeHelper<FT>(root, currentIndex, targetIndex,false); }
//////////////////////////////////////////////////// //////////////////////////////////////////////////// ////////////////////////////////////////////////////// ノードを削除する関数 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()); } } }
// 指定したノードの管理情報を取得する関数 // 戻り値 1 親ノード // 戻り値 2 posで指定したノードを持つ親ノードの、子ノードリストのインデクス template <HasAsString FT> std::pair< std::shared_ptr<NodeBase>,int> GetNodeListPos(std::shared_ptr<NodeBase> root,int pos) { // posの位置の現在のノードを取得 auto now_node = getNodeOnlyOpen<FT>(root, pos); // now_nodeの親ノードを取得 auto parent_node = now_node->getParent(); // now_nodeの親ノードの子ノードリストを取得 auto parent_folder = std::dynamic_pointer_cast<Folder<FT>>(parent_node); auto& siblings = parent_folder->getChildren(); // now_nodeの親ノードの子ノードリストのインデクスを取得 auto it = std::find(siblings.begin(), siblings.end(), now_node); int index = std::distance(siblings.begin(), it); return { parent_node,index }; }
template <HasAsString FT, HasAsString IT> void addNodeUnder(std::shared_ptr<NodeBase> root, std::shared_ptr<NodeBase> node) { // nodeをrootの最後に追加 auto folder = std::dynamic_pointer_cast<Folder<FT>>(root); folder->getChildren().push_back(node); node->parent = root; }
template <HasAsString FT, HasAsString IT> void addNodeHere(std::shared_ptr<NodeBase> root, std::shared_ptr<NodeBase> node, int pos) { // ノードを追加する関数 // 挿入位置は番号posで指定する // 新しく追加したアイテムが必ずpos番目になる // 必ず、追加前のposのノードと同じ階層に追加する // 番号posは開いているノードのみでカウントする // 例えばfolder21がノードを持っていても、folder21は開いていないのでその中のノードはカウントしない // 0 - folder1 // 1 - folder2 // 2 item21 // 3 item22 // 4 + folder21 // 5 - folder3 // 6 item31 // 7 item32 // 8 item33 // getNode(folder1,3) == item21 // この時、 // 例1 addNode(NewFolder,2) で // 1 - folder2 // 2 + NewFolder // 3 item21 // 4 item22 auto childinfo = GetNodeListPos<FT>(root, pos); std::shared_ptr<NodeBase> childlist = childinfo.first; auto index = childinfo.second; // nodeをchildlistのindex番に追加 auto folder = std::dynamic_pointer_cast<Folder<FT>>(childlist); folder->getChildren().insert(folder->getChildren().begin() + index, node); node->parent = childlist; }//////////////////////////////////////////////////// //////////////////////////////////////////////////// ////////////////////////////////////////////////////
struct TreeSliceItem { int pos; std::shared_ptr<NodeBase> node; int hierarchy; };
template <HasAsString FT> void GetTreeSliceTraverse(const std::shared_ptr<NodeBase>& node, int hierarchy, int& currentIndex, int from, int to, std::vector<TreeSliceItem>& slice) { if (currentIndex >= from && currentIndex <= to) { slice.push_back({ currentIndex, node, hierarchy }); } currentIndex++; if (auto folder = std::dynamic_pointer_cast<Folder<FT>>(node)) { if (folder->getIsOpen()) { for (const auto& child : folder->getChildren()) { GetTreeSliceTraverse<FT>(child, hierarchy + 1, currentIndex, from, to, slice); } } } }
// ツリーから一部を取り出す関数 template <HasAsString FT> std::vector< TreeSliceItem> GetTreeSlice(std::shared_ptr<NodeBase> root, int from,int to) { // 例えば、以下の状態の時、 // 0 - folder1 // 1 - folder2 // 2 item21 // 3 item22 // 4 + folder21 // 5 - folder3 // 6 item31 // 7 item32 // 8 item33 // GetTreeSlice(folder1,2,6) で // 2 item21 // 3 item22 // 4 + folder21 // 5 - folder3 // 6 item31 // を取得 std::vector<TreeSliceItem> slice; int currentIndex = 0; int currentHierarchy = 0; GetTreeSliceTraverse<FT>(root, currentHierarchy, currentIndex, from, to, slice); return slice; }
#include <iostream> #include <iomanip> #include <sstream> #include <memory> #include <vector> #include <string> #include "tree.hpp" //////////////////////////////////////////////////// //////////////////////////////////////////////////// //////////////////////////////////////////////////// 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) {} }; ///////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////
// ノードの番号を付けて表示するための補助関数 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+2, ' ') << (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 + 2, ' ') << item->asString() << "\n"; } } // 指定したノード以下のツリーを表示する関数 template <HasAsString FT, HasAsString IT> void printTree(const std::shared_ptr<NodeBase>& node, bool open = false) { int lineNum = 0; printTreeHelper<FT, IT>(node, lineNum, 0, open); }
template <HasAsString FT, HasAsString IT> void printTreeSlice(const std::vector<TreeSliceItem>& slice) { for (const auto& item : slice) { if (auto folder = std::dynamic_pointer_cast<Folder<FT>>(item.node)) { std::cout << std::setw(2) << item.pos << std::string(item.hierarchy * 2, ' ') << (folder->getIsOpen() ? "- " : "+ ") << folder->asString() << "\n"; } else if (auto itemNode = std::dynamic_pointer_cast<Item<IT>>(item.node)) { std::cout << std::setw(2) << item.pos << std::string(item.hierarchy * 2, ' ') << itemNode->asString() << "\n"; } } }
//////////////////////////////////////////////////// //////////////////////////////////////////////////// ////////////////////////////////////////////////////
// ノードの親ノードを表示する関数 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"; // ルートに到達したら終了 }
//////////////////////////////////////////////////// //////////////////////////////////////////////////// ////////////////////////////////////////////////////
bool input_command(std::string* 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); std::string cmd = " "; int id; std::string value; do { if (cmd == "*") { // 開閉 auto node = getNodeOnlyOpen<FolderData>(root, id); auto folder = std::dynamic_pointer_cast<Folder<FolderData>>(node); folder->setIsOpen(!folder->getIsOpen()); } else if (cmd == "p") { // 指定したノードを表示 auto node = getNodeOnlyOpen<FolderData>(root, id); std::cout<<node->asString() << std::endl; } else if (cmd == "afh") { // 指定した場所にフォルダを追加 ex. afh 1 folder3 addNodeHere<FolderData, ItemData>( root, std::make_shared<Folder<FolderData>>(FolderData{ value }), id ); } else if (cmd == "aih") { // 指定した場所にアイテムを追加 ex. aih 3 item3 addNodeHere<FolderData, ItemData>( root, std::make_shared<Item<ItemData>>(ItemData{ value }), id ); } else if (cmd == "afu") { // 指定したフォルダの下にフォルダを追加 ex. afu 3 folder3 auto selected = getNodeOnlyOpen<FolderData>(root, id); addNodeUnder<FolderData, ItemData>( selected, std::make_shared<Folder<FolderData>>(FolderData{ value }) ); } else if (cmd == "aiu") { // 指定したフォルダの下にアイテムを追加 ex. aiu 3 item3 auto selected = getNodeOnlyOpen<FolderData>(root, id); addNodeUnder<FolderData, ItemData>( selected, std::make_shared<Item<ItemData>>(ItemData{ value }) ); } else if (cmd == "d") { // 削除 auto node = getNodeOnlyOpen<FolderData>(root, id); deleteNode<FolderData>(node); } else if (cmd == "s") { // ツリーの一部を取得 ex. s 3 auto slice = GetTreeSlice<FolderData>(root, id, id+4); printf("%d-%d\n", id, id + 4); printTreeSlice<FolderData, ItemData>(slice); printf("\n"); } 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); }
0 - folder1 1 - folder2 2 + folder21 3 - folder22 4 item221 5 item222 6 item223 7 + folder23 8 + folder24
0 - folder1 1 - folder2 2 + folder21 3 - folder22 4 item221 5 + NEW_FOLDER 6 item222 7 item223 8 + folder23 9 + folder24
0 - folder1 1 - folder2 2 + folder21 3 - folder22 4 item221 5 + NEW_FOLDER 6 item222 7 item223 8 New_Item 9 + folder23 10 + folder24
6 item222 7 item223 8 New_Item 9 + folder23 10 + folder24