Set.h

Go to the documentation of this file.

/*
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Written (W) 2012 Evgeniy Andreev (gsomix)
 *
 * Copyright (C) 2012 Evgeniy Andreev (gsomix)
 */

#ifndef _SET_H_
#define _SET_H_

#include <shogun/base/SGObject.h>
#include <shogun/lib/common.h>
#include <shogun/lib/Hash.h>
#include <shogun/base/DynArray.h>

#include <cstdio>

namespace shogun
{

#ifndef DOXYGEN_SHOULD_SKIP_THIS

template<class T> struct CSetNode
{   
    int32_t index;

    bool free;

    T element;

    CSetNode<T> *left;

    CSetNode<T> *right;
};
#endif

template<class T> class CSet: public CSGObject
{
public:
    CSet(int32_t size=41, int32_t reserved=128, bool tracable=true)
    {   
        hash_size=size;
        free_index=0;
        num_elements=0;
        use_sg_mallocs=tracable;

        if (use_sg_mallocs)
            hash_array=SG_CALLOC(CSetNode<T>*, size);
        else
            hash_array=(CSetNode<T>**) calloc(size, sizeof(CSetNode<T>*));

        for (int32_t i=0; i<size; i++)
        {
            hash_array[i]=NULL;
        }

        array=new DynArray<CSetNode<T>* >(reserved, tracable);
    }

    virtual ~CSet()
    {
        if (array!=NULL)
        {
            for(int32_t i=0; i<array->get_num_elements(); i++)
            {
                if (array->get_element(i)!=NULL)
                {
                    if (use_sg_mallocs)
                        SG_FREE(array->get_element(i));
                    else
                        free(array->get_element(i));
                }
            }
            delete array;
        }

        if (hash_array!=NULL)
        {
            if (use_sg_mallocs)
                SG_FREE(hash_array);
            else
                free(hash_array);
        }
    }

    virtual const char* get_name() const { return "Set"; }

    void add(const T& element)
    {
        int32_t index=hash(element);
        if (chain_search(index, element)==NULL)
        {
            insert_key(index, element);
            num_elements++;
        }
    }

    bool contains(const T& element)
    {
        int32_t index=hash(element);
        if (chain_search(index, element)!=NULL)
            return true; 

        return false;
    }

    void remove(const T& element)
    {
        int32_t index=hash(element);
        CSetNode<T>* result=chain_search(index, element);

        if (result!=NULL)       
        {
            delete_key(index, result);
            num_elements--;
        }
    }

    int32_t index_of(const T& element)
    {
        int32_t index=hash(element);
        CSetNode<T>* result=chain_search(index, element);

        if (result!=NULL)
             return result->index;
        
        return -1;
    }

    int32_t get_num_elements() const
    {
        return num_elements;
    }

    int32_t get_array_size() const
    {
        return array->get_num_elements();
    }

    T* get_element_ptr(int32_t index)
    {
        if (array->get_element(index)!=NULL)
            return &(array->get_element(index)->element);
        return NULL;
    }

    CSetNode<T>* get_node_ptr(int32_t index)
    {
        return array->get_element(index);
    }
        
    CSetNode<T>** get_array()
    {
        return array->get_array();
    }

private:
    int32_t hash(const T& element)
    {
        return CHash::MurmurHash3((uint8_t*)(&element), sizeof(element), 0xDEADBEEF) % hash_size;
    }

    bool is_free(CSetNode<T>* node)
    {
        if (node->free==true)
            return true;

        return false;
    }

    CSetNode<T>* chain_search(int32_t index, const T& element)
    {
        if (hash_array[index]==NULL)
        {
            return NULL;
        }
        else
        {
            CSetNode<T>* current=hash_array[index];

            do // iterating all items in the list
            {
                if (current->element==element)
                    return current; // it's a search key

                current=current->right;

            } while (current!=NULL);

            return NULL;
        }
    }
    
    void insert_key(int32_t index, const T& element)
    {
        int32_t new_index;
        CSetNode<T>* new_node;

        if ((free_index>=array->get_num_elements()) || (array->get_element(free_index)==NULL))
        {
            // init new node
            if (use_sg_mallocs)
                new_node=SG_CALLOC(CSetNode<T>, 1);
            else
                new_node=(CSetNode<T>*) calloc(1, sizeof(CSetNode<T>));

            array->append_element(new_node);

            new_index=free_index;
            free_index++;
        }
        else
        {
            new_node=array->get_element(free_index);
            ASSERT(is_free(new_node));

            new_index=free_index;
            free_index=new_node->index;
        }

        new_node->index=new_index;
        new_node->free=false;
        new_node->element=element;
        new_node->left=NULL;
        new_node->right=NULL;

        // add new node in start of list
        if (hash_array[index]==NULL)
        {
            hash_array[index]=new_node;
        }
        else
        {
            hash_array[index]->left=new_node;
            new_node->right=hash_array[index];

            hash_array[index]=new_node;
        }
    }

    void delete_key(int32_t index, CSetNode<T>* node)
    {       
        int32_t temp=0;

        if (node==NULL)
            return;

        if (node->right!=NULL)
            node->right->left = node->left;

        if (node->left!=NULL)
            node->left->right = node->right;        
        else
            hash_array[index] = node->right;

        temp=node->index;

        node->index=free_index;
        node->free=true;
        node->left=NULL;
        node->right=NULL;

        free_index=temp;        
    }


protected:
    bool use_sg_mallocs;

    int32_t hash_size;

    int32_t free_index;

    int32_t num_elements;

    CSetNode<T>** hash_array;

    DynArray<CSetNode<T>*>* array;
};

}

#endif /* _MAP_H_ */