Rotate one to the left

Last week I wrote a small function in Perl that rotates and array to left. The function takes the item from the front and appends it to the back.

# precondition: @list >= 1;
sub rotate_left_by_one {
    my $ar = shift;
    my $item = shift @$ar;
    push @$ar, $item;
    return;
}

After calling this function as many times as the length of the array, it leaves the items in the same order they started in. Every call to this function puts a different item in the first location. I use it to compare this item to the rest of the items.

You would use it like this:

while (1 .. @list) {
    # your code
    rotate_left_by_one(\@list);
}

This function works great when the code doesn't depend on the order of the items in @list. The items in @list will be in a different order than what it started with for most of the iterations of the loop. This means that the code in the loop body needs to have the commutative property.

Low level code

Google released the PDF code of Chrome just a few days. I took a look at it. This file (core/src/fpdfdoc/doc_vt.cpp) is an example of how the code looks.

Sometime later it dawned on me that this code is built out of only low level pieces. There are almost no algorithms extracted to functions.

An example would binary search. There are five copies of binary search hidden in just that file. No wonder this file is 1864 lines of code.

What else would be hidden in there?

StrictWeakOrdering

I always forget what strict weak ordering means, but it's quite simple, actually.

My explanation is based on the Programming Conversation of last week and I hope this will help me remember the next time I hear about this.

Let's start with ordering. A relation is an ordering if it is transitive.

ordering -->  for all a, b, c: r(a, b) and r(b, c) => r(a, c)

And now strict.

strict  -->   for all a:  !r(a, a)

This means that for a strict relation comparing a with itself will never be true. An example of r that is strict is <. A value will never be less than itself.

The complement of strict is reflexive.

reflexive -->  for all a: r(a, a)

This means that for a strict relation comparing a with itself will always be true. An example of relation that is reflexive is equality.

total   -->  for all a, b: r(a, b) or r(b, a) or a = b
weak    -->  for all a, b: r(a, b) or r(b, a) or (!r(a, b) and !(r(b, a))

Total ordering means that two objects relate to each other in one of three ways: a < b or b < a or a = b.

Weak ordering means the two objects relatie to each other in one of three ways: a < b or b < a or ( !(a < b) && !(b < a) ).

Broken interface of Math.min

In an article about creating a column layout I found the following two lines of code:

var min = Array.min(blocks);
var index = $.inArray(min, blocks);

This first finds the minimum value in blocks and then the index of that value. This combination of lines is very strange. Array.min already knows the index of the minimum element and throws it away. Then the programmer needs to find the index again with a linear search.

This means the interface of Array.min is incomplete. A more general version would return the index of the value in the array that is minimal. This can't be written on top of the Array.min function in a efficient manner.

The following is a function that returns the index of the minimum element in elements.

// elements is a non-empty array
function min_index(elements) {
    var i = 1;
    var mi = 0;

    while (i < elements.length) {
        if (elements[i] < elements[mi])
            mi = i;
        i += 1;
    }
    return mi;
}

The corresponding max_index looks like this:

// elements is a non-empty array
function max_index(elements) {
    var i = 1;
    var mi = 0;

    while (i < elements.length) {
        if (!(elements[i] < elements[mi]))
            mi = i;
        i += 1;
    }
    return mi;
}

Stability in column layout

I was reading the notes on programming PDF and found a discussion about writing min and max functions for multiple arguments. I didn't what to use this for. Also there was a discussion about stability. Stability is when you leave elements in the same position when they're the same. This seems to be about sorting.

At the same I was implementing a Pinterest like column layout. I already had a working version. But sometimes the images weren't loaded completely and the algorithm would overlap images, because the height of the element wasn't known.

So I started searching for solutions to this problem and found this answer on StackOverflow from the creator of the Pinterest layout himself. He doesn't have the solution to my problem, but suggests to put the element in the shortest column. This will solve a problem that I hadn't seen yet.

So I implemented the following:

function min(cols) {
    return (cols[0] < cols[1]) ? 0 : 1;
}

$(window).load(function() {
    var start = 100;
    var cols = [ start, start ];
    var w    = [ 0, 330 ];

    $('.submission').each(function() {
        var col = min(cols);

        var height = $(this).height();
        $(this).css('position','absolute');
        $(this).css('left', w[col]+ 'px');
        $(this).css('top', cols[col]+ 'px');
        $(this).css('width', '320px');
        cols[col] += height + 32;
    });
});

As you can see in this case with two columns we can pick a column based on the height of column. At first I didn't think this had anything to do with stability. But it does. If you run this code the first element will be inserted in the right column. This is because the 0 in column 0 is not smaller than the 0 in column 1, it's equal. The min function will return 1 in this case, which is the right column.

Stability in the case of column selection is that the algorithm prefers to insert the element in the left column instead of the right column in case of equal heights.

There is a simple change that should be made to the min function to fix this problem. We need to swap the operands of the < operator and the return values so we don't lose stability.

function min(cols) {
    return (cols[1] < cols[0]) ? 1 : 0;
}

Properties like stability are general and also apply to Javascript.

Renewed interest in C++

In the previous post I showed a playlist of presentations by Alexander Stepanov, the creator of STL. In these videos he talks about algorithms and data structures (written in C++). This principled explanation of programming makes a lot of sense to me. And has me take a renewed look at C++.

Programming conversations

BitTorrent Sync

A month ago I wrote about File Transfer for mobile phones. There I wrote how I think a solution for file transfer should work. A few days later I found Bittorrent Sync. Problem solved!

Use ZeroMQ to control a receipt printer

A customer needed a solution to the following problem. There are multiple web POS systems that need to print to a receipt printer. The web server is not in the same place as the POS terminals, but they are connected to a network.

To solve the problem I used ZeroMQ to connect the web server to the receipt printers. The current solution consists of four parts.

  1. Web app
  2. Web server (connects a PUSH socket to a PULL socket)
  3. ZeroMQ device (a multiplexer receives from a PULL socket and sends these to a PUB socket)
  4. Computer with receipt printer (a sink that receives on a SUB socket subscribed to its own address)

First a user in a browser clicks the button to print a receipt.

This command is converted into a data packet formatted for the receipt printer.

This data packet is send to a small program that connects the web server and the point of sale systems. The first frame of the data packet contains the name of the POS system that should print the receipt.

The command to print the receipt contains the address of the terminal that requested to print.

The two small programs are written in Go. The multiplexer program opens two sockets and reads from one socket and sends the other socket. Program 4 opens a socket and reads from it. It sends the packets that it receives to WinAPI printer functions.

The nice thing of the solution is that the multiplexer program doesn't need to know how many printers are connected. So the customer can just connect a sink program for every new terminal that is added.

File transfers for mobile phones

Sometimes I need to copy a file from my computer to my phone. That's should be really easy. But it's not. I would like it to work like this:

  1. I put a file in a folder.
  2. If my phone is on the same network, the file should be copied from the computer to my phone, without further actions from me.

And that's it. The file shouldn't be copied to a server somewhere else. It should only move from my computer to my phone and never touch the internet.

It also means that this functionality won't work over the internet. So if my phone is not connected to the local wifi, it stays on the computer.

The other way around, if I make a few photos with my phone, these photos should be copied automatically to a directory on my computer when I come home.

Why doesn't it work like this?

Welcome

My name is Peter Stuifzand. You're reading my personal website.

Profiles