00001 /*========================================================================= 00002 00003 Program: Visualization Toolkit 00004 Module: vtkPriorityQueue.h 00005 00006 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen 00007 All rights reserved. 00008 See Copyright.txt or http://www.kitware.com/Copyright.htm for details. 00009 00010 This software is distributed WITHOUT ANY WARRANTY; without even 00011 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 00012 PURPOSE. See the above copyright notice for more information. 00013 00014 =========================================================================*/ 00037 #ifndef __vtkPriorityQueue_h 00038 #define __vtkPriorityQueue_h 00039 00040 #include "vtkObject.h" 00041 00042 #include "vtkIdTypeArray.h" // Needed for inline methods 00043 00044 class VTK_COMMON_EXPORT vtkPriorityQueue : public vtkObject 00045 { 00046 public: 00047 //BTX 00048 class Item 00049 { 00050 public: 00051 double priority; 00052 vtkIdType id; 00053 }; 00054 //ETX 00055 00058 static vtkPriorityQueue *New(); 00059 00060 vtkTypeMacro(vtkPriorityQueue,vtkObject); 00061 void PrintSelf(ostream& os, vtkIndent indent); 00062 00064 void Allocate(const vtkIdType sz, const vtkIdType ext=1000); 00065 00068 void Insert(double priority, vtkIdType id); 00069 00074 vtkIdType Pop(vtkIdType location, double &priority); 00075 //ETX 00076 00079 vtkIdType Pop(vtkIdType location=0); 00080 00083 vtkIdType Peek(vtkIdType location, double &priority); 00084 //ETX 00085 00088 vtkIdType Peek(vtkIdType location=0); 00089 00092 double DeleteId(vtkIdType id); 00093 00096 double GetPriority(vtkIdType id); 00097 00099 vtkIdType GetNumberOfItems() {return this->MaxId+1;}; 00100 00103 void Reset(); 00104 00105 protected: 00106 vtkPriorityQueue(); 00107 ~vtkPriorityQueue(); 00108 00109 Item *Resize(const vtkIdType sz); 00110 00111 vtkIdTypeArray *ItemLocation; 00112 Item *Array; 00113 vtkIdType Size; 00114 vtkIdType MaxId; 00115 vtkIdType Extend; 00116 private: 00117 vtkPriorityQueue(const vtkPriorityQueue&); // Not implemented. 00118 void operator=(const vtkPriorityQueue&); // Not implemented. 00119 }; 00120 00121 inline double vtkPriorityQueue::DeleteId(vtkIdType id) 00122 { 00123 double priority=VTK_DOUBLE_MAX; 00124 int loc; 00125 00126 if ( id <= this->ItemLocation->GetMaxId() && 00127 (loc=this->ItemLocation->GetValue(id)) != -1 ) 00128 { 00129 this->Pop(loc,priority); 00130 } 00131 return priority; 00132 } 00133 00134 inline double vtkPriorityQueue::GetPriority(vtkIdType id) 00135 { 00136 int loc; 00137 00138 if ( id <= this->ItemLocation->GetMaxId() && 00139 (loc=this->ItemLocation->GetValue(id)) != -1 ) 00140 { 00141 return this->Array[loc].priority; 00142 } 00143 return VTK_DOUBLE_MAX; 00144 } 00145 00146 inline vtkIdType vtkPriorityQueue::Peek(vtkIdType location, double &priority) 00147 { 00148 if ( this->MaxId < 0 ) 00149 { 00150 return -1; 00151 } 00152 else 00153 { 00154 priority = this->Array[location].priority; 00155 return this->Array[location].id; 00156 } 00157 } 00158 00159 inline vtkIdType vtkPriorityQueue::Peek(vtkIdType location) 00160 { 00161 if ( this->MaxId < 0 ) 00162 { 00163 return -1; 00164 } 00165 else 00166 { 00167 return this->Array[location].id; 00168 } 00169 } 00170 00171 #endif
1.5.6