{"id":375,"date":"2014-07-09T07:02:45","date_gmt":"2014-07-09T13:02:45","guid":{"rendered":"http:\/\/dev.iachieved.it\/iachievedit\/?p=375"},"modified":"2023-07-29T21:28:42","modified_gmt":"2023-07-30T02:28:42","slug":"writing-reusable-algorithms-with-swift-generics","status":"publish","type":"post","link":"https:\/\/dev.iachieved.it\/iachievedit\/writing-reusable-algorithms-with-swift-generics\/","title":{"rendered":"Writing Reusable Algorithms With Swift Generics"},"content":{"rendered":"<p>Learning a new programming language is fun, and learning Swift has been no different.  We&#8217;ve been covering, through brief tutorials, features that most Objective-C programmers will find to be <i>new<\/i>.  As many have observed, Swift borrows from many different languages and brings the &#8220;best&#8221; features together in a single language.  One such feature is <i>generics<\/i>.<\/p>\n<p>Simply put a generic is code that is agnostic of type, that is, code that can work with any type.  One of the most powerful forms of a &#8220;generic&#8221; is the generic algorithm, i.e., an algorithm that can be used with most any type.  By far the most common &#8220;example&#8221; algorithm is that of sorting.  It&#8217;s common because its easy-to-grasp (everyone understands sorting and its applicability to software), easy to implement, and actually a useful algorithm to have in ones toolbox.<\/p>\n<p>We&#8217;ve been big fans of <a href=\"http:\/\/dev.iachieved.it\/iachievedit\/?p=336\">showing how Swift can be used as a general purpose scripting language<\/a> on OS X, and this example will be no different.  A reality check, however; Swift is not going to displace Python as a scripting language, but we were able to take <a href=\"http:\/\/hetland.org\/coding\/python\/quicksort.html\">this Python implementation of Quicksort<\/a> and convert it into Swift in two shakes of a lamb&#8217;s tail.<\/p>\n<p>For this tutorial, however, we&#8217;re going to use the most basic sorting algorithms of all, the venerable <a href=\"http:\/\/en.wikipedia.org\/wiki\/Bubble_sort\">bubble sort<\/a>.  We like to think of the bubble sorting algorithm as the thing you&#8217;d come up with (perhaps on the back of a napkin) given no previous experience thinking about sorting.  Let&#8217;s think about how to sort an array of <code>Int<\/code>s in Swift:<\/p>\n<pre>\r\nfunc bubblesort(list:Array<Int>) {\r\n  var swapped:Bool\r\n  do {\r\n    swapped = false\r\n    for i in 0..list.count - 1 {\r\n      if (list[i] > list[i+1]) {\r\n        swap(&list[i], &list[i+1])\r\n        swapped = true\r\n      }\r\n    }\r\n  } while swapped\r\n}\r\n<\/pre>\n<p>The details of the algorithm aren&#8217;t necessarily important, but for completeness sake, let&#8217;s review it.  So you have a list of integers, say:  10, 11, 8, 5, 27, 1, 25, and you want to sort them.  Bubble sort says, okay, I will walk along this list one integer at a time, and when I find two integers next to each other that are out of order, I&#8217;ll swap them.  Once I swap the two, I&#8217;ll move to the next pair.  After I&#8217;ve done that over the whole list, I&#8217;ll come back around and do it again, until I haven&#8217;t swapped anything, thus knowing I&#8217;m done.<\/p>\n<p>Thus in the first pass I compare 10 and 11, and since 10 is less than 11, I don&#8217;t have to swap them.  Then I look at 11 and 8.  8 <i>is<\/i> less than 11, so I swap them giving me 10, 8, 11, 5, 27, 1, 25.  Now I compare 11 and 5, and since 5 is less than 11, I swap them.  And so on.  The point is at the end (after passing through the list several times), I&#8217;ll have my sorted list:  1, 5, 8, 10, 11, 25, 27.  For a visual representation of this happening, check out <a href=\"http:\/\/en.wikipedia.org\/wiki\/Bubble_sort#mediaviewer\/File:Bubble_sort_animation.gif\">this cool animation<\/a> of bubble sort in action.<\/p>\n<p>That&#8217;s handy and all, but the <code>bubblesort<\/code> function we&#8217;ve written only handles <code>Int<\/code> arrays.  If we wanted to handle a <code>String<\/code> array, we would have to duplicate the routine and change out <code>Array<Int><\/code> for <code>Array<String><\/code>.  &#8220;There has to be a better way!&#8221; you say?  Of course there is.  Enter generics.<\/p>\n<p>We want to write a function that can sort an array of <i>any<\/i> type.  An array of <code>String<\/code>s, an array of <code>Double<\/code>s, even arrays of object types we haven&#8217;t created yet.  We do this all through <i>generics<\/i>.  Here&#8217;s the definition of our new bubble sort function:<\/p>\n<pre>\r\nfunc bubblesort<T>(list:Array<T>) {\r\n \/\/ Everything else remains the same\r\n}\r\n<\/pre>\n<p>Pay attention to the comment we wrote, &#8220;Everything else remains the same.&#8221;  That&#8217;s right.  The bubble sort algorithm doesn&#8217;t change just because we&#8217;re sorting <code>SelfSealingStemBolt<\/code>s instead of <code>String<\/code>s.<\/p>\n<p>In theory you should be able to enter this code in a text editor and run it from the command line:<\/p>\n<pre>\r\nimport Foundation\r\n\r\nfunc bubblesort<T>(list:Array<T>) {\r\n\r\n    var swapped:Bool\r\n    do {\r\n        swapped = false\r\n        for i in 0..list.count - 1 {\r\n            if (list[i] > list[i+1]) {\r\n                swap(&list[i], &list[i+1])\r\n                swapped = true\r\n            }\r\n        }\r\n    } while swapped\r\n\r\n}\r\n\r\nvar listOfNumbers = [10, 11, 8, 5, 27, 1, 25]\r\n\r\nbubblesort(listOfNumbers)\r\n\r\nprintln(listOfNumbers)\r\n<\/pre>\n<p>A side bar:  to quickly run the code above and all of our examples, add the following to the end of your <code>.bashrc<\/code> (assuming you are using <b>Beta2<\/b>, adjust appropriately if not):<\/p>\n<pre>\r\nPATH=\"\/Applications\/Xcode6-Beta2.app\/Contents\/Developer\/Toolchains\/XcodeDefault.xctoolchain\/usr\/bin\/\":$PATH\r\nalias swift='swift -sdk $(xcrun --show-sdk-path --sdk macosx) -i'\r\n<\/pre>\n<p>Re-source your <code>.bashrc<\/code>, add the code to a file called <code>~\/Documents\/generics.swift<\/code> and then just run <code>swift ~\/Documents\/generics.swift<\/code>.  See <a href=\"http:\/\/dev.iachieved.it\/iachievedit\/?p=336\">our previous post<\/a> for more details.<\/p>\n<p>We said <i>in theory<\/i> the above code would work, but in reality it won&#8217;t.  You will be greeted with the error:<\/p>\n<p><code><br \/>\nerror: could not find an overload for '>' that accepts the supplied arguments<br \/>\n<\/code><\/p>\n<p>Let&#8217;s think about what this means for a minute.  Swift has to compile your code and determine how to accomplish the task you&#8217;ve requested, namely that Swift can take <i>any type <b>T<\/b><\/i> and apply the algorithm you&#8217;ve provided.  That algorithm happens to include the <b>greater than<\/b> comparison between two objects of this generic (there&#8217;s that word again) type we are calling <b>T<\/b>.  So in effect, you are making an implicit statement about objects of type <b>T<\/b>, and that&#8217;s that they are <b>comparable<\/b>.  With Swift you need to make that statement <i>explicit<\/i>, by telling the generic function that types you will be handling adhere to certain <i>protocols<\/i>.  In our case we can use the <a href=\"https:\/\/developer.apple.com\/library\/prerelease\/ios\/documentation\/General\/Reference\/SwiftStandardLibraryReference\/\">Swift Standard Library<\/a> protocol <code><a href=\"https:\/\/developer.apple.com\/library\/prerelease\/ios\/documentation\/General\/Reference\/SwiftStandardLibraryReference\/Comparable.html\">Comparable<\/a><\/code>, like this:<\/p>\n<pre>\r\nfunc bubblesort<T:Comparable>(list:Array<T>)\r\n<\/pre>\n<p>The inclusion of the <code>:Comparable<\/code> declaration here is critical, and it tells Swift that elements given to the generic function will implement the <code>Comparable<\/code> protocol, which requires the definition of the function <b>less-than<\/b> (and subsequently also provides <b>greater-than<\/b>, as well as <b>less-than-or-equal<\/b> and <b>greater-than-or-equal<\/b>).<\/p>\n<p>With this addition we can now throw an array of integers or array of strings at our bubblesort routine.  Since <code>Int<\/code> and <code>String<\/code> adhere to the <code>Comparable<\/code> protocol out of the box, things will &#8220;just work.&#8221;<\/p>\n<p>Of course, we are not satisfied with sorting just integers and strings!  We demand more!  Enter our <code>Element<\/code> class, which holds information about an element, as in the periodic table of elements.  <\/p>\n<pre>\r\nclass Element : NSObject, Printable {\r\n  var name:String\r\n  var number:Int\r\n  init(name:String, number:Int) {\r\n    self.name   = name\r\n    self.number = number\r\n  }\r\n  override var description:String {\r\n    return \"\\(self.name) (\\(self.number))\"\r\n  }\r\n}\r\n<\/pre>\n<p>With this basic definition we can do the following:<\/p>\n<pre>\r\nimport Foundation\r\n\r\n\/\/ class Element {\r\n\/\/ }\r\n\r\nvar e:Element(name:\"Gold\", number:79)\r\n\r\nprintln(e)\r\n<\/pre>\n<p>and get <code>Gold (79)<\/code> printed.  Note that we inherit from <code>NSObject<\/code> and implement the <code>Printable<\/code> protocol to enable our ability to <code>override var description:String<\/code> and utilize <code>println<\/code> to pretty-print our element.<\/p>\n<p>Now, we want to create an array of <code>Element<\/code>s and sort them with our <code>bubblesort<\/code> routine:<\/p>\n<pre>\r\nvar listOfElements = [Element(name:\"Gold\",      number:79),\r\n                      Element(name:\"Silver\",    number:47),\r\n                      Element(name:\"Zinc\",      number:30),\r\n                      Element(name:\"Titanium\",  number:22),\r\n                      Element(name:\"Plutonium\", number:94)]\r\n\r\nbubblesort(listOfElements)\r\n\r\nprintln(listOfElements)\r\n<\/pre>\n<p>This isn&#8217;t going to work, and it should be painfully obvious as to why, but Swift will tell you if its not obvious:  <code>error: cannot convert the expression's type '()' to type 'Comparable'<\/code>.<\/p>\n<p>Our <code>bubblesort<\/code> function says &#8220;I accept generic types that adhere to the <code>Comparable<\/code> protocol&#8221;.  We have passed in a class that adheres to <code>Printable<\/code>, but we&#8217;ve said nothing about <code>Comparable<\/code>.  So let&#8217;s go back add see if we can trick Swift by just adding <code>Comparable<\/code> to the class definition.<\/p>\n<pre>\r\nclass Element : NSObject, Comparable, Printable {\r\n<\/pre>\n<p>If you are following along executing Swift code in the terminal you will see all manner of hell break loose trying to run that.  We stopped counting how many notes Swift tossed out, but they are all along the lines of <code>candidate has non-matching type (X, X) -> Bool<\/code>.  In short, the compiler is telling you, I have looked high and low trying to match global comparison functions to your class, but I can&#8217;t.  We have declared our class to follow the <code>Comparable<\/code> protocol, but didn&#8217;t back it up with an implementation as to <i>what it means to compare two elements<\/i>.  So we have to do that.<\/p>\n<p>So, what does it mean to compare two <code>Element<\/code>s?  We aren&#8217;t chemists (thank God), so we&#8217;ll just make something up for illustration and say that &#8220;a given element X is less than a given element Y if the atomic number of X is less than the atomic number of Y&#8221;.  That&#8217;s a fancy way of saying, &#8220;elements are sorted by their atomic number.&#8221;  <\/p>\n<p>To implement, we add the following <i>outside the class body<\/i>:<\/p>\n<pre>\r\nfunc < (lhs:Element, rhs:Element) -> Bool {\r\n    return lhs.number < rhs.number\r\n}\r\n<\/pre>\n<p><i>Now<\/i> Swift will have a function that \"matches\" when it goes looking for something to fulfill the <code>Comparable<\/code> protocol for <code>Element<\/code>.  The code embodies what we wrote out, and <code>lhs<\/code> and <code>rhs<\/code> are simply abbreviations for \"left-hand side\" and \"right-hand side\", meaning of the equation.  <\/p>\n<p>We are <i>almost<\/i> done.  When declaring yourself to adhere to the <code>Comparable<\/code>, you are also declaring support for the <code><a href=\"https:\/\/developer.apple.com\/library\/prerelease\/ios\/documentation\/General\/Reference\/SwiftStandardLibraryReference\/Equatable.html\">Equatable<\/a><\/code> protocol, which requires you to define <code>==<\/code> (equality).  So, we oblige with:<\/p>\n<pre>\r\nfunc == (lhs:Element, rhs:Element) -> Bool {\r\n    return lhs.number == rhs.number\r\n}\r\n<\/pre>\n<p>Add it all up and you should have:<\/p>\n<pre>\r\nclass Element : NSObject, Comparable, Printable {\r\n    var name:String\r\n    var number:Int\r\n    init(name:String,number:Int) {\r\n        self.name   = name\r\n        self.number = number\r\n    }\r\n\r\n    override var description: String {\r\n        return \"\\(self.name) (\\(self.number))\"\r\n    }\r\n}\r\n\r\n\/\/ Support Equatable\r\nfunc == (lhs:Element, rhs:Element) -> Bool {\r\n    return lhs.number == rhs.number\r\n}\r\n\r\n\/\/ Support Comparable\r\nfunc < (lhs:Element, rhs:Element) -> Bool {\r\n    return lhs.number < rhs.number\r\n}\r\n\r\n\/\/ Generic Bubblesort\r\nfunc bubblesort<T:Comparable>(list:Array<T>) {\r\n\r\n    var swapped:Bool\r\n    do {\r\n        swapped = false\r\n        for i in 0..list.count - 1 {\r\n            if (list[i] > list[i+1]) {\r\n                swap(&list[i], &list[i+1])\r\n                swapped = true\r\n            }\r\n        }\r\n    } while swapped\r\n\r\n}\r\n\r\nvar listOfElements = [Element(name:\"Gold\",      number:79),\r\n                      Element(name:\"Silver\",    number:47),\r\n                      Element(name:\"Zinc\",      number:30),\r\n                      Element(name:\"Titanium\",  number:22),\r\n                      Element(name:\"Plutonium\", number:94)]\r\n\r\nbubblesort(listOfElements)\r\n\r\nprintln(listOfElements)\r\n<\/pre>\n<p>Run this code and see the magic:<\/p>\n<p><code><br \/>\n[Titanium (22), Zinc (30), Silver (47), Gold (79), Plutonium (94)]<br \/>\n<\/code><\/p>\n<p>To recap:  <a href=\"https:\/\/developer.apple.com\/library\/prerelease\/mac\/documentation\/Swift\/Conceptual\/Swift_Programming_Language\/Generics.html\">Swift's support of generics<\/a> allows us developers to write algorithms and data structures that are not bound to a concrete type or the type's implementation.  In the above example we explored only the generic algorithm, but Swift also supports generic types for implementing data structures such as stacks, queues, etc.  We will admit, the syntax can be a bit daunting (too many brackets!) and <code>T<\/code>erse (get it?), but with patience and perseverance you'll be writing your own generic data structures and algorithms in no time.<\/p>\n<p>Now, we promised an implementation of Quicksort in Swift using generics.  You can find a full example on <a href=\"http:\/\/pastebin.com\/PChnWmQw\">Pastebin<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Learning a new programming language is fun, and learning Swift has been no different. We&#8217;ve been covering, through brief tutorials, features that most Objective-C programmers will find to be new. As many have observed, Swift borrows from many different languages and brings the &#8220;best&#8221; features together in a single language. One such feature is generics. [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[10,9,7,8],"class_list":["post-375","post","type-post","status-publish","format-standard","hentry","category-swift","tag-generics","tag-ios8","tag-swift-2","tag-xcode6"],"_links":{"self":[{"href":"https:\/\/dev.iachieved.it\/iachievedit\/wp-json\/wp\/v2\/posts\/375"}],"collection":[{"href":"https:\/\/dev.iachieved.it\/iachievedit\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dev.iachieved.it\/iachievedit\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dev.iachieved.it\/iachievedit\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dev.iachieved.it\/iachievedit\/wp-json\/wp\/v2\/comments?post=375"}],"version-history":[{"count":30,"href":"https:\/\/dev.iachieved.it\/iachievedit\/wp-json\/wp\/v2\/posts\/375\/revisions"}],"predecessor-version":[{"id":4907,"href":"https:\/\/dev.iachieved.it\/iachievedit\/wp-json\/wp\/v2\/posts\/375\/revisions\/4907"}],"wp:attachment":[{"href":"https:\/\/dev.iachieved.it\/iachievedit\/wp-json\/wp\/v2\/media?parent=375"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dev.iachieved.it\/iachievedit\/wp-json\/wp\/v2\/categories?post=375"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dev.iachieved.it\/iachievedit\/wp-json\/wp\/v2\/tags?post=375"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}