X-Git-Url: https://feistymeow.org/gitweb/?a=blobdiff_plain;ds=sidebyside;f=core%2Flibrary%2Fstructures%2Fset.h;fp=core%2Flibrary%2Fstructures%2Fset.h;h=0000000000000000000000000000000000000000;hb=457b128b77b5b4a0b7dd3094de543de2ce1477ad;hp=3215080f66c9465ad53a4d93b811f0c337cb6c0b;hpb=32d7caf45d886d0d24e69eea00511c7815ac15d0;p=feisty_meow.git diff --git a/core/library/structures/set.h b/core/library/structures/set.h deleted file mode 100644 index 3215080f..00000000 --- a/core/library/structures/set.h +++ /dev/null @@ -1,315 +0,0 @@ -#ifndef SET_CLASS -#define SET_CLASS - -/*****************************************************************************\ -* * -* Name : set * -* Author : Chris Koeritz * -* * -******************************************************************************* -* Copyright (c) 1996-$now By Author. This program is free software; you can * -* redistribute it and/or modify it under the terms of the GNU General Public * -* License as published by the Free Software Foundation; either version 2 of * -* the License or (at your option) any later version. This is online at: * -* http://www.fsf.org/copyleft/gpl.html * -* Please send any updates to: fred@gruntose.com * -\*****************************************************************************/ - -#include "object_packers.h" -#include "string_array.h" - -#include -#include -#include -#include - -namespace structures { - -//! Emulates a mathematical set, providing several standard set operations. -/*! - Note: this is not an efficient object and it should not be used for - sets of non-trivial sizes. -*/ - -template -class set : public basis::array -{ -public: - //! Constructs a set with "num" elements, copying them from "init". - /*! Be very careful to ensure that the array "init" has sufficient length - for "num" elements to be copied from it. */ - set(int num = 0, const contents *init = NIL, - basis::un_short flags = basis::array::EXPONE) - : basis::array(num, init, flags) {} - - ~set() {} //!< Destroys any storage held for the set. - - int elements() const { return this->length(); } - //!< Returns the number of elements in this set. - - bool empty() const { return elements() == 0; } - //!< Returns true if the set has no elements. - bool non_empty() const { return elements() != 0; } - //!< Returns true if the set has some elements. - - void clear() { this->reset(); } //!< Empties out this set. - - bool member(const contents &to_test) const; - //!< Returns true if the item "to_test" is a member of this set. - - bool add(const contents &to_add); - //!< Adds a new element "to_add" to the set. - /*!< This always succeeds, but will return true if the item was not - already present. */ - - set &operator += (const contents &to_add) - { add(to_add); return *this; } - //!< An algebraic operator synonym for add() that operates on the contents. - set &operator += (const set &to_add) - { unionize(to_add); return *this; } - //!< An algebraic operator synonym for add() that operates on a set. - - bool remove(const contents &to_remove); - //!< Removes the item "to_remove" from the set. - /*!< If it was not present, false is returned and the set is unchanged. */ - - set &operator -= (const contents &to_zap) - { remove(to_zap); return *this; } - //!< An algebraic operator synonym for remove that operates on the contents. - set &operator -= (const set &to_zap) - { differentiate(to_zap); return *this; } - //!< An algebraic operator synonym for remove that operates on a set. - - set set_union(const set &union_with) const; - //!< Implements the set union of "this" with "union_with". - /*!< This returns the set formed from the union of "this" set with the set - specified in "union_with". (unfortunately, the name "set_union" must - be used to distinguish from the C keyword "union".) */ - - void unionize(const set &union_with); - //!< Makes "this" set a union of "this" and "union_with". - - set operator + (const set &uw) const { return set_union(uw); } - //!< A synonym for set_union. - - set intersection(const set &intersect_with) const; - //!< Returns the intersection of "this" with the set in "intersect_with". - - set operator * (const set &iw) const { return intersection(iw); } - //!< A synonym for intersection. - - set difference(const set &differ_with) const; - //!< Returns the difference of this with "differ_with". - /*!< Difference is defined as the subset of elements in "this" that are not - also in "differ_with". */ - - void differentiate(const set &differ_with); - //!< Makes "this" set equal to the difference of "this" and "differ_with". - /*!< That is, after the call, "this" will only contain elements that were - not also in "differ_with". */ - - set operator - (const set &dw) const { return difference(dw); } - //!< A synonym for difference. - - int find(const contents &to_find) const; - //!< Returns the integer index of the item "to_find" in this set. - /*!< This returns a negative number if the index cannot be found. Note - that this only makes sense within our particular implementation of set as - an array. */ - - //! Zaps the entry at the specified "index". - /*! This also treats the set like an array. The index must be within the - bounds of the existing members. */ - bool remove_index(int index) - { return this->zap(index, index) == basis::common::OKAY; } -}; - -////////////// - -//! provides a way to pack any set that stores packable objects. -template -void pack(basis::byte_array &packed_form, const set &to_pack) -{ - obscure_attach(packed_form, to_pack.elements()); - for (int i = 0; i < to_pack.elements(); i++) to_pack[i].pack(packed_form); -} - -//! provides a way to unpack any set that stores packable objects. -template -bool unpack(basis::byte_array &packed_form, set &to_unpack) -{ - to_unpack.clear(); - basis::un_int len; - if (!obscure_detach(packed_form, len)) return false; - contents to_fill; - for (int i = 0; i < (int)len; i++) { - if (!to_fill.unpack(packed_form)) return false; - to_unpack.add(to_fill); - } - return true; -} - -////////////// - -//! A simple object that wraps a templated set of ints. -class int_set : public set, public virtual basis::root_object -{ -public: - int_set() {} - //!< Constructs an empty set of ints. - int_set(const set &to_copy) : set(to_copy) {} - //!< Constructs a copy of the "to_copy" array. - - DEFINE_CLASS_NAME("int_set"); -}; - -//! A simple object that wraps a templated set of strings. -class string_set : public set, public virtual basis::packable -{ -public: - string_set() {} - //!< Constructs an empty set of strings. - string_set(const set &to_copy) - : set(to_copy) {} - //!< Constructs a copy of the "to_copy" array. - string_set(const string_array &to_copy) { - for (int i = 0; i < to_copy.length(); i++) - add(to_copy[i]); - } - - DEFINE_CLASS_NAME("string_set"); - - bool operator == (const string_set &compare) const { - for (int i = 0; i < elements(); i++) - if (get(i) != compare.get(i)) return false; - return true; - } - - operator string_array() const { - string_array to_return; - for (int i = 0; i < length(); i++) - to_return += get(i); - return to_return; - } - - virtual void pack(basis::byte_array &packed_form) const - { structures::pack(packed_form, *this); } - virtual bool unpack(basis::byte_array &packed_form) - { return structures::unpack(packed_form, *this); } - virtual int packed_size() const { - int to_return = sizeof(int) * 2; // length packed in, using obscure. - for (int i = 0; i < length(); i++) - to_return += get(i).length() + 1; - return to_return; - } -}; - -//! A set of pointers that hides the platform's pointer size. -class pointer_set : public set -{ -public: - pointer_set() {} - //!< Constructs an empty set of void pointers. - pointer_set(const set &to_copy) : set(to_copy) - {} - //!< Constructs a copy of the "to_copy" array. -}; - -////////////// - -// implementation for longer functions is below... - -template -bool set::member(const contents &to_test) const -{ - for (int i = 0; i < elements(); i++) - if (to_test == this->get(i)) - return true; - return false; -} - -template -bool set::add(const contents &to_add) -{ - if (member(to_add)) return false; - concatenate(to_add); - return true; -} - -template -int set::find(const contents &to_find) const -{ - for (int i = 0; i < elements(); i++) - if (to_find == this->get(i)) - return i; - return basis::common::NOT_FOUND; -} - -template -bool set::remove(const contents &to_remove) -{ - for (int i = 0; i < elements(); i++) - if (to_remove == this->get(i)) { - this->zap(i, i); - return true; - } - return false; -} - -template -set set::intersection(const set &intersect_with) const -{ - set created(0, NIL, this->flags()); - const set *smaller = this; - const set *larger = &intersect_with; - if (elements() > intersect_with.elements()) { - // switch the smaller one into place. - smaller = &intersect_with; - larger = this; - } - for (int i = 0; i < smaller->length(); i++) - if (larger->member(smaller->get(i))) - created.concatenate(smaller->get(i)); - return created; -} - -template -set set::set_union(const set &union_with) const -{ - set created = *this; - for (int i = 0; i < union_with.elements(); i++) - created.add(union_with.get(i)); - return created; -} - -template -void set::unionize(const set &union_with) -{ - for (int i = 0; i < union_with.elements(); i++) - add(union_with.get(i)); -} - -template -set set::difference(const set &differ_with) const -{ - set created = *this; - for (int i = 0; i < differ_with.elements(); i++) { - if (created.member(differ_with[i])) - created.remove(differ_with[i]); - } - return created; -} - -template -void set::differentiate(const set &differ_with) -{ - for (int i = 0; i < differ_with.elements(); i++) { - if (member(differ_with[i])) - remove(differ_with[i]); - } -} - -} // namespace. - -#endif -