// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- //
// C++ Header File Name: btwalker.h
// Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
// Produced By: Doug Gaer   
// File Creation Date: 12/02/1998 
// Date Last Modified: 03/15/1999
// Copyright (c) 1997 Douglas M. Gaer
// ----------------------------------------------------------- // 
// ---------- Include File Description and Details  ---------- // 
// ----------------------------------------------------------- // 
/*
The VBD C++ classes are copyright (c) 1997, by Douglas M. Gaer.
All those who put this code or its derivatives in a commercial
product MUST mention this copyright in their documentation for
users of the products in which this code or its derivative
classes are used. Otherwise, you have the freedom to redistribute
verbatim copies of this source code, adapt it to your specific
needs, or improve the code and release your improvements to the
public provided that the modified files carry prominent notices
stating that you changed the files and the date of any change.

THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
CORRECTION.

The BtreeWalkerb class defines a generic iterator used to walk
through balanced multi-way file-base trees. The BtreeWalker
class is a general-purpose class used to sort the entry keys
and perform search operations.
*/
// ----------------------------------------------------------- //   
#ifndef __BTWALKER_HPP
#define __BTWALKER_HPP

#include "btree.h"
#include "queue.h"  
#include "dllist.h"

enum BtreeWalkOrder {
  btPREORDER,  // Visit Root first, then Left, then Right subtree 
  btPOSTORDER, // Visit Left subtree first, then Right, then Root 
  btINORDER,   // Visit Left subtree first, then Root, then Right 
  btLVLORDER   // Visit (L)evel by (L)evel, start at Root, and go Left to Right
};

class BtreeWalkerb
{
public:
  BtreeWalkerb(Btree *t, BtreeWalkOrder w); 
  virtual ~BtreeWalkerb() { }

public:
  void Reset() { Reset(tree, worder); }
  void Reset(Btree *t, BtreeWalkOrder w); 
  CachePointer Next() { return (this->*NextFptr)(); }
  
protected:
  CachePointer (BtreeWalkerb::*NextFptr)(); // Pointer to member function
  CachePointer NextPreOrder();
  CachePointer NextInOrder();
  CachePointer NextPostOrder();
  CachePointer NextLvlOrder();
  
protected:
  Queue<__LWORD__> path;       // Current path of parents through the tree
  Queue<__LWORD__> right_path; // Current path of right parents 
  Btree *tree;                 // Pointer to the B-tree
  CachePointer root;           // Start of the B-tree being iterated
  CachePointer curr;           // Current node being traversed
  int state;                   // Holds up or down state indication 
  BtreeWalkOrder worder;       // Enumerated type of WalkOrder 
};

// The visit action defines a procedure used to process entry keys.
typedef void (*EntryKeyVisitFunc)(EntryKey &e); 

class BtreeWalker 
{
public:
  BtreeWalker(Btree *t) { btx = t; }
  ~BtreeWalker() { }

public:
  unsigned Sort(EntryKeyVisitFunc Visit);
  int Find(const EntryKey &key, EntryKey &e);
  unsigned Partiallookup(const char *p, EntryKeyVisitFunc Visit);

private:
  Btree *btx; // Pointer to the currently open B-tree
};

#endif // __BTWALKER_HPP
// ----------------------------------------------------------- // 
// ------------------------------- //
// --------- End of File --------- //
// ------------------------------- //
