CAB201 – Programming Principles - Collections

Collections

• A collection is a type that contains multiple variables/values, making it easier to manage and manipulate data.
  • This includes adding, removing, finding, and inserting data.

Types of Collections

• Arrays
  • Array
  • Parallel arrays
  • Multidimensional arrays
• Collections Framework
  • List
  • SortedList
  • Dictionary
  • Queue
  • Stack
• To use these, import collections near the top of the .cs file (before namespace).

Arrays

• An array is a collection of elements.

Declaring Arrays

• Syntax: TYPE[] IDENTIFIER;
  • TYPE: Data type of the elements in the array.
  • IDENTIFIER: Name of the array.
• Arrays are a collection of the same data type.
• They are referenced using one identifier.
• Uses a plural identifier (e.g., names, ages, sales).
• Examples:
  • string[] stringArray;
  • int[] intArray;
  • double[] doubleArray;
  • bool[] boolArray;

Creating Arrays

• Syntax:
  • TYPE[] IDENTIFIER = new TYPE[length];
  • TYPE[] IDENTIFIER; IDENTIFIER = new TYPE[length];
• Range of length is 0 – Int32.MaxLength (approximately 2 Billion).
• Example:
  • const int numOfMonths = 12;
  • int[] monthlySales = new int[numOfMonths];
  • Console.WriteLine(monthlySales);

Memory Allocation

• The entire array is stored as a block in memory.
• Size = Length * Type size
• Example:
  • double[20] sales = new double[20];
  • Double (8 bits) * Length (20) = 160
  • Position 20000 – 20152

Default Values

• Numeric fields are set to 0.
• Characters are set to "\u0000".
• Booleans are set to false.
• Strings are set to null.

Task Example

• Gordon owns a bakery with five employees, and wants to print the number of hours each worked.
  • Length = 5
  • Values = 30, 50, 20, 15, 40
  • Employees: Jenny (30 hours), Simon (50 hours), Yue (20 hours), Felipe (15 hours), Nala (40 hours).

Initializing Elements

• When declared:
  • int[] hoursArray1 = {30, 50, 20, 15, 40 };
  • int[] hoursArray2 = new int[ ] {30, 50, 20, 15, 40 };
  • int[] hoursArray3 = new int[5] {30, 50, 20, 15, 40 };
• Element by element:
  • int[] hoursArray4 = new int[5];
  • hoursArray4[0] = 30; hoursArray4[1] = 50;
  • hoursArray4[2] = 20; hoursArray4[3] = 15;
  • hoursArray4[4] = 40;

Take Home

• Arrays are a very common collection type.
• They store memory values in a block.
• Arrays use an index to access and assign values.

Arrays and Iterations

• Iterate through arrays using:
  • for loop
  • while loop
  • do while loop
  • foreach loop

Iterations Task

• Gordon wants to print the hours each employee worked using iterations.
• Length = 5, Values = 30, 50, 20, 15, 40.

Iterating

• Printing each element using indices:

csharp
int[] hoursArray = {30, 50, 20, 15, 40};
Console.WriteLine(hoursArray[0]);
Console.WriteLine(hoursArray[1]);
Console.WriteLine(hoursArray[2]);
Console.WriteLine(hoursArray[3]);
Console.WriteLine(hoursArray[4]);
Console.WriteLine(hoursArray[5]); // Will cause a run time error

For Loop

int[] hoursArray = { 30, 50, 20, 15, 40 };
for (int i = 0; i < 5; i++)
{
    Console.WriteLine(hoursArray[i]);
}

for (int i = 0; i < hoursArray.Length; i++)
{
    Console.WriteLine(hoursArray[i]);
}

• Using Length limits the threshold to the number of elements in the array.
• Example of defensive programming, stopping errors from accruing.

While Loops

int i = 0;
while(i < hoursArray.Length)
{
    Console.WriteLine(hoursArray[i]);
    i++;
}

int i = 0;
do
{
    Console.WriteLine(hoursArray[i]);
    i++;
} while (i < hoursArray.Length); // problem for an empty array

Foreach Loop

• Syntax:

foreach (CONTROL_TYPE CONTROL in COLLECTION)
{
    STATEMENTS;
}

CONTROL_TYPE – The type of the control statement
CONTROL – The control variable
COLLECTION – The collection

foreach(int hour in hoursArray)
{
    Console.WriteLine(hour);
}

Foreach Loop Disadvantages

• Must process the whole collection, not a subset.
  • Cannot do:

for (int i = 0; i < 2; i++)
{
    Console.WriteLine(hoursArray[i]);
}

• Can only use to access, not change elements.
  • This will not reassign:

foreach (int hour in hoursArray)
{
    hour = 2 * hour; // can not reassign
}

for (int i = 0; i < hoursArray.Length; i++)
{
    hoursArray[i] = hoursArray[i];
    Console.WriteLine(hoursArray[i]);
}

Test Cases

• Plus all the testing for the element values (e.g. negative values for ages, hours etc.).

Comparison of Loops

• What to use?
  • Just accessing/Whole array – foreach
  • Changing elements/subset - for

Array Methods

• Copy, Sort, Reverse

Copying Arrays

• Assigning by value:

int x = 42;
int y = x;
Console.WriteLine("x is " + x + " y is " + y); // x is 42 y is 42

y = y * 10;
Console.WriteLine("x is " + x + " y is " + y); // x is 42 y is 420

• Assigning by reference:

int[] hoursArrayX = { 30, 50, 20, 15, 40 };
int[] hoursArrayY = hoursArrayX;
int LENGTH = 5;

for (int i = 0; i < LENGTH; i++)
{
    Console.WriteLine("At index " + i + " x is " + hoursArrayX[i] + " and y is " + hoursArrayY[i]);
}

// At index 0 x is 30 and y is 30
// At index 1 x is 50 and y is 50
// At index 2 x is 20 and y is 20
// At index 3 x is 15 and y is 15
// At index 4 x is 40 and y is 40

for (int i = 0; i < LENGTH; i++)
{
    hoursArrayY[i] = hoursArrayY[i] * 10;
}

for (int i = 0; i < LENGTH; i++)
{
    Console.WriteLine("At index " + i + " x is " + hoursArrayX[i] + " and y is " + hoursArrayY[i]);
}

// At index 0 x is 300 and y is 300
// At index 1 x is 500 and y is 500
// At index 2 x is 200 and y is 200
// At index 3 x is 150 and y is 150
// At index 4 x is 400 and y is 400

• Using the Array.Copy method:

void Array.Copy(TYPE SOURCE, TYPE[] DESTINATION, int LENGTH)

TYPE – The element’s type
SOURCE – The source array
DESTINATION – the destination array
LENGTH – The length array

int[] hoursArrayX = { 30, 50, 20, 15, 40 };
int[] hoursArrayY = new int[hoursArrayX.Length];

Array.Copy(hoursArrayX, hoursArrayY, hoursArrayX.Length);

for (int i = 0; i < LENGTH; i++)
{
    Console.WriteLine("At index " + i + " x is " + hoursArrayX[i] + " and y is " + hoursArrayY[i]);
}

Console.WriteLine();

for (int i = 0; i < LENGTH; i++)
{
    hoursArrayY[i] = hoursArrayY[i] * 10;
}

for (int i = 0; i < LENGTH; i++)
{
    Console.WriteLine("At index " + i + " x is " + hoursArrayX[i] + " and y is " + hoursArrayY[i]);
}

// At index 0 x is 30 and y is 30
// At index 1 x is 50 and y is 50
// At index 2 x is 20 and y is 20
// At index 3 x is 15 and y is 15
// At index 4 x is 40 and y is 40

// At index 0 x is 30 and y is 300
// At index 1 x is 50 and y is 500
// At index 2 x is 20 and y is 200
// At index 3 x is 15 and y is 150
// At index 4 x is 40 and y is 400

Sort

• void Array.Sort(ELEMENT_TYPE ARRAY)

int[] hoursArray1 = { 30, 50, 20, 15, 40 };

for (int i = 0; i < hoursArray1.Length; i++)
{
    Console.WriteLine("At index " + i + " x is " + hoursArray1[i]);
}
// At index 0 x is 30
// At index 1 x is 50
// At index 2 x is 20
// At index 3 x is 15
// At index 4 x is 40

Array.Sort(hoursArray1);
Console.WriteLine();

for (int i = 0; i < hoursArray1.Length; i++)
{
    Console.WriteLine("At index " + i + " x is " + hoursArray1[i]);
}

//At index 0 x is 15
//At index 1 x is 20
//At index 2 x is 30
//At index 3 x is 40
//At index 4 x is 50

Sort - Test Cases

Reverse

• void Array.Reverse(ARRAY)

int[] hoursArray2 = { 30, 50, 20, 15, 40 };

for (int i = 0; i < hoursArray2.Length; i++)
{
    Console.WriteLine("At index " + i + " x is " + hoursArray2[i]);
}

//At index 0 x is 30
//At index 1 x is 50
//At index 2 x is 20
//At index 3 x is 15
//At index 4 x is 40

Array.Sort(hoursArray2);
Array.Reverse(hoursArray2);
Console.WriteLine();

for (int i = 0; i < hoursArray2.Length; i++)
{
    Console.WriteLine("At index " + i + " x is " + hoursArray2[i]);
}

//At index 0 x is 50
//At index 1 x is 40
//At index 2 x is 30
//At index 3 x is 20
//At index 4 x is 15

Reverse - Test Cases

Take Home

• There are many array methods.
• Some methods need to be executed in order (Sort, Reverse).

Searching Arrays

• BinarySearch

Task

• Marie wants to give a tip to one of Gordon’s employees but only knows the names ‘Simon’ or ‘Sam’.
• Steps:
  1. Initialize an array of names.
  2. Sort the array.
  3. Perform a Binary search for both names.
  4. Report if either person is an employee.

Search Task

static void Main(string[] args)
{
    string[] namesArray = { "Jenny", "Simon", "Yue", "Felipe", "Nala" };

    foreach (string name in namesArray)
    {
        Console.WriteLine(name);
    }

    Array.Sort(namesArray);
    Console.WriteLine();

    foreach (string name in namesArray)
    {
        Console.WriteLine(name);
    }
}

Binary Search

• RETURN Array.BinarySearch(ARRAY,ELEMENT)
  • ARRAY – The sorted array
  • ELEMENT – The element to search for
  • RETURN – A positive or negative number
    • If the element is FOUND, then a zero or positive number is returned.
    • If the element is NOT FOUND, then a negative number is returned.

// Previous code
int simonResult = Array.BinarySearch(namesArray, "Simon");
if (simonResult >= 0)
    Console.WriteLine("Simon is an employee.");
else
    Console.WriteLine("Simon is NOT an employee.");

int samResult = Array.BinarySearch(namesArray, "Sam");
if (samResult >= 0)
    Console.WriteLine("Sam is an employee.");
else
    Console.WriteLine("Sam is NOT an employee.");

Test Cases

Improvements

• Zero length array: Explicitly report to the user.
• Place `