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 "debug.h"

#define ROOT_PARENT_ID -1

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;
}

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

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);
//      printf("!!!!!!!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;
    }
  }

//  printf("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);

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

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

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

//  printf("!!!!!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++) {
//    printf("%p\n", *it);
  }
//  printf("!!!!!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, task_t t) 
  throw (std::exception) 
{
  
  TaskIdList affectedNodes;

  try {
    node_t* node = id2node.at(id);
    node->data = t;

    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 = tmp.id;
    t.title = tmp.title;
//    printf("!!!!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;
  }
  
//  printf("Collected %d ancestors to %u\n", ancestors.size(), id);
//  for(TaskIdList::iterator it = ancestors.begin();
//      it != ancestors.end(); it++) {
//    printf("\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) {
  parent->children.push_back(child);
  child->parent = parent;
}

static void printNode(node_t* node, std::string prefix) {
  if(!node) return;
  task_t t = node->data;
  printf("%s- %u - %s (%p)\n", prefix.c_str(), t.id, t.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, "");
}


#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.title = "root";
t.id = ROOT_ID;
tree.insertAsChild(0, ROOT_ID, t);

t.title = "Finished";
t.id = FINISHED_ID;
tree.insertAsChild(ROOT_ID, FINISHED_ID, t);

t.title = "Backlog";
t.id = BACKLOG_ID;
tree.insertAsChild(ROOT_ID, BACKLOG_ID, t);

t.title = "Lost+Found";
t.id = LOSTFOUND_ID;
tree.insertAsChild(ROOT_ID, LOSTFOUND_ID, t);

t.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*/