This file is indexed.

/usr/include/libMems-1.6/libMems/TreeUtilities.h is in libmems-1.6-dev 1.6.0+4725-2.

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
#ifndef __TreeUtilities_h__
#define __TreeUtilities_h__

#include <stack>

namespace mems {

template<class T, class S>
void findAndErase( T& container, S& item )
{
	T new_container;
	for( typename T::iterator t_iter = container.begin(); t_iter != container.end(); t_iter++ )
		if( *t_iter != item )
			new_container.push_back( *t_iter );
	container = new_container;
};

/**
 * Depth first search to check whether a subtree contains a given node
 */
template<class Tree>
bool containsNode( Tree& t, node_id_t subtree_nodeI, node_id_t query_nodeI )
{
	std::stack< node_id_t > node_stack;
	node_stack.push( subtree_nodeI );
	while( node_stack.size() > 0 )
	{
		node_id_t cur_node = node_stack.top();
		node_stack.pop();
		if( cur_node == query_nodeI )
			return true;
		if( t[cur_node].children.size() > 0 )
		{
			for( size_t childI = 0; childI < t[cur_node].children.size(); childI++ )
				node_stack.push( t[cur_node].children[childI] );
		}
	}
	return false;
}


/** place a root on the branch with endpoints root_left and root_right
 */
template<class Tree>
void rerootTree( Tree& t, node_id_t new_root )
{
	// new root must be an internal node
	if( t[new_root].children.size() == 0 )
		throw "Can't root on a leaf node";
	if( new_root == t.root )
		return;	// idiot caller didn't realize it's already rooted here

	// change the old root node to an internal node
	uint childI = 0;
	for( ; childI < t[t.root].children.size(); childI++ ){
		if( containsNode( t, t[t.root].children[childI], new_root ) )
		{
			t[t.root].parents.push_back( t[t.root].children[childI] );
			findAndErase( t[t.root].children, t[t.root].children[childI] );
			break;
		}
	}
	// shake the tree out on the new root node
	t.root = new_root;
	t[t.root].children.insert( t[t.root].children.end(), t[t.root].parents.begin(), t[t.root].parents.end() );
	t[t.root].parents.clear();

	std::stack<node_id_t> node_stack;
	node_stack.push(t.root);
	while( node_stack.size() > 0 )
	{
		// delete the current node from all of its child nodes lists 
		// and insert it as a parent
		// make all other nodes reference by the child grandchildren
		// recurse on each child
		node_id_t cur_node = node_stack.top();
		node_stack.pop();
		for( uint childI = 0; childI < t[cur_node].children.size(); childI++ )
		{
			findAndErase( t[t[cur_node].children[childI]].children, cur_node );
			findAndErase( t[t[cur_node].children[childI]].parents, cur_node );
			t[t[cur_node].children[childI]].children.insert( t[t[cur_node].children[childI]].children.end(), t[t[cur_node].children[childI]].parents.begin(), t[t[cur_node].children[childI]].parents.end() );
			t[t[cur_node].children[childI]].parents.clear();
			t[t[cur_node].children[childI]].parents.push_back(cur_node);
			node_stack.push(t[cur_node].children[childI]);
		}
	}
}

/**
 * takes a rooted tree and moves the root to a branch
 */
template<class Tree>
void moveRootToBranch( Tree& t, node_id_t left_node, node_id_t right_node )
{
	// this function has no effect if left_node or right_node are already the root
	if( left_node == t.root || right_node == t.root )
		return;
	// left_node and right_node must be adjacent
	if( (t[left_node].parents.size() == 0 || t[right_node].parents.size() == 0 ) ||
		(t[left_node].parents[0] != right_node && t[right_node].parents[0] != left_node ) )
		return;

	if( t[left_node].children.size() == 0 )
		swap( left_node, right_node );	// left node was a leaf so root on right node

	// save the root
	node_id_t old_root = t.root;
	// reroot the tree on left_node, then move the old root on the branch leading to right_node
	rerootTree( t, left_node );
	// remove old_root
	node_id_t rp = t[old_root].parents[0];
	findAndErase( t[rp].children, old_root );
	for( size_t cI = 0; cI < t[old_root].children.size(); cI++ )
	{
		t[t[old_root].children[cI]].parents[0] = rp;
		t[t[old_root].children[cI]].distance += t[old_root].distance;
		t[rp].children.push_back( t[old_root].children[cI] );
	}
	t[old_root].children.clear();

	// link old_root in between left_node and right_node
	findAndErase( t[left_node].children, right_node );
	t[left_node].children.push_back( old_root );
	t[old_root].parents[0] = left_node;
	t[right_node].parents[0] = old_root;
	t[old_root].children.push_back( right_node );
	t[old_root].distance = t[right_node].distance / 2.0;
	t[right_node].distance /= 2.0;

	// finally reroot on old_root
	rerootTree( t, old_root );
}


}	// namespace mems

#endif // __TreeUtilities_h__