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 
00008 Copyright (c) 1993-2001 Ken Martin, Will Schroeder, Bill Lorensen 
00009 All rights reserved.
00010 
00011 Redistribution and use in source and binary forms, with or without
00012 modification, are permitted provided that the following conditions are met:
00013 
00014  * Redistributions of source code must retain the above copyright notice,
00015    this list of conditions and the following disclaimer.
00016 
00017  * Redistributions in binary form must reproduce the above copyright notice,
00018    this list of conditions and the following disclaimer in the documentation
00019    and/or other materials provided with the distribution.
00020 
00021  * Neither name of Ken Martin, Will Schroeder, or Bill Lorensen nor the names
00022    of any contributors may be used to endorse or promote products derived
00023    from this software without specific prior written permission.
00024 
00025  * Modified source versions must be plainly marked as such, and must not be
00026    misrepresented as being the original software.
00027 
00028 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS''
00029 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00030 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00031 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR
00032 ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00033 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
00034 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
00035 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
00036 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
00037 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00038 
00039 =========================================================================*/
00065 #ifndef __vtkPriorityQueue_h
00066 #define __vtkPriorityQueue_h
00067 
00068 #include "vtkObject.h"
00069 #include "vtkIdTypeArray.h"
00070 
00071 //BTX
00072 typedef struct _vtkPriorityItem
00073   {
00074   float priority;
00075   vtkIdType id;
00076   } vtkPriorityItem;
00077 //ETX
00078 
00079 class VTK_COMMON_EXPORT vtkPriorityQueue : public vtkObject
00080 {
00081 public:
00084   static vtkPriorityQueue *New();
00085 
00086   vtkTypeMacro(vtkPriorityQueue,vtkObject);
00087   void PrintSelf(ostream& os, vtkIndent indent);
00088 
00090   void Allocate(const vtkIdType sz, const vtkIdType ext=1000);
00091 
00094   void Insert(float priority, vtkIdType id);
00095 
00100   vtkIdType Pop(float &priority, vtkIdType location=0);
00101 
00104   vtkIdType Pop(vtkIdType location=0);
00105 
00108   vtkIdType Peek(float &priority, vtkIdType location=0);
00109   
00112   vtkIdType Peek(vtkIdType location=0);
00113 //ETX    
00116   float DeleteId(vtkIdType id);
00117 
00120   float GetPriority(vtkIdType id);
00121 
00123   vtkIdType GetNumberOfItems() {return this->MaxId+1;};
00124 
00127   void Reset();
00128 
00129 protected:
00130   vtkPriorityQueue();
00131   ~vtkPriorityQueue();
00132   
00133   vtkPriorityItem *Resize(const vtkIdType sz);
00134 
00135   vtkIdTypeArray *ItemLocation;
00136   vtkPriorityItem *Array;
00137   vtkIdType Size;
00138   vtkIdType MaxId;
00139   vtkIdType Extend;
00140 private:
00141   vtkPriorityQueue(const vtkPriorityQueue&);  // Not implemented.
00142   void operator=(const vtkPriorityQueue&);  // Not implemented.
00143 };
00144 
00145 inline float vtkPriorityQueue::DeleteId(vtkIdType id)
00146 {
00147   float priority=VTK_LARGE_FLOAT;
00148   int loc;
00149 
00150   if ( id <= this->ItemLocation->GetMaxId() &&  
00151   (loc=this->ItemLocation->GetValue(id)) != -1 )
00152     {
00153     this->Pop(priority,loc);
00154     }
00155   return priority;
00156 }
00157 
00158 inline float vtkPriorityQueue::GetPriority(vtkIdType id)
00159 {
00160   int loc;
00161 
00162   if ( id <= this->ItemLocation->GetMaxId() &&  
00163   (loc=this->ItemLocation->GetValue(id)) != -1 )
00164     {
00165     return this->Array[loc].priority;
00166     }
00167   return VTK_LARGE_FLOAT;
00168 }
00169 
00170 inline vtkIdType vtkPriorityQueue::Peek(float &priority, vtkIdType location)
00171 {
00172   if ( this->MaxId < 0 )
00173     {
00174     return -1;
00175     }
00176   else
00177     {
00178     priority = this->Array[location].priority;
00179     return this->Array[location].id;
00180     }
00181 }
00182 
00183 inline vtkIdType vtkPriorityQueue::Peek(vtkIdType location)
00184 {
00185   if ( this->MaxId < 0 )
00186     {
00187     return -1;
00188     }
00189   else
00190     {
00191     return this->Array[location].id;
00192     }
00193 }
00194 
00195 #endif

Generated on Thu Mar 28 14:19:16 2002 for VTK by doxygen1.2.11.1 written by Dimitri van Heesch, © 1997-2001