Algorithms in C++
Site Map Feedback
		Convert Find Generate Store
	A collection of useful C++ Algorithms

As I create code, I try to make everything as "lumpy" as possible and to make the lumps re-usable. I expect these classes to be of most interest to students who want to watch an algorithm work in their debugger. There are always other ways to achieve the same goal. Although Standard Template Library users will want to keep using the STL, my efforts are, to the best of my knowledge, the fastest and clearest solutions to each problem and not a reproduction of existing libraries. For example, where the STL uses a Red-Black Tree, I chose to create an AVL Tree class and make it able to morph to a linked list and back just because it was easy. My Linked list class should be as fast as writing an inline linked list and has iterators that can move nodes between them, even between different lists. It's fast. Other classes like itow (integer to words - 123 becomes "one hundred and twenty three") are just hard to get right and don't exist in things like STL!

Constants and Basics

The following will help beginners with C++ fundamentals. Most are already defined in C++ systems and so this actual list isn't necessarily useful!

#define _USE_MATH_DEFINES // Exposes  M_PI and M_SQRT2 from math.h
#include <math.h> // For sqrt, hypot, M_PI and M_SQRT2
#define M_SQRT3 1.7320508075688772935274463415059 // add a couple more defines suitable for long double
#define M_GOLD  1.6180339887498948482045868343656 // The Golden Ratio (used in my Graphics section)

// If you are using doubles to hold real-world values you must use a tolerance when comparing two of the values:
bool   Equal      (double a, double b) {return fabs(a-b)<1e-6;} // fabs is in <math.h>
bool   LessThan   (double a, double b) {return a<b-1e-6;}
bool   GreaterThan(double a, double b) {return a>b+1e-6;}

double Degrees2Radians(double a) {return (PI*a)/180;}
double Radians2Degrees(double a) {return (180*a)/PI;}

double Fahrenheit2Celsius(double F) {return 5.0/9.0*(F-32.0);}
double Celsius2Fahrenheit(double C) {return 9.0/5.0* C+32.0 ;}

// A quick example of how to use templated types:
template <typename T> T   min(T a, T b) {return a<b ? a : b;}
template <typename T> T   max(T a, T b) {return a>b ? a : b;}
template <typename T> int sgn(T a)      {return a<0 ? -1 : a>0;}
template <typename T> void Swap(T& a, T& b) {T tmp=b; b=a; a=tmp;}

double abs(double a)                  {return (a<0) ? -a : a;}
long   abs(long a)                    {return (a<0) ? -a : a;}
int    NearestOne(double a)           {return (int)(a+(a<0 ? -0.5 : 0.5));}
double NearestTen(double a)           {return ((int)(a+=5)-((int)a)%10);} // 10*(int)(a/10+0.5);}
double Quad(double a, double b)       {return hypot(a,b);}    // Quadrature: sqrt(a*a+b*b);}
double QuadMi(double a, double b)     {return sqrt(a*a-b*b);} // Quadrature Minus

int GreatestCommonDivisor(int i, int j) {
  while(i!=j)
    if(i>j) i-=j;
    else    j-=i;
  return i;
}

// Tick,Tick Boom! When code must do something just once after a wait (OnTick may be called by a timer or event).
// Used for Tool-tips and other pop-ups, comms time-outs etc.
// Usage example:
// static int Wait=2; // Boom() will be called during the second OnTick() call. To call Boom() again, Wait must be set to non-zero.
// void Cancel () {Wait=0;}
// bool IsWaiting(int* Counter) {return *Counter;}
// void Restart() {Wait=2;} // Called by OnMouseOver for ToolTips. Like a sprug suction-pad toy: keep pushing it down every now and again and it stays down.
// void OnTick () {if(TimeUp(&Wait)) Boom();} // Called by a 1 second timer.
bool TimeUp(int* Counter) {return *Counter ? --*Counter==0 : false;}

// For ASCII characters and null-terminated strings:
char ToUpper(char c) {return c & ~0x20;} // Clear bit 5
char ToLower(char c) {return c |  0x20;} // Set bit 5
void strcpy(char* dst,const char* src) {while(*dst++=*src++);} // Copies up to a null-terminator
int InStr(const char* ptr, int i, char c) {
  for(ptr+=i; *ptr!=c && *ptr++; ++i);
  return (*--ptr ? i : -1);
}

// Use structs or classes to remember to restore states by using the destructor:
struct CWaitCursor {
  CWaitCursor() {SetMouseToHourGlass();}
 ~CWaitCursor() {SetMouseToPointer();}
};
// The only technical difference between a class and struct is that a struct starts with an implied public: and a class with private.
// Since CWaitCursor has no need for encapsulation it is a struct.

class Remember2Free {
  void* Base;
public:
  Remember2Free(void* Base) : Base(Base) {}
 ~Remember2Free() {try{delete[] Base;}catch(...){}} // Never let a destructor throw an exception!
};
// Usage:
bool ArrayThings() {
 char* Array=SomeAllocatingFunction(1234);
 Remember2Free That(Array);
 // do some things
 if(something) return false; // Array will be free'd by the Remember2Free destructor
 // do some more
 return true;
} 

---

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 'AS IS' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

---