UN_DataIndexMap.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:        UN_DataIndexMap.h ( UN Library, C++)
 *
 * COMMENTS:
 *      Core functionality for a utility-based node.
 */

#ifndef __UN_DataIndexMap_h__
#define __UN_DataIndexMap_h__

#include "UN_API.h"
#include "UN_Include.h"
#include <UT/UT_ArrayMap.h>


// ============================================================================
/// Maintains a mapping from data ID to data index in the data buffer.

class UN_API UN_DataIndexMap
{
public:
    /// Constructor.
                    UN_DataIndexMap();

    /// Adds a new data entry to the map. 
    /// Returns a pair, where the first component is the data ID that uniquely 
    /// identifies it in the graph, and the second component is the index
    /// to the data entry in the data buffer arrays.
    std::pair< UN_DataID, UN_DataIndex >    addEntry();

    /// Adds a new data entry to the map, forcing it to have the given ID.
    /// If a given ID is already in the map, returns the existing index.
    std::pair< UN_DataID, UN_DataIndex >    findOrAddEntry( UN_DataID data_id );

    /// Removes the data ID/Index lookup entry from the map.
    /// Returns true on successs; false if ID was not found in the map.
    bool            removeEntry( UN_DataID data_id );

    /// Removes all the data IDs entries from the map.
    /// @param 'reset_next_id' If true, the data ID generator is reset to zero.
    void            removeAllEntries( bool reset_next_id )
                        { clear( reset_next_id ); }

    /// Clears the map to an empty state, with no map entries.
    /// @param 'reset_next_id' If true, the data ID generator is reset to zero.
    ///         This may be useful if a graph loads and clears nodes repeatedly,
    ///         but has the danger of anyone holding the previous IDs thinking 
    ///         that this data is still valid. 
    ///         So use this option with great caution!!!
    // TODO: FIXME: consider removing the 'reset_next_id' parameter, since
    //              setting it to 'true' defeats the purpose of unique IDs.
    //              It's here because APEX resets IDs, but it does not need to.
    void            clear( bool reset_next_id = false );

    /// Returns true if the given ID refers to a valid entry in the map.
    bool            isValid( UN_DataID data_id ) const
                        { 
                            auto &map = myIndexFromID;
                            return data_id && map.find(data_id) != map.end(); 
                        }

    // TODO: FIXME: introduce the concept of identity map, which may be
    //      a very common use case when we don't delete any entries.
    //      Just load and traverse and edit parms, etc.
    //      Have 1:1 flag and just caset ID to Index. When removing entry
    //      mark map as dirty, and rebuild it on subsequent access.
    /// Returns an index into a data array buffer given the data ID.
    UN_DataIndex    indexFromID( UN_DataID data_id ) const
                        {
                            // There is no index for an invalid data ID!
                            if( !data_id )
                                return UN_DataIndex();

                            auto it = myIndexFromID.find( data_id );
                            if( it == myIndexFromID.end() )
                                return UN_DataIndex();
                            return it->second;
                        }

    /// Iterator for traversing valid data IDs in the map.
    class IDIterator
    {
    public:
        using iterator_category = std::input_iterator_tag;
        using value_type = UN_DataID;
        using difference_type = exint;
        using pointer = value_type*;
        using reference = value_type&;

        IDIterator( const UN_DataIndexMap &map, bool end = false )
            : myIter( end ? map.myIndexFromID.cend() 
                          : map.myIndexFromID.cbegin() )
            {}

        IDIterator&             operator++()    
                                    { 
                                        ++myIter; 
                                        return *this;
                                    }

        IDIterator              operator++(int)
                                    {
                                        auto bkup = *this;
                                        ++myIter;
                                        return bkup;
                                    }

        bool                    operator ==( const IDIterator &b ) const
                                    { return myIter == b.myIter; }

        bool                    operator !=( const IDIterator &b ) const
                                    { return myIter != b.myIter; }

        value_type              operator*() const
                                    { return myIter->first; }

        bool                    atEnd() const
                                    { return myIter.atEnd(); }

    private:
        /// Iterator into the map of valid IDs to their buffer indices.
        UT_ArrayMap< UN_DataID, UN_DataIndex >::const_iterator  myIter;
    };

    /// Iterator for traversing valid data IDs in the map in an ordered fashion.
    class OrderedIDIterator
    {
    public:
        using iterator_category = std::input_iterator_tag;
        using value_type = UN_DataID;
        using difference_type = exint;
        using pointer = value_type*;
        using reference = value_type&;

        OrderedIDIterator( const UN_DataIndexMap &map, bool end = false )
            :   myMap(map)
            ,   myCurrentID( end ? map.idSize().exintValue() : 0 )
            {
                goPastInvalid();
            }

        OrderedIDIterator&      operator++()    
                                    { 
                                        ++myCurrentID; 
                                        goPastInvalid();
                                        return *this;
                                    }

        OrderedIDIterator       operator++(int) 
                                    { 
                                        auto bkup = *this;
                                        ++myCurrentID; 
                                        goPastInvalid();
                                        return bkup;
                                    }

        bool                    operator ==( const OrderedIDIterator &b ) const
                                    { return myCurrentID == b.myCurrentID; }

        bool                    operator !=( const OrderedIDIterator &b ) const
                                    { return myCurrentID != b.myCurrentID; }

        value_type              operator*() const
                                    { return UN_DataID(myCurrentID); }

        bool                    atEnd() const
                                    { return myCurrentID >= myMap.idSize(); }
    private:
        void goPastInvalid()
        {
            // In graphs that don't have many deleted nodes, there won't be
            // many invalid IDs, so scanning past them should be fast.
            while( !atEnd() && !myMap.isValid(UN_DataID(myCurrentID)) )
                myCurrentID++;
        }

    private:
        const UN_DataIndexMap & myMap;
        exint                   myCurrentID;
    };


    /// Returns a range for iterating valid data IDs (order is not defined).
    /// Best for fast iteration without large memory footprint,
    /// but yields non-sorted IDs.
    using IDRange = UT_IteratorRange< IDIterator >;
    IDRange         idRange() const
                        { 
                            return IDRange( IDIterator(*this),
                                            IDIterator(*this, true)); 
                        }

    /// Returns a range for iterating valid data IDs in an ascending order.
    /// Best for iterating without large memory footprint, yields sorted IDs,
    /// but does not perform any explicit sorting (scans past invalid holes by 
    /// checking the validity of IDs) so is only slightly slower than idRange().
    using OrderedIDRange = UT_IteratorRange< OrderedIDIterator >;
    OrderedIDRange      orderedIDRange() const
                        { 
                            return OrderedIDRange( 
                                    OrderedIDIterator(*this),
                                    OrderedIDIterator(*this, true)); 
                        }

    /// Returns an array of valid (non-sorted) IDs.
    /// Builds an array, by quickly traversing the map keys, 
    /// but yields non-sorted IDs.
    UT_Array<UN_DataID> ids() const
                        {
                            UT_Array<UN_DataID> ids(myIndexFromID.size());
                            myIndexFromID.forEachKey([&](const UN_DataID &key) 
                                    {
                                        ids.append(key);
                                    });
                            return ids;
                        }

    /// Returns an array of valid IDs sorded in an ascending order.
    /// Builds an array, but incurs sorting cost, so it's slower than ids().
    UT_Array<UN_DataID> sortedIDs() const
                        {
                            auto node_ids( ids() );
                            node_ids.sort();
                            return node_ids;
                        }


    /// Returns the number of valid data itmes in the map.
    UN_DataSize     size() const
                        { return UN_DataSize( myIndexFromID.size() ); }

    /// Returns the upper limit on the valid indices issued by this container.
    /// Ie, maximum index value plus one.
    UN_DataSize     indexSize() const
                        { return dataBufferSize(); }

    /// Returns the upper limit on the numerical value of the valid data IDs 
    /// issued by this container. Ie, maximum ID plus one.
    UN_DataSize     idSize() const
                        { return UN_DataSize( myNextDataID.exintValue() ); }

    /// Returns the size of the data buffers that use indexing based
    /// on this map. The size is calculated as the largest known index 
    /// issued by this map plus one.
    UN_DataSize     dataBufferSize() const
                        { return UN_DataSize( myNextDataIndex.value() ); }

    /// Returns the number of free slots in the data buffer.
    /// Ie, the buffer consists of data entry slots that are either occupied 
    /// or free, and this menthod returns the free slots count.
    UN_DataSize     freeDataBufferSize() const
                        { return UN_DataSize( myFreeDataIndices.size() ); }

    /// Returns the number of valid data entries in the data buffer.
    /// Ie, the buffer consists of data entry slots that are either occupied 
    /// or free, and this menthod returns the occupied slots count.
    UN_DataSize     usedDataBufferSize() const
                        { 
                            return UN_DataSize( dataBufferSize().exintValue() 
                                    - freeDataBufferSize().exintValue() );
                        }

    /// Merges another index map into this one, creating mappings for
    /// the data entries to merged/copied from the given source.
    ///
    /// If @p combine_id_zero is true, the data for the ID zero is not mapped
    /// to a brand new data slot, but is combined with existing slot ID of zero.
    /// Some data containers use ID of zero for a special entry 
    /// that is treated differently than the other ones. 
    /// Notably, the node data container uses ID of zero for the root node,
    /// and the root node from the src should not become a regular node in dst.
    /// Instead, src root ID maps to dst root ID and their data is combined.
    UN_DataMergeInfo merge( const UN_DataIndexMap &src_map,
                           bool combine_id_zero = false );

private:
    /// Helper method to add entries for the merged data.
    UN_DataIDRemap  mergeEntries( const UN_DataIndexMap &src_map,
                            bool combine_id_zero );

    /// Helper to add an entry to the map.
    std::pair< UN_DataID, UN_DataIndex >    addNewEntry( UN_DataID data_id );

private:
    /// A map from data ID to data index.
    UT_ArrayMap< UN_DataID, UN_DataIndex >  myIndexFromID;

    /// A stack of indices to the free slots in the data buffer.
    UT_Array< UN_DataIndex >                myFreeDataIndices;

    /// The unique data ID that will be assigned to the next added entry.
    UN_DataID                               myNextDataID;

    /// The data buffer array index that will be used if the buffer needs
    /// to grow (ie, there is no more free slots in the buffer).
    UN_DataIndex                            myNextDataIndex;
};


#endif