statistc.h File Reference

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

Go to the source code of this file.

Classes
singleton	GenericVector< T >
class	STATS

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

Function Documentation

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

Definition at line 642 of file statistc.cpp.

                                                              {
  inT32 next_sample;             // next one to do
  inT32 next_lesser;             // space for new
  inT32 prev_greater;            // last one saved
  inT32 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) (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;
  }
}

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

Definition at line 709 of file statistc.cpp.

                                                               {
  int result;                    // of compar
  inT32 next_sample;             // next one to do
  inT32 next_lesser;             // space for new
  inT32 prev_greater;            // last one saved
  inT32 equal_count;             // no of equal ones
  inT32 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) (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;
}

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

Definition at line 770 of file statistc.cpp.

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

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