/* Demo of saving a data structure into a file
 * Binary data files:
 * 	Just need to be consistent about where everything goes
 * 	Make sure input routine doesn't change anything
 * 	What if you copied it to a big endian machine?
 * 
 */

#pragma once

#include<iostream>
#include<cmath>
#include<random>
#include<graphviz/cgraph.h>
#include<graphviz/gvc.h>
using namespace std;

class Heap {
	int *heap_memory;
	size_t end = 0;
	size_t allocation = 100;
	public:
	void load_failed(){
			perror("open");
			allocation = 0;
			end = 0;
	}
	Heap(const char* filename){
		int fd = open(filename, O_RDONLY);
		if(fd == -1){
			load_failed();
			return;
		}
		if(sizeof(end) != read(fd, &end, sizeof(end))){
			load_failed();
			return;
		}
		allocation = end;
		heap_memory = (int*)malloc(sizeof(int) * end);
		ssize_t total_read = 0;
		ssize_t expected_total = end * sizeof(int);
		while(true){
			ssize_t readlen = read(fd, heap_memory, end * sizeof(int));
			total_read += readlen;
			if(total_read == expected_total)
				break;
			if(readlen < 1) {
				end = 0;
				break;
			}
		}
		close(fd);
	}
	Heap() {
		heap_memory = (int*)malloc(sizeof(int) * 100);
	}
	void insert(int new_number){
		if(end >= allocation){
			allocation *= 2;
			heap_memory = (int*)realloc(heap_memory, allocation * sizeof(int));
		}
		heap_memory[end++] = new_number;
		reorder_up(end - 1);
		//		print_heap_as_array();
	}
	void reorder_up(size_t idx){
		//		cout << "reorder_up:  ";
		//		print_heap_as_array();
		if(!idx)
			return;
		size_t parent_idx = (idx-1)/2;
		if(heap_memory[parent_idx] >= heap_memory[idx])
			return;
		int tmp = heap_memory[parent_idx];
		heap_memory[parent_idx] = heap_memory[idx];
		heap_memory[idx] = tmp;
		reorder_up(parent_idx);
	}
	void reorder_down(size_t idx){
		//		cout << "reorder_up:  ";
		//		print_heap_as_array();
		size_t lchild = idx * 2 + 1;
		size_t rchild = lchild + 1;
		if(rchild >= end){
			heap_memory[idx] = heap_memory[end - 1];
			reorder_up(idx);
			return;
		}
		size_t schild = rchild;
		if(heap_memory[lchild] > heap_memory[rchild])
			schild = lchild;
		heap_memory[idx] = heap_memory[schild];
		reorder_down(schild);
	}
	int get_max(){
		if(end)
			return heap_memory[0];
	}
	int pop(){
		int retval = heap_memory[0];
		reorder_down(0);
		end--;
		return retval;
	}
	size_t size(){
		return end;
	}
	void print_heap_as_array(){
		for(int i = 0; i < end; i++)
			cout << heap_memory[i] << " ";
		cout << endl;
	}
	~Heap(){
		free(heap_memory);
	}
	void make_image_recur(Agraph_t *g, Agnode_t *parent, size_t place){
		char number[32];
		sprintf(number, "%d\n(%lu)", heap_memory[place], place);
		Agnode_t *us = agnode(g, number, 1);
		if(parent)
			Agedge_t *e = agedge(g, parent, us, (char*)"", 1);
		size_t lchild = place * 2 + 1;
		size_t rchild = lchild + 1;
		if(lchild < end)
			make_image_recur(g, us, lchild);
		if(rchild < end)
			make_image_recur(g, us, rchild);
	}

	void make_image(string name){
		Agraph_t *g;
		g = agopen((char*)"G", Agdirected, 0);
		Agsym_t *color_attr = agattr(g, AGNODE, (char*)"color", (char*)"black");

		// Go through the tree, and add all our nodes!
		// Add our own node
		// If there is a left subtree, add the left subtree
		// If there is a right subtree, add the right subtree
		make_image_recur(g, 0, 0);

		GVC_t* gvc = gvContext();
		gvLayout(gvc, g, "dot");
		agwrite(g, stdout);	;
		gvRenderFilename(gvc, g, "png", (name + ".png").c_str());
		gvFreeLayout(gvc, g);
		agclose(g);
	}
	bool save(const char* filename){
		/* Save the heap data
 		 * Also save the size of the heap 
 		 *	Format:
 		 *		Size of the heap in the file (8 byte little-endien unsigned integer)
 		 *		Heap data as a series of 4-byte signed integers 
 		 */
		int fd = open(filename, O_WRONLY | O_CREAT | O_TRUNC, 0644);
		if(fd == -1) { // It didn't work 
			perror("open");
			return false;
		}
		if(8 != write(fd, &end, sizeof(end))){ // if we could open the file, but not write to it?
			perror("write");
			close(fd);
			return false;
		}
		// Note:  Take a look at load.  write has the same limit on Linux, will transfer only 2gb at once
		if(end * sizeof(int) != write(fd, heap_memory, end * sizeof(int))) {
			perror("write");
			close(fd);
			return false;
		}
		close(fd);
		return true;
	}

};