home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / tree_col.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  4.3 KB  |  139 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  tree_collection.h
  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. #ifndef DYNTREESH
  19. #define DYNTREESH
  20.  
  21. #include <LEDA/basic.h>
  22.  
  23.  /*********************************************************************\
  24.  *                                                                     *
  25.  *  dyna_trees T; deklariert eine (vorerst leere) Menge von dyn_trees  *
  26.  *                                                                     *
  27.  *  d_vertex T.maketree(); Erzeugt einen Baum, der genau einen Knoten  *
  28.  *     enthaelt (der in keinen anderem Baum enthalten ist.             *
  29.  *                                                                     *
  30.  *  d_vertex T.findroot(d_vertex v); Gibt die Wurzel des v enthaltenden*
  31.  *     Baumes zurueck.                                                 *
  32.  *                                                                     *  
  33.  *  d_vertex T.findcost(d_vertex v, double& d); Gibt den entsprechenden*
  34.  *     Knoten zurueck (s.o.), die Kosten werden im Argument d zurueck- *
  35.  *     gegeben.                                                        *
  36.  *                                                                     *
  37.  *  void   T.addcost(d_vertex v, double x); s.o.                       *
  38.  *                                                                     *
  39.  *  void   T.link(d_vertex v, d_vertex w); s.o.                        *
  40.  *                                                                     *
  41.  *  void   T.cut(d_vertex v); s.o.                                     *
  42.  *                                                                     *
  43.  *                                                                     *
  44.  * Implemented by Jan Timm                                             *
  45.  *                                                                     *
  46.  \*********************************************************************/
  47.  
  48.  
  49.  
  50.  
  51.  
  52. class d_node;
  53. typedef d_node *d_vertex;
  54. typedef d_node *d_path;
  55.  
  56. class d_node {
  57.  
  58. friend class dyna_trees;
  59.  
  60.      void*    info;        // user-defined information
  61.  
  62.      d_vertex left,        // linkes Kind
  63.               right,       // rechtes Kind
  64.               parent,      // Elter
  65.               successor,   // Nachfolger (fuer Pfad)
  66.               next;        // fuer Verkettung fuer ~dyna_tree
  67.  
  68.      double dcost,
  69.             dmin;
  70.  
  71.      d_node(void* i) { 
  72.                        left=right=parent=successor=next=0;
  73.                        dcost=dmin=0;
  74.                        info = i;
  75.                       };
  76. OPERATOR_NEW(10);
  77. OPERATOR_DEL(10);
  78.  
  79. };
  80.   
  81.    
  82. class dyna_trees {
  83.      d_vertex first,
  84.             last;  // diese beiden Zeiger fuer ~dyna_tree
  85.  
  86.      void splay(d_vertex);
  87.  
  88.      d_vertex assemble(d_vertex, d_vertex, d_vertex);
  89.      void   disassemble(d_vertex, d_vertex&, d_vertex&);
  90.  
  91.      d_vertex makepath(void*);
  92.      d_vertex findpath(d_vertex);
  93.      d_vertex findpathcost(d_path, double&);
  94.      d_vertex findtail(d_path);
  95.      void   addpathcost(d_path, double);
  96.      d_vertex join(d_path, d_path, d_path);
  97.      void   split(d_vertex, d_vertex&, d_vertex&);
  98.      
  99.      d_path   expose(d_vertex);
  100.  
  101. virtual void copy_inf(ent& x)      { x=x; }
  102. virtual void clear_inf(ent& x)     { x=0; }
  103.  
  104. public:
  105.      dyna_trees() { first=last=0; };
  106.      ~dyna_trees();
  107.  
  108.      void*    inf(d_vertex v) { return v->info; }
  109.        
  110.      d_vertex maketree(void*);
  111.      d_vertex findroot(d_vertex);
  112.      d_vertex findcost(d_vertex, double&);
  113.      void   addcost(d_vertex, double);
  114.      void   link(d_vertex, d_vertex);
  115.      void   cut(d_vertex);
  116. };
  117.  
  118. #define tree_collection(itype)  name2(itype,tree_collection)
  119.  
  120. #define tree_collectiondeclare(itype)\
  121. \
  122. class  tree_collection(itype) : public dyna_trees{\
  123. \
  124. void copy_inf(ent& x)      { x = Copy(*(itype*)&x); }\
  125. void clear_inf(ent& x)     { Clear(*(itype*)&x);    }\
  126. \
  127. public:\
  128. \
  129. d_vertex maketree(itype x)  { return dyna_trees::maketree(Ent(x)); }\
  130. itype    inf(d_vertex v)    { return itype(dyna_trees::inf(v)); }\
  131. \
  132.  tree_collection(itype)() {}\
  133. ~tree_collection(itype)() {}\
  134. \
  135. };
  136.  
  137. #endif
  138.  
  139.