RedBlackTreeMap.hpp

Go to the documentation of this file.

// ======================================================================
// \file   RedBlackTreeMap.hpp
// \author bocchino
// \brief  An map based on a red-black tree with internal storage
// ======================================================================

#ifndef Fw_RedBlackTreeMap_HPP
#define Fw_RedBlackTreeMap_HPP

#include "Fw/DataStructures/ExternalRedBlackTreeMap.hpp"

namespace Fw {

template <typename K, typename V, FwSizeType C>
class RedBlackTreeMap final : public MapBase<K, V> {
    // ----------------------------------------------------------------------
    // Static assertions
    // ----------------------------------------------------------------------

    static_assert(C > 0, "capacity must be greater than zero");

    // ----------------------------------------------------------------------
    // Friend class for testing
    // ----------------------------------------------------------------------

    template <typename KK, typename VV, FwSizeType CC>
    friend class RedBlackTreeMapTester;

  public:
    // ----------------------------------------------------------------------
    // Public types
    // ----------------------------------------------------------------------

    using ConstIterator = MapConstIterator<K, V>;

    using Node = typename RedBlackTreeSetOrMapImpl<K, V>::Node;

    using Nodes = Node[C];

    using Index = typename RedBlackTreeSetOrMapImpl<K, V>::Index;

    using FreeNodes = Index[C];

  public:
    // ----------------------------------------------------------------------
    // Public constructors and destructors
    // ----------------------------------------------------------------------

    RedBlackTreeMap() : MapBase<K, V>(), m_extMap(m_nodes, m_freeNodes, C) {}

    RedBlackTreeMap(const RedBlackTreeMap<K, V, C>& map) : MapBase<K, V>(), m_extMap(m_nodes, m_freeNodes, C) {
        *this = map;
    }

    ~RedBlackTreeMap() override = default;

  public:
    // ----------------------------------------------------------------------
    // Public member functions
    // ----------------------------------------------------------------------

    RedBlackTreeMap<K, V, C>& operator=(const RedBlackTreeMap<K, V, C>& map) {
        this->m_extMap.copyDataFrom(map);
        return *this;
    }

    ConstIterator begin() const override { return this->m_extMap.begin(); }

    void clear() override { this->m_extMap.clear(); }

    ConstIterator end() const override { return this->m_extMap.end(); }

    Success find(const K& key,  
                 V& value       
    ) const override {
        return this->m_extMap.find(key, value);
    }

    FwSizeType getCapacity() const override { return this->m_extMap.getCapacity(); }

    FwSizeType getSize() const override { return this->m_extMap.getSize(); }

    Success insert(const K& key,   
                   const V& value  
                   ) override {
        return this->m_extMap.insert(key, value);
    }

    Success remove(const K& key,  
                   V& value       
                   ) override {
        return this->m_extMap.remove(key, value);
    }

  private:
    // ----------------------------------------------------------------------
    // Private member variables
    // ----------------------------------------------------------------------

    Nodes m_nodes = {};

    FreeNodes m_freeNodes = {};

    ExternalRedBlackTreeMap<K, V> m_extMap = {};
};

}  // namespace Fw

#endif