hash tree

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include "MD5.h"
#define DIGEST_SIZE 4

using namespace std;

class Node{
private:
  unsigned int label[DIGEST_SIZE];
  int counter;
  int fan_out;
  Node **childs;
public:
  Node(int x, unsigned int digest[]):fan_out(x){
    counter = 0;		//deixnei sti prwti adeia thesi tou pinaka. auksanetai otan eisaxthei ena paidi
    if(fan_out > 0){
      childs = new Node*[fan_out];  	//pinakas me deiktes sta paidia enos komvou
    }					//ean o komvos einai fillo, o pinakas tha einai adeios
    else{
      childs = NULL;
    }
    if(digest != NULL){
      this->setDigest(digest);
    }
  }
  
  Node(int x):fan_out(x){
    counter = 0;
    if(fan_out > 0){
      childs = new Node*[fan_out];      
    }                                   
    else{
      childs = NULL;
    }
  }
  
  Node(int x, int levels_to_leaf):fan_out(x){
    counter = 0;
    if(fan_out > 0){
      if(levels_to_leaf != 0){
        childs = new Node*[fan_out];
        childs[0] = new Node(fan_out, levels_to_leaf - 1);
      }
      childs = NULL;
    }
    else{
      childs = NULL;
    }
  }
  
  ~Node(){
    for(int i = 0; i < fan_out; i++)
      delete childs[i];
    delete[] childs;
  }
  
  void setDigest(unsigned int* x){
    for(int i = 0; i < DIGEST_SIZE; i++)
      label[i] = x[i];
  }
  
  int insertDigest(unsigned int* x, MD5_CTX ctx, int levels_to_leaf){    //0 fail, -1 success kai paraxthike digest, 1 success, exw keno xwro
    int check;
    if(childs != NULL){
      if(counter == fan_out){
        return 0;
      }
      else{
        check = childs[counter]->insertDigest(x, ctx, levels_to_leaf - 1);
        switch(check){
          case 0:
            return 0;
          case 1:
            return 1;
          case -1:
            counter++;
            if(counter == fan_out){
              MD5Init(&ctx);
              for(int i =0; i < fan_out; i++)
                MD5Update(&ctx,(char*)getChildDigest(i),DIGEST_SIZE);
              MD5Final(label, &ctx);
              return -1;
            }
            else{
              childs[counter] = new Node(fan_out, levels_to_leaf - 1);
            }
        }
      }
    }
    else{       //exoume ftasei se paidi
      setDigest(x);
      return -1;
    }
  }
  
  int forceDigest(MD5_CTX ctx){		//0 fail; -1 den exei digest, 1 exei digest
    int check;
    if(label != NULL){ //exw digest
      return 1;
    }
    else{ 
      check = forceDigest(ctx);
      switch(check){
	case 0:
	  return 0;
	case 1:
	  return 1;
	case -1:
	  MD5Init(&ctx);
	  for(int i = 0; i < counter; i++)
	    MD5Update(&ctx,(char*)getChildDigest(i),DIGEST_SIZE);
	  MD5Final(label, &ctx);
	  setDigest(label);
	  return -1;
      }
    }
  }
  
  bool insertChild(Node* child){
    if(counter < fan_out){
      childs[counter++] = child;
      return true;
    }
    else{
      return false;
    }
  }
  
  unsigned int* getDigest(){
    return label;
  }
  
  int getCounter(){
    return counter;
  }
  
  unsigned int* getChildDigest(int x){
    return childs[x]->getDigest();
  }
  
  void compare(Node* node){
    
  }
};


class Tree{
private:
  Node *root;
  int fan_out;
  int levels_to_leaf;
  Node *active_node;
  MD5_CTX context;
public:
  Tree(int x, MD5_CTX ctx):fan_out(x),context(ctx){
    levels_to_leaf = 1;
    root = new Node(fan_out,0);
//     active_node = new Node(fan_out,0);
//     if(!root->insertChild(active_node)){
//       cout << "error inserting child" << endl;
//     }
  }
  ~Tree(){
    delete root;
   }
   
   bool insertDigest(unsigned int *x){
     int check;
     check = root->insertDigest(x,context,levels_to_leaf); 
     switch(check){
       case -1:
       levels_to_leaf++;
       active_node = root;
       root = new Node(fan_out,0);
       root->insertChild(active_node);
       return true;
       case 0:
	 return false;
       case 1:
	 return true;
     }
   }
   
   bool forceDigest(MD5_CTX ctx){
     int check;
     check = root->forceDigest(ctx); 
     switch(check){
       case 1:
	return true;
       case 0:
	 return false;
     }
   }
   
   bool insertChild(Node* child){
    if(root->insertChild(child))
      return true;
    else
      return false;
  }  
};

/////////////////////////////////////////////////////////////////////////////////////////////////

int main(int argc, char* argv[]){
  
  FILE* first_file;
  FILE* second_file;
  size_t read;
  unsigned int iPage = 1;
  unsigned int page_size;
  int tree_fan_out;
  unsigned int digest[DIGEST_SIZE];
  Tree *first_tree;
  Tree *second_tree;
  MD5_CTX context;
  
  if(argc != 5){
    cout << "Please execute as: " << argv[0] << " (file 1 name) (file 2 name) (page size) (tree fan-out)" << endl;
    return EXIT_FAILURE;
  }
  
  page_size = atoi(argv[3]);
  tree_fan_out = atoi(argv[4]);
  if(tree_fan_out < 2){
    cout << "Invalid Tree fan out" << endl;
    return EXIT_FAILURE;
  }
  char buffer[page_size];
  char concat[4*tree_fan_out + 1];  	//to megethos tis parathesis twn sinopsewn twn paidiwn enos komvou einai 
  size_t buffsize = sizeof(buffer);	//iso me 4(megethos tis kathe sinopsis) epi ton paragonta diakladwsis sin to \0
  //diavasma prwtou arxeiou
  first_file = fopen(argv[1], "rb+");
  if(first_file == NULL){
    perror("Failed to open file");
    return EXIT_FAILURE;
  }
  first_tree = new Tree(tree_fan_out,context);
  
  do{
    read = fread(buffer, 1, sizeof(buffer), first_file);
    if( read > 0) { 
      if(read < buffsize){
	memset(buffer + read, 0, buffsize - read);		//zero padding sti teleutaia selida
      }
      cout << "read page " << iPage << " with size " << read << endl;
      iPage++;
      MD5Update(&context,buffer,strlen(buffer));
      MD5Final(digest, &context);
      if(!first_tree->insertDigest(digest)){
	cout << "Error inserting in first tree" << endl;
	return EXIT_FAILURE;
      }
    }
  }while (read == buffsize);
  if(ferror(first_file))
    perror("Error occured during reading first file");
  fclose(first_file);
  first_tree->forceDigest(context);
  
  //diavasma deuterou arxeiou
  second_file = fopen(argv[2], "rb+");
  if(second_file == NULL){
    perror("Failed to open file");
    return EXIT_FAILURE;
  }
  second_tree = new Tree(tree_fan_out,context);
  
  do{
    read = fread(buffer, 1, sizeof(buffer), second_file);
    if( read > 0) { 
      if(read < buffsize){
	memset(buffer + read, 0, buffsize - read);		//zero padding sti teleutaia selida
      }
      cout << "read page " << iPage << " with size " << read << endl;
      iPage++;
      MD5Update(&context,buffer,strlen(buffer));
      MD5Final(digest, &context);
      if(!second_tree->insertDigest(digest)){
	cout << "Error inserting in second tree" << endl;
	return EXIT_FAILURE;
      }
    }
  }while (read == buffsize);
  if(ferror(second_file))
    perror("Error occured during reading second file");
  fclose(second_file);
  second_tree->forceDigest(context);
  ///Initiate Compare Stage
  ///Print Results
  return 0;
}