UT/UT_NameManager.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.
*
* Produced by:
*       Oleg Samus
*       Side Effects Software Inc.
*       123 Front Street West, Suite 1401
*       Toronto, Ontario
*       Canada   M5J 2M2
*       416-366-4607
*
* NAME:        UT_NameManager.h
*
* COMMENTS:
*
*       This class implements a templated name manager, which aims to
*       provide fast unique name management functions. Note that it
*       is templated, and thus can be used with any data type.
*
*       The cost analysis below assumes names of the form "base123", consisting
*       of a base string and a numerical suffix which is optional. Let n denote
*       the number of unique base strings, and m denote the number of unique
*       suffixes within each base name class.
*
*       Note that the worst case assumes a really bad string hashing function which
*       causes all base strings to be put into a single bucket in a hash table, and is
*       therefore extremely unlikely.
*
*       Approximate time costs
*       ----------------------
*           Look up, add, or remove an element:
*              Best case:        O(1)
*              Average case:     O(log m)
*              Worst case:       O(n log m)
*
*           Generate a unique name:
*              Best case:        O(1)
*              Average case:     O(1)
*              Worst case:       O(n)
*
*/

#ifndef __UT_NameManager_h__
#define __UT_NameManager_h__

#include "UT_API.h"
#include "UT_SymbolTable.h"
#include "UT_String.h"

#include <map>
using namespace std;

/*****************************************************************************/
/// This is an internal class that generally doesn't need to be used.
template < class DATA_TYPE >
class UT_BaseNameCategory
{
public:
    UT_BaseNameCategory(const char* base_name, int start_suffix) : myBaseName(base_name, true)
    { 
        myStartSuffix = start_suffix;
    }
    ~UT_BaseNameCategory() { }

    bool add(const char *num_suffix, DATA_TYPE data, unsigned int &num_entries)
    {
        long index = myStartSuffix;
        if(num_suffix && strlen(num_suffix) > 0)
        {
            UT_String temp_str(num_suffix);
            index = temp_str.toInt();
        }

        pair<typename map<long, DATA_TYPE >::iterator, bool> result = myEntries.insert(typename map<long, DATA_TYPE >::value_type(index, data));
        if(result.second)
        {
            num_entries++;
            return true;
        }
        else
            return false;
    }

    DATA_TYPE find(const char* num_suffix) const
    {
        long index = myStartSuffix;
        if(num_suffix && strlen(num_suffix) > 0)
        {
            UT_String temp_str(num_suffix);
            index = temp_str.toInt();
        }
        typename map<long, DATA_TYPE >::const_iterator mi = myEntries.find(index);
        if(mi == myEntries.end())
            return NULL;
        else
            return mi->second;
    }

    bool deleteSymbol(const char* num_suffix, unsigned int &num_entries)
    {
        long index = myStartSuffix;
        if(num_suffix && strlen(num_suffix) > 0)
        {
            UT_String temp_str(num_suffix);
            index = temp_str.toInt();
        }
        typename map<long, DATA_TYPE >::iterator mi = myEntries.find(index);
        if(mi != myEntries.end())    
        {
            myEntries.erase(mi);
            if(num_entries > 0)
                num_entries--;
            return true;
        }
        else
            return false;
    }

    long getLastIndex(void) const
    {
        if(myEntries.size() > 0)
        {
            typename map<long, DATA_TYPE >::const_iterator mi = myEntries.end();
            mi--;
            return mi->first;
        }
        else
            return myStartSuffix;
    }

    unsigned entries(void) const { return myEntries.size(); }

private:
    int myStartSuffix;
    UT_String myBaseName;
    map<long, DATA_TYPE > myEntries;
};
/*****************************************************************************/
// A callback for deleting entries.
template < class DATA_TYPE > int
utNMTraverse(UT_Thing &p, const char *name, void *data)
{
    void        *entry;
    UT_Thing    *tablep;
    UT_BaseNameCategory<DATA_TYPE> *value;

    tablep = &p;
    entry = *tablep;
    value = (UT_BaseNameCategory<DATA_TYPE> *)entry;

    delete value;

    return 1;
}
/*****************************************************************************/
template < class DATA_TYPE >
class UT_NameManager
{
public:

    /// suffix_start_number determines the starting numerical suffix when unique names are generated.
    /// For example:
    /// If set to 0, generating unique names for "base" will result in  "base0", "base1", "base2", etc.
    /// If set to 1, generating unique names for "base" will result in  "base", "base1", "base2", etc.
    /// If set to 2, generating unique names for "base" will result in  "base", "base2", "base3", etc.
    /// And so on.
    UT_NameManager(int suffix_start_number = 2)  {   myNbrEntries = 0; mySuffixStartNumber = suffix_start_number - 1; }
    virtual ~UT_NameManager()    {    }

    /// Returns the total number of unique names in the manager.
    unsigned     entries() const { return myNbrEntries; }

    /// Returns true if empty, false otherwise.
    bool         empty() const { return !myNbrEntries; }

    /// Removes a name, such as "base123", from the manager. If the removed name 
    /// was the last one in a category and the category is now empty, deletes 
    /// the category as well.
    /// Returns true if removal was successfull, false otherwise.
    bool         deleteSymbol(const char *symbol)
    {
        if(!symbol)
            return false;

        UT_String temp_symbol(symbol);
        UT_String *base = temp_symbol.base();

        UT_Thing temp_thing;
        UT_BaseNameCategory<DATA_TYPE>* name_cat;
        bool did_find = myTable.findSymbol(*base, &temp_thing);
        if(!did_find)
        {
            delete base;
            return false;
        }

        name_cat = (UT_BaseNameCategory<DATA_TYPE>*)(void*)temp_thing;
        UT_ASSERT(name_cat);
        if(!name_cat)
        {
            delete base;
            return false;
        }

        bool res = name_cat->deleteSymbol(temp_symbol.suffix(), myNbrEntries);  
        if(res)
        {
            // See if this category is empty
            if(name_cat->entries() == 0)
            {
                // Remove it from our table
                myTable.deleteSymbol(*base);
                delete name_cat;
            }
        }

        delete base;
        return res;
    }

    /// Clears all the entries from this manager.
    void clear(void)
    {
        // Go through all symbol table entries, deallocate the memory
        myTable.traverse(utNMTraverse<DATA_TYPE>, NULL);

        // Clear the table
        myTable.clear();

        myNbrEntries = 0;
    }

    /// Generates a new name unique relative to the items alraedy in this collection, 
    /// optionally starting with a given name. Note that it always converts 
    /// unique_name_out string to be deep.
    void getUniqueName(const char* orig_name_in, UT_String& unique_name_out) const
    {
        unique_name_out.setAlwaysDeep(true);

        UT_String temp_name(orig_name_in && strlen(orig_name_in) > 0 ? orig_name_in : "name", false);
        UT_String *base = temp_name.base();

        UT_Thing temp_thing;
        UT_BaseNameCategory<DATA_TYPE>* name_cat;
        bool did_find = myTable.findSymbol(*base, &temp_thing);
        if(!did_find)
        {
            unique_name_out = temp_name;
            delete base;
            return;
        }

        name_cat = (UT_BaseNameCategory<DATA_TYPE>*)(void*)temp_thing;
        UT_ASSERT(name_cat);
        if(!name_cat)
        {
            unique_name_out = temp_name;
            delete base;
            return;
        }

        // Found the category
        if(name_cat->entries() == 0 && mySuffixStartNumber >= 0)
            unique_name_out = *base;
        else
        {
            long idx = name_cat->getLastIndex();
            idx++;
            unique_name_out.sprintf("%s%ld", (const char*)(*base), idx);
        }

        delete base;
    }

    /// Adds a new name to this collection. If the name already exists, 
    /// the addition will silently fail, so it is the caller's responsibility
    /// to assure that the name is unique by calling findSymbol() if
    /// needed. This is done to avoid extra uniqueness checks that may
    /// be unnecessary in certain situations.
    ///
    /// Returns true if symbol added successfully, false otherwise.
    bool         addSymbol(const char *symbol, DATA_TYPE data)
    {
        if(!symbol)
            return false;

        UT_String temp_symbol(symbol);
        UT_String *base = temp_symbol.base();

        // Get the category for the base of the name
        UT_Thing temp_thing;
        UT_BaseNameCategory<DATA_TYPE>* name_cat;
        bool did_find = myTable.findSymbol(*base, &temp_thing);
        if(!did_find)
        {
            // Create it and insert it
            name_cat = new UT_BaseNameCategory<DATA_TYPE>(*base, mySuffixStartNumber);
            myTable.addSymbol(*base, (void*)name_cat);
        }
        else
            name_cat = (UT_BaseNameCategory<DATA_TYPE>*)(void*)temp_thing;

        // Now add this entry to it
        delete base;
        return name_cat->add(temp_symbol.suffix(), data, myNbrEntries);
    }

    /// Similar to addSymbol(), but does a uniqueness check before adding
    /// the item, and if the name already exists, generates a new unique
    /// name with which the item is added.
    ///
    /// If make_name_copy is true, returns NULL if the original name was unique, 
    /// or a pointer to a new name if a different name was generated. Note that 
    /// deallocating the new name is the responsibility of the caller.
    /// If make_name_copy is false, always returns NULL.
    const char* addSymbolUnique(const char* symbol, DATA_TYPE data, bool make_name_copy = false)
    {
        bool generated_name = false;
        UT_String temp_name(UT_String::ALWAYS_DEEP);
        if(findSymbol(symbol) || !symbol)
        {
            // An item with this name already exists. Generate a new name.
            getUniqueName(symbol, temp_name);
            generated_name = true;
        }
        else
            temp_name = symbol;

        // Add the item
        addSymbol(temp_name, data);

        if(!make_name_copy)
            return NULL;

        // If we generated a new name and want a copy, make it and return
        if(generated_name)
            return strdup((const char*)temp_name);
        else
            return NULL;
    }

    /// Finds the data item associated with a given name. Returns a pointer
    /// to the item if found, NULL if the name is not in the collection.
    DATA_TYPE    findSymbol(const char *symbol) const
    {
        if(!symbol)
            return NULL;

        UT_String temp_symbol(symbol);
        UT_String *base = temp_symbol.base();

        UT_Thing temp_thing;
        UT_BaseNameCategory<DATA_TYPE>* name_cat;
        bool did_find = myTable.findSymbol(*base, &temp_thing);
        if(!did_find)
            return NULL;

        name_cat = (UT_BaseNameCategory<DATA_TYPE>*)(void*)temp_thing;
        UT_ASSERT(name_cat);
        if(!name_cat)
        {
            delete base;
            return NULL;
        }

        delete base;
        return name_cat->find(temp_symbol.suffix());
    }

private:

    UT_SymbolTable myTable;
    unsigned int myNbrEntries;
    int mySuffixStartNumber;
};
/*****************************************************************************/
#endif

---