// *****************************************************************************
// File: rtree.h
// Definition of the "r-tree"
// *****************************************************************************

#ifndef __RTREE
#define __RTREE

#include "typedefs.h"
#include "node.h"
#include "stack.h"
#include "page.h"
#include "set.h"
// #include "graphic.h"
#include "geometr.h"

class r_tree {
private:
   int ftree;		// file desrcriptor
   long treesize;	// Size of tree file.
   node *n;		// Nodes mapped from tree file.
   long root_pagenumber;
   int minimum_number_of_entries;
   int maximum_number_of_entries;
   int tree_height;
   long num_objects;

   enum { position, sphere, rect, convex } selection_type;
   point search_rect[2];   // used in rectangle search
   point search_pt;        // used in sphere search
   coord search_r;         // used in sphere search
   int   search_nop;       // used in convex polygon search (2D only!)
   point *search_pts;      // used in convex polygon search (2D only!)

   long_stack visited_node, visited_entry;
   page_manager *manager;
   geometr *geom;

   void clear_stacks();
   void extend_tree();
   void pick_seeds(r_entry *list, int &list_length, r_entry &e1,
      r_entry &e2);
   int pick_next(r_entry *list, int &list_length, point *rec1,
      point *rec2, r_entry &temp_entry);
   long split_node(long temp, r_entry temp_entry);
   long choose_node(long temp, r_entry new_entry, int level);
   long adjust_tree(long temp, long temp2);
   void add_subtree(r_entry new_entry, int level);
   long find_leaf(long temp, r_entry old_entry);
   void condense_tree(long temp);

   boolean overlap(r_entry e);
   void perform_select(long_set *selection);
   long perform_First();
public:
   r_tree(char *name, int m, int M);                     // Create new rtree
   r_tree(char *name);                                   // Open existing rtree

   void print_rtree_info(); 
   void printstat();
   long nr_of_objects() { return num_objects; }
   void analyse();
   boolean domain_objects(point domain[2]);

   //Update the "r-tree".
   void add_object(r_entry new_entry);
   void del_object(r_entry old_entry);

   //Search for objects.
   void select(long_set *selection, point pt, coord radius);// within sphere
   void select(long_set *selection, point rect[2]);         // within rectangle
   void select(long_set *selection, int nop, point *pts);   // within convex p.

   long First(point search_rect[2]);
   long First(point search_pt, coord radius);
   long Next();

   // void display_tree(graphic *x, point rect[2]);            // Test function.

   ~r_tree();                                               // Close the file.
};

#endif