home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / database / app_d_l / index.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-09-15  |  17.9 KB  |  929 lines
  1. /*
  2.  *
  3.  * Index manipulations.
  4.  *
  5.  * (C) 1990 Vision Software
  6.  *
  7.  * $Id: index.c 1.2001 91/04/25 15:08:06 pcalvin release $
  8.  *
  9.  * Comments:
  10.  *
  11.  * This class provides DATABASE if efficient indexing of the structures.
  12.  * It is currently implemented as a disk-based binary search tree.  Some
  13.  * extensions were required because we are using records instead of pointers
  14.  * First off, the implementation has been modified to link the binary tree
  15.  * in both directions.  Without this, traversing the tree would be an
  16.  * extremely ineffecient function.
  17.  * Secondly, recError is used as the terminator for nodes.  It is also used
  18.  * as the "parent" of the root.
  19.  *
  20.  * Bugs:
  21.  *
  22.  * Probably, none presently documented.
  23.  *
  24.  */
  25. #include <stdhdr.h>
  26. #include <string.h>
  27. #include <stdlib.h>
  28.  
  29. #include <dbase.h>
  30.  
  31. /*
  32.  * Absolute construction.  Follows normal ACCESS construction.
  33.  * In addition, we assert that if no records are available the idx
  34.  * structure truely reflects this..
  35.  */
  36. INDEX::INDEX(SZ sz,CCH cch) : ACCESS(&idx,sizeof(ITREE)+cch,sz,".inx",fTrue)
  37.     {
  38.     /*
  39.      * Assert there is records available, if not, fill in tree pointers to
  40.      * reflect this.
  41.      */
  42.     if (!FFirst())
  43.         {
  44.         idx.recLeft = recError;
  45.         idx.recRight = recError;
  46.         idx.recNext = recError;
  47.         idx.recPrevious = recError;
  48.         idx.recParent = recError;
  49.         }
  50.     }
  51.  
  52. /*
  53.  * Deletes the current index reference from the disk.
  54.  * Answers with the next record in the DATABASE, or recError
  55.  * if none exist.
  56.  *    Simplified if the record to delete has an identical key available
  57.  */
  58. REC INDEX::RecDelete()
  59.     {
  60.     REC recOriginal = RecQuery();
  61.     REC recParent = idx.recParent;
  62.     REC recLeft = idx.recLeft;
  63.     REC recRight = idx.recRight;
  64.     REC recPrevious = idx.recPrevious;
  65.     REC recAnswer = recError;
  66.  
  67.     /*
  68.      *    If key has duplicate, just replace entry
  69.      */
  70.     if (idx.recNext != recError)
  71.         {
  72.         REC recReplace = idx.recNext;
  73.  
  74.         /*
  75.          *    Fixup replacement first.
  76.          */
  77.         Verify(FGotoRec(recReplace));
  78.  
  79.         idx.recParent = recParent;
  80.         idx.recLeft = recLeft;
  81.         idx.recRight = recRight;
  82.         idx.recPrevious = recPrevious;
  83.  
  84.         Verify(FSave());
  85.  
  86.         /*
  87.          *    If we had previous similar key, fix it.
  88.          */
  89.         if (FGotoRec(recPrevious))
  90.             {
  91.             idx.recNext = recReplace;
  92.  
  93.             Verify(FSave());
  94.             }
  95.         
  96.         /*
  97.          *    Now, links to original part of tree
  98.          */
  99.         if (FGotoRec(recParent))
  100.             {
  101.             if (idx.recLeft == recOriginal)
  102.                 idx.recLeft = recReplace;
  103.             else    
  104.                 idx.recRight = recReplace;
  105.  
  106.             Verify(FSave());
  107.             }
  108.         else    
  109.             {
  110.             Verify(FMakeFirstRec(recReplace));
  111.             }
  112.  
  113.         /* 
  114.          *    And the children..
  115.          */
  116.         if (FGotoRec(recLeft))
  117.             {
  118.             idx.recParent = recReplace;
  119.  
  120.             Verify(FSave());
  121.             }
  122.  
  123.         if (FGotoRec(recRight))
  124.             {
  125.             idx.recParent = recReplace;
  126.  
  127.             Verify(FSave());
  128.             }
  129.  
  130.         /*
  131.          *    Where we want to end up
  132.          */
  133.         recAnswer = recReplace;
  134.         }
  135.     else if (FGotoRec(recPrevious))
  136.         {
  137.         idx.recNext = recError;
  138.         recAnswer = RecQuery();
  139.  
  140.         Verify(FSave());
  141.         }
  142.     else if (idx.recRight != recError)
  143.         {
  144.         Verify(FGotoRec(idx.recRight));
  145.  
  146.         /*
  147.          * If there is a left sub-tree, follow that chain, otherwise
  148.          * simply remove delete record from the list..
  149.          */
  150.         if (idx.recLeft == recError)
  151.             {
  152.             recAnswer = RecDeleteRightLinear(recOriginal,recParent,recLeft);
  153.             }
  154.         else
  155.             {
  156.             while (FGotoRec(idx.recLeft))
  157.                 ;
  158.  
  159.             recAnswer = RecDeleteRight(recOriginal,recParent,recRight,recLeft);
  160.             }
  161.         }
  162.     else if (idx.recLeft != recError)
  163.         {
  164.         Verify(FGotoRec(idx.recLeft));
  165.  
  166.         /*
  167.          * If there is a right sub-tree, follow that chain.  Otherwise
  168.          * remove from the list
  169.          */
  170.         if (idx.recRight == recError)
  171.             {
  172.             recAnswer = RecDeleteLeftLinear(recOriginal,recParent,recRight);
  173.             }
  174.         else
  175.             {
  176.             while (FGotoRec(idx.recRight))
  177.                 ;
  178.  
  179.             recAnswer = RecDeleteLeft(recOriginal,recParent,recRight,recLeft);
  180.             }
  181.         }
  182.     else
  183.         {
  184.         if (!FGotoRec(recParent))
  185.             {
  186.             Verify(FMakeFirstRec(recError));
  187.             }
  188.  
  189.         if (idx.recLeft == recOriginal)
  190.             idx.recLeft = recError;
  191.         else
  192.             idx.recRight = recError;
  193.  
  194.         Verify(FSave());
  195.         }
  196.  
  197.     /*
  198.      *    Delete original reference, Leave record pointer
  199.      *    at new current
  200.      */
  201.     Verify(FGotoRec(recOriginal));
  202.     Verify(FDelete());
  203.     
  204.     /*
  205.      *    Tell dBase where to go..
  206.      */
  207.     if (FGotoRec(recAnswer))
  208.         return (idx.rec);
  209.     else
  210.         return (recError);
  211.     }
  212.  
  213. /*
  214.  * Answers with the first logical record in the DATABASE.
  215.  * If there are any records, we simply follow the BST all the way
  216.  * to the left.  Otherwise, answer with recError
  217.  */
  218. REC INDEX::RecFirst()
  219.     {
  220.     REC recAnswer = recError;
  221.  
  222.     if (FFirst())
  223.         {
  224.         /*
  225.          * Search for the first record..
  226.          */
  227.         while (idx.recLeft != recError)
  228.             {
  229.             Verify(FGotoRec(idx.recLeft));
  230.             }
  231.  
  232.         /*
  233.          *    Assert we are at the beginning of at list..
  234.          */
  235.         while (idx.recPrevious != recError)
  236.             {
  237.             Verify(FGotoRec(idx.recPrevious));
  238.             }
  239.             
  240.         recAnswer = idx.rec;
  241.         }
  242.  
  243.     return (recAnswer);
  244.     }
  245.  
  246. /*
  247.  *    Answers with the last logical record in the DATABASE, recError
  248.  *    if none exist
  249.  */
  250. REC INDEX::RecLast()
  251.     {
  252.     REC recAnswer = recError;
  253.  
  254.     if (FFirst())
  255.         {
  256.         /*
  257.          *    Search for the last record
  258.          */
  259.         while (idx.recRight != recError)
  260.             {
  261.             Verify(FGotoRec(idx.recRight));
  262.             }
  263.  
  264.         /* 
  265.          *    Goto last in list..
  266.          */
  267.          while (idx.recNext != recError)
  268.              {
  269.              Verify(FGotoRec(idx.recNext));
  270.              }
  271.  
  272.         recAnswer = idx.rec;
  273.         }
  274.  
  275.     return (recAnswer);
  276.     }
  277.  
  278. /*
  279.  * Simple?? traversal of this BinarySearchTree.  This implementation is
  280.  * complicated by the fact that we may not use recusion to store the
  281.  * parent of a record.
  282.  *
  283.  *    If there is a duplicate key to follow, answer with that.
  284.  *
  285.  * Answers with the rec in the DATABASE, or recError
  286.  */
  287. REC INDEX::RecNext()
  288.     {
  289.     REC recOriginal = RecQuery();
  290.  
  291.     /*
  292.      *    Check first for a duplicate, if none are found, follow
  293.      *    recPrevious until we are at the head
  294.      */
  295.     if (idx.recNext != recError)
  296.         {
  297.         Verify(FGotoRec(idx.recNext));
  298.  
  299.         return (idx.rec);
  300.         }
  301.     else
  302.         {
  303.         Verify(FFirstInChain());
  304.         }
  305.         
  306.     REC rec = idx.recRight;
  307.     REC recAnswer = recError;
  308.     /*
  309.      * Two possibilities at this stage:
  310.      * 1. recRight != recError (i.e. Right subtree exists)
  311.      *     In this case, the next record is the farthest left sub
  312.      *     tree that exists..
  313.      * 2. recRight == recError (i.e. Right subtree does not exist)
  314.      *     This case has two possibilities:
  315.      *     1. Current branch is a left sub-tree
  316.      *         The next record is the parent of the current record
  317.      *     2. Current branch is a right sub-tree
  318.      *         Follow parent's chain while the child is a right sub-tree
  319.      *         the next record is the first parent who the child as a left
  320.      *         sub-tree
  321.      */
  322.     if (rec != recError)
  323.         {
  324.         while (FGotoRec(rec) && idx.recLeft != recError)
  325.             rec = idx.recLeft;
  326.  
  327.         recAnswer = idx.rec;
  328.         }
  329.     else
  330.         {
  331.         REC recSearchBase = RecQuery();
  332.         
  333.         if (idx.recParent == recError)
  334.             {
  335.             if (recOriginal != recError)
  336.                 {
  337.                 Verify(FGotoRec(recOriginal));
  338.                 }
  339.  
  340.             recAnswer = recError;
  341.             }
  342.         else
  343.             {
  344.             Verify(FGotoRec(idx.recParent));
  345.  
  346.             if (idx.recLeft == recSearchBase)
  347.                 {
  348.                 recAnswer = idx.rec;
  349.                 }
  350.             else
  351.                 {
  352.                 REC recChild = recSearchBase;
  353.  
  354.                 while (idx.recRight == recChild && idx.recParent != recError)
  355.                     {
  356.                     recChild = RecQuery();
  357.                     Verify(FGotoRec(idx.recParent));
  358.                     }
  359.  
  360.                 /*
  361.                  * Was a left-parent found??
  362.                  */
  363.                 if (idx.recLeft == recChild)
  364.                     {
  365.                     recAnswer = idx.rec;
  366.                     }
  367.                 else
  368.                     {
  369.                     Verify(FGotoRec(recOriginal));
  370.                     recAnswer = recError;
  371.                     }
  372.                 }
  373.             }
  374.         }
  375.  
  376.     return (recAnswer);
  377.     }
  378.  
  379. /*
  380.  * Answers with the previous record in the DATABASE, or recError
  381.  *
  382.  *    If there is a duplicate key previous, answer with that.
  383.  */
  384. REC INDEX::RecPrevious()
  385.     {
  386.     /*
  387.      *    Check first for a duplicate, if found, answer with that.
  388.      */
  389.     if (idx.recPrevious != recError)
  390.         {
  391.         Verify(FGotoRec(idx.recPrevious));
  392.  
  393.         return (idx.rec);
  394.         }
  395.         
  396.     REC rec = idx.recLeft;
  397.     REC recAnswer = recError;
  398.  
  399.     /*
  400.      * Two possibilities at this stage:
  401.      * 1. recLeft != recError (i.e. Left subtree exists)
  402.      *     In this case, the previous record is the farthest right
  403.      *     sub-tree of that record..
  404.      * 2. recLeft == recError (i.e. Left subtree does not exist)
  405.      *     This case as two possibilities:
  406.      *     1. Current branch is a right sub-tree
  407.      *         The parent(if it exists) is the previous one.
  408.      *     2. Current branch is a left sub-tree
  409.      *         Follow the parents chain while the child is a left-subtree
  410.      *         the previous record is the first parent that has the child as a
  411.      *         right sub-tree
  412.      */
  413.     if (rec != recError)
  414.         {
  415.         while (FGotoRec(rec) && idx.recRight != recError)
  416.             rec = idx.recRight;
  417.  
  418.         Verify(FLastInChain());    
  419.         recAnswer = idx.rec;
  420.         }
  421.     else
  422.         {
  423.         REC recOriginal = RecQuery();
  424.  
  425.         if (idx.recParent == recError)
  426.             {
  427.             if (recOriginal != recError)
  428.                 {
  429.                 Verify(FGotoRec(recOriginal));
  430.                 }
  431.  
  432.             recAnswer = recError;
  433.             }
  434.         else
  435.             {
  436.             Verify(FGotoRec(idx.recParent));
  437.  
  438.             if (idx.recRight == recOriginal)
  439.                 {
  440.                 Verify(FLastInChain());    
  441.                 recAnswer = idx.rec;
  442.                 }
  443.             else
  444.                 {
  445.                 REC recChild = recOriginal;
  446.  
  447.                 while (idx.recLeft == recChild && idx.recParent != recError)
  448.                     {
  449.                     recChild = RecQuery();
  450.                     Verify(FGotoRec(idx.recParent));
  451.                     }
  452.  
  453.                 /*
  454.                  * Did we find one??
  455.                  */
  456.                 if (idx.recRight == recChild)
  457.                     {
  458.                     Verify(FLastInChain());    
  459.                     recAnswer = idx.rec;
  460.                     }
  461.                 else
  462.                     {
  463.                     Verify(FGotoRec(recOriginal));
  464.                     recAnswer = recError;
  465.                     }
  466.                 }
  467.             }
  468.         }
  469.  
  470.     return (recAnswer);
  471.     }
  472.  
  473. /*
  474.  * Finally!! Something simple.  Here we are traversing the BST in search
  475.  * of sz.
  476.  * Answers with rec in DATABASE or recError if it doesn't exist..
  477.  *    If fMatchIfClose, we answer with a match only if sz matches
  478.  *    the key for its' length.
  479.  */
  480. REC INDEX::RecFromSz(SZ sz,CCH cch,BOOL fMatchIfClose)
  481.     {
  482.     Assert(sz != szNil);
  483.  
  484.     REC recAnswer = recError;
  485.     BOOL fContinue = fTrue;
  486.     CCH cchCompare = (fMatchIfClose) ? strlen(sz) : cch;
  487.  
  488.     /*
  489.      *    If sz is not safely formed, assert that the length
  490.      *    remains less than the maximum
  491.      */
  492.     if (cchCompare > cch)
  493.         cchCompare = cch;
  494.         
  495.     /*
  496.      *    Optimization.  If we are already at the key, just answer
  497.      *    Otherwise, if there are no records available, answer
  498.      */
  499.      if (strncmp(sz,idx.rgchKey,cchCompare) == 0)
  500.          return (idx.rec);
  501.     else if (!FFirst())
  502.         return (recError);
  503.  
  504.     /*
  505.      * Disk-based Binary Search Tree..
  506.      */
  507.     while (fContinue)
  508.         {
  509.         REC recSearch = recError;
  510.         DSZ dsz = strncmp(sz,idx.rgchKey,cchCompare);
  511.  
  512.         if (dsz == 0)
  513.             {
  514.             recAnswer = idx.rec;
  515.             fContinue = fFalse;
  516.             }
  517.         else if (dsz < 0)
  518.             {
  519.             recSearch = idx.recLeft;
  520.             }
  521.         else
  522.             {
  523.             recSearch = idx.recRight;
  524.             }
  525.  
  526.         if (fContinue)
  527.             fContinue = FGotoRec(recSearch);
  528.         }
  529.  
  530.     return (recAnswer);
  531.     }
  532.  
  533. /*
  534.  * Creates an index reference for the DATABASE.  Simple insertion
  535.  * into the BST.  Must be sure to recall the parents.  Also check
  536.  * for inserting if there are no records. (The ROOT)
  537.  */
  538. REC INDEX::RecCreateSz(SZ sz,CCH cchCompare,REC recCreated)
  539.     {
  540.     Assert(sz != szNil);
  541.  
  542.     REC recAnswer = recError;
  543.     REC recIndex = recError;
  544.     BOOL fContinue = fTrue;
  545.  
  546.     /*
  547.      * If this is the first record in the tree, just create it..
  548.      * Be sure to tell ACCESS() that this is the root of the tree.
  549.      */
  550.     if (!FFirst())
  551.         {
  552.         recIndex = RecFromSzCchRecRec(sz,cchCompare,recCreated,recError);
  553.         Verify(FMakeFirstRec(recIndex));
  554.         fContinue = fFalse;
  555.         recAnswer = recCreated;
  556.         }
  557.  
  558.     /*
  559.      * Disk-based Binary Search Tree..
  560.      */
  561.     while (fContinue)
  562.         {
  563.         DSZ dsz = strncmp(sz,idx.rgchKey,cchCompare);
  564.  
  565.         /*
  566.          *    If identical, Create the new record at the end of the chain.
  567.          *    Otherwise, continue search.
  568.          */
  569.         if (dsz == 0)
  570.             {
  571.             recIndex = RecCreateDuplicate(sz,cchCompare,recCreated);
  572.             recAnswer = recCreated;
  573.             fContinue = fFalse;
  574.             }
  575.         else if (dsz < 0)
  576.             {
  577.             /*
  578.              * Found end of BST.  Add new record into the INDEX
  579.              */
  580.             if (idx.recLeft == recError)
  581.                 {
  582.                 REC rec = RecQuery();
  583.                 
  584.                 recIndex = RecFromSzCchRecRec(sz,cchCompare,recCreated,rec);
  585.                 Verify(FGotoRec(rec));
  586.                 idx.recLeft = recIndex;
  587.                 Verify(FSave());
  588.                 recAnswer = recCreated;
  589.                 fContinue = fFalse;
  590.                 }
  591.             else
  592.                 {
  593.                 Verify(FGotoRec(idx.recLeft));
  594.                 }
  595.             }
  596.         else
  597.             {
  598.             /*
  599.              * Found end of BST.  New record is placed here..
  600.              */
  601.             if (idx.recRight == recError)
  602.                 {
  603.                 REC rec = RecQuery();
  604.                 
  605.                 recIndex = RecFromSzCchRecRec(sz,cchCompare,recCreated,rec);
  606.                 Verify(FGotoRec(rec));
  607.                 idx.recRight = recIndex;
  608.                 Verify(FSave());
  609.                 recAnswer = recCreated;
  610.                 fContinue = fFalse;
  611.                 }
  612.             else
  613.                 {
  614.                 Verify(FGotoRec(idx.recRight));
  615.                 }
  616.             }
  617.         }
  618.  
  619.     /*
  620.      *    Assure that we leave the index file pointing to the
  621.      *    current record
  622.      */
  623.     Verify(FGotoRec(recIndex));
  624.     
  625.     return (recAnswer);
  626.     }
  627.  
  628. /*
  629.  *    This function places a new record at the end of the chain.
  630.  *    Answers with the created record.
  631.  */
  632. REC INDEX::RecCreateDuplicate(SZ sz,CCH cch,REC recCreated)
  633.     {
  634.     /*
  635.      *    Follow chain..
  636.      */
  637.     while (idx.recNext != recError)
  638.         Verify(FGotoRec(idx.recNext));
  639.  
  640.     /*
  641.      *    For identical chains, this is simply a linked list..
  642.      */
  643.      REC recPrevious = RecQuery();
  644.      REC recNext = RecFromSzCchRecRec(sz,cch,recCreated,recError);
  645.      
  646.      /*
  647.       *    Now, both links have been created, join them..
  648.       */
  649.      Verify(FGotoRec(recNext));
  650.      idx.recPrevious = recPrevious;
  651.      Verify(FSave());
  652.      
  653.      Verify(FGotoRec(recPrevious));
  654.      idx.recNext = recNext;
  655.      Verify(FSave());
  656.  
  657.      return (recNext);
  658.     }
  659.     
  660. /*
  661.  * Creates a new record and copies the index entry and DATABASE destination
  662.  * to it..
  663.  */
  664. REC INDEX::RecFromSzCchRecRec(SZ sz,CCH cch,REC recCreated,REC recParent)
  665.     {
  666.     REC recIndex = RecCreate();
  667.  
  668.     strncpy(idx.rgchKey,sz,cch);
  669.     idx.rec = recCreated;
  670.     idx.recLeft = recError;
  671.     idx.recRight = recError;
  672.     idx.recPrevious = recError;
  673.     idx.recNext = recError;
  674.     idx.recParent = recParent;
  675.     Verify(FSave());
  676.  
  677.     return (recIndex);
  678.     }
  679.  
  680.  
  681. /*
  682.  * Deletes an entry from the Binary Search Tree.  In this case, we
  683.  * are deleting from a list
  684.  */
  685. REC INDEX::RecDeleteRightLinear(REC recOriginal,REC recParent,REC recLeft)
  686.     {
  687.     REC recReplace = RecQuery();
  688.  
  689.     idx.recParent = recParent;
  690.     idx.recLeft = recLeft;
  691.     idx.recNext = recError;
  692.     idx.recPrevious = recError;
  693.  
  694.     Verify(FSave());
  695.  
  696.     if (FGotoRec(recLeft))
  697.         {
  698.         idx.recParent = recReplace;
  699.  
  700.         Verify(FSave());
  701.         }
  702.  
  703.     if (!FGotoRec(recParent))
  704.         {
  705.         Verify(FMakeFirstRec(recReplace));
  706.         }
  707.     else
  708.         {
  709.         if (idx.recLeft == recOriginal)
  710.             idx.recLeft = recReplace;
  711.         else
  712.             idx.recRight = recReplace;
  713.  
  714.         Verify(FSave());
  715.         }
  716.  
  717.     return (recReplace);
  718.     }
  719.  
  720. /*
  721.  * Deletes an entry from the left line..
  722.  */
  723. REC INDEX::RecDeleteLeftLinear(REC recOriginal,REC recParent,REC recRight)
  724.     {
  725.     REC recReplace = RecQuery();
  726.  
  727.     idx.recParent = recParent;
  728.     idx.recRight = recRight;
  729.     idx.recNext = recError;
  730.     idx.recPrevious = recError;
  731.  
  732.     Verify(FSave());
  733.  
  734.     if (FGotoRec(recRight))
  735.         {
  736.         idx.recParent = recReplace;
  737.  
  738.         Verify(FSave());
  739.         }
  740.  
  741.     if (!FGotoRec(recParent))
  742.         {
  743.         Verify(FMakeFirstRec(recReplace));
  744.         }
  745.     else
  746.         {
  747.         if (idx.recLeft == recOriginal)
  748.             idx.recLeft = recReplace;
  749.         else
  750.             idx.recRight = recReplace;
  751.  
  752.         Verify(FSave());
  753.         }
  754.  
  755.     return (recReplace);
  756.     }
  757.  
  758.  
  759. /*
  760.  * Deletes an entry that doesn't fall in a linear list..
  761.  */
  762. REC INDEX::RecDeleteRight(REC recOriginal,REC recParent,REC recRight,REC recLeft)
  763.     {
  764.     REC recReplace = RecQuery();
  765.     REC recReplaceParent = idx.recParent;
  766.     REC recReplaceRight = idx.recRight;
  767.  
  768.     /*
  769.      * Step #1
  770.      */
  771.     Verify(FGotoRec(recReplaceParent));
  772.  
  773.     idx.recLeft = recReplaceRight;
  774.  
  775.     Verify(FSave());
  776.  
  777.     if (FGotoRec(recReplaceRight))
  778.         {
  779.         idx.recParent = recReplaceParent;
  780.  
  781.         Verify(FSave());
  782.         }
  783.  
  784.     /*
  785.      * Step #2
  786.      */
  787.     if (!FGotoRec(recParent))
  788.         {
  789.         Verify(FMakeFirstRec(recReplace));
  790.         }
  791.     else
  792.         {
  793.         if (idx.recLeft == recOriginal)
  794.             idx.recLeft = recReplace;
  795.         else
  796.             idx.recRight = recReplace;
  797.  
  798.         Verify(FSave());
  799.         }
  800.  
  801.     /*
  802.      * Step #3
  803.      */
  804.     if (FGotoRec(recRight))
  805.         {
  806.         idx.recParent = recReplace;
  807.  
  808.         Verify(FSave());
  809.         }
  810.  
  811.     if (FGotoRec(recLeft))
  812.         {
  813.         idx.recParent = recReplace;
  814.  
  815.         Verify(FSave());
  816.         }
  817.  
  818.     /*
  819.      * Step #4
  820.      */
  821.     Verify(FGotoRec(recReplace));
  822.  
  823.     idx.recParent = recParent;
  824.     idx.recRight = recRight;
  825.     idx.recLeft = recLeft;
  826.     idx.recNext = recError;
  827.     idx.recPrevious = recError;
  828.  
  829.     Verify(FSave());
  830.  
  831.     return (recReplace);
  832.     }
  833.  
  834. /*
  835.  * Deletes an entry that doesn't fall in a linear list..
  836.  */
  837. REC INDEX::RecDeleteLeft(REC recOriginal,REC recParent,REC recRight,REC recLeft)
  838.     {
  839.     REC recReplace = RecQuery();
  840.     REC recReplaceParent = idx.recParent;
  841.     REC recReplaceLeft= idx.recLeft;
  842.  
  843.     /*
  844.      * Step #1
  845.      */
  846.     Verify(FGotoRec(recReplaceParent));
  847.  
  848.     idx.recRight = recReplaceLeft;
  849.  
  850.     Verify(FSave());
  851.  
  852.     if (FGotoRec(recReplaceLeft))
  853.         {
  854.         idx.recParent = recReplaceParent;
  855.  
  856.         Verify(FSave());
  857.         }
  858.  
  859.     /*
  860.      * Step #2
  861.      */
  862.     if (!FGotoRec(recParent))
  863.         {
  864.         Verify(FMakeFirstRec(recReplace));
  865.         }
  866.     else
  867.         {
  868.         if (idx.recLeft == recOriginal)
  869.             idx.recLeft = recReplace;
  870.         else
  871.             idx.recRight = recReplace;
  872.  
  873.         Verify(FSave());
  874.         }
  875.  
  876.     /*
  877.      * Step #3
  878.      */
  879.     if (FGotoRec(recLeft))
  880.         {
  881.         idx.recParent = recReplace;
  882.  
  883.         Verify(FSave());
  884.         }
  885.  
  886.     if (FGotoRec(recRight))
  887.         {
  888.         idx.recParent = recReplace;
  889.  
  890.         Verify(FSave());
  891.         }
  892.  
  893.     /*
  894.      * Step #4
  895.      */
  896.     Verify(FGotoRec(recReplace));
  897.  
  898.     idx.recParent = recParent;
  899.     idx.recRight = recRight;
  900.     idx.recLeft = recLeft;
  901.     idx.recNext = recError;
  902.     idx.recPrevious = recError;
  903.  
  904.     Verify(FSave());
  905.  
  906.     return (recReplace);
  907.     }
  908.  
  909. /*
  910.  *    These functions allow use to move back and forth throughout a duplicate
  911.  *    key
  912.  */
  913. BOOL INDEX::FLastInChain()
  914.     {
  915.     while (idx.recNext != recError)
  916.         Verify(FGotoRec(idx.recNext));
  917.  
  918.     return (fTrue);
  919.     }
  920.  
  921. BOOL INDEX::FFirstInChain()
  922.     {
  923.     while (idx.recPrevious != recError)
  924.         Verify(FGotoRec(idx.recPrevious));
  925.  
  926.     return (fTrue);
  927.     }
  928.  
  929.