home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / TBTREE.ZIP / BTREE.PAS next >
Encoding:
Pascal/Delphi Source File  |  1988-07-26  |  8.8 KB  |  192 lines
  1. (* TBTree13             Copyright (c)  1988            Dean H. Farwell II    *)
  2.  
  3. unit Btree;
  4.  
  5. (*****************************************************************************)
  6. (*                                                                           *)
  7. (*                      B T R E E   R O U T I N E S                          *)
  8. (*                                                                           *)
  9. (*****************************************************************************)
  10.  
  11. (* These routines are responsible for handling the indexes.  The scheme used
  12.    is Knuth's variation of B-Trees discussed on page 64 of "Database Systems
  13.    Volume I Fourth Edition" by C.J. Date.  There are two different types of
  14.    nodes in the tree.  The upper level(s) are index nodes and fill the role of
  15.    the normal B-Tree.  The lowest level nodes are sequence nodes and represent
  16.    dense index to the file.  The entries in the sequence node are sorted and
  17.    thus provide an alternate means to access information in the file.  This
  18.    allows rapid sorted retrievals without the need to sort.
  19.  
  20.    It is important to understand the operations can be performed on this BTree.
  21.    Routines provided are used to add a value, delete a value (one or more
  22.    occurences), create an index, and fetch a list of logical record numbers
  23.    corresponding to a value.  When an index file is created, the zeroth record,
  24.    the root node, and one sequence node are created.  Therefore, there will
  25.    always be one root node and one sequence node for every index.  The
  26.    sequence node can, of course, be empty.                                   *)
  27.  
  28. (* Version Information
  29.  
  30.    Version 1.1 - Corrected error in InsertValueInBTree routine.   I
  31.                  was not checking for duplicate entries.  This has
  32.                  been resolved.
  33.  
  34.                - Added GetRangeFromBTree routine
  35.  
  36.                - Added GetSubstringFromBTree routine
  37.  
  38.                - Divided the source code into 3 source files - BTREE.PAS
  39.                                                                BTREE1.INC
  40.                                                                BTREE1.INC
  41.  
  42.    Version 1.2 - No Changes
  43.  
  44.    Version 1.3 - Added NumberOfBTreeLevels routine                           *)
  45.  
  46. (*\*)
  47. (*////////////////////////// I N T E R F A C E //////////////////////////////*)
  48.  
  49. interface
  50.  
  51. uses
  52.     Compare,
  53.     FileDecs,
  54.     Files,
  55.     Numbers,
  56.     LRecList,
  57.     Page;
  58.  
  59. const
  60.     MAXVALSIZE    = 494;                          (* max value size in index *)
  61.  
  62. type
  63.     VSizeType     = 1 .. MAXVALSIZE;         (* size range for index entries *)
  64.  
  65.  
  66. (* This routine will create an index file and set the zeroth record as
  67.    appropriate.  The root node will also be created.  The root node will
  68.    be empty.
  69.  
  70.    note - File name passed as parameter does not have a file extension.  The
  71.    extension will be added and returned.
  72.  
  73.    note - Extremely important - WARNING - for CHARVALUE indexes only - the
  74.    valsize must be 1 greater than the number of characters of the longest
  75.    string.  This will allow 1 byte for the string length to be stored.
  76.    for example - if 'abc' is the longest string then valSize = 4.            *)
  77.  
  78. procedure CreateIndex(var iFName : FnString;
  79.                       valSize : VSizeType;
  80.                       dataFName : FnString;
  81.                       valType : ValueType);
  82.  
  83.  
  84. (* This routine will insert a value and its associated logical record number
  85.    into the given index file.  This routine will guard against duplicate
  86.    entries.  An index should have no more than one occurence of any
  87.    lrNum,paramValue pair (no two entries match on paramValue and lrNum).  This
  88.    routine assures this by calling DeleteValueFromBTree prior to performing the
  89.    insert.  This will get rid of a previous occurence if it exists.          *)
  90.  
  91. procedure InsertValueInBTree(iFName : FnString;
  92.                              lrNum : LRNumber;
  93.                              var paramValue);
  94.  
  95. (*\*)
  96. (* This routine will delete a value and its associated logical record number
  97.    from a given index file.  If the logical record number passed in is zero
  98.    then all records with a matching paramValue will be deleted.  Otherwise,
  99.    only the entry with the matching paramValue and the matching logical record
  100.    number will be deleted.                                                   *)
  101.  
  102. procedure DeleteValueFromBTree(iFName : FnString;
  103.                                lrNum : LrNumber;
  104.                                var paramValue);
  105.  
  106.  
  107. (* This routine will start at the root node and return the number of levels
  108. that exist in a BTree.  The index file name is the only required input.      *)
  109.  
  110. function NumberOfBTreeLevels(iFName : FnString) : Byte;
  111.  
  112.  
  113. (* This routine locates all values within the index which meet a condition
  114.    (cond) and returns a list of logical record numbers corresponding to these
  115.    values.
  116.  
  117.    note - In the case of  cond = EX (exists) all entries in the index will be
  118.    returned.  paramValue is not really used in this case so anything (a dummy)
  119.    can be passed in as the parameter corresponding to paramValue.            *)
  120.  
  121. procedure GetValuesFromBTree(iFName : FnString;
  122.                              var paramValue;
  123.                              cond : Condition;
  124.                              var lrLst : LrList);
  125.  
  126.  
  127. (* This routine locates all values within the index within a given range and
  128.    returns a list of logical record numbers corresponding to values within
  129.    that range.  The range is determined by paramValue1 and paramValue2.
  130.    paramValue1 must be less than paramValue2.  cond1 and cond2 are used to
  131.    determine if the range is inclusive or exclusive.  cond1 must be either
  132.    GE or GT and cond2 must be either LE or LT for this to work.  If any of
  133.    the above conditions is not true then an empty list will be returned.     *)
  134.  
  135. procedure GetRangeFromBTree(iFName : FnString;
  136.                             var paramValue1;
  137.                             cond1 : Condition;
  138.                             var paramValue2;
  139.                             cond2 : Condition;
  140.                             var lrLst : LrList);
  141.  
  142. (*\*)
  143. (* This routine locates partial string matches in an index of type
  144.    STRINGVALUE.  A partial string match occurs when the string passed in as
  145.    paramValue is contained within a string entry in the index.  You must
  146.    specify where in the string the match must occur.  You accomplish this by
  147.    using cond.  cond can be CO which stands for contains.  In this case, a
  148.    match occurs if the string passed in as paramValue is anywhere in the
  149.    string in the index.  Another option for cond is ST which stands for
  150.    starts.  A match will occur in this instance if paramValue is located at
  151.    the start of the string in the index.  The last option for cond is EN which
  152.    stands for ends.  A match here occurs if paramValue matches the last
  153.    characters in the index string.  Be aware that if paramValue and the string
  154.    being checked are the same length and they match exactly, then a match
  155.    would occur if any of the three options were selected (not earth shattering
  156.    but true nonetheless).
  157.  
  158.    Otherwise, this works like any of the other retrieval routines.  A list of
  159.    logical record numbers will be returned.
  160.  
  161.    This is exceptionally useful for many applications.  For example, a field
  162.    might be a 7 digit code stored as a string (STRINGVALUE).  The last two
  163.    digits might mean something in particular (part category, state, or
  164.    whatever).  Using this you can look for all the matches on only the last
  165.    two digits.
  166.  
  167.    One reality note here!! - For cond <> ST I have to look at every entry in
  168.    the index for matches.  Why this is true should be reasonably obvious.
  169.    Anyway, for cond = EN or cond = CO it will be somewhat slower than for cond
  170.    = ST.  How much slower depends on the size of the index.  It boils down to
  171.    the difference between a O(LOG(n)) algorithm and a O(n) algorithm, the
  172.    former being much faster for n = a large number.  If any of the above is
  173.    confusing ignore it and experiment.  It is still better to use this routine
  174.    than to grovel through all of the data records yourself!!                 *)
  175.  
  176. procedure GetSubstringFromBTree(iFName : FnString;
  177.                                 var paramValue;      (* must be a string var *)
  178.                                 cond : StringCondition;
  179.                                 var lrLst : LrList);
  180.  
  181.  
  182. (*\*)
  183. (*///////////////////// I M P L E M E N T A T I O N /////////////////////////*)
  184.  
  185. implementation
  186.  
  187. {$I btree1.inc}         (* most of the implementation part of the btree unit *)
  188.  
  189. {$I btree2.inc}         (* the rest of the implementation of the btree unit  *)
  190.  
  191. end.                                                    (* end of BTree unit *)
  192.