Some codes and contents are sourced from Apple’s official documentation, educative.io and mozilla. This post is for personal notes where I summarize the original contents to grasp the key concepts(🎨 some images I draw it)
URLSession
The URLSession class and related classes provide an API for downloading data from and uploading data to endpoints indicated by URLs. Your app can also use this API to perform background downloads when your app isn’t running or, in iOS, while your app is suspended.
Your app creates one or more URLSession instances, each of which coordinates a group of related data-transfer tasks. For example, if you’re creating a web browser, your app might create one session per tab or window, or one session for interactive use and another for background downloads. Within each session, your app adds a series of tasks, each of which represents a request for a specific URL (following HTTP redirects, if necessary).
Type of URL Sessions
URLSession has a singleton shared session (which doesn’t have a configuration object) for basic requests. It’s not as customizable as sessions you create, but it serves as a good starting point if you have very limited requirements. You access this session by calling the shared class method. For other kinds of sessions, you create a URLSession with one of three kinds of configurations:
A default session behaves much like the shared session, but lets you configure it. You can also assign a delegate to the default session to obtain data incrementally.
Ephemeral sessions are similar to shared sessions, but don’t write caches, cookies, or credentials to disk.
Background sessions let you perform uploads and downloads of content in the background while your app isn’t running.
Types of URL session tasks
Data tasks send and receive data using NSData objects. Data tasks are intended for short, often interactive requests to a server.
Upload tasks are similar to data tasks, but they also send data (often in the form of a file), and support background uploads while the app isn’t running.
Download tasks retrieve data in the form of a file, and support background downloads and uploads while the app isn’t running.
WebSocket tasks exchange messages over TCP and TLS, using the WebSocket protocol defined in RFC 6455.
The session object keeps a strong reference to the delegate until your app exits or explicitly invalidates the session. If you don’t invalidate the session, your app leaks memory until the app terminates.
URLSessionprovidesstatus and progress properties. Query these properties if you need to make programmatic decisions based on the current state of the task (with the caveat that its state can change at any time).
Protocol supports
he URLSession class natively supports the data, file, ftp, http, and https URL schemes, with transparent support for proxy servers and SOCKS gateways, as configured in the user’s system preferences.
URLSession supports the HTTP/1.1, HTTP/2, and HTTP/3 protocols. HTTP/2 support, as described by RFC 7540, requires a server that supports Application-Layer Protocol Negotiation (ALPN).
You can also add support for your own custom networking protocols and URL schemes (for your app’s private use) by subclassing URLProtocol.
iOS 9.0 and macOS 10.11 and later use App Transport Security (ATS) for all HTTP connections made with URLSession. ATS requires that HTTP connections use HTTPS (RFC 2818).
There are various ways to communicate with a server. In my experience, these methods can often be combined with others, such as APNS (Apple Push Notification Service).
Some codes and contents are sourced from Apple’s official documentation. This post is for personal notes where I summarize the original contents to grasp the key concepts
hitTest
Returns the farthest descendant in the view hierarchy of the current view, including itself, that contains the specified point.
Return value
The view object that’s the farthest descendent of the current view and contains point. Returns nilif the point lies completely outside the view hierarchy of the current view.
This method traverses the view hierarchy by calling the point(inside:with:) method of each subview to determine which subview to send a touch event to. If point(inside:with:) returns true, this method continues to traverse the subview hierarchy until it finds the frontmost view that contains the specified point. If a view doesn’t contain the point, this method ignores its branch of the view hierarchy. You rarely need to call this method yourself, but you might override it to hide touch events from subviews.
This method ignores view objects that are hidden, that have disabled user interactions, or that have an alpha level less than 0.01. This method doesn’t take the view’s content into account when determining a hit, so it can return a view even if the specified point is in a transparent portion of that view’s content.
This method doesn’t report points that lie outside the view’s bounds as hits, even if they actually lie within one of the view’s subviews. This situation can occur if the view’s clipsToBounds property is false and the affected subview extends beyond the view’s bounds.
Note
When the system calls this method to perform hit-testing for event routing, it expects the resulting view to be part of a UIWindow hierarchy.
class ViewController: UIViewController {
@IBOutlet weak var blueView: UIView!
@IBOutlet weak var greenView: UIView!
@IBOutlet weak var redView: UIView!
override func viewDidLoad() {
super.viewDidLoad()
// Do any additional setup after loading the view.
let tapGesture = UITapGestureRecognizer(target: self, action: #selector(didTap))
view.addGestureRecognizer(tapGesture)
}
@objc func didTap(_ recognizer: UITapGestureRecognizer) {
let point = recognizer.location(in: view)
let farthestView = view.hitTest(point, with: nil)
let viewTag = farthestView?.tag
guard let viewTag else {
return
}
switch viewTag {
case 0:
print("BlueView")
case 1:
print("GreenView")
case 2:
print("RedView")
default:
break
}
}
}
When you tap the center of rectangle, It prints RedView because It’s the farthest view.
point(inside:with:)
Returns a Boolean value indicating whether the receiver contains the specified point. by Apple Document
point
A point that is in the receiver’s local coordinate system (bounds).event
The event that warranted a call to this method. If you are calling this method from outside your event-handling code, you may specify nil.
Let’s test.
@objc func didTap(_ recognizer: UITapGestureRecognizer) {
let point = recognizer.location(in: view)
let isPointInsideBlueView = blueView.point(inside: point, with: nil) //false
let isPointInsideGreenView = greenView.point(inside: point, with: nil) //false
let isPointInsideRedView = redView.point(inside: point, with: nil) //false
print(point)
print(blueView.bounds)
}
I changed UIView(Blue, Green, and Red) to CustomView to check hitTest and point(inside: CGPoint, with: event)
In fact, when pass the UITapGestureRecognizer’s point which is view based coordinates converted to subview’s coordinates.
//Point: UITapGestureRecognizer's point based on viewController's view
let point = recognizer.location(in: view)
//convert it to redView's coordinates (bounds)
let convertedPoint = view.convert(point, to: redView)
Summary
hitTest itself calls point(inside:) function to check is bounds contains point or not. It uses Depth First Search.
If point(inside:with:) returns true, this method continues to traverse the subview hierarchy until it finds the frontmost view that contains the specified point.
Some codes are sourced from Loony Corn’s Udemy Course (https://www.udemy.com/user/janani-ravi-2/). This post is for personal notes where I summarize the original contents to grasp the key concepts
Warming up, Recursive sense
Iterative solutions involve loops
Recursive solutions involve function that call themselves
A recursively written function takes in input, splits that input into smaller parts. Then calls itself on the smaller parts and re-combines the outputs
If the inputs to the function are too simple to split further, the recursive function will return a simple output (and not call itself)
Base case of the recursion (It prevents the recursion from going on forever)
func reverseStringIteratively(input: String) -> String {
if input.count == 1 || input.isEmpty {
return input
}
var inputArray = Array(input)
for i in 0..<input.count {
let firstIndex = i
let lastIndex = (input.count - 1) - i
if firstIndex == lastIndex {
break
}
inputArray.swapAt(firstIndex, lastIndex)
}
return String(inputArray)
}
reverseStringIteratively(input: "2AB") //BA2
Recursion approach
func reverseStringRecursively(input: String) -> String {
//Base case
if input.count == 1 || input.isEmpty {
return input
}
var inputArray = Array(input)
let first = inputArray.removeFirst()
let reversedString = reverseStringRecursively(input: String(inputArray))
return reversedString + String(first)
}
reverseStringRecursively(input: "2AB") //BA2
Exercise 1. Binary Search
Choose an element in at the mid point of a sorted list
Check whether it’s smaller than or greater than the element you are looking for
If the element at the mid point is larger than the element you are searching for
Reduce your search area to the portion where the element might be present
Base case
There is no part of the list to search and the element has not been found
The search element has been found at the mid point of the portion we’re searching
Recursive case
Binary search smaller portions of the list where the element might be found
Summary
By halving the search area at every step, binary search works much fatser than linear search
The complexity of binary search is O(logN)
The Iterative approach to binary search might perform better than the recursive approach in terms of space complexity. There is not recursive stack in the iterative approach, which means we save on some space.
Example 1. No boundary, Assumed that You will search entire input ranges
let input = Array(0...10000)
/// Return : Index
func binarySearch(input: [Int], search: Int) -> Int {
if input.isEmpty {
return -1
}
let midPoint = (input.count - 1) / 2
if input[midPoint] == search {
return input[midPoint]
}
if search > input[midPoint] {
return binarySearch(input: Array(input[midPoint..<input.count]), search: search)
}
else {
return binarySearch(input: Array(input[0..<midPoint]), search: search)
}
}
let searchedItem = binarySearch(input: input, search: 2859)
Example 2. Boundary search
let input = Array(0...10000)
/// Return : Index
/// min, max: Search Area in Input
func binarySearch(input: [Int], search: Int, min: Int, max: Int) -> Int {
//If the indices have crossed one another at the center, the term is not present in the array, return -1, base case of the recursion
if min > max {
return -1
}
let midPoint = min + (max - min) / 2
if input[midPoint] == search {
return input[midPoint]
}
//Call binary search on a smaller portion of the array depending on whether the element might be found in the first or second half of the list
if search > input[midPoint] {
return binarySearch(input: input, search: search, min: midPoint + 1, max: max)
}
else {
return binarySearch(input: input, search: search, min: min, max: midPoint - 1)
}
}
let searchedItem = binarySearch(input: input, search: 2859, min: 2800, max: 2900)
print(searchedItem)
Exercise 2. Find all subsets of a given set
Example, {1, 2, 3, 4}
There are 2^4 subsets of this set, If we have a set of N elements the number of subsets will be 2^N
At subsets, order is not important!
Recursive mind (Find a pattern!)
Break this down, 1 element {1} -> subsets are {}, {1}
2 elements {1, 2} -> subsets are {}, {1}, {2}, {1, 2}
Exercise 4. Build a car given all tasks and each task’s dependencies
Tip (It’s the same, How OperationQueue works, see my post)
Set up the data structure that you plan to use to store a tasks and it’s dependencies
Dependencies of Task “A” are all tasks which should be complete before “A” can execute.
Paint a car, depends on build chassis of the car, The chassis needs to be ready before it can be painted
The method should take in a list of all tasks which are needed to build a car along with their dependencies and execute every task in order to build the car
The tasks are in any order, It’s up to you to determine some order in which it can be executed.
Tasks and dependencies
Tasks are A, B, C, D, E, F, G, H
B depends on A
D depends on E
C depends on A, B, D
F depends on C
An acceptable order of performing the tasks are
E-> D -> A -> B -> C -> F
or A -> E -> B -> D -> C -> F
and more
Remember
Remember that you can’t execute a task unless it’s dependencies have completed
Store the dependencies such that they are easily accessible from a task
Recursively execute the dependencies till you get to the task
Base case
The current task has been executed, it’s marked done
Recursive case
Execute dependencies before coming to the current task
Notes
The tasks and it’s dependencies form a directed acyclic graph
The graph may not be fully connected, I.E. certain tasks stand completely alone.
It’s a topological sort.
We have to visit every task to execute it, the complexity is O(N), where N is the number of tasks.
class TaskQueue {
let value: String
var dependsOn = [TaskQueue]()
var isFinished = false
init(value: String) {
self.value = value
}
}
let taskA = TaskQueue(value: "A")
let taskB = TaskQueue(value: "B")
let taskC = TaskQueue(value: "C")
let taskD = TaskQueue(value: "D")
let taskE = TaskQueue(value: "E")
let taskF = TaskQueue(value: "F")
let taskG = TaskQueue(value: "G")
let taskH = TaskQueue(value: "H")
taskB.dependsOn = [taskA]
taskD.dependsOn = [taskE]
taskC.dependsOn = [taskA, taskB, taskD]
taskF.dependsOn = [taskC]
func buildCar(_ tasks: [TaskQueue]) {
//Base case
if tasks.isEmpty {
return
}
var remainingTasks = tasks
let dequeue = remainingTasks.removeFirst()
if dequeue.isFinished {
return buildCar(remainingTasks)
}
//[a, b, c]
// a: finish return
//Recursive case
let dependsOnUnfinishedTasks = dequeue.dependsOn.filter { $0.isFinished == false }
if !dependsOnUnfinishedTasks.isEmpty {
buildCar(dependsOnUnfinishedTasks)
}
dequeue.isFinished = true
print("\(dequeue.value)", terminator: "->")
return buildCar(remainingTasks)
}
buildCar([taskA, taskB, taskC, taskD, taskE, taskF, taskG, taskH])
//Prints
A->B->E->D->C->F->G->H
Example 2. Simplify version
class TaskQueue {
let value: String
var dependsOn = [TaskQueue]()
var isFinished = false
init(value: String) {
self.value = value
}
func run() {
if isFinished {
return
}
//Before run, recursively call run on all the dependencies of this task
for task in dependsOn {
task.run()
}
isFinished = true
print("Completed task: \(value)")
}
}
let taskA = TaskQueue(value: "A")
let taskB = TaskQueue(value: "B")
let taskC = TaskQueue(value: "C")
let taskD = TaskQueue(value: "D")
let taskE = TaskQueue(value: "E")
let taskF = TaskQueue(value: "F")
let taskG = TaskQueue(value: "G")
let taskH = TaskQueue(value: "H")
taskB.dependsOn = [taskA]
taskD.dependsOn = [taskE]
taskC.dependsOn = [taskA, taskB, taskD]
taskF.dependsOn = [taskC]
func runTask(_ tasks: [TaskQueue]) {
for task in tasks {
task.run()
}
}
runTask([taskA, taskB, taskC, taskD, taskE, taskF, taskG, taskH])
//Prints
Completed task: A
Completed task: B
Completed task: E
Completed task: D
Completed task: C
Completed task: F
Completed task: G
Completed task: H
Exercise 5. Generate anagrams of a Word
Anagrams
A word have all the same letters of the word itself in a different order
Consider that the letters in the word passed in are unique and that there are no spaces. I.E. It’s a word not a sentence
The anagram need not be a valid word, we just want all the permutations of the letters.
If all letters are unique then there are N! anagrams.
Example
“ROAD” -> 4! Anagrams
“ROAD”, “ORAD”, “OARD”, “RDOA”, “RAOD”, …more!
Hint
Basic idea is the same as finding a all subsets from given a string
Break this down! (Finding a patterns!)
Consider a word of 1 letter “A” -> Anagrams are “A”
Consider a word of 2 letters “AB” -> Anagrams are “AB“, “BA”
Consider a word of 3 letters “ABC” -> Anagrams are “CAB”, “ACB”, “ABC“, “CBA”, “BCA”, “BAC“
Break the word into smaller and smaller words, till we find the anagram of the smallest word.
To the smaller anagrams add in letter by letter at every possible positions
Recursively do this till we get all the letters in at every position
Base case
The anagram of an empty string is an empty string
The smallest word of one letter is the anagram itself
Recursive case
Find anagrams of smaller words by removing letters from the original word
Add the letters back one by one to every position
Complexity
The number of anagrams for a word with unique letter is N! which means the complexity of this algorithm is also O(N!)
import Foundation
//https://github.com/ShawnBaek/Table
import Table
//0: Empty, 1: Queen
var chessBoard = Array(
repeating: Array(repeating: 0, count: 8),
count: 8
)
func isSafeOnLeftDiagonal(chess: [[Int]], row: Int, col: Int) -> Bool {
var r = 0
var c = 0
//Find the initial position tracing the left diagonal from the first cell in the line of the placed queen
if row > col {
r = row - col
}
else {
c = col - row
}
let columns = chess.first?.count ?? 0
let rows = chess.count
var numberOfQueen = 0
while r < rows && c < columns {
if chess[r][c] == 1 {
numberOfQueen += 1
}
r += 1
c += 1
}
return numberOfQueen <= 1
}
func isSafeOnRightDiagonal(chess: [[Int]], row: Int, col: Int) -> Bool {
let columns = chess.first?.count ?? 0
let rows = chess.count
//Start position will be top right based on current position
var r = 0
var c = columns - 1
var numberOfQueens = 0
//Option 1. I suggest calculating it and checking the start position
if (row + col < columns) {
c = min(row + col, columns - 1)
}
else {
r = (row + col) % (columns - 1)
}
while r < rows && c > 0 {
if chess[r][c] == 1 {
numberOfQueens += 1
}
r += 1
c -= 1
}
return numberOfQueens <= 1
}
func isSafePosition(chess: [[Int]], row: Int, col: Int) -> Bool {
let columns = chess.first?.count ?? 0
let rows = chess.count
//Edge case
if col < 0 || col >= columns {
return false
}
if row < 0 || row >= rows {
return false
}
//Check horizontal
for c in 0..<columns {
//Found a Queen and It's not a current position of Queen
if chess[row][c] == 1, c != col {
return false
}
}
//Check vertical
for r in 0..<rows {
if chess[r][col] == 1, r != row {
return false
}
}
//Check TopLeft -> DownRight Diagonal
if !isSafeOnLeftDiagonal(chess: chess, row: row, col: col) {
return false
}
if !isSafeOnRightDiagonal(chess: chess, row: row, col: col) {
return false
}
return true
}
func placeQueen(
chess: inout [[Int]],
col: Int
) -> Bool {
//Base case, Placed all Queens
if col >= 8 {
return true
}
for row in 0..<8 {
//Place a Queen
chess[row][col] = 1
if isSafePosition(chess: chess, row: row, col: col) {
if placeQueen(chess: &chess, col: col + 1) {
return true
}
}
//Remove Queen at this position
chess[row][col] = 0
}
return false
}
let isPlacedAllQueens = placeQueen(chess: &chessBoard, col: 0)
print(table: chessBoard)
Results
Time Complexity is O(N!), We’re trying every possible position for the queens
Some codes and contents are sourced from The Clean Code Blog official documentation, The iOS Interview Guide Book, Head First Design Patterns 2nd, theswiftdev.com, and Wiki Pedia. This post is for personal notes where I summarize the original contents to grasp the key concepts
Clean Architecture
The Dependency Rule always applies. Source code dependencies always point inwards. As you move inwards the level of abstraction increases. The outermost circle is low level concrete detail. As you move inwards the software grows more abstract, and encapsulates higher level policies. The inner most circle is the most general by cleancoder.com
Independent of Frameworks. The architecture does not depend on the existence of some library of feature laden software. This allows you to use such frameworks as tools, rather than having to cram your system into their limited constraints.
Testable. The business rules can be tested without the UI, Database, Web Server, or any other external element.
Independent of UI. The UI can change easily, without changing the rest of the system. A Web UI could be replaced with a console UI, for example, without changing the business rules.
Independent of Database. You can swap out Oracle or SQL Server, for Mongo, BigTable, CouchDB, or something else. Your business rules are not bound to the database.
Independent of any external agency. In fact your business rules simply don’t know anything at all about the outside world
The overriding rule that makes this architecture work is The Dependency Rule. This rule says that source code dependencies can only point inwards. Nothing in an inner circle can know anything at all about something in an outer circle.
Entities
Entities encapsulate Enterprise wide business rules. An entity can be an object with methods, or it can be a set of data structures and functions. It doesn’t matter so long as the entities could be used by many different applications in the enterprise
If you don’t have an enterprise, and are just writing a single application, then these entities are the business objects of the application. They encapsulate the most general and high-level rules. They are the least likely to change when something external changes. For example, you would not expect these objects to be affected by a change to page navigation, or security. No operational change to any particular application should affect the entity layer.
My comments
ViewModel can be a Entities
Use Cases
The software in this layer contains application specific business rules. It encapsulates and implements all of the use cases of the system. These use cases orchestrate the flow of data to and from the entities, and direct those entities to use their enterprise wide business rules to achieve the goals of the use case.
We do not expect changes in this layer to affect the entities. We also do not expect this layer to be affected by changes to externalities such as the database, the UI, or any of the common frameworks. This layer is isolated from such concerns.
Interface Adapters
The software in this layer is a set of adapters that convert data from the format most convenient for the use cases and entities, to the format most convenient for some external agency such as the Database or the Web. It is this layer, for example, that will wholly contain the MVC architecture of a GUI. The Presenters, Views, and Controllers all belong in here. The models are likely just data structures that are passed from the controllers to the use cases, and then back from the use cases to the presenters and views.
Frameworks and Drivers
The outermost layer is generally composed of frameworks and tools such as the Database, the Web Framework, etc. Generally you don’t write much code in this layer other than glue code that communicates to the next circle inwards.
Crossing boundaries.
At the lower right of the diagram is an example of how we cross the circle boundaries. It shows the Controllers and Presenters communicating with the Use Cases in the next layer. Note the flow of control. It begins in the controller, moves through the use case, and then winds up executing in the presenter. Note also the source code dependencies. Each one of them points inwards towards the use cases.
For example, consider that the use case needs to call the presenter. However, this call must not be direct because that would violate The Dependency Rule: No name in an outer circle can be mentioned by an inner circle. So we have the use case call an interface (Shown here as Use Case Output Port) in the inner circle, and have the presenter in the outer circle implement it.
I redraw the Clean Architecture
As my understanding, Clean Architecture is guidance that app can be separated by layers. There are boundaries between layers
App can have multiple layers like below (by The iOS Interview Guide)
Service Layer
UI Layer
Storage Layer
Business Logic Layer
This Image I added layers and informations which can be related to from the original clean architecture diagram.
VIPER Architecture, It’s iOS version of Clean Architecture
View: displays what it is told to by the Presenter and relays user input back to the Presenter.
Interactor: contains the business logic as specified by a use case.
Presenter: contains view logic for preparing content for display (as received from the Interactor) and for reacting to user inputs (by requesting new data from the Interactor).
Entity: contains basic model objects used by the Interactor.
Routing: contains navigation logic for describing which screens are shown in which order.
Class / Module should have only one responsibility and reason to change. Avoid changing a class if possible. This principle is related to cohesion. If you follow this principle, You can easily maintain a class than a class which has multiple responsibility.
If class have multiple responsibility, There is multiple reason to change it. It makes hard to maintaining.
O, Open-Closed Principle
Class opens for extension but closed for modification. It sounds complicated when I read this principle.
Opens for extension. It means without modification, class can be extended. There is many way to extension. The purpose is adding a new functionalities without changing the existing codes / logics. (by Head First Design Patterns 2nd)
For example, Observer pattern, you can add a new observer without changing a existing code. You can also follow this principle by adopting decoration pattern. Abstraction is also good for following this principle. Important thing is choosing which parts will be changed and separate it. (by Head First Design Pattens 2nd)
Also you can extend objects through inheritance, polymorphism, and composition by implementing them using interfaces, abstractions, and dependency injection. (by The iOS Interview Guide book)
L, Liskov Substitution Principle
An object (such as a class) may be replaced by a sub-object (such as a class that extends the first class) without breaking the program
Let say you have a class T. And you have a class S that inheritance from T. Your program could allow to replace T with S without breaking it.
Or you can think usecase protocol. You have a protocol and struct or class which conforms to usecase protocol. And You can inject that protocol type in ViewModel. In this case your program can allow to replace the injecting objects with the others that conforms to usecase protocol without breaking it.
Sub-Type: Subclass or Conforms to Protocol
Super-Type: Super class or high level protocol
I, Interface Segregation Principle
No code should be forced to depend on methods it does not use.[1] ISP splits interfaces that are very large into smaller and more specific ones so that clients will only have to know about the methods that are of interest to them. Such shrunken interfaces are also called role interfaces. (by Wikipedia)
If you familiar with protocol oriented programming, You can easily understand what is meaning.
This principle is introduced at chapter 1, Head First Design Patterns 2nd
Example is making a Duck class. There are protocols that has multiple methods. Like a FlyBehavior and QuackBehavior. Separating the interfaces prevents the problem like RubberDuck class doesn’t need to implement FlyBehavior because It can’t fly. That interface doesn’t need.
In a Head First Design Patterns book, author suggested creating a FlyNoWay class that conforms to FlyBehavior protocol.
Tips for following this principle (by Head First Design Patterns 2nd)
Don’t save concrete class’s reference using variable
Create a class that conforms to protocol (Don’t create a class by inheritance from concrete class)
Don’t override function that already implemented at base class. (Base class’s function should be defined that can be sharable for all the subclasses)
It is useful for writing unit testing.
With the addition of an abstract layer, both high- and lower-level layers reduce the traditional dependencies from top to bottom. Nevertheless, the “inversion” concept does not mean that lower-level layers depend on higher-level layers directly. Both layers should depend on abstractions(interfaces) that expose the behavior needed by higher-level layers.
In a direct application of dependency inversion, the abstracts are owned by the upper/policy layers. This architecture groups the higher/policy components and the abstractions that define lower services together in the same package. The lower-level layers are created by inheritance/implementation of these abstract classes or interfaces.[1]
The inversion of the dependencies and ownership encourages the re-usability of the higher/policy layers. Upper layers could use other implementations of the lower services. When the lower-level layer components are closed or when the application requires the reuse of existing services, it is common that an Adapter mediates between the services and the abstractions.
Some codes and contents are sourced from Apple’s official documentation. This post is for personal notes where I summarize the original contents to grasp the key concepts
Increasing Performance by Reducing Dynamic Dispatch
Swift allows a class to override methods and properties declared in its superclasses. This means that the program has to determine at runtime which method or property is being referred to and then perform an indirect call or indirect access. This technique, called dynamic dispatch, increases language expressivity at the cost of a constant amount of runtime overhead for each indirect usage. In performance sensitive code such overhead is often undesirable. This blog post showcases three ways to improve performance by eliminating such dynamism: final, private, and Whole Module Optimization.
class ParticleModel {
var point = ( 0.0, 0.0 )
var velocity = 100.0
func updatePoint(newPoint: (Double, Double), newVelocity: Double) {
point = newPoint
velocity = newVelocity
}
func update(newP: (Double, Double), newV: Double) {
updatePoint(newP, newVelocity: newV)
}
}
var p = ParticleModel()
for i in stride(from: 0.0, through: 360, by: 1.0) {
//dynamically dispatched call
p.update((i * sin(i), i), newV:i*1000)
}
As written, the compiler will emit a dynamically dispatched call to:
Call update on p.
Call updatePoint on p.
Get the property point tuple of p.
Get the property velocity of p.
The dynamic calls are necessary because a subclass of ParticleModel might override point or velocity with a computed property or override updatePoint() or update() with new implementations.
In Swift, dynamic dispatch calls are implemented by looking up a function from a method table and then performing an indirect call. This is slower than performing a direct call. Additionally, indirect calls also prevent many compiler optimizations, making the indirect call even more expensive. In performance critical code there are techniques you can use to restrict this dynamic behavior when it isn’t needed to improve performance.
Apple
Use final keyword
class ParticleModel {
final var point = ( x: 0.0, y: 0.0 )
final var velocity = 100.0
final func updatePoint(newPoint: (Double, Double), newVelocity: Double) {
point = newPoint
velocity = newVelocity
}
//This function performing a indirect call because no final keyword
func update(newP: (Double, Double), newV: Double) {
updatePoint(newP, newVelocity: newV)
}
}
/*
It is possible to mark an entire class as final by attaching the attribute to the class itself. This forbids subclassing the class, implying that all functions and properties of the class are final as well.
*/
final class ParticleModel {
var point = ( x: 0.0, y: 0.0 )
var velocity = 100.0
// ...
}
Some codes and contents are sourced from Apple’s official documentation. This post is for personal notes where I summarize the original contents to grasp the key concepts
Life cycle
I checked what functions are called when first launches, enter background, foreground and terminated.
figure shows the state transitions for scenes. When the user or system requests a new scene for your app, UIKit creates it and puts it in the unattached state. User-requested scenes move quickly to the foreground, where they appear onscreen. A system-requested scene typically moves to the background so that it can process an event. For example, the system might launch the scene in the background to process a location event. When the user dismisses your app’s UI, UIKit moves the associated scene to the background state and eventually to the suspended state. UIKit can disconnect a background or suspended scene at any time to reclaim its resources, returning that scene to the unattached state.
When UIKit connects a scene to your app, configure your scene’s initial UI and load the data your scene needs.
Upon entering the background state, finish crucial tasks, free up as much memory as possible, and prepare for your app snapshot. See Preparing your UI to run in the background.
At scene disconnection, clean up any shared resources associated with the scene.
Creates the application object and the application delegate and sets up the event cycle.
This function instantiates the application object from the principal class and instantiates the delegate (if any) from the given class and sets the delegate for the application. It also sets up the main event loop, including the application’s run loop, and begins processing events. If the application’s Info.plist file specifies a main nib file to be loaded, by including the NSMainNibFile key and a valid nib file name for the value, this function loads that nib file.
Despite the declared return type, this function never returns.
Restoration occurs during the middle of your app’s initialization, and it proceeds only when a state restoration archive is available and your app delegate’s application(_:shouldRestoreApplicationState:) method returns true.
Some codes are sourced from Loony Corn’s Udemy Course (https://www.udemy.com/user/janani-ravi-2/). This post is for personal notes where I summarize the original contents to grasp the key concepts
What is Linked List
It is a list data structure where each element in the list holds some information and points to where the next element lies.
Linked List vs Arrays
Linked List
List sizes are unlimited, you don’t need to know up front how many elements will be added to the linked list, the size of the linked list can grow dynamically
Inserting a new element in a linked list is a very easy operation, the logical next pointers have to be reassigned but not much else needs to be done
Similarly deleting an element in a list is very easy and efficient
Random access to an element at a specific index in the linked list is not possible. The entire list up-to that element has to be traversed
Each element requires additional space to store a pointer to the next element
Cannot take advantage of spatial locality (for caching) when accessing the elements
Each element can live pretty much anywhere in memory and be pointed to
Arrays
Arrays have to be declared upfront with the number of elements it will hold, the size of array cannot be increased dynamically <- In Swift, You can increase size, You can read details at Apple Document – Growing the Size of an Array
Arrays are located in contiguous memory locations, in order to insert an element, the elements to it’s right have to move over to make room for it. It is a more heavyweight operation.
Array elements have to be moved in the case of deletion as well
Arrays provide very quick lookup for elements at specific indices, since they are in contiguous memory locations, we know exactly where in memory the element is
No extra space is required other than for the actual elements which make up the array
As elements are in contiguous memory locations access to arrays takes significant advantage of spatial locality in caches
This can be a significant performance improvement
Use Linked Lists when
You have a large number of insert or delete operations to perform
You have no idea how large your list might be
Use Array when
Read operations need to be extremely fast and you have relatively few updates to the array
class Node {
let value: Int
var next: Node?
init(value: Int, next: Node? = nil) {
self.value = value
self.next = next
}
}
let head = Node(value: 1)
let second = Node(value: 2)
let third = Node(value: 3)
let fourth = Node(value: 4)
//Make linked list
head.next = second
second.next = third
third.next = fourth
fourth.next = nil
var start: Node? = head
while start != nil {
print("\(start!.value)")
var next = start?.next
start = next
}
//Prints
1
2
3
4
Exercise 1. Get Length of a linked list
func length(of linkedList: Node?) -> Int {
var length = 0
var head = linkedList
while head != nil {
length += 1
head = head?.next
}
return length
}
length(of: head)
Exercise 2. Get the N-th element in a Linked List
func element(of linkedList: Node?, at index: Int) -> Node? {
if index < 0 {
return nil
}
var length = 0
var head = linkedList
while head != nil {
if index == length {
return head
}
length += 1
head = head?.next
}
return nil
}
// 1 -> 2 -> 3 -> 4, Index 3 is 4
element(of: head, at: 3)?.value //Prints 4, It's correct
Exercise 3. Append an element to the end of a linked list
There is 2 case you need to handle
head is null -> create a head node
there is a linked list, create a new node and append it as a last node. Don’t forget to handle last node’s next is nil
var head: Node? = Node(value: 1)
let second = Node(value: 2)
let third = Node(value: 3)
let fourth = Node(value: 4)
//Make linked list
head?.next = second
second.next = third
third.next = fourth
fourth.next = nil
func print(linkedList: Node?) {
var head = linkedList
while head != nil {
print("\(head!.value)")
head = head?.next
}
}
//To handle if linkedList is nil, and You don't want to return anything then use inout parameter.
func append(data: Int, at linkedList: inout Node?) {
if linkedList == nil {
linkedList = Node(value: data)
return
}
var head = linkedList
var lastItem: Node?
while linkedList?.next != nil {
linkedList = linkedList?.next
}
lastItem = linkedList
lastItem?.next = Node(value: data)
//Important, Reset head node
linkedList = head
}
var emptyHead: Node?
//Case 1. Empty Head
append(data: 4, at: &emptyHead)
print(emptyHead?.value)
//Case 2. 1 -> 2 -> 3 -> 4, append 5
append(data: 5, at: &head)
print(linkedList: head)
Exercise 5. Delete all the elements (All nodes should be removed from Memory)
class Node {
let value: Int
var next: Node?
init(value: Int, next: Node? = nil) {
self.value = value
self.next = next
}
deinit {
print("Node \(value) is deinit")
}
}
func removeAll(linkedList: inout Node?) {
guard linkedList != nil else {
return
}
while linkedList != nil {
print("Remove : \(linkedList!.value) Refcount: \(CFGetRetainCount(linkedList))")
var next = linkedList?.next
linkedList?.next = nil
linkedList = next
}
}
//Prints
Remove : 1 Refcount: 2
Node 1 is deinit
Remove : 2 Refcount: 3
Remove : 3 Refcount: 3
Remove : 4 Refcount: 3
What’s wrong? Only Node 1 deinit. The rest of nodes are still remaining in Memory.
To remove all nodes from Memory, We need to fix previous example of linked list.
Let’s make a linkedList function.
func linkedList(_ input: [Int]) -> Node? {
guard input.count > 0 else {
return nil
}
var head: Node? = Node(value: input.first!)
var linkedList = head
for i in 1..<input.count {
let value = input[i]
linkedList?.next = Node(value: value)
linkedList = linkedList?.next
}
return head
}
var newList = linkedList([1, 2, 3, 4])
removeAll(linkedList: &newList)
//Prints
Remove : 1 Refcount: 2
Node 1 is deinit
Remove : 2 Refcount: 2
Node 2 is deinit
Remove : 3 Refcount: 2
Node 3 is deinit
Remove : 4 Refcount: 2
Node 4 is deinit
I used a same removeAll function. I only change the linkedList by using linkedList function. This function returns linkedList and all nodes has a same reference counts.
Now You can see all nodes are completely removed from Memory.
Next example, I’ll continue use linkedList function for creating a linked list.
Exercise 6. Insert an elements at index
func print(linkedList: Node?) {
var head = linkedList
while head != nil {
print("\(head!.value)", terminator: head?.next == nil ? "" : " -> ")
head = head?.next
}
}
func insert(value: Int, at index: Int, in linkedList: inout Node?) {
guard linkedList != nil else {
return
}
var head = linkedList
//Edge case
if index == 0 {
var newHead = Node(value: value, next: linkedList)
linkedList = newHead
return
}
for i in 0..<index - 1 {
var next = linkedList?.next
linkedList = next
}
var prevItem = linkedList
var prevNextItem = prevItem?.next
prevItem?.next = Node(value: value)
prevItem?.next?.next = prevNextItem
//Pointing to head node
linkedList = head
}
var newList = linkedList([1, 2, 3, 4])
//MARK: Print All nodes
print("Current List")
print(linkedList: newList)
print("\n")
insert(value: 9, at: 2, in: &newList)
print("After insert 9 at index 2")
print(linkedList: newList)
print("\n")
insert(value: 10, at: 0, in: &newList)
print("After insert 10 at index 0")
print(linkedList: newList)
//Prints
Current List
1 -> 2 -> 3 -> 4
After insert 9 at index 2
1 -> 2 -> 9 -> 3 -> 4
After insert 10 at index 0
10 -> 1 -> 2 -> 9 -> 3 -> 4
Example 7. Insert an element at the right position in Sorted Linked List
func insert(value: Int, in sortedLinkedList: inout Node?) {
guard sortedLinkedList != nil else {
return
}
var head = sortedLinkedList
while sortedLinkedList != nil, sortedLinkedList!.value < value {
var next = sortedLinkedList?.next
if let nextValue = next?.value, nextValue > value {
break
}
else {
sortedLinkedList = sortedLinkedList?.next
}
}
var prevItem = sortedLinkedList
var prevNextItem = prevItem?.next
prevItem?.next = Node(value: value)
prevItem?.next?.next = prevNextItem
//Pointing to head node
sortedLinkedList = head
}
var newList = linkedList([1, 2, 3, 5])
//MARK: Print All nodes
print("Current List")
print(linkedList: newList)
print("\n")
insert(value: 4, in: &newList)
print("After insert 4 in sorted LinkedList")
print(linkedList: newList)
//Prints
Current List
1 -> 2 -> 3 -> 5
After insert 4 in sorted LinkedList
1 -> 2 -> 3 -> 4 -> 5
Example 8. Append one linked list to the end of another
func append(a: inout Node?, b: inout Node?) {
var mergedLinkedListHeader = a
while a?.next != nil {
a = a?.next
}
a?.next = b
a = mergedLinkedListHeader
b = mergedLinkedListHeader
}
var a = linkedList([1, 2, 3, 4])
var b = linkedList([5, 6, 7, 8])
//MARK: Print All nodes
print("A: Linked List")
print(linkedList: a)
print("\n")
print("B: Linked List")
print(linkedList: b)
print("\n")
print("A+B")
append(a: &a, b: &b)
print(linkedList: a)
print("\n")
//Prints
A: Linked List
1 -> 2 -> 3 -> 4
B: Linked List
5 -> 6 -> 7 -> 8
A+B
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
Example 9. Split one Linked List to two Linked List, find a mid point and split it!
🤔 Wait, why use 2 pointer?
Without 2 pointer, You need to get a length of linkedList first and then iterate linkedList again to split it.
func split(list: inout Node?) -> (first: Node?, seconds: Node?) {
var firstNode: Node? = list
var secondsNode: Node?
//for 1 step
var slowPointer = list
//for 2 steps
var fastPointer = list?.next
while fastPointer?.next != nil {
slowPointer = slowPointer?.next
fastPointer = fastPointer?.next?.next
}
//Split first list
secondsNode = slowPointer?.next
slowPointer?.next = nil
return (firstNode, secondsNode)
}
Test case 1. Input = [1, 2, 3, 4, 5, 6, 7, 8]
var list = linkedList([1, 2, 3, 4, 5, 6, 7, 8])
//MARK: Print All nodes
print("Linked List")
print(linkedList: list)
print("\n")
var (firstSubList, secondsSublist) = split(list: &list)
print("First Sub Linked List")
print(linkedList: firstSubList)
print("\n")
print("Seconds Sub Linked List")
print(linkedList: secondsSublist)
print("\n")
/Prints
Linked List
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
First Sub Linked List
1 -> 2 -> 3 -> 4
Seconds Sub Linked List
5 -> 6 -> 7 -> 8
Test case 2. Input = [1, 2, 3, 4, 5, 6, 7]
var list = linkedList([1, 2, 3, 4, 5, 6, 7])
//MARK: Print All nodes
print("Linked List")
print(linkedList: list)
print("\n")
var (firstSubList, secondsSublist) = split(list: &list)
print("First Sub Linked List")
print(linkedList: firstSubList)
print("\n")
print("Seconds Sub Linked List")
print(linkedList: secondsSublist)
print("\n")
//Prints
Linked List
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
First Sub Linked List
1 -> 2 -> 3 -> 4
Seconds Sub Linked List
5 -> 6 -> 7
Example 10. Remove duplicate nodes in a sorted linked list
func removeDuplicates(linkedList: inout Node?) {
var head: Node? = linkedList
while linkedList?.next != nil {
var nextNode = linkedList?.next
//Check duplicates
if linkedList?.value == nextNode?.value {
while nextNode?.value == nextNode?.next?.value {
var tempNext = nextNode?.next
nextNode = tempNext
}
linkedList?.next = nextNode?.next
}
linkedList = linkedList?.next
}
linkedList = head
}
var list = linkedList([1, 2, 3, 3, 3, 4, 4, 5])
//MARK: Print All nodes
print("Linked List")
print(linkedList: list)
print("\n")
removeDuplicates(linkedList: &list)
print("Removed duplicates in Linked List")
print(linkedList: list)
print("\n")
Example 11. Move node from the head of one list and add to the front of another
func moveHeadToAnother(source: inout Node?, dest: inout Node?) {
var sourceHead = source
source = source?.next
var destHead = dest
sourceHead?.next = destHead
dest = sourceHead
}
var source = linkedList([1, 2, 3])
var dest = linkedList([7, 8, 9])
//MARK: Print All nodes
print("Source Linked List")
print(linkedList: source)
print("\n")
print("Destination Linked List")
print(linkedList: dest)
print("\n")
moveHeadToAnother(source: &source, dest: &dest)
print("Result: Source Linked List")
print(linkedList: source)
print("\n")
print("Result: Destination Linked List")
print(linkedList: dest)
print("\n")
//Prints
Source Linked List
1 -> 2 -> 3
Destination Linked List
7 -> 8 -> 9
Result: Source Linked List
2 -> 3
Result: Destination Linked List
1 -> 7 -> 8 -> 9
🤯 Example 12. Merge two sorted linked list and then return a new sorted linked list
func merge(a: Node?, b: Node?) -> Node? {
//Edge cases
if a == nil, b == nil {
return nil
}
if a == nil, b != nil {
return b
}
if a != nil, b == nil {
return a
}
var result: Node?
var resultHead: Node?
var headA = a
var headB = b
if headA!.value < headB!.value {
resultHead = headA
headA = headA?.next
}
else {
resultHead = headB
headB = headB?.next
}
resultHead?.next = nil
result = resultHead
while headA != nil && headB != nil {
if headA!.value < headB!.value {
result?.next = headA
headA = headA?.next
}
else {
result?.next = headB
headB = headB?.next
}
result = result?.next
}
//Add rest of nodes
var restNodes = headA ?? headB
//When one list runs out make sure the remaining elements of the other are appended to the end of the result
result?.next = restNodes
//Pointing to head
result = resultHead
return result
}
var listA = linkedList([1, 2, 5])
var listB = linkedList([1, 4, 6])
//MARK: Print All nodes
print("listA Linked List")
print(linkedList: listA)
print("\n")
print("listB Linked List")
print(linkedList: listB)
print("\n")
let mergedList = merge(a: listA, b: listB)
print("Merged Linked List")
print(linkedList: mergedList)
print("\n")
//Prints
listA Linked List
1 -> 2 -> 5
listB Linked List
1 -> 4 -> 6
Merged Linked List
1 -> 1 -> 2 -> 4 -> 5 -> 6
Example 13. Reverse a Linked List
Code
func reverseLinkedList(input: Node?) -> Node? {
//Prev will become a head of reversed linked list
var prev = input
var current = input?.next
//At this time, prev is tail node, but after while loop, It become a head node
prev?.next = nil
while current != nil {
//next node is input's next step
var next = current?.next
//It makes reversed direction
current?.next = prev
//next step for reversed linkedList
prev = current
current = next
}
return prev
}
var input = linkedList([1, 2, 5])
//MARK: Print All nodes
print("Input Linked List")
print(linkedList: input)
print("\n")
var reversedLinkedList = reverseLinkedList(input: input)
print("Reversed Linked List")
print(linkedList: reversedLinkedList)
print("\n")
//Prints
Input Linked List
1 -> 2 -> 5
Reversed Linked List
5 -> 2 -> 1
Doubly Linked List
A doubly linked list has pointers to the next element as well as pointers to the previous element.
This requires additional memory in every node to store the previous pointer.
Some codes are sourced from Loony Corn’s Udemy Course (https://www.udemy.com/user/janani-ravi-2/). This post is for personal notes where I summarize the original contents to grasp the key concepts
Tree Data Structure
class Node {
var left: Node?
var right: Node?
var value: Int
init(value: Int) {
self.value = value
}
}
//Create a Tree
let root = Node(value: 5)
root.left = Node(value: 3)
root.right = Node(value: 7)
root.right?.left = Node(value: 6)
root.right?.right = Node(value: 9)
BFS: Breadth First Search
func bfs(root: Node) {
var root = root
var queue = [Node]()
queue.append(root)
while !queue.isEmpty {
let dequeue = queue.removeFirst()
print("\(dequeue.value)", terminator: " ")
if let leftChild = dequeue.left {
queue.append(leftChild)
}
if let rightChild = dequeue.right {
queue.append(rightChild)
}
}
}
bfs(root: root)
DFS: Depth First Search
Use Recursion!
Define base case -> when the root is null
Recursion technique -> Processing can be performed
Before -> Pre-Order
In-Between or -> In-Order
After -> Post-Order
Pre-Order
Each node is processed first (PRE) before It’s right and left subtrees
In-Order
Post-Order
func dfs(root: Node?) {
//base: node is not null
guard root != nil else {
return
}
dfs(root: root?.left)
dfs(root: root?.right)
//Post-Order - print value after recursing to the left and right subtrees
print("\(root!.value)", terminator: " ")
}
dfs(root: root)
//Prints
3 6 9 7 5
Binary Search Tree
It is called an Ordered Binary Tree.
Each node in the left sub-tree of that node has a value less than or equal to the value of the node
Each node in the right sub-tree of that node has a value greater than the value of the node
Key Feature
Typically used for Fast Insertion and Fast Lookup
Fast Insertion
In a tree when a new node is added there is exactly one place that it can be
The structure of a tree depends on the order in which the nodes are added
Fast Lookup
While searching for a node in the tree there is only one place where that node can be found
You can simply follow the right or left sub-trees based on the value you want to find
Insertion
🙏 Below Images are wrong, Level 4 -> Level 3.
Let’s see step by step.
Step 1
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Step 8 -> Finish
class Node {
var left: Node?
var right: Node?
var value: Int
init(value: Int) {
self.value = value
}
}
let root = Node(value: 8)
//Level 1
root.left = Node(value: 6)
root.right = Node(value: 14)
//Level 2
root.left?.left = Node(value: 4)
root.left?.right = Node(value: 7)
root.right?.right = Node(value: 16)
//Level 3
root.right?.right?.right = Node(value: 18)
func insertion(root: Node?, newNode: Node) -> Node? {
if root == nil {
return newNode
}
if newNode.value < root!.value {
root?.left = insertion(root: root?.left, newNode: newNode)
}
else {
root?.right = insertion(root: root?.right, newNode: newNode)
}
return root
}
insertion(root: root, newNode: Node(value: 15))
func bfs(root: Node) {
var root = root
var queue = [Node]()
queue.append(root)
while !queue.isEmpty {
let dequeue = queue.removeFirst()
print("\(dequeue.value)", terminator: " ")
if let leftChild = dequeue.left {
queue.append(leftChild)
}
if let rightChild = dequeue.right {
queue.append(rightChild)
}
}
}
bfs(root: root)
//Prints
8 6 14 4 7 16 15 18
func minimumValue(root: Node?) -> Int {
if root == nil {
return 0 //or return Int.min
}
//Left child has a minimum value
if root?.left == nil {
return root!.value
}
return minimumValue(root: root?.left)
}
minimumValue(root: root)
Exercise 2. Maximum Depth
🙏 Below Images are wrong, Level 4 -> Level 3.
func maximumDepth(root: Node?) -> Int {
if root == nil {
return 0
}
//Leaf node
if root?.left == nil, root?.right == nil {
return 0
}
//Count up when look up next level
let leftDepth = 1 + maximumDepth(root: root?.left)
let rightDepth = 1 + maximumDepth(root: root?.right)
return max(leftDepth, rightDepth)
}
maximumDepth(root: root) //Prints 3
Exercise 3. Mirror Tree
func mirror(root: Node?) {
if root == nil {
return
}
mirror(root: root?.left)
mirror(root: root?.right)
//Switch left and right child
let temp = root?.left
root?.left = root?.right
root?.right = temp
}
mirror(root: root)
🤯 Exercise 4. Create the number of structurally unique Binary Trees possible
Problem definition
Let say If you have 3 nodes, How many various binary trees you can create?
func countTrees(nodeCount: Int) -> Int {
//Base case: node 1 -> possible tree is 1, If it is zero then root node will be null
if nodeCount <= 1 {
return 1
}
var sum = 0
//Every node can be the root
for i in 1...nodeCount {
//Left and right form their own sub trees
//The nodes before it will be on the left
let leftTrees = countTrees(nodeCount: i - 1)
//THe nodes after it on the right
let rightTrees = countTrees(nodeCount: nodeCount - i)
//leftTree * rightTrees = the number of possible trees with this root
sum = sum + leftTrees * rightTrees
}
return sum
}
countTrees(nodeCount: 3) //Prints 5
Exercise 5. Print all nodes within a range in a Binary Search Tree
func printAllNodeWithin(root: Node?, range: ClosedRange<Int>) {
if root == nil {
return
}
//If the range low value is less than the current, run the operation on the left subtree
if root!.value >= range.lowerBound {
printAllNodeWithin(root: root?.left, range: range)
}
//In-Order
if range ~= root!.value {
print("\(root!.value)", terminator: " ")
}
//If the range high value is greater than the current node, run the operation on the right subtree
if root!.value < range.upperBound {
printAllNodeWithin(root: root?.right, range: range)
}
}
print("\nExercise: Print All Nodes\n")
printAllNodeWithin(root: root, range: 6...14)
//Prints
Exercise: Print All Nodes
6 7 8 14
Exercise 6. Is a Binary Tree is a Binary Search Tree?
Remind what is Binary Search Tree?
For every node in a binary search tree – The nodes with values <= node are in the left subtree and nodes with values > node are in the right sub tree
let nonBinarySearchTreeRoot = Node(value: 8)
//Level 1
nonBinarySearchTreeRoot.left = Node(value: 14)
nonBinarySearchTreeRoot.right = Node(value: 6)
//Level 2
nonBinarySearchTreeRoot.left?.left = Node(value: 4)
nonBinarySearchTreeRoot.left?.right = Node(value: 7)
nonBinarySearchTreeRoot.right?.right = Node(value: 16)
//Level 3
nonBinarySearchTreeRoot.right?.right?.right = Node(value: 18)
func isBinarySearchTree(root: Node?) -> Bool {
//Null node consider valid binary search tree
if root == nil {
return true
}
if let left = root?.left?.value, root!.value < left {
return false
}
if let right = root?.right?.value, root!.value > right {
return false
}
return isBinarySearchTree(root: root?.left) && isBinarySearchTree(root: root?.right)
}
isBinarySearchTree(root: nonBinarySearchTreeRoot) //Prints false
Exercise 7. Has Path Sum?
func hasPathSum(root: Node?, sum: Int) -> Bool {
//Check hasPathSum or not
if root?.left == nil, root?.right == nil {
return root?.value == sum
}
if root == nil {
return false
}
let subSum = sum - root!.value
if let left = root?.left {
var hasPathSum = hasPathSum(root: root?.left, sum: subSum)
if hasPathSum {
return true
}
}
if let right = root?.right {
var hasPassSum = hasPathSum(root: root?.right, sum: subSum)
if hasPassSum {
return true
}
}
return false
}
hasPathSum(root: root, sum: 21) //True
Exercise 9. Find the Least Common Ancestor for 2 nodes
Let’s check step by step.
Remember, This step is important!
Found! The lease common ancestor is 3
//It's not a Binary Search Tree
let findAncestorRoot = Node(value: 1)
//Level 1
findAncestorRoot.left = Node(value: 2)
findAncestorRoot.right = Node(value: 3)
//Level 2
findAncestorRoot.right?.left = Node(value: 7)
findAncestorRoot.right?.right = Node(value: 6)
//Level 3
findAncestorRoot.right?.left?.left = Node(value: 8)
findAncestorRoot.right?.left?.right = Node(value: 5)
findAncestorRoot.right?.right?.right = Node(value: 4)
func findLeastCommonAncestor(root: Node?, targetNodeValue1: Int, targetNodeValue2: Int) -> Int? {
if root == nil {
return nil
}
//If the current root is either of the two node then return it itself. (It will be use later)
if root!.value == targetNodeValue1 || root!.value == targetNodeValue2 {
return root!.value
}
let leftAncestor = findLeastCommonAncestor(root: root?.left, targetNodeValue1: targetNodeValue1, targetNodeValue2: targetNodeValue2)
let rightAncestor = findLeastCommonAncestor(root: root?.right, targetNodeValue1: targetNodeValue1, targetNodeValue2: targetNodeValue2)
//If both exist it means - either the node or it's ancestor exist in the left and right subtree. So current node is the least common ancestor
if let leftAncestor, let rightAncestor {
return root!.value
}
if let leftAncestor {
return leftAncestor
}
return rightAncestor
}
findLeastCommonAncestor(root: findAncestorRoot, targetNodeValue1: 8, targetNodeValue2: 6) //It is 3
Exercise 10. iOS, Find the Least Common Ancestor for 2 subview
UIView is not a binary tree. It has more 2 child views.
func createNodeView(tag: Int) -> UIView {
let view = UIView()
view.tag = tag
return view
}
//Level 0
let rootView = createNodeView(tag: 1)
//Level 1
let tag3View = createNodeView(tag: 3)
rootView.addSubview(createNodeView(tag: 2))
rootView.addSubview(tag3View)
//Level 2
let tag7View = createNodeView(tag: 7)
let tag6View = createNodeView(tag: 6)
let tag9View = createNodeView(tag: 9)
tag3View.addSubview(tag7View)
tag3View.addSubview(tag6View)
tag3View.addSubview(tag9View)
//Level 3
tag7View.addSubview(createNodeView(tag: 11))
tag6View.addSubview(createNodeView(tag: 8))
tag6View.addSubview(createNodeView(tag: 5))
tag9View.addSubview(createNodeView(tag: 4))
func findLeastCommonAncestor(root: UIView?, targetNodeValue1: Int, targetNodeValue2: Int) -> UIView? {
print("visited: \(root?.tag)")
if root == nil {
return nil
}
//If the current root is either of the two node then return it itself. (It will be use later)
if root!.tag == targetNodeValue1 || root!.tag == targetNodeValue2 {
return root
}
var ancestors = [UIView]()
for subView in root!.subviews {
if let ancestor =
findLeastCommonAncestor(root: subView, targetNodeValue1: targetNodeValue1, targetNodeValue2: targetNodeValue2) {
ancestors.append(ancestor)
}
}
print(ancestors.compactMap { $0.tag })
let tags = ancestors.compactMap { $0.tag }
//If rootView has both nodes then return it
if tags.contains(targetNodeValue1), tags.contains(targetNodeValue2) {
return root
}
if ancestors.isEmpty {
return nil
}
//Need to check whether It's okay to return last item or not..but most of cases It works correctly so far.
return ancestors.last
}
Some codes and contents are sourced from Apple’s official documentation. This post is for personal notes where I summarize the original contents to grasp the key concepts
Archives and serializations are two ways in which you can create architecture-independent byte streams of hierarchical data. Byte streams can then be written to a file or transmitted to another process, perhaps over a network. When the byte stream is decoded, the hierarchy is regenerated. Archives provide a detailed record of a collection of interrelated objects and values. Serializations record only the simple hierarchy of property-list values
Apple
Example 1, Conforms NSCoding
class Person: NSObject, NSCoding {
var name: String
var age: Int
var friend: Person?
init(name: String, age: Int, friend: Person? = nil) {
self.name = name
self.age = age
self.friend = friend
}
required convenience init?(coder: NSCoder) {
guard let name = coder.decodeObject(forKey: "name") as? String
else {
return nil
}
let age = coder.decodeInteger(forKey: "age")
let friend = coder.decodeObject(forKey: "friend") as? Person
self.init(name: name, age: age, friend: friend)
}
func encode(with coder: NSCoder) {
coder.encode(name, forKey: "name")
coder.encode(age, forKey: "age")
coder.encode(friend, forKey: "friend")
}
}
func savePerson(_ person: Person, to path: String) {
do {
let data = try NSKeyedArchiver.archivedData(withRootObject: person, requiringSecureCoding: false)
try data.write(to: URL(fileURLWithPath: path))
print("Saved Person")
} catch {
print("Failed: \(error)")
}
}
func loadPerson(from path: String) -> Person? {
do {
let data = try Data(contentsOf: URL(fileURLWithPath: path))
//Instead unarchiveTopLevelObjectWithData You can use unarchivedObject(ofClass:from:) when you conforms NSSecureCoding protocol
if let loadedPerson = try NSKeyedUnarchiver.unarchiveTopLevelObjectWithData(data) as? Person {
return loadedPerson
}
} catch {
print("Failed: \(error)")
}
return nil
}
let friend = Person(name: "Bob", age: 35)
let person = Person(name: "Alice", age: 30, friend: friend)
let filePath = NSTemporaryDirectory() + "person_with_friend.archive"
savePerson(person, to: filePath)
if let loadedPerson = loadPerson(from: filePath) {
if let loadedFriend = loadedPerson.friend {
print("Person: \(loadedPerson.name), \(loadedPerson.age)")
print("Friend: \(loadedFriend.name), \(loadedFriend.age)")
} else {
print("No friends")
}
}
Example 2. Conforms NSSecureCoding
In example 1, You may see this warning. unarchiveTopLevelObjectWithData was deprecated. To resolve it, let’s conforms NSSecureCoding.
class Person: NSObject, NSSecureCoding {
static var supportsSecureCoding = true
var name: String
var age: Int
var friend: Person?
init(name: String, age: Int, friend: Person? = nil) {
self.name = name
self.age = age
self.friend = friend
}
required convenience init?(coder: NSCoder) {
guard let name = coder.decodeObject(forKey: "name") as? String
else {
return nil
}
let age = coder.decodeInteger(forKey: "age")
let friend = coder.decodeObject(forKey: "friend") as? Person
self.init(name: name, age: age, friend: friend)
}
func encode(with coder: NSCoder) {
coder.encode(name, forKey: "name")
coder.encode(age, forKey: "age")
coder.encode(friend, forKey: "friend")
}
}
func savePerson(_ person: Person, to path: String) {
do {
let data = try NSKeyedArchiver.archivedData(withRootObject: person, requiringSecureCoding: true)
try data.write(to: URL(fileURLWithPath: path))
print("Saved Person")
} catch {
print("Failed: \(error)")
}
}
func loadPerson(from path: String) -> Person? {
do {
let data = try Data(contentsOf: URL(fileURLWithPath: path))
if let loadedPerson = try NSKeyedUnarchiver.unarchivedObject(ofClass: Person.self, from: data) {
return loadedPerson
}
} catch {
print("Failed: \(error)")
}
return nil
}
let friend = Person(name: "Bob", age: 35)
let person = Person(name: "Alice", age: 30, friend: friend)
let filePath = NSTemporaryDirectory() + "person_with_friend.archive"
savePerson(person, to: filePath)
if let loadedPerson = loadPerson(from: filePath) {
if let loadedFriend = loadedPerson.friend {
print("Person: \(loadedPerson.name), \(loadedPerson.age)")
print("Friend: \(loadedFriend.name), \(loadedFriend.age)")
} else {
print("No friends")
}
}
Some codes and contents are sourced from Apple’s official documentation. This post is for personal notes where I summarize the original contents to grasp the key concepts
When layoutSubViews has called?
Subclasses can override this method as needed to perform more precise layout of their subviews. You should override this method only if the autoresizing and constraint-based behaviors of the subviews do not offer the behavior you want. You can use your implementation to set the frame rectangles of your subviews directly.
You should not call this method directly. If you want to force a layout update, call the setNeedsLayout() method instead to do so prior to the next drawing update. If you want to update the layout of your views immediately, call the layoutIfNeeded() method.
Test it your self. When you call a setNeedsLayout a layoutSubviews in CustomView will be called.
viewWillLayoutSubviews and viewDidLayoutSubviews
When a view’s bounds change, the view adjusts the position of its subviews. Your view controller can override this method to make changes before the view lays out its subviews. The default implementation of this method does nothing.
When you changed a subview’s bounds, viewWillLayoutSubviews and viewDidLayoutSubviews are called. And then subview’s layoutSubviews is also called
When use Autolayout and changes NSLayoutConstraints, It also calls viewWillLayoutSubviews and viewDidLayoutSubviews
What is intrinsicContentSize?
The natural size for the receiving view, considering only properties of the view itself.
Custom views typically have content that they display of which the layout system is unaware. Setting this property allows a custom view to communicate to the layout system what size it would like to be based on its content. This intrinsic size must be independent of the content frame, because there’s no way to dynamically communicate a changed width to the layout system based on a changed height, for example.
If a custom view has no intrinsic size for a given dimension, it can use noIntrinsicMetric for that dimension.
Let’s test. UILabel has 2 constraints which are leading and top. I set font and text. As you can see It’s intrinsicContentSize is based on it’s content.
I added trailingAnchor. As you can see frame width is bigger than first one. ButintrinsicSize doesn’t changed. Because It’s based on contents. Now we know that It is independent from frame
UIImageView
An image view uses its contentMode property and the configuration of the image itself to determine how to display the image. It’s best to specify images whose dimensions match the dimensions of the image view exactly, but image views can scale your images to fit all or some of the available space. If the size of the image view itself changes, it automatically scales the image as needed.
You can create a resizable image that stretches using the resizableImage(withCapInsets:resizingMode:) method of UIImage. When using an image of this type, you typically set the image view’s content mode to UIView.ContentMode.scaleToFill so that the image stretches in the appropriate places and fills the image view’s bounds.
Image scaling and alpha blending are two relatively expensive operations that can impact your app’s performance. To maximize performance of your image view code, consider the following tips:
Cache scaled versions of frequently used images. If you expect certain large images to be displayed frequently in a scaled-down thumbnail view, consider creating the scaled-down images in advance and storing them in a thumbnail cache. Doing so alleviates the need for each image view to scale them separately.
Use images whose size is close to the size of the image view. Rather than assigning a large image to an image view, created a scaled version that matches the current size of the image view. You can also create a resizable image object using the UIImage.ResizingMode.tile option, which tiles the image instead of scaling it.
Make your image view opaque whenever possible. Unless you’re intentionally working with images that contain transparency (drawing UI elements, for example), make sure the isOpaque property of your image view is set to true. For more information about how transparency is determined, see Determine the final transparency of the image.
You must be logged in to post a comment.