Main Page | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages

Common/vtkPriorityQueue.h

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