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 //-----------------------------------------------------------------------------