load_binary_tree_from_forward_iterator.h File Reference

This file contains the code for the function template load_binary_tree_from_forward_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_forward_iterator (pnt begin, pnt end, mp &container, to_map_element tme)

---

Detailed Description

This file contains the code for the function template load_binary_tree_from_forward_iterator.

Definition in file load_binary_tree_from_forward_iterator.h.

---

Function Documentation

template<class pnt , class mp , typename to_map_element >

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

Assumes:

1. class pnt is a forward iterator.
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 44 of file load_binary_tree_from_forward_iterator.h.

{
  unsigned long long len = 0;

  pnt pdata = begin;
  for (; pdata != end; ++len, ++pdata)
    {
    }

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

  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;
}