AfanasevGad7

commit a2d666b3cd65783d9b6e7be7312a443b1d8337ca
parent 463fc87d1f300814edd5e6e67cb340205d95a34e
Author: Plat <plat@stellar-nexus.ru>
Date:   Fri,  7 Nov 2025 19:07:35 +0000

Added ntree.cxx

Diffstat:
M
Makefile
 | 
6
+++++-
A
ntree.cxx
 | 
204
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 209 insertions(+), 1 deletion(-)
diff --git a/Makefile b/Makefile
@@ -1,9 +1,10 @@
 include config.mk
 BIN = avl fib rb
+CXX = ntree
 LIBS = ${wildcard libutil/*.c}
 OBJS = ${LIBS:.c=.o}
 
-all: ${BIN} config.h
+all: ${BIN} ${CXX} config.h
 
 config.h:
 	cp config.def.h config.h
@@ -12,6 +13,9 @@ ${BIN}: ${BIN:%=%.o} ${OBJS}
 	${CC} ${CFLAGS} -o $@ $@.o ${OBJS} ${LDFLAGS}
 	strip $@
 
+${CXX}: ${CXX:%=%.o} ${OBJS}
+	${CXX} ${CXXFLAGS} -o $@ $@.cxx ${OBJS} ${LDFLAGS}
+
 %.o: %.c
 	${CC} ${CFLAGS} -c $< -o $@
 
diff --git a/ntree.cxx b/ntree.cxx
@@ -0,0 +1,204 @@
+#include <iostream>
+#include <vector>
+
+#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 add(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->add(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);
+        Node *n_p = this->find_parent_node(this->root, n);
+
+        for (Node *r : n->children) n_p->children.push_back(r);
+
+        n_p->children.erase(std::find(n_p->children.begin(), n_p->children.end(), n));
+
+        free(n);
+
+        return true;
+
+    }
+};
+
+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':
+		eprintf("Not implemented\n");
+		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.add(arr[i] % (i+1) - 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) - 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) - 1);
+		elapsed += clock() - start_time;
+	}
+
+	printf("%f\n", (double)elapsed/CLOCKS_PER_SEC);
+}