Skip to content

Instantly share code, notes, and snippets.

@MagnusTiberius
Created October 27, 2016 23:10
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save MagnusTiberius/90c0babad04d4b91696bb87244382ead to your computer and use it in GitHub Desktop.
Save MagnusTiberius/90c0babad04d4b91696bb87244382ead to your computer and use it in GitHub Desktop.
A
|
B
| |
C D
| | |
E F H
|
G
|
I
Approach:
1. given a tree (ast), with an input (2 params) find_mgr(emp e1, emp e2) => emp mgr
2. define emp ==> struct{char* name, int emp_id, vector<struct emp*> children, int emp_type, struct emp* parent } emp;
3. define emp_type: REGULAR:1, MANAGER:2,
4. define interface: init_tree(), register_emp(), remove_emp(), find_mgr(); set_attr();
5. use new/free, no caching.
Implementation:
#define SUCCESS 0
#define FAILURE 1
struct emp *root_node;
int main()
{
struct emp e1;
struct emp e2;
struct emp m1;
e1.emp_id = 1000;
e2.emp_id = 2000;
int result = find_mgr(&e1, &e2, &m1 );
}
int result find_mgr(struct emp* emp1, struct emp* emp2, struct emp* mgr)
{
if (root_node == NULL) return FAILURE;
int rval1 = find_emp(root_node, emp1->emp_id, emp1);
int rval2 = find_emp(root_node, emp2->emp_id, emp2);
if (rval1 && rval2)
{
}
}
int result search_up_mgr(struct emp* emp1, struct emp* emp2, struct emp* mgr)
{
if (emp1->parent->emp_id == emp2->parent->emp_id)
{
mgr = emp1->parent;
return SUCCESS;
}
else
{
return search_up_mgr(emp1->parent, emp2->parent, mgr);
}
}
int result find_emp(struct emp* current, int emp_id, struct emp* out_emp)
{
if (current == NULL) return FAILURE;
iterator it1;
for(it1 = current.children.begin(); it1 != current.children.end(); it1++)
{
struct emp* v_emp = it1->value;
if (v_emp->emp_id == emp_id)
{
out_emp = v_emp;
return SUCCESS;
}
else
{
return find_emp(v_emp, emp_id, out_emp);
}
}
return FAILURE;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment