/*
 * (C) Copyright Ian D. Romanick 2007
 * All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * on the rights to use, copy, modify, merge, publish, distribute, sub
 * license, and/or sell copies of the Software, and to permit persons to whom
 * the Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.  IN NO EVENT SHALL
 * AUTHORS, COPYRIGHT HOLDERS, AND/OR THEIR SUPPLIERS BE LIABLE FOR ANY CLAIM,
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
 * USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include "vector.h"
#include "aabb.h"

#ifndef NULL
# define NULL 0
#endif

#define MAX_CHILDREN 10

class volume_node;

class rtree_node {
public:
    float volume(void) const
    {
        return box.volume();
    }
    
    bool overlaps(const aabb &a) const
    {
        return box.overlaps(a);
    }

    friend bool compare_node_x(const void *a, const void *b);
    friend bool compare_node_y(const void *a, const void *b);
    friend bool compare_node_z(const void *a, const void *b);

    friend class volume_node;

protected:
    aabb box;
};


class volume_data : public rtree_node {
public:
    volume_data(const aabb &add, const void *d)
    {
        box = add;
        data = d;
    }

    const void *data;
};


union rtchild {
    volume_node *n;
    volume_data *d;
    rtree_node *child;
};

class volume_node : public rtree_node {
public:
    volume_node(void)
    {
        leaf = true;
        used_children = 0;
    }

    float expansion(const aabb &add_box) const;
    volume_node *insert(const aabb &add_box, const void *data);
    float child_cost(const aabb &add_box) const;
    volume_node *do_split(void);


    bool is_full(void) const
    {
        return (used_children == MAX_CHILDREN);
    }

    bool is_leaf(void) const
    {
        return leaf;
    }

    void dump(unsigned);

    friend class volume_rtree_iterator;
    friend class volume_rtree;

private:
    unsigned choose_subtree(const aabb &add_box) const;
    float surface_increase(const aabb &add_box) const;
    void choose_split_axis(void);
    unsigned choose_split_index(void) const;

    void get_AABB_for_groups(unsigned first_group_size, aabb *first_group,
                             aabb *second_group) const;
    float margin_value(unsigned first_group_size) const;
    float overlap_value(unsigned first_group_size) const;
    float area_value(unsigned first_group_size) const;


    bool leaf;

    unsigned used_children;

    union rtchild children[MAX_CHILDREN];
};


struct node_atom {
    node_atom *next;
    unsigned position;

    struct {
        volume_node *node;
        unsigned index;
    } atoms[16];
};

class volume_rtree_iterator {
public:
    volume_rtree_iterator(void)
    {
        atom = NULL;
    }


    volume_rtree_iterator(volume_node *node, int index, const idr_vec4 *_box)
    {
        atom = NULL;

        if (node) {
            push(node, index);
        }

        if (_box != NULL) {
            box.add_point(_box[0]);
            box.add_point(_box[1]);
        }
    }

    void *operator*(void) const
    {
        if (atom == NULL) {
            return NULL;
        }

        const unsigned idx = atom->atoms[atom->position - 1].index;
        volume_node *const n = atom->atoms[atom->position - 1].node;

        return (n->is_leaf()) ? (void *) (n->children[idx].d->data) : NULL;
    }

    volume_rtree_iterator &operator++(void);

    bool operator==(const volume_rtree_iterator &a) const
    {
        if (atom == NULL) {
            return (a.atom == NULL);
        }
        else {
            if (a.atom == NULL) {
                return false;
            }

            const unsigned idx = atom->atoms[atom->position - 1].index;
            volume_node *const n = atom->atoms[atom->position - 1].node;
            const unsigned a_idx = a.atom->atoms[a.atom->position - 1].index;
            volume_node *const a_n = a.atom->atoms[a.atom->position - 1].node;

            return (n == a_n) && (idx == a_idx);
        }
    }

    bool operator!=(const volume_rtree_iterator &a) const
    {
        if (atom == NULL) {
            return (a.atom != NULL);
        }
        else {
            if (a.atom == NULL) {
                return true;
            }

            const unsigned idx = atom->atoms[atom->position - 1].index;
            volume_node *const n = atom->atoms[atom->position - 1].node;
            const unsigned a_idx = a.atom->atoms[a.atom->position - 1].index;
            volume_node *const a_n = a.atom->atoms[a.atom->position - 1].node;

            return (n != a_n) || (idx != a_idx);
        }
    }

private:
    void push(volume_node *n, unsigned i)
    {
        if ((atom == NULL) || (atom->position == 16)) {
            node_atom *a = new node_atom;

            a->next = atom;
            a->position = 0;
            atom = a;
        }

        atom->atoms[atom->position].node = n;
        atom->atoms[atom->position].index = i;
        atom->position++;
    }


    void pop(void)
    {
        if (atom == NULL) {
            return;
        }

        atom->position--;
        if (atom->position == 0) {
            node_atom *a = atom->next;
            
            delete atom;
            atom = a;
        }
    }


    volume_node *get_node(void) const
    {
        if (atom == NULL) {
            return NULL;
        }

        return atom->atoms[atom->position - 1].node;
    }


    unsigned get_index(void) const
    {
        if (atom == NULL) {
            return 0;
        }

        return atom->atoms[atom->position - 1].index;
    }


    void set_index(unsigned idx)
    {
        if (atom != NULL) {
            atom->atoms[atom->position - 1].index = idx;
        }
    }

    struct node_atom *atom;
    aabb box;
};

class volume_rtree {
public:
    volume_rtree(void);

    void insert(const idr_vec4 &position, const void *data);


    volume_rtree_iterator &search(const idr_vec4 *aabb);
    volume_rtree_iterator &end(void)
    {
        return end_iter;
    }

    void dump(void);

private:
    volume_node *root;
    volume_rtree_iterator end_iter;
};
