From fa5985ed620c3cd4c7b9712b6b80a2e2c1a8ba31 Mon Sep 17 00:00:00 2001 From: Bent Bisballe Nyeng Date: Sat, 6 Jun 2020 18:32:11 +0200 Subject: Rename task to node everywhere. --- src/nodetree.cc | 475 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 475 insertions(+) create mode 100644 src/nodetree.cc (limited to 'src/nodetree.cc') diff --git a/src/nodetree.cc b/src/nodetree.cc new file mode 100644 index 0000000..1c3992e --- /dev/null +++ b/src/nodetree.cc @@ -0,0 +1,475 @@ +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set et sw=2 ts=2: */ +/*************************************************************************** + * nodetree.cc + * + * Tue Mar 27 11:07:48 CEST 2012 + * Copyright 2012 Jonas Suhr Christensen + * jsc@umbraculum.org + ****************************************************************************/ + +/* + * This file is part of Munia. + * + * Munia is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * Munia is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Munia; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. + */ +#include "nodetree.h" + +#include + +#include "xmlparser.h" + +#include "hugin.hpp" + +#include "xml_encode_decode.h" + +#define ROOT_PARENT_ID -1 + +static inline std::string id2str(nodeid_t id) +{ + char buf[32]; + sprintf(buf, "%u", id); + return buf; +} + +std::string Node::toXML(std::string prefix) +{ + std::string xml; + + xml += prefix + "\n"; + xml += prefix + " \n"; + std::map::iterator ai = data.attributes.begin(); + while(ai != data.attributes.end()) + { + xml += prefix + " first) + "\">" + + xml_encode(ai->second) + "\n"; + ai++; + } + xml += prefix + " \n"; + xml += prefix + " \n"; + NodeList::iterator ni = children.begin(); + while(ni != children.end()) + { + xml += (*ni)->toXML(prefix + " "); + ni++; + } + xml += prefix + " \n"; + xml += prefix + "\n"; + + return xml; +} + +static void concatNodeIdLists(NodeIdList& pre, NodeIdList& post) +{ + pre.insert(pre.end(), post.begin(), post.end()); + //for(NodeIdList::iterator it = post.begin(); + //it != post.end(); it++) + //{ + // pre.push_back( + //} +} + +NodeTree::NodeTree() +{ + root = NULL; + nextid = 10; +} + +NodeTree::~NodeTree() +{ + // cleanup tree +} + +nodeid_t NodeTree::createId() +{ + nodeid_t nodeid; + + do + { + nodeid = nextid++; + } + while(id2node.find(nodeid) != id2node.end()); + + return nodeid; +} + +static nodeid_t rootid = -1; + +NodeIdList NodeTree::insertAsChild(nodeid_t parentid, nodeid_t id, node_t data) + throw (std::exception) +{ + NodeIdList affectedNodes; + + // Initialize + if(!root) + { + rootid = id; + Node* node = createNode(id); + root = node; + node->data = data; + affectedNodes.push_back(id); + } + else + { + try + { + Node* parent = id2node.at(parentid); + Node* child = createNode(id); + //DEBUG(nodetree, "!!!!!!!id in insert: %d\n", data.id); + child->data = data; + insertChild(parent, child); + + //affectedNodes.push_back(parentid); + affectedNodes.push_back(id); + NodeIdList ancestors = ancestorList(id); + concatNodeIdLists(affectedNodes, ancestors); + } + catch(std::exception& e) + { + throw e; + } + } + + //DEBUG(nodetree, "Child %d added to %d, affecting %d nodes\n", + // id, parentid, affectedNodes.size()); + return affectedNodes; +} + +NodeIdList NodeTree::remove(nodeid_t id) + throw (std::exception) +{ + NodeIdList affectedNodes; + affectedNodes.push_back(id); + NodeIdList ancestors = ancestorList(id); + concatNodeIdLists(affectedNodes, ancestors); + + //DEBUG(nodetree, "Removing %d\n", id); + //DEBUG(nodetree, "!!!!!affected nodes %d\n", affectedNodes.size()); + + Node* node = id2node[id]; + + //DEBUG(nodetree, "node: %p, id %d, parent %p\n", node, node->data.id, node->parent); + + //DEBUG(nodetree, "!!!!!size %d\n", node->parent->children.size()); + node->parent->children.remove(node); + for(NodeList::iterator it = node->parent->children.begin(); + it != node->parent->children.end(); + it++) + { + //DEBUG(nodetree, "%p\n", *it); + } + //DEBUG(nodetree, "!!!!!size %d\n", node->parent->children.size()); + + NodeIdList idlist = bfs(id); + NodeIdList::reverse_iterator it = idlist.rbegin(); + while(it != idlist.rend()) + { + node_t node = data(*it); + //Node* n = id2node[node.id]; + //delete(n); + it++; + } + + return affectedNodes; +} + +static bool findNode(Node *needle, Node *haystack) +{ + if(needle == haystack) return true; + NodeList::iterator i = haystack->children.begin(); + while(i != haystack->children.end()) + { + if(findNode(needle, *i)) + { + return true; + } + i++; + } + return false; +} + +NodeIdList NodeTree::move(nodeid_t id, nodeid_t toid) + throw (std::exception) +{ + NodeIdList affectedNodes; + + try + { + Node* child = id2node.at(id); + Node* newparent = id2node.at(toid); + + // Test if new parent is a child of the node itself... + if(findNode(newparent, child)) + { + throw std::exception(); + } + + if(!child->parent) + { + throw std::exception(); + } + + child->parent->children.remove(child); + newparent->children.push_back(child); + + child->parent = newparent; + + affectedNodes.push_back(id); + // affectedNodes.push_back(child->parent->id); + NodeIdList ancestors = ancestorList(id); + concatNodeIdLists(affectedNodes, ancestors); + affectedNodes.push_back(toid); + ancestors = ancestorList(toid); + } + catch(std::exception& e) + { + throw e; + } + + return affectedNodes; +} + +NodeIdList NodeTree::updateData(nodeid_t id, const std::string &name, + const std::string &value) + throw (std::exception) +{ + NodeIdList affectedNodes; + + try + { + Node* node = id2node.at(id); + node->data.attributes[name] = value; + + affectedNodes.push_back(id); + NodeIdList ancestors = ancestorList(id); + concatNodeIdLists(affectedNodes, ancestors); + } + catch(std::exception& e) + { + throw e; + } + + return affectedNodes; +} + +node_t NodeTree::data(nodeid_t id) + throw (std::exception) +{ + node_t t; + + try + { + Node* node = id2node.at(id); + node_t tmp = node->data; + t.id = node->id; + t.attributes = tmp.attributes; + //DEBUG(nodetree, "!!!!t.id and tmp.id in data: %d and %d\n", t.id, tmp.id); + if(node->parent) + { + t.parentid = node->parent->id; + } + else + { + if(t.id != rootid) + { + throw std::exception(); + } + t.parentid = -1; + } + } + catch(std::exception& e) + { + throw e; + } + + return t; +} + +// bfs search from id in tree +NodeIdList NodeTree::bfs(nodeid_t id) + throw (std::exception) +{ + NodeIdList lst; + lst.push_back(id); + + std::list queue; + Node* current = id2node.at(id); + while(true) + { + NodeList children = current->children; + for(NodeList::iterator it = children.begin(); it != children.end(); it++) + { + Node* child = *it; + queue.push_back(child); + lst.push_back(child->id); + } + + if(!queue.empty()) + { + current = queue.front(); + queue.pop_front(); + } + else + { + break; + } + } + + return lst; +} + +NodeIdList NodeTree::ancestorList(nodeid_t id) + throw (std::exception) +{ + NodeIdList ancestors; + + try + { + Node* current = id2node.at(id); + while(current->parent) + { + ancestors.push_back(current->parent->id); + current = current->parent; + } + } + catch(std::exception& e) + { + throw e; + } + + //DEBUG(nodetree, "Collected %d ancestors to %u\n", ancestors.size(), id); + //for(NodeIdList::iterator it = ancestors.begin(); + // it != ancestors.end(); it++) + //{ + // DEBUG(nodetree, "\tancestor %u\n", *it); + //} + return ancestors; +} + +Node* NodeTree::createNode(nodeid_t id) +{ + Node* node = new Node(); + node->parent = NULL; + node->id = id; + id2node[id] = node; + return node; +} + +void NodeTree::insertChild(Node* parent, Node* child) +{ + if(parent) + { + parent->children.push_back(child); + } + else + { + rootid = child->id; + root = child; + } + child->parent = parent; +} + +static void printNode(Node* node, std::string prefix) +{ + if(!node) + { + return; + } + node_t t = node->data; + DEBUG(nodetree, "%s- %u - %s (%p)\n", prefix.c_str(), node->id, + t.attributes["title"].c_str(), node); + + NodeList::iterator it; + for(it = node->children.begin(); it != node->children.end(); it++) + { + Node* child = *it; + printNode(child, " " + prefix); + } +} + +void NodeTree::toStdOut() +{ + printNode(root, ""); +} + +std::string NodeTree::toXML() +{ + Node *root = id2node.at(rootid); + + std::string xml; + xml += "\n"; + xml += "\n"; + xml += root->toXML(" "); + xml += ""; + + return xml; +} + +void NodeTree::fromXML(std::string xml) +{ + XmlParser p(this); + p.parse(xml.c_str(), xml.size()); +} + + +#ifdef TEST_NODETREE +//Additional dependency files +//deps: debug.cc log.cc +//Required cflags (autoconf vars may be used) +//cflags: -I.. +//Required link options (autoconf vars may be used) +//libs: +#include "test.h" +#include + +#define ROOT_ID 0 +#define LOSTFOUND_ID 1 +#define FINISHED_ID 2 +#define BACKLOG_ID 3 +#define PROJECTS_ID 4 +#define FIRST_NODE_ID 10 + +TEST_BEGIN; + +NodeTree tree; + +node_t t; +t.attributes["title"] = "root"; +t.id = ROOT_ID; +tree.insertAsChild(0, ROOT_ID, t); + +t.attributes["title"] = "Finished"; +t.id = FINISHED_ID; +tree.insertAsChild(ROOT_ID, FINISHED_ID, t); + +t.attributes["title"] = "Backlog"; +t.id = BACKLOG_ID; +tree.insertAsChild(ROOT_ID, BACKLOG_ID, t); + +t.attributes["title"] = "Lost+Found"; +t.id = LOSTFOUND_ID; +tree.insertAsChild(ROOT_ID, LOSTFOUND_ID, t); + +t.attributes["title"] = "Projects"; +t.id = PROJECTS_ID; +tree.insertAsChild(ROOT_ID, PROJECTS_ID, t); + +TEST_EQUAL_INT(5, tree.bfs(0).size(), "Testing BFS function"); +TEST_EQUAL_INT(PROJECTS_ID, tree.data(PROJECTS_ID).id, "Testing project id"); +TEST_EQUAL_INT(ROOT_ID, tree.data(ROOT_ID).id, "Testing root id"); + +TEST_END; + +#endif/*TEST_NODETREE*/ -- cgit v1.2.3