calculate the row and cols based on the tree structure to generate the excel file

I have a class Department:

class Department{
  string des;
  string name;
  string id;
  List<Department> subDeps;
}

As the code shown,one department may have several sub-departmens.

Now,I have read the information from database,and I get the root Department object.

Then I want to generate a excel worksheet like this manner:

In fact,The root "Department开发者_StackOverflow中文版" object is a tree structure .

When I try to write the items to the excel sheet,I have to decide the rows and cols for the item,but I can not make it.

And one can do me a favor?

---

Look at it this way:

0 00 000 | (0,0) (0,1) (0,2)
     001 |             (1,2)
1 10 100 | (2,0) (2,1) (2,2)
     101 |             (3,2)
  11     |       (4,1)

I used the same syntax as you to name the nodes (left side) and the corresponding position "(row,column)" into the grid (right side). There are two top level departments here, 0 and 1. You can label your nodes with "(x,y)" coordinates with a depth first visit for every tree/top level department. Whenever you descend from father to child, you have to increase the column number by 1. Every time you visit a new sibling your row index must refer to a new, empty one (in the example, the sibling of 10 is 11 but you can't put it in (3,1) because row 3 is already occupied by dept 101).

I would write the algorithm following these guidelines. Keep track of the current (x,y) with two variables that are passed down as parameters of a recursive depth-first visit, together with the current node/department to be visited. Make sure that the function edits as required the excel representation but returns the maximum row index used (so that you can use it to know which is the following row when visiting a new sibling -- as in the previous example). Every time you make a recursive call you have to call it with coords (x, y+1) because it's a new column. In a similar manner, when you visit a new sibling you call it with (coords prev_call_retn+1, y) because it's a new row (where coords_prev_call_retn is the value of the last recursive call on the previous sibling). An helper function will call the recursive one on the root node and using as base coords (0,0), or whatever you like to start from.

#include <iostream>
#include <list>
#include <string>

using namespace std;

class Dept {
public:
    string id;
    list<Dept*> *subDepts;

    Dept(string id) {
        this->id = id;
        this->subDepts = new list<Dept*>();
    }

    Dept *addChild(Dept *d) {
        this->subDepts->push_back(d);
        return d;
    }

    Dept *addChild(string id) {
        Dept *d = new Dept(id);
        return this->addChild(d);
    }

};

void visit(Dept *d, int row, int col) {
    cout << "Dept " << d->id  << ": (" <<  row << ", " << col << ")\n";
}

int label(Dept *d, int row, int col) {
    if (d == 0) return row;
    visit(d, row, col);
    list<Dept*> *lst = d->subDepts;
    for (list<Dept*>::iterator it = lst->begin() ; it != lst->end(); it++)
    {
        row = label(*it, row, col+1) + 1;
    }
    if (lst->size() > 0) row--;
    return row;
}

int label(Dept *d) {
    label(d, 0, 0);
}

In this C++ code, label() is the function you're interested in.

The parameters row and col are supposed to be the correct coordinates of the department *d, so that we can visit the node immediately.

The loop recursively calls label() on each children (if any). Note that I use the variable row in order to keep track of the last used row + 1.

Lastly, we have to return the last used row by the function, but being careful to subtract one if the d->subDepts is not empty. This is because the for loop that adds 1 extra row in the last iteration.

Here is an example main:

int main(int argc, char **argv) {
    Dept *d0   = new Dept("0");
    Dept *d00  = d0->addChild("00");
    Dept *d01  = d0->addChild("01");
    Dept *d000 = d00->addChild("000");
    Dept *d001 = d00->addChild("001");
    Dept *d002 = d00->addChild("002");
    Dept *d010 = d01->addChild("010");
    Dept *d02  = d0->addChild("02");
    label(d0);
    return 0;
}

And here the result:

bash-4.2$ g++ dept.cpp  && ./a.out
Dept 0: (0, 0)
Dept 00: (0, 1)
Dept 000: (0, 2)
Dept 001: (1, 2)
Dept 002: (2, 2)
Dept 01: (3, 1)
Dept 010: (3, 2)
Dept 02: (4, 1)

I hope this helps.

---

If you want to do the layout as in your example, with colspans to align the cells then I don't see any way to do so without first finding out, or knowing in advance (hard coding), the max depth of the tree - you will need this to determine the total number of columns used for departments.

Assumptions of some table properties (will help understand the code below):

• Only the rightmost cells span multiple columns, all others have colWidth 1
• The rightmost cells never span multiple rows, always have colHeight 1
• There exists some function to compute maximum width, or alternatively max column index, for the 'department' part of the table (to set the variable blockWidth or maxY in the code)

Pseudocode to layout the table:

displayDeptTree(Department root) {
    startX, startY: beginning coord of the root dept
    blockWidth: total no. of columns (tree depth + 1, or hardcoded to value > possible depth)
    maxY = startY + blockWidth - 1 // global var?

    addDeptIntoCell(root, startX, startY)
}

// returns height of the cell
int addDeptIntoCell(Department d, x, y) {
    colHeight = 1
    if (d->subDeps is empty) {
        colWidth = maxY - y
        addDepartment(d, x, y, colHeight, colWidth) // colHeight = 1 always
    } else {
        currY = y
        for (Dept child : d->subDeps) {
            childHeight = addDeptIntoCell(child, x + 1, currY);  // increment x pos for children
            currY += childHeight
        }
        colHeight = currY - y
        addDepartment(d, x, colHeight, 1)
    }
    return colHeight
}


addDepartment(Department d, x, y, height, width) {
    // Actually adds the department info into table, parameters should be self-explanatory, implementation not shown
}

This may have off by one errors etc., and I'm using d->subDeps in the Java sense not C++ pointer deference, but you should get the general idea :)