1,120
edits
Changes
From Genome Analysis Wiki
Jump to navigationJump to searchBiostatistics 615/815 Fall 2011 (view source)
Revision as of 12:34, 4 February 2011
, 12:34, 4 February 2011→Problem Sets
std::cout << "std::set (Search) " << duration << std::endl;
std::cout << "std::set (Search) " << duration << std::endl;
}
}
#include <iostream>
#define DEFAULT_ALLOC 1024
template <class T> // template supporting a generic type
class mySortedArray {
protected: // member variables hidden from outside
T *data; // array of the genetic type
int size; // number of elements in the container
int nalloc; // # of objects allocated in the memory
mySortedArray(mySortedArray& a) {};
int search(const T& x, int begin, int end);
public: // abstract interface visible to outside
mySortedArray(); // default constructor
~mySortedArray(); // desctructor
void insert(const T& x); // insert an element x
int search(const T& x); // search for an element x and return its location
bool remove(const T& x); // delete a particular element
};
template <class T>
mySortedArray<T>::mySortedArray() { // default constructor
size = 0; // array do not have element initially
nalloc = DEFAULT_ALLOC;
data = new T[nalloc]; // allocate default # of objects in memory
}
template <class T>
mySortedArray<T>::~mySortedArray() { // destructor
if ( data != NULL ) {
delete [] data; // delete the allocated memory before destorying
} // the object. otherwise, memory leak happens
}
template <class T>
void mySortedArray<T>::insert(const T& x) {
if ( size >= nalloc ) { // if container has more elements than allocated
T* newdata = new T[nalloc*2]; // make an array at doubled size
for(int i=0; i < nalloc; ++i) {
newdata[i] = data[i]; // copy the contents of array
}
delete [] data; // delete the original array
data = newdata; // and reassign data ptr
}
int i;
for(i=size-1; (i >= 0) && (data[i] > x); --i) {
data[i+1] = data[i]; // insert the list into right position
}
data[i+1] = x;
++size; // increase the size
}
template <class T>
int mySortedArray<T>::search(const T& x) {
return search(x, 0, size-1);
}
template <class T>
int mySortedArray<T>::search(const T& x, int begin, int end) {
if ( begin > end ) {
return -1;
}
else {
int mid = (begin+end)/2;
if ( data[mid] == x ) {
return mid;
}
else if ( data[mid] < x ) {
return search(x, mid+1, end);
}
else {
return search(x, begin, mid);
}
}
}
template <class T>
bool mySortedArray<T>::remove(const T& x) {
int i = search(x); // try to find the element
if ( i >= 0 ) { // if found
for(int j=i; j < size-1; ++j) {
data[i] = data[i+1]; // shift all the elements by one
}
--size; // and reduce the array size
return true; // successfully removed the value
}
else {
return false; // cannot find the value to remove
}
}
== Office Hours ==
== Office Hours ==
