Simple implementation of a stack and Quicksort on that stack

.gitignore

Debug*
Stack.vcxproj*

main.cpp

#include <iostream>
using std::cout;
using std::endl;

#include "Stack.h"
#include "StackSort.h"

#include "timer.h"

#include <ctime>
// time()
#include <cstdlib>
// srand(), rand()

int main()
{

   srand(time(0));

   const size_t length = 1<<22;

   timer tim;

   Stack<int> stack;

   cout << "constructing stack of " << length << " random integers... ";
   cout.flush();
   for(size_t i = 0; i < length; ++i){
      stack.push( rand() % 101 );
   }
   cout << "done" << endl;

   cout << "sorting... ";
   cout.flush();

   tim.start();
   quicksort(stack);
   tim.end();

   cout << "done" << endl;
   cout << "took " << (tim.duration() * 1e-6) << " seconds" << endl;
   // ^ have to convert from microseconds

   bool sorted = true;

   size_t length_counter = 0;
   int prev = stack.pop();
   int curr;
   ++length_counter;

   cout << "Verifying sortedness and length of stack... ";
   cout.flush();
   while(sorted && stack.size()){
      curr = stack.pop();
      sorted = sorted && (prev <= curr);
      prev = curr;
      ++length_counter;
   }
   cout << "done" << endl;

   if(sorted){
      if(length_counter == length){
         cout << "SUCCESS! Stack is sorted and the correct length!" << endl;
      }else{
         cout << "FAILURE! Stack is sorted, but the wrong length! (Is " << length_counter << " long, should be " << length << ")" << endl;
      }
   }else{
      if(length_counter == length){
         cout << "FAILURE! Stack ain't sorted (but it is the right length)" << endl;
      }else{
         cout << "FAILURE! Stack ain't sorted, and it's not even the right length! (Is " << length_counter << " long, should be " << length << ")" << endl;
      }
   }

   #ifdef _WIN32
   system("pause");
   #endif

   return 0;
}

Makefile

exe=test
ldflags=-lrt
ccflags=-O3 -std=c++0x -ggdb -Wall -Wextra -Weffc++
cc=g++

.PHONY: all clean

all: $(exe)

clean:
	@rm -f *.o
	@rm -f $(exe)

test: main.cpp timer.o Stack.tpp StackSort.tpp Stack.h StackSort.h
	$(cc) $(ccflags) $< timer.o $(ldflags) -o $@

timer.o: timer.cpp timer.h
	$(cc) $(ccflags) -c $< $(ldflags) -o $@

Stack.cpp

#include "Stack.h"
#include <algorithm> // std::copy

// some useful macros to make things a bit more readable
#define FULL  (data_next == data_end)
#define EMPTY (data_next == data_start)
#define USED_SPACE (data_next - data_start)
#define AVAILABLE_SPACE (data_end - data_start)

template <typename T>
Stack<T>::Stack(size_t size)
   : data_start(new T[size]),
     data_next(data_start),
     data_end(data_start + size)
{

}

#define size 8
template <typename T>
Stack<T>::Stack()
   : data_start(new T[size]),
     data_next(data_start),
     data_end(data_start + size)
{

}
#undef size

template <typename T>
Stack<T>::~Stack(){
   delete [] data_start;
}

template <typename T>
Stack<T>::Stack(const Stack<T> & other){
   size_t otherUsed = other.data_next - other.data_start;
   size_t otherAvailable = other.data_end - other.data_start;

   data_start = new T[ otherAvailable ];
   std::copy(other.data_start, other.data_next, data_start);

   data_next = data_start + otherUsed;
   data_end  = data_start + otherAvailable;
}

template <typename T>
Stack<T> & Stack<T>::operator=(const Stack<T> & other){
   size_t otherUsed = other.data_next - other.data_start;
   size_t otherAvailable = other.data_end - other.data_start;

   data_start = new T[ otherAvailable ];
   std::copy(other.data_start, other.data_next, data_start);

   data_next = data_start + otherUsed;
   data_end  = data_start + otherAvailable;
}

template <typename T>
void Stack<T>::_realloc(){
   /*
    * reallocate the data to a new region that's twice the length of
    * the currently used data. In the case where the stack is full, this
    * doubles the size of the available memory.
    *
    * In the case where it's 3/4 empty, this halves the size of the
    * available memory
    *
    * */
   size_t _size = USED_SPACE;
   T * new_data = new T[ 2 * _size ];
   std::copy(data_start, data_next, new_data);
   delete [] data_start;
   data_start = new_data;
   data_next = new_data + _size;
   data_end = new_data + (2*_size);
}

template <typename T>
void Stack<T>::push(const T & element){
   if( FULL ){
      _realloc();
   }
   *data_next = element;
   ++data_next;
}

template <typename T>
T Stack<T>::pop(){
   if( !EMPTY ){
      if( USED_SPACE <= (AVAILABLE_SPACE/4) ){
         _realloc();
      }
      return *(--data_next);
   }else{
      throw EmptyStackException();
   }
}

template <typename T>
const T & Stack<T>::peek(){
   if( !EMPTY )
      return *(data_next - 1);
   else
      throw EmptyStackException();
}

template <typename T>
size_t Stack<T>::size(){
   return USED_SPACE;
}

// get rid of the macros we defined
// (don't need them anymore, and they no longer make sense after this point)
#undef FULL
#undef EMPTY
#undef USED_SPACE
#undef AVAILABLE_SPACE

Stack.h

#ifndef STACK_H
#define STACK_H

#include <cstddef> // size_t

template <typename T>
class Stack {
   private:
      T * data_start;
      T * data_next;
      T * data_end;

      void _realloc();

   public:

      class EmptyStackException : std::exception{
         public:
         virtual const char * what() const throw() {
            return "Tried to pop or peek an empty stack.";
         }
      };

      Stack(size_t size);
      Stack();
     ~Stack();

      Stack(const Stack &);
      Stack & operator= (const Stack &);

      void push(const T & element);
      T pop();
      const T & peek();

      size_t size();
};

#include "Stack.cpp"

#endif

StackSort.cpp

#include <functional>

template <typename T, typename Comparator>
void quicksort(Stack<T> & stack, Comparator sortsBefore, bool reversed){

   if (stack.size() < 2) return; // base case 

   // We make some guesses about the amount of elements that will be in
   // each of the partitions. These should be correct in the average case
   // and save us a few _realloc()s
   Stack<T> before = Stack<T>(stack.size()/2);
   Stack<T> equal  = Stack<T>(2);
   Stack<T> after  = Stack<T>(stack.size()/2);

   equal.push(stack.pop()); // this is our pivot value

   // divide the stack into three stacks, One containing every
   // value less than the pivot, one with every value greater than
   // the pivot, and one with all the values equal to the pivot
   while(stack.size()){
      if( sortsBefore(stack.peek(), equal.peek()) ){
         before.push(stack.pop());
      }else if ( sortsBefore(equal.peek(), stack.peek()) ){
         after.push(stack.pop());
      }else{
         equal.push(stack.pop());
      }
   }

   // sort the two partitions, but make sure to sort them in the
   // opposite order, because when we pop from them, they get reversed
   quicksort(before, sortsBefore, !reversed);
   quicksort(after,  sortsBefore, !reversed);

   // pop from the stacks back into the original stack, which is now sorted.
   // Again, We have to pay attention to the sort order, as this pop-copying
   // reverses it
   if(reversed){
      while(before.size()) stack.push(before.pop());
      while(equal.size()) stack.push(equal.pop());
      while(after.size()) stack.push(after.pop());
   }else{
      while(after.size()) stack.push(after.pop());
      while(equal.size()) stack.push(equal.pop());
      while(before.size()) stack.push(before.pop());
   }
}

// TODO - is this actually the right way to do this?
template <typename T>
void quicksort(Stack<T> & stack){
   quicksort(stack, std::less<T>());
}

StackSort.h

#ifndef STACK_SORT_H
#define STACK_SORT_H

#include "Stack.h"

template <typename T, typename Comparator>
void quicksort(Stack<T> & stack, Comparator sortsBefore, bool reversed = false);

template <typename T>
void quicksort(Stack<T> & stack);

#include "StackSort.cpp"

#endif

timer.cpp

/*
 *  A class that provides a simple timer
 *  Works in Windows and Linux, resolution is hardware dependant
 *
 *
 *  Copyleft Gordon Bailey 2012 - All wrongs reserved
 *
 * */

#include "timer.h"

#ifdef _WIN32

#include <cstdlib>

#include <iostream>
using std::endl;
using std::cerr;

timer::timer() : ready(false) {
   bool success = QueryPerformanceFrequency(&counter_freq);
   if(!success){
      cerr << "Error, QueryPerformanceFrequency failed." << endl;
      system("pause");
      exit(EXIT_FAILURE);
   }
}

void timer::start() {
   ready = false;
   bool success = QueryPerformanceCounter(&start_time);
   if(!success){
      cerr << "Error, QueryPerformanceCounter failed." << endl;
      system("pause");
      exit(EXIT_FAILURE);
   }
}

void timer::end(){
   ready = true;
   bool success = QueryPerformanceCounter(&end_time);
   if(!success){
      cerr << "Error, QueryPerformanceCounter failed." << endl;
      system("pause");
      exit(EXIT_FAILURE);
   }
}

// there is probably some unnecessary typecasting here, but better safe than sorry
double timer::duration(){
   if (ready){
	   return 1e6 * (((double)(end_time.QuadPart - start_time.QuadPart)) / ((double)counter_freq.QuadPart));
   }else{
      return 0;
   }
}

#else

timer::timer() : ready(false) {}

void timer::start() {
   ready = false;
   clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start_time);
}

void timer::end(){
   clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end_time);
   ready = true;
}

double timer::duration(){
   if (ready){
      return 1e6 * (difftime(end_time.tv_sec, start_time.tv_sec) + (1e-9 * (double)(end_time.tv_nsec - start_time.tv_nsec)));
   }else{
      return 0;
   }
}

#endif

timer.h

#ifndef TIMER_H
#define TIMER_H

#ifdef _WIN32
#include <Windows.h>
#else
#include <time.h>
#endif

class timer{

#ifdef _WIN32
      LARGE_INTEGER start_time;
      LARGE_INTEGER end_time;
      LARGE_INTEGER counter_freq;
#else
      struct timespec start_time;
      struct timespec end_time;
#endif

      bool ready;
   public:
      void start();
      void end();
      double duration();
      timer();
};

#endif