.. highlight:: c++

Libraries of Code
=================

Complex Numbers
---------------

suppose you want to make a library of functions for doing arithmetic with
`complex numbers <http://en.wikipedia.org/wiki/Complex_number>`_

you don't need to understand complex numbers in any detail to understand these
notes

but it is useful to know that a complex number is usually written in the a +
bi, where a and b are real numbers, and i is the square root of -1

a is called the real part of a + bi, and b is called the imaginary part

lets assume you plan to use this library in many different programs

and maybe even share it with other people

in these notes we will see how to structure a library of code so that it can
be used with other programs

note: C/C++ already have a standard library of complex number functions, so in
real-life you would usually just that


Complex Numbers
---------------

lets agree to represent complex numbers with this struct

::

	struct Complex {
		double real;  // real part of the number
		double imag;  // imaginary part of the number
	};

we'll need functions for printing complex numbers

and for doing basic arithmetic, such as addition and multiplication

we'll also include functions for calculating conjugates and magnitudes (you
can read about what these functions are on `the Wikipedia complex numbers page
<http://en.wikipedia.org/wiki/Complex_number>`_)


Complex Numbers
---------------

here's a first draft of the code as a single program

notice that we use operator-overloading to define operations using their usual
mathematical symbols

operator-overloading is a feature of C++, but it is not in C

::

	// complex1.cpp

	//
	// This is the beginning of a simple library to help with complex numbers.
	//

	#include "cmpt_error.h"
	#include <iostream>
	#include <cmath>

	using namespace std;

	struct Complex {
		double real;  // real part of the number
		double imag;  // imaginary part of the number
	}; 

	// I is the square root of -1
	const Complex I{0, -1};

	void print_full(const Complex& c) {
		cout << c.real << " + " << c.imag << "i"; 
	}

	void println_full(const Complex& c) {
		print_full(c);
		cout << "\n";
	}

	// Fancier print function that tries to print complex numbers in the style
	// people like.
	void print(const Complex& c) {
		if (c.real == 0.0 && c.imag == 0.0) {
			cout << "0";
		} else if (c.real == 0.0) {
			if (c.imag == -1.0) {
				cout << "-i";
			} else if (c.imag == 1.0) {
				cout << "i";
			} else {
				cout << c.imag << "i";
			}
		} else if (c.imag == 0.0) {
			cout << c.real;
		} else if (c.imag == -1.0) {
			cout << c.real << " - i";
		} else if (c.imag == 1.0) {
			cout << c.real << " + i";
		} else if (c.imag < 0) {
			cout << c.real << " - " << -c.imag << "i"; 
		} else {
			cout << c.real << " + " << c.imag << "i";
		}
	}

	void println(const Complex& c) {
		print(c);
		cout << "\n";
	}

	bool operator==(const Complex& a, const Complex& b) {
		return (a.real == b.real) && (a.imag == b.imag);
	}

	bool operator!=(const Complex& a, const Complex& b) {
		return !(a == b);
	}

	Complex conjugate(const Complex& a) {
		return Complex{a.real, -a.imag};
	}

	double magnitude(const Complex& a) {
		return sqrt(a.real * a.real + a.imag * a.imag);
	}

	Complex operator+(const Complex& a, const Complex& b) {
		double real = a.real + b.real;
		double imag = a.imag + b.imag;
		Complex result{real, imag};
		return result;
	}

	Complex operator-(const Complex& a, const Complex& b) {
		double real = a.real - b.real;
		double imag = a.imag - b.imag;
		Complex result{real, imag};
		return result;
	}

	// (a + bi)(c + di) = (ac - bd) + (bc + ad)i
	Complex operator*(const Complex& w, const Complex& z) {
		double a = w.real;
		double b = w.imag;
		double c = z.real;
		double d = z.imag;
		double real = a * c - b * d;
		double imag = b * c + a * d;
		Complex result{real, imag};
		return result;
	}

	// (a + bi)(c + di) = (ac - bd) + (bc + ad)i
	Complex operator/(const Complex& w, const Complex& z) {
		if (z.real == 0.0 && z.imag == 0.0) error("can't divide by 0");
		double a = w.real;
		double b = w.imag;
		double c = z.real;
		double d = z.imag;
		double real = (a * c + b * d) / (c * c + d * d);
		double imag = (b * c - a * d) / (c * c + d * d);
		Complex result{real, imag};
		return result;
	}

	int main() {
		Complex a{2, 3};
		Complex b{-1, -4};
		println_full(a);
		println_full(b);
		println_full(a + b);
		println_full(a - b);
		println_full(a * b);
		println_full(I * I);
		println_full(a / b);
		cout << "---------\n";
		println(a);
		println(b);
		println(a + b);
		println(a - b);
		println(a * b);
		println(I * I);
		println(a / b);
	} // main


Compiling the Library
---------------------

to make the complex number functions easy to re-use, think about how we would
like it to work when its done

ideally, we would want to write code like this

::

	#include "cmpt_error.h"
	#include <iostream>
	#include <cmath>
	#include "complex.h"

	using namespace std;

	int main() {
		Complex a{2, 3};
		Complex b{-1, -4};
		// ...
	} // main

in other words, we include complex.h just like how we include any other header
file


Header Files
------------

a .h file is a header file, and it usually contains **declarations** of
functions, but **not** their definitions

for example

::

	// this is a declaration of operator==
	// a function can be declared any number of times
	bool operator==(const Complex& a, const Complex& b);

	// this is the definition of operator==
	// a function can only be defined once
	bool operator==(const Complex& a, const Complex& b) {
		return (a.real == b.real) && (a.imag == b.imag);
	}

the distinction between a declaration and a definition can be tricky at first

but it's important in C/C++ programming

a typical .h header is filled mainly with declarations

the corresponding definitions (i.e. implementations) are in a separate file


Header Files
------------

so we will do the usual C/C++ thing of splitting our library of functions into
separate files

complex.h will have the declarations of all the functions (but no function
implementations)

complex.cpp will have the definitions of all the functions (i.e. the
implementations)

programmers who want to use our complex number functions should only need to
look at the .h file

so that's where we will put the documentation for how to use the functions

as long as our implementation is correct and efficient, most programmers
probably don't need (or want!) to look at the precise implementation details


Header Files
------------

another advantage of splitting our library into complex.h and complex.cpp is
that we can pre-compile complex.cpp

that way, programmers using our code don't need to compile complex.cpp every
time they compile their own program

instead, they link-in the pre-compiled complex.cpp code

compiling large C/C++ programs turns out to be quite time-consuming, and so
you generally want to pre-compile code whenever possible


A Header File and an Implementation
-----------------------------------

lets split our complex number library into two files

complex.h: the headers of all the functions, i.e. their declarations only

complex.cpp: the implementation of all the functions in the header

::

	// complex.h

	// declare Complex to be a struct
	// this is the definition of Complex
	struct Complex {
		double real;  // real part of the number
		double imag;  // imaginary part of the number
	};

	// I is the square root of -1
	// The extern keyword means that this a declaration of
	// I, and that its definition is somewhere else.
	extern const Complex I;

	// Full print functions prints the real and imaginary parts of a complex
	// number in every case. This is useful for debugging, or when you want to see
	// both parts of a complex number.
	void print_full(const Complex& a);
	void println_full(const Complex& a);

	// These are fancy print functions that print complex numbers in a more
	// friendly, human-readable way. For example, 4 + -1i would be printed
	// as 4 - i.
	void print(const Complex& a);
	void println(const Complex& a);

	// Equality and inequality. 
	bool operator==(const Complex& a, const Complex& b);
	bool operator!=(const Complex& a, const Complex& b);

	// Some common complex number operations.
	Complex conjugate(const Complex& a);
	double magnitude(const Complex& a);

	// Basic arithmetic operations.
	Complex operator+(const Complex& a, const Complex& b);
	Complex operator-(const Complex& a, const Complex& b); // binary minus
	Complex operator-(const Complex& a); // unary minus, e.g. -a
	Complex operator*(const Complex& a, const Complex& b);
	Complex operator/(const Complex& a, const Complex& b);

here is complex.cpp

::

	// complex.cpp

	#include "cmpt_error.h"
	#include <iostream>
	#include <cmath>
	#include "complex.h"

	using namespace std;

	// I is the square root of -1
	const Complex I{0, -1};

	void print_full(const Complex& a) {
		cout << a.real << " + " << a.imag << "i"; 
	}

	void println_full(const Complex& a) {
		print_full(a);
		cout << "\n";
	}

	// Fancier print function that tries to print complex numbers in the style
	// people like.
	void print(const Complex& a) {
		if (a.real == 0.0 && a.imag == 0.0) {
			cout << "0";
		} else if (a.real == 0.0) {
			if (a.imag == -1.0) {
				cout << "-i";
			} else if (a.imag == 1.0) {
				cout << "i";
			} else {
				cout << a.imag << "i";
			}
		} else if (a.imag == 0.0) {
			cout << a.real;
		} else if (a.imag == -1.0) {
			cout << a.real << " - i";
		} else if (a.imag == 1.0) {
			cout << a.real << " + i";
		} else if (a.imag < 0) {
			cout << a.real << " - " << -a.imag << "i"; 
		} else {
			cout << a.real << " + " << a.imag << "i";
		}
	}

	void println(const Complex& c) {
		print(c);
		cout << "\n";
	}

	bool operator==(const Complex& a, const Complex& b) {
		return (a.real == b.real) && (a.imag == b.imag);
	}

	bool operator!=(const Complex& a, const Complex& b) {
		return !(a == b);
	}

	Complex conjugate(const Complex& a) {
		return Complex{a.real, -a.imag};
	}

	double magnitude(const Complex& a) {
		return sqrt(a.real * a.real + a.imag * a.imag);
	}

	Complex operator+(const Complex& a, const Complex& b) {
		double real = a.real + b.real;
		double imag = a.imag + b.imag;
		Complex result{real, imag};
		return result;
	}

	Complex operator-(const Complex& a, const Complex& b) {
		double real = a.real - b.real;
		double imag = a.imag - b.imag;
		Complex result{real, imag};
		return result;
	}

	Complex operator-(const Complex& a) {
		double real = -a.real;
		double imag = -a.imag;
		Complex result{real, imag};
		return result;
	}

	// (a + bi)(c + di) = (ac - bd) + (bc + ad)i
	Complex operator*(const Complex& w, const Complex& z) {
		double a = w.real;
		double b = w.imag;
		double c = z.real;
		double d = z.imag;
		double real = a * c - b * d;
		double imag = b * c + a * d;
		Complex result{real, imag};
		return result;
	}

	Complex operator/(const Complex& w, const Complex& z) {
		if (z.real == 0.0 && z.imag == 0.0) error("can't divide by 0");
		double a = w.real;
		double b = w.imag;
		double c = z.real;
		double d = z.imag;
		double real = (a * c + b * d) / (c * c + d * d);
		double imag = (b * c - a * d) / (c * c + d * d);
		Complex result{real, imag};
		return result;
	}


and here is complex_test.cpp (this is the only file with a ``main`` function)

::

	// complex_test.cpp

	#include "cmpt_error.h"
	#include <iostream>
	#include <cmath>
	#include "complex.h"

	using namespace std;

	int main() {
		Complex a{2, 3};
		Complex b{-1, -4};
		println_full(a);
		println_full(b);
		println_full(a + b);
		println_full(a - b);
		println_full(a * b);
		println_full(I * I);
		println_full(a / b);
		cout << "---------\n";
		println(a);
		println(b);
		println(a + b);
		println(a - b);
		println(a * b);
		println(I * I);
		println(a / b);
		println((a + b) / -(a + b));
	} // main


Using complex.cpp
-----------------

to compile a file with ``g++``, use the ``-c`` option

::
	
	$ g++ -c complex.cpp -std=c++0x -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g

this creates a file called ``complex.o`` that contains object code

as long as we don't change ``complex.cpp``, we don't need to do this
compilation step again

now we compile ``complex_test.cpp``

::

	$ g++ -c complex_test.cpp -std=c++0x -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g

this creates the file ``complex_test.o``

finally, to create the executable file ``complex_test`` we link ``complex.o``
and ``complex_test.o`` together with the ``-o`` option

::

	$ g++ -o complex_test complex_test.o complex.o -std=c++0x -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g

now we can run our program

	$ ./complex_test


Compiling and Linking
---------------------

using libraries requires multiple compile steps

that's because each ``.cpp`` file must be compiled

big problems can have hundreds, or more, ``.cpp`` files

the output of a compile step is a ``.o`` file

an executable file is composed of multiple ``.o`` files

the process of combining ``.o`` files is called **linking**


Using a makefile
----------------

as you've seen above, it can get tedious to type all these compiling/linking
commands

it can also get confusing, i.e. you don't want to re-compile files if
necessary (to speed of compiling time), but you need to be sure that all the
``.o`` files are compiled from the most recent ``.cpp`` files

essentially, every time you change a ``.cpp`` file you to re-compile it so the
``.o`` file is up to date

but you should never re-compile a file that hasn't changed

keeping track of this in large programs can be very hard!

so there are software tools designed to help you with this


Using a makefile
----------------

one of the oldest and most popular is ``make``

``make`` is a program that reads **make files**

and make files contains rules and commands for how to compile and link
programs

a very useful feature of make is that it can ensure that a file is re-compiled
just when its corresponding ``.cpp`` file has changed

this one little trick can significantly speed up compile times


Using a makefile
----------------

here's a very simple example of a makefile

::

	CPPFLAGS = -std=c++0x -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g

	all:
		g++ -c complex.cpp $(CPPFLAGS)
		g++ -c complex_test.cpp $(CPPFLAGS)
		g++ -o complex_test complex_test.o complex.o $(CPPFLAGS)


``make`` expects this to be in a file named ``makefile`` or ``Makefile``

to run it, just type ``make``

::

	$ make
	g++ -c complex.cpp -std=c++0x -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g
	g++ -c complex_test.cpp -std=c++0x -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g
	g++ -o complex_test complex_test.o complex.o -std=c++0x -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g

``CPPFLAGS`` is a makefile variable that contains all the g++ flags

the g++ commands underneath ``all:`` must be indented using a tab, not a space

that's one of the (many!) annoying details of ``make``: **you must indent
makefiles with tabs, not spaces**


Using a makefile
----------------

lets improve the makefile a little bit

it should not re-compile ``complex.cpp`` unless ``complex.cpp`` has changed
sometime after the last time it was compiled

similarly, there's no need to re-compile ``complex_test.cpp`` unless either it
or ``complex.cpp`` has changed

::

	CPPFLAGS = -std=c++0x -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g

	# typing just "make" will cause make to try to build complex_test
	all: complex_test

	complex_test: complex.o complex_test.o
		g++ -o complex_test complex_test.o complex.o $(CPPFLAGS)

	complex_test.o: complex_test.cpp complex.cpp
		g++ -c complex_test.cpp $(CPPFLAGS)

	complex.o: complex.cpp 
		g++ -c complex.cpp $(CPPFLAGS)

	# to run this, type "make clean"
	clean:
		rm -f complex.o complex_test.o complex_test

the makefile now consists of multiple rules

look at this rule

::

	complex_test: complex.o complex_test.o
		g++ -o complex_test complex_test.o complex.o $(CPPFLAGS)

the g++ command here is only run if necessary, i.e. it is only run if
``complex_test`` does not already exist, or if ``complex.o`` or
``complex_test.o`` is not up to date (according to their rules below)

look at this rule for making the file ``complex_test.o``

::

	complex_test.o: complex_test.cpp complex.cpp
		g++ -c complex_test.cpp $(CPPFLAGS)

it says that you only need to compile ``complex_test.cpp`` if either
``complex_test.o`` doesn't exist, or if ``complex_test.cpp`` or
``complex.cpp`` has changed since the last time ``complex_test.o`` was created

Using a makefile
----------------

makefiles are written in their own special-purpose programming language

and it's not an especially nice or easy to use language (many alternatives to
make have been proposed and are in use --- but it turns out to be trickier
than you might first think to solve all the problems make solves)

but it works well, even for very large programs, e.g. the Linux kernel is
compiled using makefiles

learning to write makefiles takes time

when starting out, it's wise to just copy existing makefiles and change them
as needed to do what you want

then you can you look up how to use other make features and commands when you
need them