nucleus/library/structures/bit_vector.h

   1 #ifndef BIT_VECTOR_CLASS
   2 #define BIT_VECTOR_CLASS
   3
   4 /*****************************************************************************\
   5 *                                                                             *
   6 *  Name   : bit_vector                                                        *
   7 *  Author : Chris Koeritz                                                     *
   8 *                                                                             *
   9 *******************************************************************************
  10 * Copyright (c) 1990-$now By Author.  This program is free software; you can  *
  11 * redistribute it and/or modify it under the terms of the GNU General Public  *
  12 * License as published by the Free Software Foundation; either version 2 of   *
  13 * the License or (at your option) any later version.  This is online at:      *
  14 *     http://www.fsf.org/copyleft/gpl.html                                    *
  15 * Please send any updates to: fred@gruntose.com                               *
  16 \*****************************************************************************/
  17
  18 #include <basis/astring.h>
  19 #include <basis/definitions.h>
  20
  21 namespace structures {
  22
  23 //! An array of bits with operations for manipulating and querying individual bits.
  24
  25 class bit_vector
  26 {
  27 public:
  28   bit_vector();
  29     //!< creates a zero length bit_vector.
  30
  31   bit_vector(int size, const basis::abyte *initial = NULL_POINTER);
  32     //!< creates a bit_vector able to store "size" bits.
  33     /*!< if initial is NULL_POINTER, the vector is initialized to zero.  otherwise, the
  34     bits are copied from "initial".  "initial" must be large enough for the
  35     copying to succeed. */
  36
  37   bit_vector(const bit_vector &to_copy);
  38
  39   ~bit_vector();
  40
  41   bit_vector &operator =(const bit_vector &to_copy);
  42
  43   int bits() const;
  44     //!< returns the number of bits in the vector.
  45
  46   bool operator [] (int position) const;
  47     //!< returns the value of the bit at the position specified.
  48
  49   bool on(int position) const;
  50     //!< returns true if the bit at "position" is set.
  51
  52   bool off(int position) const;
  53     //!< returns true if the bit at "position" is clear.
  54
  55   void set_bit(int position, bool value);
  56     //!< sets the bit at "position" to a particular "value".
  57
  58   bool whole() const;
  59     //!< returns true if entire vector is set.
  60
  61   bool empty() const;
  62     //!< returns true if entire vector is unset.
  63
  64   int find_first(bool to_find) const;
  65     //!< Seeks the first occurrence of "to_find".
  66     /*!< locates the position at which a bit equal to to_find is located or it
  67     returns common::NOT_FOUND if no bit of that value is in the vector. */
  68
  69   void light(int position);
  70     //!< sets the value of the bit at "position".
  71
  72   void clear(int position);
  73     //!< clears the value of the bit at "position".
  74
  75   void resize(int size);
  76     //!< Changes the size of the bit_vector to "size" bits.
  77     /*!< This keeps any bits that still fit.  Any new bits are set to zero. */
  78
  79   void reset(int size);
  80     //!< resizes the bit_vector and clears all bits in it.
  81
  82   bool compare(const bit_vector &that, int start, int stop) const;
  83     //!< true if "this" is the same as "that" between "start" and "stop".
  84
  85   bool operator == (const bit_vector &that) const;
  86     //!< returns true if "this" is equal to "that".
  87     /*!< neither vector is changed.  if the vectors do not have the same size,
  88     false is returned. */
  89
  90   basis::astring text_form() const;
  91     //!< prints a nicely formatted list of bits to a string.
  92
  93   bit_vector subvector(int start, int end) const;
  94     //!< Extracts a chunk of the vector between "start" and "end".
  95     /*!< Returns a bit_vector that is copied from this one starting at "start"
  96     and running until "end".  An empty bit vector is returned if the indices
  97     are out of range. */
  98
  99   bool overwrite(int start, const bit_vector &to_write);
 100     //!< Stores bits from "to_write" into "this" at "start".
 101     /*!< overwrites the contents of this bit_vector with the contents of
 102     "to_write", beginning at "start" in this bit_vector.  true is returned
 103     for a successful write.  false will be returned if the "start" is out of
 104     range or if "to_write" is too large. */
 105
 106   basis::un_int get(int start, int size) const;
 107     //!< gets a portion of the vector as an unsigned integer.
 108     /*!< returns an integer (as interpreted by the operating system) where the
 109     pattern of bits in that integer is identical to the bits in this
 110     bit_vector, beginning at "start" and including enough bits for an
 111     integer of "size" bits. */
 112
 113   bool set(int start, int size, basis::un_int source);
 114     //!< puts the "source" value into the vector at "start".
 115     /*!< sets the pattern of bits in this bit_vector beginning at "start"
 116     identically to how they are stored in the integer "source", where the
 117     integer is expected to be using "size" of its bits.  the bits are copied
 118     starting from the low end of "source", where the operating system
 119     defines what the low end is.  true is returned for a successful copying. */
 120
 121   operator const basis::byte_array &() const;
 122     //!< returns a copy of the low-level implementation of the bit vector.
 123     /*!< the first bit is stored at the bit in first byte, and so forth. */
 124
 125 private:
 126   basis::byte_array *_implementation;  //!< holds the real state of the bits.
 127   int _number_of_bits;  //!< the total number of bits possible in this vector.
 128
 129   struct two_dim_location { int c_byte; int c_offset; };
 130     //!< a two-dimensional position given by byte number and offset within byte.
 131
 132   two_dim_location into_two_dim(int position) const;
 133     /*!< turns a bit position in the vector into a two dimensional position
 134     of the byte number and a bit offset within that byte. */
 135   bool get_bit(const two_dim_location &pos_in2) const;
 136     //!< returns the value of the bit given its two dimensional location.
 137   void set_bit(const two_dim_location &pos_in2, bool value);
 138     //!< sets the value of the bit if "value", and clears it if not.
 139 };
 140
 141 //////////////
 142
 143 // NOTE: these are operations on numbers, NOT on bit_vectors.
 144
 145 //! returns a number based on "to_modify" but with "bits" turned on.
 146 template <class type>
 147 void SET(type &to_modify, type bits) { to_modify |= bits; }
 148
 149 //! returns a number based on "to_modify" but with "bits" turned off.
 150 template <class type>
 151 void CLEAR(type &to_modify, type bits) { to_modify &= (type)~bits; }
 152
 153 //! returns non-zero if the "bits" bit pattern is turned on in "to_test".
 154 template <class type>
 155 bool TEST(type to_test, type bits) { return bool(!(!(to_test & bits))); }
 156
 157 //////////////
 158
 159 } //namespace.
 160
 161 #endif
 162