NodeSet.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_NODE_SET_H
#define OGDF_NODE_SET_H


#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/SList.h>



namespace ogdf {


//---------------------------------------------------------
// NodeSetSimple
// maintains a subset S of the nodes contained in an associated
// graph G (only insertion of elements and clear operation)
//---------------------------------------------------------
class OGDF_EXPORT NodeSetSimple {
public:
    // creates a new empty face set associated with combinatorial embedding E
    NodeSetSimple(const Graph &G) : m_isContained(G,false) { }

    // destructor
    ~NodeSetSimple() { }

    // inserts node v into set S
    // running time: O(1)
    // Precond.: v is a node in the associated graph
    void insert(node v) {
        OGDF_ASSERT(v->graphOf() == m_isContained.graphOf());
        bool &isContained = m_isContained[v];
        if (isContained == false) {
            isContained = true;
            m_nodes.pushFront(v);
        }
    }


    // removes all nodes from set S
    // running time: O(|S|)
    void clear() {
        SListIterator<node> it;
        for(it = m_nodes.begin(); it.valid(); ++it) {
            m_isContained[*it] = false;
        }
        m_nodes.clear();
    }


    // returns true iff node v is contained in S
    // running time: O(1)
    // Precond.: v is a node in the asociated graph
    bool isMember(node v) const {
        OGDF_ASSERT(v->graphOf() == m_isContained.graphOf());
        return m_isContained[v];
    }

    // returns the list of nodes contained in S
    const SListPure<node> &nodes() const {
        return m_nodes;
    }

private:
    // m_isContained[v] is true <=> v is contained in S
    NodeArray<bool> m_isContained;
    // list of nodes contained in S
    SListPure<node> m_nodes;
};



//---------------------------------------------------------
// NodeSetPure
// maintains a subset S of the nodes contained in an associated
// graph G (no efficient access to size of S)
//---------------------------------------------------------
class OGDF_EXPORT NodeSetPure {
public:
    // creates a new empty node set associated with graph G
    NodeSetPure(const Graph &G) : m_it(G,ListIterator<node>()) { }

    // destructor
    ~NodeSetPure() { }

    // inserts node v into set S
    // running time: O(1)
    // Precond.: v is a node in the associated graph
    void insert(node v) {
        OGDF_ASSERT(v->graphOf() == m_it.graphOf());
        ListIterator<node> &itV = m_it[v];
        if (!itV.valid())
            itV = m_nodes.pushBack(v);
    }

    // removes node v from set S
    // running time: O(1)
    // Precond.: v is a node in the asociated graph
    void remove(node v) {
        OGDF_ASSERT(v->graphOf() == m_it.graphOf());
        ListIterator<node> &itV = m_it[v];
        if (itV.valid()) {
            m_nodes.del(itV);
            itV = ListIterator<node>();
        }
    }


    // removes all nodes from set S
    // running time: O(|S|)
    void clear() {
        ListIterator<node> it;
        for(it = m_nodes.begin(); it.valid(); ++it) {
            m_it[*it] = ListIterator<node>();
        }
        m_nodes.clear();
    }


    // returns true iff node v is contained in S
    // running time: O(1)
    // Precond.: v is a node in the asociated graph
    bool isMember(node v) const {
        OGDF_ASSERT(v->graphOf() == m_it.graphOf());
        return m_it[v].valid();
    }

    // returns the list of nodes contained in S
    const ListPure<node> &nodes() const {
        return m_nodes;
    }

private:
    // m_it[v] contains list iterator pointing to v if v is contained in S,
    // an invalid list iterator otherwise
    NodeArray<ListIterator<node> > m_it;
    // list of nodes contained in S
    ListPure<node> m_nodes;
};



//---------------------------------------------------------
// NodeSet
// maintains a subset S of the nodes contained in an associated
// graph G
//---------------------------------------------------------
class OGDF_EXPORT NodeSet {
public:
    // creates a new empty node set associated with graph G
    NodeSet(const Graph &G) : m_it(G,ListIterator<node>()) { }

    // destructor
    ~NodeSet() { }

    // inserts node v into set S
    // running time: O(1)
    // Precond.: v is a node in the associated graph
    void insert(node v) {
        OGDF_ASSERT(v->graphOf() == m_it.graphOf());
        ListIterator<node> &itV = m_it[v];
        if (!itV.valid())
            itV = m_nodes.pushBack(v);
    }

    // removes node v from set S
    // running time: O(1)
    // Precond.: v is a node in the asociated graph
    void remove(node v) {
        OGDF_ASSERT(v->graphOf() == m_it.graphOf());
        ListIterator<node> &itV = m_it[v];
        if (itV.valid()) {
            m_nodes.del(itV);
            itV = ListIterator<node>();
        }
    }


    // removes all nodess from set S
    // running time: O(|S|)
    void clear() {
        ListIterator<node> it;
        for(it = m_nodes.begin(); it.valid(); ++it) {
            m_it[*it] = ListIterator<node>();
        }
        m_nodes.clear();
    }


    // returns true iff node v is contained in S
    // running time: O(1)
    // Precond.: v is a node in the asociated graph
    bool isMember(node v) const {
        OGDF_ASSERT(v->graphOf() == m_it.graphOf());
        return m_it[v].valid();
    }

    // returns the size of set S
    // running time: O(1)
    int size() const {
        return m_nodes.size();
    }

    // returns the list of nodes contained in S
    const List<node> &nodes() const {
        return m_nodes;
    }

private:
    // m_it[v] contains list iterator pointing to v if v is contained in S,
    // an invalid list iterator otherwise
    NodeArray<ListIterator<node> > m_it;
    // list of nodes contained in S
    List<node> m_nodes;
};


} // end namespace ogdf


#endif