statistc.h File Reference

#include <cstdio>
#include "host.h"
#include "kdpair.h"
#include "scrollview.h"

Go to the source code of this file.

Classes
class	GenericVector< T >
class	STATS

Functions
int32_t	choose_nth_item (int32_t index, float *array, int32_t count)
int32_t	choose_nth_item (int32_t index, void *array, int32_t count, size_t size, int(*compar)(const void *, const void *))
void	swap_entries (void *array, size_t size, int32_t index1, int32_t index2)

Function Documentation

choose_nth_item() [1/2]

int32_t choose_nth_item	(	int32_t	index,
		float *	array,
		int32_t	count
	)

Definition at line 637 of file statistc.cpp.

                                                                    {
  int32_t next_sample;             // next one to do
  int32_t next_lesser;             // space for new
  int32_t prev_greater;            // last one saved
  int32_t equal_count;             // no of equal ones
  float pivot;                   // proposed median
  float sample;                  // current sample

  if (count <= 1)
    return 0;
  if (count == 2) {
    if (array[0] < array[1]) {
      return index >= 1 ? 1 : 0;
    }
    else {
      return index >= 1 ? 0 : 1;
    }
  }
  else {
    if (index < 0)
      index = 0;                 // ensure legal
    else if (index >= count)
      index = count - 1;
    equal_count = (int32_t) (rand() % count);
    pivot = array[equal_count];
                                 // fill gap
    array[equal_count] = array[0];
    next_lesser = 0;
    prev_greater = count;
    equal_count = 1;
    for (next_sample = 1; next_sample < prev_greater;) {
      sample = array[next_sample];
      if (sample < pivot) {
                                 // shuffle
        array[next_lesser++] = sample;
        next_sample++;
      }
      else if (sample > pivot) {
        prev_greater--;
                                 // juggle
        array[next_sample] = array[prev_greater];
        array[prev_greater] = sample;
      }
      else {
        equal_count++;
        next_sample++;
      }
    }
    for (next_sample = next_lesser; next_sample < prev_greater;)
      array[next_sample++] = pivot;
    if (index < next_lesser)
      return choose_nth_item (index, array, next_lesser);
    else if (index < prev_greater)
      return next_lesser;        // in equal bracket
    else
      return choose_nth_item (index - prev_greater,
        array + prev_greater,
        count - prev_greater) + prev_greater;
  }
}

choose_nth_item() [2/2]

int32_t choose_nth_item	(	int32_t	index,
		void *	array,
		int32_t	count,
		size_t	size,
		int(*)(const void *, const void *)	compar
	)

Definition at line 704 of file statistc.cpp.

                                                               {
  int result;                    // of compar
  int32_t next_sample;             // next one to do
  int32_t next_lesser;             // space for new
  int32_t prev_greater;            // last one saved
  int32_t equal_count;             // no of equal ones
  int32_t pivot;                   // proposed median

  if (count <= 1)
    return 0;
  if (count == 2) {
    if (compar (array, (char *) array + size) < 0) {
      return index >= 1 ? 1 : 0;
    }
    else {
      return index >= 1 ? 0 : 1;
    }
  }
  if (index < 0)
    index = 0;                   // ensure legal
  else if (index >= count)
    index = count - 1;
  pivot = (int32_t) (rand () % count);
  swap_entries (array, size, pivot, 0);
  next_lesser = 0;
  prev_greater = count;
  equal_count = 1;
  for (next_sample = 1; next_sample < prev_greater;) {
    result =
      compar ((char *) array + size * next_sample,
      (char *) array + size * next_lesser);
    if (result < 0) {
      swap_entries (array, size, next_lesser++, next_sample++);
      // shuffle
    }
    else if (result > 0) {
      prev_greater--;
      swap_entries(array, size, prev_greater, next_sample);
    }
    else {
      equal_count++;
      next_sample++;
    }
  }
  if (index < next_lesser)
    return choose_nth_item (index, array, next_lesser, size, compar);
  else if (index < prev_greater)
    return next_lesser;          // in equal bracket
  else
    return choose_nth_item (index - prev_greater,
      (char *) array + size * prev_greater,
      count - prev_greater, size,
      compar) + prev_greater;
}

swap_entries()

void swap_entries	(	void *	array,
		size_t	size,
		int32_t	index1,
		int32_t	index2
	)

Definition at line 765 of file statistc.cpp.

                                  {
  char tmp;
  char *ptr1;                    // to entries
  char *ptr2;
  size_t count;                  // of bytes

  ptr1 = static_cast<char *>(array) + index1 * size;
  ptr2 = static_cast<char *>(array) + index2 * size;
  for (count = 0; count < size; count++) {
    tmp = *ptr1;
    *ptr1++ = *ptr2;
    *ptr2++ = tmp;               // tedious!
  }
}