开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
_iv_tree.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：23k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

_iv_tree.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _iv_tree.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. // -------------------------------------------------------------------
  14. //
  15. //  Interval Trees
  16. //
  17. //  Michael Seel   (1990/91)
  18. //
  19. // Implementation as described in
  20. // Kurt Mehlhorn: Data Structures and Algorithms 3, section VIII.5.1.1
  21. //
  22. // -------------------------------------------------------------------
  24. #include <LEDA/impl/iv_tree.h>
  27. // -------------------------------------------------------------
  28. // member functions von iv_tree
  29. // -------------------------------------------------------------
  31. // -------------------------------------------------------------
  32. // lrot() , rrot() , ldrot() , rdrot()
  33. // Rotationen am Knoten p
  35. void iv_tree::lrot(iv_item p, iv_item q)
  37. // p ist der zentrale Knoten um den rotiert wird
  38. // q ist der Vater von p
  40. { 
  41.   iv_item h = p->son[_right];
  42.   p->son[_right] = h->son[_left];
  43.   h->son[_left] = p;
  44.    
  45.   if (!q) root=h;
  46.   else
  47.   {
  48.    if ( p == q->son[_left] )   q->son[_left]=h;
  49.    else q->son[_right]=h;
  50.   }; 
  51.   
  52.   p->gr=p->son[_left]->groesse()+p->son[_right]->groesse();
  53.   h->gr=p->groesse()+h->son[_right]->groesse();
  55.   reorganize_nodelist(h,p);
  56. }
  58. void iv_tree::rrot(iv_item p, iv_item q)
  60. // p ist der zentrale Knoten um den rotiert wird
  61. // q ist der Vater von p
  63. { 
  64.   iv_item h = p->son[_left];
  65.   p->son[_left] = h->son[_right];
  66.   h->son[_right] = p;
  68.   if (!q) root=h;
  69.   else
  70.   {
  71.    if ( p == q->son[_left] ) q->son[_left] = h;
  72.    else q->son[_right] = h; 
  73.   };
  75.   p->gr=p->son[_left]->groesse()+p->son[_right]->groesse();
  76.   h->gr=p->groesse()+h->son[_left]->groesse();
  78.   reorganize_nodelist(h,p);
  79. }
  81. void iv_tree::ldrot(iv_item p, iv_item q)
  82. { 
  83.   iv_item h = p->son[_right];
  84.   //iv_item t = h->son[_left];
  85.   rrot(h,p);
  86.   lrot(p,q);
  87. }
  89. void iv_tree::rdrot(iv_item p, iv_item q)
  90. {
  91.   iv_item h = p->son[_left];
  92.   //iv_item t = h->son[_right];
  93.   lrot(h,p);
  94.   rrot(p,q);
  95. }
  96.  
  97. // ------------------------------------------------------------------
  98. // reorganize_nodelist()
  99. // reorganisiert die nach der Rotation falsch mit Intervallen belegten
  100. // Nodelists entsprechend neu.
  102. void iv_tree::reorganize_nodelist(iv_item father, iv_item son)
  103. {
  104.   // nach Aendern des Dictionary-Typs in perfekte BB_trees mit Konstruk-
  105.   // tionsprozedur, die aus einer Liste von n geordneten Knoten ein neu-
  106.   // es Dictionary in Zeit O(n) erzeugt, werden von den folgenden 4 Ite-
  107.   // rationen je 2 in ein Misch_Sort Verfahren abgeaendert und die so
  108.   // auf father und son verteilten Intervalle in Linearzeit in die Kno-
  109.   // ten dictionarys eingebunden
  111.   dic_item it;
  112.   nodelist_p fx = new nodelist;
  113.   nodelist_p fy = new nodelist;
  114.   nodelist_p sx = new nodelist;
  115.   nodelist_p sy = new nodelist;
  117.   forall_items(it,*(father->x_nodelist())) // father->x_nodelist
  118.          // liefert Pointer
  119.          // auf x-Dictionary
  120.       {
  121.  if (split_in_x_interval(father , x_nodelist(father)->key(it)))
  122.     fx->insert(x_nodelist(father)->key(it),x_nodelist(father)->inf(it));
  123.          else
  124.     sx->insert(x_nodelist(father)->key(it),x_nodelist(father)->inf(it));
  125.       };
  126.   // die x-Knotenliste des Vaters wird durchsucht und alle passenden
  127.   // Intervalle der Vater-Knotenliste zugeordnet, Rest an den Sohn
  129.   forall_items(it,*(son->x_nodelist())) // son->x_nodelist
  130.               // liefert Pointer
  131.             // auf x-Dictionary
  132.       {
  133.  if (split_in_x_interval(father , x_nodelist(son)->key(it))) 
  134.     fx->insert(x_nodelist(son)->key(it),x_nodelist(son)->inf(it));
  135.          else
  136.     sx->insert(x_nodelist(son)->key(it),x_nodelist(son)->inf(it));
  137.       };
  138.   // die x-Knotenliste des Sohns wird durchsucht und alle passenden
  139.   // Intervalle der Vater-Knotenliste zugeordnet, Rest an den Sohn
  142.   forall_items(it,*(father->y_nodelist())) // father->y_nodelist
  143.                         // liefert Pointer
  144.                // auf y-Dictionary
  145.       {
  146.  if (split_in_y_interval(father , y_nodelist(father)->key(it)))
  147.     fy->insert(y_nodelist(father)->key(it),y_nodelist(father)->inf(it));
  148.          else
  149.     sy->insert(y_nodelist(father)->key(it),y_nodelist(father)->inf(it));
  150.       };
  151.   // die y-Knotenliste des Vaters wird durchsucht und alle passenden
  152.   // Intervalle der Vater-Knotenliste zugeordnet, Rest an den Sohn
  154.   forall_items(it,*(son->y_nodelist())) // son->y_nodelist
  155.     // liefert Pointer
  156.     // auf y-Dictionary
  157.       {
  158.  if (split_in_y_interval(father, y_nodelist(son)->key(it)))
  159.     fy->insert(y_nodelist(son)->key(it),y_nodelist(son)->inf(it));
  160.          else
  161.     sy->insert(y_nodelist(son)->key(it),y_nodelist(son)->inf(it));
  162.       };
  163.   // die y-Knotenliste des Sohns wird durchsucht und alle passenden
  164.   // Intervalle der Vater-Knotenliste zugeordnet, Rest an den Sohn
  166.   delete x_nodelist(father);
  167.   delete y_nodelist(father);
  168.   delete x_nodelist(son);
  169.   delete y_nodelist(son);
  170.   // alte Dictionaries werden geloescht und freigegeben
  171.   father->x_nl = fx;
  172.   father->y_nl = fy;
  173.   son->x_nl = sx;
  174.   son->y_nl = sy;
  175.   // Knotenlisten werden mit neu angeordneten Dictionaries intialisiert
  176. }
  179. // ------------------------------------------------------------
  180. // search()
  181. // nachher: st = ( pk ,..., p1 ) mit 
  182. //          pk = locate(y) , p1 = root 
  183. //          p1 , ... , pk ist Suchpfad nach y
  184. // liefert inneren Knoten k mit key(k) = y , falls existiert
  185. //         0                               , sonst
  187. iv_item iv_tree::search(split_item x)
  189. { 
  190.   st.clear();
  191.   iv_item p = root;
  192.   iv_item searched = 0;
  194.   if (!root) return 0;         // Baum leer
  195.   while (!p->blatt())
  196.   { 
  197.     if (cmp(x,split_value(p))<=0)
  198.     {
  199.       if (cmp(x,split_value(p))==0) searched = p;
  200.       st.push(p);
  201.       p = p->son[_left];
  202.     }
  203.     else
  204.     {
  205.       st.push(p);
  206.       p = p->son[_right];
  207.     }
  208.   }
  209.   st.push(p);
  210.   return searched;
  211. }
  214. // ------------------------------------------------------------------
  215. // iv_insert(x_typ,x_typ)
  216. // fuegt ein neues Intervall (x,y) in den Baum ein
  217. // gibt Zeiger auf Knoten, in dessen Knotenliste Intervall
  218. // eingefuegt wurde, zurueck.
  220. iv_item iv_tree::iv_insert(x_typ x, x_typ y)
  221. {
  222.  if (y<x)
  223.  {
  224.   error_handler(0,"kein Intervall zum einfuegen");
  225.   return 0;
  226.  }
  227.  else
  228.  {
  229.   interval_item x_iv = new interval(x,y);
  230.   interval_item y_iv = new interval(y,x);
  231.   return ins(x_iv,y_iv,++interval_nb);
  232.  }
  233. }
  235. // ------------------------------------------------------------------
  236. // ins(interval_item,interval_item,int)
  237. // fuegt den entsprechenden Knoten in die Grundstruktur mit dem 
  238. // entsprechenden split_value und fuegt die beiden Intervalle am
  239. // entsprechenden Knoten in die Knotenlisten
  241. iv_item iv_tree::ins(interval_item x, interval_item y, int lfnr) 
  242. {
  243.  iv_item p;
  244.  iv_item t;
  245.  iv_item father;
  246.  split_pair x_pair(x->koo1,-lfnr);
  247.  split_item x_split = &x_pair; 
  248.  
  249.  if (!root)                                     // neuer Baum
  250.  { 
  251.   root = new iv_node(x_split);
  252.   anzahl=1;
  253.  }
  254.  else     // Baum existiert schon !!
  255.   if (root->blatt())
  256.   {
  257.     if (cmp(x_split,split_value(root))<0)
  258.     {
  259.      iv_item help = new iv_node(x_split);
  260.      root = new iv_node(x_split,node,help,root);
  261.      if (x_split->key1==split_value(root->son[_right])->key1)
  262.       nodelist_swap(root , root->son[_right]);
  263.      anzahl++;
  264.     }
  265.     else
  266.      if (cmp(x_split,split_value(root))>0)
  267.      {
  268.       iv_item help = new iv_node(x_split);
  269.       root = new iv_node(split_value(root),node,root,help);
  270.       nodelist_swap(root , root->son[_left]);
  271.       anzahl++;
  272.      }
  273.   }
  274.   else // in Knoten von nicht trivialem Baum wird eingefuegt
  275.   {
  276.     search(x_split);
  277.     p = st.pop();
  278.     father = st.top();
  279.   
  280.     if(cmp(x_split,split_value(p))<0)
  281.     {
  282.      iv_item help = new iv_node(x_split);
  283.      p = new iv_node(x_split,node,help,p);
  284.      // neuer Knoten in p mit split x, x-Blatt links, p-Blatt rechts
  285.      if (x_split->key1==split_value(p->son[_right])->key1)
  286.       nodelist_swap(p , p->son[_right]);
  288.      if (cmp(split_value(p),split_value(father))<=0)
  289.        father->son[_left] = p;
  290.      else
  291.        father->son[_right] = p;
  292.      anzahl++;
  293.     }
  294.     else
  295.      if (cmp(x_split,split_value(p))>0)
  296.      {           
  297.       iv_item help = new iv_node(x_split);
  298.       p = new iv_node(split_value(p),node,p,help);
  299.       // neuer Knoten in p mit split p, p-Blatt links, x-Blatt rechts
  300.       nodelist_swap(p , p->son[_left]);
  302.       if (cmp(split_value(p),split_value(father))<=0)
  303.         father->son[_left] = p;
  304.       else
  305.         father->son[_right] = p;
  306.       anzahl++;
  307.      }
  308.   }
  310.   while (!st.empty())                          // rebalancieren
  311.   { 
  312.     t=st.pop();
  313.     father = st.empty() ? 0 : st.top();
  314.     t->gr++;  
  315.     float i = t->bal();
  316.     if (i < alpha)
  317.     {
  318.      if (t->son[_right]->bal()<=d)
  319.        lrot(t,father);
  320.      else
  321.        ldrot(t,father);
  322.     }
  323.     else
  324.     if (i>1-alpha) 
  325.     {
  326.       if (t->son[_left]->bal()>d)
  327. rrot(t,father);
  328.       else
  329. rdrot(t,father);
  330.     }
  331.   }
  332.   
  333.   p = sink(root,x,y,lfnr);
  334.   return p;
  335. }
  338. // ------------------------------------------------------------------
  339. // sink()
  340. // laesst Intervall im Baum bis zu dem Knoten v abwaerts gleiten an dem 
  341. // gilt: 1.Komponente von split_value(v) <in> Intervall <Teilmenge von> x_range(v)
  343. iv_item iv_tree::sink(iv_item v, interval_item x, interval_item y, int lfnr)
  344. {
  345.    if (v)
  346.    {
  347.      if (split_in_x_interval(v,x))
  348.      {
  349.        if (x_nodelist(v)->lookup(x))
  350.        {
  351.          error_handler(0,"Interval wurde schon eingefuegt!n");
  352.  split_pair h(x->koo1,-lfnr);
  353.  split_item hi=&h;
  354.  del(hi);
  355.  return 0;
  356.        }
  357.        x_nodelist(v)->insert(x,lfnr);
  358.        y_nodelist(v)->insert(y,lfnr);
  359.        return v;
  360.      }
  361.      else
  362.      {
  363.        if (x->cmp(x->koo2,split_value(v)->key1) < 0)
  364.        { 
  365.  return sink(v->son[_left],x,y,lfnr);
  366.        }
  367.        else
  368.        if (x->cmp(split_value(v)->key1,x->koo1) < 0)
  369.        {
  370.  return sink(v->son[_right],x,y,lfnr);
  371.        }
  372.      }
  373.    }
  375.    return 0;
  376. }
  378. // ------------------------------------------------------------------
  379. // iv_delete(x_typ,x_typ)
  380. // loescht ein Intervall (x,y) aus dem Baum
  381. // gibt Zeiger auf geloeschtes intervall zurueck 
  383. void iv_tree::iv_delete(x_typ x, x_typ y)
  384. {
  385.   if (y<x) 
  386.   {
  387.    error_handler(0,"kein Intervall!n");
  388.    return;
  389.   }
  390.   else
  391.   if (!root) error_handler(0,"Baum ist leer!n");
  392.   else
  393.   {
  394.    iv_item v = root;
  395.    interval xi(x,y);
  396.    interval yi(y,x);
  397.    interval_item x_iv = &xi;
  398.    interval_item y_iv = &yi; 
  399.    while ( !split_in_x_interval(v,x_iv) && !v->blatt() )
  400.    {
  401.     if (split_value(v)->cmp(y,split_value(v)->key1) < 0)
  402.     {
  403.       v = v->son[_left];
  404.     }
  405.     if (split_value(v)->cmp(split_value(v)->key1,x) < 0) 
  406.     {
  407.       v = v->son[_right];
  408.     }
  409.    }
  410.    // nun ist v der Knoten an dem das Intervall [x,y] abgespeichert sein muesste
  411.    dic_item help1 = x_nodelist(v)->lookup(x_iv);
  412.    dic_item help2 = y_nodelist(v)->lookup(y_iv);
  413.    if (!(help1 && help2))
  414.    {
  415.     error_handler(0,"Intervall nicht vorhanden!n");
  416.     return;
  417.    }
  418.    else
  419.    {
  420.     split_pair s(x_nodelist(v)->key(help1)->koo1,-x_nodelist(v)->inf(help1));
  421.     split_item search_split = &s; 
  422.     x_nodelist(v)->del_item(help1);
  423.     y_nodelist(v)->del_item(help2);
  424.     if (!del(search_split)) 
  425.       error_handler(1,"Intervall geloescht, Grundstruktur nicht in Ordnungn");
  426.    } 
  427.   }
  428. }
  431. // ------------------------------------------------------------------
  432. // del()
  433. // loescht Item it im Baum mit split(it)=y , falls existiert
  434. // gibt 1 zurueck, falls existent und geloescht
  435. // gibt 0 zurueck, falls nicht existent
  437. int iv_tree::del(split_item y)
  438. {
  439.   st.clear();
  440.   if (root==0) return 0;                         // s.n.
  442.   if (root->blatt())                             // Wurzel loeschen
  443.     if (cmp(y,split_value(root))==0)
  444.     { 
  445.       if (!x_nodelist(root)->empty()) 
  446.  error_handler(1,"noch Intervalle in zu loeschender Wurzel!n");
  447.       anzahl=0; 
  448.       delete root;
  449.       root=0; 
  450.       return 1; 
  451.     }
  452.     else
  453.     {
  454.      error_handler(0,"Element nicht im Baumn");  
  455.      return 0;
  456.     }
  457.   else // Baum nicht trivial
  458.   {
  459.     iv_item p,father;
  460.     iv_item pp=search(y);
  461.     if (st.size()==2)                            // Sohn der Wurzel
  462.     { 
  463.       p=st.pop();
  464.       father=st.pop();
  466.       int v1 = cmp(y,split_value(father));
  467.       if (cmp(y,split_value(p))!=0)
  468.       {
  469.         return 0;
  470.       }
  471.       anzahl--;
  472.       if (v1<=0)
  473.       {
  474.         root=root->son[_right];
  475. if(!x_nodelist(father)->empty())
  476.   nodelist_swap(father,root);
  477.       }
  478.       else
  479.       {
  480.         root=root->son[_left];
  481. if(!x_nodelist(father)->empty())
  482.   {
  483.     if (!root->son[_right]) 
  484.        nodelist_swap(father,root);
  485.             else
  486.     if ((root->son[_right])&&(x_nodelist(father)->size()==2))
  487.             {
  488.        nodelist_swap(father,root->son[_right]);
  489.        reorganize_nodelist(root,root->son[_right]);
  490.             }
  491.             else
  492.        nodelist_swap(father,root->son[_right]);
  493.           } 
  494.       }
  495.       if (!x_nodelist(father)->empty() || !x_nodelist(p)->empty())
  496. error_handler(1,"Knotenlisten beim Loeschen nicht leern");
  497.       delete father;
  498.       delete p;
  499.     }
  500.     else                                // Blatt mit Tiefe >= 2     
  501.     {
  502.       iv_item p=st.pop();
  503.       if (cmp(y,split_value(p))!=0)
  504.       { 
  505. return 0;
  506.       }
  507.       iv_item q = st.pop();
  508.       father = st.top();
  509.       int v1 = cmp(y,split_value(father));
  510.       int v2 = cmp(y,split_value(q));
  511.       anzahl--;
  512.       if (v1<=0)
  513.         if (v2<=0)
  514. {
  515.   father->son[_left]=q->son[_right];
  516.   if(!x_nodelist(q)->empty())
  517.     nodelist_swap(q,father->son[_right]);
  518.         }
  519.         else
  520. {
  521.   father->son[_left]=q->son[_left];
  522.   if(!x_nodelist(q)->empty())
  523.   {
  524.     if (!father->son[_left]->son[_right])
  525.        nodelist_swap(q,father->son[_left]);
  526.             else
  527.     if ((father->son[_left]->son[_right])&&(x_nodelist(q)->size()==2))
  528.             {
  529.        nodelist_swap(q,father->son[_left]->son[_right]);
  530.        reorganize_nodelist(father->son[_left],father->son[_left]->son[_right]);
  531.             }
  532.             else
  533.        nodelist_swap(q,father->son[_left]->son[_right]);
  534.           } 
  535.         }
  536.       else
  537. if (v2<=0)
  538. {
  539.   father->son[_right]=q->son[_right];
  540.   if(!x_nodelist(q)->empty())
  541.     nodelist_swap(q,father->son[_right]);
  542.         }
  543.         else
  544. {
  545.   father->son[_right]=q->son[_left];
  546.   if(!x_nodelist(q)->empty())
  547.   {
  548.     if (!father->son[_right]->son[_right])
  549.        nodelist_swap(q,father->son[_right]);
  550.             else
  551.     if ((father->son[_right]->son[_right])&&(x_nodelist(q)->size()==2))
  552.             {
  553.        nodelist_swap(q,father->son[_right]->son[_right]);
  554.        reorganize_nodelist(father->son[_right],father->son[_right]->son[_right]);
  555.             }
  556.             else
  557.        nodelist_swap(q,father->son[_right]->son[_right]);
  558.           } 
  559.         }
  560.       if (!x_nodelist(p)->empty())
  561. error_handler(1,"Knotenlisten von p beim Loeschen nicht leer");
  562.       delete p;
  563.       delete q;
  564.     }
  565.   }
  566.   
  567.   // REBALANCIEREN
  568.   iv_item p;
  569.   iv_item father;
  570.   while (!st.empty())
  571.   { p = st.pop();
  572.     father = st.empty() ? 0 : st.top() ;
  573.     p->gr--;              
  574.     float i=p->bal();
  575.     if (i<alpha)
  576.       if (p->son[_right]->bal() <= d)
  577.        lrot(p,father);
  578.       else
  579.        ldrot(p,father);
  580.     else
  581.     if (i>1-alpha)
  582.       if(p->son[_left]->bal() > d)
  583.        rrot(p,father);
  584.       else
  585.        rdrot(p,father);
  586.   }
  587.   return 1;
  588. }
  591. // ------------------------------------------------------------------
  592. // iv_query(x_typ,x_typ)
  593. // gibt alle Intervalle in einer Liste zurueck, die das mit 
  594. // den Parametern uebergebene Intervall schneiden.
  596. interval_list iv_tree::iv_query(x_typ x, x_typ y)
  597. {
  598.  interval_list query_list;
  599.  if (!root)
  600.  {
  601.    error_handler(0,"Baum ist leer");
  602.    return query_list;
  603.  } 
  604.  if (y<x)
  605.  { 
  606.   error_handler(0,"kein Intervalln");
  607.   return query_list;
  608.  }
  609.  split_pair xp(x,-MAXINT);
  610.  split_pair yp(y,MAXINT);
  611.  split_item xi = &xp;
  612.  split_item yi = &yp;
  613.  iv_item v = root;
  614.  int done=0;
  615.  // Bestimmung der P-Menge mit Hilfe von search-Schleife nach x,
  616.  // unterwegs Abzweig zu search nach y
  617.  // alle zwischen den Pfaden liegenden Knoten werden mit get_all
  618.  // abgearbeitet
  619.  // jeder Knoten wird mit Hilfe von check_iv() nach den in den 
  620.  // Knotenmengen vorhandenen Intervallen, die die Schnittbegingung
  621.  // erfuellen abgearbeitet.
  622.  while (!v->blatt())
  623.  {
  624.    check_nodelist(query_list,v,x,y);
  625.    if (cmp(xi,split_value(v))<=0) // xi <= split(v)
  626.    {
  627.      if ((cmp(yi,split_value(v))>0) && !done)
  628.      {
  629.        y_search(query_list,v->son[_right],yi,x,y);
  630.        done=1;
  631.      }
  632.      else
  633.      {
  634.        if (done)  // klappert den gesamten Unterbaum von v der C-Menge ab
  635.          get_all_in_tree(query_list,v->son[_right]);
  636.      }
  637.      v=v->son[_left];
  638.    }
  639.    else  // xi > split(v)
  640.    {
  641.      v=v->son[_right];
  642.    }
  643.  }
  644.  check_nodelist(query_list,v,x,y);
  645.  return query_list;
  646. }
  648. // ------------------------------------------------------------------
  649. // y_search()
  650. // verzweigt vom Knoten v aus, in einen neuen Suchpfad nach dem y-
  651. // Wert des query-Intervalls und fuehrt auch dort die P-checks durch
  653. void iv_tree::y_search(interval_list& il, iv_item v, split_item ys,
  654.        x_typ x, x_typ y)
  655. {
  656.  while (!v->blatt())
  657.  {
  658.    check_nodelist(il,v,x,y);
  659.    if (cmp(ys,split_value(v))<=0) // ys <= split(v)
  660.      v=v->son[_left];
  661.    else  // ys > split(v)
  662.    {
  663.      get_all_in_tree(il,v->son[_left]);
  664.      // klappert den gesamten Unterbaum von v der C-Menge ab
  665.      v=v->son[_right];
  666.    }
  667.  }
  668.  check_nodelist(il,v,x,y);
  669. }
  670.   
  671. // ------------------------------------------------------------------
  672. // check_nodelist()
  673. // ueberprueft entsprechend der in MEHLHORN III dargestellten Fall-
  674. // unterscheidung fuer P-Knoten die jeweilige x- oder y-Knotenliste
  675. // oder uebernimmt alle Eintraege.
  677. void iv_tree::check_nodelist(interval_list& il, iv_item v, x_typ x, x_typ y)
  678. {
  679.   if ((split_value(v)->cmp(x,split_value(v)->key1)<=0)
  680.   && (split_value(v)->cmp(split_value(v)->key1,y)<=0))
  681.   // dann ist split(v) im query-Intervall, das damit alle Intervalle
  682.   // der Knotenliste schneidet.
  683.     take_all_iv(il,v);
  684.   else
  685.   if (split_value(v)->cmp(x,split_value(v)->key1)>0)
  686.   // Intervall oberhalb des split(v)
  687.     check_y_iv(il,v,x);
  688.   else
  689.   // Intervall unterhalb des split(v)
  690.     check_x_iv(il,v,y);
  691. }
  694. // ------------------------------------------------------------------
  695. // get_all_in_tree()
  696. // uebernimmt alle im Unterbaum des Knotens v abgespeicherten Inter-
  697. // valle in die uebergebene Liste
  698. // entspricht einer Teilmenge der C-Menge
  700. void iv_tree::get_all_in_tree(interval_list& il, iv_item v)
  701. {
  702.   take_all_iv(il,v);
  703.   if (!v->blatt())
  704.   { 
  705.     get_all_in_tree(il,v->son[_left]);
  706.     get_all_in_tree(il,v->son[_right]);
  707.   }
  708. }
  710. // ------------------------------------------------------------------
  711. // take_all_iv()
  712. // uebernimmt an einem Knoten alle abgespeicherten Intervalle
  713. // in die mituebergebene Liste.
  715. void iv_tree::take_all_iv(interval_list& il, iv_item v)
  716. {
  717.   dic_item it;
  718.   forall_items(it,*(v->x_nodelist()))
  719.   {
  720.     interval_item help = x_nodelist(v)->key(it);
  721.     interval_item ii = new interval(help->koo1, help->koo2);
  722.     il.append(ii);
  723.   }
  724. }
  727. // ------------------------------------------------------------------
  728. // check_y_iv()
  729. // ueberprueft an einem Knoten alle Intervalle der y-Knotenliste
  730. // auf Schnittbedingung mit dem uebergebenen x-Wert des query-
  731. // Intervalls und haengt bei erfuellter Schnittbedingung das In-
  732. // tervall an die mituebergebene Liste an.
  734.   void iv_tree::check_y_iv(interval_list& il, iv_item v, x_typ x)
  735.   { 
  736.       if (!y_nodelist(v)->empty())
  737.       {
  738. dic_item maxit = y_nodelist(v)->max();
  739. if (split_value(v)->cmp(y_nodelist(v)->key(maxit)->koo1,x)>=0) 
  740. {
  741.   dic_item it = maxit;
  742.   int intersect = 1;
  743.   while(it && intersect) 
  744.   {
  745.     if (split_value(v)->cmp(y_nodelist(v)->key(it)->koo1,x)>=0) 
  746.     {
  747.      interval_item help = y_nodelist(v)->key(it); 
  748.      interval_item ii = new interval(help->koo2, help->koo1);
  749.      // die Intervalle der y-Knotenliste haben 1. Komponente
  750.      // y und 2. Komponente x, zur Rueckgabe ist aber die
  751.      // umgekehrte Reihenfolge verlangt.
  752.      il.append(ii);
  753.     }
  754.     else
  755.      intersect = 0;
  756.     it = y_nodelist(v)->pred(it);
  757.           }
  758.         }
  759.       }
  760.   }
  762. // ------------------------------------------------------------------
  763. // check_x_iv()
  764. // ueberprueft an einem Knoten alle Intervalle der x-Knotenliste
  765. // auf Schnittbedingung mit dem uebergebenen y-Wert des query-
  766. // Intervalls und haengt bei erfuellter Schnittbedingung das In-
  767. // tervall an die mituebergebene Liste an.
  769.   void iv_tree::check_x_iv(interval_list& il, iv_item v, x_typ y)
  770.   { 
  771.       if (!x_nodelist(v)->empty())
  772.       {
  773. dic_item minit = x_nodelist(v)->min();
  774. if (split_value(v)->cmp(x_nodelist(v)->key(minit)->koo1,y)<=0) 
  775. {
  776.   dic_item it = minit; 
  777.   int intersect = 1;
  778.   while(it && intersect) 
  779.   {
  780.     if (split_value(v)->cmp(x_nodelist(v)->key(it)->koo1,y)<=0) 
  781.     {
  782.      interval_item help = x_nodelist(v)->key(it); 
  783.      interval_item ii = new interval(help->koo1, help->koo2);
  784.      // die Intervalle der x-Knotenliste haben 1. Komponente
  785.      // x und 2. Komponente y.
  786.      il.append(ii);
  787.     }
  788.     else
  789.      intersect = 0;
  790.     it = x_nodelist(v)->succ(it);
  791.           }
  792.         }
  793.       }
  794.   }
  797. //-----------------------------------------------------------------------
  798. // void print_split(iv_item) 
  799. // gibt split_value von p aus
  801.   void iv_tree::print_split(iv_item it)   
  802.   { 
  803.     if (it)
  804.       { it->split_value()->print();
  805.         if (it->blatt()) text(" (blatt)n");
  806.         else text("(Knoten)n");
  807.        }
  808.     else
  809.       cout << " Knoten leer!n";
  810.   }
  815. //-----------------------------------------------------------------------
  816. // void pr_iv_tree(iv_item p;int blancs)
  817. // gibt den Baum mit Wurzel p aus
  819. void iv_tree::pr_iv_tree(iv_item p,int blancs)
  820. {
  821.  if (p==0)
  822.  {
  823.   for (int j=1;j<=blancs;j++) cout << " ";
  824.   cout << "NILn";
  825.   return;
  826.  }
  827.  else
  828.  {
  829.   pr_iv_tree(p->son[_left],blancs+10); 
  830.   for (int j=1;j<=blancs;j++) cout << " ";
  831.   
  832.   cout << "(" << p->split_value()->key1 << "," << p->split_value()->key2;
  833.   cout << ") ";
  834.   pr_iv_list(p);
  835.   pr_iv_tree(p->son[_right],blancs+10); 
  836.  }
  837. }
  838.  
  839. //-----------------------------------------------------------------------
  840. // void pr_iv_list(iv_item p)
  841. // gibt die Intervalliste eines Knotens p aus
  843. void iv_tree::pr_iv_list(iv_item p)
  844. {
  845.   dic_item it;
  846.   forall_items(it,*(p->x_nodelist()))
  847.   { cout << "[" << x_nodelist(p)->key(it)->koo1;
  848.     cout << "," << x_nodelist(p)->key(it)->koo2 << "]"; 
  849.     cout << "#" << x_nodelist(p)->inf(it) << ";";
  850.    }
  851.   cout << "  *  ";
  852.   forall_items(it,*(p->y_nodelist()))
  853.   { cout << "[" << y_nodelist(p)->key(it)->koo1;
  854.     cout << "," << y_nodelist(p)->key(it)->koo2<< "]"; 
  855.     cout << "#" << y_nodelist(p)->inf(it) << ";";
  856.    }
  857.   cout << "n";
  858. }
  860. //-----------------------------------------------------------------------
  861. // void pr_list()
  862. // gibt die zurueckgegebene Intervalliste der query aus
  864. void iv_tree::pr_list(interval_list& il)
  865. {
  866.   cout << "Liste: n";
  867.   if(il.empty()) cout << " leern";
  868.   list_item it;
  869.   forall_list_items(it,il)
  870.     il.contents(it)->print(); 
  871. }
  872.     
  874. //-----------------------------------------------------------------------
  875. // Funktion fuer Destruktor
  876. //-----------------------------------------------------------------------
  877.   
  878. void iv_tree::deltree(iv_item p)
  879. {
  880.  if (p)
  881.  {
  882.   if (!p->blatt())
  883.   {
  884.    deltree(p->son[_left]);
  885.    deltree(p->son[_right]);
  886.   }
  887.   delete(p);
  888.  }
  889. }