sets.h

Go to the documentation of this file.

#ifndef SETS_H
#define SETS_H
 
#include "allocator.h"
#include "couple.h"
#include "hash.h"
#include "hashTable.h"
#include "set.h"
#include "ownerPtr.h"
#include "comparator.h"
#include "RBTree.h"
 
 
namespace original {
    template <typename TYPE,
              typename HASH = hash<TYPE>,
              typename ALLOC = allocator<couple<const TYPE, const bool>>>
    class hashSet final : public hashTable<TYPE, const bool, ALLOC, HASH>,
                          public set<TYPE, ALLOC>,
                          public iterable<const TYPE>,
                          public printable{
 
        using hashNode = typename hashTable<TYPE, const bool, ALLOC, HASH>::hashNode;
 
        using rebind_alloc_pointer = typename hashTable<TYPE, const bool, ALLOC, HASH>::rebind_alloc_pointer;
 
    public:
        class Iterator final : public hashTable<TYPE, const bool, ALLOC, HASH>::Iterator,
                             public baseIterator<const TYPE> {
 
            explicit Iterator(vector<hashNode*, rebind_alloc_pointer>* buckets = nullptr,
                              u_integer bucket = 0, hashNode* node = nullptr);
 
            bool equalPtr(const iterator<const TYPE>* other) const override;
 
        public:
            friend class hashSet;
 
            Iterator(const Iterator& other);
 
            Iterator& operator=(const Iterator& other);
 
            Iterator* clone() const override;
 
            [[nodiscard]] std::string className() const override;
 
            void operator+=(integer steps) const override;
 
            void operator-=(integer steps) const override;
 
            integer operator-(const iterator<const TYPE>& other) const override;
 
            [[nodiscard]] bool hasNext() const override;
 
            [[nodiscard]] bool hasPrev() const override;
 
            bool atPrev(const iterator<const TYPE>* other) const override;
 
            bool atNext(const iterator<const TYPE>* other) const override;
 
            void next() const override;
 
            void prev() const override;
 
            Iterator* getPrev() const override;
 
            const TYPE& get() override;
 
            const TYPE get() const override;
 
            void set(const TYPE& data) override;
 
            [[nodiscard]] bool isValid() const override;
 
            ~Iterator() override = default;
        };
 
        explicit hashSet(HASH hash = HASH{}, ALLOC alloc = ALLOC{});
 
        hashSet(const hashSet& other);
 
        hashSet& operator=(const hashSet& other);
 
        hashSet(hashSet&& other) noexcept;
 
        hashSet& operator=(hashSet&& other) noexcept;
 
        [[nodiscard]] u_integer size() const override;
 
        bool contains(const TYPE &e) const override;
 
        bool add(const TYPE &e) override;
 
        bool remove(const TYPE &e) override;
 
        Iterator* begins() const override;
 
        Iterator* ends() const override;
 
        [[nodiscard]] std::string className() const override;
 
        [[nodiscard]] std::string toString(bool enter) const override;
 
        ~hashSet() override;
    };
 
    template <typename TYPE,
              typename Compare = increaseComparator<TYPE>,
              typename ALLOC = allocator<couple<const TYPE, const bool>>>
    class treeSet final : public RBTree<TYPE, const bool, ALLOC, Compare>,
                          public set<TYPE, ALLOC>,
                          public iterable<const TYPE>,
                          public printable {
        using RBTreeType = RBTree<TYPE, const bool, ALLOC, Compare>;
 
        using RBNode = typename RBTreeType::RBNode;
    public:
        class Iterator final : public RBTreeType::Iterator,
                               public baseIterator<const TYPE>
        {
            explicit Iterator(RBTreeType* tree, RBNode* cur);
 
            bool equalPtr(const iterator<const TYPE>* other) const override;
        public:
            friend class treeSet;
 
            Iterator(const Iterator& other);
 
            Iterator& operator=(const Iterator& other);
 
            Iterator* clone() const override;
 
            [[nodiscard]] std::string className() const override;
 
            void operator+=(integer steps) const override;
 
            void operator-=(integer steps) const override;
 
            integer operator-(const iterator<const TYPE> &other) const override;
 
            [[nodiscard]] bool hasNext() const override;
 
            [[nodiscard]] bool hasPrev() const override;
 
            bool atPrev(const iterator<const TYPE>* other) const override;
 
            bool atNext(const iterator<const TYPE>* other) const override;
 
            void next() const override;
 
            void prev() const override;
 
            Iterator* getPrev() const override;
 
            const TYPE& get() override;
 
            const TYPE get() const override;
 
            void set(const TYPE& data) override;
 
            [[nodiscard]] bool isValid() const override;
 
            ~Iterator() override = default;
        };
 
        friend class Iterator;
 
        explicit treeSet(Compare comp = Compare{}, ALLOC alloc = ALLOC{});
 
        treeSet(const treeSet& other);
 
        treeSet& operator=(const treeSet& other);
 
        treeSet(treeSet&& other) noexcept;
 
        treeSet& operator=(treeSet&& other) noexcept;
 
        [[nodiscard]] u_integer size() const override;
 
        bool contains(const TYPE &e) const override;
 
        bool add(const TYPE &e) override;
 
        bool remove(const TYPE &e) override;
 
        Iterator* begins() const override;
 
        Iterator* ends() const override;
 
        [[nodiscard]] std::string className() const override;
 
        [[nodiscard]] std::string toString(bool enter) const override;
 
        ~treeSet() override;
    };
}
 
template<typename TYPE, typename HASH, typename ALLOC>
original::hashSet<TYPE, HASH, ALLOC>::Iterator::Iterator(vector<hashNode*, rebind_alloc_pointer> *buckets,
u_integer bucket, hashNode *node) : hashTable<TYPE, const bool, ALLOC, HASH>::Iterator(
    const_cast<vector<hashNode*, rebind_alloc_pointer>*>(buckets), bucket, node) {}
 
template<typename TYPE, typename HASH, typename ALLOC>
bool original::hashSet<TYPE, HASH, ALLOC>::Iterator::equalPtr(const iterator<const TYPE> *other) const {
    auto other_it = dynamic_cast<const Iterator*>(other);
    return other_it &&
           this->p_buckets == other_it->p_buckets &&
           this->cur_bucket == other_it->cur_bucket &&
           this->p_node == other_it->p_node;
}
 
template<typename TYPE, typename HASH, typename ALLOC>
original::hashSet<TYPE, HASH, ALLOC>::Iterator::Iterator(const Iterator &other) : Iterator() {
    this->operator=(other);
}
 
template<typename TYPE, typename HASH, typename ALLOC>
typename original::hashSet<TYPE, HASH, ALLOC>::Iterator&
original::hashSet<TYPE, HASH, ALLOC>::Iterator::operator=(const Iterator &other) {
    if (this == &other) {
        return *this;
    }
 
    hashTable<TYPE, const bool, ALLOC, HASH>::Iterator::operator=(other);
    return *this;
}
 
template<typename TYPE, typename HASH, typename ALLOC>
typename original::hashSet<TYPE, HASH, ALLOC>::Iterator*
original::hashSet<TYPE, HASH, ALLOC>::Iterator::clone() const {
    return new Iterator(*this);
}
 
template<typename TYPE, typename HASH, typename ALLOC>
std::string original::hashSet<TYPE, HASH, ALLOC>::Iterator::className() const {
    return "hashSet::Iterator";
}
 
template<typename TYPE, typename HASH, typename ALLOC>
void original::hashSet<TYPE, HASH, ALLOC>::Iterator::operator+=(integer steps) const {
    hashTable<TYPE, const bool, ALLOC, HASH>::Iterator::operator+=(steps);
}
 
template<typename TYPE, typename HASH, typename ALLOC>
void original::hashSet<TYPE, HASH, ALLOC>::Iterator::operator-=(integer) const {
    throw unSupportedMethodError();
}
 
template<typename TYPE, typename HASH, typename ALLOC>
original::integer
original::hashSet<TYPE, HASH, ALLOC>::Iterator::operator-(const iterator<const TYPE>&) const {
    throw unSupportedMethodError();
}
 
template<typename TYPE, typename HASH, typename ALLOC>
bool original::hashSet<TYPE, HASH, ALLOC>::Iterator::hasNext() const {
    return hashTable<TYPE, const bool, ALLOC, HASH>::Iterator::hasNext();
}
 
template<typename TYPE, typename HASH, typename ALLOC>
bool original::hashSet<TYPE, HASH, ALLOC>::Iterator::hasPrev() const {
    throw unSupportedMethodError();
}
 
template<typename TYPE, typename HASH, typename ALLOC>
bool original::hashSet<TYPE, HASH, ALLOC>::Iterator::atPrev(const iterator<const TYPE> *other) const {
    auto other_it = dynamic_cast<const Iterator*>(other);
    if (!other_it) {
        return false;
    }
    auto next = ownerPtr(this->clone());
    if (!next->isValid()){
        return false;
    }
 
    next->next();
    return next->equalPtr(other_it);
}
 
template<typename TYPE, typename HASH, typename ALLOC>
bool original::hashSet<TYPE, HASH, ALLOC>::Iterator::atNext(const iterator<const TYPE> *other) const {
    return other->atPrev(*this);
}
 
template<typename TYPE, typename HASH, typename ALLOC>
void original::hashSet<TYPE, HASH, ALLOC>::Iterator::next() const {
    hashTable<TYPE, const bool, ALLOC, HASH>::Iterator::next();
}
 
template<typename TYPE, typename HASH, typename ALLOC>
void original::hashSet<TYPE, HASH, ALLOC>::Iterator::prev() const {
    throw unSupportedMethodError();
}
 
template<typename TYPE, typename HASH, typename ALLOC>
typename original::hashSet<TYPE, HASH, ALLOC>::Iterator*
original::hashSet<TYPE, HASH, ALLOC>::Iterator::getPrev() const {
    throw unSupportedMethodError();
}
 
template<typename TYPE, typename HASH, typename ALLOC>
const TYPE& original::hashSet<TYPE, HASH, ALLOC>::Iterator::get() {
    return hashTable<TYPE, const bool, ALLOC, HASH>::Iterator::get().template get<0>();
}
 
template<typename TYPE, typename HASH, typename ALLOC>
const TYPE original::hashSet<TYPE, HASH, ALLOC>::Iterator::get() const {
    return hashTable<TYPE, const bool, ALLOC, HASH>::Iterator::get().template get<0>();
}
 
template<typename TYPE, typename HASH, typename ALLOC>
void original::hashSet<TYPE, HASH, ALLOC>::Iterator::set(const TYPE&) {
    throw unSupportedMethodError();
}
 
template<typename TYPE, typename HASH, typename ALLOC>
bool original::hashSet<TYPE, HASH, ALLOC>::Iterator::isValid() const {
    return hashTable<TYPE, const bool, ALLOC, HASH>::Iterator::isValid();
}
 
template<typename TYPE, typename HASH, typename ALLOC>
original::hashSet<TYPE, HASH, ALLOC>::hashSet(HASH hash, ALLOC alloc)
    : hashTable<TYPE, const bool, ALLOC, HASH>(std::move(hash)),
      set<TYPE, ALLOC>(std::move(alloc)) {}
 
template<typename TYPE, typename HASH, typename ALLOC>
original::hashSet<TYPE, HASH, ALLOC>::hashSet(const hashSet &other) : hashSet() {
    this->operator=(other);
}
 
template<typename TYPE, typename HASH, typename ALLOC>
original::hashSet<TYPE, HASH, ALLOC>&
original::hashSet<TYPE, HASH, ALLOC>::operator=(const hashSet &other) {
    if (this == &other) {
        return *this;
    }
 
    this->buckets = this->bucketsCopy(other.buckets);
    this->size_ = other.size_;
    if constexpr(ALLOC::propagate_on_container_copy_assignment::value) {
        this->allocator = other.allocator;
        this->rebind_alloc = other.rebind_alloc;
    }
    return *this;
}
 
template<typename TYPE, typename HASH, typename ALLOC>
original::hashSet<TYPE, HASH, ALLOC>::hashSet(hashSet &&other) noexcept : hashSet() {
    this->operator=(std::move(other));
}
 
template<typename TYPE, typename HASH, typename ALLOC>
original::hashSet<TYPE, HASH, ALLOC>&
original::hashSet<TYPE, HASH, ALLOC>::operator=(hashSet &&other) noexcept {
    if (this == &other) {
        return *this;
    }
 
    this->buckets = std::move(other.buckets);
    this->size_ = other.size_;
    other.size_ = 0;
    if constexpr(ALLOC::propagate_on_container_move_assignment::value) {
        this->allocator = std::move(other.allocator);
        this->rebind_alloc = std::move(other.rebind_alloc);
    }
    return *this;
}
 
template<typename TYPE, typename HASH, typename ALLOC>
original::u_integer original::hashSet<TYPE, HASH, ALLOC>::size() const {
    return this->size_;
}
 
template<typename TYPE, typename HASH, typename ALLOC>
bool original::hashSet<TYPE, HASH, ALLOC>::contains(const TYPE &e) const {
    return this->find(e);
}
 
template<typename TYPE, typename HASH, typename ALLOC>
bool original::hashSet<TYPE, HASH, ALLOC>::add(const TYPE &e) {
    return this->insert(e, true);
}
 
template<typename TYPE, typename HASH, typename ALLOC>
bool original::hashSet<TYPE, HASH, ALLOC>::remove(const TYPE &e) {
    return this->erase(e);
}
 
template<typename TYPE, typename HASH, typename ALLOC>
typename original::hashSet<TYPE, HASH, ALLOC>::Iterator*
original::hashSet<TYPE, HASH, ALLOC>::begins() const {
    auto p_buckets = const_cast<vector<hashNode*, rebind_alloc_pointer>*>(&this->buckets);
    if (this->buckets[0]) {
        return new Iterator(p_buckets, 0, this->buckets[0]);
    }
    auto bucket = Iterator::findNextValidBucket(p_buckets, 0);
    return new Iterator(p_buckets, bucket, p_buckets->get(bucket));
}
 
template<typename TYPE, typename HASH, typename ALLOC>
typename original::hashSet<TYPE, HASH, ALLOC>::Iterator*
original::hashSet<TYPE, HASH, ALLOC>::ends() const {
    auto p_buckets = const_cast<vector<hashNode*, rebind_alloc_pointer>*>(&this->buckets);
    auto bucket = Iterator::findPrevValidBucket(p_buckets, this->buckets.size());
    auto node = this->buckets[bucket];
    while (node && node->getPNext()) {
        node = node->getPNext();
    }
    return new Iterator(p_buckets, bucket, node);
}
 
template<typename TYPE, typename HASH, typename ALLOC>
std::string original::hashSet<TYPE, HASH, ALLOC>::className() const {
    return "hashSet";
}
 
template<typename TYPE, typename HASH, typename ALLOC>
std::string original::hashSet<TYPE, HASH, ALLOC>::toString(const bool enter) const {
    std::stringstream ss;
    ss << this->className();
    ss << "(";
    bool first = true;
    for (auto it = this->begin(); it != this->end(); it.next()){
        if (!first){
            ss << ", ";
        }
        ss << printable::formatString(it.get());
        first = false;
    }
    ss << ")";
    if (enter)
        ss << "\n";
    return ss.str();
}
 
template<typename TYPE, typename HASH, typename ALLOC>
original::hashSet<TYPE, HASH, ALLOC>::~hashSet() = default;
 
template <typename TYPE, typename Compare, typename ALLOC>
original::treeSet<TYPE, Compare, ALLOC>::Iterator::Iterator(RBTreeType* tree, RBNode* cur)
    : RBTreeType::Iterator(tree, cur)  {}
 
template <typename TYPE, typename Compare, typename ALLOC>
bool original::treeSet<TYPE, Compare, ALLOC>::Iterator::equalPtr(const iterator<const TYPE>* other) const
{
    auto other_it = dynamic_cast<const Iterator*>(other);
    return other_it &&
           this->tree_ == other_it->tree_ &&
           this->cur_ == other_it->cur_;
}
 
template <typename TYPE, typename Compare, typename ALLOC>
original::treeSet<TYPE, Compare, ALLOC>::Iterator::Iterator(const Iterator& other)
    : Iterator(nullptr, nullptr)
{
    this->operator=(other);
}
 
template <typename TYPE, typename Compare, typename ALLOC>
typename original::treeSet<TYPE, Compare, ALLOC>::Iterator&
original::treeSet<TYPE, Compare, ALLOC>::Iterator::operator=(const Iterator& other)
{
    if (this == &other) {
        return *this;
    }
 
    this->tree_ = other.tree_;
    this->cur_ = other.cur_;
    return *this;
}
 
template <typename TYPE, typename Compare, typename ALLOC>
typename original::treeSet<TYPE, Compare, ALLOC>::Iterator*
original::treeSet<TYPE, Compare, ALLOC>::Iterator::clone() const
{
    return new Iterator(*this);
}
 
template <typename TYPE, typename Compare, typename ALLOC>
std::string original::treeSet<TYPE, Compare, ALLOC>::Iterator::className() const
{
    return "treeSet::Iterator";
}
 
template <typename TYPE, typename Compare, typename ALLOC>
void original::treeSet<TYPE, Compare, ALLOC>::Iterator::operator+=(integer steps) const
{
    RBTreeType::Iterator::operator+=(steps);
}
 
template <typename TYPE, typename Compare, typename ALLOC>
void original::treeSet<TYPE, Compare, ALLOC>::Iterator::operator-=(integer steps) const
{
    RBTreeType::Iterator::operator-=(steps);
}
 
template <typename TYPE, typename Compare, typename ALLOC>
original::integer
original::treeSet<TYPE, Compare, ALLOC>::Iterator::operator-(const iterator<const TYPE>& other) const
{
    throw unSupportedMethodError();
}
 
template <typename TYPE, typename Compare, typename ALLOC>
bool original::treeSet<TYPE, Compare, ALLOC>::Iterator::hasNext() const
{
    return RBTreeType::Iterator::hasNext();
}
 
template <typename TYPE, typename Compare, typename ALLOC>
bool original::treeSet<TYPE, Compare, ALLOC>::Iterator::hasPrev() const
{
    return RBTreeType::Iterator::hasPrev();
}
 
template <typename TYPE, typename Compare, typename ALLOC>
bool original::treeSet<TYPE, Compare, ALLOC>::Iterator::atPrev(const iterator<const TYPE>* other) const
{
    auto other_it = dynamic_cast<const Iterator*>(other);
    if (!other_it) {
        return false;
    }
    auto next = ownerPtr(this->clone());
    if (!next->isValid()){
        return false;
    }
 
    next->next();
    return next->equalPtr(other_it);
}
 
template <typename TYPE, typename Compare, typename ALLOC>
bool original::treeSet<TYPE, Compare, ALLOC>::Iterator::atNext(const iterator<const TYPE>* other) const
{
    return other->atNext(*this);
}
 
template <typename TYPE, typename Compare, typename ALLOC>
void original::treeSet<TYPE, Compare, ALLOC>::Iterator::next() const
{
    RBTreeType::Iterator::next();
}
 
template <typename TYPE, typename Compare, typename ALLOC>
void original::treeSet<TYPE, Compare, ALLOC>::Iterator::prev() const
{
    RBTreeType::Iterator::prev();
}
 
template <typename TYPE, typename Compare, typename ALLOC>
typename original::treeSet<TYPE, Compare, ALLOC>::Iterator*
original::treeSet<TYPE, Compare, ALLOC>::Iterator::getPrev() const
{
    auto it = this->clone();
    it->prev();
    return it;
}
 
template <typename TYPE, typename Compare, typename ALLOC>
const TYPE& original::treeSet<TYPE, Compare, ALLOC>::Iterator::get()
{
    return RBTreeType::Iterator::get().template get<0>();
}
 
template <typename TYPE, typename Compare, typename ALLOC>
const TYPE original::treeSet<TYPE, Compare, ALLOC>::Iterator::get() const
{
    return RBTreeType::Iterator::get().template get<0>();
}
 
template <typename TYPE, typename Compare, typename ALLOC>
void original::treeSet<TYPE, Compare, ALLOC>::Iterator::set(const TYPE& data)
{
    throw unSupportedMethodError();
}
 
template <typename TYPE, typename Compare, typename ALLOC>
bool original::treeSet<TYPE, Compare, ALLOC>::Iterator::isValid() const
{
    return RBTreeType::Iterator::isValid();
}
 
template<typename TYPE, typename Compare, typename ALLOC>
original::treeSet<TYPE, Compare, ALLOC>::treeSet(Compare comp, ALLOC alloc)
    : RBTreeType(std::move(comp)),
      set<TYPE, ALLOC>(std::move(alloc)) {}
 
template<typename TYPE, typename Compare, typename ALLOC>
original::treeSet<TYPE, Compare, ALLOC>::treeSet(const treeSet& other) : treeSet() {
    this->operator=(other);
}
 
template<typename TYPE, typename Compare, typename ALLOC>
original::treeSet<TYPE, Compare, ALLOC>&
original::treeSet<TYPE, Compare, ALLOC>::operator=(const treeSet& other) {
    if (this == &other){
        return *this;
    }
 
    this->destroyTree();
    this->root_ = other.treeCopy();
    this->size_ = other.size_;
    if constexpr(ALLOC::propagate_on_container_copy_assignment::value) {
        this->allocator = other.allocator;
        this->rebind_alloc = other.rebind_alloc;
    }
    return *this;
}
 
template<typename TYPE, typename Compare, typename ALLOC>
original::treeSet<TYPE, Compare, ALLOC>::treeSet(treeSet&& other) noexcept : treeSet() {
    this->operator=(std::move(other));
}
 
template<typename TYPE, typename Compare, typename ALLOC>
original::treeSet<TYPE, Compare, ALLOC>&
original::treeSet<TYPE, Compare, ALLOC>::operator=(treeSet&& other) noexcept {
    if (this == &other){
        return *this;
    }
 
    this->root_ = other.root_;
    other.root_ = nullptr;
    this->size_ = other.size_;
    other.size_ = 0;
    if constexpr(ALLOC::propagate_on_container_move_assignment::value) {
        this->allocator = std::move(other.allocator);
        this->rebind_alloc = std::move(other.rebind_alloc);
    }
    return *this;
}
 
template<typename TYPE, typename Compare, typename ALLOC>
original::u_integer original::treeSet<TYPE, Compare, ALLOC>::size() const {
    return this->size_;
}
 
template<typename TYPE, typename Compare, typename ALLOC>
bool original::treeSet<TYPE, Compare, ALLOC>::contains(const TYPE &e) const {
    return this->find(e);
}
 
template<typename TYPE, typename Compare, typename ALLOC>
bool original::treeSet<TYPE, Compare, ALLOC>::add(const TYPE &e) {
    return this->insert(e, true);
}
 
template<typename TYPE, typename Compare, typename ALLOC>
bool original::treeSet<TYPE, Compare, ALLOC>::remove(const TYPE &e) {
    return this->erase(e);
}
 
template <typename TYPE, typename Compare, typename ALLOC>
typename original::treeSet<TYPE, Compare, ALLOC>::Iterator*
original::treeSet<TYPE, Compare, ALLOC>::begins() const
{
    return new Iterator(const_cast<treeSet*>(this), this->getMinNode());
}
 
template <typename TYPE, typename Compare, typename ALLOC>
typename original::treeSet<TYPE, Compare, ALLOC>::Iterator*
original::treeSet<TYPE, Compare, ALLOC>::ends() const
{
    return new Iterator(const_cast<treeSet*>(this), this->getMaxNode());
}
 
template<typename TYPE, typename Compare, typename ALLOC>
std::string original::treeSet<TYPE, Compare, ALLOC>::className() const {
    return "treeSet";
}
 
template<typename TYPE, typename Compare, typename ALLOC>
std::string original::treeSet<TYPE, Compare, ALLOC>::toString(const bool enter) const {
    std::stringstream ss;
    ss << this->className();
    ss << "(";
    bool first = true;
    for (auto it = this->begin(); it != this->end(); it.next()){
        if (!first){
            ss << ", ";
        }
        ss << printable::formatString(it.get());
        first = false;
    }
    ss << ")";
    if (enter)
        ss << "\n";
    return ss.str();
}
 
template<typename TYPE, typename Compare, typename ALLOC>
original::treeSet<TYPE, Compare, ALLOC>::~treeSet() = default;
 
#endif //SETS_H