for Dutch vectored tree

[jonnin]

I lost the thread where we were talking about this, but decided to make a crude and rough hack at expressing what I was trying to say. I did not finish the used/unused ideas, but put enough in to see where it was going. It may have bugs etc, I cranked it out pretty fast.

*Its going to need some TLC if you delete the root node and then put it back in.
*The only interesting part is insert. the rest is just filler really.

advantages over pure tree:
- can load and store tree to file directly without a rebuild though a more complex node type would have serialize needs.
- can iterate as a vector to touch all nodes, etc
- less page faults/ solid block of memory used
- fairly compact, vs the classic computed index tree to array approach

disadvantages: its a convoluted oddity just to get tree traversals and BST like behavior, eg sorted inserts? Im not a big tree guy, so I dunno what other practical use such a thing might have?

/shrug anyway, it was interesting to poke at, but I probably won't clean it up and finish it given I don't have much use for it.

#include <cstdio> //a pile of common includes. not all needed here. 
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
#include <ctype.h>
#include <stdint.h> 
#include <cmath>
#include <vector>
#include <numeric>
#include <random>
#include <iomanip>
#include <fstream>
#include <bits/stdc++.h>
#include <set>
#include <ctime>
#include <numeric>

//#include <pthread.h>
//#include <unistd.h>

using namespace std;

struct vtnode
{
  int data;
  int left;
  int right;
  bool used;
  vtnode(){left = right = 0; used = false;}
  vtnode(int d){data = d; used = true; left = right = 0;}
};

class vectree
{
  vector<vtnode> vn;
  vector<int> unused;
  int count;
  
  public:  
  vectree(){count = 0; vtnode x; vn.push_back(x);}
  
  void ins(int in)
  {
	  static vtnode tmp(0);
      static int dest  = 0;    	  
	  
     if(count == 0) //special case empty tree
	 {
		count++;
		vn[0].data = in;
		vn[0].left = vn[0].right= 0;
		vn[0].used = true;
		return;
	 }	 
	 if(unused.size()) 
	 {
		dest = unused[unused.size()-1];
	    unused.pop_back();
	 }
	  else
	  {		
	    dest = vn.size();
		tmp.data = in;
		vn.push_back(tmp);		
	  }
	 for(int i = 0; i < count;)
	 {
	   if(in < vn[i].data && vn[i].left)
	   {
	   		   i = vn[i].left;
	   }
	   else if(in < vn[i].data && vn[i].left == 0)
	   {
		 vn[i].left = dest;
         count++;		 
		 return;
	   }

	   if(in >= vn[i].data && vn[i].right)
	   {
	   		   i = vn[i].right;
	   }
	   else if(in >= vn[i].data && vn[i].right == 0)
	   {
		 vn[i].right = dest;
         count++;		 
		 return;
	   }
	 }    	 
  }
  
  void save()
  {
	  ofstream ofs("tr.bin",ios::binary);
	  unsigned int s = vn.size();
	  ofs.write((char*)&s, sizeof(unsigned int));
	  ofs.write((char*)&vn[0], vn.size()*sizeof(vtnode));
	  ofs.close();
  }
  void load()
  {	    
	  ifstream ifs("tr.bin",ios::binary);
	  unsigned int s;
	  ifs.read((char*)&s, sizeof(unsigned int));
	  vn.resize(s);
	  ifs.read((char*)&vn[0], s*sizeof(vtnode));
	  ifs.close();
	  unused.clear(); //or we could save unused and load that too. 
	  for(int x = 0; x < vn.size(); x++)
		  if(vn[x].used == false) 
			  unused.push_back(x);			  
  }
  
  void del (int in)
  {
	  //mark unused, add index to unused vector etc
  }
  void prn(int pos = 0)
  {		
	if(vn[pos].left) prn(vn[pos].left);
	cout << vn[pos].data << endl;
	if(vn[pos].right) prn(vn[pos].right);	
  }
  void vecprn()
  {
	for(auto x : vn)
		cout << x.data << endl;
  }
};


int main()
{
  vectree v;
  v.ins(10);
  v.ins(5);
  v.ins(7);
  v.ins(15);
  //v.prn();
  vectree v2;
  v.save();
  v2.load();
  v2.prn();
  v2.vecprn();
  return 0;    
}

outputs as tree and then as vector
5
7
10
15

10
5
7
15

[Duthomhas]

Here ya go.

  void prn(int pos = 0) // formatted as an infix s-expression 
  {
    int  L = vn[pos].left;
    int  R = vn[pos].right;
    if (L||R) 
    {
      cout << "(";
      if (L) prn(L); 
      else cout << "()";
      cout << " ";
    }
    cout << vn[pos].data;
    if (L||R) 
    {
      cout << " ";
      if (R) prn(R); 
      else cout << "()";
      cout << ")";
    }
    if (!pos) cout << endl;
  }
  
  void vecprn() // formatted as a list
  {
    auto n = vn.size();
    for (auto v : vn)
    {
      cout << v.data;
      if (--n) cout << ",";
    }
    cout << endl;
  }

((() 5 7) 10 15)
10,5,7,15

:O)

[edit]
Oh, almost forgot: I know people like to #include stuff in bits/, but, just, don’t. Please.

[jonnin]

that is a pile of includes for dumping code from here, actually, so it has things I needed to make posted code from the site work. I don't think I used 90% of that pile, should have trimmed it down. I am not even sure what is in bits anymore, but something someone posted used it.

that is certainly one way to use it. But I don't know that it has much merit over a normal tree approach for small data like equations. They all felt like 'giant volume' pros.

[Duthomhas]

Everything in bits/ is non-standard. It is a GCC-ism, which simply includes everything. Hence, whatever that someone who posted it used from it was anything in the standard library, which could have been much more easily done by simply #including the proper header.

Read more here:
https://stackoverflow.com/a/31816096/2706707


I am unsure what your second paragraph is trying to say.

[jonnin]

I was saying the tree in a vector thing feels like it is more useful for large amounts of data. I am not sure its a very useful toy, but we were talking about it a week or 2 ago and I got curious enough to play a little.

[Duthomhas]

Ah, yes, it is indeed a very useful way to organize a tree, especially for large amounts of data.
+1