#ifndef INDEX_H
#define INDEX_H

#include "io.h"
#include "record.h"
#include "tape.h"
#include <inttypes.h>
#include <stdbool.h>

#define SIZEOF_ENTRIES(n) (sizeof(btree_node_header_t) + (sizeof(btree_entry_t) - sizeof(page_t))*(n) + ((n) > 0 ? 1 : 0) * sizeof(page_t))
#define NODE_SIZE(node) SIZEOF_ENTRIES(node->header.entries)
#define NODE_SIZE_MAX (PAGE_SIZE - sizeof(btree_node_header_t))
#define NODE_ENTRY_OFFSET(n) (sizeof(btree_entry_t) - sizeof(page_t))*(n)

#define NODE_ENTRY(buffer, n) ((btree_entry_t*)((char*)buffer + NODE_ENTRY_OFFSET(n)))
#define ENTRY_INDEX(buffer, entry) (((char*)buffer - (char*)entry) / (sizeof(btree_entry_t) - sizeof(page_t)))

#define NODE_IS_ROOT 1
#define NODE_IS_LEAF 2

#define BTREE_ERR_CANNOT_OPEN_FILE    -1
#define BTREE_ERR_PAGE_SIZE_DIFFERENT -2

#define BTREE_OPTIMIZE_RECORDS_MIN 1000
#define BTREE_OPTIMIZE_THRESHOLD   0.1

typedef struct {
    size_t d;         /* 8 bytes long */
    size_t page_size; /* 8 bytes long */
    page_t root;      /* 8 bytes long */
    char   main[256]; /* 256 bytes long */
    size_t records;   /* 8 bytes long */
    size_t changes;   /* 8 bytes long */
} btree_header_t;     /* 296 bytes long */

typedef struct {
    uint16_t flags;
    uint16_t entries;
} btree_node_header_t;

typedef struct {
    btree_node_header_t header;
    char                entries[NODE_SIZE_MAX];
    page_t              page;
} btree_node_t;

typedef struct {
    page_t       left;
    record_key_t key;
    offset_t     location;
    page_t       right;
} btree_entry_t;

typedef struct {
    btree_node_t  node;
    btree_entry_t *entry;
    unsigned      position;
} btree_stack_elem_t;

typedef struct {
    file_t         *file;
    tape_t         *main;
    btree_header_t header;
    struct {
        btree_stack_elem_t *current;
        btree_stack_elem_t stack[100];
    } trace;
} btree_t;

typedef struct {
    page_t left;
    page_t right;

    btree_entry_t *left_entry;
    btree_entry_t *right_entry;
} btree_siblings_t;

int btree_init(btree_t *tree, char* filename, size_t d);
int btree_open(btree_t *tree, char* filename);

void btree_optimize(btree_t *tree);

page_t btree_insert(btree_t *tree, record_t record);
page_t btree_remove(btree_t *tree, record_key_t key);
bool   btree_update(btree_t *tree, record_key_t key, record_t record);
page_t btree_find(btree_t *tree, record_key_t key, btree_entry_t *entry, btree_node_t *node, unsigned *index);

page_t btree_read_record(btree_t *tree, record_key_t key, record_t *record);

btree_entry_t *btree_get_entry(btree_node_t* node, unsigned n);

void btree_flush(btree_t* tree);
void btree_close(btree_t* tree);

#endif /* INDEX_H */