Visual explanation of Merge Sort Complexity

How do we derive complexity of merge sort using its recursive relation? Every wondered how merge sort results in a logarithmic time complexity? How many leaf nodes are in a merge sort recursion tree? How do we know the height of merge sort recursion tree? What does a logarithm time complexity means in the mathematical sense?

The following explanation should demystify all the above questions for you.

Click image to view full size

Click image to view full size

 

Understanding CALayer anchorPoint and position property

For me understanding position and anchorPoint was easiest when I started comparing it with my understanding of frame.origin in UIView. A UIView with frame.origin = (20,30) means that the UIView is 20 points from left and 30 points from top of its parent view. This distance is calculated from which point of a UIView? Its calculated from top-left corner of a UIView.

In layer anchorPoint marks the point (in normalized form or unit-coordinates i.e. 0 to 1) from where this distance is calculated so e.g. layer.position = (20, 30) means that the layer anchorPoint is 20 points from left and 30 points from top of its parent layer. By default a layer anchorPoint is (0.5, 0.5) so the distance calculation point is right in the center of the layer. The following figure will help clarify my point:

anchorPoint also happens to be the point around which rotation will happen in case you apply a transform to the layer.

Supporting Custom URL Schemes in iOS App

To enable your iOS app to respond to custom URLs from third party application you need to do some changes. If you want the app to respond to click of following url scheme:

talsa://article/ios?id=201244075

The URL should follow format: scheme://host/path?query and the following changes need to be done in xcode project .plist file:

plist

The app delegate should provide a similar custom implementation:

-(BOOL)application:(UIApplication *)application handleOpenURL:(NSURL *)url
{
    if ([[url absoluteString] hasPrefix:@"talsa"]) //talsa
    {
        NSDictionary* parameters = [self parseQueryString:[url query]];
        NSString* articleId = [parameters valueForKey:@"id"];
        if (articleId != nil)
        {
            //do something here, open a view or whatever
        }
        return YES;
    }
    return NO;
}

- (NSDictionary *)parseQueryString:(NSString *)query
{
    NSMutableDictionary *dict = [[[NSMutableDictionary alloc] init] autorelease];
    NSArray *pairs = [query componentsSeparatedByString:@"&"];

    for (NSString *pair in pairs)
    {
        NSArray *elements = [pair componentsSeparatedByString:@"="];
        NSString *key = [[elements objectAtIndex:0] stringByReplacingPercentEscapesUsingEncoding:NSUTF8StringEncoding];
        NSString *val = [[elements objectAtIndex:1] stringByReplacingPercentEscapesUsingEncoding:NSUTF8StringEncoding];

        [dict setObject:val forKey:key];
    }
    return dict;
}

In circumstances where url is more complicated e.g. it included another url as input parameter then URL would need to be specified in URL encoded form: http://www.w3schools.com/TAGS/ref_urlencode.asp i.e.

URL in encoded form:

scheme://url_identifier/ios?accesscode=123456789&callback=http%3A%2F%2Fwww%2Efoo%2Ecom

URL in normal form:

scheme://url_identifier/ios?accesscode=123456789&callback=http://www.foo.com

Time Complexity of Binary Search or Similar Recursive Tree

Binary tree is a special case where a problem of size n is divided into sub-problem of size n/2. Let me show you how to calculate the height of tree in which a problem is divided into subproblems of size b until we recursively reach a problem of size 1.

Binary Search Tree Recursive Relation = T(n/2) + O(1)

If you feel like thanking just follow me on Twitter

Shake animation to a UIView or UIButton

I think button shake is such a nice effect that could be applied to different views especially in cases where you want to indicator an error. On a mobile device where you are limited for screen space a shake effect is even more elegant.

Lets see the button shake in action first:

And here is the small objectiveC code that you can use to produce a similar effect for any UIView, call startShake on the view you want to shake:

- (void) startShake:(UIView*)view
{
    CGAffineTransform leftShake = CGAffineTransformMakeTranslation(-5, 0);
    CGAffineTransform rightShake = CGAffineTransformMakeTranslation(5, 0);

    view.transform = leftShake;  // starting point

    [UIView beginAnimations:@"shake_button" context:view];
    [UIView setAnimationRepeatAutoreverses:YES]; // important
    [UIView setAnimationRepeatCount:5];
    [UIView setAnimationDuration:0.06];
    [UIView setAnimationDelegate:self];
    [UIView setAnimationDidStopSelector:@selector(shakeEnded:finished:context:)];

    view.transform = rightShake; // end here & auto-reverse

    [UIView commitAnimations];
}

- (void) shakeEnded:(NSString *)animationID finished:(NSNumber *)finished context:(void *)context
{
    if ([finished boolValue]) {
        UIView* item = (UIView *)context;
        item.transform = CGAffineTransformIdentity;
    }
}

3D Flip Between Two View or ViewGroup on Android

3D flip makes a nice effect. It seems like there is no good android implementation on the internet that shows how to make two generic view flip with each other. Let me first show you the end result, the card flips if you clicking on it anywhere.

First the activity layout file:


<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
xmlns:tools="http://schemas.android.com/tools"
android:id="@+id/main_activity_root"
android:layout_width="fill_parent"
android:layout_height="fill_parent"
android:background="@android:color/transparent" >

<RelativeLayout
android:id="@+id/main_activity_card_face"
android:layout_width="300dp"
android:layout_height="407dp"
android:layout_centerHorizontal="true"
android:layout_centerVertical="true"
android:background="@drawable/front"
android:clickable="true"
android:onClick="onCardClick"
android:padding="5dp" >
</RelativeLayout>

<RelativeLayout
android:id="@+id/main_activity_card_back"
android:layout_width="300dp"
android:layout_height="407dp"
android:layout_centerHorizontal="true"
android:layout_centerVertical="true"
android:background="@drawable/back"
android:clickable="true"
android:onClick="onCardClick"
android:visibility="gone" >
</RelativeLayout>

</RelativeLayout>

As the layout file flips two view groups you could put anything else inside the view group and it should work. Now lets look at the methods inside the activity which handles calling the flip animation code:

public void onCardClick(View view)
{
      flipCard();
}

private void flipCard()
{
	View rootLayout = (View) findViewById(R.id.main_activity_root);
	View cardFace = (View) findViewById(R.id.main_activity_card_face);
	View cardBack = (View) findViewById(R.id.main_activity_card_back);

	FlipAnimation flipAnimation = new FlipAnimation(cardFace, cardBack);

	if (cardFace.getVisibility() == View.GONE)
	{
		flipAnimation.reverse();
	}
	rootLayout.startAnimation(flipAnimation);
}

And finally the FlipAnimation class:

public class FlipAnimation extends Animation
{
    private Camera camera;

    private View fromView;
    private View toView;

    private float centerX;
    private float centerY;

    private boolean forward = true;

    /**
     * Creates a 3D flip animation between two views.
     *
     * @param fromView First view in the transition.
     * @param toView Second view in the transition.
     */
	public FlipAnimation(View fromView, View toView)
    {
        this.fromView = fromView;
        this.toView = toView;

		setDuration(700);
        setFillAfter(false);
        setInterpolator(new AccelerateDecelerateInterpolator());
    }

    public void reverse()
    {
        forward = false;
		View switchView = toView;
        toView = fromView;
        fromView = switchView;
    }

    @Override
    public void initialize(int width, int height, int parentWidth, int parentHeight)
    {
        super.initialize(width, height, parentWidth, parentHeight);
        centerX = width/2;
        centerY = height/2;
        camera = new Camera();
    }

    @Override
    protected void applyTransformation(float interpolatedTime, Transformation t)
    {
        // Angle around the y-axis of the rotation at the given time
        // calculated both in radians and degrees.
        final double radians = Math.PI * interpolatedTime;
        float degrees = (float) (180.0 * radians / Math.PI);

        // Once we reach the midpoint in the animation, we need to hide the
        // source view and show the destination view. We also need to change
        // the angle by 180 degrees so that the destination does not come in
        // flipped around
        if (interpolatedTime >= 0.5f)
        {
            degrees -= 180.f;
            fromView.setVisibility(View.GONE);
            toView.setVisibility(View.VISIBLE);
        }

        if (forward)
            degrees = -degrees; //determines direction of rotation when flip begins

        final Matrix matrix = t.getMatrix();
        camera.save();
        camera.rotateY(degrees);
        camera.getMatrix(matrix);
        camera.restore();
        matrix.preTranslate(-centerX, -centerY);
        matrix.postTranslate(centerX, centerY);
    }

The FlipAnimation code was borrowed from code I found somewhere on internet. I can’t find reference to it anymore so if anyone happens to find anything similar please provide reference in the comments and I’ll link it up. The images I used in the code you can grab similar images from here.

Try modifying the code and making a flip around X axis and if you read this far consider following me on Twitter:

TextView drawables & XML state list resource

Its painfully bad to change graphic of a TextView drawable programmatically. If you want android:drawableRight, android:drawableLeftandroid:drawableTop or android:drawableBottom to change based on the TextView state it is possible to do it simply the same way you would specify to a android:background attribute. There should be no need to change any of these properties programmatically. It is much more neat & efficient to deal with this in the layout file.

e.g. in your layout file:

android:drawableRight="@drawable/icon_accept_selector"

icon_accept_selector is an XML state list drawable file:

<?xml version="1.0" encoding="utf-8"?>
<selector xmlns:android="http://schemas.android.com/apk/res/android">
    <item android:drawable="@drawable/icon_accept" android:state_enabled="true"/>
    <item android:drawable="@drawable/icon_accept_disabled" android:state_enabled="false"/>
</selector>