setlist.h

Go to the documentation of this file.

// Evo C++ Library
/* Copyright 2019 Justin Crowell
Distributed under the BSD 2-Clause License -- see included file LICENSE.txt for details.
*/

#pragma once
#ifndef INCL_evo_setlist_h
#define INCL_evo_setlist_h

#include "set.h"
#include "list.h"

namespace evo {


template<class TKey, class TCompare=Compare<TKey>, class TSize=SizeT>
class SetList : public Set<TKey,TSize> {
public:
    EVO_CONTAINER_TYPE;
#if defined(_MSC_VER) || defined(EVO_OLDCC) // avoid errors with older compilers and MSVC
    typedef Set<TKey,TSize> SetBaseType;                
    typedef typename SetBaseType::Size Size;
    typedef typename SetBaseType::Key Key;
    typedef typename SetBaseType::Value Value;
    typedef typename SetBaseType::Item Item;
    typedef typename SetBaseType::IterKey IterKey;
    typedef typename SetBaseType::IterItem IterItem;
#else
    using typename Set<TKey,TSize>::SetBaseType;
    using typename Set<TKey,TSize>::Size;
    using typename Set<TKey,TSize>::Key;
    using typename Set<TKey,TSize>::Value;
    using typename Set<TKey,TSize>::Item;
    using typename Set<TKey,TSize>::IterKey;
    using typename Set<TKey,TSize>::IterItem;
#endif
    typedef SetList<TKey,TCompare,TSize> ThisType;      
    typedef TCompare Compare;                           

    typedef typename IteratorRa<ThisType>::Const Iter;  
    typedef IteratorRa<ThisType>                 IterM; 

    SetList()
        { }

    SetList(const SetBaseType& src)
        { set(src); }

    SetList(const ThisType& src) : data_(src.data_)
        { SetBaseType::size_ = src.size_; }

    ~SetList()
        { }

#if defined(EVO_CPP11)

    SetList(std::initializer_list<Value> init) : SetList() {
        assert( init.size() < IntegerT<Size>::MAX );
        capacitymin((Size)init.size());
        for (const auto& val : init)
            add(val);
    }

    SetList(ThisType&& src) : data_(std::move(src.data_)) {
        SetBaseType::size_ = src.SetBaseType::size_;
        src.SetBaseType::size_ = 0;
    }

    ThisType& operator=(ThisType&& src) {
        data_ = std::move(src.data_);
        SetBaseType::size_ = src.SetBaseType::size_;
        src.SetBaseType::size_ = 0;
        return *this;
    }
#endif

    const ThisType& asconst() const {
        return *this;
    }

    // SET

    ThisType& operator=(const SetBaseType& src)
        { set(src); return *this; }

    ThisType& operator=(const ThisType& src)
        { set(src); return *this; }

    ThisType& set() {
        data_.items.set();
        SetBaseType::size_ = 0;
        return *this;
    }

    ThisType& set(const SetBaseType& src) {
        clear();
        for (typename SetBaseType::Iter iter(src); iter; ++iter)
            add(*iter);
        return *this;
    }

    ThisType& set(const ThisType& src) {
        ((Compare&)data_) = (const Compare&)src.data_;
        data_.items.set(src.data_.items);
        SetBaseType::size_ = src.size_;
        return *this;
    }

    ThisType& setempty() {
        data_.items.setempty();
        SetBaseType::size_ = 0;
        return *this;
    }

    ThisType& clear() {
        data_.items.clear();
        SetBaseType::size_ = 0;
        return *this;
    }

    // INFO

    bool null() const
        { return data_.items.null(); }

    bool shared() const
        { return data_.items.shared(); }

    Size capacity() const
        { return data_.items.capacity(); }

    bool ordered() const
        { return true; }

    // COMPARE

    const Compare& get_compare() const
        { return data_; }

    Compare& get_compare()
        { return data_; }

    using SetBaseType::operator==;
    using SetBaseType::operator!=;

    bool operator==(const ThisType& set) const
        { return (this == &set || data_.items == set.data_.items); }

    bool operator!=(const ThisType& set) const
        { return (this != &set && data_.items != set.data_.items); }

    // FIND

    Iter cbegin() const
        { return Iter(*this); }

    Iter cend() const
        { return Iter(); }

    IterM begin()
        { return IterM(*this); }

    Iter begin() const
        { return Iter(*this); }

    IterM end()
        { return IterM(); }

    Iter end() const
        { return Iter(); }

    bool contains(const Value& value) const
        { Size i = 0; return (search(i, value) != NULL); }

    Iter iter(const Value& value) const {
        IterKey iterkey;
        const Item* item = search(iterkey.a, value);
        return (item != NULL ? Iter(*this, iterkey, (IterItem*)item) : Iter(*this, iterEND));
    }

    Iter iter_lower(const Value& value) const {
        IterKey iterkey;
        const Item* item = search(iterkey.a, value);
        if (item != NULL)
            return Iter(*this, iterkey, (IterItem*)item);
        if (iterkey.a < data_.items.size())
            return Iter(*this, iterkey, (IterItem*)&data_.items.item(iterkey.a));
        return Iter(*this, iterEND);
    }

    IterM iter_lowerM(const Value& value) {
        IterKey iterkey;
        const Item* item = search(iterkey.a, value);
        if (item != NULL)
            return IterM(*this, iterkey, (IterItem*)item);
        if (iterkey.a < data_.items.size())
            return IterM(*this, iterkey, (IterItem*)&data_.items.item(iterkey.a));
        return IterM(*this, iterEND);
    }

    Iter iter_upper(const Value& value) const {
        IterKey iterkey;
        if (search(iterkey.a, value) != NULL)
            ++iterkey.a;
        if (iterkey.a < data_.items.size())
            return Iter(*this, iterkey, (IterItem*)&data_.items.item(iterkey.a));
        return Iter(*this, iterEND);
    }

    IterM iter_upperM(const Value& value) {
        IterKey iterkey;
        if (search(iterkey.a, value) != NULL)
            ++iterkey.a;
        if (iterkey.a < data_.items.size())
            return IterM(*this, iterkey, (IterItem*)&data_.items.item(iterkey.a));
        return IterM(*this, iterEND);
    }

    IterM iterM(const Value& value) {
        IterKey iterkey;
        const Item* item = search(iterkey.a, value);
        return (item != NULL ? IterM(*this, iterkey, (IterItem*)item) : IterM(*this, iterEND));
    }

    Value& get(const Value& value, bool* created=NULL) {
        Item* item;
        Size pos;
        if ( (item=(Item*)search(pos, value)) == NULL) {
            item = &(data_.items.itemM(data_.items.insert(pos, &value, 1)));
            if (created != NULL)
                *created = true;
            ++SetBaseType::size_;
        } else if (created != NULL)
            *created = false;
        return *item;
    }

    const Value& item(Size index) const
        { return data_.items.item(index); }

    // INFO_SET

    ThisType& unshare()
        { data_.items.unshare(); return *this; }

    ThisType& capacity(Size size)
        { data_.items.capacity(size); return *this; }

    ThisType& capacitymin(Size min)
        { data_.items.capacitymin(min); return *this; }

    ThisType& reserve(Size size)
        { data_.items.reserve(size); return *this; }

    ThisType& compact()
        { data_.items.compact(); return *this; }

    // ADD

    Value& add(const Value& item, bool update=false) {
        bool created_val;
        Value& upditem = get(item, &created_val);
        if (!created_val && update)
            upditem = item;
        return upditem;
    }

    // REMOVE

    bool remove(const Value& value) {
        Size index;
        if (search(index, value) != NULL) {
            data_.items.remove(index);
            --SetBaseType::size_;
            return true;
        }
        return false;
    }

    Size remove(const Value& value, Size count) {
        Size index;
        if (count > 0 && search(index, value) != NULL) {
            count = data_.items.remove(index, count);
            SetBaseType::size_ -= count;
            return count;
        }
        return 0;
    }

    bool remove(typename SetBaseType::IterM& iter, IteratorDir dir=iterNONE)
        { return remove((IterM&)iter, dir); }

    bool remove(IterM& iter, IteratorDir dir=iterNONE) {
        if (iter && this == &iter.getParent()) {
            IterKey& iterkey = iter.getKey();
            data_.items.remove(iterkey.a);
            bool nextitem = false;
            if (--SetBaseType::size_ > 0 && dir != iterNONE) {
                if (dir == iterRV) {
                    if (iterkey.a > 0)
                        { --iterkey.a; nextitem = true; }
                } else if (iterkey.a < data_.items.size())
                    nextitem = true;
            }
            if (nextitem)
                iter.setData( (IterItem*)&data_.items.item(iterkey.a) );
            else 
                iter = iterEND;
            return true;
        }
        return false;
    }

    Size removeat(Size index, Size count=1) {
        assert( index < data_.items.size() );
        count = data_.items.remove(index, count);
        SetBaseType::size_ -= count;
        return count;
    }

    Size remove_range(IterM& start, Size count) {
        if (count > 0 && start && this == &start.getParent()) {
            count = data_.items.remove(start.index().a, count);
            SetBaseType::size_ -= count;
            if (start.index().a >= SetBaseType::size_)
                start = iterEND;
            return count;
        }
        return 0;
    }

    Size remove_range(IterM& start, IterM& end) {
        if (start && this == &start.getParent()) {
            const Size index = start.index().a;
            if (end) {
                if (this == &end.getParent()) {
                    const Size end_index = end.index().a;
                    if (end_index > index) {
                        const Size count = data_.items.remove(index, end_index - index);
                        SetBaseType::size_ -= count;
                        end = iterEND;
                        return count;
                    }
                }
            } else {
                const Size count = data_.items.remove(index, ALL);
                SetBaseType::size_ -= count;
                start = iterEND;
                return count;
            }
        }
        return 0;
    }

    // INTERNAL

    // Iterator support methods
    void iterInitMutable()
        { data_.items.iterInitMutable(); }
    const IterItem* iterFirst(IterKey& key) const
        { return (IterItem*)data_.items.iterFirst(key.a); }
    const IterItem* iterNext(IterKey& key) const
        { return (IterItem*)data_.items.iterNext(key.a); }
    const IterItem* iterNext(Size count, IterKey& key) const
        { return (IterItem*)data_.items.iterNext(count, key.a); }
    const IterItem* iterLast(IterKey& key) const
        { return (IterItem*)data_.items.iterLast(key.a); }
    const IterItem* iterPrev(IterKey& key) const
        { return (IterItem*)data_.items.iterPrev(key.a); }
protected:
    const Value* getiter(IterKey& iterkey, const Value& value) const
        { return search(iterkey.a, value); }

private:
    // Use inheritance to reduce size bloat with empty Compare
    struct Data : public TCompare {
        using TCompare::operator();

        List<Item> items;

        Data()
            { }
        Data(const Data& data) : TCompare(data), items(data.items)
            { }
    #if defined(EVO_CPP11)
        Data(Data&& data) : TCompare(std::move(data)), items(std::move(data.items))
            { }

        Data& operator=(Data&& data) {
            ((TCompare&)*this) = std::move((TCompare&)data);
            items = std::move(data.items);
            return *this;
        }
    #endif
    };

    Data data_;

    const Value* search(Size& index, const Value& value) const {
        int cmp;
        Size left = 0, right = data_.items.size(), mid = 0;
        while (left < right) {
            mid = left + ((right - left) / 2);
            const Value& item = data_.items.item(mid);
            cmp = data_(value, item);
            if (cmp < 0) {
                right = mid;
            } else if (cmp == 0) {
                index = mid;
                return &item;
            } else
                left = mid + 1;
        }
        index = left;
        return NULL;
    }
};


#if defined(INCL_evo_string_h) || defined(DOXYGEN)

typedef SetList<String> StrSetList;
#endif


}
#endif