Implementing an URL shortener using Django/Python

Posted on by

Recently, I implemented an URL shortener service and this post describes the design decisions that I took while implementing it. I have always been in love with Python because of it’s offerings that enable developers to write beautiful code. I decided to use the Django web framework for writing the URL shortener as it is simple enough to easily get started with.

The specs are as below. This webservice will expose the following APIs:

POST /shorten
Parameters: Parameter link contains the link to shorten.
Returns: Id for the shortened link in text/plain format.

GET /{id}
Returns: 301 redirects the user agent to a previously stored URL. 404 error if no link stored with given id.

The core functionality that such a service provides is that it shortens an URL as much as possible, while still being fast in it’s lookups. The obvious way to implement the shortening is to use a classical computer science concept — Hashing. The advantages of using a hashtable are:

  • All traditional hash functions such as MD5, SHA-1, CRC32 provide collision resistance to a significant level. This guarantees that no two different urls will have the same shortened url until we accumulate a considerable amount of URLs in our service. For example, MD5 takes any arbitrary length of string and outputs 128 bits. The Birthday problem tells us that there will be a collision only after 2^64 URLs. That is, after 18,446,744,073,709,551,616 URLs.
  • If we maintain a hashtable, the lookups are really fast. If we maintain an in-memory datastructure, the lookup is O(1). If we decide to store it in an RDBMS, we can create an index for the shortened id column.

But the obvious problem is that the output is not short enough. MD5 provides a 32 length hex string. This makes hashing unusable for our URL shortening.

Another approach is to use a simple rolling index, where we start with value 1, and we keep incrementing by 1 for every new URL. This index can be converted to an alphanumeric string (a-zA-Z0-9) by doing a simple base 62 encoding. The vice-versa is also simple, we just need to decode the string to get the index. This way, we can start with 1 letter shortened URL and when we run out of one-letter URLs, we can move to 2-letter URLs and so on.

Implementing the base 62 encoding/decoding is simple:

import math

ALLOWED_ALPHABETS = [
	'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s',
	't','u','v','w','x','y','z','A','B','C','D','E','F','G','H','I','J','K','L',
	'M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','1','2','3','4','5',
	'6','7','8','9','0'
]

string_to_digit_map = {}

ctr = 0
for alpha in ALLOWED_ALPHABETS:
	string_to_digit_map[alpha] = ctr
	ctr = ctr + 1

def convert_to_base62(id):
	base62_string = ''
	while id > 0:
		rem = id % 62
		id = id / 62
		base62_string = ALLOWED_ALPHABETS[rem] + base62_string
	return base62_string

def convert_from_base62(string):
	res = 0
	digit_ctr = len(string) - 1
	for char in string:
		if char not in string_to_digit_map:
			return -1
		res = res + string_to_digit_map[char] * int(math.pow(62, digit_ctr))
		digit_ctr = digit_ctr - 1
	return res

Using this approach, the rolling index doesn’t need any special logic. An auto-increment primary key in an RDBMS will do the job. So, the model for our URL class would look like this:

from django.db import models

class Url(models.Model):
	"""
	Model representing each url shortened. The primary key (auto-generated) becomes
	the shortened url.
	"""

	url = models.TextField()
	date_created = models.DateTimeField()
	date_last_accessed = models.DateTimeField(null=True)
	visits = models.IntegerField(null=True)

With the models in place, we come to the controller (which are called ‘views’ in Django). Our controller just has two methods, one to shorten a given URL and another to redirect to the original URL, given a shortened URL. In the shorten method, we have to make sure that the URL contains a scheme (http/https) and if it doesn’t we add a default ‘http’ scheme. Now, we also need to check if we already have a shortened URL for the given URL, so that we don’t have duplicate shortened URLs for the same URLs.

import urllib2
from django.shortcuts import render, get_object_or_404
from django.shortcuts import redirect as http_redirect
from django.views.decorators.http import require_http_methods
from django.http import HttpResponse, HttpResponsePermanentRedirect, HttpResponseBadRequest
from shorten.models import Url
from shorten.conversions import convert_to_base62, convert_from_base62
from datetime import datetime
from django.http import Http404
from urlparse import urlparse

def redirect(request, query):
	print query
	id = convert_from_base62(query)
	if id < 0:
		#Unknown shortened url
		raise Http404("Url does not exist")

	url = get_object_or_404(Url, id=id)
	return HttpResponsePermanentRedirect(url.url)


@require_http_methods(["POST"])
def shorten(request):
	if request.META.get('CONTENT_TYPE') != "application/x-www-form-urlencoded":
		print "Not application/x-www-form-urlencoded"

	submitted_url = request.POST.get('link')
	if submitted_url == None or len(submitted_url) == 0:
		return HttpResponseBadRequest("No url specified.")

	#Make sure we have a scheme for the url. Else add http as default.
	url_parsed = urlparse(submitted_url.strip())
        if url_parsed.scheme == '':
            submitted_url = "http://"+ submitted_url
	print "Shorten request:", submitted_url

	#Check if we already have already shortened this URL
	url = None

	try:
		url = Url.objects.get(url=submitted_url)
	except Url.DoesNotExist:
		print "New Url"

	if url != None:
		#We already have a shortened url for the given url
		return HttpResponse(convert_to_base62(url.id))

	url = Url()
	url.url = submitted_url
	url.date_created = datetime.now()
	url.save()
	return HttpResponse(convert_to_base62(url.id))

And finally for the routes (URL mapping for the web service):

from django.conf.urls import patterns, include, url
import shorten.views

urlpatterns = patterns('',
    url(r'shorten/$', 'shorten.views.shorten'),
    url(r'shorten$', 'shorten.views.shorten'),
    url(r'(?P<query>\w+)', 'shorten.views.redirect'),
)

The last regex matches any ‘word’ (represented by \w+) and should be the last route, since the other mappings should take precedence.

The full project is available in GitHub at https://github.com/c05mic/django-url-shortener

Would love your comments on the implementation.

Timer with Pause and Resume Support – Android/Java

Posted on by

The CountDownTimer implementation of Android may not be suitable for all cases as the onTick() method of the CountDownTimer runs on the main/UI thread.

The same could also be achieved using a TimerTask, but we do not have support for Pause/Resume operations when you’re using a Timer and a TimerTask.

The following implementation of a generic Timer runs on a separate thread and hence is most suitable for any operation that does not involve UI updates. It is basically a wrapper around a Runnable scheduled with a ScheduledExecutorService which is part of the java.util.concurrent package. The following is a gist of the core Runnable that handles the tick.

future = execService.scheduleWithFixedDelay(new Runnable() {
	@Override
	public void run() {
		onTick();
		elapsedTime += Timer.this.interval;
		if (duration > 0) {
			if(elapsedTime >=duration){
				onFinish();
				future.cancel(false);
			}
		}
	}
}, 0, interval, TimeUnit.MILLISECONDS);

For pause, we cancel the Future instance that we obtained when we scheduled the Runnable using the ExecutorService.

future.cancel(false);

For resume, we just schedule the same Runnable again.

We leave the following methods as abstract, to force the classes extending the Timer class to override them.

/**
*	This method is called periodically with the interval set as the delay between subsequent calls.
*/
	protected abstract void onTick();

/**
* This method is called once the timer has run for the specified duration. If the duration was set as infinity, then   * this method is never called.
*/
	protected abstract void onFinish();

Following is an example implementation of a concrete class extending the abstract Timer:

public class ExampleTimer extends Timer{

	public ExampleTimer() {
		super();
	}

	public ExampleTimer(long interval, long duration){
		super(interval, duration);
	}

	@Override
	protected void onTick() {
		System.out.println("onTick called!");
	}

	@Override
	protected void onFinish() {
		System.out.println("onFinish called!");
	}

}

Following is a simple test showing the usage of the Timer.

//This creates a timer which will tick every second indefinitely.
Timer oneSecondInfiniteTimer = new ExampleTimer();

//This creates a timer which ticks every 2 seconds, and runs for 20 seconds.
Timer twoSecondTimer = new ExampleTimer(2000l, 20000l);

//Start the timer.
twoSecondTimer.start();

//Pause the timer.
twoSecondTimer.pause();

//Resume the timer
twoSecondTimer.resume();

The whole code is hosted in GitHub (https://github.com/c05mic/pause-resume-timer ) for your copy-pasting pleasure. 🙂

Contributions are welcome!

Generic N-ary Tree implementation in Java

Posted on by

I needed a simple implementation of a Generic N-ary tree in Java with some useful utility methods for my work, and to my surprise I couldn’t find a simple library that will do the job. So I went ahead and wrote it myself.

You can find it here: https://github.com/c05mic/GenericN-aryTree . Please “star” the repository if you find it useful. 🙂

Features methods:

  • To check if a node exists in the tree.
  •  To find the total number of nodes in the tree
  • To find the total number of descendants of any node in the tree.
  •  To get all the paths from the root to all the leaves as an ArrayList.
  •  To get the longest path from the root to any leaf.
  •  To get the pre-order/post-order traversal path as an ArrayList.

Contributions are welcome!

Activity as a Dialog – Android

Posted on by

It’d be cool to have an Activity to be shown like a Dialog, with the previous activity still in the background.

It turns out that this can easily be done, making use of the android:theme attribute in your activity tag in the AndroidManifest.xml file.

<activity
 android:name=".YourActivityName"
 android:theme="@style/CustomDialog" >
 </activity>

where CustomDialog is a style that we declare in styles.xml (which should go into the res/values folder). Put the following inside the styles.xml.

<?xml version="1.0" encoding="utf-8"?>
<resources>

<style name="CustomDialog" parent="@android:style/Theme.Dialog">
 <item name="android:windowBackground">@color/transparent</item>
 <item name="android:windowIsFloating">true</item>
 <item name="android:windowNoTitle">true</item>
 </style>

</resources>

Start your activity, as you normally would, using startActivity(Intent intent).

Animating an image using Path and PathMeasure – Android

Posted on by

Animating an image along a predefined path (be it a line or a curve) is a common situation that game developers face. Instead of doing it the usual way (Finding the equation of the path, substituting x and finding y values and then using the co-ordinates [x,y] for the animation), we can do this in a more simpler way by making use of Path and PathMeasure.

If you already have a game loop running with its update and render cycles, the following code can easily be implemented. If you’re new to game loops, Obviam.net explains the concept behind game loops in a very concise manner.

Suppose, I want to move an image in a straight line from (0,0) to, say, (100, 100).

Following is a code snippet that shows you how to do it:

Declare the variables that we’d be using:

Path path;
PathMeasure measure;
float[] pos, tan;
float speed, distance;

Initialize your Path object and other variables that we’d be using later on. You could do this on your surfaceCreated() callback if you are using a SurfaceView.

// Init the Path.
 path=new Path();

// Set the starting position of the path to (0,0).
 path.moveTo(0,0); 

// Add a line to the Path, starting from (0,0), ending at (100, 100).
 path.lineTo(100,100); 

// Create a PathMeasure object, passing in the Path object
 // we created and a boolean that specifies if the Path should
 // be forced to a closed path.
 measure = new PathMeasure(path, false);

// Here, we're dividing the whole length of the path by 30.
 speed = measure.getLength() / 30;


pos=new float[2];
 tan=new float[2];

The concept behind the moving of the image is simple: Staring at (0,0), in every update cycle, we find a point along the defined path, traversing a little each time.
Now inside the update() method of our game loop, we’d be doing the following:

 public void update()
 {
 while(distance < measure.getLength())
 {

    // getPosTan pins the distance along the Path and
 // computes the position and the tangent.
 measure.getPosTan(distance, pos, tan);

     distance += speed;   // Traversal
 }
 }


Now to render,

 public void render(Canvas canvas)
 {

    //Draw the bitmap on the canvas, passing in the
 //Bitmap object, the x and y co-ordinate and a
 // Paint object.
 canvas.render(bmpImage, pos[0], pos[1], null);
 }

Here the speed directly determines the speed of the animation. Playing with that value, you can arrive at your desired speed.

Just like a line, you can also use curves, Bezier curves, arcs, etc., and a combination of these as well.

Hope this helps!