Week 4 - Inheritance and Composition

Goals

Preparation

Simple Container Library I

In this lab you will develop a container library—let’s call it SCL for Simple Container Library. This should give you some practice with inheritance and composition. The Foundation framework provides its own, more complete and powerful, set of containers, which you’ll start using in the following labs. The ones you are going to create in this lab will have some of the same functionality, and similar basic principles. This should give you an idea on how containers work, which might be helpful later on when using the classes provided by the Foundation framework.

The hierarchy of the first version of SCL will be as shown in the figure below:

The base class for all the containers will be the LinkedList, which will be a direct parent of the SortableList, the Stack and the Queue. The SortableList will also be the superclass of the Array class. Hopefully these data structures are vaguely familiar to you—you have implemented some of them in the data structures papers.

Linked list

Create a new OS X / Application / Command Line Tool project in Xcode and call it prog4.1. Download the following file with implementation of the LinkedList class. Add the file to your project—to download the entire file just click on the file name link at the top of the code box:

001:
002:
003:
004:
005:
006:
007:
008:
009:
010:
011:
012:
013:
014:
015:
016:
017:
018:
019:
020:
021:
022:
023:
024:
025:
026:
027:
028:
029:
030:
031:
032:
033:
034:
035:
036:
037:
038:
039:
040:
041:
042:
043:
044:
045:
046:
047:
048:
049:
050:
051:
052:
053:
054:
055:
056:
057:
058:
059:
060:
061:
062:
063:
064:
065:
066:
067:
068:
069:
070:
071:
072:
073:
074:
075:
076:
077:
078:
079:
080:
081:
082:
083:
084:
085:
086:
087:
088:
089:
090:
091:
092:
093:
094:
095:
096:
097:
098:
099:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
/**
A list node containing a reference to an object
and a reference to the next node

*/
class Node {
    
    // STORED PROPERTIES
    
    var object: Any  //Reference to the listed object
    var next : Node?       //Optional reference to the next node

    // INITIALISERS
    
    /**
    Designated initialiser
    
    - parameter object: Object referenced by the node
    */
    init(object: Any) {
        self.object = object
        // By default, this node
        // doesn't have a next node
        // to point to
        self.next = nil;
    }
}

/**
Linked list of objects

*/
class LinkedList : CustomStringConvertible {

    // STORED PROPERTIES

    var head: Node?  // Reference to the head node
    var tail: Node?  // Reference to the tail node

    // COMPUTED PROPERTIES
    
    /**
    Checks if list is empty
    
    - returns: Bool True if list is empty, false otherwise.
    */
    var empty: Bool {
        if tail != nil {
            return false
        } else {
            return true
        }
    }
    
    /**
    Counts the number of the items in the list
    
    - returns: Int Number of items in the list.
    */
    var count: Int {
        
        var nodeCount: Int = 0 
        
        //Starting with the head, walk
        //through the list until the next
        //node points to nil
        var node: Node? = head;
        while let n = node {
            //Count the node
            nodeCount += 1 
            //Get the reference to the next node
            node = n.next
        }
        
        return nodeCount
    }

    /**
    String representation of the list
    
    - returns: String String representation of the list.
    */
    var description: String {
        
        //The beginning of the list is marked
        //with the left-square bracket
        var descStr: String = "["

        //Walk through all the nodes and a string
        //representation of each object's contents
        //to descStr
        var node: Node? = head
        while let n = node {
            descStr += "\(n.object)"
            node = n.next
            if(node != nil) {
                descStr += ", "
            }
        }
        //Close the description string
        //with the right-square bracket
        descStr += "]"
        return descStr
        
    }
    
    // INITIALISERS
    
    /**
    Designated initialiser

    - parameter list: Linked list to initialise with (nil by default)
    */
    init(list: LinkedList? = nil) {
        
        //Set the list to empy
        self.head = nil
        self.tail = nil
        
        //If argument is not nil, then
        //add objects from that list to
        //this one
        if let newList = list {
            var node: Node? = newList.head
            while let n = node {
                self.add(object: n.object)
                node = n.next
            }
        }
        
    }
    
    // METHODS

    /**
    Adds an object to the list
    
    - parameter object: Object to add to the list
    */
    func add(object: Any) {
        //Create a new node pointing to the
        //object to be added
        let node: Node = Node(object: object)
        
        //Add the node to the list
        if let t = tail {
            // If list is not empty, point its
            // last node to the new node and
            // point the tail to the new node
            t.next = node
            tail = node
        } else {
            // If list is empty, point the
            // head and tail to the new node
            head = node
            tail = node
        }
    }
    
    /**
    Removes a node from list

    - parameter node: Node to remove from the list
    - returns: Bool True if node found in the list and removed,
            false otherwise.
    */
    func remove(node: Node) -> Bool {
        
        var nodeFound = false
        
        //Find the node preceding the one
        //to be removed - list is not double
        //linked, so we need to walk through it
        //form the head until we find the node
        //with next link to the node to be removed
        var prevNode: Node? = nil
        var nextNode: Node? = head
        while let n = nextNode {
            //Check if next node is the node
            //to be removed...the === is an
            //address comparison operator;
            //the n is the unwrapped
            //optional
            if(n === node) {
                nodeFound = true
                break;
            }
            prevNode = nextNode;
            nextNode = n.next
        }

        
        if nextNode !== node {
            prevNode = nil;
        }
        
        // If node to be removed is
        // the last one in the list,
        // set tail to the previous node,
        if tail === node {
            nodeFound = true
            if let n = prevNode {
                n.next = nil
            }
            tail = prevNode
            prevNode = nil
        }
        
        // If the list is empty,
        // set head to nil as well
        if tail == nil {
            head = nil
        }
        
        // If node to be removed is
        // the first one in the list,
        // set head to the next node
        if head === node {
            nodeFound = true
            head = node.next
        }
        
        // If head points to nil,
        // then we have empty list
        // and need to set tail accordingly
        if head == nil {
            tail = nil
        }
        
        // Relink the node preceeding
        // the one that we are removing
        // to the node following the one
        // that we are removing
        if let n = prevNode {
            n.next = node.next
        }
        
        return nodeFound
    }
    
    /**
    
    Removes all objects from the list

    */
    func removeAll() {
        head = nil
        tail = nil
    }
    
    
    
}

LinkedList.swift implements two classes: Node and LinkedList. A Node object is an object that contains two references—one to the contained object, the other to the next node in the list. A LinkedList object contains references to the head and tail of the set of linked nodes. The figure below shows a diagram of how it all fits together.

A linked list is a data structure that links set of objects into a chain, which can be traversed through, from object to object, in one direction. The first and last objects are denoted as the head and tail of the list. When the list is empty, the head and tail point to nil.

The code is document, so you can look through the details of LinkedList's implementation, but the class diagram (shown below) should provide sufficient information about the class: (Note that method name "addObject" should be "add" and "removeNode" should be "remove")

In the class diagram, each box represents a class. The three sections within a box give the class name, its properties, and method signatures. Properties that are objects point to the class diagram of their corresponding class. In this case, LinkedList includes two variables of Node? type (that is, Node wrapped in an optional). The Node class has also a variable that points to a Node? (an optional of the same type). LinkedList uses Nodes through composition—a list is not a node, but it has nodes.

The class diagram above doesn't show initialisers. If you take a look at the implementation of LinkedList you'll see that its initialiser is init(list: LinkedList? = nil). This initialiser has a parameter with a specified default value. This means that it can be invoked without providing the parameter, in which case the default value of the parameter will be taken. If the initialiser is provided with a parameter that is a LinkedList, it will make the new list as a copy of the one passed in. The add and remove methods allows adding and removing items from the list. Addition puts the new object at the end of the list. When removing a node, the nodes preceding and following the one that is removed are relinked together.

To test the LinkedList, place the following code in main.swift:

01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
import Foundation

let str1: String = "Item V";
let str2: String = "Item E";
let str3: String = "Item S";
let str4: String = "Item M";

var list: LinkedList = LinkedList()
print("\(list)")

list.add(object: str1)
list.add(object: str2)
list.add(object: str3)
list.add(object: str4)
print("\(list)")

At first, this program creates an empty linked list and shows its contents—LinkedList is Printable, so its description method will be invoked through interpolation. Since the LinkedList class refers to its elements with Any type, it means that it can contain object references or values of any type. In Swift, every type automatically type casts to Any. In the program above, the items added to the list are Strings. Afterwards, the list is printed again. Compile and run. You should get the following output in your Debug window:

[]
[Item V, Item E, Item S, Item M]

Queue

Then next container you'll be adding to the SCL is the Queue class. A queue is a first-in-first-out structure, where the order of objects removed from the queue follows the order of insertion. Queues are useful for buffering, where data can be stored for later processing.

A queue can be seen as a linked list implementing the put and get methods: put inserts an object at the tail end of the list, get removes objects from the head of the list. Hence, in SCL I, the Queue class will inherits from the LinkedList.

Crate a new file in Xcode, name it Queue.swift, and fill it out with the following code (best to type it out this time):

01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
import Foundation
/**
A queue of objects

*/
class Queue : LinkedList {

    /**
    Queue desription - adds a string indicating the
    container is a queue before invoking super's description
    
    - returns: String String representation of the queue
    */
    override var description: String {
        return "(Queue)<--"+super.description+"<--"
    }
    
    /**
    Puts an an object at the end of the queue
    
    - parameter object: Object to put in the queue.
    */
    func put(object: Any) {
        // Use inherited method to add object
        // to the list
        self.add(object: object);
    }
    
    /**
    Gets an an object from the start of the queue
    
    - returns: Any? Object removed from the start of the queue,
                nil if queue is empy.
    */
    func get() -> Any? {
        // If head points to a non-nil node,
        // remove that node and return its
        // object
        if let n = head {
            //Use inherited method to remove
            //node from the list
            self.remove(node: n)
            return n.object
        } else {
            return nil
        }
    }
}

The put method uses the inherited method add to add an object to the end of itself. The get method uses inherited method remove to remove the node at the head of the list and return the object that node is referencing.

The Queue class also overrides the description method. It still invokes its parent's description by calling super.description, but the string returned by the superclass is wrapped in a string indicating that the new container is a queue. The wrapping string also indicates the insert and remove ends of the queue (with the arrows) where the objects enter and exit the list.

The class diagram for the Queue is shown below.

Notice that Queue responds to all the methods that LinkedList does—that's the nature of inheritance. Visibility of the inherited methods can be controlled to certain degree with Access Control, but in this lab all the methods will carry the implicit privacy setting, which corresponds to internal access.

Add the following code to main.swift to test the new container:

01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
import Foundation

let str1: String = "Item V";
let str2: String = "Item E";
let str3: String = "Item S";
let str4: String = "Item M";

var list: LinkedList = LinkedList()
print("\(list)")

list.add(object: str1)
list.add(object: str2)
list.add(object: str3)
list.add(object: str4)
print("\(list)")

var queue: Queue = Queue(list: list)
print("\n\(queue)")

if let item1 = queue.get() {
    print("Got item: \(item1 as! String)")
}
print("\(queue)")

print("Putting item: \(str2)")
queue.put(object: str2)
print("\(queue)")

Notice that the above program uses initialisation method inherited from LinkedList, passing an existing list into the new Queue instance. Hence, the first print out of the queue contents is the same as the contents of that list. Also note the forced casting of item1. The type of variable item1 is inferred to be Any, because that's the type that the get() method returns. However, this object is definitely a String, because the list has been populated only with Strings.

Compile and run. You should get additional output that looks as follows:

(Queue)<--[Item V, Item E, Item S, Item M]<--
Got item: Item V
(Queue)<--[Item E, Item S, Item M]<--
Putting item: Item E
(Queue)<--[Item E, Item S, Item M, Item E]<--

Stack

Next container you'll be implementing is a stack. A stack is a last-in-first-out data structure, where the order of insertion is reversed when removing objects from the structure. A stack can be seen as a linked list implementing push and pop methods: push inserts objects at list's tail, pop removes objects at the tail. Stacks mirror constraints present in many real world problems, and therefore are quite useful as programming abstractions. For instance, think of a line of cars parked on a narrow driveway—the last person to park must move their car before others can leave.

This time you have to implement the class yourself. Create a new file Stack.swift in your Xcode project and implement the Stack class so that its interface conforms to the class diagram below. Remember, you don't need to implement the inherited methods. Model your new methods on Queue class—there's very little that needs to change in order to have it behave like a stack.

Once you're satisfied with your implementation, add the following code to main.swift:

01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
import Foundation

let str1: String = "Item V";
let str2: String = "Item E";
let str3: String = "Item S";
let str4: String = "Item M";

var list: LinkedList = LinkedList()
print("\(list)")

list.add(object: str1)
list.add(object: str2)
list.add(object: str3)
list.add(object: str4)
print("\(list)")

var queue: Queue = Queue(list: list)
print("\n\(queue)")

if let item1 = queue.get() {
    print("Got item: \(item1 as! String)")
}
print("\(queue)")

print("Putting item: \(str2)")
queue.put(object: str2)
print("\(queue)")

var stack: Stack = Stack(list: list)
print("\n\(stack)")

if let item2 = stack.pop() {
    print("Popped item: \(item2 as! String)")
}
print("\(stack)")

print("Pushing item: \(str2)")
stack.push(object: str2)
print("\(stack)")

Run and check for the following additional output:

(Stack)[Item V, Item E, Item S, Item M]<-->
Popped item: Item M
(Stack)[Item V, Item E, Item S]<-->
Pushing item: Item E
(Stack)[Item V, Item E, Item S, Item E]<-->

Is your output the same? No? Is it perhaps because you didn't override the description method, or you did it in a different way? As long as the stack contents are correct, you can leave your version of the descrition method. If you'd like to make it look like the one above, you should be able to deduce how it works from the print out above.

Array

An array associates index numbers with objects it contains. This makes it easy to access any object in the list (by providing its index), reading and writing from/to an arbitrary position. In SCL I, an array is going to be a linked list with enumerated items. This is going to be rather inefficient implementation of an array, but the point of this exercise is to practice inheritance.

To implement the Array class, you'l need first the SortableList class, from which Array will inherit. Download the following file and add it to your project:

001:
002:
003:
004:
005:
006:
007:
008:
009:
010:
011:
012:
013:
014:
015:
016:
017:
018:
019:
020:
021:
022:
023:
024:
025:
026:
027:
028:
029:
030:
031:
032:
033:
034:
035:
036:
037:
038:
039:
040:
041:
042:
043:
044:
045:
046:
047:
048:
049:
050:
051:
052:
053:
054:
055:
056:
057:
058:
059:
060:
061:
062:
063:
064:
065:
066:
067:
068:
069:
070:
071:
072:
073:
074:
075:
076:
077:
078:
079:
080:
081:
082:
083:
084:
085:
086:
087:
088:
089:
090:
091:
092:
/**
Extending the node class to provide it with a method
for swapping objects between nodes
*/
extension Node {
    
    /**
    Swaps objects between self and another node nodes - useful for
    sorting - instead of swapping and relinking the nodes, it's easier
    to leave the nodes where they are, and just swap their
    objects
    
    - parameter n Node to swap objects with
    */
    func swapObjectsWith(n: Node) {
        let temp: Any = self.object
        self.object = n.object
        n.object = temp
    }
}


class SortableList : LinkedList {
    
    /**
    Get the Nth node from the LinkedList
    
    - parameter index: Index of the node to Get
    - returns: Node? The node at the specified index, or nil
    if index exceeds list count
    */
    func getNodeAtIndex(index: Int) -> Node? {
        var node: Node? = head;
        // Walk through the list until the
        // specified index
        if index > 0 {
            for _ in 1...index {
                if let n = node {
                    node = n.next;
                } else {
                    // Exit early if index
                    // exceeds number of
                    // items on the list
                    return nil;
                }
            }
        }
        return node;
    }
    
    /**
    Sort the list using the provided compare function
    
    - parameter isObject: A function that compares two objects and
    returns true if the first one is smaller than the second one
    
    */
    func sort(isObject: (Any, Any) -> Bool) {
        
        while true {
            var swap: Bool = false;
            
            var nodeLeft: Node? = head
            
            // Walk through the nodes in the list
            while let nLeft = nodeLeft  {
                // Get the next node in the list
                if let nRight = nLeft.next {
                    // Invoked the function that got passed
                    // in as a parameter to check if the
                    // object that follows the current one
                    // on the list is smaller - if yes,
                    // then swap the object of the two nodes
                    if(isObject(nRight.object, nLeft.object)) {
                        nLeft.swapObjectsWith(n: nRight)
                        swap = true
                    }
                }
                nodeLeft = nLeft.next
            }
            
            // Check if anything got swapped in this
            // pass through the entire list - if not,
            // then the entire list has been completely
            // sorted
            if !swap {
                break;
            }
        }
    }
    
}

The first thing you'll notice in SortableList.swift is the extension of the Node class. Extension is like a continuation of implementation of a given class; it allows you to add new methods. In this case, a method has been added to Node that performs object swap with another node. This method will be useful for sorting. Extensions are a good alternative to inheritance when a bit of extra functionality is needed from a class, but not so much to justify creation of a new subclass.

SortableList inherits from LinkedList and implements three methods: one for fetching a node at given index in the the list, and another for sorting. The argument of the sort method is a function—in Swift you can pass in a function as a parameter into another function/method. In this case, the isObject parameter is a function with signature (Any, Any) -> Bool, and is meant to provide code for comparing two items on the list. It does not always make sense to compare objects, and even when it does, it's not always apparent what does it mean for one instance of a given class to be bigger/smaller than another instance of another class. Hence, the sorting method requires the programmer, who invokes the method, to provide the code that does the comparison. That code is invoked in the second if statement of the sort method, followed by a call to Node's newly extended swapObjectWith method.

The class diagram for SortableList is shown below (note the new method in the extended Node class).

Create a new file in you project and name it Array.swift. Implement the Array class that inherits from SortableList and conforms to the interface of the class diagram below.

The get(index: Int) -> Any method should return object at specified index, and the set(object: Any, at: Int) method should place the new object at given index. In both cases, if the index exceed the size of the array, an assert should be triggered. This means that array can be extended only by using the inherited add(object: Any) method. If you're not sure how to go about implementing the new methods, here's a hint—the getNodeAtIndex method, inherited from SortableList, should be very useful.

Once you're finished with your implementation, add the following code to main.swift:

01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
import Foundation

let str1: String = "Item V";
let str2: String = "Item E";
let str3: String = "Item S";
let str4: String = "Item M";

var list: LinkedList = LinkedList()
print("\(list)")

list.add(object: str1)
list.add(object: str2)
list.add(object: str3)
list.add(object: str4)
print("\(list)")

var queue: Queue = Queue(list: list)
print("\n\(queue)")

if let item1 = queue.get() {
    print("Got item: \(item1 as! String)")
}
print("\(queue)")

print("Putting item: \(str2)")
queue.put(object: str2)
print("\(queue)")

var stack: Stack = Stack(list: list)
print("\n\(stack)")

if let item2 = stack.pop() {
    print("Popped item: \(item2 as! String)")
}
print("\(stack)")

print("Pushing item: \(str2)")
stack.push(object: str2)
print("\(stack)")

var array: Array = Array(list: list)
print("\n\(array)")

print("Setting array[2] to \(str1)")
array.set(object: str1, at: 2)
print("\(array)")

print("Sorting array");
array.sort(isObject: { o1, o2 in (o1 as! String) < (o2 as! String) })
for index in 0..<array.count {
    print("array[\(index)]=\(array.get(index: index))")
}

Note the parameter that is passed in to array's sort method: "{ o1, o2 in (o1 as! String) < (o2 as! String) }"—that's the block of code that compares two objects from the list. This block of code is called a closure, and the syntax given above is a short-hand syntax that implements anonymous function of signature "(Any, Any) -> Bool". This signature matches the signature of the isObject argument of SortableList's sort method. Swift comes with a defined "<" operator for Strings, and so inside the closure, all that is needed is to force type cast o1 and o2 from Any type to String type and use the "<" operator for comparision. Type casting to String in this way is not very safe, but in this case all the items on the list are Strings, and so there will be no problem at runtime. For more explanation on closures and their syntax read on Closures.

Run the program, if your implementation is right you should get the following output:

(Array) 0->[Item V, Item E, Item S, Item M]<-3
Setting array[2] to Item V
(Array) 0->[Item V, Item E, Item V, Item M]<-3
Sorting array
array[0]=Item E
array[1]=Item M
array[2]=Item V
array[3]=Item V

Once again, your print out of the array list might not be exactly the same, depending whether you chose to, and how you chose to, override the description method. In the above output, the new method adds "(Array)" string at the beginning of the print out along with the first and last index value.

Array internals

Arrays are not typically implemented as linked lists—in fact, the whole point of having an indexed data structure is to have it in a contiguous memory block where index facilitates instant computation of the offset for a given item from the beginning of the array. Hence, the SCL's Array is doomed to be slow. However, there's one aspect that can be improved on, and it presents an opportunity for more practice with inheritance.

The element count plays an important role in an array, because array users need to keep checking the array size to make sure that they don't try to access items out of bounds. Hence, the count property is likely to get much heavier use on an Array object than other LinkedList objects. If you followed the examples of the Stack and SortableList, your implementation of Array at the moment inherits LinkedList's computed property count. LinkedList's implementation of count is very inefficient, because it traverses the list and counts the object every time the method is invoked. It's more efficient to have a variable that keeps the count of items in the array. This variable must be updated whenever elements are added/removed to/from the array. Given this variable, the stored property count can be overriden to simply return the count instead of traversing the list every time. Here's how this can be done (the code below doesn't give the entire implementation of Array—it should be just supplementing your current implementation):

01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
import Foundation

/**
Indexed array of objects

*/
class Array : SortableList {
    
    // STORED PROPERTIES
    
    private var _count: Int    // Stored property that counts elements in the array
    
    // COMPUTED PROPERTIES
    
    /**
    Computed property that returns the number of elements in the array - overrides
    LinkedList property to return stored _count property rather than traversing
    the list and coutning the elements.

    - returns: Int Number of items in the array
    */
    override var count: Int {
        return self._count
    }

    // INITIALISERS
    
    /**
    Designated initialiser for Array - overrides LinkedList initialiser
    in order to initialise the _count stored property
    
    - parameter list: LinkedList to initialise array with (nil by default)
    */
    override init(list: LinkedList? = nil) {
        self._count = 0 
        super.init(list: list)
    }

    // METHODS
    
    /**
    Adds an object to the array - overrrides LinkedList method
    in order to increment the _count variable when new object
    is added.
    
    - parameter object: Object to add to the list
    */
    override func add(object: Any) {
        super.add(object: object)
        self._count += 1 
    }

    /**
    Removes a node from the array - overrideds LinkedList method
    in order to decrement the _count variable when an node (and object)
    is removed form the list
    
    - parameter node: Node to remove from the list
    - returns: Bool True if node found in the list and removed,
    false otherwise.
    */
    override func remove(node: Node) -> Bool {
        let nodeRemoved: Bool = super.remove(node: node)
        if nodeRemoved {
            self._count -= 1 
        }
        return nodeRemoved
    }
}

Let's go over the introduced changes one by one. A new private stored property called _count is added to Array, and the computed count method is overriden to simply return the _count value. Whereas before, initialisation method was inherited from LinkedList, now the init method is overriden, because the new stored property needs to initialised by the Array class. The reminder of initialisation remains the same, and so it can be done with a call to parent's initialiser.

In this exercise you were guided to implement the SCL heirarchy in such a way, so that an addition of the new object to the list always goes through LinkedList's add method and a removal of an object form the list always goes through LinkedList's remove method. Hence, in order to maintain the _count in synch with the number of elements in the list, all that is required is overriding those two methods. The new add simply calls the parent method and follows with increment of the _count property. The new remove method check if removal using parent method was successful before decrementing the _count property.

Note that Array's interface hasn't changed, yet its internal behaviour has been modified to speed up the call to _count. All it took is understanding of LinkedList's internals and overriding of certain methods such that they still invokes parent's implementation. The output of the program in main.swift should remain the same. The speed improvement for invocation of count will not be noticeable, but it would make quite a difference if one was to repeatedly iterate over large arrays.

Subscripts

Part of the job of the Toolmaker is to provide the Builder with a nice interface. In case of arrays, it would be nice to be able to access its elements using the square bracket syntax—that is, to be able to write "array[2] = str3" instead of "array.setObject(str3, at: 2)". Swift allows definition of bracket notation on objects through the computed subscript property. For the Array class, the required getter and setter code can simply wrap the getObject and setObject methods, as shown below (again, the entire class is not shown, just the method in question):

01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
import Foundation

/**
Indexed array of objects

*/
class Array : SortableList {
    
    /**
    Method for indexed square bracket notation that
    wraps the getObject and setObject methods
    
    - parameter index: Index of the item in the array
    */
    subscript(index: Int) -> Any {
        get {
            return self.get(index: index)
        }
        set(newObject) {
            self.set(object: newObject, at: index)
        }
    }
}

Once you add the above subscript computed property to Array, you can change the code in main.swift as follows, without impacting the program output:

01:
02:
03:
04:
05:
06:
07:
08:
09:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
import Foundation

let str1: String = "Item V";
let str2: String = "Item E";
let str3: String = "Item S";
let str4: String = "Item M";

var list: LinkedList = LinkedList()
print("\(list)")

list.add(object: str1)
list.add(object: str2)
list.add(object: str3)
list.add(object: str4)
print("\(list)")

var queue: Queue = Queue(list: list)
print("\n\(queue)")

if let item1 = queue.get() {
    print("Got item: \(item1 as! String)")
}
print("\(queue)")

print("Putting item: \(str2)")
queue.put(object: str2)
print("\(queue)")

var stack: Stack = Stack(list: list)
print("\n\(stack)")

if let item2 = stack.pop() {
    print("Popped item: \(item2 as! String)")
}
print("\(stack)")

print("Pushing item: \(str2)")
stack.push(object: str2)
print("\(stack)")

var array: Array = Array(list: list)
print("\n\(array)")

print("Setting array[2] to \(str1)")
array[2] = str1
print("\(array)")

print("Sorting array");
array.sort(isObject: { o1, o2 in (o1 as! String) < (o2 as! String) })
for index in 0..<array.count {
    print("array[\(index)]=\(array[index])")
}

Simple Container Library II

In the previous exercise you have implemented a simple container library. Hopefully, thanks to inheritance, this didn’t take you too much time. Still, you managed to create a library with quite an assortment of tools for organising collections of objects: a linked list, queue, stack and an array. Try to answer the following questions:

Question 1: What was the point of creating the SortableList class, as opposed to implementing all its functions in the Array class?

Question 2: Can you think of another type of container that is not an Array, but could inherit from SortableList? If you can’t think of anything at this time, could there be still a good reason to have the SortableList in the SCL hierarchy?

Does the relationship between Queue and LinkedList seem right? Is a queue a linked list, or should it contain a linked list? Same goes for Stack—should it inherit from LinkedList or should it just contain a list? Take a look at their class diagrams. Notice for instance, that through inheritance, both the Stack and Queue classes provides the remove method. This method allows for object removal from any part of the list...and that's not really desired for either a queue or a stack.

As a Toolmaker you have a choice. When creating object hierarchies you can ignore the fact that some inherited methods make no sense or should not be used by the child object. Sometimes it's reasonable to assume that a Builder will not misuse inherited methods—especially if the Builder is you. Another way is to override undesired method with calls to assertions (or exceptions). This will prevent the method from use by crashing the program—hopefully during testing phase and not in operation. Though this second path is often taken, you can imagine that it's generally considered a bad practice.

There is a third option—to use composition instead of inheritance. The most common OOP mistake made by a novice programmer is overuse of inheritance. Inheritance is tempting because of it allows code reuse. However, sometimes a little bit extra effort is worthwhile, especially if it prevents potential misuse of objects of your class.

In this part of the exercise, you'll be creating a second version of SCL. Create new Xcode project, name it "prog4.2". Add LinkedList.swift to the project—the same one as in the first part of this lab. The Node and LinkedList classes will remain unchanged.

Create new versions of Queue, Stack, and Array that conform to the class diagrams shown below:

The three classes above do not inherit from LinkedList, but have a stored property, called list, of LinkedList type to/from which objects can be added and removed. All other details of the implementation are up to you—just make sure that these classes don't provide only the methods listed in the diagram (initialisers are not shown). Though, at first, it might seem like a lot of work, you can do everything reusing the code from SCL I. Most of it will be modification of certain references to self that now will be references to the contained list object. The empty, count and discription properties will not be inherited from LinkedList anymore, but they don't need to do much more beyond wrapping the calls to list's methods. You don't have to implement the SortableList, but you may chose to do it as a parent of Array. Regardless of whether you chose to have a SortableList or not, you will need to extend Node to add the swapObjectsWith method like what was done previously, and the sort method needs to be working for the Array class.

Hopefully over the course of implementation of SCL II you've been reflecting on similarities and differences of inheritance and composition. In this case, it's not entirely clear that one approach is better than the other—there are pros and cons in either case. When designing OOP programs/libraries it's best to carefully consider implications of going one way or another, and make an informed decision on which one will be more appropriate.