AfanasevGad7

ntree.cxx (4403B)

---

 #include <algorithm>
 #include <climits>
 #include <cstdint>
 #include <iostream>
 #include <vector>
 
 extern "C" {
 #include "tree.h"
 }
 
 #include "config.h"
 
 
 class NTree {
 
     struct Node {
         int id, data;
         std::vector<Node*> children;
     };
 
 
     bool push_node(int id, int data, Node *rt) {
         Node *n = new Node;
 
         n->id = id;
         n->data = data;
 
         rt->children.push_back(n);
 
         n = rt->children.back();
 
         return true;
     }
 
 
     Node* find_parent_node(Node *rt, Node *rt_s) {
 
         if (rt_s->id == 0) return 0;
 
         if (rt->children.size() == 0) return 0;
     
         std::vector<Node*> rts;
 
         for (Node *c : rt->children) {
             if (c->id == rt_s->id) return rt;
             rts.push_back(this->find_parent_node(c, rt_s));
         }
 
         for (Node *i : rts) {
             if (i) return i;
         }
 
         return 0;
     }
 
 
 public:
 
     Node *root = new Node;
 
     int last_id = 0;
 
 
     NTree() {
         Node *genesis = new Node;
 
         genesis->id = 0;
         genesis->data = 0;
 
         this->root = genesis;
     }
 
     
     bool insert(int parent_id, int data, Node *rt) {
 
         if (rt->id == parent_id) return this->push_node(++this->last_id, data, rt);
 
         if (rt->children.size() == 0) return false;
 
         std::vector<bool> r;
 
         for (auto c : rt->children) {
             r.push_back(this->insert(parent_id, data, c));
         }
 
         for (bool a : r) {
             if (a) return true;
         }
 
         return false;
     };
 
 
     void parse(Node *rt) {
         Node *p = this->find_parent_node(this->root, rt);
         std::cout << std::endl << "id: " << rt->id << " data: " << rt->data << " parent id: " << (p ? p->id : (rt->id ? -1 : 0));
 
         for (Node *c : rt->children) {
             this->parse(c);
         }
     }
 
 
     Node* search(int id, Node *rt) {
 
         if (rt->id == id) return rt;
 
         std::vector<Node*> r;
 
         for (Node *c : rt->children) {
             r.push_back(this->search(id, c));
         }
 
         for (Node *c : r) {
             if (c) return c;
         }
 
         return 0;
     }
 
 
     bool remove(int id) {
         Node *n = this->search(id, this->root);
 	if (!n) return false;
 
         Node *n_p = this->find_parent_node(this->root, n);
 	if (!n_p) return false;
 
         for (Node *r : n->children) n_p->children.push_back(r);
 
 	auto it = std::find(n_p->children.begin(), n_p->children.end(), n);
 	if (it != n_p->children.end())
 		n_p->children.erase(it);
 
 	delete n;
 
         return true;
 
     }
 };
 
 static void
 usage(void)
 {
 	eprintf("usage: %s [-c] [-s] [-d] [filename]\n", argv0);
 }
 
 int
 main(int argc, char *argv[])
 {
 	int cflag = 0, sflag = 0, dflag = 0;
 	ARGBEGIN {
 	case 'c':
 		cflag = 1;
 		break;
 	case 's':
 		sflag = 1;
 		break;
 	case 'd':
 		dflag = 1;
 		break;
 	} ARGEND
 	if (argc > 1 || (cflag + sflag + dflag) < 1)
 		usage();
 	const char *filename;
 	if (argc == 1)
 		filename = argv[0];
 	else
 		filename = FILENAME;
 	
 	FILE *file;
 	if (!(file = fopen(filename, "r")))
 		eprintf("fopen %s:", filename);
 	
 	int arr[TESTNUMBER+1], ch;
 	char w[64];
 	int len = 0, wi = 0;
 	do {
 		ch = fgetc(file);
 		if (!isspace(ch) && ch != EOF) {
 			w[wi++] = ch;
 		} else if (wi > 0) {
 			w[wi] = '\0';
 			arr[len++] = estrtonum(w, 0, INT_MAX);
 			wi = 0;
 		}
 	} while (ch != EOF && len <= TESTNUMBER);
 	efshut(file, filename);
 	if (len < TESTNUMBER)
 		eprintf("Array too small\n");
 	if (len > TESTNUMBER)
 		weprintf("Array too big - using only the first %d elements\n", TESTNUMBER);
 
 	NTree r;
 	clock_t start_time, elapsed = 0;
 
 	if (cflag)
 		start_time = clock();
 	for (int i = 0; i < TESTNUMBER; ++i)
 		r.insert(arr[i] % (i+1), arr[i], r.root);
 	if (cflag)
 		elapsed += clock() - start_time;
 	
 	volatile uintptr_t checksum = 0; /* to avoid optimization */
 	if (sflag) {
 		start_time = clock();
 		for (int i = 0; i < TESTNUMBER; ++i)
 			checksum = (uintptr_t)r.search(arr[i] % (i+1), r.root);
 		elapsed += clock() - start_time;
 	}
 
 	if (dflag) {
 		start_time = clock();
 		for (int i = 0; i < TESTNUMBER; ++i)
 			r.remove(arr[i] % (i+1));
 		elapsed += clock() - start_time;
 	}
 
 	printf("%f\n", (double)elapsed/CLOCKS_PER_SEC);
 }