1 /// \file DS_WeightedGraph.h 2 /// \internal 3 /// \brief Weighted graph. 4 /// \details I'm assuming the indices are complex map types, rather than sequential numbers (which could be implemented much more efficiently). 5 /// 6 /// This file is part of RakNet Copyright 2003 Jenkins Software LLC 7 /// 8 /// Raknet is available under the terms of the GPLv3 license, see /usr/local/share/licenses/raknet-3.9.2_10,1/GPLv3. 9 10 11 #ifndef __WEIGHTED_GRAPH_H 12 #define __WEIGHTED_GRAPH_H 13 14 #include "DS_OrderedList.h" 15 #include "DS_Map.h" 16 #include "DS_Heap.h" 17 #include "DS_Queue.h" 18 #include "DS_Tree.h" 19 #include "RakAssert.h" 20 #include "RakMemoryOverride.h" 21 #ifdef _DEBUG 22 #include <stdio.h> 23 #endif 24 25 #ifdef _MSC_VER 26 #pragma warning( push ) 27 #endif 28 29 /// The namespace DataStructures was only added to avoid compiler errors for commonly named data structures 30 /// As these data structures are stand-alone, you can use them outside of RakNet for your own projects if you wish. 31 namespace DataStructures 32 { 33 template <class node_type, class weight_type, bool allow_unlinkedNodes> 34 class RAK_DLL_EXPORT WeightedGraph 35 { 36 public: IMPLEMENT_DEFAULT_COMPARISON(void)37 static void IMPLEMENT_DEFAULT_COMPARISON(void) {DataStructures::defaultMapKeyComparison<node_type>(node_type(),node_type());} 38 39 WeightedGraph(); 40 ~WeightedGraph(); 41 WeightedGraph( const WeightedGraph& original_copy ); 42 WeightedGraph& operator= ( const WeightedGraph& original_copy ); 43 void AddNode(const node_type &node); 44 void RemoveNode(const node_type &node); 45 void AddConnection(const node_type &node1, const node_type &node2, weight_type weight); 46 void RemoveConnection(const node_type &node1, const node_type &node2); 47 bool HasConnection(const node_type &node1, const node_type &node2); 48 void Print(void); 49 void Clear(void); 50 bool GetShortestPath(DataStructures::List<node_type> &path, node_type startNode, node_type endNode, weight_type INFINITE_WEIGHT); 51 bool GetSpanningTree(DataStructures::Tree<node_type> &outTree, DataStructures::List<node_type> *inputNodes, node_type startNode, weight_type INFINITE_WEIGHT ); 52 unsigned GetNodeCount(void) const; 53 unsigned GetConnectionCount(unsigned nodeIndex) const; 54 void GetConnectionAtIndex(unsigned nodeIndex, unsigned connectionIndex, node_type &outNode, weight_type &outWeight) const; 55 node_type GetNodeAtIndex(unsigned nodeIndex) const; 56 57 protected: 58 void ClearDijkstra(void); 59 void GenerateDisjktraMatrix(node_type startNode, weight_type INFINITE_WEIGHT); 60 61 DataStructures::Map<node_type, DataStructures::Map<node_type, weight_type> *> adjacencyLists; 62 63 // All these variables are for path finding with Dijkstra 64 // 08/23/06 Won't compile as a DLL inside this struct 65 // struct 66 // { 67 bool isValidPath; 68 node_type rootNode; 69 DataStructures::OrderedList<node_type, node_type> costMatrixIndices; 70 weight_type *costMatrix; 71 node_type *leastNodeArray; 72 // } dijkstra; 73 74 struct NodeAndParent 75 { 76 DataStructures::Tree<node_type>*node; 77 DataStructures::Tree<node_type>*parent; 78 }; 79 }; 80 81 template <class node_type, class weight_type, bool allow_unlinkedNodes> WeightedGraph()82 WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::WeightedGraph() 83 { 84 isValidPath=false; 85 costMatrix=0; 86 } 87 88 template <class node_type, class weight_type, bool allow_unlinkedNodes> ~WeightedGraph()89 WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::~WeightedGraph() 90 { 91 Clear(); 92 } 93 94 template <class node_type, class weight_type, bool allow_unlinkedNodes> WeightedGraph(const WeightedGraph & original_copy)95 WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::WeightedGraph( const WeightedGraph& original_copy ) 96 { 97 adjacencyLists=original_copy.adjacencyLists; 98 99 isValidPath=original_copy.isValidPath; 100 if (isValidPath) 101 { 102 rootNode=original_copy.rootNode; 103 costMatrixIndices=original_copy.costMatrixIndices; 104 costMatrix = RakNet::OP_NEW_ARRAY<weight_type>(costMatrixIndices.Size() * costMatrixIndices.Size(), __FILE__, __LINE__ ); 105 leastNodeArray = RakNet::OP_NEW_ARRAY<node_type>(costMatrixIndices.Size(), __FILE__, __LINE__ ); 106 memcpy(costMatrix, original_copy.costMatrix, costMatrixIndices.Size() * costMatrixIndices.Size() * sizeof(weight_type)); 107 memcpy(leastNodeArray, original_copy.leastNodeArray, costMatrixIndices.Size() * sizeof(weight_type)); 108 } 109 } 110 111 template <class node_type, class weight_type, bool allow_unlinkedNodes> 112 WeightedGraph<node_type, weight_type, allow_unlinkedNodes>& WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::operator=( const WeightedGraph& original_copy ) 113 { 114 adjacencyLists=original_copy.adjacencyLists; 115 116 isValidPath=original_copy.isValidPath; 117 if (isValidPath) 118 { 119 rootNode=original_copy.rootNode; 120 costMatrixIndices=original_copy.costMatrixIndices; 121 costMatrix = RakNet::OP_NEW_ARRAY<weight_type>(costMatrixIndices.Size() * costMatrixIndices.Size(), __FILE__, __LINE__ ); 122 leastNodeArray = RakNet::OP_NEW_ARRAY<node_type>(costMatrixIndices.Size(), __FILE__, __LINE__ ); 123 memcpy(costMatrix, original_copy.costMatrix, costMatrixIndices.Size() * costMatrixIndices.Size() * sizeof(weight_type)); 124 memcpy(leastNodeArray, original_copy.leastNodeArray, costMatrixIndices.Size() * sizeof(weight_type)); 125 } 126 127 return *this; 128 } 129 130 template <class node_type, class weight_type, bool allow_unlinkedNodes> AddNode(const node_type & node)131 void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::AddNode(const node_type &node) 132 { 133 adjacencyLists.SetNew(node, RakNet::OP_NEW<DataStructures::Map<node_type, weight_type> >( __FILE__, __LINE__) ); 134 } 135 136 template <class node_type, class weight_type, bool allow_unlinkedNodes> RemoveNode(const node_type & node)137 void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::RemoveNode(const node_type &node) 138 { 139 unsigned i; 140 DataStructures::Queue<node_type> removeNodeQueue; 141 142 removeNodeQueue.Push(node, __FILE__, __LINE__ ); 143 while (removeNodeQueue.Size()) 144 { 145 RakNet::OP_DELETE(adjacencyLists.Pop(removeNodeQueue.Pop()), __FILE__, __LINE__); 146 147 // Remove this node from all of the other lists as well 148 for (i=0; i < adjacencyLists.Size(); i++) 149 { 150 adjacencyLists[i]->Delete(node); 151 152 #ifdef _MSC_VER 153 #pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant 154 #endif 155 if (allow_unlinkedNodes==false && adjacencyLists[i]->Size()==0) 156 removeNodeQueue.Push(adjacencyLists.GetKeyAtIndex(i), __FILE__, __LINE__ ); 157 } 158 } 159 160 ClearDijkstra(); 161 } 162 163 template <class node_type, class weight_type, bool allow_unlinkedNodes> HasConnection(const node_type & node1,const node_type & node2)164 bool WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::HasConnection(const node_type &node1, const node_type &node2) 165 { 166 if (node1==node2) 167 return false; 168 if (adjacencyLists.Has(node1)==false) 169 return false; 170 return adjacencyLists.Get(node1)->Has(node2); 171 } 172 173 template <class node_type, class weight_type, bool allow_unlinkedNodes> AddConnection(const node_type & node1,const node_type & node2,weight_type weight)174 void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::AddConnection(const node_type &node1, const node_type &node2, weight_type weight) 175 { 176 if (node1==node2) 177 return; 178 179 if (adjacencyLists.Has(node1)==false) 180 AddNode(node1); 181 adjacencyLists.Get(node1)->Set(node2, weight); 182 if (adjacencyLists.Has(node2)==false) 183 AddNode(node2); 184 adjacencyLists.Get(node2)->Set(node1, weight); 185 } 186 187 template <class node_type, class weight_type, bool allow_unlinkedNodes> RemoveConnection(const node_type & node1,const node_type & node2)188 void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::RemoveConnection(const node_type &node1, const node_type &node2) 189 { 190 adjacencyLists.Get(node2)->Delete(node1); 191 adjacencyLists.Get(node1)->Delete(node2); 192 193 #ifdef _MSC_VER 194 #pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant 195 #endif 196 if (allow_unlinkedNodes==false) // If we do not allow _unlinked nodes, then if there are no connections, remove the node 197 { 198 if (adjacencyLists.Get(node1)->Size()==0) 199 RemoveNode(node1); // Will also remove node1 from the adjacency list of node2 200 if (adjacencyLists.Has(node2) && adjacencyLists.Get(node2)->Size()==0) 201 RemoveNode(node2); 202 } 203 204 ClearDijkstra(); 205 } 206 207 template <class node_type, class weight_type, bool allow_unlinkedNodes> Clear(void)208 void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::Clear(void) 209 { 210 unsigned i; 211 for (i=0; i < adjacencyLists.Size(); i++) 212 RakNet::OP_DELETE(adjacencyLists[i], __FILE__, __LINE__); 213 adjacencyLists.Clear(); 214 215 ClearDijkstra(); 216 } 217 218 template <class node_type, class weight_type, bool allow_unlinkedNodes> GetShortestPath(DataStructures::List<node_type> & path,node_type startNode,node_type endNode,weight_type INFINITE_WEIGHT)219 bool WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::GetShortestPath(DataStructures::List<node_type> &path, node_type startNode, node_type endNode, weight_type INFINITE_WEIGHT) 220 { 221 path.Clear(false, __FILE__, __LINE__); 222 if (startNode==endNode) 223 { 224 path.Insert(startNode, __FILE__, __LINE__); 225 path.Insert(endNode, __FILE__, __LINE__); 226 return true; 227 } 228 229 if (isValidPath==false || rootNode!=startNode) 230 { 231 ClearDijkstra(); 232 GenerateDisjktraMatrix(startNode, INFINITE_WEIGHT); 233 } 234 235 // return the results 236 bool objectExists; 237 unsigned col,row; 238 weight_type currentWeight; 239 DataStructures::Queue<node_type> outputQueue; 240 col=costMatrixIndices.GetIndexFromKey(endNode, &objectExists); 241 if (costMatrixIndices.Size()<2) 242 { 243 return false; 244 } 245 if (objectExists==false) 246 { 247 return false; 248 } 249 node_type vertex; 250 row=costMatrixIndices.Size()-2; 251 if (row==0) 252 { 253 path.Insert(startNode, __FILE__, __LINE__); 254 path.Insert(endNode, __FILE__, __LINE__); 255 return true; 256 } 257 currentWeight=costMatrix[row*adjacencyLists.Size() + col]; 258 if (currentWeight==INFINITE_WEIGHT) 259 { 260 // No path 261 return true; 262 } 263 vertex=endNode; 264 outputQueue.PushAtHead(vertex, 0, __FILE__,__LINE__); 265 row--; 266 #ifdef _MSC_VER 267 #pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant 268 #endif 269 while (1) 270 { 271 while (costMatrix[row*adjacencyLists.Size() + col] == currentWeight) 272 { 273 if (row==0) 274 { 275 path.Insert(startNode, __FILE__, __LINE__); 276 for (col=0; outputQueue.Size(); col++) 277 path.Insert(outputQueue.Pop(), __FILE__, __LINE__); 278 return true; 279 } 280 --row; 281 } 282 283 vertex=leastNodeArray[row]; 284 outputQueue.PushAtHead(vertex, 0, __FILE__,__LINE__); 285 if (row==0) 286 break; 287 col=costMatrixIndices.GetIndexFromKey(vertex, &objectExists); 288 currentWeight=costMatrix[row*adjacencyLists.Size() + col]; 289 } 290 291 path.Insert(startNode, __FILE__, __LINE__); 292 for (col=0; outputQueue.Size(); col++) 293 path.Insert(outputQueue.Pop(), __FILE__, __LINE__); 294 return true; 295 } 296 297 template <class node_type, class weight_type, bool allow_unlinkedNodes> GetNodeAtIndex(unsigned nodeIndex)298 node_type WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::GetNodeAtIndex(unsigned nodeIndex) const 299 { 300 return adjacencyLists.GetKeyAtIndex(nodeIndex); 301 } 302 303 template <class node_type, class weight_type, bool allow_unlinkedNodes> GetNodeCount(void)304 unsigned WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::GetNodeCount(void) const 305 { 306 return adjacencyLists.Size(); 307 } 308 309 template <class node_type, class weight_type, bool allow_unlinkedNodes> GetConnectionCount(unsigned nodeIndex)310 unsigned WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::GetConnectionCount(unsigned nodeIndex) const 311 { 312 return adjacencyLists[nodeIndex]->Size(); 313 } 314 315 template <class node_type, class weight_type, bool allow_unlinkedNodes> GetConnectionAtIndex(unsigned nodeIndex,unsigned connectionIndex,node_type & outNode,weight_type & outWeight)316 void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::GetConnectionAtIndex(unsigned nodeIndex, unsigned connectionIndex, node_type &outNode, weight_type &outWeight) const 317 { 318 outWeight=adjacencyLists[nodeIndex]->operator[](connectionIndex); 319 outNode=adjacencyLists[nodeIndex]->GetKeyAtIndex(connectionIndex); 320 } 321 322 template <class node_type, class weight_type, bool allow_unlinkedNodes> GetSpanningTree(DataStructures::Tree<node_type> & outTree,DataStructures::List<node_type> * inputNodes,node_type startNode,weight_type INFINITE_WEIGHT)323 bool WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::GetSpanningTree(DataStructures::Tree<node_type> &outTree, DataStructures::List<node_type> *inputNodes, node_type startNode, weight_type INFINITE_WEIGHT ) 324 { 325 // Find the shortest path from the start node to each of the input nodes. Add this path to a new WeightedGraph if the result is reachable 326 DataStructures::List<node_type> path; 327 DataStructures::WeightedGraph<node_type, weight_type, allow_unlinkedNodes> outGraph; 328 bool res; 329 unsigned i,j; 330 for (i=0; i < inputNodes->Size(); i++) 331 { 332 res=GetShortestPath(path, startNode, (*inputNodes)[i], INFINITE_WEIGHT); 333 if (res && path.Size()>0) 334 { 335 for (j=0; j < path.Size()-1; j++) 336 { 337 // Don't bother looking up the weight 338 outGraph.AddConnection(path[j], path[j+1], INFINITE_WEIGHT); 339 } 340 } 341 } 342 343 // Copy the graph to a tree. 344 DataStructures::Queue<NodeAndParent> nodesToProcess; 345 DataStructures::Tree<node_type> *current; 346 DataStructures::Map<node_type, weight_type> *adjacencyList; 347 node_type key; 348 NodeAndParent nap, nap2; 349 outTree.DeleteDecendants(); 350 outTree.data=startNode; 351 current=&outTree; 352 if (outGraph.adjacencyLists.Has(startNode)==false) 353 return false; 354 adjacencyList = outGraph.adjacencyLists.Get(startNode); 355 356 for (i=0; i < adjacencyList->Size(); i++) 357 { 358 nap2.node=RakNet::OP_NEW<DataStructures::Tree<node_type> >( __FILE__, __LINE__ ); 359 nap2.node->data=adjacencyList->GetKeyAtIndex(i); 360 nap2.parent=current; 361 nodesToProcess.Push(nap2, __FILE__, __LINE__ ); 362 current->children.Insert(nap2.node, __FILE__, __LINE__); 363 } 364 365 while (nodesToProcess.Size()) 366 { 367 nap=nodesToProcess.Pop(); 368 current=nap.node; 369 adjacencyList = outGraph.adjacencyLists.Get(nap.node->data); 370 371 for (i=0; i < adjacencyList->Size(); i++) 372 { 373 key=adjacencyList->GetKeyAtIndex(i); 374 if (key!=nap.parent->data) 375 { 376 nap2.node=RakNet::OP_NEW<DataStructures::Tree<node_type> >( __FILE__, __LINE__ ); 377 nap2.node->data=key; 378 nap2.parent=current; 379 nodesToProcess.Push(nap2, __FILE__, __LINE__ ); 380 current->children.Insert(nap2.node, __FILE__, __LINE__); 381 } 382 } 383 } 384 385 return true; 386 } 387 388 template <class node_type, class weight_type, bool allow_unlinkedNodes> GenerateDisjktraMatrix(node_type startNode,weight_type INFINITE_WEIGHT)389 void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::GenerateDisjktraMatrix(node_type startNode, weight_type INFINITE_WEIGHT) 390 { 391 if (adjacencyLists.Size()==0) 392 return; 393 394 costMatrix = RakNet::OP_NEW_ARRAY<weight_type>(adjacencyLists.Size() * adjacencyLists.Size(), __FILE__, __LINE__ ); 395 leastNodeArray = RakNet::OP_NEW_ARRAY<node_type>(adjacencyLists.Size(), __FILE__, __LINE__ ); 396 397 node_type currentNode; 398 unsigned col, row, row2, openSetIndex; 399 node_type adjacentKey; 400 unsigned adjacentIndex; 401 weight_type edgeWeight, currentNodeWeight, adjacentNodeWeight; 402 DataStructures::Map<node_type, weight_type> *adjacencyList; 403 DataStructures::Heap<weight_type, node_type, false> minHeap; 404 DataStructures::Map<node_type, weight_type> openSet; 405 406 for (col=0; col < adjacencyLists.Size(); col++) 407 { 408 // This should be already sorted, so it's a bit inefficient to do an insertion sort, but what the heck 409 costMatrixIndices.Insert(adjacencyLists.GetKeyAtIndex(col),adjacencyLists.GetKeyAtIndex(col), true, __FILE__,__LINE__); 410 } 411 for (col=0; col < adjacencyLists.Size() * adjacencyLists.Size(); col++) 412 costMatrix[col]=INFINITE_WEIGHT; 413 currentNode=startNode; 414 row=0; 415 currentNodeWeight=0; 416 rootNode=startNode; 417 418 // Clear the starting node column 419 if (adjacencyLists.Size()) 420 { 421 adjacentIndex=adjacencyLists.GetIndexAtKey(startNode); 422 for (row2=0; row2 < adjacencyLists.Size(); row2++) 423 costMatrix[row2*adjacencyLists.Size() + adjacentIndex]=0; 424 } 425 426 while (row < adjacencyLists.Size()-1) 427 { 428 adjacencyList = adjacencyLists.Get(currentNode); 429 // Go through all connections from the current node. If the new weight is less than the current weight, then update that weight. 430 for (col=0; col < adjacencyList->Size(); col++) 431 { 432 edgeWeight=(*adjacencyList)[col]; 433 adjacentKey=adjacencyList->GetKeyAtIndex(col); 434 adjacentIndex=adjacencyLists.GetIndexAtKey(adjacentKey); 435 adjacentNodeWeight=costMatrix[row*adjacencyLists.Size() + adjacentIndex]; 436 437 if (currentNodeWeight + edgeWeight < adjacentNodeWeight) 438 { 439 // Update the weight for the adjacent node 440 for (row2=row; row2 < adjacencyLists.Size(); row2++) 441 costMatrix[row2*adjacencyLists.Size() + adjacentIndex]=currentNodeWeight + edgeWeight; 442 openSet.Set(adjacentKey, currentNodeWeight + edgeWeight); 443 } 444 } 445 446 // Find the lowest in the open set 447 minHeap.Clear(true,__FILE__,__LINE__); 448 for (openSetIndex=0; openSetIndex < openSet.Size(); openSetIndex++) 449 minHeap.Push(openSet[openSetIndex], openSet.GetKeyAtIndex(openSetIndex),__FILE__,__LINE__); 450 451 /* 452 unsigned i,j; 453 for (i=0; i < adjacencyLists.Size()-1; i++) 454 { 455 for (j=0; j < adjacencyLists.Size(); j++) 456 { 457 RAKNET_DEBUG_PRINTF("%2i ", costMatrix[i*adjacencyLists.Size() + j]); 458 } 459 RAKNET_DEBUG_PRINTF("Node=%i", leastNodeArray[i]); 460 RAKNET_DEBUG_PRINTF("\n"); 461 } 462 */ 463 464 if (minHeap.Size()==0) 465 { 466 // Unreachable nodes 467 isValidPath=true; 468 return; 469 } 470 471 currentNodeWeight=minHeap.PeekWeight(0); 472 leastNodeArray[row]=minHeap.Pop(0); 473 currentNode=leastNodeArray[row]; 474 openSet.Delete(currentNode); 475 row++; 476 } 477 478 /* 479 #ifdef _DEBUG 480 unsigned i,j; 481 for (i=0; i < adjacencyLists.Size()-1; i++) 482 { 483 for (j=0; j < adjacencyLists.Size(); j++) 484 { 485 RAKNET_DEBUG_PRINTF("%2i ", costMatrix[i*adjacencyLists.Size() + j]); 486 } 487 RAKNET_DEBUG_PRINTF("Node=%i", leastNodeArray[i]); 488 RAKNET_DEBUG_PRINTF("\n"); 489 } 490 #endif 491 */ 492 493 isValidPath=true; 494 } 495 496 template <class node_type, class weight_type, bool allow_unlinkedNodes> ClearDijkstra(void)497 void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::ClearDijkstra(void) 498 { 499 if (isValidPath) 500 { 501 isValidPath=false; 502 RakNet::OP_DELETE_ARRAY(costMatrix, __FILE__, __LINE__); 503 RakNet::OP_DELETE_ARRAY(leastNodeArray, __FILE__, __LINE__); 504 costMatrixIndices.Clear(false, __FILE__, __LINE__); 505 } 506 } 507 508 template <class node_type, class weight_type, bool allow_unlinkedNodes> Print(void)509 void WeightedGraph<node_type, weight_type, allow_unlinkedNodes>::Print(void) 510 { 511 #ifdef _DEBUG 512 unsigned i,j; 513 for (i=0; i < adjacencyLists.Size(); i++) 514 { 515 //RAKNET_DEBUG_PRINTF("%i connected to ", i); 516 RAKNET_DEBUG_PRINTF("%s connected to ", adjacencyLists.GetKeyAtIndex(i).systemAddress.ToString()); 517 518 if (adjacencyLists[i]->Size()==0) 519 RAKNET_DEBUG_PRINTF("<Empty>"); 520 else 521 { 522 for (j=0; j < adjacencyLists[i]->Size(); j++) 523 // RAKNET_DEBUG_PRINTF("%i (%.2f) ", adjacencyLists.GetIndexAtKey(adjacencyLists[i]->GetKeyAtIndex(j)), (float) adjacencyLists[i]->operator[](j) ); 524 RAKNET_DEBUG_PRINTF("%s (%.2f) ", adjacencyLists[i]->GetKeyAtIndex(j).systemAddress.ToString(), (float) adjacencyLists[i]->operator[](j) ); 525 } 526 527 RAKNET_DEBUG_PRINTF("\n"); 528 } 529 #endif 530 } 531 } 532 533 #ifdef _MSC_VER 534 #pragma warning( pop ) 535 #endif 536 537 #endif 538