A non-recursive implementation of an in-order traversal of a binary search tree without a stack

In my spare time, I occasionally was reading a book: “Introduction to algorithms” written by Cordon et al. to refresh and extend my knowledge on this field. Reading a book on algorithms has a side affect on me, that sooner or later I end up playing around with algorithm’s code. This time I wanted to get a non-recursive traversal of a BST without using an auxiliary stack. While a recursive traversal of a BST is really trivial, a non-recursive one is not. At least not in my eyes.
First, this is a simple API which I decided to use for a BST:

template <class T> class btree;
 
template <class T> struct node
{
public:
  friend class btree<T>;
   
private:
  T *data;
  node *left;
  node *right;
};
 

template <class T> class btree
{
public:
  btree (std::function<int(const T&, const T&)> cmp);
  ~btree ();
...
  void foreach2 (std::function<void(T&)> func) const;
...
   
private:
  node<T> *root;
  std::function<int(const T&, const T&)> cmp;
...
};

So, as you can observe, there are two classes: a node and the btree itself. The constructor of a btree takes a compare function to be able to compare its elements while searching, for example. However, this post is actually dedicated to the foreach2 member function, which travels in-order through the whole BST and takes a function as a parameter to do some action with a node’s item.

Next, I try to introduce this algorithm step by step. This way to traverse a tree is not really efficient as it visits most of the nodes almost twice on one side, but on the other side it does not require any additional data structure to keep track how to return to the parent node. All in one, it’s a lot of fun:) Below you see the whole algorithm, and as you will find out, despite the fact that this code is really small, at first glance, it’s really hard to figure out, how it works and why it works at all. So, just scroll over.

template <class T>
void btree<T>::foreach2 (std::function<void(T&)> func) const
{
  node<T> *i = root;
 
  while (i != nullptr) {
    if (i->left != nullptr) {
      node<T> *r = i->left;
 
      while (r->right != nullptr && r->right != i) {
        r = r->right;
      }
 
      if (r->right == nullptr) {
        r->right = i;
        i = i->left;
        continue;
      } else {
        r->right = nullptr;
      }
    }
 
    func (*i->data);
    i = i->right;
  }
}

So, let’s build it from scratch. Therefore, we consider a few simple cases of a BST. Suppose all node in our BST have no left nodes, so it has a form similar to this one:

//    A
//   / \
//      B
//     / \
//        C
//       / \

To traverse this BST and thus cover this case, the lines of code we come up with should be very simple:

template <class T>
void btree<T>::foreach2 (std::function<void(T&)> func) const
{
  node<T> *i = root;
 
  while (i != nullptr) {
    ...
    func (*i->data);
    i = i->right;
  }
}

And it’s no wonder, because it’s just the code, which is used to go through the singly linked list. Therefore let’s consider another special case, in which all nodes have no right child.

//       A
//      / \
//     B
//    / \
//   C
//  / \

To be able to traverse this, we should first go to the bottom of the left subtree. Let us therefore add this part of the code:

template <class T>
void btree<T>::foreach2 (std::function<void(T&)> func) const
{
  node<T> *i = root;
 
  while (i != nullptr) {
    if (i->left != nullptr) {
      ...
      i = i->left;
      continue;
      ...
    }
 
    func (*i->data);
    i = i->right;
  }
}

Once, we have arrived at the bottom we perform an operation on C’s data and bump we are stuck! At this point we should go backwards the tree. However, there is no way to go back and it’s too late already. Nevertheless, from the bottom position we can make an interesting observation: taking an arbitrary tree structure into account, all nodes at which we are going to stuck will have no right child set. Hence, at the beginning while moving down the left subtree, we should find a predecessor of the current node (in the sense of in-order traversal order) and temporarily adjust its right child to this node i.e. while visiting node A, we find its predecessor and it’s B, we set its right child temporarily to A and go one step down in the left subtree to B. For the node B we do absolutely the same thing.
Once we will arrive to the node A for the second time we should revert the temporary change by setting B’s right link to null pointer again, proceed with the data of node A and finally move to the right subtree. Remarkably, this is all what is required to be able to traverse a BST of any arbitrary structure.

Bellow you can find the entire example, in which a randomly build BST containing 50 items is constructed and traversed in-order afterwards, printing its items:

#include <functional>
#include <iostream>
#include <random>
#include <algorithm>

template <class T> class btree;

template <class T> struct node 
{
public:
  friend class btree<T>;
  
private:
  T *data;
  node *left;
  node *right;
};

template <class T> class btree
{
public:
  btree (std::function<int(const T&, const T&)> cmp);
  ~btree ();

  void insert (const T& data);
  void foreach (std::function<void(T&)> func) const;
  void foreach2 (std::function<void(T&)> func) const;
  int length () const;
  void remove (const T& data);
  
private:
  node<T> *root;
  std::function<int(const T&, const T&)> cmp;

  void foreach (node <T>* node, std::function<void(T&)> func) const;
  int length (node<T> *node, int len) const;
};

template <class T>
btree<T>::btree (std::function<int(const T&, const T&)> cmp)
{
  root = nullptr;
  this->cmp = cmp;
}

template <class T>
btree<T>::~btree ()
{
}

template <class T>
int btree<T>::length () const
{
  return length (root, 0);
}

template <class T>
int btree<T>::length (node<T> *node, int len) const
{
  if (node != NULL) {
    int l1, l2;
    l1 = length (node->left, len + 1);
    l2 = length (node->right, len + 1);

    return std::max (l1, l2);
  }
  
  return len;
}

template <class T>
void btree<T>::foreach (std::function<void(T&)> func) const
{
  foreach (root, func);
}

template <class T>
void btree<T>::foreach (node<T> *node, std::function<void(T&)> func) const
{
  if (node != NULL) {
    foreach (node->left, func);
    func (*node->data);
    foreach (node->right, func);
  }
}

template <class T>
void btree<T>::remove (const T& data)
{
  node<T> *i = root;
  node<T> *p = nullptr;
  node<T> *s = nullptr;
  int val;

  while (i != nullptr && (val = cmp (data, *i->data)) != 0) {
    p = i;
    if (val > 0) {
      i = i->right;
    } else {
      i = i->left;
    }
  }

  if (i == nullptr) return;

  if (i->left == nullptr) {
    s = i->right;
  } else if (i->right == nullptr) {
    s = i->left;
  } else {
    node<T> *b = i;
    s = i->right;

    while (s->left != nullptr) {
      b = s;
      s = s->left;
    }

    if (b->left == s) {
      b->left = s->right;
    } else {
      b->right = s->right;
    }

    s->left = i->left;
    s->right = i->right;
  }

  if (p == nullptr) {
    root = s;
  } else if (p->left == i) {
    p->left = s;
  } else {
    p->right = s;
  }
  
  delete i->data;
  delete i;
}

template <class T>
void btree<T>::foreach2 (std::function<void(T&)> func) const
{
  node<T> *i = root;

  while (i != nullptr) {
    if (i->left != nullptr) {
      node<T> *r = i->left;

      while (r->right != nullptr && r->right != i) {
        r = r->right;
      }

      if (r->right == nullptr) {
        r->right = i;
        i = i->left;
        continue;
      } else {
        r->right = nullptr;
      }
    }

    func (*i->data);
    i = i->right;
  }
}

template <class T>
void btree<T>::insert (const T& data)
{
  node<T> *n = new node<T>;
  n->data = new T (data);
  n->left = nullptr;
  n->right = nullptr;

  node<T> *i = root;
  node<T> *p = nullptr;

  while (i != nullptr) {
    p = i;
    if (cmp (*i->data, *n->data) >= 0) {
      i = i->left;
    } else {
      i = i->right;
    }
  }

  if (p == nullptr) {
    root = n;
  } else if (cmp (*p->data, *n->data) >= 0) {
      p->left = n;
  } else {
      p->right = n;
  }
}

int main ()
{
  std::random_device rd;
  std::uniform_int_distribution<int> dist (0, 1000);

  std::cout << "testing..." << std::endl;
  btree<int> bt([] (const int &a, const int &b) -> int { return (a - b); });
  int num;
  for (int i = 0; i < 50; i ++) {
    num = dist (rd);
    bt.insert (num);
  }

  bt.foreach ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;

  bt.foreach2 ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;
  std::cout << "length: " << bt.length () << std::endl;
  
  std::cout << "testing delete..." << std::endl;
  btree<int> bt2([] (const int &a, const int &b) -> int { return (a - b); });
  int vals[] = { 12, 20, 8, 10, 4, 3, 2, 1 };
  for (int i = 0; i < sizeof (vals)/sizeof (vals[0]); i++) {
    bt2.insert (vals[i]);
  }
  bt2.foreach2 ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;
  bt2.remove (8);
  bt2.foreach2 ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;
  bt2.remove (12);
  bt2.foreach2 ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;
}

It can be compiled with:

all:
	g++ inorder.cpp -o inorder --std=c++11 -O3

Reference: Threaded binary tree

Advertisements

GSOC with gnome-clocks – Final Report

Well people, the summer is sadly long gone, at least for me, and my summer of coding is approaching its end as well. I must say, that I am very thankful to Google for this opportunity to work in concert with my preferred desktop environment, which is still GNOME. I am glad, that I have seized this frame to finally move myself toward the first contribution to the GNOME project. I really enjoy this time and it’s a great pleasure for me, may be due my awesome mentor Paolo Borelli, I luckily have chosen for me. Thank you. 🙂 Moreover, during this period I have improved my knowledge in different areas and gained a lot of experience.

About the project results: as were reported many times geolocation support has managed to land in last minute to the 3.10 release, which is for sure great!
Moreover, there is even a not yet documented option for our users to toggle the geolocation service:

$ echo "Turn off geolocation support"
$ gsettings set org.gnome.clocks geolocation 'false'
$ echo "Turn on again"
$ gsettings set org.gnome.clocks geolocation 'true'

There is an experimental city images support in gnome-clocks available in the wip/cityimages branch try it out.
Screenshot from 2013-09-21 18:53:33 A youtube video is also available: city images – preview. The video illustrates the functionality of the implemented image providers: flickr image provider requests the corresponding images from the gnome-clocks flickr group, and downloads them for you, so the next time you launch the application they appear instantaneously. The capabilities of the local image provider are also demonstrated: It means, that you always have a possibility to overwrite the suggested image by the flickr provider with your own, you would like to see in gnome-clocks. Therefore you just need to put the corresponding image file into the folder:

~/.local/share/gnome-clocks/city-images/

Be aware of the following name convention for the image files. They should be named like: “berlin-germany-day.jpg” At the moment you can have two images for each location; one for a day and one for a night, the latter having the suffix “…-night.jpg” in its file name.

More information about gnome-clocks enhancements are available on the project page. Take care 🙂

Aaaah, and one more thank you for my sponsored travel to the GUADEC this year, it was just amazing 🙂
sponsored-badge-simple

Maintenance of the Project’s Page

After a few reminders I have finally managed to update during the last week my Summer of code page for the so lovely Clocks project. Now, it contains a lot of more contents instead of many promising “todo” statements. Since then I try to keep it up to date by including exemplary new code snippets or by informing you about ongoing activities. So I hope that, besides me, you can also find it useful for you. 🙂

Vala support for the Libgweather

The recent version of libgweather library from git master comes with the Vala bindings support. At least the Clocks App (gnome-clocks) will heavily rely on this bindings support and therefore we are very thankful to Giovanni Campagna for his fruitful cooperation and good and friendly support.

Please note additionally, that the new version of libgweather will deprecate some function calls. To obtain a new instance of the Location object the function “gweather_location_get_world” should be used instead of “gweather_location_new_world”. “gweather_location_new_world” is deprecated and should be omitted in the newly written code. There are many more, so for more details please refer to the official documentation.

In favour of this good announcement I would like to share with you a small sample code written in Vala, in which some capabilities of the libgweather library are briefly demonstrated: This example reveals how to obtain a timezone name for almost all corresponding major cities.
libgweather
Sample app:

public class LocationInfo {
    private Gtk.Window window;
    private Gtk.Box box;
    private GWeather.LocationEntry location_entry;
    private Gtk.Label city_label;
    private Gtk.Label timezone_label;

    public LocationInfo () {
        Gtk.Builder builder = new Gtk.Builder ();

        try {
            builder.add_from_file ("window.ui");
        } catch (Error e) {}

        this.window = builder.get_object ("window") as Gtk.Window;

        this.window.title = "libgweather testing";
        this.window.border_width = 10;
        this.window.window_position = Gtk.WindowPosition.CENTER;
        this.window.destroy.connect (Gtk.main_quit);

        this.box = builder.get_object ("box") as Gtk.Box;
        this.location_entry =
          new GWeather.LocationEntry (GWeather.Location.get_world ());
        this.location_entry.set_activates_default (true);
        this.location_entry.changed.connect (this.location_defined);
        this.box.pack_start (location_entry);

        this.city_label = builder.get_object ("city") as Gtk.Label;
        this.timezone_label = builder.get_object ("time_zone") as Gtk.Label;
    }

    public void show () {
        this.window.show_all ();
    }

    private void location_defined () {
        GWeather.Location? l = null;
        GWeather.Timezone? t = null;

        if (this.location_entry.get_text () != "") {
            l = this.location_entry.get_location ();
        }

		if (l != null) {
			t = l.get_timezone ();

			this.city_label.set_text (l.get_city_name ());

			if (t != null)
				this.timezone_label.set_text (t.get_tzid ());
			else
				this.timezone_label.set_text ("Unknown");
		}
		else {
			this.city_label.set_text ("");
			this.timezone_label.set_text ("");
		}
	}

    public static void main (string[] args)	{
        Gtk.init (ref args);

        var location_info = new LocationInfo ();
        location_info.show ();
	
		Gtk.main ();
	}
}

The code can be compiled with the following Makefile:

all:
	valac --pkg gtk+-3.0 --target-glib=2.38 gweather-sample.vala \
		--pkg gweather-3.0 -X -DGWEATHER_I_KNOW_THIS_IS_UNSTABLE

The source code can be found here: libgweather-vala.tar.gz.

Impressions after the GUADEC 2013 in Brno

Right before the conference I should admit that I was very sceptical, not only because it was my first computer science related conference at all, and thus as well the first attempt to join and meet the entire GNOME community. I was not sure about the accommodation and if I will enjoy my stay there and I personally could not justify for me the chosen location. But as I came there, it quickly turned out that all my concerns were about nothing. The Taufer dormitory, where the most of us stayed during the conference was a peaceful place, not at all what I used to imaging in my head, incorporating all my previous experience, when I hear the word “dormitory”.

The city itself and the downtown is just amazing, there are just a lot of to observe. Just to go for a walk was a pleasure for me there.

I do not really know how it could happen to me but I am also a picky vegetarian, so normally I tend to lose weight heavily once I am on holiday, somewhere in italy or spain. Therefore this time I was really prepared and about one third of my luggage was filled with fast food which I took back to home. I am still trying to figure out, why the meal there was so tasty, was it so, because it was so cheap and people were so friendly or they really know how to cook, maybe both. 🙂 To be honest, I still have no idea… During my stay in Brno I as well tasted different sorts of beer and enjoyed local drinks. SAMSUNG CSC

The conference took place in a modern building and moreover was very well organized. Each conference day was accompanied by an entertainment. One of them was a guided tour around Brno and a football game.

The given talks were very exciting. Moreover these talks were also recorded, so you can use an opportunity to grab them and follow them yourself. I also missed some of them, so I plan to watch them online.

There are some selected pictures of a guided tour:
SAMSUNG CSCWe had a wise guide, by all means. 🙂 There are rumors, that he is one of the best.
SAMSUNG CSC
There are of course some pictures of the football game, I would like to share with you:
SAMSUNG CSC
If it’s still not hot for you, it should be mentioned, that is was about 30 degrees outside. So I allow me to say that it definitely was one of the hottest events in Brno. 🙂
SAMSUNG CSC
Additionally there is also a short video of that amazing football game. 🙂 And yes, it ends with a GOAAAL!!!

The way back home was a real adventure. Maybe because I wanted to stay there for a couple of days longer, and this was in the air. To summarize shortly, nine of ten things which was initially planned, to get home in safety, went wrong. On the following picture It looks like that I have missed my plane.
SAMSUNG CSC
But luckily for me, I have not missed the plane, and it was one of a few things which worked as expected, and thus at the end of the day, I landed with a smile on my face, so probably I was happy. 🙂

To sum up, without over pushing: The GUADEC is a must for everyone and in this conference that plank were raised very high, so to organize the next GUADEC will be a very tough task! Give five😀
sponsored-badge-simple

Summer of Code with gnome-clocks

It has been a while since my last post about my ongoing contribution in GNOME. I mainly work on the gnome-clocks app. Therefore, in this post I try to summarize many of new upcoming features which gnome-clocks hopefully soon bring with a new stable release.

New selection mode design pattern

Gnome-clocks belongs to a few apps (among others like baobab, gnome-weather, and gitg) which has started to experiment with the new borderless window design. Moreover the new selection mode design was additionally implemented. Feel free to try it out, and let us know about your usability opinion. Otherwise enjoy the screenshots and the attached video.Screenshot from 2013-06-11 10:00:17Screenshot from 2013-06-11 10:00:31 From the developer point of view there are several new changes as well: Gnome-clocks does not anymore depend on the libgd submodule library as the revealer, headerbar and stack widgets have been added to gtk+. So, we were able to switch to them almost straightforward. Additionally some of the classes, which were building on the GtkBuilder functionality were ported to composite templates. This is a new feature recently introduced in gtk+ and successfully integrated into the Vala language. This feature tends to make your code cleaner and in the same time increases its readability.

Automatic geolocation discovery

One of the greatest new features I currently work on is the geolocation support in clocks. The first working implementation was used as starting point for a future design development. After a fruitful discussion with Paolo Borelli and Allan Day a new mockup for geoloction support in clocks was created. So, let’s see how it will progress. You can track the status of the geocode implementation here. Any positive suggestions are welcomed. Remember, only positive:)

City images

Another eye candy for the clocks app users is the city image support. I already have started playing with its implementation. Here in the video, which is not up to date any more the small image city is shown in the standalone mode. This has been already changed, so the image is now drawn in the background, similar way like it is done in gnome-weather. For getting in we have decided first to create a basic local image provider.Screenshot from 2013-07-01 16:14:26The main goal here, we are stiving for, is to provide support for the online image stoarage. One of the candidates in mind is the flicr group.

Some nasty bugs

Headerbar: The libgd port which is mentioned earlier in this post has sadly brought a user visible regression. Have you spotted it already? If not, it’s also fine. Maybe it’s only my eyes, which are time to time very picky. The issue is a headerbar height fluctuation. This becomes visible by switching back and forth between normal and selection mode. First, I thought, that I must be the person to blame, because this issue in my belief has landed due to one of many oversights I introduce and often find myself during writing. However, I have occasionally discovered that the weather app has exactly the same issue. So the reason for this should lie somewhere else. If you have an Idea, do not hesitate and please let me know.

The price developers pay for a good look: One of the new and tiny design improvements in GNOME was the replacement of the colon in the time string by a better looking centralized character. This new character widely used in the time strings is the ratio character “\u2236”. Screenshot from 2013-07-22 13:34:31Here, in the first screenshot the new centralized character is used in the date and time string once for the LTR and RTL language, respectively. I must admit, that it indeed appears much, much better than with the normal colon for comparison shown in the strings below. The source code of this simple test case app can be found here.Screenshot from 2013-07-22 14:18:45However nobody could never even assume that this little change would be an origin of so many issues. One of them is the funny appearance of the time in clocks. I have hidden from you this image not to burn it into your head, so look at it at your own risk. Just joking. Luckily this bug is already fixed and the time string from now on looks beautiful even in the RTL languages:)Yeaaah!Screenshot from 2013-07-22 16:06:36Another issue is when the non UTF-8 locale is in use the time string is not even displayed at all, as illustrated here. This bug will be already fixed by me tomorrow:-)Similar issues do appear in gnome-desktop and in other libraries like libgweather, in which ratio character was used.

Good news: Vala support for the \uXXXX escape sequence

The Vala compiler in git master from now on supports a unicode escape character \uXXXX, which can be used in strings and regular expression patterns, where X represents a hex digit. It could be used in strings by typing an escaped ‘u’ followed by exactly four hex digits. For example:

string s = "Copyright \u00a9"; // Copyright ©

In this particular example, there seems to be no point in using the escape sequence, because the ©-character can be used directly in the string. However for the next example it comes very handy.

string time1 = "12∶56 AM";
string time2 = "12\xE2\x88\xB656\xE2\x80\x89AM";
string time3 = "12\u223656\u2009AM";

A normal human eye, at least mine, cannot spot that in time1 the ratio character and moreover the thin space were used instead of commonly applied characters. And they are sometimes not easy to enter. The escaped x sequence can be used in this case, as illustrated in time2 string. The only downside is that \x uses a variable length for the following hex digits. This way \x9 represent probably a tab, and from the time2 string the part \xB656 will be treated by a compiler as a single escape sequence. So the use of \u would be handy here or correct me if I am wrong:) There are probably better examples, but whatever!

GUADEC

If there will be no short-term changes I am heavily planning and going to join the GUADEC conference for the first time and I hope to see you all there. I am looking forward to it and it will be for sure a good time. And here is a GUDEC logo I have snapped from the latex-beamer template.guadec-logo

Hello Planet GNOME

It’s a pleasure for me to announce to you, that from now on some of my blog entries will be published on PGO.

This summer I work on improving the gnome-clocks app accomplished by a strong support of my mentor Paolo Borelli and a close collaboration with the GNOME design team, especially with Allan Day.

For those, who still does not know how it looks like, here is a screenshot of its current stable 3.8.x release in Russian locale, using a dark theme.
Screenshot from 2013-05-10 00:28:54

Therefore, I will try to keep you informed periodically about ongoing work and achievements concerning this project.

So, Hello. 🙂