Thoughts about building an SMS system

What a sunny day. Yesterday I decided to take one more class – Math221 to discover the possibility of math majoring. I don’t know if it’s possible for me to triple major in CS, ECE and math but we’ll see.

Recently I’ve been thinking how I can improve my Wheeshare app. I believe protecting user privacy should be of high priority, so the app could be better with a built-in SMS system like Taobao’s Aliwangwang or WeChat. However building such thing is no easy – from the data structure of chats to UI design to speed enhancement. No one wants a chat screen that lags. I have to think of an efficient architecture. If everything goes perfectly, I will upload the project to GitHub for others to use.

For the chat screen, I plan to use a UITableView to hold every chat message, with user thumbnail profile picture on each side. I will make a NIB file for the chat bubble and add a UILabel in it to display chat. One technical challenge would be how to update messages if the user received a new one. I will look into Parse API documentation to look for a notification API so that my app can observe the database on the user’s phone.

As for the general structure, I would like to create and store an object for each pair of users (if they started chatting, of course) and label it with two users’ IDs. When the app inits it tries to retrieve chats from online database with the current user ID. Inside each object I store an array of chat messages, each labeled with its sender.

Another technical challenge: how to cache all messages locally? For now, my tentative solution is to use CoreData so that I can directly push any updated chat object into the Core Data Stack. It sounds so simple right now but I am 100% sure it will give me a headache when I try to implement it.

One other problem to think about is whether to keep the connection between two users after they ended their relationship as borrower/lender. Again this is a privacy issue that I need to think about.

Other than this SMS system plan, I need to somehow restrict the app’s area. I probably need to get users’ locations and limit the access to Duke University for now to prevent possible malicious data attack. Thank you for watching, that’s it for today.

Sorting Algorithms

So class has started for a week now, but I’ve only gone to class for six days because we had MLK holiday and class got cancelled because of the snow. North Carolina can’t handle the mere thought of snow lol.

I’m writing down some of the easy Quicksort and Mergesort I’ve learned in COMPSCI 330. Maybe they’ll help me in the review process.

QuickSort:

Quicksort uses a divide-and-conquer spirit. It gets a pivot in the array and recurse on all numbers smaller or larger than the pivot. There are several ways to implement it. Here’s the method on Introduction to Algorithms:

QSORT(A, i, j)
    pivot = SPLIT(A, i, j)
    QSORT(A, i, pivot - 1)
    QSORT(A, pivot + 1, j)
SPLIT(A, m, n)
    i = m - 1
    FOR j from 0 to n - 1
        if A[j] < A[n]
            i++
            SWAP A[i], A[j]
        SWAP A[i + 1], A[n]
    return i + 1

This version is pretty hard to understand, but the key is that for each m <= k <= i, A[k] < A[n], and for each i + 1 <= k <= j, A[k] > A[n].

The running time is obviously O(n log n).

MergeSort

MergeSort also uses divide-and-conquer. Instead of dealing with a pivot, it first divide, and then merge two divisions in linear time.

MSORT(A, i, j)
    B = MSORT(A, i, (i + j) / 2)
    C = MSORT(A, (i + j) / 2 + 1, j)
    A = MERGE(B, C)
Merge(B, C)
    D = empty array
    i = j = k = 1
    while (i < |B| and j < |C|)
        if(B[i] < C[j])
            D[k] = B[i], i++
        else
            D[k]=C[j], j++
    k++
    Copy all elements of the other array into D
    return D

The running time is still O(n log n).

Grand Central Dispatch with Swift

When I’m building my LOL helper app, there’s one thing that I noticed: I had to deal with asynchronous networking requests properly so that the UI is only updated after multiple requests have been completed. I am using Alamofire to complete such requests, which does provide a callback function that is only called after getting a response. However, it is unable to do so with multiple requests. After searching online, I found the problem could be solved with Grand Central Dispatch in Swift. GCD Tutorial

The idea is that to put the requests into a “dispatch group” which can notify or be monitored. Tasks in the group are run on different threads. Before the start of a HTTP request, we need to enter the group, and after it finishes (in the callback function), we leave the group. Then we execute some methods only after the group is clean, which means no task is going on.

Here’s what we could do:

func downloadThings() {
  dispatch_async(dispatch_get_global_queue(QOS_CLASS_USER_INITIATED, 0)) { // 1
    var downloadGroup = dispatch_group_create() // 2
 
    for address in someURLStringGroup {
      dispatch_group_enter(downloadGroup) // 3
      download(address) { _ in
        dispatch_group_leave(downloadGroup) // 4
      }
    }
 
    dispatch_group_wait(downloadGroup, DISPATCH_TIME_FOREVER) // 5
    dispatch_async(dispatch_get_global_queue(QOS_CLASS_USER_INTERACTIVE, 0)) { 
        // some cool stuff here
    }
  }
}

In this example, we first get on the user initiated queue, which has a relatively high priority. In 2, before anything happens, we need to create a group to “store” our tasks. Then before each task we enter the group, and after they complete we leave. dispatch_group_wait waits for the group to be empty and continue. After all that we get back on the main queue and update UI and stuff.

One problem with this implementation is that it blocks the main queue by waiting on the user interactive queue. The solution is thinking from the other direction: instead of waiting for the group, how about letting the group notify us? Luckily, Apple thought of that:

func downloadThings() {
  dispatch_async(dispatch_get_global_queue(QOS_CLASS_USER_INITIATED, 0)) { // 1
    var downloadGroup = dispatch_group_create() // 2
 
    for address in someURLStringGroup {
      dispatch_group_enter(downloadGroup) // 3
      download(address) { _ in
        dispatch_group_leave(downloadGroup) // 4
      }
    }
 
    dispatch_group_notify(downloadGroup, dispatch_get_global_queue(QOS_CLASS_USER_INITIATED, 0)) 
    { // 2
      // some cool stuff here
    }
  }

Here we let the group notify us when everything is done. The UI is responsive while the data is being loaded. Everyone is happy.

The app is now able to retrieve current game information of a player, including who she or he is playing with. It is also able to get those players’ information with requests. However, Riot prevents “too many” requests in a second, which now seems that 10 requests in one second is still too many!! I’m working on a way to set a delay between requests, but since they are operating on different threads it is kind of difficult.

Also, I’ve been reading chapters and chapters of algorithms lately for my class. I should update what I learn urgently, maybe sometime tonight.

 

League of Legends API

Today is the first day of class this semester. I still have forty minutes before the section that I TA for starts, so I’m writing about my new iOS project.

The other day I came across with League of Legends API. As a LOL summoner and an iOS developer, I felt obligated to do something with it. The app let users search players with their summoner names and view their stats. In the near future, it will also provide a function like LOL nexus, which shows the summoners a user is playing with before entering the game.

Intuitively, I used a TabViewController as the initial view controller for the app since I have several “categories” of functions. These categories include the following:

  1. basic data about LOL: maps, champions and spells etc.
  2. search for a player by summoner name
  3. view players the user is against

The API is very handy. It also let developers try them out on the webpage, but they could add a search function. I am using Alamofire as the networking tool. I followed the instructions written by Ray Wenderlich to set it up.

There are several things that I noticed when writing the code:

  1. summoner names can contain spaces, I escaped that with
    name.stringByAddingPercentEncodingWithAllowedCharacters(NSCharacterSet.URLQueryAllowedCharacterSet())!

    which translates spaces into “%20″s.

  2. a lot of things returned by the server are optional. I have to unwrap them as soon as possible, otherwise when they are cast into String, “optional” will be there and that is not good to hear.
  3. the status code returned has to be 200 for the app to continue.

Here’s the GitHub Project Page

Paging view with control

Before talking about boring(no it’s absolutely not) programming, some babbles about my life. I’m going back to America tomorrow and will arrive at midnight. Let’s hope I won’t get much jet lag. As for the semester, I kind of need to learn to drive and get a license so life won’t suck. I’m taking a pretty hard algorithm class and at the same time having two jobs so wish me luck!

In the project StoreSearch, I used scroll view and UIPageControl to implement a paging view with control once, but what did I know I just mindlessly followed the detailed tutorial. Thankfully, I used the money granted by Duke CoLab to subscribe for online tutorials on Ray Wenderlich’s website and learned again about paging view there.

There are two ways to do this: one is using UIScrollView and set constraints on pages manually, the other is taking advantage of UIPageViewController and have things set up. I personally prefer the former because it’s more customizable, so selfishly I’ll write about that here.

First, we should have a view controller set up. This controller takes care of each page in our paging view. Then in the initial view controller put in a UIScrollViewController and set proper constraints.

Screen Shot 2016-01-09 at 8.20.46 PM

Next we accomplish paging through the following steps:

  1. set pagingEnabled to true:
    scrollView.pagingEnabled = true
  2. keep view controllers in a dictionary so that we can set constraints later:
    pages = [page1, page2, page3, page4, page5]
            let views = ["view": view, "page1": page1.view, "page2": page2.view, "page3": page3.view, "page4": page4.view, "page5": page5.view]
    /*"pageX" means the Xth view controller.*/
  3. set constraints on views:
    let metrics = ["edgeMargin": 10, "betweenMargin": 20]
     
    let verticalConstraints = NSLayoutConstraint.constraintsWithVisualFormat("V:|[page1(==view)]|", options: [], metrics: nil, views: views)
    NSLayoutConstraint.activateConstraints(verticalConstraints)
     
    let horizontalConstraints =
        NSLayoutConstraint.constraintsWithVisualFormat("H:|-edgeMargin-[page1(==view)]-betweenMargin-[page2(==view)]-betweenMargin-[page3(==view)]-betweenMargin-[page4(==view)]-betweenMargin-[page5(==view)]-edgeMargin-|", options: [.AlignAllTop, .AlignAllBottom], metrics: metrics, views: views)
     
    NSLayoutConstraint.activateConstraints(horizontalConstraints)

Oh, before all these remember to set the view controllers for each page not to autoresize:

view.translatesAutoresizingMaskIntoConstraints = false

And voila we have a nice looking five pages view.

To add a page control, first add it in storyboard and set proper constraints and outlet:

Screen Shot 2016-01-09 at 8.21.30 PM

Then follow the steps below:

  1. set its number of pages:
    pageControl.numberOfPages = pages.count
  2. show the correct current page. We need to round the value of offset.x/width because we would like it to show the correct page when we are in between pages:
    extension TutorialViewController: UIScrollViewDelegate {
        func scrollViewDidScroll(scrollView: UIScrollView) {
            let pageWidth = CGRectGetWidth(scrollView.bounds)
            let pageFraction = scrollView.contentOffset.x / pageWidth
            pageControl.currentPage = Int(round(pageFraction))
        }
    }
  3. control the change of page with an action outlet:
    @IBAction func pageChanged(sender: AnyObject) {
            let currentPage = sender.currentPage
            let pageWidth = CGRectGetWidth(scrollView.bounds)
            let targetContentOffsetX = CGFloat(currentPage) * pageWidth
     
            UIView.animateWithDuration(0.33, delay: 0,
                options: .CurveEaseInOut, animations: { () -&gt; Void in
                    self.scrollView.contentOffset.x = targetContentOffsetX
                }, completion: nil)
        }

    Here we’re using a cute little animation.

And there we go! Paging view with control. I uploaded the code to GitHub in case I need the template in future development. If one intends to use it be aware of its license.

Elementary Layer Animations

Today I learned that apart from UIView animations provided by UIKit, we can also use Layer Animations integrated inside any ViewController. Layer animation is also faster in performance because it is relatively “lower-level”.

For an animation, if we use UIView, the code would be like:

UIView.animateWithDuration(0.5, delay: 0.5, options: [], animations: {
    // something about UI change
}, completion: nil)

One little problem with this method is that we have to specify the UI modification in the animation closure. If we have ten different views we would like to animate, we would have to cut and paste this chunk for at least ten times. Obviously we would like to reuse code, so layer animation is the way to go:

animationName = CABasicAnimation(keyPath:"some property")
animationName.fromValue = 0.0
animationName.toValue = 1.0
animationName.duration = 5.0
object.layer.addAnimation(animationName, forKey: “key”)
animationName.setValue(object.layer, forKey: “layer”)

The above code does the same thing, but notice that it does not specify the target layer. We could simply modify fromValue or toValue and add it to another layer and it would work.

This is not all. If we set the delegate of a layer animation object to self (every NSObject already implements the delegate methods) and overrides these two functions:

func animationDidStart(anim: CAAnimation )
func animationDidStop(anim: CAAnimation , finished flag: Bool )

We would be able to monitor the status of layer animations. Neat.

Elsewhere in the class, we could use the keys that we set earlier to get either the animation object or the layer. I’ll save the code here.

Now that we have fromValue, toValue and duration, we would also like to set the delay time of our animations. Again, this is pretty easy:

animationName.beginTime = CACurrentMediaTime() + 1.0

Note that the beginTime is relative to the fixed currentMediaTime(), not that the animation is delayed by the time after the former animation.

Animations can also be grouped together with CAAnimationGroup:

let group = CAAnimationGroup()
group.animations = [animation1, animation2, animation3]

Then it is convenient to set the common properties of animations to the group.

That’s pretty much it.

Dynamic Programming – Knapsack & Shortest Path

Happy New Year! I sure enjoyed my holiday. I visited my girlfriend’s city in southern China and spent happy three days with her :).

These two days I read about dynamic programming. This is the first time I ever systematically learn its principles, so I thought I should write my thoughts down.

When to use dynamic programming? In my opinion, when the problem fits the following requirements:

  1. It can be divided into a certain amount of subproblems.
  2. The subproblems can be solved in a certain order.
  3. There are not too many variables.

“Dynamic programming” is really a fancy phrase of solving problems in an order. I think it essentially is recursion with memoization. I’ll write solutions of two sample problems here. One is the famous knapsack program, the other is finding the shortest path in a graph with negative edges.

Knapsack problem: Given a “bag” that can only hold items weighing less than or equal to W and weights w and values v of n items, how should we pick the items so that we have the largest possible value in the “bag”?

Here we have two variables with which we divide the problem: the number of items we are choosing from and the largest weight we can have. We use these two variables because when they are small, the problem is trivial: when we can only choose from 1 item, we have to choose that one; when the weight available is small, we can only choose from “light” items. Another reason is that we can solve subproblems in an order: from a small number of items to the whole group, and from 0 weight to W. It is mandatory that we understand the spirit of dynamic programming, because we use it to divide subproblems.

Now we consider if we choose an item or not. Assume we are looking for the largest possible value for i items and weight t – OPT(i, t) (OPT stands for “optimal”, not optional practical training lol). If the optimal plan includes item i, then OPT(i, t) = OPT(i – 1, t – Wi) + Vi. If it does not, OPT(i, t) = OPT(i – 1, t). When t is less than Wi, it can only be the latter. In this way, we have our recurrence function:

OPT(i, t) = MAX(OPT(i- 1, t – Wi) + Vi, OPT(i – 1, t))

The rest is easy.

Shortest Path Problem: In a graph with negative edges but without negative cycles, find the shortest path from vertex s to t.

(I should note here that MacBook keyboard sucks. It feels so bad.)

We use OPT(i, v) to represent the least weight from vertex v to t, with at most i edges. If the optimal path P contains at most i – 1 edges, OPT(i, v) = OPT(i – 1, v). If P contains i edges, OPT(i, v) = OPT(i – 1, w) + cost(v to w).

Therefore, OPT(i, v) = MIN(OPT(i – 1, v), OPT(i – 1, w) + cost(v to w))

To be honest, I don’t quite understand how this works. I can see it does the job but I can’t form a logical shortcut of the algorithm in my mind. Anyway, I think with practice I will be able to master dynamic programming.