Thanh Pham Thanh Pham - 4 months ago 44
Swift Question

Swift: Why the CustomStringConvertible description is run too many times in this case?

I was trying this code in Xcode Playground and noticed that the

description
getter method got called too many times.

The code is here: https://gist.github.com/T-Pham/4b72d17851162a32b2fc534f0618135d

First with both
print
lines, the code is run 3176 times.

enter image description here

Then with the first
print
commented out, the code is run 3164 times.

enter image description here

That means the first
print
would have to run the code 12 times.
However,

enter image description here

it is 148 times instead.

Answer

It is the playground that is messing with your head.

Playground is counting calls of its own for variables that have the CustomStringConvertibe protocol (probably to feed the information on the right side panel).

You can see this going on if you simply invoke mirror(tree) without printing at all.

If you count the actual number of invocations using your own counter, it will give a very different result:

 var descCount = 0
 extension Node: CustomStringConvertible {
     var description: String 
     {
         descCount += 1
         return "id: \(id)\nleft: \(left)\nright: \(right)"
     }
 }

 descCount = 0
 print(tree)
 descCount   // 12

 descCount = 0
 print(mirror(tree))
 descCount   // 12 

By the way, I had a little trouble understanding the mirror() function and I figured that a recursive one would probably be simpler to understand. How about adding a mirror() function to Node :

 func mirror() -> Node
 {
    let result = Node()
    result.id      = id
    result.left    = right?.mirror()
    result.right   = left?.mirror()
    return result
 }

 print(tree.mirror())

[EDIT] Here's a non-recursive mirror function (same logic as yours) with a somewhat clearer structure:

 func mirror2(tree:Node) -> Node
 {
    // will return top of mirrored tree
    let newTree = Node()

    // node pair used for traversal and duplication
    var original:Node! = tree
    var mirrored:Node! = newTree

    // traversal of tree structure left side first
    // (uses mirrored tree to keep track of traversed nodes)
    while original != nil
    {
       // carry node identifier (and contents eventually)
       mirrored.id = original.id

       // downwards, mirror left side first (if not already done)
       if original.left?.id !== mirrored.right?.id
       {
          original       = original.left
          mirrored.right = Node()
          mirrored       = mirrored.right! 
          continue     
       }

       // downwards, mirror right side second (if not already done)
       if original.right?.id !== mirrored.left?.id
       {
          original      = original.right
          mirrored.left = Node()
          mirrored      = mirrored.left!
          continue
       }

       // upwards from leaves
       original = original.parent
       mirrored = mirrored.parent
    }
    return newTree
 }

and some visual candy for tree descriptions:

 extension Node: CustomStringConvertible 
 {
     var indent:String 
     { return "  " + (parent?.indent ?? "") }
     var description: String 
     {
         return "\(id)\n"
              + ( left  != nil ? "\(indent)L:\(left!)" : "" )
              + ( right != nil ? "\(indent)R:\(right!)" : "" )
     }
 }

resulting in an easier comparison of results:

 print(tree)

 // 0
 //   L:1
 //     L:3
 //       L:7
 //       R:8
 //     R:4
 //       L:9
 //       R:10
 //   R:2
 //     R:6
 //       L:13
 //       R:14
 //

 print(mirror2(tree))

 //  0
 //    L:2
 //      L:6
 //        L:14
 //        R:13
 //    R:1
 //      L:4
 //        L:10
 //        R:9
 //      R:3
 //        L:8
 //        R:7
Comments