Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound 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 =========================================================================*/
00056 #ifndef __vtkPriorityQueue_h
00057 #define __vtkPriorityQueue_h
00058 
00059 #include "vtkObject.h"
00060 
00061 #include "vtkIdTypeArray.h" // Needed for inline methods
00062 
00063 class VTK_COMMON_EXPORT vtkPriorityQueue : public vtkObject
00064 {
00065 public:
00066   //BTX
00067   class Item
00068   {
00069   public:
00070     float priority;
00071     vtkIdType id;
00072   };
00073   //ETX
00074 
00077   static vtkPriorityQueue *New();
00078 
00079   vtkTypeRevisionMacro(vtkPriorityQueue,vtkObject);
00080   void PrintSelf(ostream& os, vtkIndent indent);
00081 
00083   void Allocate(const vtkIdType sz, const vtkIdType ext=1000);
00084 
00087   void Insert(float priority, vtkIdType id);
00088 
00093   vtkIdType Pop(vtkIdType location, float &priority);
00094 //ETX    
00095 
00098   vtkIdType Pop(vtkIdType location=0);
00099 
00102   vtkIdType Peek(vtkIdType location, float &priority);
00103 //ETX    
00104   
00107   vtkIdType Peek(vtkIdType location=0);
00108 
00111   float DeleteId(vtkIdType id);
00112 
00115   float GetPriority(vtkIdType id);
00116 
00118   vtkIdType GetNumberOfItems() {return this->MaxId+1;};
00119 
00122   void Reset();
00123 
00124 protected:
00125   vtkPriorityQueue();
00126   ~vtkPriorityQueue();
00127   
00128   Item *Resize(const vtkIdType sz);
00129 
00130   vtkIdTypeArray *ItemLocation;
00131   Item *Array;
00132   vtkIdType Size;
00133   vtkIdType MaxId;
00134   vtkIdType Extend;
00135 private:
00136   vtkPriorityQueue(const vtkPriorityQueue&);  // Not implemented.
00137   void operator=(const vtkPriorityQueue&);  // Not implemented.
00138 };
00139 
00140 inline float vtkPriorityQueue::DeleteId(vtkIdType id)
00141 {
00142   float priority=VTK_LARGE_FLOAT;
00143   int loc;
00144 
00145   if ( id <= this->ItemLocation->GetMaxId() &&  
00146   (loc=this->ItemLocation->GetValue(id)) != -1 )
00147     {
00148     this->Pop(loc,priority);
00149     }
00150   return priority;
00151 }
00152 
00153 inline float vtkPriorityQueue::GetPriority(vtkIdType id)
00154 {
00155   int loc;
00156 
00157   if ( id <= this->ItemLocation->GetMaxId() &&  
00158   (loc=this->ItemLocation->GetValue(id)) != -1 )
00159     {
00160     return this->Array[loc].priority;
00161     }
00162   return VTK_LARGE_FLOAT;
00163 }
00164 
00165 inline vtkIdType vtkPriorityQueue::Peek(vtkIdType location, float &priority)
00166 {
00167   if ( this->MaxId < 0 )
00168     {
00169     return -1;
00170     }
00171   else
00172     {
00173     priority = this->Array[location].priority;
00174     return this->Array[location].id;
00175     }
00176 }
00177 
00178 inline vtkIdType vtkPriorityQueue::Peek(vtkIdType location)
00179 {
00180   if ( this->MaxId < 0 )
00181     {
00182     return -1;
00183     }
00184   else
00185     {
00186     return this->Array[location].id;
00187     }
00188 }
00189 
00190 #endif