home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_300 / 308_01 / bfind.cpp < prev    next >
C/C++ Source or Header  |  1990-09-20  |  3KB  |  122 lines
  1.  
  2. /*
  3.     HEADER          CUG308;
  4.     TITLE:          Binary search on sorted List Object;
  5.     DATE:           9/21/90;
  6.     VERSION:        1.0;
  7.     FILENAME:       BFIND.CPP;
  8.     COMPILER:       Borland C++ V.1.0;
  9.     REQUIRES:    BASELIST.CPP, BASELIST.HPP, BFIND.HPP;
  10.     SEE-ALSO:       DBL_LIST.HPP, SGL_LIST.HPP;
  11.  
  12.     AUTHOR:         Michael Kelly
  13.                     254 Gold St. Boston, MA 02127
  14.             Copyright 1990;
  15.  
  16.     COPYRIGHT:    This code may not be commercially distributed
  17.             without prior arrangement with the author.  It
  18.             may be used by programmers, without royalty, for
  19.             their personal programs and for "one of a kind"
  20.             or "custom" applications, provided that said
  21.             programmers assume all liability concerning
  22.             same.
  23. */
  24.  
  25. /*
  26.  *  BFIND
  27.  */
  28.  
  29. #include <stddef.h>
  30. #include "bfind.hpp"
  31.  
  32. /*
  33.  *  routine to binary search sorted linked list instance
  34.  *  derived from class BaseList.
  35.  *
  36.  *  note:    BaseList is a virtual base class for linked list
  37.  *        objects.  It uses virtual functions, so calls made
  38.  *        through the BaseList pointer call the appropriate
  39.  *        function in the derived class.  I recommend using
  40.  *        class DoubleList with this function as the prev()
  41.  *        method for the SingleList class is slow ( having
  42.  *        only a forward pointing link in each node ).
  43.  *
  44.  *  arguments:  list -  a pointer of class type BaseList
  45.  *
  46.  *        item - void pointer to data to search for
  47.  *
  48.  *  warnings:    The linked list must be sorted or results are erroneous
  49.  *
  50.  *  returns:    True if item found -- item is the "current" item
  51.  *
  52.  *        False if item not found -- "current" location undefined
  53.  *        ( Use first() or last() method on return, to reset list
  54.  *          "cursor" or "current location" to a known state.     )
  55.  */
  56. Boolean bfind(BaseList *list, void *item)
  57. {
  58.     size_t i;                   // loop counter
  59.     size_t gap;            // gap used to halve search path
  60.     const int opt = 3;        // use this for performance tuning
  61.     const int termcount = 2;    // for ending "forever" while loop
  62.  
  63.     enum direction { left, right } direc;      // direction to step
  64.     int dif;                                    // comparison result
  65.     int count = 0;                // count of single steps
  66.     size_t list_entries = list->get_entries();   // entries in List
  67.  
  68.     if(! list_entries)
  69.     return False;
  70.  
  71.     if(list_entries < opt)
  72.     return(list->find_item(item));
  73.  
  74.         // compare to smallest item
  75.  
  76.     list->first();
  77.     if((dif = list->compare_item(item)) < 1)
  78.     return (Boolean) !dif;
  79.  
  80.         // compare to largest item
  81.  
  82.     list->last();
  83.     if((dif = list->compare_item(item)) > -1)
  84.     return (Boolean) !dif;
  85.  
  86.         // partition list in two
  87.  
  88.     gap = (list_entries >> 1) + (list_entries & 1);
  89.  
  90.     direc = left;
  91.  
  92.     // "forever" while loop
  93.  
  94.     while(gap)  {
  95.     if(direc == left)
  96.         for(i = 0;i < gap;i++)
  97.         list->prev();
  98.     else
  99.         for(i = 0;i < gap;i++)
  100.         list->next();
  101.  
  102.     /*
  103.      *  after stepping to center of partion,
  104.      *  make another comparison
  105.      */
  106.     if(!(dif = list->compare_item(item)))
  107.         return True;    // return True if "current" item is a match
  108.     else if(dif < 0)    // else ...
  109.         direc = left;   // set direction according to comparison
  110.     else
  111.         direc = right;
  112.  
  113.     if(gap == 1)
  114.         ++count;
  115.     if(count == termcount)
  116.         break;          // gaurantee an end to the loop
  117.  
  118.     gap = (gap >> 1) + (gap & 1);   // re-partition list
  119.     }
  120.     return False;
  121. }
  122.