home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c100 / 1.ddi / OOPWLD.ZIP / DIRECT / DIRTREE.HPP < prev    next >
Encoding:
C/C++ Source or Header  |  1990-06-11  |  2.6 KB  |  73 lines
  1. // DIRTREE.HPP: very simple binary tree to hold directory entries.
  2. // An inorder traversal of this tree produces a sorted list
  3. #include "direct2.hpp"
  4.  
  5. // Add two "overloaded operators" to our directory class:
  6. class dirfile3 : public dirfile2 {  // more inheritance
  7. public:
  8.   dirfile3() {} // what happens here? (base constructor called)
  9.   dirfile3(ffblk * file_info) { // overloaded function name
  10.     // at this point, the base class constructor has been called:
  11.     setfile(file_info);
  12.   }
  13.   // reference automatically takes the address:
  14.   int operator>(dirfile3 & d) { // overload the comparison operators
  15.     // note we access protected members here:
  16.     return strcmp(filename, d.filename) > 0;
  17.   }
  18.   int operator<(dirfile3 & d) {
  19.     return strcmp(filename, d.filename) < 0;
  20.   }
  21. };
  22.  
  23. // a tiny "collection" class:
  24. class dlist {
  25.   dirfile3 ** dl; // points to an array of pointers
  26.   int size, index;
  27.   static dirfile3 df3;  // for empty places in the list
  28. public:
  29.   dlist(int sz) : index(0) { 
  30.     dl = new dirfile3*[size = sz]; // space for array
  31.     for(int i = 0; i < size; i++)
  32.       dl[i] = &df3;  // set all elements to empty object
  33.   }
  34.   ~dlist() { delete dl; }  // clean up free store
  35.   void add(dirfile3 * d) {  // put things in
  36.     dl[index] = d;
  37.     // don't pass the end:
  38.     index = (index + 1 < size ? index + 1 : index);
  39.   }
  40.   // Operator overloading:
  41.   dirfile3 * operator[](int i) {
  42.     // Simple but robust error handling:
  43.     if(i < 0) return dl[0];
  44.     if(i >= size) return dl[size - 1];
  45.     return dl[i];
  46.   }
  47. };  
  48.  
  49. // Binary tree.  A dirtree is a node AND a tree, simultaneously:
  50. class dirtree {
  51.   dirfile3 * data;
  52.   dirtree * left, * right;
  53. public:
  54.   dirtree(dirfile3 * dat) : left(NULL), right(NULL), data(dat) {}
  55.   ~dirtree() {}  // do something intelligent here...
  56.   void add(dirfile3 * dat) { // insert a new node in the tree
  57.     if( *dat > *data) { // put it in the right tree (note operator call)
  58.       if(right) right->add(dat);  // if subtree is there, recursive call
  59.       else right = new dirtree(dat); // if not, make a new subtree
  60.     } else if(*dat < *data) {  // put it in left tree
  61.       if(left) left->add(dat); // if subtree is there, recursive call
  62.       else left = new dirtree(dat);  // if not, make a new subtree
  63.     }
  64.     // do nothing if it's already in the tree (dat == data)
  65.   }
  66.   // inorder traversal puts the sorted list sequentially into a dlist:
  67.   void distribute(dlist & dl) {
  68.     if(left) left->distribute(dl); // recursive call
  69.     dl.add(data);  // in-order traversal == sorted
  70.     if(right) right->distribute(dl); // recursive call
  71.   }
  72. };
  73.