/usr/include/vtk-5.8/vtkPriorityQueue.h is in libvtk5-dev 5.8.0-5.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 | /*=========================================================================
Program: Visualization Toolkit
Module: vtkPriorityQueue.h
Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
All rights reserved.
See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
This software is distributed WITHOUT ANY WARRANTY; without even
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the above copyright notice for more information.
=========================================================================*/
// .NAME vtkPriorityQueue - an list of ids arranged in priority order
// .SECTION Description
// vtkPriorityQueue is a general object for creating and manipulating lists
// of object ids (e.g., point or cell ids). Object ids are sorted according
// to a user-specified priority, where entries at the top of the queue have
// the smallest values.
//
// This implementation provides a feature beyond the usual ability to insert
// and retrieve (or pop) values from the queue. It is also possible to
// pop any item in the queue given its id number. This allows you to delete
// entries in the queue which can useful for reinserting an item into the
// queue.
//
// .SECTION Caveats
// This implementation is a variation of the priority queue described in
// "Data Structures & Algorithms" by Aho, Hopcroft, Ullman. It creates
// a balanced, partially ordered binary tree implemented as an ordered
// array. This avoids the overhead associated with parent/child pointers,
// and frequent memory allocation and deallocation.
#ifndef __vtkPriorityQueue_h
#define __vtkPriorityQueue_h
#include "vtkObject.h"
#include "vtkIdTypeArray.h" // Needed for inline methods
class VTK_COMMON_EXPORT vtkPriorityQueue : public vtkObject
{
public:
//BTX
class Item
{
public:
double priority;
vtkIdType id;
};
//ETX
// Description:
// Instantiate priority queue with default size and extension size of 1000.
static vtkPriorityQueue *New();
vtkTypeMacro(vtkPriorityQueue,vtkObject);
void PrintSelf(ostream& os, vtkIndent indent);
// Description:
// Allocate initial space for priority queue.
void Allocate(const vtkIdType sz, const vtkIdType ext=1000);
// Description:
// Insert id with priority specified. The id is generally an
// index like a point id or cell id.
void Insert(double priority, vtkIdType id);
//BTX
// Description:
// Removes item at specified location from tree; then reorders and
// balances tree. The location == 0 is the root of the tree. If queue
// is exhausted, then a value < 0 is returned. (Note: the location
// is not the same as deleting an id; id is mapped to location.)
vtkIdType Pop(vtkIdType location, double &priority);
//ETX
// Description:
// Same as above but simplified for easier wrapping into interpreted
// languages.
vtkIdType Pop(vtkIdType location=0);
//BTX
// Description:
// Peek into the queue without actually removing anything. Returns the
// id and the priority.
vtkIdType Peek(vtkIdType location, double &priority);
//ETX
// Description:
// Peek into the queue without actually removing anything. Returns the
// id.
vtkIdType Peek(vtkIdType location=0);
// Description:
// Delete entry in queue with specified id. Returns priority value
// associated with that id; or VTK_DOUBLE_MAX if not in queue.
double DeleteId(vtkIdType id);
// Description:
// Get the priority of an entry in the queue with specified id. Returns
// priority value of that id or VTK_DOUBLE_MAX if not in queue.
double GetPriority(vtkIdType id);
// Description:
// Return the number of items in this queue.
vtkIdType GetNumberOfItems() {return this->MaxId+1;};
// Description:
// Empty the queue but without releasing memory. This avoids the
// overhead of memory allocation/deletion.
void Reset();
protected:
vtkPriorityQueue();
~vtkPriorityQueue();
Item *Resize(const vtkIdType sz);
vtkIdTypeArray *ItemLocation;
Item *Array;
vtkIdType Size;
vtkIdType MaxId;
vtkIdType Extend;
private:
vtkPriorityQueue(const vtkPriorityQueue&); // Not implemented.
void operator=(const vtkPriorityQueue&); // Not implemented.
};
inline double vtkPriorityQueue::DeleteId(vtkIdType id)
{
double priority=VTK_DOUBLE_MAX;
int loc;
if ( id <= this->ItemLocation->GetMaxId() &&
(loc=this->ItemLocation->GetValue(id)) != -1 )
{
this->Pop(loc,priority);
}
return priority;
}
inline double vtkPriorityQueue::GetPriority(vtkIdType id)
{
int loc;
if ( id <= this->ItemLocation->GetMaxId() &&
(loc=this->ItemLocation->GetValue(id)) != -1 )
{
return this->Array[loc].priority;
}
return VTK_DOUBLE_MAX;
}
inline vtkIdType vtkPriorityQueue::Peek(vtkIdType location, double &priority)
{
if ( this->MaxId < 0 )
{
return -1;
}
else
{
priority = this->Array[location].priority;
return this->Array[location].id;
}
}
inline vtkIdType vtkPriorityQueue::Peek(vtkIdType location)
{
if ( this->MaxId < 0 )
{
return -1;
}
else
{
return this->Array[location].id;
}
}
#endif
|