A Set of Swift Standard Library Classes Equivalent to Some C++ STL Classes

• Download source code - 56.4 KB

Introduction

Swift has been widely used in iOS/MAC OSX software development, but comparing to C++, Swift standard library still lacks some generic algorithm implementations like C++ STL.

Background

I developed a set of Swift generics queue (FIFO) and stack (FILO) classes to match the functionalities of C++ STL queue and stack classes.

Detail of the Project

The project implements a set of Swift generics classes:

• CSingleLinkedListNode: the single linked list node class
• CSingleLinkedList: the single linked list
• CStack: the stack (FILO) class
• CQueue: the queue (FIFO) class

To reach better performance and memory usage, these Swift queue and stack classes are implemented by the set of Swift generics single linked list node and single linked list classes.

The single linked list class, CSingleLinkedList, is the fundamental class for implementation of queue (FIFO) and stack (FILO) classes. It is the wrapper class of single linked list node class, CSingleLinkedListNode, containing the data, reference of next node and a hash value for cycle-finding algorithm implementation.

To avoid loop in the CSingleLinkedList class, a cycle-finding algorithm is implemented with a lookup table of CSingleLinkedListNode object’s key with object instance. To ensure the unique key value of each CSingleLinkedListNode object instance in lookup table, the built in integer type hash value property is designed and generated by exponentiation of two random integer variables.

The cycle-finding algorithm is implemented by checking the existence of repeated node object’s key in the look up table, if no finding of repeated key value in look up table, then the linked list is not looped.

Points of Interest

For C++ developer on Swift programming, there are some interesting points that need attention.

1. Optional, Unwrapped Optional

In C++ coding world, it is very common that a pointer variable null value assignment or null value condition check. Such case scenario in Swift coding, the variable must be declared as optional for following null value assignment, and optional unwrapping must be applied in later code implementation.

var tempValue : T ?  // "?" as declaration of Optional
tempValue = nil      // If not declared as Optional, compilation error here

2. Generics

Swift Generics provides similar functions as C++ template, so Swift Generics make it possible and easier to port C++ template base code to Swift. All classes in this article are implemented by Generics.

3. Swift Multiple Values Function Return: Tuples

One of powerful features in Swift programming is Swift Tuples allowing multiple values function return. In CSingleLikedListNode class, cycle-finding function iscycled() returns three values, boolean value indicating linked list loop or not, the two node objects making the linked list looped.

4. For Loop

Swift for loop is less flexible or powerful than C/C++ for loop. The Swift for loop condition is constant, static, does not support dynamic condition as C/C++ does. For C/C++, for loop code looks like the following:

for (int i = 0; i <= (10-i); ++i)
{
    std::cout << i << std::endl;
}

The above C/C++ code cannot directly port into Swift for loop, since i < (10-i) is dynamic boundary. Its output is 0 1 2 3 4 5.

For Swift for loop code like:

var i : Int = 0
for i in 0 ...(10 - i) {
    print (i)
}

This Swift code segment is not the same as C++ code; its condition boundary is static and initialized to 10 by (10-i) as i with initial value of 0. Its output is 0 1 2 3 4 5 6 7 8 9 10. The solution for porting to Swift is using where condition in the for loop as 

for i in 0...10 where i < (10-i) {
    print(i)
}

or use while loop as:

var i : Int = 0
while i <= (10-i) {
    print(i)
    i += 1
}

For Swift for loop with decremental step, using generic function “stride” is the best solution. For C++ code:

for (int i = 10; 0 <= i; --i)
{
    std::cout << i << std::endl;
}

The equivalent Swift code is:

for i in (0...10).reversed() {
    print (i)
}

or

for i in stride(from:10, to:0, by:-1) {
    print (i)
}

How to Run the Code

The project is developed with XCode on MAC OSX, the classes’ test cases are developed within XCode playground. The code repository in GitHub is https://github.com/zhaohuixing/Swift-Algorithm-Library.