Merge branch 'dev' of feistymeow.org:feisty_meow into dev
[feisty_meow.git] / 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