//*****************************************************************************
// File: rtree.cc
// Implementation of the "r-tree"
//*****************************************************************************

#include <math.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <sys/types.h>
#include <sys/file.h>
#include <fcntl.h>
#include <stdio.h>
#include <values.h>

#include "rtree.h"

extern "C" {
#include <sys/mman.h>

int munmap(char *, long);
}

int	rtree_ro= 0;


void r_tree::printstat()
{
   struct rusage ru;

   getrusage(RUSAGE_SELF, &ru);
   printf("time: user= %ld.%06ld sec ",
	  ru.ru_utime.tv_sec, ru.ru_utime.tv_usec);
   printf("system= %ld.%06ld sec\n",
	  ru.ru_stime.tv_sec, ru.ru_stime.tv_usec);
   printf("maxrss=%d textmemory size=%d\n", ru.ru_maxrss, ru.ru_ixrss);
   printf("unshared data size=%d unshared stack size=%d\n",
	  ru.ru_idrss, ru.ru_isrss);
   printf("page reclaims=%d ", ru.ru_minflt);
   printf("page faults=%d\n", ru.ru_majflt);
   printf("# swaps=%d block in=%d block out=%d\n",
	  ru.ru_nswap, ru.ru_inblock, ru.ru_oublock);
   printf("messages sent=%d messages received=%d ",
	  ru.ru_msgsnd, ru.ru_msgrcv);
   printf("signals received=%d\n", ru.ru_nsignals);
   printf("voluntary context switches=%d involuntary context switches=%d\n",
	  ru.ru_nvcsw, ru.ru_nivcsw);
}

// Constructors of the r-tree 

r_tree::r_tree(char *name):visited_node(), visited_entry()
// the two stacks are automatically created (and deleted).
{
   int page_size;
   char *TreeName, *PageName;

// printf("Size of node is %d\n",sizeof(node));
   TreeName = new char[strlen(name) + 7];
   sprintf(TreeName, "%s.rtree", name);
   PageName = new char[strlen(name) + 7];
   sprintf(PageName, "%s.rpage", name);

   if ((geom = new geometr()) == NULL) {
      fprintf(stderr, "Index tree: Out of memory (for new geometr).\n");
      exit(1);
   }
   sprintf(PageName, "%s.rpage", name);
   if ((manager = new page_manager(PageName)) == NULL) {
      fprintf(stderr, "Index tree: Out of memory (for new page_manager).\n");
      exit(1);
   }
   if ((ftree = open(TreeName, rtree_ro ? O_RDONLY: O_RDWR)) != -1) {
      lseek(ftree, 0L, L_SET);
      read(ftree, &page_size, sizeof(int));
      if (page_size != PAGE_SIZE) {
         fprintf(stderr,
            "Tree created with page-size %d, however current size is %d\n",
            page_size, PAGE_SIZE);
         exit(1);
      }
      read(ftree, &minimum_number_of_entries, sizeof(int));
      read(ftree, &maximum_number_of_entries, sizeof(int));
      read(ftree, &root_pagenumber, sizeof(long));
      read(ftree, &tree_height, sizeof(int));
      read(ftree, &num_objects, sizeof(long));
   } else {
      fprintf(stderr, "Can't open file %s.\n", TreeName);
      exit(1);
   }
   treesize=lseek(ftree, 0L, L_XTND);
   if ((n = (node *) mmap(0,treesize, (PROT_READ|(rtree_ro ? 0: PROT_WRITE)),
	MAP_SHARED,ftree,0))
           == (node *)-1) {
      fprintf(stderr, "R-tree file %s can't be mapped.\n", TreeName);
      exit(1);
   }
   delete TreeName;
   delete PageName;
}


r_tree::r_tree(char *name, int m, int M):visited_node(), visited_entry()
// the two stacks are automatically created (and deleted).
{
   char *TreeName, *PageName, c='x';

// printf("Size of node is %d\n",sizeof(node));
   TreeName = new char[strlen(name) + 7];
   sprintf(TreeName, "%s.rtree", name);
   PageName = new char[strlen(name) + 7];
   sprintf(PageName, "%s.rpage", name);

   if ((geom = new geometr()) == NULL) {
      fprintf(stderr, "Index tree: Out of memory (for new geometr).\n");
      exit(1);
   }
   if ((manager = new page_manager(PageName,
      (long)(1+(4*sizeof(int)+2*sizeof(long))/PAGE_SIZE))) == NULL) {
      fprintf(stderr, "Index tree: Out of memory (for new page_manager).\n");
      exit(1);
   }
   if ((m >= 2) && (m <= (int) ceil((double) ((double) M) / 2)) &&
      (M >= 3) && (M <= MAX)) {
      minimum_number_of_entries = m;
      maximum_number_of_entries = M;
      root_pagenumber = NULL_PAGE;
      tree_height = 0;
      num_objects = 0L;
      if ((ftree = creat(TreeName, PERMS)) == -1) {
         printf("R-tree creator: could not create %s.\n", TreeName);
         exit(1);
      } else {
	 close(ftree);
	 if ((ftree = open(TreeName, rtree_ro ? O_RDONLY: O_RDWR)) == -1) {
            printf("R-tree creator: could not open %s.\n", TreeName);
            exit(1);
         }
      }
      lseek(ftree,(long)(PAGE_SIZE-1),L_XTND);
      write(ftree,&c,1);
      treesize=lseek(ftree,0L,L_XTND);
      if ((n = (node *) mmap(0,treesize, (PROT_READ|(rtree_ro ? 0: PROT_WRITE)),
         MAP_SHARED,ftree,0)) == (node *)-1) {
         fprintf(stderr, "R-tree file %s can't be mapped.\n", TreeName);
         exit(1);
      }
   } else {
      printf("Illegal values of m and/or M.\n");
      printf("The value of m (=%d) must be between 2 and %d (included)\n", m, 
         (int) ceil((double) ((double) M) / 2));
      printf("The value of M (=%d) must be between 3 and %d (included)\n", M,
         MAX);
      exit(1);
   }
   delete TreeName;
   delete PageName;
}


r_tree::~r_tree()
// Destructor of the r-tree
{
   int page_size = PAGE_SIZE;

   clear_stacks();
   munmap((char*)n, treesize);
   lseek(ftree, 0L, L_SET);
   write(ftree, &page_size, sizeof(int));
   write(ftree, &minimum_number_of_entries, sizeof(int));
   write(ftree, &maximum_number_of_entries, sizeof(int));
   write(ftree, &root_pagenumber, sizeof(long));
   write(ftree, &tree_height, sizeof(int));
   write(ftree, &num_objects, sizeof(long));
   close(ftree);
   delete geom;
   delete manager;
}


void r_tree::extend_tree()
{
   char c='x';

   if ( -1 == munmap((char*) n, treesize)) {
      printf("Error in extend_tree: munmap\n"); exit(1);}
   if (-1 == lseek(ftree,(long)((GROW_PAGES*PAGE_SIZE)-1),L_XTND)) {
      printf("Error in extend_tree: lseek 1\n"); exit(1);}
   if (-1 == write(ftree,&c,1)) {
      printf("Error in extend_tree: write\n"); exit(1);}
   if (-1 == (treesize=lseek(ftree,0L,L_XTND))) {
      printf("Error in extend_tree: lseek 2\n"); exit(1);}
   if ((n = (node *) mmap(0,treesize,(PROT_READ|PROT_WRITE),
      MAP_SHARED,ftree,0)) == (node *)-1) {
      fprintf(stderr, "The tree file can't be mapped after extension.\n");
      exit(1);
   }
printf("\n Tree extended, new size %ld\n", treesize);
}


void r_tree::print_rtree_info()
{
   printf("______________________________________________________________\n");
   printf("                                                              \n");
   printf("R-TREE: m=%d, M=%d (maximum=%d), #objects=%d\n",
      minimum_number_of_entries, maximum_number_of_entries, MAX, num_objects);
   printf("        root_no=%d, height=%d, page size=%d (of which waisted=%d)\n",
      root_pagenumber, tree_height, PAGE_SIZE, UNUSED);
   printf("______________________________________________________________\n");
}


void r_tree::clear_stacks()
{
   node *temp;

   visited_entry.clear();
   while (!visited_node.empty()) {
      temp = (node *) visited_node.pop();
      delete temp;
   }
}


void r_tree::pick_seeds(r_entry *list, int &list_length,
   r_entry &entry1, r_entry &entry2)
// Update tree
{
   coord area1, area2, d, max_d;
   int i, j, e1_no, e2_no;
   point res_rect[2];

   max_d = (coord)-MAXFLOAT;
   e1_no=0; e2_no=1;
   for (i = 1; i < list_length - 1; i++) {
      area1 = geom->calc_area(list[i].mbr);
      for (j = i + 1; j < list_length; j++) {
	 area2 = geom->calc_area(list[j].mbr);
	 geom->calc_rect(list[i].mbr, list[j].mbr, res_rect);
	 d = geom->calc_area(res_rect) - area1 - area2;
	 if (d > max_d) {
	    max_d = d;
	    e1_no = i;
	    e2_no = j;
	 }
      }
   }
   entry1 = list[e1_no];
   entry2 = list[e2_no];
   --list_length;
   if (e2_no == list_length) {
      --list_length;
      if (e1_no != list_length)
	 list[e1_no] = list[list_length];
   } else {
      if (e1_no != list_length)
	 list[e1_no] = list[list_length];
      --list_length;
      if (e2_no != list_length)
	 list[e2_no] = list[list_length];
   }
}


int r_tree::pick_next(r_entry *list, int &list_length, point *rec1,
   point *rec2, r_entry &temp_entry)
{
   int i, e_no = 0, verz = 1;
   coord area1, area2, d1, d2, dd = -1.0;
   point res_rect1[2], res_rect2[2];

   area1 = geom->calc_area(rec1);
   area2 = geom->calc_area(rec2);
   for (i = 0; i < list_length; i++) {
      geom->calc_rect(rec1, list[i].mbr, res_rect1);
      geom->calc_rect(rec2, list[i].mbr, res_rect2);
      d1 = geom->calc_area(res_rect1) - area1;
      d2 = geom->calc_area(res_rect2) - area2;
      if (fabs(d1 - d2) > dd) {
	 dd = fabs(d1 - d2);
	 e_no = i;
	 verz = (d1 < d2) ? 1 : 2;
      }
   }
   temp_entry = list[e_no];
   --list_length;
   if (e_no < list_length)
      list[e_no] = list[list_length];
   return verz;
}


long r_tree::split_node(long temp, r_entry new_entry)
{
   int entry_no, list_length = maximum_number_of_entries + 1;
   long temp2;
#if 0
   r_entry entry1, entry2, temp_entry, list[list_length];
#else
   r_entry entry1, entry2, temp_entry, *list= new r_entry[list_length];
#endif
   point rec1[2], rec2[2];

   temp2 = manager->new_page();
   if ((temp2+1)*PAGE_SIZE > treesize) extend_tree();

   n[temp].copy_to_list(list);
   n[temp].clear();
   n[temp2].clear();

   list[list_length - 1] = new_entry;
   pick_seeds(list, list_length, entry1, entry2);
   n[temp].add_entry(entry1);
   n[temp2].add_entry(entry2);
   geom->calc_rect(entry1.mbr, entry1.mbr, rec1);
   geom->calc_rect(entry2.mbr, entry2.mbr, rec2);
   while ((list_length > 0) &&
      (minimum_number_of_entries - n[temp].nr_of_entries < list_length) &&
      (minimum_number_of_entries - n[temp2].nr_of_entries < list_length)) {
      if (pick_next(list, list_length, rec1, rec2, temp_entry) == 1) {
         n[temp].add_entry(temp_entry);
	 geom->calc_rect(rec1, temp_entry.mbr, rec1);
      } else {
         n[temp2].add_entry(temp_entry);
	 geom->calc_rect(rec2, temp_entry.mbr, rec2);
      }
   }
   if (n[temp].nr_of_entries < minimum_number_of_entries)
      while (list_length > 0) n[temp].add_entry(list[--list_length]);
   else
      while (list_length > 0) n[temp2].add_entry(list[--list_length]);
#if 1
   delete(list);
#endif
   return temp2;
}


long r_tree::choose_node(long temp, r_entry new_entry, int level)
// Find the best node at level 'level' to add new entry, a (sub)tree.
{
   coord min_area, temp_area, min_enl_area, enl_area;
   int min_entry;
   point res_rect[2];

   while (visited_node.length() + 1 < level) {
      // While not on leaf-level: choose best child node.
      min_entry = 0;
      min_area = geom->calc_area(n[temp].entry[0].mbr);
      geom->calc_rect(n[temp].entry[0].mbr, new_entry.mbr, res_rect);
      min_enl_area = geom->calc_area(res_rect) - min_area;
      for (int e = 1; e < n[temp].nr_of_entries; e++) {
	 temp_area = geom->calc_area(n[temp].entry[e].mbr);
	 geom->calc_rect(n[temp].entry[e].mbr, new_entry.mbr, res_rect);
	 enl_area = geom->calc_area(res_rect) - temp_area;
	 if (enl_area <= min_enl_area) {
	    if ((enl_area < min_enl_area) || (temp_area < min_area)) {
	       min_area = temp_area;
	       min_enl_area = enl_area;
	       min_entry = e;
	    }
	 }
      }
      // Memorize visited node and entry.
      visited_node.push((long) temp);
      visited_entry.push((long) min_entry);
      // Go to choosen child node.
      temp = n[temp].entry[min_entry].id;
   }
   return temp;
}


long r_tree::adjust_tree(long temp, long temp2)
// Update ancestors after the addition of new entry (or sub-tree).
{
   long parent, parent2;
   int entry_no;
   r_entry temp_entry;
   point new_rect[2];

   while (!visited_node.empty()) {
      parent =  visited_node.pop();
      entry_no =  visited_entry.pop();
      // Update the MBR of the node in the parent node.
      n[temp].total_rectangle(new_rect);
      if (!geom->rect_equal(new_rect, n[parent].entry[entry_no].mbr)) {
	 // rectangle of the child node has changed.
	 geom->rect_cpy(new_rect, n[parent].entry[entry_no].mbr);
      }
      // Add the entry of the splited node to the parent node.
      if (temp2 != NULL) {
	 n[temp2].total_rectangle(temp_entry.mbr);
	 temp_entry.id = temp2;
	 if (n[parent].nr_of_entries < maximum_number_of_entries) {
	    n[parent].add_entry(temp_entry);
	    parent2 = NULL;
	 } else
	    parent2 = split_node(parent, temp_entry);
      } else
	 parent2 = NULL;
      // Update the parents of the parent nodes.
      temp = parent;
      temp2 = parent2;
   }
   return temp2;
}


void r_tree::add_subtree(r_entry new_entry, int level)
//Insert a subtree into the tree.
{
   long root, root2, temp, temp2;
   r_entry temp_entry;

   if (root_pagenumber == NULL_PAGE) {
      root = root_pagenumber = manager->new_page();
      if ((root+1)*PAGE_SIZE > treesize) extend_tree();
      n[root].clear();
      n[root].add_entry(new_entry);
      tree_height++;
   } else {
      // Choose best leaf or node.
      root = root_pagenumber;
      temp = choose_node(root, new_entry, level);
      // Add entry.
      if (n[temp].nr_of_entries < maximum_number_of_entries) {
	 n[temp].add_entry(new_entry);
	 temp2 = NULL;
      } else {
	 temp2 = split_node(temp, new_entry);
      }
      root2 = adjust_tree(temp, temp2); // Update ancestors.
      if (root2 != NULL) { // Update tree (extend with new top-level root).
         // Create the new root.
	 root_pagenumber = manager->new_page();
         if ((root_pagenumber+1)*PAGE_SIZE > treesize) extend_tree();
         n[root_pagenumber].clear();
         // Add the old root.
	 n[root].total_rectangle(temp_entry.mbr);
	 temp_entry.id = root;
	 n[root_pagenumber].add_entry(temp_entry);
         // Add the new brother of old root.
	 n[root2].total_rectangle(temp_entry.mbr);
	 temp_entry.id = root2;
	 n[root_pagenumber].add_entry(temp_entry);
	 tree_height++;
      }
   }
}


void r_tree::add_object(r_entry new_entry)
// Insert an object into the 'r-tree'.
{
   num_objects++;
   clear_stacks();
   add_subtree(new_entry, tree_height);
}


long r_tree::find_leaf(long temp, r_entry old_entry)
{
   int entry_no;
   boolean found = false;

   visited_node.push((long) temp);
   visited_entry.push((long) (-1));
   while (!found && !visited_node.empty()) {
      temp = (long) visited_node.pop();
      entry_no = (int) visited_entry.pop();
      entry_no++; // Examine next entry.
      while (!found && (entry_no < n[temp].nr_of_entries)) {
         if (geom->cover(n[temp].entry[entry_no].mbr, old_entry.mbr)) {
            if (visited_node.length() + 1 < tree_height) {
               visited_node.push((long) temp);
               visited_entry.push((long) entry_no);
               temp = n[temp].entry[entry_no].id;
               entry_no = 0;
            } else {
               if (n[temp].entry[entry_no].id == old_entry.id) found = true;
                  else entry_no++;
            }
         } else entry_no++;
      }
   } 
   return found ? temp : NULL_PAGE;
}


void r_tree::condense_tree(long temp)
// Update ancestors after the removal of new entry (or sub-tree).
{
   long parent;
   int entry_no;
   point new_rect[2];
   long_stack *deleted_node;

   deleted_node = new long_stack();
   deleted_node->clear();
   // Update ancestors and remove under-occupied nodes.
   while (!visited_node.empty()) {
      parent = visited_node.pop();
      entry_no = (int) visited_entry.pop();
      if (n[temp].nr_of_entries >= minimum_number_of_entries) {
	 // Update MBR of the node in the parent.
	 n[temp].total_rectangle(new_rect);
	 if (!geom->rect_equal(new_rect, n[parent].entry[entry_no].mbr)) {
	    // rectangle of the child node has changed.
	    geom->rect_cpy(new_rect, n[parent].entry[entry_no].mbr);
	 }
      } else {
	 // Remove node and update the parent.
	 n[parent].del_entry(n[parent].entry[entry_no]);
	 deleted_node->push((long) temp);
      }
      // Update the parent of the parent node.
      temp = parent;
   }
   // Re - insert deleted subroots.
   while (!deleted_node->empty()) {
      temp = deleted_node->pop();
      for (entry_no = 0; entry_no < n[temp].nr_of_entries; entry_no++)
	 add_subtree(n[temp].entry[entry_no],
            tree_height - deleted_node->length());
      manager->dispose_page(temp);
      n[temp].clear();
   }
   delete deleted_node;
}


void r_tree::del_object(r_entry old_entry)
// Remove an object from the 'r-tree'.
{
   long temp, root;

   if (root_pagenumber == NULL_PAGE) return;

   clear_stacks();
   root = root_pagenumber;
   temp = find_leaf(root, old_entry);
   if (temp == NULL_PAGE) {
      printf("del_object: Warning entry not found!\n");
   } else {
      n[temp].del_entry(old_entry); // Delete entry.
      condense_tree(temp); // Update tree.
      num_objects--;
      // Shorten tree.
      if ((tree_height > 1) && (n[root].nr_of_entries == 1)) {
         root_pagenumber = n[root].entry[0].id;
         manager->dispose_page(root);
         n[root].clear();
         tree_height--;
      } else if ((tree_height == 1) && (n[root].nr_of_entries == 0)) {
         root_pagenumber = NULL_PAGE;
         manager->dispose_page(root);
         n[root].clear();
         tree_height--;
      }
   }
}

// Search for objects

void r_tree::select(long_set *selection, point pt, coord radius = 0.0)
// Select the objects within a sphere (centre is pt, radius is r).
// Return with the complete set of id's.
{
   if (radius == 0.0)
      selection_type = position;
   else
      selection_type = sphere;
   geom->pt_cpy(pt, search_pt);
   search_r = radius;
   perform_select(selection);
}


void r_tree::select(long_set *selection, point rectangle[2])
// Select the objects within a rectangle.
// Return with the complete set of id's.
{
   selection_type = rect;
   geom->rect_cpy(rectangle, search_rect);
   perform_select(selection);
}


void r_tree::select(long_set *selection, int nop, point *pts)
// Select the objects within a convex polygon (2D) with fixed implementation.
// Return with the complete set of id's.
{
   selection_type = convex;
   search_nop = nop;
   search_pts = pts;
   perform_select(selection);
}


inline boolean r_tree::overlap(r_entry e)
// Test whether there is overlap between the current search region and
// the mbr in entry e. The type and parameters of the current search region are
// object state variables.
{
   switch(selection_type) {
   case rect:
      return (geom->overlap(e.mbr, search_rect));
   case position:
      return (geom->point_inside(e.mbr, search_pt));
   case sphere:
      return (geom->overlap(e.mbr, search_pt, search_r));
   case convex:
      return (geom->overlap(search_nop, search_pts, e.mbr));
   }
   printf("Select_type has illegal value.\n");
   exit(1);
}


void r_tree::perform_select(long_set *selection)
// This function is selects objects (either in the sphere or rectangle version).
// It is assumed that 'selection_type' is set by one of the functions
// 'select' (overloaded function name), together with either:
// a rectangle (search_rect), or
// a sphere (centre is search_pt, radius is search_r).
// Return with the complete set of id's that have overlap with the region.
{
   long temp;
   int entry_no;
   long temp_pagenumber;

   clear_stacks();
   if (root_pagenumber != NULL_PAGE) {
      temp = root_pagenumber;
      entry_no = 0;
      visited_node.push((long) temp);
      visited_entry.push((long) entry_no);
      do {
	 temp = visited_node.pop();
	 entry_no = (int) visited_entry.pop();
	 while (entry_no < n[temp].nr_of_entries) {
            if (overlap(n[temp].entry[entry_no])) {
	       if (visited_node.length() + 1 < tree_height) {
		  temp_pagenumber = n[temp].entry[entry_no].id;
		  entry_no++;
		  visited_entry.push((long) entry_no);
		  visited_node.push((long) temp);
		  temp = temp_pagenumber;
		  entry_no = 0;
	       } else {
// TEST (reduce overhead) selection->put(n[temp].entry[entry_no].id);
 selection->put(n[temp].entry[entry_no].id);
		  entry_no++;
	       }
	    } else {
	       entry_no++;
	    }
	 }
      } while (!visited_node.empty());
   }
}

void r_tree::analyse()
{
   long temp;
   int i, entry_no;
   long temp_pagenumber;
   double *area;
   long *nr;

   clear_stacks();
   if (root_pagenumber == NULL_PAGE) {
      printf("Analyse tree: empty tree\n");
      return;
   }

   area = new double[tree_height];
   nr = new long[tree_height];
   for (i=0; i<tree_height; i++) {area[i]=0.0; nr[i]=0;}

   visited_node.push((long) root_pagenumber);
   visited_entry.push((long) 0);
   do {
      temp = visited_node.pop();
      entry_no = (int) visited_entry.pop();
      while (entry_no < n[temp].nr_of_entries) {
         if (visited_node.length() + 1 < tree_height) {
            temp_pagenumber = n[temp].entry[entry_no].id;
            area[visited_node.length()] +=
               geom->calc_area(n[temp].entry[entry_no].mbr);
            nr[visited_node.length()]++;
            entry_no++;
            visited_entry.push((long) entry_no);
            visited_node.push((long) temp);
            temp = temp_pagenumber;
            entry_no = 0;
         } else {
            area[visited_node.length()] +=
               geom->calc_area(n[temp].entry[entry_no].mbr);
            nr[visited_node.length()]++;
            entry_no++;
         }
      }
   } while (!visited_node.empty());
   printf("Analyse tree results:\n");
   for (i=0;i<tree_height;i++)
      printf("level %d: area %lf number %ld arvg area %lf\n",
         i, area[i], nr[i], area[i]/(double)nr[i]);

   delete area;
   delete nr;
}


boolean r_tree::domain_objects(point domain[2])
{
   // It is sufficient to inspect the root only.
   if (root_pagenumber != NULL_PAGE) {
      n[root_pagenumber].total_rectangle(domain);
      return true;
   } else return false;
}

long r_tree::First(point pt, coord radius = 0.0)
{
   if (radius == 0.0)
      selection_type = position;
   else
      selection_type = sphere;
   geom->pt_cpy(pt, search_pt);
   search_r = radius;
   return(perform_First());
}


long r_tree::First(point rectangle[2])
{
   selection_type = rect;
   geom->rect_cpy(rectangle, search_rect);
   return(perform_First());
}


long r_tree::perform_First()
{
   long temp, temp_pagenumber, object_id = NULL_ID;
   int entry_no;

   if (root_pagenumber == NULL_PAGE) return(NULL_ID);

   clear_stacks();
   temp = root_pagenumber;
   entry_no = 0;
   visited_node.push((long) temp);
   visited_entry.push((long) entry_no);
   do {
      temp = visited_node.pop();
      entry_no = (int) visited_entry.pop();
      while ((entry_no < n[temp].nr_of_entries)&&(object_id == NULL_ID)) {
         if (overlap(n[temp].entry[entry_no])) {
            if (visited_node.length() + 1 < tree_height) {
               temp_pagenumber = n[temp].entry[entry_no].id;
               entry_no++;
               visited_entry.push((long) entry_no);
               visited_node.push((long) temp);
               temp = temp_pagenumber;
               entry_no = 0;
            } else {
               object_id = n[temp].entry[entry_no].id;
               entry_no++;
            }
         } else entry_no++;
      }
   } while (!visited_node.empty() && (object_id == NULL_ID));
   if (object_id != NULL_ID) {
      visited_entry.push((long) entry_no);
      visited_node.push((long) temp);
   }
   return object_id;
}


long r_tree::Next()
{
   long temp;
   int entry_no;
   long temp_pagenumber;
   long object_id = NULL_ID;

   while (!visited_node.empty() && (object_id == NULL_ID)) {
      temp = visited_node.pop();
      entry_no = (int) visited_entry.pop();
      while ((entry_no < n[temp].nr_of_entries) && (object_id == NULL_ID)) {
         if (overlap(n[temp].entry[entry_no])) {
	    if (visited_node.length() + 1 < tree_height) {
	       temp_pagenumber = n[temp].entry[entry_no].id;
	       entry_no++;
	       visited_entry.push((long) entry_no);
	       visited_node.push((long) temp);
	       temp = temp_pagenumber;
	       entry_no = 0;
	    } else {
	       object_id = n[temp].entry[entry_no].id;
	       entry_no++;
	    }
	 } else {
	    entry_no++;
	 }
      }
   }
   if (object_id != NULL_ID) {
      visited_entry.push((long) entry_no);
      visited_node.push((long) temp);
   }
   return object_id;
}