Binary Search Tree library in Python

December 18, 2010

This article is about a Python library I created to manage binary search trees. I will go over the following:

  • Node class
  • Insert method
  • Lookup method
  • Delete method
  • Print method
  • Comparing 2 trees
  • Generator returning the tree elements one by one

You can checkout the library code on GitHub: git clone https://laurentluce@github.com/laurentluce/python-algorithms.git. This folder contains more libraries but we are just going to focus on the Binary Tree one.

As a reminder, here is a binary search tree definition (Wikipedia).

A binary search tree (BST) or ordered binary tree is a node-based binary tree data structure which has the following properties:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Here is an example of a binary search tree:

Node class

We need to represent a tree node. To do that, we create a new class named Node with 3 attributes:

  • Left node
  • Right node
  • Node’s data (same as key in the definition above.)
class Node:
    """
    Tree node: left and right child + data which can be any object
    """
    def __init__(self, data):
        """
        Node constructor

        @param data node data object
        """
        self.left = None
        self.right = None
        self.data = data

Let’s create a tree node containing the integer 8. You can pass any object for the data so it is flexible. When you create a node, both left and right node equal to None.

root = Node(8)

Note that we just created a tree with a single node.

Insert method

We need a method to help us populate our tree. This method takes the node’s data as an argument and inserts a new node in the tree.

class Node:
    ...
    def insert(self, data):
        """
        Insert new node with data

        @param data node data object to insert
        """
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

insert() is called recursively as we are locating the place where to add the new node.

Let’s add 3 nodes to our root node which we created above and let’s look at what the code does.

root.insert(3)
root.insert(10)
root.insert(1)

This is what happens when we add the second node (3):

  • 1- root node’s method insert() is called with data = 3.
  • 2- 3 is less than 8 and left child is None so we attach the new node to it.

This is what happens when we add the third node (10):

  • 1- root node’s method insert() is called with data = 10.
  • 2- 10 is greater than 8 and right child is None so we attach the new node to it.

This is what happens when we add the fourth node (1):

  • 1- root node’s method insert() is called with data = 1.
  • 2- 1 is less than 8 so the root’s left child (3) insert() method is called with data = 1. Note how we call the method on a subtree.
  • 3- 1 is less than 3 and left child is None so we attach the new node to it.

This is how the tree looks like now:

Let’s continue and complete our tree so we can move on to the next section which is about looking up nodes in the tree.

root.insert(6)
root.insert(4)
root.insert(7)
root.insert(14)
root.insert(13)

The complete tree looks like this:

Lookup method

We need a way to look for a specific node in the tree. We add a new method named lookup which takes a node’s data as an argument and returns the node if found or None if not. We also return the node’s parent for convenience.

class Node:
    ...
    def lookup(self, data, parent=None):
        """
        Lookup node containing data

        @param data node data object to look up
        @param parent node's parent
        @returns node and node's parent if found or None, None
        """
        if data < self.data:
            if self.left is None:
                return None, None
            return self.left.lookup(data, self)
        elif data > self.data:
            if self.right is None:
                return None, None
            return self.right.lookup(data, self)
        else:
            return self, parent

Let’s look up the node containing 6.

node, parent = root.lookup(6)

This is what happens when lookup() is called:

  • 1- lookup() is called with data = 6, and default value parent = None.
  • 2- data = 6 is less than root’s data which is 8.
  • 3- root’s left child lookup() method is called with data = 6, parent = current node. Notice how we call lookup() on a subtree.
  • 4- data = 6 is greater than node’s data which is now 3.
  • 5- node’s right child lookup() method is called with data = 6 and parent = current node
  • 6- node’s data is equal to 6 so we return it and its parent which is node 3.

Delete method

The method delete() takes the data of the node to remove as an argument.

class Node:
    ...
    def delete(self, data):
        """
        Delete node containing data

        @param data node's content to delete
        """
        # get node containing data
        node, parent = self.lookup(data)
        if node is not None:
            children_count = node.children_count()
        ...

There are 3 possibilities to handle:

  • 1- The node to remove has no child.
  • 2- The node to remove has 1 child.
  • 3- The node to remove has 2 children.

Let’s tackle the first possibility which is the easiest. We look for the node to remove and we set its parent’s left or right child to None. If it is the root node (no parent), we clear its data.

    def delete(self, data):
        ...
        if children_count == 0:
            # if node has no children, just remove it
            if parent:
                if parent.left is node:
                    parent.left = None
                else:
                    parent.right = None
                del node
            else:
                self.data = None
        ...

Note: children_count() returns the number of children of a node.

Here is the function children_count:

class Node:
    ...
    def children_count(self):
        """
        Returns the number of children

        @returns number of children: 0, 1, 2
        """
        cnt = 0
        if self.left:
            cnt += 1
        if self.right:
            cnt += 1
        return cnt

For example, we want to remove node 1. Node 3 left child will be set to None.

root.delete(1)

Let’s look at the second possibility which is the node to be removed has one child. We replace the node with its child. We also handle the special case when the node is the root of the tree.

    def delete(self, data):
        ...
        elif children_count == 1:
            # if node has 1 child
            # replace node with its child
            if node.left:
                n = node.left
            else:
                n = node.right
            if parent:
                if parent.left is node:
                    parent.left = n
                else:
                    parent.right = n
                del node
            else:
                self.left = n.left
                self.right = n.right
                self.data = n.data
        ...

For example, we want to remove node 14. Node 14 data will be set to 13 (its left child’s data) and its left child will be set to None.

root.delete(14)

Let’s look at the last possibility which is the node to be removed has 2 children. We replace its data with its successor’s data and we fix the successor’s parent’s child.

    def delete(self, data):
        ...
        else:
            # if node has 2 children
            # find its successor
            parent = node
            successor = node.right
            while successor.left:
                parent = successor
                successor = successor.left
            # replace node data by its successor data
            node.data = successor.data
            # fix successor's parent's child
            if parent.left == successor:
                parent.left = successor.right
            else:
                parent.right = successor.right

For example, we want to remove node 3. We look for its successor by going right then left until we reach a leaf. Its successor is node 4. We replace 3 with 4. Node 4 doesn’t have a child so we set node 6 left child to None.

root.delete(3)

Print method

We add a method to print the tree inorder. This method has no argument. We use recursion inside print_tree() to walk the tree depth-first. We first traverse the left subtree, then we print the root node then we traverse the right subtree.

class Node:
    ...
    def print_tree(self):
        """
        Print tree content inorder
        """
        if self.left:
            self.left.print_tree()
        print self.data,
        if self.right:
            self.right.print_tree()

Let’s print our tree:

root.print_tree()

The output will be: 1, 3, 4, 6, 7, 8, 10, 13, 14

Comparing 2 trees

To compare 2 trees, we add a method which compares each subtree recursively. It returns False when one leaf is not the same in both trees. This includes 1 leaf missing in the other tree or the data is different. We need to pass the root of the tree to compare to as an argument.

class Node:
    ...
    def compare_trees(self, node):
        """
        Compare 2 trees

        @param node tree's root node to compare to
        @returns True if the tree passed is identical to this tree
        """
        if node is None:
            return False
        if self.data != node.data:
            return False
        res = True
        if self.left is None:
            if node.left:
                return False
        else:
            res = self.left.compare_trees(node.left)
        if res is False:
            return False
        if self.right is None:
            if node.right:
                return False
        else:
            res = self.right.compare_trees(node.right)
        return res

For example, we want to compare tree (3, 8, 10) with tree (3, 8, 11)

# root2 is the root of tree 2
root.compare_trees(root2)

This is what happens in the code when we call compare_trees().

  • 1- The root node compare_trees() method is called with the tree to compare root node.
  • 2- The root node has a left child so we call the left child compare_trees() method.
  • 3- The left subtree comparison will return True.
  • 2- The root node has a right child so we call the right child compare_trees() method.
  • 3- The right subtree comparison will return False because the data is different.
  • 4- compare_trees() will return False.

Generator returning the tree elements one by one

It is sometimes useful to create a generator which returns the tree nodes values one by one. It is memory efficient as it doesn’t have to build the full list of nodes right away. Each time we call this method, it returns the next node value.

To do that, we use the yield keyword which returns an object and stops right there so the function will continue from there next time the method is called.

We cannot use recursion in this case so we use a stack.

Here is the code:

class Node:
    ...
    def tree_data(self):
        """
        Generator to get the tree nodes data
        """
        # we use a stack to traverse the tree in a non-recursive way
        stack = []
        node = self
        while stack or node: 
            if node:
                stack.append(node)
                node = node.left
            else: # we are returning so we pop the node and we yield it
                node = stack.pop()
                yield node.data
                node = node.right

For example, we want to access the tree nodes using a for loop:

for data in root.tree_data():
    print data

Let’s look at what happens in the code with the same example we have been using:

  • 1- The root node tree_data() method is called.
  • 2- Node 8 is added to the stack. We go to the left child of 8.
  • 3- Node 3 is added to the stack. We go to the left child of 3.
  • 4- Node 1 is added to the stack. Node is set to None because there is no left child.
  • 5- We pop a node which is Node 1. We yield it (returns 1 and stops here until tree_data() is called again.
  • 6- tree_data() is called again because we are using it in a for loop.
  • 7- Node is set to None because Node 1 doesn’t have a right child.
  • 8- We pop a node which is Node 3. We yield it (returns 3 and stops here until tree_data() is called again.

Here you go, I hope you enjoyed this tutorial. Don’t hesitate to add comments if you have any feedback.

C++ Twilio REST and TwiML Helper Library

December 16, 2010

The C++ Twilio help library simplifies the process of making requests to the Twilio REST API, generating TwiML and validating HTTP request signatures using C++.

Checkout the library: git clone https://laurentluce@github.com/laurentluce/twilio-cplusplus.git

Source files:

  • Rest.cpp: Twilio REST helper
  • TwiML.cpp: TwiML generation helper
  • Utils.cpp: Utils to validate a HTTP request signature: X-Twilio-Signature
  • Examples.cpp: Examples of usage
  • UnitTests.h: Unit tests
  • Makefile: makefile to build the library (requires libcurl and openssl), examples code and unit tests suite. Type ‘make’ to build the library. ‘make examples’ to build the examples, ‘make unittests’ to build the unit tests suite and run it.

Don’t forget to include Utils.h, Rest.h and TwiML.h at the top of your source code and to use the twilio namespace: “using namespace twilio;”.

The following code examples are based on a restaurant dish recommendation service using SMS for communication. We will go through the following examples:

1- Receiving and replying to a SMS asking for a restaurant dish recommendation.
2- Sending a daily recommendation to a list of subscribers using SMS.
3- Retrieving the list of SMS we sent.

We are going to use the C++ std namespace in the rest of the code: “using namespace std;”.

We need to define the following constants:

// Twilio REST API version
const string API_VERSION = "2010-04-01";
// Twilio Account Sid
const string ACCOUNT_SID = "XXXX";
// Twilio Auth Token
const string ACCOUNT_TOKEN = "XXXX";
// Twilio SMS URL
const string SMS_URL = "http://www.example.com/sms";

Receiving and replying to a SMS asking for a restaurant dish recommendation.

When someone asks for a dish recommendation, he sends a SMS with a text such as “Burger in San Francisco”. Twilio issues a HTTP POST request to your server with the text in the POST parameter “Body”. The URL called is SMS_URL.

First, we need to validate the HTTP POST request to make sure it is coming from a Twilio server. We use the Utils class to help us with that.

Utils utils (ACCOUNT_SID, ACCOUNT_TOKEN);
// vars should contain the POST parameters received. It is a vector of Var structures: key/value.
vector<Var> vars;
vars.push_back(Var("AccountSid", "xxxx"));
vars.push_back(Var("Body", "xxxx"));
// ... add all POST parameters received
// signature is the hash we received in the X-Twilio-Signature header
bool valid = utils.validateRequest(signature, SMS_URL, vars);
if(!valid)
  // ... handle invalid request here

Then we need to reply with our dish recommendation. We use the classes TwiMLResponse and Sms to help us generate the XML.

TwiMLResponse response;
// Set SMS text based on what the user asked, which can be found in the "Body" POST parameter.
Sms sms ("Gigantic Burger at Twilio at 501 Folsom St San Francisco");
response.append(sms);
// ... reply with response.toXML()

response.toXML() returns the following:

<Response>
  <Sms>
    <![CDATA[Gigantic Burger at Twilio at 501 Folsom St San Francisco]]>
  </Sms>
</Response>

Sending a daily recommendation to a list of subscribers using SMS.

We need to issue POST requests using the following URL: /2010-04-01/Accounts/{AccountSid}/SMS/Messages. In the following code, “subscribers” is a vector containing the phone numbers that we need to send to. We use the class Rest to help us send the SMS messages.

Rest rest(ACCOUNT_SID, ACCOUNT_TOKEN);
// Fill up the POST parameters vector
vector<Var> vars;
vars.push_back(Var("From", "xxx-xxx-xxxx"));
vars.push_back(Var("Body", "Deluxe Ramen at Twilio at 501 Folsom St San Francisco"));
vars.push_back(Var("To", ""));
string res;
// Go through the list of subscribers and issue a POST request for each one. 
for(unsigned int i = 0; i < subscribers.size(); i++)
{
  // vars[2] refers to the "To" parameter
  vars[2].value = subscribers[i];
  res = rest.request("/" + API_VERSION + "/Accounts/" + ACCOUNT_SID + "/SMS/Messages", "POST", vars);
  // "res" contains the XML response returned by the Twilio server
}

Retrieving the list of SMS messages we sent and their status

We need to issue a GET request using the following URL: /2010-04-01/Accounts/{AccountSid}/SMS/Messages. We use the class Rest to help us with the GET request.

Rest rest(ACCOUNT_SID, ACCOUNT_TOKEN);
// Fill up the GET parameters vector
vector<Var> vars;
vars.push_back(Var("From", "xxx-xxx-xxxx"));
// we can also set "To" and "DateSent" to filter more
string res;
res = rest.request("/" + API_VERSION + "/Accounts/" + ACCOUNT_SID + "/SMS/Messages", "GET", vars);

“res” should contain the list of SMS sent.

<TwilioResponse>
  <SMSMessages page="0" numpages="6"...>
    <SMSMessage>
      <Sid>SM800f449d0399ed014aae2bcc0cc2f2ec</Sid>
      <DateCreated>Mon, 10 Dec 2010 03:45:01 +0000</DateCreated>
      ...
    </SMSMessage>
    ...
  </SMSMessages>
</TwilioResponse>

Note that pagination might need to be handled if the number of SMS messages is too large for one HTTP response. See http://www.twilio.com/docs/api/2010-04-01/rest/response#response-formats-list-paging-information for more details.

There is a lot more you can do using the Twilio C++ library so go ahead and have fun with it.

Amazon S3 upload and download using Python/Django

October 7, 2010

This article describes how you can upload files to Amazon S3 using Python/Django and how you can download files from S3 to your local machine using Python.

We assume that we have a file in /var/www/data/ which we received from the user (POST from a form for example).

You need to create a bucket on Amazon S3 to contain your files. This can be done using the Amazon console.

Now, we are going to use the python library boto to facilitate our work.

We define the following variables in settings.py of our Django project:

BUCKET_NAME = 'bucket_name'
AWS_ACCESS_KEY_ID = ...
AWS_SECRET_ACCESS_KEY = ...

Upload to S3

Here is the code we use to upload the picture files:

def push_picture_to_s3(id):
  try:
    import boto
    from boto.s3.key import Key
    # set boto lib debug to critical
    logging.getLogger('boto').setLevel(logging.CRITICAL)
    bucket_name = settings.BUCKET_NAME
    # connect to the bucket
    conn = boto.connect_s3(settings.AWS_ACCESS_KEY_ID,
                    settings.AWS_SECRET_ACCESS_KEY)
    bucket = conn.get_bucket(bucket_name)
    # go through each version of the file
    key = '%s.png' % id
    fn = '/var/www/data/%s.png' % id
    # create a key to keep track of our file in the storage 
    k = Key(bucket)
    k.key = key
    k.set_contents_from_filename(fn)
    # we need to make it public so it can be accessed publicly
    # using a URL like http://s3.amazonaws.com/bucket_name/key
    k.make_public()
    # remove the file from the web server
    os.remove(fn)
  except:
    ...

Download from S3

As you saw, you can access the file using the URL: http://s3.amazonaws.com/bucket_name/key but you can also use the boto library to download the files. I do that to create a daily backup of the bucket’s files on my local machine.

Here is the script to do that:

import boto
import sys, os
from boto.s3.key import Key

LOCAL_PATH = '/backup/s3/'
AWS_ACCESS_KEY_ID = '...'
AWS_SECRET_ACCESS_KEY = '...'

bucket_name = 'bucket_name'
# connect to the bucket
conn = boto.connect_s3(AWS_ACCESS_KEY_ID,
                AWS_SECRET_ACCESS_KEY)
bucket = conn.get_bucket(bucket_name)
# go through the list of files
bucket_list = bucket.list()
for l in bucket_list:
  keyString = str(l.key)
  # check if file exists locally, if not: download it
  if not os.path.exists(LOCAL_PATH+keyString):
    l.get_contents_to_filename(LOCAL_PATH+keyString)

Upload to Django with progress bar using Ajax and jQuery

September 30, 2010

In this article, I am going to describe how I implemented upload to Django + progress bar with Ajax and jQuery. I needed this feature so users could post their dish pictures on Gourmious and follow the upload’s progress.

Client Side

We need a form so the user can select a file to upload.

<form id="form_upload" action="/upload" method="POST">
  <input type="file" name="picture" id="picture" />
  <input type="hidden" id="X-Progress-ID" name="X-Progress-ID" value=""/>
  <input type="hidden" id="id" name="id" value=""/>
  <input id="form_submit_button" class="tp-button" type="submit" value="Submit" />
  </form>

We added 2 hidden inputs, first one is ‘X-Progress-ID’ which is the upload ID so we can support simultaneous uploads on the server side. We will see later how that value is handled by the server.

We also have the hidden input ‘id’ representing the dish ID in our case.

We want to use Ajax to send the POST request so it can be integrated nicely in a modern web interface along with a progress bar. To support that, we are going to use the jQuery Form plugin.

The function ajaxSubmit() is going to take care of everything for us.

We generate a random string for this upload ID and set the input value to that string.
We need to specify a URL to be called for the upload and 2 callback functions: one to be called before the request and 1 after.

$('#X-Progress-ID').val('random string');
var options = {
  dataType: 'xml',
  url: '/upload?X-Progress-ID='+$('#X-Progress-ID').val(),
  beforeSubmit: showRequest,
  success: showResponse
}
$('#form_upload').ajaxSubmit(options);

The showRequest callback can be as simple as:

function showRequest(formData, jqForm, options) {
    // do something with formData
    return True;
}

In the showResponse function, you need to process the response and act on it. In my case, I process some xml returned by the server with a status value.

function showResponse(response) {
    // do something with response
}

When the user presses submit, we want to display a progress bar so we use the following JS code to add a progress bar to the form. The progressBar() method is part of the jQuery progress bar plugin.

$('#form_upload').find('#form_submit_input').append('&lt;span id="uploadprogressbar"&gt;&lt;/span&lt;');
$('#form_upload').find('#uploadprogressbar').progressBar();

Now, we need to add a function running every few seconds to get the upload progress from the server and update the progress bar accordingly.

To do that, we use setInterval() to issue a GET request to the server to get the progress value using the JSON format. We pass the upload ID to the server. When the value null is returned, we know that the upload is finished.

function startProgressBarUpdate(upload_id) {
  $("#uploadprogressbar").fadeIn();
  if(g_progress_intv != 0)
    clearInterval(g_progress_intv);
  g_progress_intv = setInterval(function() {
    $.getJSON("/get_upload_progress?X-Progress-ID="
+ upload_id, function(data) {
      if (data == null) {
        $("#uploadprogressbar").progressBar(100);
        clearInterval(g_progress_intv);
        g_progress_intv = 0;
        return;
      }
      var percentage = Math.floor(100 * parseInt(data.uploaded) / parseInt(data.length));
      $("#uploadprogressbar").progressBar(percentage);
    });
  }, 5000);
}

Server side

First, we need a function in views.py to handle the upload. This function handles the request: “/upload?X-Progress-ID=xxxx”. We are reading the file chunk by chunk to not use too much RAM. In my case, I return some xml containing the status value: upload OK or not.

def upload(request):
  id = request.POST['id']
  path = '/var/www/pictures/%s' % id
  f = request.FILES['picture']
  destination = open(path, 'wb+')
  for chunk in f.chunks():
    destination.write(chunk)
  destination.close()
  # return status to client
  ...

How do we keep track of the upload progress? We need to use a different file upload handler. We are going to use UploadProgressCachedHandler. We just need the class from this snippet, not the view function which we are going to write ourself. You can add the class to a file named uploadprogresscachedhandler in your project.

This handler saves the upload progress to the cache so it can be retrieved easily when we receive the requests from the client.

To enable this handler, we need to add the following to settings.py:

from django.conf import global_settings
FILE_UPLOAD_HANDLERS = ('uploadprogresscachedhandler.UploadProgressCachedHandler', ) \
+ global_settings.FILE_UPLOAD_HANDLERS

We also need to enable the cache system. We are going to use memcached. This goes inside settings.py too.

CACHE_BACKEND = 'memcached://127.0.0.1:11211/'

You need to make sure memcached and the python bindings are installed on your server.

We need to add a function in views.py to return the upload progress asked by the client every few seconds during the upload. This function handles the request “/get_upload_progress?X-Progress-ID=xxxx”. The progress value is stored using the key “remoteaddress_uploadid”.

from django.utils import simplejson
from django.core.cache import cache
def get_upload_progress(request):
  cache_key = "%s_%s" % (request.META['REMOTE_ADDR'], request.GET['X-Progress-ID'])
  data = cache.get(cache_key)
  return HttpResponse(simplejson.dumps(data))

That’s it for now. Don’t hesitate to add comments to discuss more.

If you like this article, it would be cool if you can share your favorite restaurant dishes on Gourmious.

Facebook oauth and Graph API with Django

August 23, 2010

In this post, I am going to describe how I integrated Facebook into Gourmious, so users could post their favorite dishes on Gourmious and on Facebook at the same time.

I wanted to keep the Gourmious login so the users could decide to login using their Gourmious credentials or using the Facebook login feature. I also wanted all users to have a Gourmious account so I didn’t allow users to login using their Facebook credentials if they didn’t have a Gourmious account. I decided to support the following 3 scenarios :

– user has a Django account and he logs in with Facebook. I associate his Facebook account to his Django account. This needs to be done only once.
– user does not have a Django account and tries to login using Facebook. I ask him first to create a Django account and I associate both accounts.
– user logs in using his Django credentials.

Facebook oauth is easier than the old Facebook connect. I was so happy to migrate to this new scheme.

I assume that you already have a server running your Django application and a Facebook app.

We are going to use the Django app django_facebook_oauth to make our life easier. Make sure you have python simplejson package installed.

Facebook Platform uses the OAuth 2.0 protocol for authentication and authorization. Read this first before continuing.
Facebook authentication

Clone the Django Facebook oauth app source code:

git clone http://github.com/dickeytk/django_facebook_oauth.git

Copy the folder django_facebook_oauth to your Django project apps folder and rename it to facebook.

We will assume that your apps folder is called apps.

Django settings.py

We need to make the following changes:

  • Add ‘apps.facebook.backend.FacebookBackend’ to AUTHENTICATION_BACKENDS.
  • Add ‘apps.facebook’ to INSTALLED_APPS
  • Add your Facebook API app ID: API_ID = xxxx.
  • Add your Facebook secret key: APP_SECRET = xxxx.

Django urls.py

Add the following to urlpatterns:

(r'', include('apps.facebook.urls')),

Database changes

You need to add the following table so you can associate Django user IDs with Facebook user IDs and store the Facebook session token. You can use the syncdb feature or create the table manually.

CREATE TABLE `facebook_facebookuser` (
  `id` int(11) NOT NULL auto_increment,
  `user_id` int(11) NOT NULL,
  `facebook_id` varchar(150) NOT NULL,
  `access_token` varchar(150) default NULL,
  PRIMARY KEY  (`id`),
  UNIQUE KEY `user_id` (`user_id`),
  UNIQUE KEY `facebook_id` (`facebook_id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8

Facebook authentication flow

1- user clicks on the Facebook login button
2- Django Facebook app authenticate view is called
3- facebook open graph authorize url is called with application ID, redirect uri = /authenticate, scope = ‘publish_stream’ to ask for permission to post to user’s wall
4- Dajgno Facebook app authenticate view is called with a parameter called code.
5- authentication using the Django Facebook app backend by passing the code back to Facebook along with the app secret.
6- Facebook returns a session token to be used for actions like posting messages to the user’s wall.
7- if the user is already in facebook_facebookuser table, login and redirect to home page. If user is not in the table, ask him to login using your app credentials so you can associate his Django app user id with his Facebook user id.

Django Facebook app views.py

I modified views.py to use my login form to associate Django user id with Facebook ID instead of using the register form included in the Django Facebook app.

When the token is returned and the user does not exist in the facebook table, I add a parameter to the request session to indicate that the user needs to login first so I can join the accounts.

if user != None:
  login(request, user)
  return HttpResponseRedirect('/')
else:
  # lines added
  request.session['ask_to_login_facebook'] = '1'
  return HttpResponseRedirect('/')
  #return HttpResponseRedirect('/register/')

I check for this session parameter in my template to popup a login form.

When the user enters his Django app credentials, I add an entry to the Facebook table before logging in the user. This operation just needs to be done once. After that, I know how to match a user Facebook id to the Django app user id so the user can directly login using the Facebook connect button.

This the code in my Django app views.py

# check credentials
user = authenticate(username=username, password=password)
if user is not None:
  if user.is_active:
      if 'fb_id' in request.session:
        fb_user = FacebookUser(user = user,
          facebook_id = request.session['fb_id'],
          access_token = request.session['fb_token'])
        fb_user.save()
        del request.session['fb_id']
        del request.session['fb_token']
      login(request, user)
      status = 0
    else:
      status = 1
  else:
    status = 1
    msg = _('Invalid password')

Django Facebook app backend.py

I modified this file to also add the token to the request session so I can use it when I add an entry to the facebook user table in views.py.

try:
  fb_user = FacebookUser.objects.get(facebook_id = str(profile["id"]))
except FacebookUser.DoesNotExist:
  request.session['fb_id'] = profile['id']
  # line added
  request.session['fb_token'] = access_token
  return None
fb_user.access_token = access_token
fb_user.save()

Django app template

This is what I added to my Django app login form to support the Facebook login button.

<form id="form_authenticate" action="/authenticate" method="POST">
  <p>blablabla</a></p>
  <input id="form_authenticate_button" type="image" src="link_to_facebook_button"                    onClick="javascript:$('#form_authenticate').submit();">
</form>

I also added a ‘Post to Facebook’ check box to my ‘Post dish review’ form so the user can decide what gets posted to his Facebook wall.

Post a message on the user’s wall

I used to post messages using the Javascript SDK but I now do it on the server side using the Facebook python SDK.

Add the file facebook.py (http://github.com/facebook/python-sdk/blob/master/src/facebook.py) to the Facebook app folder and rename it facebook_sdk.py .

We call put_wall_post() to post a message to the user’s wall.

Here is the code I am using in my Django app views.py to format the parameters before calling put_wall_post() .

def post_to_facebook(request):
  try:
    fb_user = FacebookUser.objects.get(user = request.user)
    # GraphAPI is the main class from facebook_sdp.py
    graph = GraphAPI(fb_user.access_token)
    attachment = {}
    message = 'test message'
    caption = 'test caption'
    attachment['caption'] = caption
    attachment['name'] = 'test name'
    attachment['link'] = 'link_to_picture'
    attachment['description'] = 'test description'
    graph.put_wall_post(message, attachment)
    return 0
  except:
    logging.debug('Facebook post failed')

That’s it for now.

If you enjoyed this article, check out my web app Gourmious to discover and share your favorite restaurant dishes. It would be cool if you could add some of your favorite restaurant dishes.

Upload files from Python to Django

January 24, 2010

In this post, we are going to upload files using Python to a Django server in an efficient way (streaming style on both sides). We will upload all the files found in 1 folder to our Django server. We will also use authentication to post our data to the server.

Client side

A very nice module to use is the poster module. It facilitates making POST requests using the standard multipart/form-data encoding, as well as enabling streaming POST requests.

We have a cookie in hand which we created using:

cj = cookielib.CookieJar()

We need to import few functions from the poster module:

from poster.encode import multipart_encode
from poster.streaminghttp import StreamingHTTPHandler, StreamingHTTPRedirectHandler, StreamingHTTPSHandler

We build and install our opener using the streaming handler functions of the poster module:

handlers = [StreamingHTTPHandler, StreamingHTTPRedirectHandler, StreamingHTTPSHandler]
opener = urllib2.build_opener(urllib2.HTTPCookieProcessor(cj), *handlers)
urllib2.install_opener(opener)

You could use register_openers() but it doesn’t support authentication so we call the internal functions ourself.

We need to read the list of files in the folder ‘/data’ and post them to the server:

params = {}
dir = u'/data/'
for f in os.listdir(dir):
  params[f] = open(dir+f)
data, headers = multipart_encode(params)
url = 'https://test/upload.py'
req = urllib2.Request(url, data, headers)
result = urllib2.urlopen(req)

Server side

We also don’t want to overwhelm the memory on the server side so we are going to read the data in chunks.

The files received are in request.FILES as a dictionary of UploadedFile objects.

If the file size is above 2.5MB (this can be modified in your settings.py), it will be split in multiple parts so reading doesn’t consume too much RAM.

We add the following in the view function handling upload.py requests:

for key, file in request.FILES.items():
  path = '/data/'+ file.name
  dest = open(path.encode('utf-8'), 'wb+')
  if file.multiple_chunks:
    for c in file.chunks():
      dest.write(c)
    else:
      dest.write(file.read())
    dest.close()

Here it is, we have all our files uploaded saved in the data folder on the server side.

If you enjoyed this article, check out my web app Gourmious and discover and share your favorite restaurant dishes.

Create a Debian package for your Django application

January 2, 2010

This post is about building a Debian package to deploy a Django application on a Debian server.

The package will take care of the following:

  • Install application
  • Web server configuration (in our case: Lighttpd with fastcgi)
  • Init.d script to start/stop Django server

We will also use a debconf template to ask 1 question to the user to make our package more dynamic.

Let’s assume you have a Django application located in /usr/share/djangoapp . This is where you have settings.py, manage.py, views.py etc…

First thing, we need to create a folder debian and copy the Django app folder into it:

mkdir ./debian
mkdir -p ./debian/usr/share/
cp -r /usr/share/djangoapp ./debian/usr/share/

We also need to create a folder names DEBIAN in debian/

mkdir ./debian/DEBIAN

DEBIAN files

This folder needs to contain the following files:

  • control
  • config
  • conffiles
  • templates
  • postinst
  • postrm
  • preinst
  • prerm

control

This is the most important file in a Debian package. It gives information on the package itself along with some dependencies. In our case, it looks like this:

Package: djangoapp
Version: 0.1-1
Section: devel
Priority: optional
Architecture: all
Depends: python, python-django, python-flup, debconf, lighttpd
Maintainer: Laurent Luce <laurent@tomnica.com>
Description: short description
 long description

Depends consists of a list of packages required for our package to run properly.

config

config is a script responsible for asking questions to the user before the package gets installed. In our case, we will ask one simple question: what is your full name?

#!/bin/sh -e

# Source debconf library.
. /usr/share/debconf/confmodule

# server type?
db_input critical djangoapp/username || true
db_go

As you can see, you need to include debconf confmodule to add configuration support. Our question is critical.

Wait a minute, where is the question definition? It is defined in the templates file

templates

This is where we define our question: string type.

Template: djangoapp/username
Type: string
Description: Username:
This package requires your full name.

conffiles
This file contains the configuration files generally located under /etc . We add our Django start script and the lighttpd configuration file.

/etc/init.d/django
/etc/lighttpd/lighttpd.conf

preinst
This script is run before the package gets installed.

#!/bin/bash
set -e

# stop django server
if [ -f /etc/init.d/django ]
then
  invoke-rc.d django stop
fi

postinst
This script is run after the package is unpacked.

#!/bin/sh
set -e

# Source debconf library.
. /usr/share/debconf/confmodule

db_get djangoapp/username
username="$RET"
# do what you want with this username

# register django
update-rc.d django defaults 90 >/dev/null
# start django
invoke-rc.d django start

db_stop

postrm
This script is run after the package is removed.

#!/bin/bash
set -e

if [ "$1" = "purge" -a -e /usr/share/debconf/confmodule ]; then
    # Source debconf library.
    . /usr/share/debconf/confmodule
    # Remove my changes to the db.
    db_purge
fi

if [ "$1" = "remove" ]; then

# Source debconf library.
. /usr/share/debconf/confmodule

# remove Django start script
update-rc.d -f django remove

# Remove my changes to the db.
db_purge
fi

prerm
This script is run before the package is removed.

#!/bin/bash
set -e

# stop django server
invoke-rc.d django stop

Web server configuration

Here is what needs to be modified in the web server configuration (in our case, lighttpd.conf):

mod_fastcgi needs to be added to the server modules.

The Django server will be running on port 3033 so we need to specify the connection here:

fastcgi.server = (
  "/djangoapp.fcgi" => (
    "main" => (
      # Use host / port instead of socket for TCP fastcgi
      "host" => "127.0.0.1",
      "port" => 3033,
      "check-local" => "disable",
  ))
)

Django init.d script

Now is time to add our Django start/stop script:

#! /bin/sh
### BEGIN INIT INFO
# Provides:          FastCGI servers for Django
# Required-Start:    networking
# Required-Stop:     networking
# Default-Start:     2 3 4 5
# Default-Stop:      0 1 6
# Short-Description: Django FastCGI
#

DJANGO_SITE="djangoapp"
SITE_PATH=/var/www
RUNFILES_PATH=$SITES_PATH/tmp
HOST=127.0.0.1
PORT_START=3033
RUN_AS=www-data

set -e

PATH=/usr/local/sbin:/usr/local/bin:/sbin:/bin:/usr/sbin:/usr/bin
DESC="Django FastCGI"
NAME=$0
SCRIPTNAME=/etc/init.d/$NAME

#
#       Function that starts the daemon/service.
#
d_start()
{
    # Starting all Django FastCGI processes
    echo -n ", $DJANGO_SITE"
    if [ -f $RUNFILES_PATH/$DJANGO_SITE.pid ]; then
        echo -n " already running"
    else
       start-stop-daemon --start --quiet \
                       --pidfile $RUNFILES_PATH/$DJANGO_SITE.pid \
                       --chuid $RUN_AS --exec /usr/bin/env -- python \
                       $SITE_PATH/$DJANGO_SITE/manage.py runfcgi \
                       host=$HOST port=$PORT \
                       pidfile=$RUNFILES_PATH/$DJANGO_SITE.pid
    fi
}

#
#       Function that stops the daemon/service.
#
d_stop() {
    # Killing all Django FastCGI processes running
    echo -n ", $DJANGO_SITE"
    start-stop-daemon --stop --quiet --pidfile $RUNFILES_PATH/$SITE.pid \
                          || echo -n " not running"
    if [ -f $RUNFILES_PATH/$DJANGO_SITE.pid ]; then
        rm $RUNFILES_PATH/$DJANGO_SITE.pid
    fi
}

ACTION="$1"
case "$ACTION" in
    start)
        echo -n "Starting $DESC: $NAME"
        d_start
        echo "."
        ;;

    stop)
        echo -n "Stopping $DESC: $NAME"
        d_stop
        echo "."
        ;;

    restart|force-reload)
        echo -n "Restarting $DESC: $NAME"
        d_stop
        sleep 1
        d_start
        echo "."
        ;;

    *)
        echo "Usage: $NAME {start|stop|restart|force-reload}" >&2
        exit 3
        ;;
esac

exit 0

This script needs to be placed in ./debian/etc/init.d/

You will also need to create a link from /var/www/djangoapp to /usr/share/djangoapp

changelog, changelog.Debian and copyright

Those are required for Debian packages:

changelog

djangoapp (0.1-1) unstable; urgency=low

  * Initial release.
    + Initial package

 -- Laurent Luce <laurent@tomnica.com>  Fri, 01 Jan 2010 00:00:00 +0000

In our case, changelog.Debian is identical to changelog.

copyright

DjangoApp

Copyright: bla bla

2010-01-01

The home page of xxx is at: 
http://www.xxx.com

Copyright xxx 2010

We need to place those files properly:

mkdir -p ./debian/usr/share/doc/djangoapp
cp changelog changelog.Debian copyright ./debian/usr/share/doc/djangoapp/
gzip --best ./debian/usr/share/doc/djangoapp/changelog
gzip --best ./debian/usr/share/doc/djangoapp/changelog.Debian

Build package

We need to fix the permission of our package files:

find ./debian -type d | xargs chmod 755

We build the package and verify it:

fakeroot dpkg-deb --build debian
mv debian.deb DjangoApp_0.1-1_all.deb
lintian DjangoApp_0.1-1_all.deb

Our package is now ready to be deployed.

If you enjoyed this article, check out my web app Gourmious and discover and share your favorite restaurant dishes.

 
Powered by Wordpress and MySQL. Theme by Shlomi Noach, openark.org