home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / sortseq.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  3.3 KB  |  97 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  sortseq.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 SORTSEQH
  19. #define SORTSEQH
  20.  
  21.  
  22. //------------------------------------------------------------------------------
  23. // sortseq: sorted sequences 
  24. //
  25. // data structure: (2,4)-Trees
  26. //
  27. // Stefan Naeher (1989)
  28. //------------------------------------------------------------------------------
  29.  
  30. #include <LEDA/ab_tree.h>
  31.  
  32. typedef ab_tree_node* seq_item;
  33.  
  34. #define sortseq(keytype,infotype) name3(keytype,infotype,sortseq)
  35.  
  36. #define sortseqdeclare2(keytype,infotype)\
  37. \
  38. struct sortseq(keytype,infotype) : public ab_tree {\
  39. \
  40. int  cmp(ent& x, ent& y) const { return compare(*(keytype*)&x,*(keytype*)&y); }\
  41. void clear_key(ent& x)   const { Clear(*(keytype*)&x); }\
  42. void clear_inf(ent& x)   const { Clear(*(infotype*)&x); }\
  43. void copy_key(ent& x)    const { Copy(*(keytype*)&x); }\
  44. void copy_inf(ent& x)    const { Copy(*(infotype*)&x); }\
  45. void print_key(ent& x)   const { Print(*(keytype*)&x); }\
  46. void print_inf(ent& x)   const { Print(*(infotype*)&x); }\
  47. \
  48. seq_item  lookup(keytype y) const { return ab_tree::lookup(Ent(y)); }\
  49. seq_item  locate(keytype y) const { return ab_tree::locate(Ent(y)); }\
  50. seq_item  locate_pred(keytype y) const { return ab_tree::locate_pred(Ent(y)); }\
  51. \
  52. seq_item  succ(seq_item x) const { return ab_tree::succ(x); }\
  53. seq_item  succ(keytype y) const { return locate(y); }\
  54. \
  55. seq_item  pred(seq_item x) const { return ab_tree::pred(x); }\
  56. seq_item  pred(keytype y) const { return locate_pred(y); }\
  57. \
  58. seq_item  insert(keytype y,infotype x)\
  59.                          { return ab_tree::insert(Ent(y),Ent(x)); } \
  60. \
  61. seq_item  insert_at(seq_item it,keytype y,infotype x)\
  62.                          { return ab_tree::insert_at_node(it,Ent(y),Ent(x)); } \
  63. \
  64. void      flip_items(seq_item a, seq_item b)    { ab_tree::flip(a,b); }\
  65. void      reverse_items(seq_item a, seq_item b) { ab_tree::reverse(a,b); }\
  66. \
  67. void      del(keytype y)         { ab_tree::del(Ent(y)); } \
  68. void      del_item(seq_item it)  { ab_tree::del_node(it); } \
  69. void      change_inf(seq_item it, infotype i) { ab_tree::change_inf(it,Ent(i));}\
  70. keytype   key(seq_item it)  const { return keytype(ab_tree::key(it)); }\
  71. infotype  inf(seq_item it)  const { return infotype(ab_tree::inf(it)); } \
  72. \
  73. void split(seq_item x,sortseq(keytype,infotype)& S1,sortseq(keytype,infotype)& S2)\
  74.                       { ab_tree::split_at_item(x,(ab_tree&)S1,(ab_tree&)S2); }\
  75. \
  76. sortseq(keytype,infotype)& conc(sortseq(keytype,infotype)& S)\
  77.                            { ab_tree::conc((ab_tree&)S); return *this; }\
  78. \
  79. sortseq(keytype,infotype)()    {}\
  80. sortseq(keytype,infotype)(const sortseq(keytype,infotype)& w) : ab_tree((ab_tree&)w) {}\
  81. \
  82. sortseq(keytype,infotype)& operator=(const sortseq(keytype,infotype)& w)\
  83. { ab_tree::operator=((ab_tree&)w); return *this; }\
  84. \
  85. ~sortseq(keytype,infotype)()   { clear(); }\
  86. } ;
  87.  
  88.  
  89. // ----------------------------------------------------------------
  90. // iteration
  91. // ----------------------------------------------------------------
  92.  
  93. #define forall_seq_items(i,S) for(i=(S).first_item(); i; i=(S).next_item(i))
  94.  
  95.  
  96. #endif
  97.