Changelist.h

Go to the documentation of this file.

// $Id: Changelist.h 243 2006-07-06 07:57:25Z bingmann $

#ifndef VGS_ChangeList_H
#define VGS_ChangeList_H

#include "GraphTypes.h"
#include "GraphData.h"
#include "AttributeBlob.h"
#include "GraphPort.h"

#if defined(__GNUC__)
#include <ext/hash_map>
#include <ext/hash_set>
#else
#include <hash_map>
#include <hash_set>
#endif

namespace VGServer {

#if defined(__GNUC__)

using __gnu_cxx::hash_set;
using __gnu_cxx::hash_map;
using __gnu_cxx::hash_multimap;

#else

using stdext::hash_set;
using stdext::hash_map;
using stdext::hash_multimap;

#endif

class Changelist
{
private:
    friend class GraphData;

    friend class GraphContainer;

    const class GraphData &graph;

    /* The Changelist consists of two hash_maps holding AttributeBlobs which
     * contain the attribute values of the changed vertices and edges. If a
     * vertex or edge is deleted, then the AttributeBlob at that position is
     * empty. Thus addVertex and addEdge allocate the default bitfield and/or
     * the varying attributes. Furthermore the addV/E function add a new entry
     * to the hash_sets of newly create vertices or edges. These are checked
     * when providing frame 0 in getArea. */
    
    typedef hash_map<vertexid_t, AttributeVertexTinyBlob> vertexchglist_t;

    hash_map<vertexid_t, AttributeVertexTinyBlob> vertexchglist;

    typedef hash_set<vertexid_t> vertexaddlist_t;

    hash_set<vertexid_t>        vertexaddlist;

    typedef std::pair<vertexid_t, vertexid_t> vertexidpair_t;

#if defined(__GNUC__)

    struct vertexidpair_hashfunc {
        inline size_t operator()(const vertexidpair_t &p) const
        { return p.first; }
    };

    struct vertexidpair_equalfunc {
        inline bool operator()(const vertexidpair_t &a, const vertexidpair_t &b) const
        { return (a.first == b.first); }
    };

    struct vertexidpair_add_hashfunc { // another hash function for the add list
        inline size_t operator()(const vertexidpair_t &p) const
        { return (p.first ^ p.second); }
    };

    typedef hash_multimap<vertexidpair_t, AttributeEdgeTinyBlob,
                          vertexidpair_hashfunc, vertexidpair_equalfunc> edgechglist_t;

    typedef hash_set<vertexidpair_t, vertexidpair_add_hashfunc> edgeaddlist_t;

#else
    // visual c++

    struct vertexidpair_hash_compare {
        static const size_t bucket_size = 4;
        static const size_t min_buckets = 8;

        inline size_t operator()(const vertexidpair_t &p) const
        { return p.first; }

        inline bool operator()(const vertexidpair_t &a, const vertexidpair_t &b) const
        { return (a.first == b.first); }
    };

    typedef hash_multimap<vertexidpair_t, AttributeEdgeTinyBlob,
                          vertexidpair_hash_compare> edgechglist_t;

    // TODO: typedef edgeaddlist_t

#endif


    edgechglist_t edgechglist;

    edgeaddlist_t edgeaddlist;
    
    inline edgechglist_t::iterator find_edgechglist(vertexid_t src, vertexid_t tgt)
    {
        unsigned int ec = edgechglist.count(vertexidpair_t(src,tgt));
        if (ec == 0) return edgechglist.end();

        edgechglist_t::iterator e = edgechglist.find(vertexidpair_t(src,tgt));

        while( e != edgechglist.end() && !(e->first.first == src && e->first.second == tgt) )
        {
            if (e->first.first == src) {
                if (--ec == 0)
                    return edgechglist.end();
            }
            e++; // find right target change entry
        }

        return e;
    }

    inline edgechglist_t::const_iterator find_edgechglist(vertexid_t src, vertexid_t tgt) const
    {
        unsigned int ec = edgechglist.count(vertexidpair_t(src,tgt));
        if (ec == 0) return edgechglist.end();

        edgechglist_t::const_iterator e = edgechglist.find(vertexidpair_t(src,tgt));

        while( e != edgechglist.end() && !(e->first.first == src && e->first.second == tgt) )
        {
            if (e->first.first == src) {
                if (--ec == 0)
                    return edgechglist.end();
            }
            e++; // find right target change entry
        }

        return e;
    }

public:
    explicit Changelist(const class GraphData &graph);

    void        clear();

    bool        addVertex(vertexid_t id);

    bool        addVertex(vertexid_t id, const AttributeVertexTinyBlob &vb);

    bool        setVertexAttr(vertexid_t id, unsigned int attrid, const AnyType &value);

    bool        setVertexAttr(vertexid_t id, const AttributeVertexTinyBlob &vb);
    
    bool        delVertex(vertexid_t id);
    
    bool        addEdge(vertexid_t src, vertexid_t tgt);

    bool        addEdge(vertexid_t src, vertexid_t tgt, const AttributeEdgeTinyBlob &eb);
    
    bool        setEdgeAttr(vertexid_t src, vertexid_t tgt, unsigned int attrid, const AnyType &value);

    bool        setEdgeAttr(vertexid_t src, vertexid_t tgt, const AttributeEdgeTinyBlob &eb);
    
    bool        delEdge(vertexid_t src, vertexid_t tgt);

    inline bool isVertexChanged(vertexid_t id) const
    { return (vertexchglist.find(id) != vertexchglist.end()); }

    inline const AttributeVertexTinyBlob& getVertexChange(vertexid_t vid) const
    { return vertexchglist.find(vid)->second; }

    inline bool isEdgeChanged(vertexid_t src, vertexid_t tgt) const
    {
        edgechglist_t::const_iterator e = find_edgechglist(src,tgt);

        return (e != edgechglist.end());
    }

    inline const AttributeEdgeTinyBlob& getEdgeChange(vertexid_t src, vertexid_t tgt) const
    {
        edgechglist_t::const_iterator e = find_edgechglist(src,tgt);

        assert(e != edgechglist.end());
        return e->second;
    }

    typedef std::pair<vertexid_t, const AttributeEdgeTinyBlob*> edgeblobpair_t;
    typedef std::vector<edgeblobpair_t> edgelist_t;

    std::vector<edgeblobpair_t> getEdgeListChange(vertexid_t src) const;

};

} // namespace VGServer

#endif // VGS_Changelist_H

---