path: root/src/tasktree.cc

/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set et sw=2 ts=2: */
/***************************************************************************
 *            tasktree.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 "tasktree.h"

#include <stdio.h>

#include "xmlparser.h"

#include "hugin.hpp"

#include "xml_encode_decode.h"

#define ROOT_PARENT_ID -1

static inline std::string id2str(taskid_t id)
{
  char buf[32];
  sprintf(buf, "%u", id);
  return buf;
}

std::string node::toXML(std::string prefix)
{
  std::string xml;
  
  xml += prefix + "<task id=\""+id2str(id)+"\">\n";
  xml += prefix + "  <attributes>\n";
  std::map<std::string, std::string>::iterator ai = data.attributes.begin();
  while(ai != data.attributes.end()) {
    xml += prefix + "    <attribute name=\"" + xml_encode(ai->first) + "\">"
      + xml_encode(ai->second) + "</attribute>\n";
    ai++;
  }
  xml += prefix + "  </attributes>\n";
  xml += prefix + "  <children>\n";
  NodeList::iterator ni = children.begin();
  while(ni != children.end()) {
    xml += (*ni)->toXML(prefix + "    ");
    ni++;
  }
  xml += prefix + "  </children>\n";
  xml += prefix + "</task>\n";
  
  return xml;
}

static void concatTaskIdLists(TaskIdList& pre, TaskIdList& post) {
    pre.insert(pre.end(), post.begin(), post.end());
  //  for(TaskIdList::iterator it = post.begin();
  //  it != post.end(); it++) {
  //    pre.push_back(
  //  }
}

TaskTree::TaskTree() {
  root = NULL;
  nextid = 10;
}

TaskTree::~TaskTree() {
  // cleanup tree
}

taskid_t TaskTree::createId() {
  taskid_t taskid;

  do {
    taskid = nextid++;
  } while(id2node.find(taskid) != id2node.end());

  return taskid;
}

static taskid_t rootid = -1;

TaskIdList TaskTree::insertAsChild(taskid_t parentid, taskid_t id, task_t data) 
  throw (std::exception) 
{

  TaskIdList affectedNodes;

  // Initialize
  if(!root) {
    rootid = id;
    node_t* node = createNode(id);
    root = node;
    node->data = data;
    affectedNodes.push_back(id);

  } else {

    try { 
      node_t* parent = id2node.at(parentid);
      node_t* child = createNode(id);
//      DEBUG(tasktree, "!!!!!!!id in insert: %d\n", data.id);
      child->data = data;
      insertChild(parent, child);
      
      //    affectedNodes.push_back(parentid);
      affectedNodes.push_back(id);
      TaskIdList ancestors = ancestorList(id);
      concatTaskIdLists(affectedNodes, ancestors);
    }
    catch(std::exception& e) {
      throw e;
    }
  }

//  DEBUG(tasktree, "Child %d added to %d, affecting %d nodes\n", 
//      id, parentid, affectedNodes.size());
  return affectedNodes;
}

TaskIdList TaskTree::remove(taskid_t id) 
  throw (std::exception) 
{
  TaskIdList affectedNodes;
  affectedNodes.push_back(id);
  TaskIdList ancestors = ancestorList(id);
  concatTaskIdLists(affectedNodes, ancestors);

//  DEBUG(tasktree, "Removing %d\n", id);

//  DEBUG(tasktree, "!!!!!affected nodes %d\n", affectedNodes.size());

  node_t* node = id2node[id];
 
//  DEBUG(tasktree, "node: %p, id %d, parent %p\n", node, node->data.id, node->parent);

//  DEBUG(tasktree, "!!!!!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(tasktree, "%p\n", *it);
  }
//  DEBUG(tasktree, "!!!!!size %d\n", node->parent->children.size());

  TaskIdList idlist = bfs(id);
  TaskIdList::reverse_iterator it = idlist.rbegin();
  while(it != idlist.rend()) {
    task_t task = data(*it); 
//    node_t* n = id2node[task.id];  
//    delete(n);
    it++;
  }

  return affectedNodes;
}

TaskIdList TaskTree::move(taskid_t id, taskid_t toid) 
  throw (std::exception) 
{

  TaskIdList affectedNodes;

  try {
    node_t* child = id2node.at(id);
    node_t* newparent = id2node.at(toid);

    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);
    TaskIdList ancestors = ancestorList(id);
    concatTaskIdLists(affectedNodes, ancestors);
    affectedNodes.push_back(toid);    
    ancestors = ancestorList(toid);
  }
  catch(std::exception& e) {
    throw e;
  }

  return affectedNodes;
}

TaskIdList TaskTree::updateData(taskid_t id, const std::string &name,
                                const std::string &value) 
  throw (std::exception) 
{
  
  TaskIdList affectedNodes;

  try {
    node_t* node = id2node.at(id);
    node->data.attributes[name] = value;

    affectedNodes.push_back(id);
    TaskIdList ancestors = ancestorList(id);
    concatTaskIdLists(affectedNodes, ancestors);
  }
  catch(std::exception& e) {
    throw e;
  }

  return affectedNodes;
}

task_t TaskTree::data(taskid_t id) 
  throw (std::exception) 
{

  task_t t;

  try {
    node_t* node = id2node.at(id);
    task_t tmp = node->data;
    t.id = node->id;
    t.attributes = tmp.attributes;
//    DEBUG(tasktree, "!!!!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
TaskIdList TaskTree::bfs(taskid_t id) 
  throw (std::exception) 
{

  TaskIdList lst;
  lst.push_back(id);
  
  std::list<node_t*> queue;
  node_t* current = id2node.at(id);
  while(true) {
    NodeList children = current->children;
    for(NodeList::iterator it = children.begin(); it != children.end(); it++) {
      node_t* child = *it;
      queue.push_back(child);
      lst.push_back(child->id);
    }
    
    if(!queue.empty()) {
      current = queue.front();
      queue.pop_front();
    }
    else {
      break;
    }
  }

  return lst;
}

TaskIdList TaskTree::ancestorList(taskid_t id)
  throw (std::exception) 
{
  
  TaskIdList ancestors;

  try {
    node_t* current = id2node.at(id);
    while(current->parent) {
      ancestors.push_back(current->parent->id);
      current = current->parent;
    }
  }
  catch(std::exception& e) {
    throw e;
  }
  
//  DEBUG(tasktree, "Collected %d ancestors to %u\n", ancestors.size(), id);
//  for(TaskIdList::iterator it = ancestors.begin();
//      it != ancestors.end(); it++) {
//    DEBUG(tasktree, "\tancestor %u\n", *it);
//  }
  return ancestors;
}

node_t* TaskTree::createNode(taskid_t id) {
  node_t* node = new node_t();
  node->parent = NULL;
  node->id = id;
  id2node[id] = node;
  return node;
}

void TaskTree::insertChild(node_t* parent, node_t* child) {
  if(parent) parent->children.push_back(child);
  else {
    rootid = child->id;
    root = child;
  }
  child->parent = parent;
}

static void printNode(node_t* node, std::string prefix) {
  if(!node) return;
  task_t t = node->data;
  DEBUG(tasktree, "%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_t* child = *it;
    printNode(child, "  " + prefix);
  }
}

void TaskTree::toStdOut() {
  printNode(root, "");
}

std::string TaskTree::toXML()
{
  node_t *root = id2node.at(rootid);

  std::string xml;
  xml += "<?xml version='1.0' encoding='UTF-8'?>\n";
  xml += "<tasktree nextid=\""+id2str(nextid)+"\">\n";
  xml += root->toXML("  ");
  xml += "</tasktree>";

  return xml;
}

void TaskTree::fromXML(std::string xml)
{
  XmlParser p(this);
  p.parse(xml.c_str(), xml.size());
}


#ifdef TEST_TASKTREE
//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 <exception>

#define ROOT_ID 0
#define LOSTFOUND_ID 1
#define FINISHED_ID 2
#define BACKLOG_ID 3
#define PROJECTS_ID 4
#define FIRST_TASK_ID 10

TEST_BEGIN;

TaskTree tree;

task_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_TASKTREE*/