CS Data Structures: Fixed Array

Exordium

A fixed (or fixed-size, fixed-length) array is an array that has a max amount of items. Such arrays are used when the programmer knows how many elements an array should hold - such as the number of enemy spaceships a game should display on-screen at once or the value of an 8-bit character.

Some languages, such as C, Objective-C, and C++, use fixed arrays, while more modern languages use arrays that aren't set in size. In a language that uses fixed arrays, once you set the size of the array - it does not change. For example, if a fixed array is initialized with 15 elements, the array can not store 16 elements. Though the array is incapable of growth, it is capable of mutation. With the first 15 elements, if the 14th element needed to be changed, it could be. If an element needs to be deleted, it can be; the fixed-size of 15 can hold less than 15 elements; it just can't hold more.

Below is an array in C++ that holds 15 integers. The elements of the array are placed in a contiguous block of memory:

int foo [15];

When working with fixed arrays, it's important to be precise and understand why you're using this type of array. They leave room for overflow errors and are generally not a flexible data structure. That said, the good thing about these types of arrays is that they are predictable and fast. You know what to expect regarding the number of elements stored in the array and how large the array is in memory.

Fixed Array Operations

Fixed arrays should be able to:

• Append new elements to the end
• Insert new elements at the beginning and in the middle
• Delete elements
• Look up elements by index
• Count the size of the array

Appending an element to the end of a fixed array is easy as long as the array isn't full. Again, the size of a fixed array does not change after it is set. This operation has a time complexity of O(1). Another quick operation is finding an element by the index, also a constant time complexity. To continue on the topic of time complexity, inserting and deleting are expensive with a fixed array. If an element is being inserted in the middle or beginning of a fixed array, all the elements to the right of the new element must be moved up a position in memory by 1.

To add the number 5 to a fixed array:

Something to note; if there is code that references an object of the array using an index, and a new element is added into the middle of the array, the indexes no longer reference the correct objects.

Furthermore, deleting an element from the array is the same process, but reversed. The elements are moved one position to the left instead of the right.

To delete the number 5 from the same array:

Both inserting and deleting elements from a fixed array results in linear time complexity - O(n).

How to Build a Fixed Array

Here, Swift is used to build a fixed array, though the concept can be used in any language.

The Fundamental Properties

The first thing to do is create the fixed array, its basic properties, and an initializer. The array needs the following properties:

1. A max size to ensure it doesn't grow past what the use case needs.

2. A default value (this will be used to add an item to the array when needed).

3. An internal array (in this case, it's a Swift array ).

4. The count (which is updated each time an element is removed or added to the array).

5. Two public properties that return information. The first being the elements within the array, and the second being the length of the array. count is not directly used to return the array's length (e.g., fixedArray.count) because it is private. It is private because in this use case, tracking the amount of elements in an array with a counter and then reading the count property is faster than directly calling the internal count method on the array; which traverses through each element, then returns the number of elements in the array.

A Fixed Array in Swift:

struct FixedArray<T> {
    private var maxSize: Int
    private var defaultValue: T
    private var array = [T]()
    private var count = 0

    public var elements: [T] {
        return array
    }

    public var length: Int {
        return count
    }

    public init(maxSize: Int, defaultValue: T) {
        self.maxSize = maxSize
        self.defaultValue = defaultValue
        array = .init()
    }
}

The initializer sets the max amount of elements to be allowed in the array, along with the 'default value' of the array. defaultValue is used to add a default object to the array when appending new objects. This will be seen in the insert method.

The other thing to add in the Swift implementation of a Fixed Array is a custom subscript. In Swift, you can add custom subscripts to Structs, Classes, and Enumerations in order to access the elements of a collection, list, or sequence.

struct FixedArray<T> {
    private var maxSize: Int
    private var defaultValue: T
    private var array = [T]()
    private var count = 0

    public var elements: [T] {
        return array
    }

    public var length: Int {
        return count
    }

    public init(maxSize: Int, defaultValue: T) {
        self.maxSize = maxSize
        self.defaultValue = defaultValue
        array = .init()
    }

    subscript(index: Int) -> T {
        assert(index >= 0)
        assert(index < count)
        return array[index]
    }
}

When a fixed array is initialized, it is empty. This can be seen by using the elements and length properties.

var array = FixedArray<Int>(maxSize: 6, defaultValue: 0)
array.elements
// []
array.length
// 0

Adding Functionality to the Array

As noted in the Fixed Array Operations section of this article, fixed arrays should be able to:

• Append new elements to the end.
• Insert new elements at the beginning and in the middle.
• Delete elements.
• Look up elements by index.
• Count the size of the array.

It is important to note that any time an element is added or removed, the count variable must be updated in accordance with this action.

The first custom method will be named appendToEnd() and it will do just that - add an element to the end of the array. Before the method adds the element, it uses assert to make sure count is less than maxSize . If count is greater than the total amount of allowed elements, no more elements can be added to the array. To learn more about using assert in Swift, check out the official Apple Documentation.

// Append to end of array
public mutating func appendToEnd(element: T) {
    assert(count < maxSize)
    array.append(element)
    count += 1
}

Next, inserting elements in the middle and beginning of the array. There are a few things to keep in mind when writing this method.

The array has the chance to hold different variations when adding new elements. It may be empty; it may be full; it may be half full, etc. Also, the index where an element needs to be added may be different each time the method is used.

In this instance, the method checks for the following cases then proceeds to handle the insertion accordingly:

1. The index is 0, and the count property is 0. The array is empty, and the element needs to be inserted at the beginning, as the very first element in the array.

2. The count is equal to maxSize and the index is 0 OR the count is equal to maxSize and the index is not equal to 0. The array is full, and the element needs to be inserted at the beginning, or somewhere in the middle or end. This ensure that no new elements are added to the array when trying to insert them when the array is full.

3. The index is 0, and count is not equal to maxSize. In this case, the requested element needs to be inserted at the beginning, shifting the current elements to the right in order to make room for the new element. This is accomplished by appending a new default element to the end of the array, traversing through the elements starting at index 1, moving through the reversed version of the elements in the array, and moving them one space to the right. Remember that the value of index in this instance is 0, which ensures that the loop starts with the second element; leaving the new element in place at the 0th index of the array.

4. In all other cases, the array will do the same thing as case 3 above, except the loop doesn't start at index 0. In this case, the loop starts at the given value of index. A visualization of this can be seen earlier in this article; under the Fixed Array Operations section.
   

// Insert at index of array
public mutating func insert(element: T, at index: Int) {
    assert(index >= 0)
    assert(index < maxSize)

    if index == 0 && count == 0 {
        array.append(element)
        count += 1
    } else if count == maxSize && index == 0 || count == maxSize && index != 0 {
        array[index] = element
    } else if index == 0 && count != maxSize {
        array.append(defaultValue)
        count += 1

        for i in (index+1..<count).reversed() {
            array[i] = array[i - 1]
        }

        array[index] = element
    } else {
        array.append(defaultValue)
        count += 1

        for i in (index..<count).reversed() {
            array[i] = array[i - 1]
        }

        array[index] = element

    }
}

The Fixed Array now looks like this:

struct FixedArray<T> {
    private var maxSize: Int
    private var defaultValue: T
    private var array = [T]()
    private var count = 0

    public var elements: [T] {
        return array
    }

    public var length: Int {
        return count
    }

    public init(maxSize: Int, defaultValue: T) {
        self.maxSize = maxSize
        self.defaultValue = defaultValue
        array = .init()
    }

    // Append to end of array
    public mutating func appendToEnd(element: T) {
        assert(count < maxSize)
        array.append(element)
        count += 1
    }

    // Insert at index of array
    public mutating func insert(element: T, at index: Int) {
        assert(index >= 0)
        assert(index < maxSize)

        if index == 0 && count == 0 {
            array.append(element)
            count += 1
        } else if count == maxSize && index == 0 || count == maxSize && index != 0 {
            array[index] = element
        } else if index == 0 && count != maxSize {
            array.append(defaultValue)
            count += 1

            for i in (index+1..<count).reversed() {
                array[i] = array[i - 1]
            }

            array[index] = element
        } else {
            array.append(defaultValue)
            count += 1

            for i in (index..<count).reversed() {
                array[i] = array[i - 1]
            }

            array[index] = element

        }
    }
}

To start adding elements to the array, use either the appendToEnd or insert methods. Here, the integers 1, 2, and 3 are added to the end of the array. Then, 5 is inserted at the 3rd index, 6 is inserted at the 4th index, and 4 is inserted at the 3rd index. The array ends up holding [1, 2, 3, 4, 5, 6].

array.appendToEnd(element: 1)
array.appendToEnd(element: 2)
array.appendToEnd(element: 3)
array.elements
// [1, 2, 3]

array.insert(element: 5, at: 3)
array.elements
// [1, 2, 3, 5]

array.insert(element: 6, at: 4)
array.elements
// [1, 2, 3, 5, 6]

array.insert(element: 4, at: 3)
array.elements
// [1, 2, 3, 4, 5, 6]

Now that the array can have elements added to it, there needs to be a way to remove these elements. There are three ways to remove items in a fixed array:

1. Remove the element at the end of the array.
2. Remove the item based on a given index.
3. Remove all of the items in the array.

To delete an item from the end, simply make sure that count is greater than 0, use the removeLast method on the array, and decrement 1 from count.

// Delete from end of array
public mutating func deleteFromEnd() {
    assert(count > 0)
    array.removeLast()
    count -= 1
}

Removing an element based on a given index is a bit trickier. The index must be less than or equal to 0, and it must also be less than the value of count. After these assertions pass, count is decremented by 1, the element at the given index is obtained in result and the remove function of the Swift array is called with index as its parameter. Finally, the element that is stored in result is returned.

// Delete at index of array
public mutating func removeAt(index: Int) -> T {
    assert(index >= 0)
    assert(index < count)
    count -= 1
    let result = array[index]
    array.remove(at: index)
    return result
}

Below is the usage of these two methods. The deleteFromEnd method does not return the element that is removed, but the removeAt method does. How they are used is up to the programmer.

array.deleteFromEnd()
array.elements
// [1, 2, 3, 4, 5]

array.removeAt(index: 1)
// Returns 2

array.elements
// [1, 3, 4, 5]

The final 'delete' method is one that removes all of the elements from the array. The method loops through the value of count, removes the last element, and decrements count by 1. Once it processes the array, it then sets count to 0.

// Remove all elements
public mutating func removeAll() {
    for _ in 0..<count {
        array.removeLast()
        count -= 1
    }
    count = 0
}

Again, the usage of this method:

array.removeAll()
array.elements
// []

The methods seen here can be changed to whatever use-case the programmer may have, but they perform the basic actions that a Fixed Array should be able to perform.

One thing that needs to be seen is the usage of the subscripts. It was mentioned earlier, but hasn't been used in code yet.

Custom Subscript in a Fixed Array

Custom subscripts work the same way as regular subscripts. The difference is that you define what is returned when using the subscript. When an element needs to be accessed in a Fixed Array, (or other custom data type), it's accessed by using brackets - array[element].

When defining a custom subscript in Swift, a return type must be defined. This is expected, as subscripts return elements. Here is the subscript again:

subscript(index: Int) -> T {
    assert(index >= 0)
    assert(index < count)
    return array[index]
}

Imagine that array holds [1, 2, 3, 4, 5, 6]. Here is how an element would be accessed:

print(array.element)
// [1, 2, 3, 4, 5, 6]
let firstElement = array[0]
let fourthElement = array[3]

print(firstElement)
// 1
print(fourthElement)
// 4

The Complete Fixed Array in Swift

That is it for the Fixed Array. This data structure can be implemented in any language, and the use case is up to the programmer. A Fixed Array can be used for situations such as tracking the number of enemies on screen in a game, creating a representation of a byte (bytes are a storage unit in computing and are made up of 8 bits. Bits are the smallest unit used for storage on a computer), or limiting the number of family members that a user can add to their family account of a subscription.

Below is the complete Fixed Array in Swift, using a generic type:

struct FixedArray<T> {
    private var maxSize: Int
    private var defaultValue: T
    private var array = [T]()
    private var count = 0

    public var elements: [T] {
        return array
    }

    public var length: Int {
        return count
    }

    public init(maxSize: Int, defaultValue: T) {
        self.maxSize = maxSize
        self.defaultValue = defaultValue
        array = .init()
    }

    // Append to end of array
    public mutating func appendToEnd(element: T) {
        assert(count < maxSize)
        array.append(element)
        count += 1
    }

    // Insert at index of array
    public mutating func insert(element: T, at index: Int) {
        assert(index >= 0)
        assert(index < maxSize)

        if index == 0 && count == 0 {
            array.append(element)
            count += 1
        } else if count == maxSize && index == 0 || count == maxSize && index != 0 {
            array[index] = element
        } else if index == 0 && count != maxSize {
            array.append(defaultValue)
            count += 1

            for i in (index+1..<count).reversed() {
                array[i] = array[i - 1]
            }

            array[index] = element
        } else {
            array.append(defaultValue)
            count += 1

            for i in (index..<count).reversed() {
                array[i] = array[i - 1]
            }

            array[index] = element

        }
    }

    // Delete from end of array
    public mutating func deleteFromEnd() {
        assert(count > 0)
        array.removeLast()
        count -= 1
    }

    // Delete at index of array
    public mutating func removeAt(index: Int) -> T {
        assert(index >= 0)
        assert(index < count)
        count -= 1
        let result = array[index]
        array.remove(at: index)
        return result
    }

    // Remove all elements
    public mutating func removeAll() {
        for _ in 0..<count {
            array.removeLast()
            count -= 1
        }
        count = 0
    }

    subscript(index: Int) -> T {
        assert(index >= 0)
        assert(index < count)
        return array[index]
    }
}

Conclusion

Thank you for reading. If you're looking for more articles about computer science and software engineering, give these a read:

• Rotate Arrays in Swift by Steven Curtis
• CS Data Structures: 2D Array
• Computer Science: Recursion
• The Concept of Coupling