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 — 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. it does not change. Below is an array in C++ that holds 15 integers. The elements of the array are placed in a contiguous block of memory: foo [ ]; int 15 When working with fixed arrays, it’s important to be precise and understand 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. why 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 . Another quick operation is finding an element by the index, also a . 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. O(1) constant time complexity To add the number 5 to a fixed array: 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. Something to note; Furthermore, deleting an element from the array is the same process, but reversed. The elements are moved from 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 building 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: A max size to ensure it doesn’t grow past what the use case needs. A default value (this will be used to add an item to the array when needed). An internal array (in this case, it’s a ). Swift array The count (which is updated each time an element is removed or added to the array). Two public properties that return information. The first being the elements within the array, and the second being the length of the array. is not directly used to return the array’s length (e.g., ) because it is private. It is private because in this use case, tracking the number of elements in an array with a counter and then reading the property is faster than directly calling the internal method on the array; which traverses through each element, then returns the number of elements in the array. count fixedArray.count count count struct FixedArray<T> { private maxSize: Int private defaultValue: T private array = [T]() private count = public elements: [T] { array } public length: Int { count } public init(maxSize: Int, : T) { self.maxSize = maxSize self.defaultValue = defaultValue array = .init() } } var var var var 0 var return var return defaultValue The initializer sets the max amount of elements to be allowed in the array, along with the ‘default value’ of the array. is used to add a default object to the array when appending new objects. This will be seen in the method. defaultValue insert The other thing to add in the Swift implementation of a Fixed Array is a custom subscript. In Swift, you can add to Structs, Classes, and Enumerations in order to access the elements of a collection, list, or sequence. custom subscripts struct FixedArray<T> { private maxSize: Int private defaultValue: T private array = [T]() private count = public elements: [T] { array } public length: Int { count } public init(maxSize: Int, : T) { self.maxSize = maxSize self.defaultValue = defaultValue array = .init() } subscript(index: Int) -> T { assert(index >= ) assert(index < count) array[index] } } var var var var 0 var return var return defaultValue 0 return When a fixed array is initialized, it is empty. This can be seen by using the and properties. elements length array = FixedArray<Int>(maxSize: , : ) array.elements array.length var 6 defaultValue 0 // [] // 0 Adding Functionality to the Array As noted in the section of this article, fixed arrays should be able to: Fixed Array Operations 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 and it will do just that — add an element to the end of the array. Before the method adds the element, it uses to make sure is less than . If 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, . appendToEnd() assert count maxSize count check out the official Apple Documentation public mutating func appendToEnd(element: T) { assert(count < maxSize) array.append(element) count += } // Append to end of array 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: The is 0, and the 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. index count The is equal to and the is 0 OR the is equal to and the 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 ensures that no new elements are added to the array when trying to insert them when the array is full. count maxSize index count maxSize index The is 0, and is not equal to . 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 in one space to the right. Remember that the value of 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. index count maxSize index 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 . A visualization of this can be seen earlier in this article; under the section. index Fixed Array Operations public mutating func insert(element: T, at index: Int) { assert(index >= ) assert(index < maxSize) index == && count == { array.append(element) count += } count == maxSize && index == || count == maxSize && index != { array[index] = element } index == && count != maxSize { array.append(defaultValue) count += i (index+ .<count).reversed() { array[i] = array[i - ] } array[index] = element } { array.append(defaultValue) count += i (index..<count).reversed() { array[i] = array[i - ] } array[index] = element } } // Insert at index of array 0 if 0 0 1 else if 0 0 else if 0 1 for in 1. 1 else 1 for in 1 The Fixed Array now looks like this: struct FixedArray<T> { private maxSize: Int private defaultValue: T private array = [T]() private count = public elements: [T] { array } public length: Int { count } public init(maxSize: Int, : T) { self.maxSize = maxSize self.defaultValue = defaultValue array = .init() } public mutating func appendToEnd(element: T) { assert(count < maxSize) array.append(element) count += } public mutating func insert(element: T, at index: Int) { assert(index >= ) assert(index < maxSize) index == && count == { array.append(element) count += } count == maxSize && index == || count == maxSize && index != { array[index] = element } index == && count != maxSize { array.append(defaultValue) count += i (index+ .<count).reversed() { array[i] = array[i - ] } array[index] = element } { array.append(defaultValue) count += i (index..<count).reversed() { array[i] = array[i - ] } array[index] = element } } } var var var var 0 var return var return defaultValue // Append to end of array 1 // Insert at index of array 0 if 0 0 1 else if 0 0 else if 0 1 for in 1. 1 else 1 for in 1 To start adding elements to the array, use either the or methods. Here, the integers , , and are added to the end of the array. Then, is inserted at the 3rd index, is inserted at the 4th index, and is inserted at the 3rd index. The array ends upholding . appendToEnd insert 1 2 3 5 6 4 [1, 2, 3, 4, 5, 6] array.appendToEnd(element: ) array.appendToEnd(element: ) array.appendToEnd(element: ) array.elements array.insert(element: , : ) array.elements array.insert(element: , : ) array.elements array.insert(element: , : ) array.elements 1 2 3 // [1, 2, 3] 5 at 3 // [1, 2, 3, 5] 6 at 4 // [1, 2, 3, 5, 6] 4 at 3 // [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: Remove the element at the end of the array. Remove the item based on a given index. Remove all of the items in the array. To delete an item from the end, simply make sure that is greater than 0, use the method on the array and decrement 1 from . count removeLast count public mutating func deleteFromEnd() { assert(count > ) array.removeLast() count -= } // Delete from end of array 0 1 Removing an element based on a given index is a bit trickier. The must be less than or equal to 0, and it must also be less than the value of . After these assertions pass, is decremented by 1, the element at the given index is obtained in and the function of the Swift array is called with index as its parameter. Finally, the element that is stored in is returned. index count count result remove result public mutating func removeAt(index: Int) -> T { assert(index >= ) assert(index < count) count -= result = array[index] array.remove(at: index) result } // Delete at index of array 0 1 let return Below is the usage of these two methods. The method does not return the element that is removed, but the method does. How they are used is up to the programmer. deleteFromEnd removeAt array.deleteFromEnd() array.elements array.removeAt(index: ) array.elements // [1, 2, 3, 4, 5] 1 // Returns 2 // [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 , removes the last element and decrements by 1. Once it processes the array, it then sets to 0. count count count public mutating func removeAll() { _ .<count { array.removeLast() count -= } count = } // Remove all elements for in 0. 1 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 , a return type must be defined. This is expected, as subscripts return elements. Here is the subscript again: subscript in Swift subscript(index: Int) -> T { assert(index >= ) assert(index < count) array[index] } 0 return Imagine that holds . Here is how an element would be accessed: array [1, 2, 3, 4, 5, 6] print(array.element) firstElement = array[ ] fourthElement = array[ ] print(firstElement) print(fourthElement) // [1, 2, 3, 4, 5, 6] let 0 let 3 // 1 // 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 ( 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. bytes are a storage unit in computing Below is the complete Fixed Array in Swift, using a : generic type struct FixedArray<T> { private maxSize: Int private defaultValue: T private array = [T]() private count = public elements: [T] { array } public length: Int { count } public init(maxSize: Int, : T) { self.maxSize = maxSize self.defaultValue = defaultValue array = .init() } public mutating func appendToEnd(element: T) { assert(count < maxSize) array.append(element) count += } public mutating func insert(element: T, at index: Int) { assert(index >= ) assert(index < maxSize) index == && count == { array.append(element) count += } count == maxSize && index == || count == maxSize && index != { array[index] = element } index == && count != maxSize { array.append(defaultValue) count += i (index+ .<count).reversed() { array[i] = array[i - ] } array[index] = element } { array.append(defaultValue) count += i (index..<count).reversed() { array[i] = array[i - ] } array[index] = element } } public mutating func deleteFromEnd() { assert(count > ) array.removeLast() count -= } public mutating func removeAt(index: Int) -> T { assert(index >= ) assert(index < count) count -= result = array[index] array.remove(at: index) result } public mutating func removeAll() { _ .<count { array.removeLast() count -= } count = } subscript(index: Int) -> T { assert(index >= ) assert(index < count) array[index] } } var var var var 0 var return var return defaultValue // Append to end of array 1 // Insert at index of array 0 if 0 0 1 else if 0 0 else if 0 1 for in 1. 1 else 1 for in 1 // Delete from end of array 0 1 // Delete at index of array 0 1 let return // Remove all elements for in 0. 1 0 0 return 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 Also published on Medium's andrew-lundy
