136 lines
4.9 KiB
C++
136 lines
4.9 KiB
C++
/************************************************************************
|
|
* Copyright (c) 2005-2006 tok@openlinux.org.uk *
|
|
* *
|
|
* This software is provided as-is, without any express or implied *
|
|
* warranty. In no event will the authors be held liable for any *
|
|
* damages arising from the use of this software. *
|
|
* *
|
|
* Permission is granted to anyone to use this software for any purpose, *
|
|
* including commercial applications, and to alter it and redistribute *
|
|
* it freely, subject to the following restrictions: *
|
|
* *
|
|
* 1. The origin of this software must not be misrepresented; you must *
|
|
* not claim that you wrote the original software. If you use this *
|
|
* software in a product, an acknowledgment in the product documentation *
|
|
* would be appreciated but is not required. *
|
|
* *
|
|
* 2. Altered source versions must be plainly marked as such, and must *
|
|
* not be misrepresented as being the original software. *
|
|
* *
|
|
* 3. This notice may not be removed or altered from any source *
|
|
* distribution. *
|
|
************************************************************************/
|
|
#ifndef SET_H
|
|
#define SET_H
|
|
|
|
namespace Util {
|
|
|
|
/* Implements a set for non-negative integer values.
|
|
* storage is a char* which is either a member of this class,
|
|
* or given to an instance via alternative constructor
|
|
* or the set_data() function.
|
|
* Some macros are used to move to the correct char and
|
|
* read/write the binary data.
|
|
*/
|
|
class Set {
|
|
public:
|
|
/** Base constructor.
|
|
* Creates a set of size #MAX_SET_COUNT.
|
|
*/
|
|
Set();
|
|
|
|
/** Constructor with defined size.
|
|
* @param n the element count in an integer variable
|
|
*/
|
|
Set(int n);
|
|
/** Copy constructor, copies internal data of another Set.
|
|
* @param other reference to the other set
|
|
*
|
|
* \note This is a deep copy, rather than a shallow one; meaning
|
|
* this set will allocate memory and memcpy the data, not
|
|
* hold a pointer into the other set.
|
|
*/
|
|
Set(const Set & other);
|
|
|
|
/** Constructor with external data set.
|
|
* @param n Size of storage (in bits)
|
|
* @param data pointer to external storage
|
|
* \note The set will not handle freeing of this memory,
|
|
* it just works on it.
|
|
*/
|
|
Set(int n, unsigned char* data);
|
|
|
|
~Set();
|
|
|
|
/** Give another storage pointer to an instance.
|
|
* @param n size
|
|
* @param data pointer to data
|
|
* @note This only works for instances that were already
|
|
* constructed with external data.
|
|
*/
|
|
void set_data(int n, unsigned char* data);
|
|
|
|
/** Mutator for the last index.
|
|
* @param n the element count
|
|
* @note You should only shrink sets previously defined @e larger,
|
|
* not the other way round!
|
|
*/
|
|
void set_last(int n);
|
|
|
|
/** Set2Number - least significant bits first.
|
|
*/
|
|
int as_int(int start, int len) const;
|
|
|
|
/** Set2Number - most significant bits first.
|
|
*/
|
|
int as_int2(int start, int len) const;
|
|
|
|
/** Accessor for the last index.
|
|
* @return n the element count
|
|
*/
|
|
int get_last() const;
|
|
|
|
/** Mutator for the contained data.
|
|
* @param k the index of the item to change
|
|
* @param val true (k-th item in set) or false (not in set)
|
|
*/
|
|
void set_item(int k, bool val);
|
|
|
|
/** Accessor for the contained data.
|
|
* @param k item index to query
|
|
* @return val either true (item in set) or false (not in set)
|
|
*/
|
|
bool get_item(int k) const;
|
|
|
|
/** Test set for inclusion with another.
|
|
* the return value is either:
|
|
* 0 - the two sets are disjoint
|
|
* 1 - this set contains the other
|
|
* 2 - this set contains a subset of the other
|
|
* -1 - the other set contains this
|
|
* -2 - the other contains a subset of this
|
|
* 3 - the two sets are equal
|
|
* @param other a reference to another Set
|
|
* @return res an int value as listed above
|
|
*/
|
|
int compare(const Set & other) const;
|
|
|
|
/** Returns the address of the internal storage data.
|
|
* KNOW WHAT YOU ARE DOING WITH THIS
|
|
* @return storage a char* to the entire storage block
|
|
*/
|
|
unsigned char* give_storage() const;
|
|
|
|
void print_set() const;
|
|
|
|
protected:
|
|
int last;
|
|
private:
|
|
unsigned char* storage;
|
|
bool ext_data;
|
|
// make sure this is a power of 8
|
|
static const int MAX_SET_COUNT = 32;
|
|
};
|
|
}
|
|
#endif
|