VIM formatting

To auto format a section of code in vim use '=' followed by a movement command.

For example if you want to format

void foo() {
  int blah;
      int foo;
          int bar;
}

Navigate the the first '{' and press '=%' = will tell it format, where '%' will tell it to go to the corresponding block.

PHP Sample Command Line Scrip

Some co-workers of mine didn't believe that PHP could be used from the command line. I was rather suprised by this, and thought others might be under the same impression. To help spread the word, here's a very simple example of a php script meant to be run from the command line.

<?php

if ($argc != 2 || in_array($argv[1], array('--help', '-help', '-h', '-?'))) {
?>

This is a command line PHP script with one option.

  Usage:
  <?php echo $argv[0]; ?> <option>

  <option> can be some word you would like
  to print out. With the --help, -help, -h,
  or -? options, you can get this help.

<?php
} else {
    echo $argv[1];
}
?>

PHP Web Service example.

Its been a while since I used PHP. The last time I used it was PHP 4. I felt it was time to revisit the language. I have good memories of PHP. It was better than perl and it worked reasonably well for a mediawiki installation I maintained.

If you view the other post I've made, you'll see that a first test of a language that I like to do is to see if it supports a simple SOAP call. This tutorial will be the same test for PHP.

First lets install it. If you use any *nix system you'll probably already have it installed. If not or if you want the latest copy then go to http://www.php.net/downloads.php and download the version for you install. I chose the windows installer. During the setup process it asked which extensions I would like installed I opted for the SOAP library which will be needed for the rest of the tutorial.

I installed PHP in the default location of c:\program files\php, so I opened a command prompt and browsed to that location.

Now for our simple web service test. We'll be accessing 'http://webservices.daehosting.com/services/isbnservice.wso?WSDL' and asking if a given ISBN is valid or not.

The first task is create a new SOAPClient object.

$client = new SOAPClient('http://webservices.daehosting.com/services/isbnservice.wso?WSDL');

Now we call our method which is named '>IsValidISBN13'. Like perl's SOAP::Lite we need to give a hash as our argument so the web service knows which variable were passing so we first create a parameter list, then call the function.

$params = array('sISBN'=>"9781565926103");
$result = $client->IsValidISBN13($params);

So far so good. Now the only tricky part I found of the process. The PHP Soap libraries return a stdClass. We need to unravel this into something meaningful to us. The documentation uses this function so I did as well.

function obj2array($obj) {
  $out = array();
  foreach ($obj as $key => $val) {
    switch(true) {
        case is_object($val):
         $out[$key] = obj2array($val);
         break;
      case is_array($val):
         $out[$key] = obj2array($val);
         break;
      default:
        $out[$key] = $val;
    }
  }
  return $out;
}

Then lastly I just print out the array which contains our result:

print_r(obj2array($result));

You can now experiment by passing different ISBN's ones that are both valid and invalid and you'll see the result is different. You can also call the method that checks for validity of a 10 character length ISBN.

Here is the entire code listing.

<?php

$client = new SOAPClient('http://webservices.daehosting.com/services/isbnservice.wso?WSDL');
$params = array('sISBN'=>"9781565926103");
$result = $client->IsValidISBN13($params);

function obj2array($obj) {
  $out = array();
  foreach ($obj as $key => $val) {
    switch(true) {
        case is_object($val):
         $out[$key] = obj2array($val);
         break;
      case is_array($val):
         $out[$key] = obj2array($val);
         break;
      default:
        $out[$key] = $val;
    }
  }
  return $out;
}


print_r(obj2array($result));


?>

Boost Python - Abstract Classes

In the previous article I covered setting up Boost Python to work in Visual Studio.

In this article were going to get into a bit more detail of describing the bindings of classes. Specifically were going to deal with abstract classes and polymorphism.

Consider the following:

struct AbstractClass {
    virtual std::string speak() const = 0;
};

struct DerivedClassA : AbstractClass {
    virtual std::string speak() const {return "Derived Class A";}
};

struct DerivedClassB : AbstractClass {
    virtual std::string speak() const {return "Derived Class B";}
};

We have an Abstract Class and two derived class that implement the speak method. How do we model this in Boost Python such that in Python we can get a pointer to one of these objects and call speak on the proper derived class.

To do this we have to build a wrapper class:

struct WrapperClass : AbstractClass , boost::python::wrapper<AbstractClass> { 
    virtual std::string speak() const {
        return this->get_override("speak")();
    }
};

This wrapper class extends the AbstractClass, and extends a special boost::python::wrapper. For each virtual method you wrap it and call it with this->get_override().

Lastly you need to define the bindings for Python, this is similar to the Hello World example in article one:

BOOST_PYTHON_MODULE(PyHelloWorld)
{
    using namespace boost::python;
    def("getDerivedClassA",&getDerivedClassA,return_value_policy< manage_new_object >());
    def("getDerivedClassB",&getDerivedClassB,return_value_policy< manage_new_object >());
    class_<WrapperClass, boost::noncopyable > ("DerivedClass") 
        .def("speak",boost::python::pure_virtual(&AbstractClass::speak))
        ;
    
}

Here we added two test methods called getDerivedClassA and getDerivedClassB these will be in the package PyHelloWorld as dictated by 'BOOST_PYTHON_MODULE(PyHelloWorld)'

Lastly we want to be able to execute python in the same process as our executable. If you followed the instructions in part 1 then you simply need to add this method:

void start( ) {        
    using namespace boost::python;            
    Py_Initialize();    
    // Explicitly call the method that the BOOST_PYTHON_MODULE macro created.
    // This sets up our DLL to be used by python. 
    initPyHelloWorld();
    std::string pythonCommand;
    try {
        PyRun_SimpleString("import PyHelloWorld");        
        while(1) {
            std::cout << ">>> "; 
            getline(std::cin,pythonCommand);                           
            if (pythonCommand == "quit") {
                break; 
            }else {
                std::cout << PyRun_SimpleString(pythonCommand.c_str());
            }
        }
    } catch ( error_already_set ) {
        PyErr_Print();
    }
    Py_Finalize();                    
}

So now lets try it:

>>> import PyHelloWorld
0>>> a = PyHelloWorld.getDerivedClassA()
0>>> b = PyHelloWorld.getDerivedClassB()
0>>> print a.speak()
Derived Class A
0>>> print b.speak()
Derived Class B
0>>>

Boost Python

Boost Python allows seamless interoperability between C++ and Python. In this article we'll setup Boost and build a simple hello world program that will be able to run in Python.

Boost, in case your unfamiliar, is a powerful set of libraries for C++. There website is at www.boost.org.

For this post we will be using Boost 1.36.0

Boost can be tricky to setup. Their documentation recommends using their own build tool called bjam, but I typically like to build it myself. For this article we'll walk through setting up Boost Python for Visual Studio 2005.

If you haven't already, download boost 1.36.0 library to your local machine. I've expanded the library to c:\download\boost\boost-1.36.0 on my machine.

Now open up Visual Studio 2005. New Project, Visual C++ -> Win32 -> Win32 Console Applicaion.

At the bottom of the screen enter the name for your project: PyHelloWorld, and the location, in my case c:\download\PyHelloWord. The solution name should be filled out for you (PyHelloWorld), and the check mark for 'Create directory for solution' should be checked.

Click Ok.

In the wizard click next. Select 'Dll' as application type, and Empty Project from additional options.

Click finish.

The project we just created will hold our client code, and our python bindings code. Before we can do that though we need to build Boost Python. To do this we'll create another project.

Right click on your solution 'PyHelloWorld', Click Add->Add New Project.

Like before we'll create a Win32 Console Application but we'll call it BoostPython this time. I've decided to keep the project located in the same solution folder of PyHelloWorld.

Follow the steps in the wizard again to create an empty, dll project.

In order to build boost python we need to include all the source files. Visual studio should have created a 'Source Files' filter in the BoostPython project. Right click and select Add->Existing Item...

You want to add all the files from

• %PATH_TO_BOOST%\libs\python\src


• %PATH_TO_BOOST%\libs\python\src\converter


• %PATH_TO_BOOST%\libs\python\src\object

You now need to instruct the compiler that these are part of the boost source code. You do this by setting a preprocessor define. Right click on the BoostPython project, select c/c++ from the property pages, select Preprocessor, and append 'BOOST_PYTHON_SOURCE' to the end of the Preprocessor definitions. Its a semi-colon separated list so add a semi-colon then 'BOOST_PYTHON_SOURCE'.

Next set the include directory to find the Boost install. Right click on the BoostPython project, open the c/c++ -> General tab. Add your path to %PATH_TO_BOOST%, in my case that is C:\download\boost\boost_1_36_0

We've now set up the boost portion, we need to setup python by telling our project how to find our local python installation. First you'll need to download Python

The standard install saved Python under c:\Python25 on my machine. The standard python install comes with c++ headers so we'll point our BoostPython project at those headers.

Once again open the property page for BoostPython, C/C++ -> General , and add c:\Python25\include (or your python install) to the include path.

You can now build the BoostPython project, all the files should compile. The link step will fail though because it needs to link to the Python library as well. So one more tweak to the BoostPython project, this time Linker -> Input , Additional Dependencies. Add C:\Python25\libs\Python25.lib.

Build the project again and it should link successfully.

Okay now we have BoostPython ready to go. Lets Use it.

For the PyHelloWorld project we'll need to do the same steps as above to set the Include Path, and the Linker. More explicity you need to set:

• include path to boost
• include path to python
• linker to python lib

If you don't remember how look above to see what we set.


Now create a new cpp file by right clicking on the project, add->New Item. Selecting cpp file. Call the file hello.cpp

Add the following to the file.

#define BOOST_ALL_NO_LIB
#include <boost/python.hpp>

char const* speak()
{
    return "Hello World!";
}


BOOST_PYTHON_MODULE(PyHelloWorld)
{
    using namespace boost::python;
    def("speak", speak);
}

The first define instruct boost that we have already build it. The first function is your standard c++ function, the second is our python bindings.

Before you build you need to tell visual studio that this project is dependent on the BoostPython Project. Right click on PyHelloWorld project and click Project Dependencies. Select BoostPython.

Now Build. Everything should compile and build succesfully.

So what have we accomplished? We've build a dll that exposes method that python can understand. Lets test it and see if it works.

Open a Command shell, and navigate to your output directory. In my case its c:\download\PyHelloWorld\PyHelloWorld\debug. In order to make it easier for Python to find our dll lets rename it to pyd.

move PyHelloWorld.dll PyHelloWorld.pyd

Now lets load up the interpreter and try it out:

c:\download\PyHelloWorld\PyHelloWorld\debug>c:\Python25\python.exe
Python 2.5.2 (r252:60911, Feb 21 2008, 13:11:45) [MSC v.1310 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import PyHelloWorld
>>> print PyHelloWorld.speak();
Hello World!
>>>

There you go, python interacting with your c++ file. Now that you have the BoostPython project created it would be easy to do this binding for more complex types. The official docs cover how to use this for classes, virtual functions, etc. For more info I recommend you start there. http://www.boost.org/doc/libs/1_36_0/libs/python/doc/tutorial/doc/html/index.html

Hope that helps...

Enforce Noninstantiability With a Private Constructor

Occasionally you'll want to write a class that is just a grouping of static methods and static fields. Such classes have acquired a bad reputation because some people abuse them to avoid thinking in terms of objects, but they do have valid uses. They can be used to group related methods on primitive values or arrays, in the manner of java.lang.Math or java.util.Arrays. They can also be used to group static methods, including factory methods, for objects that implement a particular interface, in the manner of java.util.Collections. Lastly, they can be used to group methods on a final class, instead of extending the class.

Such utility classes were not designed to be instantiated: an instance would be nonsensical. In the absence of explicit constructors, however, the compiler provides a public, parameterless default constructor. To a user, this constructor is indistinguishable from any other. It is not uncommon to see unintentionally instantiable classes in published APIs.

Attempting to enforce noninstantiability by making a class abstract does not work. The class can be subclassed and the subclass instantiated. Furthermore, it misleads the user into thinking the class was designed for inheritance (Item 17). There is, however, a simple idiom to ensure noninstantiability. A default constructor is generated only if a class contains no explicit constructors, so a class can be made noninstantiable by including a private constructor:

// Noninstantiable utility class
public class UtilityClass {
   // Suppress default constructor for noninstantiability
   private UtilityClass() {
      throw new AssertionError();
   }
   ... // Remainder omitted
}

Because the explicit constructor is private, it is inaccessible outside of the class. The AssertionError isn't strictly required, but it provides insurance in case the constructor is accidentally invoked from within the class. It guarantees that the class will never be instantiated under any circumstances. This idiom is mildly counterintuitive, as the constructor is provided expressly so that it cannot be invoked. It is therefore wise to include a comment, as shown above.

As a side effect, this idiom also prevents the class from being subclassed. All constructors must invoke a superclass constructor, explicitly or implicitly, and a subclass would have no accessible superclass constructor to invoke.

This pattern also works well when you want the ability to cache an object. For example if you were creating a String class that is immutable. For every String "FOO" created you want one instance. If you make the class notinstantiable and instead add a String.get("foo") method, you can ensure that you return one and only one instance. For example:

public class MyString {
  private MyString() { }
  private WeakHashMap<String,String> map = new WeakHashMap<String,String>();
  public get(String s) {
    if (map.get(s)) 
      return map.get(s); 
    else {
      map.put(s,s);   
      return map.get(s); 
    }
  }
}

In fact this pattern is used for the Java Integer class. It is recommended you use Integer.valueOf(int i). We can see why by looking at their code:

private static class IntegerCache {
    private IntegerCache(){}

    static final Integer cache[] = new Integer[-(-128) + 127 + 1];

    static {
        for(int i = 0; i < cache.length; i++)
        cache[i] = new Integer(i - 128);
    }
    }

    /**
     * Returns a <tt>Integer</tt> instance representing the specified
     * <tt>int</tt> value.
     * If a new <tt>Integer</tt> instance is not required, this method
     * should generally be used in preference to the constructor
     * {@link #Integer(int)}, as this method is likely to yield
     * significantly better space and time performance by caching
     * frequently requested values.
     *
     * @param  i an <code>int</code> value.
     * @return a <tt>Integer</tt> instance representing <tt>i</tt>.
     * @since  1.5
     */
    public static Integer valueOf(int i) {
    final int offset = 128;
    if (i >= -128 && i <= 127) { // must cache 
        return IntegerCache.cache[i + offset];
    }
        return new Integer(i);
    }

For any value between -128 and 127 the class has already been constructed and when you call it, you simply get a pointer to that Object.

So in conclusion when you have a class that you don't always want instantiated you should consider making the constructor private.

QuickSort (c++)

Quicksort is a popular sorting algorithm. It runs in O(n log n). The sort is not stable meaning equal values may not appear in the same order. For this post we'll write a simple quick sort implementation.

Lets start with the entire code listing then we'll break it apart:

void swap(int &a, int &b) {
    int temp = a ;
    a = b;
    b = temp;
}

int partition(int * arr,int left, int right, int pivotIndex) {
    int pivotValue = arr[pivotIndex];
    swap(arr[right],arr[pivotIndex]);
    int storeIndex = left;
    for (int i=left;i<right -1; ++i) {
        if (arr[i] < pivotValue) {
            swap(arr[i],arr[storeIndex]);
            storeIndex++;
        }
    }
    swap(arr[storeIndex],arr[right]);
    return storeIndex;
}

void quicksort(int * arr, int left , int right) {
    if  (right > left) {
        int pivotIndex = left;
        int pivotNewIndex = partition(arr,left,right,pivotIndex); 
        quicksort(arr,left,pivotNewIndex-1);
        quicksort(arr,pivotNewIndex+1,right);
    }
    
}


int main(int argc, char** argv) {
    int arr[10] = { 3, 6, 1, 5, 3, 2, 6, 8, 9, 6};
    quicksort(&arr[0],0,9);
    for(int i = 0 ; i < 10; ++i) {
        printf("%d" , arr[i]);
    }
}

We have 3 methods not including main. Swap is a utility method that swaps the values.

The heart of the algorithm is the partition method. We choose value in the array and do a O(n) walk of the list putting all elements with value less than the chosen value before and all elements greater than the chosen value after the value. Our code is optimized to do it in place without requiring an extra array by moving the pivot to the end and then swapping it back at the end.

Once we have the partition method we simply recursively call quicksort and the list will be sorted.

Javascript Hangman

Hangman is a popular pencil and paper game. One player chooses a word and draws dashes to represent the length of the word.

The other player guesses letters. If the letter is in the word the dash is replaced with the letter. If the guessed letter is not in the word then a part of the hanging body is drawn (head, body, left leg, right leg, left arm, right arm) once the body is completely drawn or the entire word has been guessed the game is over.

I decided to re-create this game using Javascript and the html canvas object. Javascript is used to handle the game while the canvas is used to draw the hangman character when the guesses are incorrect.

To start lets define a simple html page that includes our canvas and a couple of spans to hold the word and messages for the user.

<html>
 <body onload="draw();" onkeyup="handleKeyUp(event);">
    <table>
        <tr>
            <td colspan=2>
                <span id='alreadyGuessed' style="visibility:hidden">Letter already guessed</span>
                <span id='strike' style="visibility:hidden">Strike!</span>
            </td>
        </tr>
        <tr>
            <td>
                <canvas id='hangman' width=150 height=150>
            </td>    
            <td>
                <span id='word'></span>                        
            </td>
        </tr>
    </table>
 </body>
</html>

When the page is loaded we call 'draw()' and we setup a keyboard listener to listen to keystrokes. We've defined a few simple span's that will be messages to the user, a canvas to draw the victim and a span to hold the word that the user will be guessing.

The game expects a character from A-Z so our keyboard listener should filter out all other values here is what our listener looks like:

function handleKeyUp(evt) {
  var e = evt ? evt : event; 
  if (e.keyCode >= 65 && e.keyCode < (65+26) ) {
    guess(String.fromCharCode(e.keyCode));            
  }
  draw();
}

The keyCode value is the ASCII representation we know that the ASCII characters are in sequence with capital 'A' being 65 and capital 'Z' being 65+26 characters away. If the user enters a valid character we enter our 'guess' function else we do nothing. After guessing our draw() function is called to redraw the screen.

The draw function as you have now seen is called when the game is first loaded and after each keypress lets see what it does.

function draw() {
        var str='';
        for(i=0;i<word.length;++i) {
            if (foundLetters[i]) {
                str += word[i];
            } else {
                str += '_';
            }
        str += ' ';
        }
        document.getElementById('word').innerHTML = str; 
    }

The draw function looks at our internal data structures which will explore later and determines if the user has guessed a letter yet or not. If the letter has been guessed the letter is shown, else a '_' is shown instead.


So now to the heart of the game, the guess function.

function guess(key) {
        hideMessages();
        if (guessedLetters[key]) {
            showAlreadyGuessed(); 
            return;
        }
        guessedLetters[key] = true;
        var found = false;
        for(i=0;i<word.length;++i) {
            if (word[i] == key) {
                foundLetters[i] = true;
                found=true;
            }
        }
        if(!found) showStrike();
        return found;

    }

The guess function iterates over the chosen word and determines if the character in the word has been guessed. If it has it marks foundLetters[index] where index is the index of the character that has been revealed. We saw in the 'draw' function how this is used to change the display.

The last thing to note is how we use the canvas element to draw a very crude hangman as the user guesses incorrectly.

function drawHangMan(numberOfStrikes) {
        var canvas = document.getElementById('hangman');
        if(canvas.getContext) {
            var ctx  = canvas.getContext('2d');
            ctx.save() ; 
            ctx.translate(45,45);
            ctx.clearRect(0,0,canvas.width,canvas.height); 
            ctx.beginPath();
            if(numberOfStrikes >= 1) ctx.fillRect(0,0,10,10);   //head
            if(numberOfStrikes >= 2) ctx.fillRect(-5,10,20,20); //body
            if(numberOfStrikes >= 3) ctx.fillRect(-20,10,20,5); //left arm
            if(numberOfStrikes >= 4) ctx.fillRect(0,10,30,5);  // right arm
            if(numberOfStrikes >= 5) ctx.fillRect(-5,30,5,10);  // left leg
            if(numberOfStrikes >= 6) ctx.fillRect(10,30,5,10);  // right leg
            
            ctx.fill();
            ctx.restore();
        }
    }

This method is pretty self explanatory. Based on the number of strikes more of the hangman's body will be revealed.

Here is the entire code listing, let me know if you have any questions. Enjoy...

<html>
 <head>
  <script type="application/x-javascript">

    var words = new Array();
    words[0] = "Ford";
     words[1] = "Chevy";
    words[2] = "Mazda";
    words[3] = "Volvo";
    words[4] = "Javascript";
    words[5] = "Google";
    words[6] = "Microsoft";
    words[7] = "Nvidia";


    var rand_no = Math.random();
    rand_no = Math.ceil(rand_no * words.length)-1;


    word = words[rand_no].toUpperCase();
    var foundLetters = new Array();


    var guessedLetters = new Array();
    function hideMessages() {
        document.getElementById("alreadyGuessed").style.visibility='hidden';
        document.getElementById("strike").style.visibility='hidden';
    }
    function showAlreadyGuessed() {
        document.getElementById("alreadyGuessed").style.visibility='';
    }

    function drawHangMan(numberOfStrikes) {
        var canvas = document.getElementById('hangman');
        if(canvas.getContext) {
            var ctx  = canvas.getContext('2d');
            ctx.save() ; 
            ctx.translate(45,45);
            ctx.clearRect(0,0,canvas.width,canvas.height); 
            ctx.beginPath();
            if(numberOfStrikes >= 1) ctx.fillRect(0,0,10,10);   //head
            if(numberOfStrikes >= 2) ctx.fillRect(-5,10,20,20); //body
            if(numberOfStrikes >= 3) ctx.fillRect(-20,10,20,5); //left arm
            if(numberOfStrikes >= 4) ctx.fillRect(0,10,30,5);  // right arm
            if(numberOfStrikes >= 5) ctx.fillRect(-5,30,5,10);  // left leg
            if(numberOfStrikes >= 6) ctx.fillRect(10,30,5,10);  // right leg
            
            ctx.fill();
            ctx.restore();
        }
    }

    var numberOfStrikes=0;
    function showStrike() {
        numberOfStrikes++;
        drawHangMan(numberOfStrikes);
        document.getElementById("strike").style.visibility='';
    }


    function guess(key) {
        hideMessages();
        if (guessedLetters[key]) {
            showAlreadyGuessed(); 
            return;
        }
        guessedLetters[key] = true;
        var found = false;
        for(i=0;i<word.length;++i) {
            if (word[i] == key) {
                foundLetters[i] = true;
                found=true;
            }
        }
        if(!found) showStrike();
        return found;

    }
    function draw() {
        var str='';
        for(i=0;i<word.length;++i) {
            if (foundLetters[i]) {
                str += word[i];
            } else {
                str += '_';
            }
        str += ' ';
        }
        document.getElementById('word').innerHTML = str; 
    }
    function handleKeyUp(evt) {
        var e = evt ? evt : event; 
        if (e.keyCode >= 65 && e.keyCode < (65+26) ) {
            guess(String.fromCharCode(e.keyCode));            
        }
        else {
            //alert("You entered " + e.keyCode);
        }
        draw();
    }


  </script>
 </head>
 <body onload="draw();" onkeyup="handleKeyUp(event);">
    <table>
        <tr>
            <td colspan=2>
                <span id='alreadyGuessed' style="visibility:hidden">Letter already guessed</span>
                <span id='strike' style="visibility:hidden">Strike!</span>
            </td>
        </tr>
        <tr>
            <td>
                <canvas id='hangman' width=150 height=150>
            </td>    
            <td>
                <span id='word'></span>                        
            </td>
        </tr>
    </table>
 </body>
</html>