This file is indexed.

/usr/include/terralib/kernel/dynpq.h is in libterralib-dev 4.3.0+dfsg.2-4build2.

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
182
183
184
185
186
187
188
189
/************************************************************************************
TerraLib - a library for developing GIS applications.
Copyright © 2001-2007 INPE and Tecgraf/PUC-Rio.

This code is part of the TerraLib library.
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.

You should have received a copy of the GNU Lesser General Public
License along with this library.

The authors reassure the license terms regarding the warranties.
They specifically disclaim any warranties, including, but not limited to,
the implied warranties of merchantability and fitness for a particular purpose.
The library provided hereunder is on an "as is" basis, and the authors have no
obligation to provide maintenance, support, updates, enhancements, or modifications.
In no event shall INPE and Tecgraf / PUC-Rio be held liable to any party for direct,
indirect, special, incidental, or consequential damages arising out of the use
of this library and its documentation.
*************************************************************************************/

// include/dynpq.h
#ifndef DYNPQ_H
#define DYNPQ_H
#include<checkvec.h>
#include<algorithm>
#include<showseq.h>

namespace br_stl
{
	// compares the associated values of passed iterators
	template<class T>
	struct IterGreater
	{
		bool operator()( T x,  T y) const
		{
			return *y < *x;
		}
	};

	template <class key_type>
	class dynamic_priority_queue
	{
	public:
		// public type definitions
		typedef typename std::vector<key_type>::size_type size_type;
		typedef typename std::vector<key_type>::difference_type index_type;

		// constructor
		dynamic_priority_queue(std::vector<key_type>& v);

		// change a value at position 'at'
		void changeKeyAt(index_type at, key_type k);

		// index of the smallest element (= highest priority)
		index_type topIndex() const { return c.front() - first; }

		// value of the smallest element (= highest priority)
		const key_type& topKey() const { return *c.front(); }

		void pop();       // remove smallest element from the heap

		bool empty() const { return csize == 0;}
		size_type size() const { return csize;}

	private:
	//    checkedVector<index_type> Indices;      // auxiliary vector ANAP
		vector<index_type> Indices;      // auxiliary vector
		typedef typename std::vector<key_type>::iterator randomAccessIterator;
	//    checkedVector<randomAccessIterator> c;  // heap of iterators  ANAP
		vector<randomAccessIterator> c;  // heap of iterators 
		randomAccessIterator first;             // beginning of the external vector
		IterGreater<randomAccessIterator> comp; // comparison object
		index_type csize;                       // current heap size

		// heap update (see below)
		void goUp(index_type);
		void goDown(index_type);
	};

	template <class key_type>
	dynamic_priority_queue<key_type>::dynamic_priority_queue(
		std::vector<key_type>& v)
	: Indices(v.size()), c(v.size()), first(v.begin()),
	csize(v.size())
	{
		// store iterators and generate heap
		for(index_type i = 0; i< csize; ++i) 
		c[i] = v.begin()+i;
		make_heap(c.begin(), c.end(), comp);        // STL

		// construct index array
		for(index_type ii = 0; ii< csize; ++ii) // ANAP i-> ii
		Indices[c[ii] - first] = ii;
	}

	template <class key_type>
	void dynamic_priority_queue<key_type>::changeKeyAt(
									index_type at, key_type k)
	{
	index_type idx = Indices[at];

	//  if (idx < csize) //ANAP
	// {
	assert(idx < csize);   // value still present in the queue?

	if(*c[idx] != k)       // in case of equality, do nothing
		if(k > *c[idx])
		{
			*c[idx] = k;   // enter heavier value
			goDown(idx);   // reorganize heap
		}
		else
		{
			*c[idx] = k;   // enter lighter value
			goUp(idx);     // reorganize heap
		}
	//	 }
	// else cout << "erro no dynamic_priority_queue<key_type>::changeKeyAt" << idx << csize << k << endl;
	}

	template <class key_type>
	void dynamic_priority_queue<key_type>::goUp(index_type idx)
	{
		index_type Predecessor = (idx-1)/2;
		randomAccessIterator temp = c[idx];

		while(Predecessor != idx && comp(c[Predecessor], temp))
		{
			c[idx] = c[Predecessor];
			Indices[c[idx]-first] = idx;
			idx = Predecessor;
			Predecessor = (idx-1)/2;
		}
	    
		c[idx] = temp;
		Indices[c[idx]-first] = idx;
	}

	template <class key_type>
	void dynamic_priority_queue<key_type>::goDown(index_type idx)
	{
		index_type Successor = (idx+1)*2-1;

		if(Successor < csize-1
			&& comp(c[Successor], c[Successor+1]))
			++Successor;
		randomAccessIterator temp = c[idx];

		while(Successor < csize && comp(temp, c[Successor]))
		{
			c[idx] = c[Successor];
			Indices[c[idx]-first] = idx;
			idx = Successor;
			Successor = (idx+1)*2-1;

			if(Successor < csize-1
			&& comp(c[Successor], c[Successor+1]))
				++Successor;
		}
		c[idx] = temp;
		Indices[c[idx]-first] = idx;
	}

	/* The method pop() removes the topmost element from the heap. This is
	done by moving the last element to the top and blocking the freed
	position with --csize. Subsequently, the element sinks down to its
	proper position. */

	template <class key_type>
	void dynamic_priority_queue<key_type>::pop()
	{
	// overwrite iterator at the top with the 
	// address of the last element
	c[0] = c[--csize];

	// enter the new address 0 at the position belonging 
	// to this element in the auxiliary array
	Indices[c[0]-first] = 0;

	// let the element at the top sink to the correct
	// position corresponding to its weight
	goDown(0);
	}

} // namespace br_stl
#endif