home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / plane / _range_t.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  18.9 KB  |  821 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _range_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. // ------------------------------------------------------------------
  18. //
  19. // d-dimensional Range Trees
  20. //
  21. // Michael Wenzel     (1990)
  22. //
  23. // Implementation follows
  24. // Data Structure Lecture, K. Mehlhorn, Summer 1989
  25. // K. Mehlhorn: Data Structures and Algorithms, Vol. 3
  26. //
  27. // ------------------------------------------------------------------
  28.  
  29. #include <LEDA/range_tree.h>
  30.  
  31. enum left_or_right {left = 0, right = 1};
  32.  
  33. #undef TEST
  34. #undef DUMP
  35. #undef STAT
  36.  
  37. #ifdef TEST
  38. #define DPRINT(x) cout << x
  39. #else
  40. #define DPRINT(x)
  41. #endif
  42.  
  43. #ifdef DUMP
  44. #define DDUMP(x) cout << x
  45. #else
  46. #define DDUMP(x)
  47. #endif
  48.  
  49. #ifdef STAT
  50. #define DSTAT print_statistics() 
  51. #else
  52. #define DSTAT
  53. #endif
  54.  
  55. //------------------------------------------------------------------
  56. // member-functions of class tuple
  57. //
  58. // Michael Wenzel          (1990)
  59. //------------------------------------------------------------------
  60.  
  61.   tuple::tuple()
  62.       { 
  63.     d=0;
  64.     t=0; }
  65.  
  66.   tuple::tuple(ent a, ent b)
  67.       { 
  68.     d=2;
  69.     t=new ent[2]; 
  70.         t[0] = a;
  71.         t[1] = b; }
  72.  
  73.   tuple::tuple(ent a, ent b, ent c)
  74.       { 
  75.     d=3;
  76.     t=new ent[3]; 
  77.         t[0] = a;
  78.         t[1] = b;  
  79.         t[2] = c;  }
  80.  
  81.   tuple::tuple(int dim)
  82.       { 
  83.     d=dim;
  84.         inf = 0;
  85.     t=new ent[dim]; }
  86.  
  87.   tuple::~tuple()
  88.       { if (t)
  89.           delete t;
  90.       }
  91.  
  92. //-------------------------------------------------------------------
  93. //  RANGE TREE
  94. //-------------------------------------------------------------------
  95.  
  96.  
  97. int range_tree::tuple_cmp(tuplep p, tuplep q)
  98. {  int i = p->cmp_dim();
  99.    int stop = (i==0) ? p->d-1 : i-1;
  100.    int res;
  101.    while ((res=cmp_tuple_entry(i,p,q))==0 && i!=stop) 
  102.      i=(i+1)%p->d;
  103.    return res;
  104. }
  105.     
  106. // ------------------------------------------------------------
  107. // lrot() , rrot() , ldrot() , rdrot()
  108. // Rotationen am Knoten p
  109.  
  110. void range_tree::lrot(bb_item p, bb_item q)
  111. {
  112.   bb_item h = p->sohn[right];
  113.   int help_dim = key(h)->cmp_dim();
  114.   key(h)->set_cmp(key(h)->dimension()-dim+1);
  115.  
  116.   DDUMP("lrot "<< (int)key(p)) ; 
  117.     if (q) DDUMP(" Vater " << (int)(key(q)));
  118.   DDUMP("\n");
  119.  
  120.   p->sohn[right] = h->sohn[left];
  121.   h->sohn[left] = p;
  122.   if (!q)
  123.     root=h;
  124.   else
  125.   { if (tuple_cmp(key(h),key(q))>0)
  126.       q->sohn[right]=h;
  127.     else
  128.       q->sohn[left]=h;
  129.   }
  130.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  131.   h->gr=p->groesse()+h->sohn[right]->groesse();
  132.  
  133.                         // update nodelists
  134.   list(range_tree_item) L;
  135.   range_tree_item x;
  136.  
  137.   bb_item s = p->sohn[left];
  138.   if (s->blatt())
  139.     inf(h)->insert_tuple(key(s));
  140.   else
  141.   { L = inf(s)->all_tuples();
  142.     forall(x,L) inf(h)->insert_tuple(x);
  143.     L.clear();
  144.   }
  145.  
  146.   s = h->sohn[right];
  147.   if (s->blatt())
  148.     inf(h)->del_tuple(key(s));
  149.   else
  150.   { L = inf(s)->all_tuples();
  151.     forall(x,L) inf(p)->del_tuple(x);
  152.   }
  153.  
  154.   key(h)->set_cmp(help_dim);
  155. }
  156.  
  157. void range_tree::rrot(bb_item p, bb_item q)
  158. {
  159.   bb_item h = p->sohn[left];
  160.   int help_dim = key(h)->cmp_dim();
  161.   key(h)->set_cmp(key(h)->dimension()-dim+1);
  162.  
  163.   DDUMP("rrot "<< (int)(key(p))) ; 
  164.     if (q) DDUMP(" Vater " << (int)(key(q)));
  165.   DDUMP("\n");
  166.  
  167.   p->sohn[left] = h->sohn[right];
  168.   h->sohn[right] = p;
  169.   if (!q) root=h;
  170.   else
  171.   { if (tuple_cmp(key(h),key(q))>0)
  172.       q->sohn[right] = h;
  173.     else
  174.       q->sohn[left] = h; }
  175.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  176.   h->gr=p->groesse()+h->sohn[left]->groesse();
  177.  
  178.                         // update nodelists
  179.   list(range_tree_item) L;
  180.   range_tree_item x;
  181.   bb_item s = p->sohn[right];
  182.   if (s->blatt())
  183.     inf(h)->insert_tuple(key(s));
  184.   else
  185.   { L = inf(s)->all_tuples();
  186.     forall(x,L) inf(h)->insert_tuple(x);
  187.     L.clear();
  188.   }
  189.  
  190.   s = h->sohn[left];
  191.   if (s->blatt())
  192.     inf(p)->del_tuple(key(s));
  193.   else
  194.   { L = inf(s)->all_tuples();
  195.     forall(x,L) inf(p)->del_tuple(x);
  196.   }
  197.   key(h)->set_cmp(help_dim);
  198. }
  199.  
  200. void range_tree::ldrot(bb_item p, bb_item q)
  201. {
  202.   bb_item h = p->sohn[right];
  203.   bb_item g = h->sohn[left];
  204.   int help_dim = key(h)->cmp_dim();
  205.   key(h)->set_cmp(key(h)->dimension()-dim+1);
  206.  
  207.   DDUMP("ldrot "<< (int)(key(p))) ; 
  208.     if (q) DDUMP(" Vater " << (int)(key(q)));
  209.   DDUMP("\n");
  210.  
  211.   p->sohn[right] = g->sohn[left];
  212.   h->sohn[left] =  g->sohn[right];
  213.   g->sohn[left] = p;
  214.   g->sohn[right] = h;
  215.   if (!q) root=g;
  216.   else
  217.   { if (tuple_cmp(key(h),key(q))>0)
  218.       q->sohn[right] =g ;
  219.     else 
  220.       q->sohn[left] = g ; }
  221.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  222.   h->gr=h->sohn[left]->groesse()+h->sohn[right]->groesse();
  223.   g->gr=p->groesse()+h->groesse();
  224.                         // update nodelists
  225.   list(range_tree_item) L;
  226.   range_tree_item x;
  227.   range_tree* help = (range_tree*)g->inf;
  228.  
  229.   g->inf = p->inf;
  230.  
  231.   bb_item s = p->sohn[right];
  232.   if (s->blatt())
  233.     inf(h)->del_tuple(key(s));
  234.   else
  235.   { L = inf(s)->all_tuples();
  236.     forall(x,L) inf(h)->del_tuple(x);
  237.     L.clear();
  238.   }
  239.  
  240.   s = h->sohn[left];
  241.   if (s->blatt())
  242.     help->del_tuple(key(s));
  243.   else
  244.   { L = inf(s)->all_tuples();
  245.     forall(x,L) help->del_tuple(x);
  246.     L.clear();
  247.   }
  248.  
  249.   s = p->sohn[left];
  250.   if (s->blatt())
  251.     help->insert_tuple(key(s));
  252.   else
  253.   { L = inf(s)->all_tuples();
  254.     forall(x,L) help->insert_tuple(x);
  255.   }
  256.  
  257.   p->inf = (ent) help;
  258.   key(h)->set_cmp(help_dim);
  259. }
  260.  
  261. void range_tree::rdrot(bb_item p, bb_item q)
  262.  
  263. {
  264.   bb_item h = p->sohn[left];
  265.   bb_item g = h->sohn[right];
  266.   int help_dim = key(h)->cmp_dim();
  267.   key(h)->set_cmp(key(h)->dimension()-dim+1);
  268.  
  269.   DDUMP("rdrot "<< (int)(key(p))) ; 
  270.     if (q) DDUMP(" Vater " << (int)(key(q)));
  271.   DDUMP("\n");
  272.  
  273.   p->sohn[left] = g->sohn[right];
  274.   h->sohn[right] =  g->sohn[left];
  275.   g->sohn[right] = p;
  276.   g->sohn[left] = h;
  277.   if (!q) root=g;
  278.   else
  279.   { if (tuple_cmp(key(h),key(q))>0)
  280.       q->sohn[right] =g ;
  281.     else 
  282.       q->sohn[left] = g ; }
  283.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  284.   h->gr=h->sohn[left]->groesse()+h->sohn[right]->groesse();
  285.   g->gr=p->groesse()+h->groesse();
  286.                         // update nodelists
  287.   list(range_tree_item) L;
  288.   range_tree_item x;
  289.   range_tree* help = (range_tree*)g->inf;
  290.  
  291.   g->inf = p->inf;
  292.  
  293.   bb_item s = p->sohn[left];
  294.   if (s->blatt())
  295.     inf(h)->del_tuple(key(s));
  296.   else
  297.   { L = inf(s)->all_tuples();
  298.     forall(x,L) inf(h)->del_tuple(x);
  299.     L.clear();
  300.   }
  301.  
  302.   s = h->sohn[right];
  303.   if (s->blatt())
  304.     help->del_tuple(key(s));
  305.   else
  306.   { L = inf(s)->all_tuples();
  307.     forall(x,L) help->del_tuple(x);
  308.     L.clear();
  309.   }
  310.  
  311.   s = p->sohn[right];
  312.   if (s->blatt())
  313.     help->insert_tuple(key(s));
  314.   else
  315.   { L = inf(s)->all_tuples();
  316.     forall(x,L) help->insert_tuple(x);
  317.   }
  318.  
  319.   p->inf = (ent) help;
  320.   key(h)->set_cmp(help_dim);
  321. }
  322.  
  323. // ------------------------------------------------------------
  324. // check(x,y,z)                              
  325. // check if a tuple x lies between y and z
  326. // some coordinates are already checked
  327.  
  328. bool range_tree::check(tuplep x, tuplep y, tuplep z)
  329.  
  330. { bool found=true;
  331.   int help_dim = x->cmp_dim();
  332.  
  333.   for (int i=x->dimension()-dim+1;i<=x->dimension();i++)
  334.   { x->set_cmp(i);
  335.     if ((tuple_cmp(x,y)<0)||(tuple_cmp(x,z)>0)) 
  336.     { x->set_cmp(help_dim);
  337.       return false;
  338.     }
  339.   }
  340.   x->set_cmp(help_dim);
  341.   return found;
  342. }
  343.  
  344.  
  345. //-------------------------------------------------------------------
  346. // insert_tuple
  347. // insert a tuple into a range_tree:             
  348. // - insert tuple according to first coordinate in main tree (bb-alpha)
  349. // - insert tuple according to second coordinate in all nodetrees
  350. //   on the path of the main tree from the root to the tuple
  351.  
  352. range_tree_item range_tree::insert_tuple(tuple* x)
  353.  
  354. { bb_tree_item inserted;
  355.   tuplep y;
  356.   int help_dim = x->cmp_dim();
  357.   x->set_cmp(x->dimension()-dim+1);
  358.  
  359.   DPRINT("insert tuple " << (int)x << " in "  << dim << " dimension ") ;
  360.   DPRINT("and comparedimension " << x->cmp_dim() << "\n");
  361.  
  362.   if (inserted=rm_tree::lookup(x)) 
  363.   { 
  364.     tuplep y=key(inserted);
  365.     clear_inf((ent&)y);                 // clear tuple and change inf
  366.     y->info() = x->info();
  367.     copy_inf((ent&)y);
  368.     clear_tuple(x);
  369.     delete x;
  370.  
  371.     return y;
  372.   }
  373.  
  374.   if (dim==1) 
  375.   { bb_tree_item t,father;
  376.     inserted = sinsert(x,0);
  377.  
  378.     if (!st.empty())
  379.       st.pop();                       // pop father of leaf
  380.   
  381.                                       // rebalancieren
  382.     while (!st.empty())
  383.     { t=st.pop();
  384.       father = st.empty() ? 0 : st.top();
  385.       t->gr++;  
  386.       float i = t->bal();
  387.  
  388.       DDUMP("rebal cur=" << (int)(key(t)) << " groesse= " << t->groesse() << " bal= " << i << " in Dimension 1\n");
  389.  
  390.       tuplep help = key(t);
  391.       int help_dimt = help->cmp_dim();
  392.       help->set_cmp(help->dimension());
  393.       if (i < alpha)
  394.         if (t->sohn[right]->bal()<=d) bb_tree::lrot(t,father);
  395.         else bb_tree::ldrot(t,father);
  396.       else if (i>1-alpha) 
  397.              if (t->sohn[left]->bal() > d ) bb_tree::rrot(t,father);
  398.          else bb_tree::rdrot(t,father);
  399.       help->set_cmp(help_dimt);
  400.     }
  401.     x->set_cmp(help_dim);
  402.  
  403.     return key(inserted);
  404.   }
  405.  
  406.   else
  407.   { bb_tree_item it,it1;                
  408.     range_tree*  t = new_range_tree(dim-1);
  409.  
  410.     it = sinsert(x,t);
  411.     inserted = it ;
  412.     DDUMP(" bei leerem Baum ");
  413.     t->insert_tuple(x);
  414.                                           // rebalance tree and insert 
  415.                       // tuple into nodelists  
  416.  
  417.     if (!st.empty())                     // insert correct tuple
  418.     { it1=st.pop();                      // node needs no rebalancing
  419.       DDUMP("bei " << (int)(key(it1)) << " " );
  420.       if (it==bb_tree::max())
  421.       { inf(it1)->insert_tuple(x);     
  422.         x->set_cmp(x->dimension()-dim+1);
  423.       }
  424.       else
  425.       { y= key(succ(it));
  426.     inf(it1)->insert_tuple(y);
  427.         y->set_cmp(y->dimension()-dim+1);
  428.       }
  429.     }
  430.  
  431.     while (!st.empty())
  432.     { it=st.pop();
  433.       DDUMP("bei " << (int)(key(it)) << " " );
  434.       inf(it)->insert_tuple(x);
  435.       it1 = st.empty() ? 0 : st.top();
  436.       it->gr++;  
  437.       float i = it->bal();
  438.       DDUMP("rebal cur=" << (int)(key(it)) << " groesse= " << it->groesse() << " bal= " << i << " in dimension " << dim  << "\n");
  439.  
  440.       if (i < alpha)
  441.     if (it->sohn[right]->bal()<=d) lrot(it,it1); 
  442.     else ldrot(it,it1); 
  443.       else if (i>1-alpha) 
  444.              if (it->sohn[left]->bal() > d ) rrot(it,it1);
  445.          else rdrot(it,it1);
  446.     }
  447.     x->set_cmp(help_dim);
  448.     return key(inserted);
  449.   }
  450. }
  451.  
  452. //-------------------------------------------------------------------
  453. // delete
  454. // delete a tuple in a range_tree:
  455. // - delete tuple in all nodetrees on the path of the main tree
  456. //   from the root to the tuple
  457. // - delete tuple in main tree
  458.  
  459. void range_tree::del(tuplep x)
  460.  
  461. { 
  462.   tuplep y = del_tuple(x);
  463.   if (y)
  464.   { clear_tuple(y);
  465.     delete y;
  466.   }
  467. }
  468.  
  469. tuplep range_tree::del_tuple(tuplep x)
  470.  
  471. {
  472.   DPRINT("delete tuple " << (int)x << " in "  << dim << " dimension\n");
  473.  
  474.   tuplep deleted;
  475.   int help_dim = x->cmp_dim();
  476.   x->set_cmp(x->dimension()-dim+1);
  477.   if (dim==1)
  478.   { bb_item p,father;
  479.     p = sdel(x);
  480.     if (p)
  481.     { 
  482.       deleted=key(p);
  483.       delete (p);
  484.       if (!st.empty())
  485.         delete (st.pop());
  486.       while (!st.empty())
  487.       { p = st.pop();
  488.         father = st.empty() ? 0 : st.top() ;
  489.         p->gr--;              
  490.         float i=p->bal();
  491.         DDUMP("rebal cur=" << (int)(key(p)) << " groesse= " << p->groesse() << " bal= " << i << " in dimension " << dim << "\n");
  492.  
  493.     tuplep help = key(p);
  494.     int help_dimp = help->cmp_dim();
  495.     help->set_cmp(help->dimension());
  496.         if (i<alpha)
  497.           if (p->sohn[right]->bal() <= d) bb_tree::lrot(p,father);
  498.           else bb_tree::ldrot(p,father);
  499.         else if (i>1-alpha)
  500.                if(p->sohn[left]->bal() > d) bb_tree::rrot(p,father);
  501.                else bb_tree::rdrot(p,father);
  502.         help->set_cmp(help_dimp);
  503.       }
  504.     }
  505.     x->set_cmp(help_dim);
  506.     return deleted; 
  507.   }
  508.  
  509.   else
  510.   { if (empty()) return 0;
  511.     if (size()==1)                     // only one tuple
  512.     { DDUMP("delete only element\n");
  513.       tuplep y=key(root);
  514.       if ( tuple_cmp(x,y) == 0 )
  515.       { delete(inf(root));
  516.     bb_tree::clear();
  517.         return y;                
  518.       }
  519.     }
  520.  
  521.     bb_item it,it1;
  522.  
  523.     x->set_cmp(x->dimension()-dim+1);
  524.  
  525.     it1 = sdel(x);
  526.     if (!it1) return 0;                  // tuple not in tree
  527.     deleted = key(it1);
  528.  
  529.  
  530.     bb_item it2 = pred(it1);
  531.                                          // delete nodelist of it1 or pred(it1)
  532.     it = st.pop();
  533.  
  534.     if (tuple_cmp(x,key(bb_tree::max()))>=0)
  535.     { DDUMP("old maximum deleted\n");    // old maximum deleted
  536.       delete(inf(it1));
  537.       inf(it)->del_tuple(x);
  538.       it2->inf = it->inf;
  539.     }
  540.     else
  541.       delete(inf(it));
  542.  
  543.     DDUMP((int)(key(it1)) << " geloescht\n" );
  544.  
  545.     delete it;
  546.     delete it1; 
  547.                      // rebalance tree
  548.                      // and delete tuple out of nodelists
  549.     while (!st.empty())
  550.     { 
  551.       it=st.pop();
  552.       inf(it)->del_tuple(x); 
  553.  
  554.       it1 = st.empty() ? 0 : st.top() ;
  555.       it->gr--;              
  556.  
  557.       float i=it->bal();
  558.       DDUMP("rebal cur=" << (int)(key(it)) << " groesse= " << it->groesse() << " bal= " << i << " in dimension " << dim << "\n");
  559.       if (i<alpha)
  560.         if (it->sohn[right]->bal() <= d) lrot(it,it1);
  561.         else ldrot(it,it1);
  562.       else if (i>1-alpha)
  563.              if(it->sohn[left]->bal() > d) rrot(it,it1);
  564.              else rdrot(it,it1);
  565.     }
  566.  
  567.     x->set_cmp(help_dim);
  568.     return deleted;
  569.   }
  570. }
  571.  
  572. //-------------------------------------------------------------------
  573. // query
  574. // returns all tuples x in the range_tree with
  575. //     lower.project(i) <= x.project(i) <= upper.project(i)
  576. //     for x.cmp_dim() <= i <= dim
  577. // by:
  578. // - perform for all tuples x with 
  579. //   lower.project(1) <= x.project(1) <= upper.project(1)
  580. //   a query in a (d-1) dimensional Range-tree 
  581.  
  582. void range_tree::query_tuples(tuplep lower, tuplep upper, dlist& L)
  583. { 
  584.   DPRINT("query in dimension " << dim << " on " << (int)(key(root)) << "\n");
  585.  
  586.   L.clear();
  587.  
  588.   if (size()==0) return;
  589.  
  590.   int help_diml = lower->cmp_dim();
  591.   int help_dimu = upper->cmp_dim();
  592.  
  593.   lower->set_cmp(lower->dimension()-dim+1);
  594.   upper->set_cmp(upper->dimension()-dim+1);
  595.  
  596.   bb_tree_item it;
  597.   tuplep y,y1;
  598.   
  599.   L.clear();
  600.  
  601.   if (size()==0) return;
  602.  
  603.   if (dim==1)                        // one - dimensional tree
  604.   { it=locate(lower);
  605.     while( it && (tuple_cmp(upper,key(it)) >=  0) )
  606.     { DDUMP((int)(key(it)) << "betrachtet\n");
  607.       L.append(key(it));
  608.       it = succ(it);
  609.     }
  610.     lower->set_cmp(help_diml);
  611.     upper->set_cmp(help_dimu);
  612.     return;
  613.   }
  614.  
  615.                                      // >= 2 dimensional tree
  616.   it=root;
  617.   if (size()==1)                     // no recursive calls
  618.   { 
  619.     if (check(key(it),lower,upper)) L.append(key(it));
  620.     lower->set_cmp(help_diml);
  621.     upper->set_cmp(help_dimu);
  622.     return;
  623.   }
  624.  
  625.                                      // look for nodetrees
  626.                      // necessary: access to nodes of bb_tree
  627.   bb_tree_item it1=root;   
  628.   while ((it==it1)&&(!it->blatt()))
  629.   { y=key(it);
  630.     y1=key(it1);
  631.     DDUMP(" same path " << (int)y1 << "\n");
  632.     lower->set_cmp(lower->dimension()-dim+1);
  633.     upper->set_cmp(upper->dimension()-dim+1);
  634.     if ( tuple_cmp(lower,y)<=0 ) it=it->sohn[left];
  635.       else it=it->sohn[right];
  636.     if ( tuple_cmp(upper,y1)<=0 ) it1=it1->sohn[left];
  637.       else it1=it1->sohn[right];
  638.   }
  639.                      // now paths to lower and upper part
  640.                                      // or it is a leaf
  641.   y=key(it);
  642.   if (it->blatt())
  643.   { 
  644.     if (check(y,lower,upper)) L.append(y);
  645.  
  646.     if(it!=it1)                      // it leaf, it != it1 => search on upper path
  647.     { list(range_tree_item) L1;
  648.       while (!it1->blatt())
  649.       { lower->set_cmp(lower->dimension()-dim+1);
  650.         upper->set_cmp(upper->dimension()-dim+1);
  651.         y1=key(it1);
  652.     DDUMP(" upper path " << (int)y1 << "\n");
  653.     if ( tuple_cmp(upper,y1)<=0 ) it1=it1->sohn[left];
  654.     else
  655.     { bb_item it2=it1->sohn[left];
  656.       if (!it2->blatt())
  657.         info(it2)->query_tuples(lower,upper,L1);
  658.           else 
  659.         if (check(key(it2),lower,upper)) L1.append(key(it2)); 
  660.       L.conc(L1);
  661.       it1=it1->sohn[right];
  662.         }
  663.       }
  664.       if (check(key(it1),lower,upper)) L.append(key(it1)); 
  665.     }
  666.     lower->set_cmp(help_diml);
  667.     upper->set_cmp(help_dimu);
  668.     return;
  669.   }
  670.  
  671.                                      // it no leaf => paths parted 
  672.   list(range_tree_item) L1;
  673.   while (!it->blatt())
  674.   { y=key(it);
  675.     DDUMP(" lower path " << (int)y << "\n");
  676.     lower->set_cmp(lower->dimension()-dim+1);
  677.     upper->set_cmp(upper->dimension()-dim+1);
  678.     if ( tuple_cmp(lower,y)>0 ) it=it->sohn[right];
  679.     else
  680.     { bb_item it2=it->sohn[right];
  681.       if (!it2->blatt())
  682.         info(it2)->query_tuples(lower,upper,L1);
  683.       else 
  684.     if (check(key(it2),lower,upper)) L1.append(key(it2)); 
  685.       L.conc(L1);
  686.       it=it->sohn[left];
  687.     }
  688.   } 
  689.   if (check(key(it),lower,upper)) L.append(key(it));
  690.  
  691.   while (!it1->blatt())
  692.   { y1=key(it1);
  693.     DDUMP(" upper path " << (int)y1 << "\n");
  694.     lower->set_cmp(lower->dimension()-dim+1);
  695.     upper->set_cmp(upper->dimension()-dim+1);
  696.     if ( tuple_cmp(upper,y1)<=0 ) it1=it1->sohn[left];
  697.     else
  698.     { bb_item it2=it1->sohn[left];
  699.       if (!it2->blatt())
  700.         info(it2)->query_tuples(lower,upper,L1);
  701.       else 
  702.     if (check(key(it2),lower,upper)) L1.append(key(it2)); 
  703.       L.conc(L1);
  704.       it1=it1->sohn[right];
  705.     }
  706.   }
  707.   if (check(key(it1),lower,upper)) L.append(key(it1)); 
  708.  
  709.   lower->set_cmp(help_diml);
  710.   upper->set_cmp(help_dimu);
  711.   return;
  712. }
  713.  
  714. //-------------------------------------------------------------------
  715. // all_tuples
  716. // returns all range_tree_items x in the range_tree 
  717.  
  718. list(range_tree_item) range_tree::all_tuples()
  719.  
  720. { 
  721.   DPRINT("all_tuples of " << int(this) << " in dimension " << dim << "\n");
  722.   
  723.   bb_item it;
  724.   list(range_tree_item) L;
  725.  
  726.   init_iterator();
  727.   while (it=rm_tree::move_iterator())
  728.     L.append(key(it));
  729.  
  730.   return L;
  731.  
  732. }
  733.  
  734.  
  735. //--------------------------------------------------------------------
  736. // Minima & Maxima
  737.  
  738. range_tree_item range_tree::min(int i)
  739. { if (i>dim || i<1)
  740.     return 0;
  741.   else 
  742.   { range_p r=this; 
  743.     while (--i) r=(range_p)r->root->inf;
  744.     return key(((bb_tree*)r)->min()); 
  745.   }
  746. }
  747.  
  748. range_tree_item range_tree::max(int i)
  749. { if (i>dim || i<1)
  750.     return 0;
  751.   else 
  752.   { range_p r=this; 
  753.     while (--i) r=(range_p)r->root->inf;
  754.     return key(((bb_tree*)r)->max()); 
  755.   }
  756. }
  757.  
  758. //--------------------------------------------------------------------
  759. //  Clear & Destruktor
  760. //  
  761.  
  762.  
  763. void range_tree::clear_tuple(tuplep& y) 
  764. { 
  765.    DPRINT("clear von " << (int)y << "\n");
  766.    clear_key((ent&)y);
  767.    clear_inf((ent&)y);
  768. }
  769.  
  770. void range_tree::del_tree(bb_item p)
  771. { 
  772.   if (!p->blatt())
  773.   {  
  774.      delete inf(p);
  775.      del_tree(p->sohn[left]);
  776.      del_tree(p->sohn[right]); 
  777.   }
  778.   else
  779.     if (p==bb_tree::max())
  780.       delete inf(p);
  781.  
  782.   delete(p);
  783.  
  784. }
  785.  
  786. void range_tree::clear()
  787. { range_tree_item it;
  788.   list(range_tree_item) L=all_tuples();
  789.   forall(it,L) 
  790.   { 
  791.      clear_tuple(it);
  792.      delete it;       
  793.   }
  794.  
  795.   if (dim==1)
  796.     bb_tree::clear();
  797.   else
  798.     if (root)
  799.       del_tree(root);
  800.  
  801.   root=0;
  802.   anzahl=0;
  803.   first=0;
  804. }
  805.  
  806.  
  807. range_tree::~range_tree()
  808. { 
  809.  
  810.    DPRINT("Destruktor in Dimension " << dim << "\n");
  811.  
  812.    if (root)
  813.    { del_tree(root);
  814.      root = 0;
  815.    }
  816.  
  817. }
  818.  
  819.   
  820. //--------------------------------------------------------------------
  821.