blog.murph.ie

Simon (or was it Aaron, those two classes have merged into one in my memory) would be proud. All it took was a casual glance at the description of a Trie on Wikipedia to remind me of what it actually was, allowing me to take a first stab at it. Not bad for something that I have only very vague recollections about learning over four years ago in a Data Structures and Algorithms lecture.

Regardless of who it was that taught us, they seem to have made a good job of it.

Why trie?

Currently for some work related to my PhD I’m looking at the initialisation of a large population of trees. One property of this initial population is that each tree should be unique, since (randomly) generating duplicate structures at the very beginning of a search is a little silly.

To date, I’ve been using Java’s builtin HashMap as a look up table to see if a specific tree structure already exists, and while this approach works, it might not be ideal. Erik, a colleague in the NCRA mentioned he had just coded up a Trie to do something similar but with Strings and chars as opposed to Trees and Nodes.

The code is available here (and a sample Iterator to use it with here).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

import java.util.ArrayList;
import java.util.Iterator;
 
/**
 * A Trie for Iterable Objects
 *
 * @author Eoin Murphy <eoin.murphy@ucd.ie>
 */
public class Trie<K extends Iterable, V> extends ArrayList<Trie<K, V>> {
 
  /** The key for this node */
  private Object key;
 
  /** The value */
  private V value;
 
  /**
   * Creates a new empty trie. The root node is keyed and valued with
   * null
   */
  public Trie() {
    key = null;
    value = null;
  }
 
  /**
   * Creates a new trie node keyed with <code>key</key> and with a
   * null <code>value</code>
   *
   * @param key The partial key for this node
   */
  public Trie(Object key) {
    this.key = key;
    value = null;
  }
 
  /**
   * Add a key-value pair to the trie, overwriting any previous value
   * that was asssociate with that key in the trie
   *
   * @param k The key 
   * @param value The value to store
   * @return If the key was already present, the previous value is returned. Otherwise, null.
   */
  public V put(K k, V value) {
    Iterator<K> i = k.iterator();
    return put(i, value);
  }
 
  /**
   * This is a private recursive method called initialy by its public
   * companion to iterate through the key, traversing the trie and
   * adding nodes when needed
   *
   * @param i The iterator for the key
   * @param value The value to store
   * @return If the key was already present, the previous value is returned. Otherwise, null.
   */
  private V put(Iterator<K> i, V value) {
    if (!i.hasNext()) {
      V returnValue = this.value;
      this.value = value;
      return returnValue;
    }
 
    Trie<K, V> next;
    Object nextKey = i.next();
 
    int index = indexOf(nextKey);
    if (index == -1) {
      next = new Trie(nextKey);
      add(next);
    }
    else 
      next = get(index);
 
    return next.put(i, value);
  }
 
  /**
   * Gets the value for the key from the trie.
   * If the key is absent, returns null
   *
   * @param i The key
   * @return The value for the key, or null if key is absent
   */
  public V get(K k) {
    Iterator<K> i = k.iterator();
    return get(i);
  }
 
  /**
   * Private recusive helper method called initialy by the public
   * version of the method
   *
   * @param i The key's iterator
   * @return The value for the key, or null if the is not present
   */
  private V get(Iterator<K> i) {
    if (!i.hasNext())
      return value;
 
    Trie<K, V> next;
    Object nextKey = i.next();
 
    int index = indexOf(nextKey);
    if (index == -1)
      return null;
    else 
      next = get(index);
 
    return next.get(i);
  }
 
  /**
   * Attempts to find the index of the child node keyed with
   * <code>o</code>
   * 
   * @param o The key to find
   * @return The index of the trie node keyed with <code>o</code> or -1 if it's absent
   */
  public int indexOf(Object o) {
    for (int i = 0; i < size(); i++)
      if (get(i).key.equals(o))
        return i;
    return -1;
  }
}

The code is available here (and a sample Iterator to use it with here).

First follow the link below to set up the repository and install Skype using yum.
http://www.multimediaboom.com/install-skype-on-fedora/

Next install glibc.i686 so we can use the tool ldd.

sudo yum install glibc.i686

We can now use ldd to find which library files are missing and yum is able to find which packages provide those files and install them for us.

for lib in `ldd /usr/bin/skype | grep "not found" | awk '{print $1}'`; do sudo yum -y install $lib; done

EDIT: It seems the audio playback was still not working, even after doing everything above. It took the following package to get it going.

sudo yum install alsa-plugins-pulseaudio.i686

Random thought today.

I found myself thinking about these strange-looking things

1
2
3

(a = 0)++;
++(a = 0);
(a = 0) = 1;

All of which produce the result of a containing the value 1. It’s kind of bizarre and I’m not overly surprised it works, but I can’t explain why.

While I have seen examples of = operations being used as rvalues (see directly below), I hadn’t seen them being used as lvalues before. Since these operations are read from right to left, the result of each operation is used as an rvalue for the next. The parentheses break this assertion.

1

a = b = c = 6;

Looking at the declaration of the operator we start to understand. The = operator returns a reference to our initial lvalue.

1

T& T::operator =(const T& b);

The IBM compiler information center (while for AIX should be fine for this example) tells us

An object is a region of storage that can be examined and stored into. An lvalue is an expression that refers to such an object…

and that

The term rvalue refers to a data value that is stored at some address in memory. An rvalue is an expression that cannot have a value assigned to it…

It goes on to say

…in C++, a function call that returns a reference is an lvalue. Otherwise, a function call is an rvalue expression. In C++, every expression produces an lvalue, an rvalue, or no value.

Going back and looking at the prototype of the = operator we can see that it does indeed return a reference, so in our example the expression (a = 0) is an lvalue and can then be used with the increment operators or the = operator and the rvalue, 1.

1
2
3
4

T& T::operator =(const T& b);
(a = 0)++;
++(a = 0);
(a = 0) = 1;

After all that, learning that an = operation produces an lvalue, how come they can also be used as rvalues like in the following example?

1

a = b = c = 6;

Well IBM also tell us that

…When an lvalue appears in a context that requires a rvalue, the lvalue is implicitly converted to an rvalue. The reverse, however, is not true: an rvalue cannot be converted to an lvalue.

And there you have it. Pointless you say? Yes. Am I likely to use any of these expressions? Probably not.

That said, at least I have learnt something about lvalues and rvalues in C++, and I’m not likely to be confused by an “lvalue required” error message again.

Groupon is dangerous.

I recently came across this deal for HelloCanvas.ie, €36 gets me €98 worth of canvas printing. Deal.

I chose a panorama I took of NY city. It was taken at night, from the top of the Rockefeller Center, facing the Empire State Building. Since it is a panorama and quite long, their regular sizes didn’t quite fit it, but their order process let me chose the dimensions that I wanted and add some comments on how I’d like the image printed.

The finished product is 40 x 140 cm and 3 cm deep. In the end I had to pay an extra €10 to get the dimensions I wanted but I am very happy with how it turned out.

Oh and it’s quite clear, apologies for the blurry photo. If you would like the original file, just let me know. It’s pretty big so I’m not going to put it up here…

Night Panorama Of New York City

Had a good day’s travelin’ today.

Duration: 16hours 30mins

And of course, Google followed me the whole way…

Yesterday, while procrastinating, I was looking through /var/log and happened upon a username brute-force attack. Any one with a static IP and ssh open to the world will be familiar to these. I was sitting there with tail -f /var/log/secure.log in front of me, watching this guy’s script try username after username to ssh into my machine. I wasn’t worried, he was already up in the ‘h’s, well past the only username accessible on the machine. He wasn’t going to get lucky today.

Intrigued by this, and not knowing enough about OS X’s firewall rules to blacklist him, I checked out the IP address that the attack was coming from. GEOIP put him in Poland, but since it would be silly to do this from your own computer I figured that he might have borrowed someone else’s machine. Sure enough the website attached to the IP was someone’s (pretty terrible) company site. It got me wondering how he got access to the Polish machine, so I googled the IP. Bingo.
Read the rest of this entry »