Main   Class Hierarchy   Classes   Compound List   Files   Compound Members   File Members   Pages  

fringesearch.cpp

Go to the documentation of this file.
00001 //-----------------------------------------------------------------------------
00002 /** @file fringesearch.cpp
00003     @see fringesearch.h
00004 
00005     $Id: fringesearch_8cpp-source.html,v 1.1.1.1 2003/08/07 19:41:39 emarkus Exp $
00006     $Source: /usr/cvsroot/www_pathfind/libpathfind/0.1.0/doc/fringesearch_8cpp-source.html,v $
00007 */
00008 //-----------------------------------------------------------------------------
00009 
00010 #include "fringesearch.h"
00011 
00012 #include "util.h"
00013 
00014 using namespace std;
00015 using namespace PathFind;
00016 
00017 //-----------------------------------------------------------------------------
00018 
00019 Fringe::Fringe()
00020 {
00021     m_numberNodes = 0;
00022 }
00023 
00024 void Fringe::init(int numberNodes)
00025 {
00026     m_nodes.resize(numberNodes);
00027     m_isInList.clear();
00028     m_isInList.resize(numberNodes, false);
00029     m_numberNodes = numberNodes;
00030     m_currentNode = NO_NODE;
00031     m_headNode = NO_NODE;
00032 }
00033 
00034 void Fringe::insertNode(int nodeId)
00035 {
00036     if (m_isInList[nodeId])
00037         removeNode(nodeId);
00038     m_isInList[nodeId] = true;
00039     Node& newNode = getNode(nodeId);
00040     if (m_headNode != NO_NODE)
00041     {
00042         Node& current = getNode(m_currentNode);
00043         int next = current.m_next;
00044         newNode.m_previous = m_currentNode;
00045         newNode.m_next = next;
00046         if (next != NO_NODE)
00047             getNode(next).m_previous = nodeId;
00048         current.m_next = nodeId;
00049     }
00050     else
00051     {
00052         m_headNode = nodeId;
00053         newNode.m_previous = NO_NODE;
00054         newNode.m_next = NO_NODE;
00055     }
00056 }
00057 
00058 void Fringe::nextNode()
00059 {
00060     assert(m_currentNode != NO_NODE);
00061     m_currentNode = getNode(m_currentNode).m_next;
00062     assert(m_currentNode == NO_NODE || m_isInList[m_currentNode]);
00063 }
00064 
00065 void Fringe::print(ostream& o) const
00066 {
00067     o << "Fringe {\n";
00068     int nodeId = m_headNode;
00069     while (nodeId != NO_NODE)
00070     {
00071         o << nodeId << '\n';
00072         nodeId = getNode(nodeId).m_next;
00073     }
00074     o << "}\n";
00075 }
00076 
00077 void Fringe::removeNode(int nodeId)
00078 {
00079     assert(nodeId != NO_NODE);
00080     assert(m_isInList[nodeId]);
00081     Node& node = getNode(nodeId);
00082     int previous = node.m_previous;
00083     int next = node.m_next;
00084     if (previous != NO_NODE)
00085         getNode(previous).m_next = next;
00086     else
00087         m_headNode = next;    
00088     if (next != NO_NODE)
00089         getNode(next).m_previous = previous;
00090     m_isInList[nodeId] = false;
00091 }
00092 
00093 void Fringe::startIteration()
00094 {
00095     m_currentNode = m_headNode;
00096 }
00097 
00098 //-----------------------------------------------------------------------------


Generated on Thu Aug 7 13:04:49 2003 by Doxygen1.3.1