My Random Tech Stuff: July 2012

Tuesday, July 31, 2012

My .vimrc

set tabstop=4
set shiftwidth=4
set expandtab
set autoindent
set smartindent
set number
set ruler
set hlsearch
set ignorecase

Monday, July 30, 2012

How to Dynamically Load C++ Shared Libraries on Linux

Below is an example how to dynamically load a C++ shared library on Linux. This is the project structure.

|-- include
|   |-- Hello.h
|   `-- IHello.h
|-- src
|   |-- Hello.cpp
|   `-- Main.cpp
`-- wscript

IHello.h

#ifndef IHELLO_H_
#define IHELLO_H_
 
class IHello {
public:
    virtual void SayHello() const = 0;
    virtual ~IHello() {};
};
 
typedef IHello* (*CreateFunc)();
typedef void (*DestroyFunc)(IHello*);
 
#endif /* IHELLO_H_ */

First, we need to create C-like functions for creating an instance of Hello and destroying it. This is a kind of factory class. Second, we need to add extern "C" to avoid C++ name mangling.

Hello.h

#ifndef HELLO_H_
#define HELLO_H_
 
#include "IHello.h"
 
class Hello : public IHello {
public:
    Hello();
    void SayHello() const;
    virtual ~Hello();
};
 
#endif /* HELLO_H_ */

Hello.cpp

#include <iostream>
#include "Hello.h"
using namespace std;
 
Hello::Hello() {
    cout << "Creating Hello" << endl;
}
 
Hello::~Hello() {
    cout << "Destroying Hello" << endl;
}
 
void Hello::SayHello() const {
    cout << "Hello World" << endl;
}
 
extern "C" IHello* CreateHello() {
    return new Hello;
}
 
extern "C" void DestroyHello(IHello* h) {
    delete h;
}

Main.cpp

#include <iostream>
#include <dlfcn.h>
#include "IHello.h"
using namespace std;
 
int main() {
    void* helloLib = dlopen("./libhello.so", RTLD_LAZY);
    if (!helloLib) {
        cerr << "Error loading libhello.so" << endl;
        return 1;
    }
 
    CreateFunc cf = (CreateFunc) dlsym(helloLib, "CreateHello");
    IHello* hello = cf();
    hello->SayHello();
 
    DestroyFunc df = (DestroyFunc) dlsym(helloLib, "DestroyHello");
    (df)(hello);
 
    if (dlclose(helloLib)) {
        cerr << "Error closing libhello.so" << endl;
        return 1;
    }
 
    return 0;
}

As you can see in the Main.cpp, we only include IHello.h and not Hello.h (the implementation), which is a pure virtual class. This is something like an interface in Java/C#.

wscript

#!/usr/bin/env python
 
top = '.'
out = 'build'
 
def options(opt):
    opt.load('compiler_cxx')
     
def configure(ctx):
    ctx.load('compiler_cxx')
     
def build(ctx):
    ctx.shlib(source='src/Hello.cpp', cxxflags=['-g', '-Wall'],
              target='hello', includes=['include'])
     
    ctx.program(source='src/Main.cpp', cxxflags=['-g', '-Wall'],
                lib=['dl'], includes=['include'], target='main')

Let's build it now.

waf configure build
cd build
./main

Below is the output.

Creating Hello
Hello World
Destroying Hello

Sunday, July 22, 2012

Getting Started with Waf to Build C/C++ Applications

Waf is another build tool like SCons. It's a fork of SCons that is more Pythonic than SCons. Here is a simple example how to get build a C++ application with Waf.

waf-project
├── include
│   └── Hello.h
├── src
│   ├── Hello.cpp
│   └── Main.cpp
└── wscript

Hello.h

#ifndef HELLO_H_
#define HELLO_H_
 
class Hello {
public:
    void sayHello();
};
 
 
#endif /* HELLO_H_ */

Hello.cpp

#include <iostream>
#include "Hello.h"
using namespace std;
 
void Hello::sayHello() {
    cout << "Hello World" << endl;
}

Main.cpp

#include "Hello.h"
using namespace std;
 
int main() {
    Hello h;
    h.sayHello();
 
    return 0;
}

wscript

#!/usr/bin/env python
 
APPNAME = 'waf-project'
VERSION = '0.1'
 
top = '.'
out = 'build'
 
def options(ctx):
    ctx.load('compiler_cxx')
    ctx.add_option("--shared", action="store_true", help="build shared library")
    ctx.add_option("--static", action="store_true", help="build static library")
     
def configure(ctx):
    ctx.load('compiler_cxx')
 
def build(ctx):
    if ctx.options.shared:
        ctx.shlib(source="src/Hello.cpp", target="hello", includes=["include"],
                  cxxflags="-g -Wall -O0")
    elif ctx.options.static:
        ctx.stlib(source="src/Hello.cpp", target="hello", includes=["include"],
                  cxxflags="-g -Wall -O0")
    else: # by default, build a shared library
        ctx.shlib(source="src/Hello.cpp", target="hello", includes=["include"],
                  cxxflags="-g -Wall -O0")
         
    ctx.program(source="src/Main.cpp", target="main", includes=["include"],
                use="hello")

waf configure

This will create all the configuration files in a "build" directory as specified in the out variable.

waf configure build --static

This will create a "hello" static library and a "main" program that is statically linked with the "hello" static library. The static library and the program will be created in a "build" directory as specified in the "out" variable.

waf configure build --shared

This will create a "hello" shared library and a "main" program that is dynamically linked with the "hello" shared library. The shared library and the program will be created in a "build" directory as specified in the "out" variable.

Friday, July 13, 2012

Compressing Characters in Python

This is an in-place algorithm for compressing characters, e.g.

AABBCCCDDXYYZ --> A2B2C3D2XY2Z

The reason why the output isn't A2B2C3D2X1Y2Z1 is because adding 1 for only any non-repeated contagious character can make the compressed data bigger than the actual data, e.g.

ABCD --> A1B1C1D1 (A1B1C1D1 is larger than ABCD)

#!/usr/bin/env python
 
def compress(l):
    if len(l) == 0: return []
    counter = 1
    tmp = l[0]
    i = 1
    while i < len(l):
        if l[i] != tmp:
            new_index = update(i, counter, l)
            i = new_index + 1
            tmp = l[i]
            counter = 1
        else:
            counter += 1
        i += 1
    update(i, counter, l)
    return l
 
def update(current_index, counter, l):
    if counter == 1: return current_index - 1
    new_index = current_index - (counter - 1)
    l[new_index] = str(counter)
    shift(current_index, new_index+1, l)
    return new_index
 
def shift(source_index, destination_index, l):
    last_index = len(l)
    i = 0
    while (source_index + i) < last_index:
        l[destination_index+i] = l[source_index+i]
        i += 1
    last_index = destination_index + i
    del l[last_index:]
 
if __name__ == "__main__":
    assert (['A', '4', 
            'B', '2', 
            'C', 
            'D', '3', 
            'E', '2', 
            'A', '2', 
            'X', 
            'Y', '5', 
            'Z'] 
            ==
            compress(["A", "A", "A", "A",
                      "B", "B",
                      "C",
                      "D", "D", "D",
                      "E", "E",
                      "A", "A",
                      "X",
                      "Y", "Y", "Y", "Y", "Y",
                      "Z"]))

Converting Relative Path to Absolute Path in Python

#!/usr/bin/env python
 
def get_absolute_path(path):
    files = path.split("/")
    l = []
    for f in files:
        if f == "..":
            l.pop()
        else:
            l.append(f)
    return "/".join(l)
 
if __name__ == "__main__":
    assert "/windows/temp/" == get_absolute_path("/windows/abs/../temp/new/../")
    assert "windows/temp/" == get_absolute_path("windows/abs/../temp/new/../")
    assert "/windows/temp" == get_absolute_path("/windows/abs/../temp/new/..")

Wednesday, July 11, 2012

Implementing Word Completion in Python

#!/usr/bin/env python
 
class Node(object):
    def __init__(self, value=None):
        self.value = value
        self.children = []
         
class Trie(object):
    def __init__(self):
        self.root = Node("Root")
     
    def add(self, key):
        self._add(self.root, key, 0)
 
    def _add(self, node, key, index):
        if len(key) == index: return
        next_node = None
        for n in node.children:
            if n.value == key[index]:
                next_node = n
                break
        if next_node is None:
            next_node = Node(key[index])
            node.children.append(next_node)
            print "Adding", next_node.value, "into", node.value
        self._add(next_node, key, index+1)
     
    def find(self, key):
        return self._find(self.root, key, 0)
     
    def _find(self, node, key, index):
        if len(key) == index: return node
        found = False
        for n in node.children:
            if n.value == key[index]:
                found = True
                last_found_node = self._find(n, key, index+1)
        if not found: return None
        else: return last_found_node
         
    def search(self, key):
        result = []
        last_node = self.find(key)
        if last_node is None: return result
        self._search(last_node, key, "", result)
        for i in xrange(0, len(result)):
            result[i] = key + result[i]
        return result
     
    def _search(self, node, key, char, result):
        if len(node.children) == 0:
            result.append(char)
            return
        for n in node.children:
            self._search(n, key, char + n.value, result)
         
     
class WordCompletion(object):
    def __init__(self, words):
        self.trie = Trie()
        for word in words:
            print "===== Inserting", word, "====="
            self.trie.add(word)
     
    def search(self, prefix):
        return self.trie.search(prefix)
         
if __name__ == "__main__":
    words = ["ABCD", "ABCE", "AFG", "AFHIJ", "AFHIK", "XY"]
    wc = WordCompletion(words)
     
    assert ['ABCD', 'ABCE', 'AFG', 'AFHIJ', 'AFHIK'] == wc.search("A")
    assert ['AFHIJ', "AFHIK"] == wc.search("AFHI")
    assert ['AFHIJ', 'AFHIK'] == wc.search("AFH")
    assert ['ABCD', 'ABCE'] == wc.search("ABC")
    assert [] == wc.search("whatever")

Wednesday, July 4, 2012

Implementing Tic-Tac-Toe in Python

This is my simple tic-tac-toe implementation in Python.

#!/usr/bin/env python
 
class TicTacToe(object):
    def __init__(self, n=3):
        self.n = n
        self.board = []
        for i in xrange(self.n):
            self.board.append([])
            for j in xrange(self.n):
                self.board[i].append(" ")
         
    def draw(self):
        for x in self.board:
            print x
             
    def move(self, player, x, y):
        if x >= self.n or y >= self.n:
            raise Exception("Invalid move!")
        if self.board[x][y] != " ":
            raise Exception("Invalid move!")
        self.board[x][y] = player
     
    def win(self, player):
        same = True
        for i in xrange(self.n):
            if self.board[0][i] != player: 
                same = False
                break
        if same: return True
         
        same = True
        for i in xrange(self.n):
            if self.board[i][0] != player:
                same = False
                break
        if same: return True
         
        same = True       
        for i in xrange(self.n):
            if self.board[self.n-1][i] != player:
                same = False
                break
        if same: return True
 
        same = True
        for i in xrange(self.n):
            if self.board[i][self.n-1] != player:
                same = False
                break
        if same: return True
         
        same = True
        for i in xrange(self.n):
            if self.board[i][i] != player:
                same = False
                break
        if same: return True
         
        same = True
        x = -1
        y = self.n
        for i in xrange(self.n):
            x += 1
            y -= 1
            if self.board[x][y] != player:
                same = False
                break
        if same: return True
        return False
                 
 
if __name__ == "__main__":
    player1 = "X"
    player2 = "O"
     
    t3 = TicTacToe()
     
    t3.move(player1, 2, 0)
    t3.move(player2, 1, 2)
     
    t3.move(player1, 1, 1)
    t3.move(player2, 2, 1)
     
    t3.move(player1, 0, 2)
     
    t3.draw()
     
    print "Player1", "won" if t3.win(player1) else "lost"
    print "Player2", "won" if t3.win(player2) else "lost"

Tuesday, July 3, 2012

How to Generate a List of Possible Words in a Phone Number in Python

Example, if we type 2 -> 2 -> 3. The we have can have words like "AAD", "AAE", "AAF", etc.

#!/usr/bin/env python
 
numbers = {"2" : ["A", "B", "C"],
           "3" : ["D", "E", "F"],
           "4" : ["G", "H", "I"],
           "5" : ["J", "K", "L"],
           "6" : ["M", "N", "O"],
           "7" : ["P", "Q", "R"],
           "8" : ["S", "T", "U"],
           "9" : ["V", "W", "X"],
           "0" : ["Y", "Z"]}
 
def generate(input_list):
    return gen(input_list, 0, "")
 
def gen(input_list, index, n):
    if index > len(input_list)-1: return [n]
    output_list = []
    for i in input_list[index]:
        index += 1
        for x in numbers[i]:
            tmp = gen(input_list, index, x)
            for t in tmp:
                output_list.append(n + t)
    return output_list
     
if __name__ == "__main__":
    for i in generate(["2", "4", "3", "6"]): print i

My Random Tech Stuff