UT_CollapseIDs.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * NAME:        UT_CollapseIDs.h ( UT Library, C++)
 *
 * COMMENTS:
 *      UT_CollapseIDs is a simple data structure that maps every (integral)
 *      input to a unique (also integral) output. These mapped outputs are
 *      guaranteed to be small, given the present mapping of values.
 */

#ifndef __UT_CollapseIDs_h__
#define __UT_CollapseIDs_h__

#include "UT_API.h"
#include "UT_Assert.h"
#include "UT_Map.h"
#include "UT_Set.h"

#include <SYS/SYS_Inline.h>

/// This class is designed to map integral values to integral values. For each
/// newly-added mapping, the mapped value will be a unique integer that's 
/// guaranteed to be small.
template <typename S, typename T>
class UT_CollapseIDs
{
public:
    UT_CollapseIDs() : myFreeStart(0) {}

    /// Returns true if the id maps to something already.
    bool contains(const S& id) const
    {
        return myMapping.contains(id);
    }

    /// Returns the value that id maps to. If the mapping doesn't yet exist, a
    /// non-clashing one is registered.
    T operator[](const S& id)
    {
        auto iter = myMapping.find(id);
        // If the mapping does not exist, find a free value and map it.
        if (iter == myMapping.end())
        {
            T free_val = getFreeValue();
            myMapping[id] = free_val;
            return free_val;
        }
        // The mapping does exist: return it.
        else
            return iter->second;
    }

    /// This call removes the mapping from id, marking whatever it was mapped to
    /// as an available value.
    void freeId(const S& id)
    {
        auto iter = myMapping.find(id);
        UT_ASSERT(iter != myMapping.end());
        returnValue(iter->second);
        myMapping.erase(iter);
    }

protected:
    /// The given value is returned as free, making it available for subsequent
    /// requests for a free value.
    SYS_FORCE_INLINE
    void returnValue(const T& value)
    {
        if (value == myFreeStart - 1)
            decrementFreeStart();
        else
            myFreeList.insert(value);
    }

    /// Returns a free value, with some effort put into ensuring that the
    /// smallest free value is returned.
    SYS_FORCE_INLINE
    T getFreeValue()
    {
        T free_val;
        // If the free list is empty, just use myFreeStart (making sure to
        // appropriately update it).
        if (myFreeList.empty())
        {
            free_val = myFreeStart;
            myFreeStart++;
            //if (myFreeStart < 0) UT_ASSERT(!"overflow");
        }
        // Otherwise, grab the first value in myFreeList (and remove it to mark
        // it not free).
        else
        {
            auto iter = myFreeList.begin();
            free_val = *iter;
            myFreeList.erase(iter);
        }

        return free_val;
    }

    /// Decreases myFreeStart by 1 and also sweeps the free list to remove any
    /// entries that can be merged with it.
    SYS_FORCE_INLINE
    void decrementFreeStart()
    {
        // Decrement the variable.
        myFreeStart--;

        // As long as myFreeStart-1 is in the free list, remove it and decrement
        // myFreeStart to ensure that myFreeStart-1 is not in the set.
        auto iter = myFreeList.find(myFreeStart - 1);
        while (iter != myFreeList.end())
        {
            myFreeStart--;
            myFreeList.erase(iter);
            iter = myFreeList.find(myFreeStart - 1);
        }
    }

protected:
    /// Set of free values; a value in this list is guaranteed to be free, and
    /// no value equal to or greater than myFreeStart-1 is in this set.
    UT_Set<T>           myFreeList;
    /// All values equal to or greater than this value are free.
    T                   myFreeStart;
    /// The actual mappings. This container ensures that no two myMapping[x]
    /// values will be the same.
    UT_Map<S, T>        myMapping;
};

#endif