November 2010

# My Implementation of Diff Algorithm

Tue
16
Nov 2010

Algorithm for comparing two sequences of some data is very useful. For example, version control systems like SVN or Git use it to highlight differences between two versions of a text file. But what if you need to code such algorithm from scratch? Today it was my task and it turned out to be not so simple, so I want to share my sample implementation in C++ which I came up with based on some readings from the Internet and my previous experiences with calculating Levenshtein distance.

What we need to compare is sometimes just lines of text files that are equal or not, but I needed something more complex, so let's say an item is defined as follows:

struct Item
{
  unsigned ID;
  const char *Text;
};

For items from opposite sides to be comparable they must have same ID values. Text may be different, but I'd prefer to match items with same Text (treated as NULL-terminated string) or at least same Text length.

Here are sample data:

const Item items1[] = {
  { 1, "Foo" },
  { 1, "Foo" },
  { 2, "Bar" },
  { 4, "Foobar" },
};
const Item items2[] = {
  { 1, "Foo" },
  { 1, "Firefox" },
  { 1, "Another one" },
  { 2, "Boo" },
  { 5, "Last one" },
};
const unsigned count1 = _countof(items1);
const unsigned count2 = _countof(items2);

The final result may look like this:

1              Foo   <->   1              Foo
--                   <->   1          Firefox
1              Foo   <->   1      Another one
2              Bar   <->   2              Boo
4           Foobar   <->   --
--                   <->   5         Last one

Comments | #algorithms Share

# C++ in Game Programming - Slides

Thu
04
Nov 2010

Here are slides from my yesterday lecture "C++ in Game Programming" (in Polish):

C++ w programowaniu gier.pdf
C++ w programowaniu gier.pptx

Comments are welcome. I consider this an attempt before writing something bigger of this kind that I hope to submit as a paper to one of Polish game developers conferences next year, like IGK.

Comments | #c++ #teaching #events Share

# My Lecture on Polygon Group

Tue
02
Nov 2010

I've joined "Polygon" - a scientific group of game developers on Warsaw University of Technology (Website, Forum, Facebook). That's true I'm no longer a student, but this fact doesn't forbid me to drink beer just like they do :) Tomorrow I'll give there a lecure entitled "C++ in game development". Slides will be available for download in the coming days.

Comments | #teaching #events Share