Search/buildIntegerProblem.c File Reference

Driver that populates a search structure by invoking insert on integers in sorted order. Populates a search structure by first inserting numElements integers, in sorted order. Thereafter, performs a number of search operations as dictated by the command line arguments. More...

#include <stdlib.h>
#include <stdio.h>
#include <getopt.h>
#include <math.h>
#include <string.h>
#include "problem.h"
#include "report.h"

Functions

void construct (int sz)
 Method to construct the initial search structure to contain 'sz' elements.
void insert (int value)
 Method to insert an integer element into the search structure.
int search (int target, int(*cmp)(const int, const int))
 Method to search for an integer element in the search structure.
int intComp (const int a1, const int a2)
 comparator function to use for all searches.
void prepareInput (int size, int argc, char **argv)
 Construct a random string of size ssize and have 'str1' and 'str2' be allocated strings with the same contents.
void postInputProcessing (long usecs)
 Report properly formatted for table.
void execute ()
 Execute by invoking malloc(numElements) a total of numT times.
void problemUsage ()
 No specific problem usage.

Variables

int verbose
 Determine whether output is to be printed as the computation progresses.
int * searchList
 Information will be stored as pointer of integers.
static float p = 0.25
 Likelihood that target will be in the collection being searched.
static int first = 0
 Should the target always be the first element.
static int z = 50
 Collection Size: default is 50.
static int numFound = 0
 Computed number found.


Detailed Description

Driver that populates a search structure by invoking insert on integers in sorted order. Populates a search structure by first inserting numElements integers, in sorted order. Thereafter, performs a number of search operations as dictated by the command line arguments.

Build up an array of Integers. Done to eliminate costs of comparisons from the equation

Required Input:

  1. seed (-s n)
  2. verbose (-v) if you want expressive output
Overridden Input:
  1. int numElements (-n x) actually is the number of queries, not elements.

Expected methods

  1. extern void construct (int); -- construct initial collection storage
  2. extern void insert (int val); -- add integer to collection
  3. extern int search (int val, int(*cmp)(const char *,const char *));
-- function to initiate search Search considerations
Search domain will be {a,b}^k which guarantees the size of |S| will be a power of 2.
Input flags:
  1. -p n Ratio in range [0,1] of available elements in target [default: .25] This reflects the strings from the domain that are to be searched for. If p=0 then the target strings are never found in the list. If p=1 then the target strings are always found in the list. Value of p in between reflect ratio of behavior.

  2. -s use same failed id (-1) [default: use different ids starting -2, -3, ...]

  3. -f Always search for the first element [default: search without constraint]

  4. -z n Number of elements in the collection

External API

  1. void problemUsage() shows what is expected
  2. void prepareInput() construct target instance DS by repeated invocation of insert(s)
  3. void postInputProcessing() performs post-solution processing
  4. void execute() begin the problem and invoke search methods

Author:
George Heineman
Date:
6/15/08

Function Documentation

void construct ( int  n  ) 

Method to construct the initial search structure to contain 'sz' elements.

Allocate array of 'n' elements for 'ds'.

void execute (  ) 

Execute by invoking malloc(numElements) a total of numT times.

.numElements

output sum to be sure is correct.

void insert ( int  s  ) 

Method to insert an integer element into the search structure.

In our case, we insert the elements into a non-balancing tree.

Parameters:
s Value to be inserted.

int intComp ( const int  a1,
const int  a2 
)

comparator function to use for all searches.

void postInputProcessing ( long  usecs  ) 

Report properly formatted for table.

void prepareInput ( int  size,
int  argc,
char **  argv 
)

Construct a random string of size ssize and have 'str1' and 'str2' be allocated strings with the same contents.

use character-swapping algorithm from strfry.c in glibc

http://www.koders.com/c/fidBD83E492934F9F671DE79B11E6AC0277F9887CF5.aspx

void problemUsage (  ) 

No specific problem usage.

int search ( int  target,
int(*)(const int, const int)  cmp 
)

Method to search for an integer element in the search structure.

Parameters:
target the desired target
cmp the comparison function between two string elements.


Variable Documentation

int first = 0 [static]

Should the target always be the first element.

int numFound = 0 [static]

Computed number found.

float p = 0.25 [static]

Likelihood that target will be in the collection being searched.

int* searchList

Information will be stored as pointer of integers.

int verbose

Determine whether output is to be printed as the computation progresses.

int z = 50 [static]

Collection Size: default is 50.

Algorithm Development Kit 1.0