maplist.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_maplist_h
#define INCL_evo_maplist_h

#include "map.h"
#include "list.h"
#include "strtok.h"

namespace evo {


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

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

    using MapBaseType::size_;

    MapList()
        { }

    MapList(const MapBaseType& src)
        { set(src); }

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

    ~MapList()
        { }

#if defined(EVO_CPP11)
    using typename MapBaseType::InitPair;   

    MapList(const std::initializer_list<InitPair>& init) : MapList() {
        assert( init.size() < IntegerT<Size>::MAX );
        capacitymin((Size)init.size());
        for (const auto& item : init)
            add(item.key, item.value);
    }

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

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

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

    // SET

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

    ThisType& operator=(const ThisType& src) {
        data_.items = src.data_.items;
        MapBaseType::size_ = src.size_;
        return *this;
    }

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

    ThisType& set(const MapBaseType& src) {
        clear();
        for (typename MapBaseType::Iter iter(src); iter; ++iter)
            this->get(iter->first) = iter->second;
        return *this;
    }

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

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

    ThisType& clear() {
        data_.items.clear();
        MapBaseType::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(); }

    // COMPARE

    using MapBaseType::operator==;
    using MapBaseType::operator!=;

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

    bool operator!=(const ThisType& map) const
        { return (this != &map && data_.items != map.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 Key& key) const {
        Size pos;
        return (search(pos, key) != NULL);
    }

    const Value* find(const Key& key) const {
        Size pos;
        const Item* item = search(pos, key);
        return (item != NULL ? &item->second : NULL);
    }

    Value* findM(const Key& key) {
        Size pos;
        const Item* item = search(pos, key);
        return (item != NULL ? (Value*)&item->second : NULL);
    }

    Size findindex(const Key& key) const
        { Size pos; return (search(pos, key) == NULL ? END : pos); }

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

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

    Item& getitem(const Key& key, bool* created=NULL) {
        Item* item;
        Size pos;
        if ( (item=(Item*)search(pos, key)) == NULL) {
            item = &data_.items.itemM(data_.items.insertnew(pos));
            item->first = key;
            if (created != NULL)
                *created = true;
            ++MapBaseType::size_;
        } else if (created != NULL)
            *created = false;
        return *item;
    }

    Value& get(const Key& key, bool* created=NULL)
        { return getitem(key, created).second; }

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

    Item& itemM(Size index)
        { return data_.items.itemM(index); }

    // INFO_SET

    Value& operator[](const Key& key)
        { return getitem(key, NULL).second; }

    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& compact()
        { data_.items.compact(); return *this; }

    ThisType& reserve(Size size)
        { capacitymin(this->size_ + size); return *this; }

    // ADD

    Item& add(const Key& key, const Value& value, bool update=true) {
        bool created_val;
        Item& upditem = getitem(key, &created_val);
        if (created_val || update)
            upditem.second = value;
        return upditem;
    }

    Item& add(const Item& item, bool update=true)
        { return add(item.first, item.second, update); }

    ThisType& add(const MapBaseType& map, bool update=true) {
        if (this != &map) {
            reserve(map.size());
            for (typename MapBaseType::Iter iter(map); iter; ++iter)
                add(iter->first, iter->second, update);
        }
        return *this;
    }

    // REMOVE

    bool remove(const Key& key) {
        bool result = false;
        Size index;
        if (search(index, key) != NULL) {
            data_.items.remove(index);
            --MapBaseType::size_;
            result = true;
        }
        return result;
    }

    bool remove(typename MapBaseType::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 (--MapBaseType::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;
    }

    void removeat(Size index) {
        assert( index < data_.items.size() );
        data_.items.remove(index);
        --MapBaseType::size_;
    }

    // ADVANCED

    const List<Item>& advList() const
        { return data_.items; }

    List<Item>& advList()
        { return data_.items; }

    // 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* 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 Item* getiter(IterKey& iterkey, const Key& key) const
        { return search(iterkey.a, key); }

private:
    typedef List<Item> Items;

    // Use inheritance to reduce size bloat with empty Compare
    struct Data : public Compare {
        Items items;

        Data() {
        }
        Data(const Data& data) : Compare(data), items(data.items) {
        }

    #if defined(EVO_CPP11)
        Data(Data&& data) : Compare(std::move((Compare&&)data)), items(std::move(data.items)) {
        }
        Data& operator=(Data&& data) {
            *((Compare*)this) = std::move((Compare&&)data);
            items = std::move(data.items);
            return *this;
        }
    #endif
    };

    Data data_;

    const Item* search(Size& index, const Key& key) const {
        int cmp;
        Size left = 0, right = data_.items.size(), mid = 0;
        while (left < right) {
            mid = left + ((right-left) / 2);
            const Item& item = data_.items.item(mid);
            cmp = data_.Compare::operator()(key, item.first);
            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 MapList<String,String> StrMapList;
#endif


}
#endif