home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Programmierung / SOURCE.mdf / programm / msdos / pascal / rehack / contain / bitset.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1993-06-21  |  9.3 KB  |  479 lines
  1. #include <mem.h>
  2. #include <dos.h>
  3. #include <assert.h>
  4.  
  5. #include "bitset.h"
  6.  
  7. inline int set_size(int low, int high) 
  8.  {
  9.   if (low >= high) return 0;
  10.   return ((((high - low + 1) >> 3) + 3) & 0xFFF0) + 12;
  11.  }
  12.  
  13. bitset::bitset()
  14.  {
  15.   low = 0;
  16.   siz = 0;
  17.   high = -1;
  18.   data = NULL;
  19.  }
  20.  
  21. void bitset::expand(int new_low, int new_high)
  22.  {
  23.   int   new_size;
  24.   char *new_data;
  25.  
  26.   new_low &= 0xFFF8;
  27.   if (data == NULL) {
  28.     low = new_low;
  29.     high = low - 1;
  30.    }
  31.   if (new_low > low)
  32.     new_low = low;
  33.   if ((new_high = ((new_high & 0xFFF8) + 7)) < high)
  34.     new_high = high;
  35.   if (new_low < low || new_high > high) {
  36.     new_size = set_size(new_low, new_high);
  37.     if (new_size > siz) {
  38.       new_data = new char[new_size];
  39.       assert(FP_SEG(new_data) < 0xA000);
  40.       memcpy(new_data, data, siz);
  41.       if (data != NULL)
  42.         delete data;
  43.       data = new_data;
  44.       siz = new_size;
  45.      }
  46.     assert(siz > 0);
  47.     if (low > new_low) {
  48.       int o = (low - new_low) >> 3;
  49.       assert(siz >= o + ((high - low + 1) >> 3));
  50.       memmove(data + o, data, (high - low + 1) >> 3);
  51.       assert(siz >= o);
  52.       memset(data, 0, o);
  53.       low = new_low;
  54.      }
  55.     if (high < new_high) {
  56.       assert(siz >= ((high - low + 1) >> 3) + ((new_high - high) >> 3));
  57.       memset(data + ((high - low + 1) >> 3), 0, ((new_high - high) >> 3));
  58.       high = new_high;
  59.      }
  60.     assert(FP_SEG(data) < 0xA000);
  61.    }
  62.  }
  63.  
  64. void bitset::contract()
  65.  {
  66.   char  *pt;
  67.   int   new_low;
  68.   int   new_high;
  69.   int   new_size;
  70.   int   o;
  71.   int   s;
  72.  
  73.   if (data == NULL) return;
  74.   new_low = low;
  75.   new_high = high;
  76.   pt = data;
  77.   while ((new_low < high) && !*pt++)
  78.     new_low += 8;
  79.   pt = data + ((high - low - 7) >> 3);
  80.   while ((new_high > new_low) && !*pt--)
  81.     new_high -= 8;
  82.   if (new_high <= new_low) {
  83.     low = 0;
  84.     high = -1;
  85.     delete data;
  86.     data = NULL;
  87.     siz = 0;
  88.    } else if (new_low > low || new_high < high) {
  89.     new_size = set_size(new_low, new_high);
  90.     s = (new_high - new_low + 1) >> 3;
  91.     assert(new_size > 0);
  92.     o = (new_low - low) >> 3;
  93.     if (new_size < siz) {
  94.       pt = new char [new_size];
  95.       assert(new_size >= s);
  96.       memcpy(pt, data + o, s);
  97.       delete data;
  98.       data = pt;
  99.       siz = new_size;
  100.      } else if (low < new_low) {
  101.       assert(siz > s);
  102.       memmove(data, data + o, s);
  103.      }
  104.     low = new_low;
  105.     high = new_high;
  106.    }
  107.  }
  108.  
  109. bitset::~bitset()
  110.  {
  111.   if (data != NULL) {
  112.     assert(FP_SEG(data) > 10);
  113.     if (FP_SEG(data) >= 0xA000)
  114.       assert(FP_SEG(data) < 0xA000);
  115.     delete data;
  116.     data = NULL;
  117.     siz = 0;
  118.    }
  119.  }
  120.  
  121. bitset::bitset(int n)
  122.  {
  123.   low = n & 0xFFF8;
  124.   high = low + 7;
  125.   siz = set_size(low, high);
  126.   data = new char[siz];
  127.   *data = 1 << (n - low);
  128.  }
  129.  
  130. bitset::bitset(int start, int stop)
  131.  {
  132.   low = 0;
  133.   high = -1;
  134.   data = NULL;
  135.   siz = 0;
  136.   set(start, stop);
  137.  }
  138.  
  139. bitset::bitset(bitset& arg) 
  140.  {
  141.   low = arg.low;
  142.   high = arg.high;
  143.   siz = arg.siz;
  144.   if (arg.data == NULL)
  145.     data = NULL;
  146.    else {
  147.     data = new char[siz];
  148.     memcpy(data, arg.data, siz);
  149.    }
  150.  }
  151.  
  152. int bitset::max()
  153.  {
  154.   int i, n;
  155.  
  156.   contract();
  157.   if (data == NULL) return 0;
  158.   n = data[(high - low) >> 3];
  159.   i = high - 7;
  160.   while ((n >>= 1) && i++) ;
  161.   return i;
  162.  }
  163.  
  164. int bitset::min()
  165.  {
  166.   int i;
  167.  
  168.   contract();
  169.   if (data == NULL) return 0;
  170.   i = 0;
  171.   while (!((1 << i) & *data)) i++;
  172.   return low + i;
  173.  }
  174.  
  175. void bitset::set(int start, int stop)
  176.  {
  177.   int size;
  178.  
  179.   if (start > stop) return;
  180.   expand(start, stop);
  181.   assert(FP_SEG(data) < 0xA000);
  182.   start -= low;
  183.   stop -= low;
  184.   size = (stop >> 3) - (start >> 3) - 1;
  185.   assert(start >= 0);
  186.   if (size < 0) {
  187.     assert(siz > (start >> 3));
  188.     data[start >> 3] |=
  189.       (0xFF << (start & 7)) & (0xFF >> (7 - (stop & 7)));
  190.    } else {
  191.     if (size > 0) {
  192.       assert(siz >= (start >> 3) + size + 1);
  193.       memset(data + (start >> 3) + 1, 0xFF, size);
  194.      }
  195.     assert(siz > (start >> 3));
  196.     data[start >> 3] |= 0xFF << (start & 7);
  197.     assert(siz > (stop >> 3));
  198.     data[stop >> 3] |= 0xFF >> (7 - (stop & 7));
  199.    }
  200.   assert(FP_SEG(data) < 0xA000);
  201.  }
  202.  
  203. void bitset::clear()
  204.  {
  205.   if (data != NULL) 
  206.     delete data;
  207.   data = NULL;
  208.   high = -1;
  209.   low = 0;
  210.   siz = 0;
  211.  }
  212.  
  213. void bitset::clear(int start, int stop)
  214.  {
  215.   int size;
  216.  
  217.   if (start > stop) return;
  218.   if (data == NULL) return;
  219.   if (stop > high) 
  220.     stop = high;
  221.   if (start < low)
  222.     start = low;
  223.   start -= low;
  224.   stop -= low;
  225.   assert(start >= 0);
  226.   size = (stop >> 3) - (start >> 3) - 1;
  227.   if (size < 0) {
  228.     assert(siz > (start >> 3));
  229.     data[start >> 3] &= 
  230.       (0xFF >> (8 - (start & 7))) & (0xFF << ((stop & 7) + 1));
  231.    } else {
  232.     if (size > 0) {
  233.       assert(siz >= (start >> 3) + size + 1);
  234.       memset(data + (start >> 3) + 1, 0, size);
  235.      }
  236.     assert(siz > (start >> 3));
  237.     data[start >> 3] &= 0xFF >> (8 - (start & 7));
  238.     assert(siz > (stop >> 3));
  239.     data[stop >> 3] &= 0xFF << ((stop & 7) + 1);
  240.    }
  241.   contract();
  242.  }
  243.  
  244. unsigned bitset::size()
  245.  {
  246.   unsigned count = 0;
  247.   unsigned i, j;
  248.   unsigned n;
  249.   char     bit;
  250.   char     *pt;
  251.  
  252.   pt = data;
  253.   n = (high - low + 1) >> 3;
  254.   while (n--) {
  255.     bit = 1;
  256.     j = 8;
  257.     while (j--) {
  258.       if ((*pt & bit) != 0)
  259.         count++;
  260.       bit <<= 1;
  261.      }
  262.     pt++;
  263.    }
  264.   return count;
  265.  }
  266.  
  267. char bitset::operator [] (int i)
  268.  {
  269.   if (i < low || i > high) 
  270.     return 0;
  271.   return data[(i - low) >> 3] & 1 << ((i - low) & 7);
  272.  }
  273.  
  274. int bitset::operator == (bitset& arg)
  275.  {
  276.   char *pt1, *pt2;
  277.   int  size;
  278.  
  279.   contract();
  280.   arg.contract();
  281.   if (data == NULL && arg.data == NULL)
  282.     return 1;
  283.   if (high != arg.high || low != arg.low)
  284.     return 0;
  285.   size = (high - low + 1) >> 3;
  286.   pt1 = data;
  287.   pt2 = arg.data;
  288.   while (size--)
  289.     if (*pt1++ != *pt2++)
  290.       return 0;
  291.   return 1;
  292.  }
  293.  
  294. int bitset::operator != (bitset& arg)
  295.  {
  296.   return !(*this == arg);
  297.  }
  298.  
  299. int bitset::operator > (bitset& arg)
  300.  {
  301.   char *pt1;
  302.   char *pt2;
  303.   int  size;
  304.  
  305.   arg.contract();
  306.   if (arg.data == NULL) 
  307.     return 1;
  308.   if (arg.low < low || arg.high > high)
  309.     return 0;
  310.   pt1 = data + ((arg.low - low) >> 3);
  311.   pt2 = arg.data;
  312.   size = (arg.high - arg.low) >> 3;
  313.   while (size--)
  314.     if ((*pt1++ ^ 0xFF) & *pt2++)
  315.       return 0;
  316.   return 1;
  317.  }
  318.  
  319. int bitset::operator < (bitset& arg)
  320.  {
  321.   return arg > *this;
  322.  }
  323.  
  324. bitset::operator void * ()
  325.  {
  326.   char *pt;
  327.   int   size;
  328.  
  329.   if (data == NULL)
  330.     return NULL;
  331.   pt = data;
  332.   size = (high - low + 1) >> 3;
  333.   while (size--)
  334.     if (*pt++)
  335.       return (void *) -1;
  336.   return NULL;
  337.  }
  338.  
  339. int bitset::operator ! ()
  340.  {
  341.   return ((void *) *this) == NULL;
  342.  }
  343.  
  344. bitset bitset::operator + (int i)
  345.  {
  346.   bitset temp(*this);
  347.   return temp += i;
  348.  }
  349.  
  350. bitset bitset::operator - (int i)
  351.  {
  352.   bitset temp(*this);
  353.   return temp -= i;
  354.  }
  355.  
  356. bitset bitset::operator + (bitset& arg)
  357.  {
  358.   bitset temp(*this);
  359.   return temp += arg;
  360.  }
  361.  
  362. bitset bitset::operator - (bitset& arg)
  363.  {
  364.   bitset temp(*this);
  365.   return temp -= arg;
  366.  }
  367.  
  368. bitset bitset::operator * (bitset& arg)
  369.  {
  370.   bitset temp(*this);
  371.   return temp *= arg;
  372.  }
  373.  
  374. bitset& bitset::operator = (bitset& arg)
  375.  {
  376.   int size;
  377.  
  378.   clear();
  379.   high = arg.high;
  380.   low = arg.low;
  381.   siz = arg.siz;
  382.   if (arg.data == NULL)
  383.     data = NULL;
  384.    else {
  385.     data = new char[siz];
  386.     memcpy(data, arg.data, siz);
  387.    }
  388.   return *this;
  389.  }
  390.  
  391. bitset& bitset::operator += (int i)
  392.  {
  393.   set(i, i);
  394.   return *this;
  395.  }
  396.  
  397. bitset& bitset::operator -= (int i)
  398.  {
  399.   clear(i,i);
  400.   return *this;
  401.  }
  402.  
  403. bitset& bitset::operator += (bitset& arg)
  404.  {
  405.   char *source;
  406.   char *dest;
  407.   int   size;
  408.  
  409.   expand(arg.low, arg.high);
  410.   source = arg.data;
  411.   dest = data + ((arg.low - low) >> 3);
  412.   size = (arg.high - arg.low + 1) >> 3;
  413.   assert(arg.low >= low);
  414.   assert(siz >= size + ((arg.low - low) >> 3));
  415.   while (size--)
  416.     *dest++ |= *source++;
  417.   return *this;
  418.  }
  419.  
  420. bitset &bitset::operator -= (bitset& arg)
  421.  {
  422.   int    start;
  423.   int    stop;
  424.   int    size;
  425.   char  *dest;
  426.   char  *source;
  427.  
  428.   if ((start = low) < arg.low)
  429.     start = arg.low;
  430.   if ((stop = high) > arg.high)
  431.     stop = arg.high;
  432.   if (start <= stop) {
  433.     dest = data + ((start - low) >> 3);
  434.     source = arg.data + ((start - arg.low) >> 3);
  435.     size = (stop - start + 1) >> 3;
  436.     assert(arg.siz >= size + ((start - arg.low) >> 3));
  437.     assert(siz >= size + ((start - low) >> 3));
  438.     while (size--) 
  439.       *dest++ &= 0xFF ^ *source++;
  440.    }
  441.   contract();
  442.   return *this;
  443.  }
  444.  
  445. bitset &bitset::operator *= (bitset& arg)
  446.  {
  447.   int    start;
  448.   int    stop;
  449.   int    size;
  450.   char  *source;
  451.   char  *dest;
  452.  
  453.   if (low < arg.low)
  454.     clear(low, arg.low - 1);
  455.   if (high > arg.high)
  456.     clear(arg.high + 1, high);
  457.   if ((start = low) < arg.low)
  458.     start = arg.low;
  459.   if ((stop = high) > arg.high)
  460.     stop = arg.high;
  461.   if (start <= stop) {
  462.     if (low > start)
  463.       assert(start >= low);
  464.     dest = data + ((start - low) >> 3);
  465.     assert(start >= arg.low);
  466.     source = arg.data + ((start - arg.low) >> 3);
  467.     size = (stop - start + 1) >> 3;
  468.     assert(arg.siz >= size + ((start - arg.low) >> 3));
  469.     assert(siz >= size + ((start - low) >> 3));
  470.     while (size--) 
  471.       *dest++ &= *source++;
  472.    }
  473.   assert(FP_SEG(data) < 0xA000);
  474.   contract();
  475.   assert(FP_SEG(data) < 0xA000);
  476.   return *this;
  477.  }
  478.  
  479.