From d2edbc38cac8da52f58c5cd3da6c0c625fa05736 Mon Sep 17 00:00:00 2001
From: Santo Cariotti <santo@dcariotti.me>
Date: Sat, 6 Feb 2021 19:56:36 +0100
Subject: conf: rename

---
 1_anno/Programmazione_2/data_structures/bfs.cc | 186 -------------------------
 1 file changed, 186 deletions(-)
 delete mode 100644 1_anno/Programmazione_2/data_structures/bfs.cc

(limited to '1_anno/Programmazione_2/data_structures/bfs.cc')

diff --git a/1_anno/Programmazione_2/data_structures/bfs.cc b/1_anno/Programmazione_2/data_structures/bfs.cc
deleted file mode 100644
index 2b4efbd..0000000
--- a/1_anno/Programmazione_2/data_structures/bfs.cc
+++ /dev/null
@@ -1,186 +0,0 @@
-#include<iostream>
-#include<vector>
-#include<queue>
-#define W -1
-#define G 0
-#define B 1
-
-using namespace std;
-
-template<class H>
-class node {
-public:
-    explicit node(H key, node<H>* next) : _key{key}, _next(next) {}
-    const H& key() const { return _key; }
-    H& key() { return _key; }
-    const node<H>*& next() const { return _next; }
-    node<H>*& next() { return _next; }
-private:
-    H _key;
-    node<H>* _next;
-};
-
-template<class H>
-class list {
-public:
-    list() : _head{nullptr} {}
-    ~list() {
-        while(_head) {
-            auto tmp = _head;
-            _head = _head->next();
-            delete tmp;
-        }
-    }
-    list<H>* push(H val) {
-        auto iter = _head;
-        while(iter && iter->next())
-            iter = iter->next();
-
-        if(!iter)
-            _head = new node<H>{val, nullptr};
-        else
-            iter->next() = new node<H>{val, nullptr};
-
-        return this;
-    }
-    void print() {
-        auto iter = _head;
-        while(iter) {
-            cout << iter->key() << ' ';
-            iter = iter->next();
-        }
-    }
-    vector<H> as_vector() {
-        vector<H> v;
-        auto iter = _head;
-        while(iter) {
-            v.push_back(iter->key());
-            iter = iter->next();
-        }
-        return v;
-    }
-    node<H>* search(H val) {
-        auto iter = _head;
-        while(iter && iter->key() != val) {
-            iter = iter->next();
-        }
-
-        return iter;
-    }
-private:
-    node<H>* _head;
-};
-
-template<class H>
-class graph {
-public:
-
-private:
-    int _len, _nodes, _edges;
-    int* _parents;
-    int* _distances;
-    H** _k; // it works like a dictionary, it saves the keys
-    list<int>** _adj;
-    int _index(H val) {
-        for(int i = 0; i < _nodes; ++i)
-            if(*_k[i] == val) return i;
-
-        return -1;
-    }
-public:
-    graph(int len) : _len{len}, _nodes{0}, _edges{0} {
-        _k = new H*[len];
-        _adj = new list<int>*[_len];
-        _parents = new int[_len];
-        _distances = new int[_len];
-        for(int i = 0; i < _len; ++i) {
-            _k[i] = nullptr;
-            _adj[i] = new list<int>{};
-        }
-    }
-
-    graph<H>* add_node(H k) {
-        if(_nodes == _len) return this;
-        if(_index(k) >= 0) return this; // node is already there
-
-        _k[_nodes++] = new H(k);
-
-        return this;
-    }
-
-    void bfs(int s) {
-        int colors[_len];
-        queue<int> q;
-
-        for(int i = 0; i < _nodes; ++i) {
-            colors[i] = W;
-            _parents[i] = -1;
-            _distances[i] = 999999999;
-        }
-        q.push(s);
-        colors[s] = G;
-        _distances[s] = 0;
-        while(!q.empty()) {
-            int x = q.front();
-            q.pop();
-            for(auto const& j : _adj[x]->as_vector()) {
-                if(colors[j] == W) {
-                    colors[j] = G;
-                    q.push(j);
-                    _parents[j] = x;
-                    _distances[j] = _distances[x] + 1;
-                }
-            }
-            colors[x] = B;
-        }
-
-        for(int i = 0; i < _nodes; ++i) {
-            cout << "[" << i << "]->";
-            if(_distances[i]==999999999) cout << "inf." << endl;
-            else cout << _distances[i] << endl;
-        }
-    }
-
-    void bfs(H x) {
-        int s = _index(x);
-        if(s != -1)
-            bfs(s);
-    }
-
-    graph<H>* add_edge(H x, H y) {
-        int i = _index(x);
-        int j = _index(y);
-        if(i < 0 || j < 0) return this;
-
-        if(!_adj[i]->search(j)) {
-            _adj[i]->push(j);
-            _edges++;
-        }
-
-        return this;
-    }
-
-    void print() {
-        for(int i = 0; i < _nodes; ++i) {
-            cout << "(" << i << ", " << *_k[i] << "): ";
-            for(auto const& j : _adj[i]->as_vector())
-                cout << "(" << j << ", " << *_k[j] << "), ";
-            cout << '\n';
-        } 
-    }
-};
-
-
-int main() {
-    graph<string>* g = new graph<string>(5);
-    g->add_node("hello")->add_node("greg")->add_node("yes");
-    g->add_node("nop")->add_node("ok");
-    g->add_edge("hello", "ok");
-    g->add_edge("ok", "yes")->add_edge("yes", "ok")->add_edge("yes", "yes");
-    g->add_edge("yes", "nop");
-    g->print();
-    g->bfs("hello");
-
-    delete g;
-    return 0;
-}
-- 
cgit v1.2.3-18-g5258