User Manual, Developers Guide and API Documentation

RangeMap.hpp

Go to the documentation of this file.

/*******************************************************************************
 * This file is part of openWNS (open Wireless Network Simulator)
 * _____________________________________________________________________________
 *
 * Copyright (C) 2004-2007
 * Chair of Communication Networks (ComNets)
 * Kopernikusstr. 16, D-52074 Aachen, Germany
 * phone: ++49-241-80-27910,
 * fax: ++49-241-80-22242
 * email: info@openwns.org
 * www: http://www.openwns.org
 * _____________________________________________________________________________
 *
 * openWNS is free software; you can redistribute it and/or modify it under the
 * terms of the GNU Lesser General Public License version 2 as published by the
 * Free Software Foundation;
 *
 * openWNS is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more
 * details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 ******************************************************************************/

#ifndef WNS_CONTAINER_RANGEMAP_HPP
#define WNS_CONTAINER_RANGEMAP_HPP

#include <WNS/Interval.hpp>
#include <WNS/Ttos.hpp>
#include <WNS/container/BinaryTree.hpp>

#include <utility>

namespace wns { namespace container {

    template<typename RangeType, typename ValueType, typename CleanupStrategy = tree::NoneOnErase>
    class RangeMap
    {
    public:

    class Exception : public wns::Exception
    {
    public:
        Exception(const std::string& s)
        : wns::Exception(s)
        {}
        ~Exception() throw() {}
    };


    typedef RangeType Index;

    typedef Interval<Index> IntervalType;

    typedef ValueType Value;

    RangeMap()
        : root(NULL)
    {}

    virtual ~RangeMap()
    {
        delete root;
    }

    RangeMap& insert(const IntervalType& interval, const ValueType& value)
    {
        IntervalValuePair intervalValue = IntervalValuePair(interval, value);
        assure(!interval.isEmpty(), "RangeMap: Can not insert empty intervals!");
        if (root == NULL) {
        root = new RangeTree(intervalValue);
        }
        else insert(intervalValue, root);
        return *this;
    }

    const Value& get(const Index& index) const
    {
        RangeTree* node = root;
        while (node != NULL) {
        if (node->getValue().first.contains(index)) return node->getValue().second;
        else {
            if (node->getValue().first.isAbove(index))
            node = node->getSubTree(0);
            else
            node = node->getSubTree(1);
        }
        }
        throw Exception("RangeMap: No value for index " + Ttos(index) + "!");
    }

    bool has(const Index& index) const
    {
        try {
        get(index);
        }
        catch (Exception) {
        return false;
        }
        return true;
    }

    private:

    typedef std::pair<IntervalType, Value> IntervalValuePair;
    typedef BinaryTree<IntervalValuePair, CleanupStrategy > RangeTree;

    void insert(const IntervalValuePair& intervalValue, RangeTree* node)
    {
        assure(node != NULL, "RangeMap: Attempt to insert into an empty tree");
        assure(!intervalValue.first.overlaps(node->getValue().first), "RangeMap: Can only insert disjoint intervals!");

        const int treeNo = (intervalValue.first.isBelow(node->getValue().first))?0:1;

        if (node->hasSubTree(treeNo)) insert(intervalValue, node->getSubTree(treeNo));
        else node->createSubTree(treeNo, intervalValue);
    }

    RangeTree* root;
    };

} // container
} // wns

#endif // NOT defined WNS_CONTAINER_RANGEMAP_HPP

---