Collections in IB Computer Science

Collections in IB book are explained a little bit messy. You can go from page 256 onwards.

Collections in PSEUDOCODE are an abstract of other "iterables" from other programming languages

Other iterables like lists, linkedlists, Calendars, Queues, Stacks, Binary trees.

For example in Java these are the UML diagram of collections. You can never have an instance of a collection but you can have an instance of an ArrayList that is an AbstractList, that is a List and an Abstract Collection and is a Collection and all of them are Iterables

The specifics of those collections are for HL but they share some stuff. In this case that we can iterate through them and that accessing to one specific element is not that fast.

In the case of the abstract (more high level) definition of the collection we're going to have some values and to access them we need to use a cursor.

Functions of a collection

You need to know and use these functions of a collection.

getNext()

That cursor is going to move (we don't need to know how) through the collection every time that we call the function "getNext()" and "getNext()" function is going to return the value that it was stored.

Example:

TREES  //collection of tree names

output TREE.getNext()  //outupts the next name that we have. For example "mapletree"
output TREE.getNext() //outputs the next name after mapletree". For example, "pine"

Each time that we call getNext() we are going to have the next element. So if we want to do something with it we should keep it in a variable.

HasNext()

To know if we have finished with the collection we can access to a function that is going to return a boolean that will return false in the case that we have finished the collection and true otherwise. That function is called "hasNext()"

Example:

If we have a TABLE collection and we call hasNext() is going to return true because we have still 2 more elements until the end of the collection.

resetNext()

Then to reset the cursor to the "first" position we call the function resetNext() that is a function that is not going to return nothing but it's going to make sure that the cursor is in the "first" position.

How to get the first item on the colection

If we have a collection of NIKESNEAKERS and we want to output just the first one this would be the code:

NIKESNEAKERS.resetNext()
output(NIKESNEAKERS.getNext())

They don't usually ask this kind of specific things of "give me the first 3 or last 5 elements", they usually go with all the collection.

addItem()

Finally to add a new item (a new value) we use "addItem()" sending the value that we want to add.

To write them we need to write the name of the collection (usually in Upper case), a dot and the name of the method. An example would be POTATOES.addItem(POTATO)

Example:

We're working on a sushi restaurant webpage and they have all the sushi dishes in a collection called DISHES.

We can start by outputting all of them. This is iterating through a collection. Pretty similar and standar if you know how to iterate through an array.

DISHES  //collection 

DISHES.resetNext()
loop while DISHES.hasNext() 
    output DISHES.getNext()
end loop

Another example

Let's do an iteration through a collection of STUDENTS. Let's output the name of the students that are inside the collection.

STUDENTS // collection
STUDENTS.resetNext()
loop while STUDENTS.hasNext()
    output STUDENTS.getNext()
end loop

The importance of resetNext()

Why the resetNext()? It's not stricly necessary in terms of IB but is a good measure. Imagine that we want to iterate the Dishes twice. Once to output the values and the other that is going to call a function called translate to translate the dishes to the prefered language. If we don't use resetNext, when we finish the first loop the second one is not going to do nothing since hasNext is going to be false

DISHES  //collection 

loop while DISHES.hasNext() //This should work
    output DISHES.getNext()
end loop
loop while DISHES.hasNext() //this doesn't work
    output translate(DISHES.getNext(), Mandarin)
end loop

To solve that we reset the cursor using DISHES.resetNext()

DISHES  //collection 

DISHES.resetNext()
loop while DISHES.hasNext() //this works for sure
    output DISHES.getNext()
end loop
DISHES.resetNext()
loop while DISHES.hasNext() //this works for sure
    output translate(DISHES.getNext(), Mandarin)
end loop

In actual programming you probably are not going to be sure to know if this method has been called already so is a good safety measure to use it just before any loop through the collection.

Let's see if we want to count how many dishes are nigiris. We know that if a dish is a nigiri it will contain the string "nigiri".

For example, "tuna nigiri", "salmon nigiri", "shrimp nigiri".

For checking it out we can use the function containsSubstring(string s) that is going to return true if the string s is cointained in the string that is calling it.

Example

WORD = "chair"
WORD2 = "chicken"
WORD.containsSubstring("ch") // returns true
WORD.containsSubstring("airs") // returns false
WORD2.containsSubstring("ch") //returns true
WORD2.containsSubstring("chicken") //true
WORD3 = "roasted chicken"
WORD3.containsSubstring(WORD2) //true
WORD3.containsSubstring("potato") //false

It's common in the IB exam that they gave you the instructions of how a function works and they ask you to use it, like in this case containsSubstring().

To count how many nigiris we have we need to check if that word contains "nigiri". So let's do it. Remember that we want to output how many nigiris we have.

DISHES  //collection 


DISHES.resetNext()
COUNT = 0
loop while DISHES.hasNext()
    if(DISHES.getNext().containsSubstring("nigiri")) then
        COUNT = COUNT + 1
    end if
end loop
output COUNT

Now the tricky part. We want to count how many nigiris or makis we have in the menu (and output them).

DISHES  //collection 


DISHES.resetNext()
COUNT = 0
loop while DISHES.hasNext()
    CURRENTDISH = DISHES.getNext()
    if(CURRENTDISH.containsSubstring("nigiri") OR CURRENTDISH.containsSubstring("maki")) then
        COUNT = COUNT + 1
     end if
end loop
output COUNT

We need to store the getNext value in a variable.

Rule of thumb: if you have an iteration and inside the loop you call getNext() twice or more times, you're probably doing it wrong (unless you're comparing pairs but it's unlikely). Use the temporary variable.

If you don't remember because you're stuck how to write the temporary variable you can do 2 loops.

DISHES  //collection 


DISHES.resetNext()
COUNT = 0
loop while DISHES.hasNext()
    if(DISHES.getNext().containsSubstring("nigiri") then
        COUNT = COUNT + 1
    end if
end loop
DISHES.resetNext()
loop while DISHES.hasNext()
    if(DISHES.getNext().containsSubstring("maki") then
        COUNT = COUNT + 1    
    end if
end loop


output COUNT

I suggest to store the value from getNext even if it's going to be used once for safety. So the first counting (of only the nigiris) I'd write in an exam like this:

DISHES  //collection 


DISHES.resetNext()
COUNT = 0
loop while DISHES.hasNext()
    CURRENT_DISH = DISHES.getNext()
    if(CURRENT_DISH.containsSubstring("nigiri")) then
        COUNT = COUNT + 1
    end if
end loop
output COUNT

Continuing the example with STUDENTS

Let's say that we want to output how many students have their name that starts with J, L or M, using the method "startsWith()"

First attempt is wrong:

STUDENTS.resetNext()
C = 0
loop while STUDENTS.hasNext()
	if STUDENTS.getNext().startsWith("L") or .startsWith("M") or .startsWith("J") then
		C = C +1
	end if
end loop
output C

Second attempt is also wrong

STUDENTS.resetNext()
C = 0
loop while STUDENTS.hasNext()
	if STUDENTS.getNext().startsWith("L") 
	or STUDENTS.getNext().startsWith("M") 
	or STUDENTS.getNext().startsWith("J") then
		C = C +1
	end if
end loop
output C

Third attempt is the correct one

STUDENTS.resetNext()
C = 0
loop while STUDENTS.hasNext()
	CURRENTSTUDENT = STUDENTS.getNext()
	if CURRENTSTUDENT.startsWith("L") 
	or CURRENTSTUDENT.startsWith("M") 
	or CURRENTSTUDENT.startsWith("J") then
		C = C +1
	end if
end loop
output C

Exercise with students

Count how many people have a name that starts with L and ends with O
use startsWith and endsWith

Exercise

We have a collection with the names of all of our employees called NAMES.

We want to know how many of them are called "Alexei" and how many of them are called "Alexander". We want to know which name is more common.

Posible

Two loops version

NAMES //collection

ALEXEIS = 0
ALEXANDERS = 0
NAMES.resetNext()
loop while NAMES.hasNext()
    if names.getNext() = "Alexei" then
        ALEXEIS = ALEXEIS +1
    end if
end loop
NAMES.resetNext()
loop while NAMES.hasNext()
    if names.getNext() = "Alexander" then
        ALEXANDERS = ALEXANDERS +1
    end if
end loop
if ALEXANDERS > ALEXEIS then
    output "there are more Alexanders than Alexeis"
else if ALEXANDERS = ALEXEIS then
    output "there are the same number of Alexanders and Alexeis"
else 
    output "there are more Alexeis than Alexanders"
end if 

One loop version

NAMES //collection

ALEXEIS = 0
ALEXANDERS = 0
NAMES.resetNext()
loop while NAMES.hasNext()
    NAME = NAMES.getNext()
    if NAME = "Alexei" then
        ALEXEIS = ALEXEIS +1
    else if NAME = "Alexander" then
        ALEXANDERS = ALEXANDERS +1
    end if
end loop

if ALEXANDERS > ALEXEIS then
    output "there are more Alexanders than Alexeis"
else if ALEXANDERS = ALEXEIS then
    output "there are the same number of Alexanders and Alexeis"
else 
    output "there are more Alexeis than Alexanders"
end if 

Another one loop version courtesy of K.B

ALEXEI=0
ALEXANDER=0
NAMES.resetNext()
current=NAMES.getNext()
loop while current.hasNext()
    if current= "Alexander" then
        alexander= ALEXANDER +1
    end if
    if current= "Alexei" then
        ALEXEI= ALEXEI+1
    end if
    current=current.getNext()
end loop
if ALEXANDER>ALEXEI then
    output "Alexander is more common"
end if
if ALEXEI>ALEXANDER then
    output "ALEXEI is more common"
end if
if ALEXEI=ALEXANDER then
    output "equally common"
end if

Exercise similar to an exam: wizards club

(last pages of the document I submitted in teams in January 2024, 27 to be precise)

Howgarts (not the magic school, the other magic school) offers diffent wizards clubs for their students. Each student must choose one of these clubs (it's mandatory)

These are the 5 collections where we're storing the wizards IDs. When a wizard student joins in, a troll adds it's ID to the collection.

PotionsAndExplotions
SetupWizards
Tennis
SpellingSpells
AncientForbiddenLanguagesAndLatin

For example this could be the content of the Collections at a certain given time

PotionsAndExplotions = {122504,5524,65521,58756,36652}
SetupWizards = {9996545,6654,2235,8887,555}
Tennis = {2555,366668}
SpellingSpells = { 1525456,22589,2114,6995,2255,22236,222578,1112}
AncientForbiddenLanguagesAndLatin = {659979,2164654,22247,23368,47798,5554}

The method isIn(X, COL) is available where

• X is an integer representing an ID number
• COL is a collection that holds student ID numbers

This method will return true if the ID number X is inside the collection COL and false otherwise.

For example

isIn(22589,SpellingSpells) returns true
isIn(6654, Tennis) returns false

Exercise 1. Implement a method

Construct a method to implement isIn(X, COL)

Remember that we don't need to do for each specific club. Because we're going to have that specific club sent as a parameter.

Remember also that this is a collection. Not an array.

 isIn (X, COL) //here we have to define the subprogram/function that will end in a "end method" line. 
     COL.resetNext()
     loop while COL.hasNext()
         CURRENT_ID = COL.getNext()
         if CURRENT_ID = X then
             return TRUE
         end if
     end loop
     return FALSE // this return FALSE has to be OUTSIDE the loop
 end method

Other variations would be these

 isIn (X, COL) //here we have to define the subprogram/function that will end in a "end method" line.
     PRESENT = False //this is a flag variable
     COL.resetNext()
     loop while COL.hasNext() AND NOT PRESENT
         CURRENT_ID = COL.getNext()
         if CURRENT_ID = X then
             PRESENT = TRUE
         end if
     end loop
     return PRESENT // this return FALSE has to be OUTSIDE the loop
 end isIn

 isIn (X, COL) //here we have to define the subprogram/function that will end in a "end method" line.
     PRESENT = 0 //this is a flag variable but with a number
     COL.resetNext()
     loop while COL.hasNext() AND NOT PRESENT
         CURRENT_ID = COL.getNext()
         if CURRENT_ID = X then
             PRESENT = 1
         end if
     end loop
     if PRESENT == 1 then 
         return True
     else 
         return False
     end if
 end isIn

Remember that this part is about defining the function, not using it. That's why it starts with the name of the method and ends with the end method or end isIn. It's like when we're implemnting the 4 lines of void dot or dash

Second part of the Exercise. Using a function that recieves a full collection

Next part of the exercise ask that it happens that some of the meetings of PotionsAndExplotions happens at the same time that SetupWizards and we have to construct a code that is going to tell how many of them are in both clubs so measures can be taken. (PotionsAndExplotions is expected to have preference but this is about internal school politics). Use the function isIn described before (in the exam they tell you that you need to use that function)

Solution:

The description of this algorithm is

We set up a counter to 0
Loop through the collection A, for each element in collection A check with isIn and collection B. If that returns true, then we upldate the counter adding 1. Else we keep looking through the collection A. When the loop is done we output the counter.

    PotionsAndExplosions //collection
    SetupWizards // collection
    
    COUNTER = 0
    SetupWizards.resetNext()
    while SetupWizards.hasNext()
        ID = SetupWizards.getNext()
        if isIn(ID, PotionsAndExplosions) then
            COUNTER = COUNTER +1
        end if
    end loop
    output COUNTER

We can use the other collection also, here is another solution

Credit Y.C

Another variation is to count how many students are in Tennis, SpellingSpells and AncientForbiddenLanguagesAndLatin. In this case we need to use either a nested if solution or a composed statement because we want to know who are in the three of them at the same time.

Solution

Composite condition sollution

    COUNTER = 0 
    AncientForbiddenLanguagesAndLatin.resetNext()
    loop while AncientForbiddenLanguagesAndLatin.hasNext()
        ID = AncientForbiddenLanguagesAndLatin.getNext()
        if isIn(ID, Tennis) and isIn(ID, Spellingspells) then
            COUNTER = COUNTER +1
        end if
    end loop
    output COUNTER

Nested if solution (the name of the long collection is wrong but you get it)

Credit Y.C

Third part of the exercise. Now with parallel arrays.

The academic director Magdalena MacGeneral wants to see if there is any student that has not chosen yet any of the clubs.

They store the names of the wizards students (that are 120) in an array called SNAMES and their ids in another parallel array called SIDS.

The exercise is to create an algorithm that will output the names of the students that has not been enrolled to any clubs and, if all the students are in at least one club, there should be an appropiate message. You may use the method isIn from before.

For doing this we're going to split this problem into several parts.

1. We state a flag variable where we supose that all the students are in a club.
2. We need to loop through all the students IDs stored in SIDS (the 120).
3. We need to check if they are not in a specific club. (all 5)
4. If a student is not in any of them, we're going to output its name using SNAMES and the flag variable is going to be set as the opposite.
5. After the loop we're going to check that flag variable to see if we didn't output any student's name. In that case we output a message.

This would be the description.

If they ask for the code this would be the possible answer.

flag = false
count= 0
loop for i from 0 to 119
    flag = false
    if isIn(SIDS[i], PotionsAndExplotions) then
        flag = true
    else if isIn(SIDS[i], SetupWizards) then
            flag = true
    else if isIn(SIDS[i], Tennis) then
                flag = true
    else if isIn(SIDS[i], SpellingSpells) then
                flag = true
    else if isIn(SIDS[i], AncientForbiddenLanguagesAndLatin) then
                    flag = true
    end if
    if flag= false
       output SNAMES[i]
       count= count +1
    end if
    end loop 
if count = 0 then
    output "there are no students who are not in a club"
end if

credit K.B.

FLAG = TRUE
loop for X from 0 to 119
if SIDS[X] not isIn (X, PotionsAndExplotions) then
	if SIDS[X] not isIn (X, SetupWizards) then
		if SIDS[X] not isIn (X, Tennis) then
			if SIDS[X] not isIn (X, SpellingSpells) then
				if SIDS[X] not isIn (X, AncientForbiddenLanguagesAndLatin) then 
					FLAG = FALSE
					output ( SNAMES[X] + "is not in any group")
				end if
			end if
		end if
	end if
end if	
end loop
 
if FLAG then
	output ("All students are in clubs")
end if

credit V.G.

flag true
loop for i from 0 to 119
  if not isIn(SIDS[i], PotionsAndExplotions) AND
     not isIn(SIDS[i], SetupWizards) AND
     not isIn(SIDS[i], Tennis) AND
     not isIn(SIDS[i], SpellingSpells) AND
     not isIn(SIDS[i], AncientForbiddenLanguagesAndLatin) then
      flag = false
  end if
end loop
 
if flag true then
  output "the students are in the clubs"
end if

credit A.P.

There is another version creating an array of the collections.

FLAG = TRUE
ARRAY [5] = {PotionsAndExplotions, SetupWizards, Tennis, SpellingSpells, AncientForbiddenLanguagesAndLatin }
loop for X from 0 to 119
	loop for Y from 0 to 4
		if SIDS [X] not isIn (X, Y) then
			FLAG = FALSE
			output ( SNAMES[X] "is not in any group")
		end if
	end loop
end loop
if FLAG then
	output ("All students are in clubs")
end if

Credit V.G.

Flights: Now with collections.

You have to implement the exercise 23 from here:

https://hackmd.io/GOWuknHrTJSBs6NsxEeDOA#Flag-variables-while-looking-into-arrays

Suposing that the nationalDestinations are stored in a collection and not in an array.

You can also use temporal collections if you need (For counting destinations will be easier)

First exercise is using the array so it's the same.

Next exercise is finding if an specific flight is national or international. Here you have the solution

PSEUDOCODE
flightDestinations[4500] 
SpanishDestinations // collection 

NATIONAL_DESTINATION = false 
SpanishDestinations.resetNext()
loop while SpanishDestinations.hasNext()
    CURRENT = SpanishDestinations.getNext()
    if (flightDestination[2] = CURRENT) 
        NATIONAL_DESTINATION = true
        break
    end if 
end loop
if NATIONAL_DESTINATION  then NATIONAL_DESTINATION = true
    output National
else
    output international
end if

The next one about counting all the fights that are National.

flightDestinations[4500] 
SpanishDestinations // collection 
flag = false
count = 0
 
loop for i from 0 to 4499
	SpanishDestination.resetNext()
	loop while SpanishDestination.hasNext()
		if (flightDestination[i] = SpanishDestination.getNext()) then
			flag = true
			break
		end if
	end loop
	if flag then
		count = count + 1
	end if
end loop
 
output count

credits to CXJ

Count how many diffent locations we have in the array.

flightDestinations[4500] // given array 

DISTINCT // empty collection 

count = 1 

new = true 

DISTINCt.resetNext() 

DISTINCT.addItem(flightDestinations[0]) 


loop for i from 1 to 4499 
	DISTINCT.resetNext() 
	loop while DINSTINCT.hasNext() 
		if (flightDestinations[i] = DISTINCT.getNext()) then 
			new = false 
			break
		end if 
	end loop 
	if new then 
		DISTINCT.addItem(flightDestinations[i]) 
		count = count + 1 
	end if 
end loop 
output count