Data Structures

Good afternoon everyone,

Today, we're going to discuss a few generic data structures sometimes used in the underpinnings of classic data types.  They include these major collections:

• Arrays
• Bitfields
• Linked Lists

Arrays have a simple setup in most languages and would be defined similar to one of these:

• NumberArray[ Type: NUMBER; Count: 10 ]
• NUMBER NumberArray[ Count: 10 ]
• NUMBER NumberArray[ ]

Arrays must contain (by design of the program, language, compiler, or library) several methods or functional blocks to perform these steps:

• Insertion (At an end or specified position)
• Deletion (At a specified position)
• Retrieval by Position (And you need to confirm if positions start at 0, 1, or use named positions)
• Update by Position (Sometimes implemented by Retreival, Deletion, and then Insertion)
• Length or Count (Used to determine validity of the request, not always available to user)

Array elements can also be arrays making table and matrix operations methods that can be implemented with an understanding of the math behind these systems.  Some early forms of images on computers were implemented with faked tables using long arrays only to be replaced by tabular style arrays in the long run.  The storage of these arrays can be complicated for either the programmer or technician researching memory issues making it a necessity for the conscientious designer to start off with error detection and built in testing.

Bitfields are specialized arrays that access or mimic the binary data of the storage and are often used for flags or systems of simple BOOLEAN equations.  Some implementations will turn an INTEGER between 0 and 2^X-1 into an array of X length.

Linked Lists utilizes a feature called a pointer.  Insertion and deletion is accomplished by holding two copies of the list. Depending on the language you may be able to specify the pointer in a variety of ways, but the general system setup is one of three styles:

• Forward links that require you to have a link to the first element and travel the list to the end to append items.
• Reverse links that start with the last element.
• Multiple links.  This special category in many cases can travel the list very fast, but the storage demands, as implied by the name, multiple quickly.

Regardless of style, Linked Lists generally have the following features:

• Insertion
• Deletion
• Length
• Update
• Retrieval
• Search

In the future, I may select sample implementations from well known tutorial sites for deeper discussions on these structures.

Every Language Needs a Dictionary

We've discussed basic troubleshooting and logic.  However, if we are going beyond attempting to emulate simple mathematics, we need a dictionary to provide meaning to the conversation between the user and the computer.  In many languages these are defined in multiple places including the most useful and dangerous of them all -- libraries not designed and tested by the standards committees.

Suppose you have a library called "Corp_ScreenManagement_v1" which names the accessible functions in the format of csm_XXX where XXX is a numeric code instead of a descriptive tag.

If the library is properly documented you will know the three key points of any particular function: return type, parameter variables, and most importantly its designated use and expected effects or results.  As demonstrated before, the documentation may look like this directly in the source:

//csm_XXX: Prints texts on the screen
//   Parameters: INTEGER xCoord, INTEGER yCoord, ARRAY characters
//   Returns:  BOOLEAN TRUE on Success
BOOLEAN csm_XXX( INTEGER xCoord, INTEGER yCoord, ARRAY characters )
...

The documentation file should, depending on the language provide much the same information, perhaps in an even clearer format than what the original programmer provided.  This allows us to create a series test cases for it so that we can prevent error states when using this function.  If the function doesn't conform to the documentation, we can update the documentation or contact the libraries support staff for corrected files.

Logic is the basis for troubleshooting

Thanks to an understanding of simple logic, we can begin to troubleshoot individual statements. A statement has two parts: the function and the result.  Here is our simple statement:

Result = Add( 3, 4 )

Functions can be complex blocks of statements and contain multiple parameters.  Lets look at a simple function:

Add( value1, value2 )
{
   Result = value1 + value2
}

If left like this, the following questions apply to debuggers and troubleshooters:

1. Is value1 able to use the "+" operation?
2. Is value2 able to use the "+" operation?
3. Are the "+" operations of value1 and value2 compatible?
4. Can the total be assigned to Result?

We know from experience with math that we can answer these question if value1, value2, and Result are numbers, so we may rebuild Add and test it as:

//Documentation notes:

//"NUMBER" is a valid math type with addition as "+" and assignment.

//"IF( x ) THEN y" is defined that when x is TRUE, then y occurs.

//"IF( x ) THEN y ELSE z" as above, also chooses z if x is FALSE.

//"Error( )" is a defined function for reporting errors and halts.

//"Pass( )" is a function indicating success state was expected.

//"Fail( )" is a function indicating failure.

//Description: NumericalAdd is a Basic addition function.

//Expected: NUMBER Result

NUMBER NumericalAdd( NUMBER value1, NUMBER value2 )

{

    IF( value1 NOT NUMBER ) THEN Error( )

    IF( value2 NOT NUMBER ) THEN Error( )

    Result = value1 + value2

}

//Description: TestSuite_NumericalAdd
//If Fail( ) is executed, then NumericalAdd needs to be
//rewritten.
TestSuite_NumericalAdd( )
{

//Result should be 2

IF( NumericalAdd( 1, 1 ) NOT NUMBER ) THEN Fail( ) ELSE Pass( )

//Error should occur for these cases.  Pass is returned for the expected Error:

IF( NumericalAdd( 1, 'a') NOT NUMBER ) THEN Pass( ) ELSE Fail( ) 

IF( NumericalAdd( 'a', 1) NOT NUMBER ) THEN Pass( ) ELSE Fail( ) 

IF( NumericalAdd( 'a', 'b') NOT NUMBER ) THEN Pass( ) ELSE Fail( ) 

}

After executing TestSuite_NumericalAdd, we have completed basic debugging the sample function.

Basic Structure for our discussions

When reviewing programming, we will need a common ground to work with.  The following definitions will apply:

Comments will start with '//'
Parameters, will use all caps for CONSTANTS or begin with a lowercase letter for a variable
Statement blocks will begin with '{' and end with '}'
Types will be defined as all caps for predefined types like 'NUMBER' or preceded with an underscore for a composite type like '_Array'
Optional items will be enclosed in '[' and ']'
Repeated items will be denoted by ', ...'
Function calls will be formatted 'Name( [value, ...] )'

Function definitions will be formated '[TYPE] [returnValue] Name( [[TYPE] value, ...] )' followed by a statement block.

BOOLEAN is a type with TRUE and FALSE defined.

Sample code:

//Function Not returns the opposite of the boolean parameter

//Simple form

BOOLEAN Result Not( BOOLEAN param )

{

    IF( param = TRUE )

    THEN Result = FALSE

    ELSE Result = TRUE

}

//Function And returns TRUE when both parameters are TRUE

//Nested block form

BOOLEAN And( param1, param2 )

{

   IF( Not( Param1 IS BOOLEAN ) )

   THEN Result = FALSE

   ELSE

   {

      IF( NOT( Param2 IS BOOLEAN ) )

      THEN Result = FALSE

      ELSE

      {

         IF( Param1 = Param2 )

         THEN Result = Param1

         ELSE Result = FALSE

      }

   }

   RETURN Result

}

A Logical Start

Before we can start talking about programming, we must understand a simple form of logic.

Everyone who has worked with logic knows that it simply starts with TRUE and FALSE.  When we program, each part of the program generates a result (TRUE) or fails (FALSE).  A sequence of statements or functions may work together and produce multiple results or failures at the same time.  It is for this reason that the standard logic table can direct your efforts in troubleshooting at later stages.  For your reference this table is included below:

Function	Values	TRUE	FALSE
NOT		FALSE	TRUE
AND	TRUE	TRUE	FALSE
	FALSE	FALSE	FALSE
OR	TRUE	TRUE	TRUE
	FALSE	TRUE	FALSE
XOR (Only one is TRUE)	TRUE	FALSE	TRUE
	FALSE	TRUE	FALSE
NOR (Neither is TRUE)	TRUE	FALSE	FALSE
	FALSE	FALSE	TRUE