load_binary_tree_from_random_access_iterator.h File Reference

This file contains the code for the function template load_binary_tree_from_random_access_iterator. More...

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
template<class pnt , class mp , typename to_map_element >
void	breadth_first_load_binary_tree_from_random_access_iterator (pnt begin, pnt end, mp &container, to_map_element tme)
	This function populates "container" by repeatedly inserting the median values.

---

Detailed Description

This file contains the code for the function template load_binary_tree_from_random_access_iterator.

Definition in file load_binary_tree_from_random_access_iterator.h.

---

Function Documentation

template<class pnt , class mp , typename to_map_element >

void breadth_first_load_binary_tree_from_random_access_iterator	(	pnt	begin,
		pnt	end,
		mp &	container,
		to_map_element	tme
	)			[inline]

This function populates "container" by repeatedly inserting the median values.

Parameters:

	begin	the first iterator in the range to be inserted
	end	an iterator marking the end of the range, ie. one past the last element
	container	the binary tree container
	to_map_element	a function of functor which takes an element of class *pnt, and returns a value of type std::pair<T,*pnt> create_map_pair, where T is the class of the key in container

Assumes:

1. class pnt is a random access iterator or more specifically it has a difference operator, "-", and a square bracket operator.
2. the class *pnt, has a less than operator, <.
3. the range from begin to end is sorted according to the < operator for *pnt
4. typename to_map_element, is a function which maps the dereferenced class of pnt, "*pnt", to the appropriate element type class mp.
5. class mp has a functions, empty, clean and insert and that insert is compatible with to_map_element.
6. class mp, uses some sort of tree structure to store data, which uses a < operator which is logically equivalent to the < operator for *pnt.
7. by repeatedly inserting median values, the tree structure of mp, is optimized for average best performance.

Changes: container
Description: This function populates "container" by repeatedly inserting the median values. Specifically, the first insert is for the median between begin and end. Subsequent inserts are for the medians between previous inserts and or begin or end. The medians are chosen in a breadth first search, so that the tree is approximately balanced at all points in time. This should prevent any unnecessary, and possibly non optimal, tree rotations in "container", if class mp automatically rebalances the tree.

Definition at line 52 of file load_binary_tree_from_random_access_iterator.h.

{
  unsigned long long len = end - begin;
  pnt *pointer_array = new pnt[len];
  unsigned long long i, j;
  for (i=0; i<len; ++i) {
    pointer_array[i] = begin + i;
  }

  if (!container.empty()) {
    container.clear();
  }

  unsigned long long step_size = len;
  j = len;
  while(step_size > 0) {
    for (i = step_size >> 1; i < len; i += step_size) {
      if (pointer_array[i] != end) {
        container.insert( tme( *pointer_array[i]));
        pointer_array[i] = end;
      }
    }
    step_size >>= 1;
  }

  delete[] pointer_array;
}