GENERAL

-------

Use real tabs that equal 4 spaces.

Use typically trailing braces everywhere (if,else, functions, structures, typedefs, class definitions, etc.)

if ( x ) {

}

The else statement starts on the same line asthe last closing brace.

if ( x ) {

} else {
}

Pad parenthesized expressions with spaces

if ( x ) {

}

Instead of

if (x) {

}

And

x = ( y * 0.5f );

Instead of

x = (y * 0.5f);

Use precision specification for floating pointvalues unless there is an explicit need for a double.

float f = 0.5f;

Instead of

float f = 0.5;

And

float f = 1.0f;

Instead of

float f = 1.f;

Function names start with an upper case:

void Function( void );

In multi-word function names each word startswith an upper case:

voidThisFunctionDoesSomething( void );

The standard header for functions is:

/*

====================

FunctionName

Description

====================

*/

Variable names start with a lower casecharacter.

float x;

In multi-word variable names the first wordstarts with a lower case character and each successive word startswith an upper case.

floatmaxDistanceFromPlane;

Typedef names use the same naming convention as variables, howeverthey always end with "_t".

typedef intfileHandle_t;

Struct names use the same naming convention as variables, howeverthey always end with "_t".

struct renderEntity_t;

Enum names use the same naming convention asvariables, however they always end with "_t". The enumconstants use all upper case characters. Multiple words are separatedwith an underscore.

enum contact_t {

CONTACT_NONE,

CONTACT_EDGE,

CONTACT_MODELVERTEX,

CONTACT_TRMVERTEX

};

Names of recursive functions end with "_r"

void WalkBSP_r( intnode );

Defined names use all upper case characters.Multiple words are separated with an underscore.

#define SIDE_FRONT 0

Use ‘const’ as much as possible.

Use:

const int *p; //pointer to const int

int * const p; //const pointer to int

const int * constp; // const pointer to const int

Don’t use:

int const *p;

CLASSES

-------

The standard header for a class is:

/*

===============================================================================

Description

===============================================================================

*/

Class names start with "id" and each successive wordstarts with an upper case.

class idVec3;

Class variables have the same naming conventionas variables.

class idVec3 {

float x;

float y;

float z;

}

Class methods have the same naming conventionas functions.

class idVec3 {

float Length( void )const;

}

Indent the names of class variables and classmethods to make nice columns. The variable type or method return typeis in the first column and the variable name or method name is in thesecond column.

class idVec3 {

float x;

float y;

float z;

float Length( void )const;

const float* ToFloatPtr( void ) const;

}

The * of the pointer is in the first columnbecause it improves readability when considered part of the type.

Ording of class variables and methods should beas follows:

1. list of friend classes

2. public variables

3. public methods

4. protected variables

5. protected methods

6. private variables

7. private methods

This allows the publicinterface to be easily found at the beginning of the class.

Always make class methods ‘const’ when theydo not modify any class variables.

Avoid use of ‘const_cast’. When object isneeded to be modified, but only const versions are accessible, createa function that clearly gives an editable version of the object. This keeps the control of the ‘const-ness’ in the hands of theobject and not the user.

Return ‘const’ objects unless the generalusage of the object is to change its state. For example, mediaobjects like idDecls should be const to a majority of the code, whileidEntity objects tend to have their state modified by a variety ofsystems, and so are ok to leave

non-const.

Function overloading should be avoided in mostcases. For example, instead of:

const idAnim* GetAnim( int index ) const;

const idAnim* GetAnim( const char *name ) const;

const idAnim* GetAnim( float randomDiversity ) const;

Use:

const idAnim* GetAnimByIndex( int index ) const;

const idAnim* GetAnimByName( const char *name ) const;

const idAnim* GetRandomAnim( float randomDiversity ) const;

Explicitly named functions tend to be lessprone to programmer error and inadvertent calls to functions due towrong data types being passed in as arguments. Example:

Anim = GetAnim( 0 );

This could be meant as a call to get arandom animation, but the compiler would interpret it as a call toget one by index.

Overloading functions for the sake of adding‘const’ accessible function is allowable:

class idAnimatedEntity: public idEntity {

idAnimator* GetAnimator( void );

constidAnimator * GetAnimator( void ) const;

};

In this case, a const version of GetAnimatorwas provided in order to allow GetAnimator to be called from constfunctions. Since idAnimatedEntity is normally a non-const object,this is allowable. For a media type, which is normally const,operator overloading should be avoided:

classidDeclMD5 : public idDecl {

constidMD5Anim * GetAnim( animHandle_t handle ) const;

idMD5Anim* GetEditableAnim( animHandle_t handle );

};

id Studio Names

---------------

id<name>Dlg      // dialog class

id<name>Ctrl    // dialog control class

id<name>Frm     // frame window

id<name>View    // view window

id<name>         //any other class

FILE NAMES

---------

Each class should be in a seperate source fileunless it makes sense to group several smaller classes.

The file name should be the same as the name ofthe class without the "id" prefix. (Upper/lower case ispreserved.)

class idWinding;

files:

Winding.cpp

Winding.h

When a class spans across multiple files thesefiles have a name that starts with the name of the class without"id", followed by an underscore and a subsection name.

class idRenderWorld;

files:

RenderWorld_load.cpp

RenderWorld_demo.cpp

RenderWorld_portals.cpp

When a class is a public virtual interface to asubsystem the public interface is implemented in a header file withthe name of the class without "id". The definition of theclass that implements the subsystem is placed in a header file withthe name of the class without "id" and ends with"_local.h". The implementation of the subsystem is placedin a cpp file with the name of the class without "id".

class idRenderWorld;

RenderWorld.h //public virtual idRenderWorld interface

RenderWorld_local.h //definition of class idRenderWorldLocal

RenderWorld.cpp //implementation of idRenderWorldLocal

Binary Search (Sorted array):

Given the range, we want to know how many comparisons it will take to complete a search.

a binary search provides a significant speed increase over a linear search.  For very small numbers of items, the difference isn’t dramatic.

But the more items there are, the bigger the difference.

repeatedly dividing a range (from the first column) in half until it’s too small to divide further.

Given the range, we want to know how many comparisons it will take to complete a search. That is, given r, we want an equation that gives us s. (Logorithm)

s = log₂(r)

you can convert easily to base 2 (log₂)to base 10 by multiplying by 3.322

For example, log₁₀(100) = 2, so log₂ (100) = 2 times 3.322, or 6.644. Rounded up to 7

Big O Notation

how efficient a computer algorithm

1.      Inserting into an Unordered Array: Constant

depend on how many items are in the array. The new item is always placed in the next available position, at a[nElems], and nElemsis then incremented.

We can say the time, T, to insert an item into an unsorted array is a constant K: T = K

2.      Linear Searching: Proportional to N

3.      a linear search of items in an array, the number of comparisons that

must be made to find a specified item is, on the average, half of the total number of

items.

T = K * N / 2

4.      Binary Searching: Proportional to log(N)

T = K * log2(N)

Eliminating the Constant K

Big O notation uses the uppercase letter O, which you can think of as meaning  “order

of.”

In Big O notation, we would say that a linear search takes O(N) time, and a binary

search takes O(log N) time.

Figure 3.5 graphs some Big O relationships between time and number of items. Based on

this graph, we might rate the various Big O values (very subjectively) like this: O(1) is

excellent, O(log N) is good, O(N) is fair, and O(N2) is poor. O(N2) occurs in certain sort-ing algorithms that we’ll look at in Hours 4 and 5.

Hour4: Bubble Sort (sorting)

To Do: Bubble-Sort the Baseball Players

1. Compare two players.

2. If the one on the left is taller, swap them.

3. Move one position right.

You continue down the line this way until you reach the right end. You have by no means finished sorting the kids, but you do know that the tallest kid is on the right.

Efficiency of the Bubble Sort(how fast)

For 10 items this is

9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45  

In general, N items:

(N-1) + (N-2) + (N-3) + ... + 1 = N*(N-1)/2

N*(N-1)/2  is 45 when N is 10.

Thus the algorithm makes about N²/2 comparisons

Because constants don’t count in Big O notation in Big O notation, we can ignore the divisors 2 and 4 and say that the bubble sort runs in O(N2) time. And this is slow

Whenever you see nested loops such as those in the bubble sort, you can suspect that an algorithm runs in O(N²) time. The outer loop executes N times, and the inner loop exe-cutes N (or perhaps N divided by some constant) times for each cycle of the outer loop.

This means you’re doing something approximately N*N or N² times.

HOUR5 The Insertion Sort

 “The Bubble Sort,” is the easiest sort to understand. However, it’s also the least sophisticated. We can improve it at the cost of some additional complexity. It still executes in O(N²) time, but it’s about twice as fast as the bubble sort.

It’s often used as the final stage of more sophisticated sorts, such as quicksort.

Insertion Sort on the Baseball Players

    It’s easier to think about the insertion sort if we begin in the middle of the process, when the team is partly sorted

Partial Sorting(Inserting the Marked Player in the Appropriate Location)

The player where the marker is, whom we’ll call the “marked” player,  and all the players on her right,   is as yet unsorted.

1.       insert the marked player in the appropriate place in the (partially) sorted group.

We take the marked player out of line, and shift the sorted players to make room

When shifting process stop?

when you’ve shifted the last player who is taller than the marked player.

Efficiency of the Insertion Sort

How many comparisons and copies does this algorithm require?

On the first pass, it compares a maximum of one item. On the second pass, it’s a maximum of two items, and so on, up to a maximum of N–1 comparisons on the last pass.

1 + 2 + 3 + ... + N-1 = N*(N-1)/2

However, because on each pass an average of only half of the maximum number of items

are actually compared before the insertion point is found, we can divide by 2, which gives the following equation:

N*(N-1)/4

For data that is already sorted or almost sorted, the insertion sort does much better.

When data is in order, the condition in the while loop is never true, so it becomes a simple statement in the outer loop, which executes N–1 times. In this case the algorithm runs in O(N) time. If the data is almost sorted, insertion sort runs in almost O(N) time, which makes it a simple and efficient way to order a file that is only slightly out of order.

However, for data arranged in inverse sorted order, every possible comparison and shift is

carried out, so the insertion sort runs no faster than the bubble sort.

Q If both the bubble sort and the insertion sort run in O(N²) time, why not use

the bubble sort, which is simpler to program?

A Besides being somewhat faster for random data, the insertion sort is much faster

for data that is only slightly out of order.