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 00070 //BTX 00072 00076 vtkIdType Pop(vtkIdType location, double &priority); 00077 //ETX 00079 00082 vtkIdType Pop(vtkIdType location=0); 00083 00084 //BTX 00086 00088 vtkIdType Peek(vtkIdType location, double &priority); 00089 //ETX 00091 00094 vtkIdType Peek(vtkIdType location=0); 00095 00098 double DeleteId(vtkIdType id); 00099 00102 double GetPriority(vtkIdType id); 00103 00105 vtkIdType GetNumberOfItems() {return this->MaxId+1;}; 00106 00109 void Reset(); 00110 00111 protected: 00112 vtkPriorityQueue(); 00113 ~vtkPriorityQueue(); 00114 00115 Item *Resize(const vtkIdType sz); 00116 00117 vtkIdTypeArray *ItemLocation; 00118 Item *Array; 00119 vtkIdType Size; 00120 vtkIdType MaxId; 00121 vtkIdType Extend; 00122 private: 00123 vtkPriorityQueue(const vtkPriorityQueue&); // Not implemented. 00124 void operator=(const vtkPriorityQueue&); // Not implemented. 00125 }; 00126 00127 inline double vtkPriorityQueue::DeleteId(vtkIdType id) 00128 { 00129 double priority=VTK_DOUBLE_MAX; 00130 int loc; 00131 00132 if ( id <= this->ItemLocation->GetMaxId() && 00133 (loc=this->ItemLocation->GetValue(id)) != -1 ) 00134 { 00135 this->Pop(loc,priority); 00136 } 00137 return priority; 00138 } 00139 00140 inline double vtkPriorityQueue::GetPriority(vtkIdType id) 00141 { 00142 int loc; 00143 00144 if ( id <= this->ItemLocation->GetMaxId() && 00145 (loc=this->ItemLocation->GetValue(id)) != -1 ) 00146 { 00147 return this->Array[loc].priority; 00148 } 00149 return VTK_DOUBLE_MAX; 00150 } 00151 00152 inline vtkIdType vtkPriorityQueue::Peek(vtkIdType location, double &priority) 00153 { 00154 if ( this->MaxId < 0 ) 00155 { 00156 return -1; 00157 } 00158 else 00159 { 00160 priority = this->Array[location].priority; 00161 return this->Array[location].id; 00162 } 00163 } 00164 00165 inline vtkIdType vtkPriorityQueue::Peek(vtkIdType location) 00166 { 00167 if ( this->MaxId < 0 ) 00168 { 00169 return -1; 00170 } 00171 else 00172 { 00173 return this->Array[location].id; 00174 } 00175 } 00176 00177 #endif