#include <iostream>
#include "graph.hpp"
#include "set.hpp"
#include <fstream>


//stack<int> dfs(graph)



int main() {

srand((unsigned) time(nullptr));

int order = 10;

nodeset U(order);
nodeset V(order);
graph T(order);

for (int i = 1; i <= order; i++) U.ins(i);

  int u = U.select(rand() % U.size() + 1);

  U.del(u);
  V.ins(u);

  while (!U.empty()) {

    int u = U.select(rand() % U.size() + 1);
    int v = V.select(rand() % V.size() + 1);

    T.set(u,v);
    U.del(u);
    V.ins(u);
  }

  T.print();
  T.dot("arbol");
  //graph covertree(T.order());


  return 0;
}

#include "set.hpp"

nodeset::nodeset(int cap): n(cap), s(0){

  r = nullptr;
}

nodeset::~nodeset() {}

void nodeset::ins(int x) {

  assert(!full());

  if (empty()){

    r = new node(x);
    s++;

  }else {

    node *p = r;
    node *q = nullptr;

    while (p and p -> data() != x){

      q = p;

      p = x < p -> data() ? p -> left() : p -> right();
    }

    if (p == nullptr) {

      if (x < q -> data()) q -> left(new node(x));
      else q -> right(new node(x));

      s++;
    }
  }

}

void nodeset::del(int x) {

  cout << "del " << x << endl;
  node *p = r;
  node *q = nullptr;

  while (p && p -> data() !=x) {

    q = p;
    if(x < p -> data()) {
      p = p ->left()
    }
  }
}

void nodeset::print() {

  cout << "[ ";
  order(r);
  cout << "]\n";
}

void nodeset::order(node *p) {
  cout << "order" << endl;
  if (p == nullptr) return;

  order(p -> left());
  order(p -> right());

  cout << p -> data() << " ";

}

void nodeset::order(node *p, int &k, int &n) {

if (p == nullptr or k == 0) return;

  k--;

  if (k == 0) n = p -> data();

  order(p -> left(), k, n);
  order(p -> right(), k, n);
}

int nodeset::select(int k){

  cout << "select" << endl;
  int n;
  order(r,k,n);
  return n;
}

#ifndef set_hpp
#define set_hpp
#include<iostream>
#include<cassert>

using namespace std;

class nodeset{

  class node {

    int _data;

    node *lft;
    node *rgt;

    public:

    node(int x): lft(nullptr), rgt(nullptr) { _data = x; }

    int data() const { return _data; }

    node *left() const { return lft; }
    node *right() const { return rgt; }

    void left(node *p) { lft = p; }
    void right(node *p) { rgt = p; }
  };

  node *r;

int n; //Capacidad
int s; //Tamaño

void order(node *);
void order(node *, int &, int &);


public:

  nodeset(int);
  ~nodeset(int);

  int select(int k);

  void ins(int);
  void del(int);

  int capacity() const { return n; }
  int size() const { return s;}

  bool empty() const { return s == 0; }
  bool full() const { return s == n; }

  void print();
};

#endif /* btree_hpp*/

#include "graph.hpp"

bool graph::valid(int i, int j){

  assert(0 < i and i <= n);
  assert(0 < j and j <= n);
  //assert(i != j);

  return true;
}

int graph::f(int i, int j) {

  valid(i,j);

  if (i < j) {
    int k = i;
    i = j;
    j = k;
  }

  return (i - 1) * (i - 2) / 2 + j - 1;
}


graph::graph(int ord): n(ord) {

  m = n * (n - 1) / 2;
  T = new bool[m];

  for (int i = 0; i < m; i++) T[i] = false;
}

graph::~graph() {

  delete [ ] T;
}

void graph::set(int i, int j, bool e) {

 valid(i,j);

  if (i != j) T[f(i,j)] = e;
}

bool graph::get(int i, int j) {

  valid(i,j);

  return i == j ? false : T[f(i,j)];
}

void graph::print() {

  for (int i = 1; i <= n; i++) {

    for (int j = 1; j <= n; j++) {

      if (i == j) cout << false << " ";
      else cout << T[f(i,j)] << " ";
    }
    cout << endl;
  }
}

void graph::dot(string fname) {

  ofstream file(fname);

  file << "graph {\n";
  cout << "graph {\n";

  for (int i = 2; i <= n; i++) 
    for (int j = 1; j < i; j++)
      if (T[f(i,j)]){

       file << i << " -- " << j << endl;
       cout << i << " -- " << j << endl;
      }
  file << "}\n";
  cout << "}\n";
}