Algorithm Magic: Binary Search Tree to Doubly Linked List

Hi friends,

This post gives solution to a famous data structures problem: Converting a Binary Search Tree to Doubly Linked List. I am assuming you are well aware of what there data structures are and their behavior.

Lets jump into algorithm to convert this.

• Since each subtree in a binary tree is a binary tree itself, we can use recursion for achieving this. We start by root node and reach leaf nodes. 
• While traversing, we see if node does not have any left or right child, the node itself is returned. If it has non empty child nodes, then we create doubly linked list with 3 nodes( current node, left child node and parent node). 
• Now here is the magic, the left child is not exactly its direct left child. Since our aim is to convert it into a sorted doubly linked list, we need to get the maximum value node which is less than current node value in left subtree as as left child for current node. Similarly, the node with least value in right subtree as right child of current node. 
• That's it, apply this logic and solve it.

The class used to represent the node in binary tree and doubly linked list*:

*left will indicate previous node in doubly linked list and right will indicate the next node in doubly linked list.

function to insert node in BST:

function to convert BST to DLL:

function to show doubly linked list:

Here is the implementation of this algorithm: Download here.

Hope this helps you learn how to convert BST into DLL.
Cheers!

Fix for Bluetooth Indicator bug in Ubuntu 13.10

Hi Guys,

I was facing the issue with Bluetooth in Ubuntu 13.10. I was able to connect my bluetooth headset but wasn't able to see it in my sound settings. Thus was unable to use it. To resolve it, I found a fix for this and here it follows:

1. Install the pre-requisites :

sudo apt-get install bzr build-essential

2. And install the dependencies:

sudo apt-get build-dep indicator-bluetooth

3. Branch the fork from Launchpad:

bzr branch lp:~robert-ancell/indicator-bluetooth/dont-hide-on-rfkill

4. Jump to the directory:

cd dont-hide-on-rfkill

5. Now run following command to build debian package:
dpkg-buildpackage

This gives an error that "Unmet build dependencies: libdbusmenu-gtk3-dev libgnome-bluetooth-dev libgtk-3-dev libido3-0.1-dev libindicator3-dev valac-0.18"

Lets go ahead these dependencies:

After installing these, lets try to run this again:

 dpkg-buildpackage 

as a result the debian package is created :

Lets go out to home directory and install the debian package:

go to home directory:

cd  

and then:

sudo dpkg -i indicator-bluetooth_0.0.6daily13.02.19-0ubuntu1_i386.deb 

and.. it works !! 

and then restart your system. Now the bluetooth icon remains even you turn it off and just gets grey when turned off.

Hope it helps !

Cheers!

Machines+Symbiotic Artificial Intelligence=Humans

I feel extremely motivated by my dream to do research and create systems which enable machines and devices to act as full fledged human companion. So that devices observe humans, their activities, conversations and understand them to create knowledge. By augmenting such intelligent systems with information about the real world entities, their properties and such minutest details will empower them to assist humans in their day to day activities. I truly believe that there is a deep symbiotic relationship between Humans and Artificial Intelligent Systems. Just imagine time when we will be having small gadgets on our wrist, over our spectacles that would assist us in every action which needs precision and quality; Imagine system that could tell you what should be your next step based on knowledge acquired by such system by observation and knowledge from world through various sources including WWW. This will not only assure effectiveness of the task being done but also will gradually help symbiotic artificial intelligence systems to evolve rapidly. I want to build algorithms, models and systems that will enable us to leverage intelligent systems at every domain. This will definitely revolutionize the way things are accomplished by humans.

Making Amkette TruBeats Bluetooth Neckphone work with Fedora 17(Beefy Miracle)

Hi,

I would like to share how I managed to get my Amkette TruBeats BT neckphone work with Fedora 17. Though the device gets paired with OS but the pulseaudio library crashes everytime I paired the device. This resulted in no device being showed up under System sound settings. Thus you can't listen to the music on your BT neckphone :(

There is a fix for this issue and here it goes:
1. Create audio.conf file under /etc directory.
2. Save the file with this content in it:
[General]
Disable=Media
Enable=Source,Sink,Gateway,Control,Socket
3. And finally reboot and its done :)

Now once you pair your device you will observe that pulseaudio is no more crashing !
Also you will be able to see your device under System sound settings:

I hope you find this post useful :)

Cheers!

Guess whoami : RTTI

Hi guys,

This time we will explore the technique used to determine the type of objects at runtime using Run Time Type Identification(RTTI) in C++.

Basically there are two common ways to achieve this:
1. Use a virtual function in base class and override that method in derived class:

output:

And when you use base class pointer or reference to hold object you may use bptr->typeOf() to detemine the type of object at run time.

2. Another approach which is built into language library is to use typeid() method. This method returns const object of typeinfo type.
For example,

We can also use Explicit Typecasting in C++ using :

dynamic_cast:

 It is used to ensure that the object returned after cast is complete object of requested type. If its not so it returns bad_cast exception in case of references and returns null pointer in case of pointers.

Consider non-polymorphic base class and its derived class:

This will not even clear the compilation phase. It will give this error:

Lets convert base class to polymorphic by adding virtual keyword for hello method in base class and check again. This time it clears compilation and the type is checked at run time. This is purely based on RTTI support by compiler.

static_cast: 

In this cast operator it is not checked that object returned after casting is actually a type of requested object. It is not type safe. Thus it is upto developers to take care when dereferencing. This works for:

• Implicit conversions
• Narrowing conversions
• Conversions from void *
• base class pointer to derived class pointer 
• derived class pointer to base class pointer

For example:

This will yield:

const_cast:

This cast is useful to convert const to non-const objects. This is used as another alternative to change const objects in a class without using mutable keyword.

For example,

output:

reinterpret_cast: 

This cast is used to convert any pointer type to any other pointer type, even for unrelated classes. It can also be used to convert int to pointer and other way round.

For example,

This will yield:

I hope this helps you understand basic typecasting mechanism present in C++. Stay tuned for more fun !

WikipediaHI: Offline Wikipedia in Hindi !!

Last week I spent some time working on WikipediaHI activity for Sugar Desktop Environment. I must say it is one of the awesome activities I have come across. The best part is that it can serve you with data in offline mode. That is even if don't have internet connection which is otherwise required to access Wikipedia online, then also your WikipediaHI activity will serve your purpose.

There are lot many developers and contributors who are working in collaborative form on such awesome stuff who continuously inspire you to take up new things and create something that can be used by others in the world. Sugar developers and contributors are epitome of such group.

I came across few of such developers, Anish Mangal and Gonzalo Odiard, two of them whose contributions are significant for Sugar. I took up the task of creating WikipediaHI using Wikipedia dump for Hindi available for free. I followed the steps specified on this page[ hosted by Gonzalo] for creating Wikipedia activity in your own language.

I will quickly explain the steps I took to create WikipediaHI:

1) Downloaded the Wikipedia dump file for Hindi:
http://dumps.wikimedia.org/hiwiki/20121225/hiwiki-20121225-pages-articles.xml.bz2
NOTE: [ Make sure you pick the valid latest file from here : http://dumps.wikimedia.org/hiwiki/   this location will show you listing as per dates. Pick the latest dump and proceed further.]

and downloaded WikipediaBase from this link

2) Created "hi" directory for HINDI under WikipediaBase directory and moved the downloaded dump to this folder.

3) Extracted contents of this file using:
bzip2 -d hiwiki-20121225-pages-articles.xml.bz2

4) Processed the dump using page parser:
../tools2/pages_parser.py

The result of this operation will generate these files:
hiwiki-20121225-pages-articles.xml.links
hiwiki-20121225-pages-articles.xml.page_templates
hiwiki-20121225-pages-articles.redirects
hiwiki-20121225-pages-articles.templates

5) Then you can include selective articles or all articles from this dump to your activity by using this command:
../tools2/make_selection.py
* Make sure you have favorites.txt and blacklist.txt filled with appropriate keywords.

Now if you want to include all articles use this command:
../tools2/make_selection.py --all

6) Then proceed to create the index for these articles:
../tools2/create_index.py

7) In order to test the index created in previous step you can use this command:
../tools2/test_index.py

8) Next step is to expand the templates of articles :
cd ..
./tools2/expandtemplates.py hi

9) Go back to hi directory and re-create the index :
cd hi
mv hiwiki-20121225-pages-articles.xml.processed_expanded hiwiki-20121225-pages-articles.xml.processed
../tools2/create_index.py --delete_all

10) Download the images for the articles you selected:
cd hi
../tools2/download_images.py

if you want to download the images for pages you selected in previous step:
../tools2/download_images.py --all

11) Create files specific to language:
(a)activity/activity.info.lang : activity info file for you language activity
(b)activity/activity-wikipedia-lang.svg : activity icon for your language
(c)activity_lang.py : activity file for your language
(d)static/about_lang.html : about page for wikipedia in your language.
(e)static/index_lang.html : index page for wikipedia in your language. This is the page displayed when activity is launched. So its important for you to know the articles included in the search.db ( generated when index is created) for you to create the index page.


12) Create the XO file for wikipedia in your language:
./setup_new_wiki.py hi/hiwiki-20121225-pages-articles.xml

I went through the search.db file to identify the articles present in it and create the index page accordingly.
This gave me an idea to write some script that can generate index page(part or whole) to be used as home page for activity using search.db[ Stay tuned for next blog on this idea]

Here you go.. you can see WikipediaHI

On launching this, you can see the index page listing the articles you can view offline using WikipediaHI

If you want to play with WikipediaHI, you can download it : WikipediaHI-35.xo

I must thank Gonzalo for his amazing help and guidance in getting this done. I have to mention here that Wikipedia
changed its XML format in their dumps which resulted in error when I was creating the index. I took Gonzalo's help to get it resolved.
Thanks to Anish, who motivated me to pick this up and guided me to complete it.

Thanks guys !! :D

gtk.Notebook widget within Sugar Activity !

This post describes how to use gtk.Notebook widget within a Sugar Activity.
In this blog you can find how to use gtk.Notebook widget to create PyGTK application native to GNOME. Now we will consider how sugar shell understands this Notebook widget and renders it for Sugar Desktop Environment.


Consider we have sugar activity DevelopWeb with following directory structure:

 

Here we have created weblib.py to include class WebToolBox that renders a toolbox on left hand side pane and tabbed container, i.e. Notebook on right side pane. Note that we are using HBox to hold this WebToolbox and Notebook widgets. Since there are only two widgets added to HBox we are using terms left side pane and right side pane.

weblib.py looks like this:

Here you can observe that we have added all the widgets in the constructor of WebToolbox class. We have used HBox as parent container. Then we have used a VBox as elementBox or  toolbox for this activity to hold the web elements. Then we set few properties for scrollable window inside elementBox. We add the buttons in this elementbox with appropriate properties. Then we add the Notebook widget with gtk.POS_TOP ( i.e. tabs will be visible on top).

Now we add the pages to this notebook instance using a custom method "addPage"(Refer to image below). You can see in the definition that a page is a container HBox as immediate child of Notebook within a page. Each page requires a Label widget as page label:

The basic activity file looks like :

Here within constructor of DevelopWeb class you can observe that we have use instance of WebToolBox class which inturn uses Notebook widget. we have used this WebToolBox instance to be placed as viewport of the activity. You can create a setup.py file required for activity.

Now when you create symbolic link for this activity using : python setup.py dev the Sugar Desktop Environment can use this activity.
When you start Sugar session you can see DevelopWeb activity:

When you launch this activity you can see elementBox on left side and Notebook on right side with two tabs or pages in it:

This example shows how you can use Notebook, the tabbed container in your sugar activity. I hope this post helps you.

Stay tuned for more Sugar Action !