How to Setup JavaFX Project with Gradle

apply plugin: "java"
apply plugin: "eclipse"

version = "0.1.0"

sourceCompatibility = 1.7
targetCompatibility = 1.7

defaultTasks = ["clean", "jar"]

def javafxLib = "jfxrt.jar"

def getJavaFXPath(def javafxLib) {
    def javaHome = System.env["JAVA_HOME"]
    if (javaHome == null) {
        throw new RuntimeException("JAVA_HOME environment variable must be set")
    }
    def javafxrt = "jre" + File.separator + "lib" + File.separator + javafxLib
    return new File(javaHome, javafxrt).absolutePath
}

dependencies {
    compile files(getJavaFXPath(javafxLib))
}

jar {
    // When creating a fat JAR, make sure we exclude javafx runtime
    // from the fat JAR
    dependsOn configurations.runtime
    from {
        configurations.runtime.findAll { !it.name.contains(javafxLib) }.collect { 
            it.isDirectory() ? it : zipTree(it)
        }
    }
    from sourceSets.main.allJava

    // There's no need to explicitly specify the -classpath or -cp
    // since the classpath information is already stored in the MANIFEST.MF
    manifest {
        attributes "Main-Class": "javafxapp.JavaFXApp"
        attributes "Class-Path": getJavaFXPath(javafxLib)
    }
}

Now we can easily execute the generated JAR by calling

java -jar <jar_file.jar>

How to Create Fully-Occupied-Space Controls in JavaFX

A simple example to create fully-occupied-space buttons in JavaFX.

package javafxapp;

import javafx.application.Application;
import javafx.geometry.Insets;
import javafx.scene.Node;
import javafx.scene.Scene;
import javafx.scene.control.Button;
import javafx.scene.control.ButtonBuilder;
import javafx.scene.layout.AnchorPane;
import javafx.scene.layout.AnchorPaneBuilder;
import javafx.scene.layout.BorderPane;
import javafx.scene.layout.Priority;
import javafx.scene.layout.VBox;
import javafx.scene.layout.VBoxBuilder;
import javafx.stage.Stage;

public class JavaFXApp extends Application {
    @Override
    public void start(Stage primaryStage) throws Exception {
        primaryStage.setTitle("JavaFX App");
        
        BorderPane root = new BorderPane();
        
        root.setLeft(createNode("Left"));
        root.setRight(createNode("Right"));
        root.setCenter(createNode("Center"));
        root.setTop(createNode("Top"));
        root.setBottom(createNode("Bottom"));
        
        Scene scene = new Scene(root);
        
        primaryStage.setScene(scene);
        primaryStage.show();
    }
    
    private Node createNode(String text) {
        VBox vbox = VBoxBuilder.create()
            .spacing(5)
            .padding(new Insets(10, 10, 10, 10))
            .build();

        Button btn = ButtonBuilder.create()
            .text(text)
            .build();
        
        AnchorPane anchoredPane = AnchorPaneBuilder.create()
            .children(btn)
            .style("-fx-border-style: solid;"
                + "-fx-border-width: 1;"
                + "-fx-border-color: black")
                .build();
        
        AnchorPane.setBottomAnchor(btn, 5.0);
        AnchorPane.setRightAnchor(btn, 5.0);
        AnchorPane.setTopAnchor(btn, 5.0);
        AnchorPane.setLeftAnchor(btn, 5.0);
        
        VBox.setVgrow(anchoredPane, Priority.ALWAYS);
        vbox.getChildren().addAll(anchoredPane);
        
        return vbox;
    }
    
    public static void main(String[] args) {
        launch(args);
    }
}

Getting Started with Gradle Multiproject

Project structure:

.
├── api
│   └── src
│       └── main
│           └── java
│               └── api
│                   └── API.java
├── build.gradle
├── cli
│   └── src
│       └── main
│           └── java
│               └── cli
│                   └── CLI.java
├── core
│   └── src
│       └── main
│           └── java
│               └── core
│                   └── Core.java
├── gui
│   └── src
│       └── main
│           └── java
│               └── gui
│                   └── GUI.java
└── settings.gradle

In this project, core depends on api, cli depends on core, and gui depends on core.

settings.gradle

include ":api", ":core", ":gui", ":cli"

build.gradle

def distDir = "dist"

defaultTasks = ["clean", "jar", "dist"]

subprojects {
    apply plugin: "java"
    apply plugin: "eclipse"
    sourceCompatibility = 1.7
    targetCompatibility = 1.7
    version = "0.1.0"
}

project(":core") {
    dependencies {
        compile project(":api")
    }
}

project(":gui") {
    dependencies {
        compile project(":core")
    }
}

project(":cli") {
    dependencies {
        compile project(":core")
    }
}

task clean << {
    delete distDir
}

task dist << {
    def d = mkdir(distDir)
    subprojects.each { subproject ->
        subproject.tasks.jar.each { archiveTask ->
            copy {
                from archiveTask.archivePath
                into d
            }
        }
    }
}

The build.gradle shown above has a dist task that will pull all the generated jars into dist directory.

How to Include Source Files into JAR in Gradle

Project structure:

├── build.gradle
└── src
    └── main
        └── java
            └── test
                └── Test.java

build.gradle

apply plugin: "java"

defaultTasks = ["clean", "jar"]

jar {
    from sourceSets.main.allJava
}

How to Solve Cutting Rod Problem

This solution uses memoization.

#!/usr/bin/env python

def find_max(list_tuples):
    if len(list_tuples) == 0:
        return None
    maximum = list_tuples[0]
    for i in xrange(1, len(list_tuples)):
        if maximum[0] < list_tuples[i][0]:
            maximum = list_tuples[i]
    return maximum

memo = {}
def cutting_rod(prices, ncuts):
    if ncuts == 0:
        return (0, [])
    if ncuts in memo:
        return memo[ncuts]
    tmp = []
    for i in xrange(0, ncuts):
        r = cutting_rod(prices, ncuts-i-1)
        new_list = list(r[1])
        new_list.append(i)
        value = prices[i] + r[0]
        tmp.append((value, new_list))
    result = find_max(tmp)
    memo[ncuts] = result
    return result

if __name__ == '__main__':
    p = [2, 5, 6, 7]
    r = cutting_rod(p, len(p))
    print "Prices:", p
    print "Optimal value:", r[0]
    print "Indices:", r[1]
    print "Cuts:", [p[x] for x in r[1]]

Output:

Prices: [2, 5, 6, 7]
Optimal value: 10
Indices: [1, 1]
Cuts: [5, 5]

How to Solve Producer Consumer Problem in Java

Change the preJava5 flag to true if you are running Java 4 and below. Change preJava5 flag to true if you are running Java 5 and above.

import java.util.LinkedList;
import java.util.Random;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.LinkedBlockingQueue;

public class ProducerConsumer {
    public static final int MAX_SIZE = 5;
    public static final int SLEEP_TIME = 5 * 100;
    
    public static class PreJava5 {
        public static class Consumer {
            private Random random = new Random();
            
            public void consume(LinkedList<Integer> queue) {
                while (true) {
                    try {
                        synchronized (queue) {
                            if (queue.isEmpty()) {
                                System.out.println("Queue is empty");
                                queue.wait();
                            } else {
                                System.out.println("Consuming something, size="
                                    + queue.size());
                                queue.removeFirst();
                                queue.notifyAll();
                            }
                        }
                        // to simulate performing some busy tasks
                        Thread.sleep(random.nextInt(SLEEP_TIME));
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                }
            }
        }
        
        public static class Producer {
            private Random random = new Random();
            
            public void produce(LinkedList<Integer> queue) {
                while (true) {
                    try {
                        synchronized (queue) {
                            if (queue.size() == MAX_SIZE) {
                                System.out.println("Queue is full");
                                queue.wait();
                            } else {
                                System.out.println("Producing something, size="
                                    + queue.size());
                                queue.addLast(0);
                                queue.notifyAll();
                            }
                        }
                        // to simulate performing some busy tasks
                        Thread.sleep(random.nextInt(SLEEP_TIME));
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                }
            }
        }
    }
    
    public static class Java5AndAbove {
        public static class Consumer {
            private Random random = new Random();
            
            public void consume(BlockingQueue<Integer> queue) {
                while (true) {
                    try {
                        System.out.println("Consuming something, size="
                            + queue.size());
                        // will block if the queue is empty
                        queue.take();
                        // to simulate performing some busy tasks
                        Thread.sleep(random.nextInt(SLEEP_TIME));
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                }
            }
        }
        
        public static class Producer {
            private Random random = new Random();
            
            public void produce(BlockingQueue<Integer> queue) {
                while (true) {
                    try {
                        System.out.println("Producing something, size="
                            + queue.size());
                        // will block if the queue is full
                        queue.put(0);
                        // to simulate performing some busy tasks
                        Thread.sleep(random.nextInt(SLEEP_TIME));
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) {
        boolean preJava5 = false;
        
        if (preJava5) {
            final LinkedList<Integer> queue = new LinkedList<>();
            final PreJava5.Producer producer = new PreJava5.Producer();
            final PreJava5.Consumer consumer = new PreJava5.Consumer();
            Thread t1 = new Thread(new Runnable() {
                @Override
                public void run() {
                    producer.produce(queue);
                }
            });
            Thread t2 = new Thread(new Runnable() {
                @Override
                public void run() {
                    consumer.consume(queue);
                }
            });
            t1.start();
            t2.start();
        } else {
            final BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(MAX_SIZE);
            final Java5AndAbove.Producer producer = new Java5AndAbove.Producer();
            final Java5AndAbove.Consumer consumer = new Java5AndAbove.Consumer();
            
            ExecutorService es1 = Executors.newSingleThreadExecutor();
            ExecutorService es2 = Executors.newSingleThreadExecutor();
            
            es1.execute(new Runnable() {
                @Override
                public void run() {
                    producer.produce(queue);
                }
            });
            
            es2.execute(new Runnable() {
                @Override
                public void run() {
                    consumer.consume(queue);
                }
            });
        }
    }
}

How to Implement Matrix Multiplication

public class Matrix {
    private static int[][] multiply(int[][] a, int[][] b) {
        if (a[0].length != b.length) {
            throw new IllegalArgumentException(
                "A(" + a.length + "x" + a[0].length + ") did not match " +
                "B(" + b.length + "x" + b[0].length + ")");
        }
        
        int[][] c = new int[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                for (int k = 0; k < a[0].length; k++) {
                    c[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return c;
    }
    
    private static void print(int[][] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                if (a[i][j] < 10) {
                    System.out.print(" ");
                } 
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        int[][] a = new int[2][3];
        int value = 1;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                a[i][j] = value++;
            }
        }
        System.out.println("Matrix A:");
        print(a);
        
        int[][] b = new int[3][2];
        value = 1;
        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[i].length; j++) {
                b[i][j] = value++;
            }
        }
        System.out.println("Matrix B:");
        print(b);
        
        
        int[][] c = multiply(a, b);
        System.out.println("Matrix C:");
        print(c);
    }
}

How to Create a Binary Search Tree from a Sorted Array

import java.util.LinkedList;

public class BST {
    static class Node {
        private int value;
        private Node leftChild;
        private Node rightChild;
        
        public Node(int value) {
            this.value = value;
        }
    }
    
    static enum ChildType {
        LEFT, RIGHT, ROOT
    }
    
    private Node root;
    
    public BST(int[] sortedArray) {
        int lo = 0;
        int hi = sortedArray.length;
        int mid = (lo + hi) / 2;
        root = new Node(sortedArray[mid]);
        build(root, ChildType.ROOT, sortedArray, lo, hi);
    }
    
    private void build(Node node, ChildType type, int[] array, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = (lo + hi) / 2;
        Node n = node;
        if (type == ChildType.LEFT) {
            node.leftChild = new Node(array[mid]);
            n = node.leftChild;
        } else if (type == ChildType.RIGHT) {
            node.rightChild = new Node(array[mid]);
            n = node.rightChild;
        }
        build(n, ChildType.LEFT, array, lo, mid);
        build(n, ChildType.RIGHT, array, mid+1, hi);
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        LinkedList<Node> nodes = new LinkedList<>();
        nodes.add(root);
        while (!nodes.isEmpty()) {
            Node n = nodes.removeFirst();
            if (n.leftChild != null) {
                sb.append(n.leftChild.value + " -- left --> " + n.value + " \n");
                nodes.add(n.leftChild);
            }
            if (n.rightChild != null) {
                sb.append(n.rightChild.value + " -- right --> " + n.value + " \n");
                nodes.add(n.rightChild);
            }
        }
        return sb.toString();
    }
    
    public static void main(String[] args) {
        int[] sortedArray = new int[7];
        for (int i = 0; i < sortedArray.length; i++) {
            sortedArray[i] = i;
        }
        BST bst = new BST(sortedArray);
        System.out.println(bst);
    }
}

How to Implement tail -f in Java

package jtail;

import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;

public class JTail {
    private static final long SLEEP_TIME = 500L;
    
    public static void open(File file) {
        RandomAccessFile raf = null;
        long lastFilePointer = 0;
        try {
            raf = new RandomAccessFile(file, "r");
            while (true) {
                if (raf.length() == lastFilePointer) {
                    // Don't forget to close the previous file handle
                    raf.close();
                    Thread.sleep(SLEEP_TIME);
                    // Wait till the file exists before opening it
                    while (!file.exists()) {}
                    raf = new RandomAccessFile(file, "r");
                    raf.seek(lastFilePointer);
                } else {
                    byte[] bytes = new byte[4096];
                    int bytesRead;
                    while ((bytesRead = raf.read(bytes, 0, bytes.length)) != -1) {
                        System.out.print(new String(bytes, 0, bytesRead));
                    }
                    lastFilePointer = raf.getFilePointer();
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            if (raf != null) {
                try {
                    raf.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }
    
    private static void printUsage() {
        System.out.println("Usage: java -cp <classpath> " +
            JTail.class.getName() + " <file>");
    }
    
    private static boolean validateArgs(String[] args) {
        if (args.length != 1) {
            printUsage();
            return false;
        }
        File file = new File(args[0]);
        if (!file.isFile()) {
            System.err.println("Error: " + file.getAbsolutePath() +
                " does not exist or is not a file");
            return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        if (!validateArgs(args)) {
            System.exit(1);
        }
        JTail.open(new File(args[0]));
    }
}

How to Solve Clock Puzzle

While playing Final Fantasy XIII-2, I came across an interesting puzzle. The puzzle is as follows.

Given n-numbers in a circle that form numbers similar to the ones in a clock. Like a clock, it has two pointers (e.g. the hour and the minute) that move to the left and to the right. Initially both pointers are pointing to the same number and we are allowed to choose any number to begin with. For any number that we pick, the two pointers will move x steps to the left and x steps to the right where x is the value shown in the number that we pick. For each number that we pick, the number will disappear and we cannot pick that number again. The next step is to pick any number that the left or right pointer is pointing to. The win this puzzle, we need to perform n-moves that will eliminate all the numbers in the clock. If both pointers are pointing to the numbers that have disappeared and there are still numbers that have not disappeared, we are lost.

Example:

      2
    3   1 
  3       3
    2   2
      2

We pick 2 (north). Number 2 (north) will disappear. The left pointer will move 2 steps to the left and pointing to 3 (west). The right pointer will move to 2 steps to the right and pointing to 3 (east)

We pick 3 (west). Number 3 (west) will disappear. The left pointer will move 3 steps to the left and pointing to 2 (southeast). The right pointer will move 3 steps to the right pointing to 1 (northeast)

We pick 2 (southeast). Number 2 (southeast) will disappear. The left pointer wil move 2 steps to the left and pointing to 1 (northeast). The right pointer will move 2 steps to the right pointing to 2 (southwest)

We keep picking a number that either a left or right pointer is pointing to and we need to make sure that if there are still some numbers in the clock, both left and right pointers must not point to the numbers that have disappeared. Once all the numbers have disappeared, we have won the puzzle

One possible solution.

 1. Init  --> 2
 2. Left  --> 3
 3. Left  --> 2
 4. Left  --> 1
 5. Right --> 3
 6. Right --> 2
 7. Right --> 3
 8. Left  --> 2

My solution in Java.

import java.util.ArrayList;
import java.util.List;

public class ClockPuzzle {
    private static class Number implements Cloneable {
        private boolean marked;
        private final int value;
        
        public Number(int value) {
            this.value = value;
        }
        
        public Number(int value, boolean marked) {
            this.value = value;
            this.marked = marked;
        }
        
        @Override
        protected Object clone() {
            return new Number(value, marked);
        }
    }
    
    private static enum Direction {
        INIT("Init "),
        LEFT("Left "),
        RIGHT("Right");
        
        private String str;
        
        private Direction(String str) {
            this.str = str;
        }
        
        @Override
        public String toString() {
            return str;
        }
    }
    
    private final Number[] numbers;
    private final int size;
    
    public ClockPuzzle(int... values) {
        numbers = new Number[values.length];
        for (int i = 0; i < values.length; i++) {
            numbers[i] = new Number(values[i]);
        }
        size = values.length;
    }
    
    public void solve(int index) {
        List<String> result = new ArrayList<>();
        Number[] newNumbers = copy(numbers);
        result.add(createResult(Direction.INIT, index, newNumbers[index].value));
        solve(newNumbers, index, result);
    }
    
    private void solve(Number[] numbers, int index, List<String> result) {
        Number e = numbers[index];
        if (e.marked) {
            return;
        }
        e.marked = true;
        if (allMarked(numbers)) {
            printResult(result);
        } else {
            // the left pointer
            int leftIndex = getActualIndex(index-e.value, numbers.length);
            solve(leftIndex, Direction.LEFT, numbers, result);
            
            // the right pointer
            int rightIndex = getActualIndex(index+e.value, numbers.length);
            solve(rightIndex, Direction.RIGHT, numbers, result);
        }
    }
    
    private void solve(int index, Direction direction, Number[] numbers, List<String> result) {
        Number[] newNumbers = copy(numbers);
        List<String> newResult = copy(result);
        newResult.add(createResult(direction, index, newNumbers[index].value));
        solve(newNumbers, index, newResult);
    }
    
    private Number[] copy(Number[] numbers) {
        Number[] newNumbers = new Number[numbers.length];
        for (int i = 0; i < newNumbers.length; i++) {
            newNumbers[i] = (Number) numbers[i].clone();
        }
        return newNumbers;
    }
    
    private String createResult(Direction direction, int index, int value) {
        return direction.toString() + " --> " + value + " (index: " + index + ")";
    }
    private List<String> copy(List<String> list) {
        List<String> newList = new ArrayList<>();
        for (String s : list) {
            newList.add(s);
        }
        return newList;
    }
    
    private void printHeader() {
        for (int i = 0; i < 50; i++) {
            System.out.print("=");
        }
        System.out.println();
    }
    
    private void printResult(List<String> result) {
        printHeader();
        int i = 1;
        for (String r : result) {
            if (i < 10) {
                System.out.println(" " + i++ + " " + r);
            } else {
                System.out.println(i++ + " " + r);
            }
        }
        printHeader();
    }
    
    private boolean allMarked(Number[] numbers) {
        for (Number n : numbers) {
            if (!n.marked) {
                return false;
            }
        }
        return true;
    }
    
    private int getActualIndex(int i, int arraySize) {
        if (i >= arraySize) {
            return i - arraySize;
        }
        if (i < 0) {
            return arraySize + i;
        }
        return i;
    }
    
    public static void main(String[] args) {
        ClockPuzzle clockPuzzle = new ClockPuzzle(2, 1, 3, 2, 2, 2, 3, 3);
        for (int i = 0; i < clockPuzzle.size; i++) {
            clockPuzzle.solve(i);
        }
    }
}

How to Get the Index of an Element in a Circular Buffer

Problem: Get the index of a particular element in a circular buffer, e.g.

Array: 7 8 9 0 1 2 3 4 5 6
search(0) --> index 3
search(6) --> index 9

public class CircularBinarySearch {
    // return -1 if not found
    private static int getIndex(int[] array, int value) {
        int minIdx = findMinIndex(array);
        return binarySearch(array, value, minIdx, array.length-1+minIdx, minIdx);
    }
    
    private static int binarySearch(int[] array, int value, int lo, int hi, int minIdx) {
        if (lo > hi) {
            return -1;
        }
        int mid = (lo + hi) / 2;
        int midIdx = getRealIndex(array.length, mid, minIdx);
        if (array[midIdx] == value) {
            return midIdx;
        } else if (array[midIdx] > value) {
            return binarySearch(array, value, lo, mid-1, minIdx);
        } else if (array[midIdx] < value) {
            return binarySearch(array, value, mid+1, hi, minIdx);
        }
        return -1;
    }
    
    private static int getRealIndex(int arrayLength, int idx, int minIdx) {
        if (idx >= arrayLength) {
            return idx - arrayLength;
        }
        return idx;
    }
    
    private static int findMinIndex(int[] array) {
        int minIdx = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[minIdx]) {
                minIdx = i;
            }
        }
        return minIdx;
    }
    
    public static void main(String[] args) {
        int[] array = new int[10];
        array[0] = 7;
        array[1] = 8;
        array[2] = 9;
        array[3] = 0;
        array[4] = 1;
        array[5] = 2;
        array[6] = 3;
        array[7] = 4;
        array[8] = 5;
        array[9] = 6;
        
        // verify it
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i] + " --> " + getIndex(array, array[i]));
        }
        System.out.print("120 --> " + getIndex(array, 120));
    }
}

How to Create an Executable Zip File

Python has the ability to execute a zip file that contains Python files. This makes it very handy to create an executable zip file. Here's an example how to do it.

test.py

#!/usr/bin/env python

def say_something(): print "Hello World"
def main(): say_something()

__main__.py

#!/usr/bin/env python

import test

if __name__ == "__main__": test.main()

The __main__.py must be in the root directory of the zip file.

Zip all the Python files so that it looks like below. We don't need to use .zip extension, we can name it anything we want.

test.zip
|-- __main__.py
`-- test.py

To execute it:

python test.zip

and you will see the output as

Hello World

How to Capture StdOut/StdErr in Java

package test;

import java.io.BufferedReader;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PipedInputStream;
import java.io.PipedOutputStream;
import java.io.PrintStream;
import java.io.StringWriter;

public class Main {
    public static interface Function {
        void execute();
    }
    
    public static String capture1(PrintStream ps, Function func)
        throws IOException {
        PipedOutputStream pos = new PipedOutputStream();
        BufferedReader br = new BufferedReader(new InputStreamReader(
            new PipedInputStream(pos)));
        StringWriter sw = new StringWriter();
        String output = null;
        try {
            PrintStream old = ps;
            System.setOut(new PrintStream(pos));

            func.execute();
            System.out.flush();

            pos.close();

            System.setOut(old);

            int charsRead;
            char[] cbuf = new char[4096];
            while ((charsRead = br.read(cbuf, 0, cbuf.length)) != -1) {
                sw.write(cbuf, 0, charsRead);
            }
            output = sw.toString();
        }
        finally {
            br.close();
            sw.close();
        }
        return output;
    }
    
    public static String capture2(PrintStream ps, Function func)
        throws IOException {
        String output = null;
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        try {
            PrintStream old = System.out;
            System.setOut(new PrintStream(baos));

            func.execute();
            System.out.flush();

            System.setOut(old);

            output = baos.toString();
        }
        finally {
            baos.close();
        }
        return output;
    }
    
    public static void main(String[] args) throws Exception {
        String output = capture1(System.out, new Function() {
            @Override
            public void execute() {
                System.out.println("Hello World");
                System.out.println("Bye World");
            }
        });
        System.out.println(output);
        
        
        output = capture2(System.out, new Function() {
            @Override
            public void execute() {
                System.out.println("Hello World");
                System.out.println("Bye World");
            }
        });
        System.out.println(output);
    }
}

How to Parse Java Source Code using Oracle/Sun Java Compiler API

NOTE: using compiler API (com.sun.*) packages can be dangerous since they are supposed to be internal packages.

package test;

public class Foo {
    public String getSomething() {
        return "Hello World";
    }
}

package test;

import javax.tools.JavaCompiler;
import javax.tools.JavaFileObject;
import javax.tools.StandardJavaFileManager;
import javax.tools.ToolProvider;

import com.sun.source.tree.ClassTree;
import com.sun.source.tree.CompilationUnitTree;
import com.sun.source.tree.MethodTree;
import com.sun.source.tree.ReturnTree;
import com.sun.source.tree.StatementTree;
import com.sun.source.tree.Tree;
import com.sun.source.util.JavacTask;
import com.sun.source.util.SimpleTreeVisitor;

public class Test {
    public static void main(String[] args) throws Exception {
        JavaCompiler compiler = ToolProvider.getSystemJavaCompiler();
        StandardJavaFileManager fileManager = compiler.getStandardFileManager(null, null, null);
        Iterable<? extends JavaFileObject> fileObjects = fileManager
            .getJavaFileObjects("test/Foo.java");
        JavacTask javac = (JavacTask) compiler.getTask(null, fileManager, null, null, null,
            fileObjects);
        Iterable<? extends CompilationUnitTree> trees = javac.parse();
        for (CompilationUnitTree tree : trees) {
            tree.accept(new CompilationUnitVisitor(), null);
        }
    }
    
    static class CompilationUnitVisitor extends SimpleTreeVisitor<Void, Void> {
        @Override
        public Void visitCompilationUnit(CompilationUnitTree cut, Void p) {
            System.out.println("Package name: " + cut.getPackageName());
            for (Tree t : cut.getTypeDecls()) {
                if (t instanceof ClassTree) {
                    ClassTree ct = (ClassTree) t;
                    ct.accept(new ClassVisitor(), null);
                }
            }
            return super.visitCompilationUnit(cut, p);
        }
    }
    
    static class ClassVisitor extends SimpleTreeVisitor<Void, Void> {
        @Override
        public Void visitClass(ClassTree ct, Void p) {
            System.out.println("Class name: " + ct.getSimpleName());
            for (Tree t : ct.getMembers()) {
                MethodTree mt = (MethodTree) t;
                mt.accept(new MethodVisitor(), null);
            }
            return super.visitClass(ct, p);
        }
    }
    
    static class MethodVisitor extends SimpleTreeVisitor<Void, Void> {
        @Override
        public Void visitMethod(MethodTree mt, Void p) {
            System.out.println("Method name: " + mt.getName());
            for (StatementTree st : mt.getBody().getStatements()) {
                if (st instanceof ReturnTree) {
                    ReturnTree rt = (ReturnTree) st;
                    rt.accept(new ReturnTreeVisitor(), null);
                }
            }
            return super.visitMethod(mt, p);
        }
    }
    
    static class ReturnTreeVisitor extends SimpleTreeVisitor<Void, Void> {
        @Override
        public Void visitReturn(ReturnTree rt, Void p) {
            System.out.println("Return statement: " + rt.getExpression());
            return super.visitReturn(rt, p);
        }
    }
}

How to Solve 3-Sum Problem

Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?

package main

import (
    "fmt"
    "sort"
)

func ThreeSum(numbers []int) {
    for i := 0; i < len(numbers); i++ {
        for j := 0; j < len(numbers); j++ {
            nSearch := -(numbers[i] + numbers[j])
            index := sort.SearchInts(numbers, nSearch)
            if index < len(numbers) && numbers[index] == nSearch {
                fmt.Println(numbers[i], numbers[j], numbers[index])
            }
        }
    }
}

func main() {
    numbers := []int{-40, 30, -10, 50, 20}
    sortedNumbers := sort.IntSlice(numbers)
    sort.Sort(sortedNumbers)
    ThreeSum(sortedNumbers)
}

A Tool to Escape HTML Characters in Go

I created a handy tool to escape HTML characters, especially for pasting code in a blog like this.

Usage: ./escapehtml  [dest_dir]

If the source is a directory, the tool will scan the whole directory and escape each file found and output the escaped string to stdout (if dest_dir isn't specified) or to a file (if dest_dir is specified).

escapehtml.go

package main

import (
    "fmt"
    "os"
    "errors"
    "path/filepath"
    "io/ioutil"
    "html"
    "strings"
)

func printUsage() {
    fmt.Println("Usage:", os.Args[0],
        "<source_file/source_dir>", "[dest_dir]")
}

func errorMessage(s string) string {
    return "Error: " + s
}

type fileType struct {
    directory bool
    regularFile bool
}

func fileExists(path string) (*fileType, error) {
    file, err := os.Open(path)
    if err != nil {
        if os.IsNotExist(err) {
            return nil, errors.New(
                errorMessage(path + " does not exist"))
        }
    }
    defer file.Close()
    fileInfo, err := file.Stat()
    if err != nil {
        return nil, err
    }
    if fileInfo.IsDir() {
        return &fileType{directory: true}, nil
    }
    return &fileType{regularFile: true}, nil
}

func validateArgs() (bool, error) {
    if len(os.Args) != 2 && len(os.Args) != 3 {
        return false, nil
    }

    if _, err := fileExists(os.Args[1]); err != nil {
        return false, err
    }
    if len(os.Args) == 3 {
        ft, _ := fileExists(os.Args[2])
        if ft != nil && !ft.directory {
            return false, errors.New(
                errorMessage(os.Args[2] + " must be a directory"))
        }
    }
    return true, nil
}

func printHeader(header string) {
    fmt.Println(strings.Repeat("=", 72))
    fmt.Println(header)
    fmt.Println(strings.Repeat("=", 72))
}

func escapeHTML(srcPath string, destPath string) {
    filepath.Walk(srcPath,
        func(path string, info os.FileInfo, err error) error {
            if info.IsDir() {
                return nil
            }

            b, err := ioutil.ReadFile(path)
            if err != nil {
                return nil
            }

            escapedString := html.EscapeString(string(b))
            if destPath == "" {
                printHeader(path)
                fmt.Println(escapedString)
            } else {
                if ft, _ := fileExists(destPath); ft == nil {
                    if e := os.MkdirAll(destPath, 0775); e != nil {
                        errors.New("Unable to create directory: " +
                            destPath)
                    } else {
                        fmt.Println("Creating directory: " + destPath)
                    }
                }
                newPath := filepath.Join(destPath,
                    filepath.Base(path) + ".txt")
                fmt.Println("Creating", newPath)
                e := ioutil.WriteFile(newPath, []byte(escapedString), 0644)
                if e != nil {
                    return e
                }
            }
            return nil
        })
}

func main() {
    if valid, err := validateArgs(); !valid {
        if err != nil {
            fmt.Println(err)
            os.Exit(1)
        } else {
            printUsage()
            os.Exit(1)
        }
    }

    srcPath := os.Args[1]
    destPath := ""
    if len(os.Args) == 3 {
        destPath = os.Args[2]
    }
    escapeHTML(srcPath, destPath)
}

To build it, just type

go build escapehtml.go

How to Implement Union Find Algorithms

package unionfind

type UnionFind interface {
    Find(int, int) bool
    Union(int, int)
}
//================================================
type QuickFind struct {
    Nodes []int
}

func (qf *QuickFind) Find(x, y int) bool {
    return qf.Nodes[x] == qf.Nodes[y]
}

func (qf *QuickFind) Union(x, y int) {
    tmp := qf.Nodes[x]
    qf.Nodes[x] = qf.Nodes[y]
    for i := 0; i < len(qf.Nodes); i++ {
        if qf.Nodes[i] == tmp {
            qf.Nodes[i] = qf.Nodes[y]
        }
    }
}
//================================================
type QuickUnion struct {
    Nodes []int
}

func (qu *QuickUnion) Find(x, y int) bool {
    return qu.root(x) == qu.root(y)
}

func (qu *QuickUnion) Union(x, y int) {
    rootX := qu.root(x)
    rootY := qu.root(y)
    qu.Nodes[rootX] = qu.Nodes[rootY]
}

func (qu *QuickUnion) root(x int) int {
    for qu.Nodes[x] != x {
        x = qu.Nodes[x]
    }
    return x
}
//================================================
type WeightedQuickUnion struct {
    Nodes []int
    sizes []int
}

func (wqu *WeightedQuickUnion) Find(x, y int) bool {
    return wqu.root(x) == wqu.root(y)
}

func (wqu *WeightedQuickUnion) Union(x, y int) {
    rootX := wqu.root(x)
    rootY := wqu.root(y)
    if wqu.sizes[rootX] < wqu.sizes[rootY] {
        wqu.Nodes[rootX] = wqu.Nodes[rootY]
        wqu.sizes[rootY] += wqu.sizes[rootX]
    } else {
        wqu.Nodes[rootY] = wqu.Nodes[rootX]
        wqu.sizes[rootX] += wqu.sizes[rootY]
    }
}

func (wqu *WeightedQuickUnion) root(x int) int {
    for wqu.Nodes[x] != x {
        x = wqu.Nodes[x]
    }
    return x
}

My .vimrc

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

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

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.

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/..")

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")

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"

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

How to Pass Some Arguments to BaseHTTPRequestHandler in Python

Let's say we have an argument, which is a function that we want to pass to BaseHTTRequestHandler to handle a request and return an appropriate response based the request. By looking at HTTPServer class definition, it may not be really obvious how to do it.

It's actually pretty simple and straightforward how to do it. First we need to subclass HTTPServer and override the constructor that takes in our own new arguments. From the RequestHandler class, there'll be a property named server that gives us access to the HTTPServer instance. And since we've subclassed HTTPServer class, we can define as many properties as we want that those properties will be accessible in the server property of the HTTPRequestHandler. The example is shown below.

#!/usr/bin/env python

import logging
from BaseHTTPServer import HTTPServer
from BaseHTTPServer import BaseHTTPRequestHandler

class HttpServerHandler(BaseHTTPRequestHandler):
    def do_POST(self):
        content_length = int(self.headers.getheader("Content-Length"))
        request = self.rfile.read(content_length)
        logging.info("Request: %s" % request)
        # BaseHTTPRequestHandler has a property called server and because
        # we create MyHTTPServer, it has a handler property
        response = self.server.handler(request)
        logging.info("Response: %s" % response)
        self.send_response(200)
        self.end_headers()
        self.wfile.write(response)
    
class MyHTTPServer(HTTPServer):
    """this class is necessary to allow passing custom request handler into
       the RequestHandlerClass"""
    def __init__(self, server_address, RequestHandlerClass, handler):
        HTTPServer.__init__(self, server_address, RequestHandlerClass)
        self.handler = handler
            
class HttpServer:
    def __init__(self, name, host, port, handler):
        self.name = name
        self.host = host
        self.port = port
        self.handler = handler
        self.server = None
        
    def start(self):
        logging.info('Starting %s at %s:%d' % (self.name, self.host, self.port))
        # we need use MyHttpServer here
        self.server = MyHTTPServer((self.host, self.port), HttpServerHandler,
                                   self.handler)
        self.server.serve_forever()
    
    def stop(self):
        if self.server:
            logging.info('Stopping %s at %s:%d' % (self.name, self.host,
                                                   self.port))
            self.server.shutdown()

def server_handler(request):
    if request == "foo":
        return "bar"
    elif request == "bar":
        return "foo"
    else:
        return "foobar"

if __name__ == "__main__":
    logging.basicConfig(format='%(asctime)s [%(levelname)s] %(message)s', 
                        level=logging.INFO)
    server = HttpServer("test server", "localhost", 9999, server_handler)
    server.start()

How to Implement DFS and BFS in Python

#!/usr/bin/env python

class Graph(object):
    def __init__(self):
        # the key is the vertex, the value is the list of adjacent vertices
        self.adjacents = {}
        self.nedges = 0

    def num_vertices(self):
        return self.adjacents.keys()

    def num_edges(self):
        return self.nedges

    def add_edge(self, v, w):
        if v not in self.adjacents: self.adjacents[v] = []
        self.adjacents[v].append(w)
        if w not in self.adjacents: self.adjacents[w] = []
        self.adjacents[w].append(v)
        self.nedges += 1

    def adjacent(self, v):
        return self.adjacents[v]

class DepthFirstSearch(object):
    def __init__(self, graph, start):
        self.count = 0
        self.markeddict = {}
        self.edge_to = {}
        self.start = start
        self._dfs(graph, start)

    def _dfs(self, graph, vertex):
        self.markeddict[vertex] = True
        self.count += 1
        for v in graph.adjacent(vertex):
            if not self.marked(v):
                self.edge_to[v] = vertex
                self._dfs(graph, v)

    def marked(self, vertex):
        return vertex in self.markeddict

    def has_path_to(self, vertex):
        return self.marked(vertex)

    def path_to(self, vertex):
        if not self.has_path_to(vertex): return None
        path = []
        path.append(vertex)
        while vertex != self.start:
            vertex = self.edge_to[vertex]
            path.append(vertex)
        
        path.reverse()
        return path

class BreadthFirstSearch(object):
    def __init__(self, graph, start):
        self.count = 0
        self.markeddict = {}
        self.edge_to = {}
        self.start = start
        self._bfs(graph, start)

    def _bfs(self, graph, vertex):
        self.markeddict[vertex] = True
        self.count += 1
        q = []
        q.append(vertex)
        while q:
            key = q.pop(0)
            for v in graph.adjacent(key):
                if not self.marked(v):
                    q.append(v)
                    self.count += 1
                    self.markeddict[v] = True
                    self.edge_to[v] = key

    def marked(self, vertex):
        return vertex in self.markeddict

    def has_path_to(self, vertex):
        return self.marked(vertex)

    def path_to(self, vertex):
        if not self.has_path_to(vertex): return None
        path = []
        path.append(vertex)
        while vertex != self.start:
            vertex = self.edge_to[vertex]
            path.append(vertex)
        
        path.reverse()
        return path

if __name__ == "__main__":
    # key is the vertex and value is the list of adjacent vertices
    graph = Graph()
    
    graph.add_edge("0", "2")
    graph.add_edge("3", "5")
    graph.add_edge("3", "4")
    graph.add_edge("0", "1")
    graph.add_edge("1", "2")
    graph.add_edge("2", "3")
    graph.add_edge("2", "4")
    graph.add_edge("0", "5")

    dfs = DepthFirstSearch(graph, "0")
    assert "0" == "-".join(dfs.path_to("0"))
    assert "0-2-1" == "-".join(dfs.path_to("1"))
    assert "0-2" == "-".join(dfs.path_to("2"))
    assert "0-2-3" == "-".join(dfs.path_to("3"))
    assert "0-2-3-4" == "-".join(dfs.path_to("4"))
    assert "0-2-3-5" == "-".join(dfs.path_to("5"))
    assert 6 == dfs.count
    
    bfs = BreadthFirstSearch(graph, "0")
    assert "0" == "-".join(bfs.path_to("0"))
    assert "0-1" == "-".join(bfs.path_to("1"))
    assert "0-2" == "-".join(bfs.path_to("2"))
    assert "0-2-3" == "-".join(bfs.path_to("3"))
    assert "0-2-4" == "-".join(bfs.path_to("4"))
    assert "0-5" == "-".join(bfs.path_to("5"))
    assert 6 == bfs.count

How to Reverse Order of Words in Python

#!/usr/bin/env python

def reverse_words(string):
    reverse(string, 0, len(string)-1)
    
    prev_space_index = 0
    for i in xrange(0, len(string)):
        if string[i] == " ":
            reverse(string, prev_space_index, i-1)
            prev_space_index = i + 1

    # the last word hasn't been reversed    
    if prev_space_index < len(string):
        reverse(string, prev_space_index, len(string)-1)

def reverse(string, beg, end):
    i = beg
    j = end
#    print string[beg:end]
    while i < j:
        string[i], string[j] = string[j], string[i]
        i += 1
        j -= 1
    
if __name__ == "__main__":
    l = list("my first name is foo and my last name is bar")
    reverse_words(l)
    
    assert "bar is name last my and foo is name first my" == "".join(l)    

How to Implement Permutations in Python

#!/usr/bin/env python

def permutate(l, n, nl):
    if n == 0:
        if len(nl) != len(set(nl)): return
        nl1 = []
        for i in nl: nl1.append(l[i])
        print nl1 
    else:
        n = n - 1 
        nl1 = [x for x in nl] 
        for i in xrange(0, len(l)):
            nl = [x for x in nl1]
            nl.append(i)
            permutate(l, n, nl) 
            del nl[:]

def permutations(l):
    permutate(l, len(l), [])

if __name__ == "__main__":
    permutations([1, 2, 3, 4])

Search Algorithms in Python

Below are some popular implementations of searching algorithms.

#!/usr/bin/env python

class SequentialSearchDict(object):
    class Node(object):
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.next = None
    
    def __init__(self):
        self.first = None
        self.size = 0
       
    def put(self, key, value):
        self._put(key, value)
    
    def _put(self, key, value):
        n = self._get(key)
        if n:
            n.value = value
            return 0
        else:
            # add the new node into the first
            tmp = self.first
            self.first = SequentialSearchDict.Node(key, value)
            self.first.next = tmp
            self.size += 1
            return 1
   
    def _get(self, key):
        n = self.first
        while n:
            if n.key == key: return n
            n = n.next
        return None
   
    def get(self, key):
        n = self._get(key)
        if n: return n.value
        return n
   
class BinarySearchDict(object):
    class Node(object):
        def __init__(self, key, value):
            self.key = key
            self.value = value
    
    def __init__(self):
        self.size = 0
        self.l = []
       
    def put(self, key, value):
        # the elements must be kept sorted for the binary search to work
        index = self._get(key)
        if index < 0:
            self.l.append(BinarySearchDict.Node(key, value))
            self.size += 1
            return
        n = self.l[index]
        if n.key == key:
            n.value = value
        else:
            self.l.append(BinarySearchDict.Node(key, value))
            # shift all the elements to the right
            if (index+1) < (len(self.l)-1):
                for i in xrange(len(self.l)-1, index, -1):
                    self.l[i] = self.l[i-1]
            self.size += 1
           
    def get(self, key):
        # search using binary search
        index = self._get(key)
        if index < 0: return None
        n = self.l[index]
        if n.key == key: return n.value
        return None
       
    def _get(self, key):
        lo = 0
        hi = len(self.l) - 1
        mid = (lo + hi) / 2
        while lo <= mid and hi >= mid:
            if self.l[mid].key > key:
                hi = mid - 1
                mid = (lo + hi) / 2
            elif self.l[mid].key == key:
                return mid
            elif self.l[mid].key < key:
                lo = mid + 1
                mid = (lo + hi) / 2
        return mid
       
class BinarySearchTreeDict(object):
    class Node(object):
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.left = None
            self.right = None
            
    def __init__(self):
        self.size = 0
        self.root = None
       
    def put(self, key, value):
        self.root = self._put(key, value, self.root)
   
    def get(self, key):
        return self._get(key, self.root)
        
    def _put(self, key, value, node):
        if node == None:
            self.size += 1
            return BinarySearchTreeDict.Node(key, value)
        if node.key == key:
            node.value = value
            return node
        elif node.key < key: node.left = self._put(key, value, node.left)
        else: node.right = self._put(key, value, node.right)
        return node
        
    def _get(self, key, node):
        if node == None: return None
        if node.key == key: return node.value
        elif node.key < key: return self._get(key, node.left)
        else: return self._get(key, node.right)
   
class BalancedSearchTreeDict(object):
    class Node(object):
        RED = True
        BLACK = False
        
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.left = None
            self.right = None
            self.color = BalancedSearchTreeDict.Node.RED
            
        def is_red(self, node):
            if node == None: return False
            return node.color == BalancedSearchTreeDict.Node.RED
        
        def rotate_left(self, node):
            x = node.right
            node.right = x.left
            x.left = node
            node.color = BalancedSearchTreeDict.Node.RED
            return x 
        
        def rotate_right(self, node):
            x = node.left
            node.left = x.right
            x.right = node
            node.color = BalancedSearchTreeDict.Node.RED
            return x
        
        def flip_colors(self, node):
            node.color = BalancedSearchTreeDict.Node.RED
            node.left.color = BalancedSearchTreeDict.Node.BLACK
            node.right.color = BalancedSearchTreeDict.Node.BLACK
            
    def __init__(self):
        self.size = 0
        self.root = None
       
    def put(self, key, value):
        self.root = self._put(key, value, self.root)
        self.root.color = BalancedSearchTreeDict.Node.BLACK
   
    def _put(self, key, value, node):
        if node == None:
            self.size += 1
            return BalancedSearchTreeDict.Node(key, value)
        if node.key == key:
            node.value = value
            return node
        elif node.key < key: node.left = self._put(key, value, node.left)
        else: node.right = self._put(key, value, node.right)
        
        # these are the properties of Red-Black tree for balancing
        # the tree
        if node.is_red(node.right) and not node.is_red(node.left):
            node = node.rotate_left(node);
        if node.is_red(node.left) and node.is_red(node.left.left):
            node = node.rotate_right(node);
        if node.is_red(node.left) and node.is_red(node.right):
            node.flip_colors(node);
      
        return node
        
    def get(self, key):
        return self._get(key, self.root)
    
    def _get(self, key, node):
        if node == None: return None
        if node.key == key: return node.value
        elif node.key < key: return self._get(key, node.left)
        else: return self._get(key, node.right)
   
class HashDict(object):
    # choose this M to be a prime number
    M = 977
    
    def __init__(self, n=M):
        self.size = 0
        self.l = []
        for i in xrange(0, n):
            self.l.append(SequentialSearchDict())
            
    def _hash(self, key):
        return (hash(key) & 0x7ffffff) % HashDict.M
    
    def put(self, key, value):
        d = self.l[self._hash(key)]
        n = d._put(key, value)
        self.size += n
   
    def get(self, key):
        return self.l[self._hash(key)].get(key)
 
if __name__ == "__main__":
    searches = [SequentialSearchDict(),
                BinarySearchDict(),
                BinarySearchTreeDict(),
                BalancedSearchTreeDict(),
                HashDict()]
    for s in searches:                                                                                                                                                                                                                  
        assert None == s.get("foo")
        s.put("1", "a")
        s.put("2", "b")
        s.put("3", "c")
        assert 3 == s.size
        assert "b" == s.get("2")
        assert "c" == s.get("3")
        assert "a" == s.get("1")
        s.put("3", "d")
        assert 3 == s.size
        assert "d" == s.get("3")
        assert "b" == s.get("2")
        assert "a" == s.get("1")
        assert None == s.get("bar")

How to Implement Pascal Triangle in Python

My implementation of Pascal Triangle.

#!/usr/bin/env python
def pascal(n):
    if n == 0: 
        return [1]
    else:
        l1 = pascal(n-1)
        print l1
        l2 = [1]
        for i in xrange(1, len(l1)):
            l2.append(l1[i-1] + l1[i])
        l2 += [1]
        return l2

if __name__ == "__main__":
    import sys
    if len(sys.argv) != 2:
        print "Usage:", sys.argv[0], "n"
        sys.exit(1)
    pascal(int(sys.argv[1]))

How to Implement Binary Search in Python

My simple implementations of binary search algorithms (iterative and recursive) in Python.

#!/usr/bin/env python

def search(l, i, func):
    lo = 0
    hi = len(l) - 1
    mid = (lo + hi) / 2
    return func(l, i, lo, mid, hi)
    
def recursive_binary_search(l, i, lo, mid, hi):
    if lo > mid or hi < mid: return -1

    if l[mid] > i:
        hi = mid - 1
        mid = (lo + hi) / 2
        return recursive_binary_search(l, i, lo, mid, hi)
    elif l[mid] == i:
        return mid
    elif l[mid] < i:
        lo = mid + 1
        mid = (lo + hi) / 2
        return recursive_binary_search(l, i, lo, mid, hi)

def iterative_binary_search(l, i, lo, mid, hi):
    while lo <= mid and hi >= mid:
        if l[mid] > i:
            hi = mid - 1
            mid = (lo + hi) / 2
        elif l[mid] == i:
            return mid
        elif l[mid] < i:
            lo = mid + 1
            mid = (lo + hi) / 2
    return -1
    
if __name__ == "__main__":
    l = [x for x in xrange(0, 10)]
    print "Using recursive binary search"
    print "Input:", l
    for i in xrange(0, len(l)):
        index = search(l, i, recursive_binary_search)
        print "Searching for", i, ", got index", index
        assert i == index
    i = 10
    index = search(l, i, recursive_binary_search)
    print "Searching for", i, ", got index", index

    print

    print "Using iterative binary search"
    print "Input:", l
    for i in xrange(0, len(l)):
        index = search(l, i, iterative_binary_search)
        print "Searching for", i, ", got index", index
        assert i == index
    i = 10
    index = search(l, i, iterative_binary_search)
    print "Searching for", i, ", got index", index

How to Access SWT UI Components from Non-UI Thread

Accessing SWT components in a non-UI thread will cause an SWTException (invalid thread access) to be thrown. This example shows how an SWT application is started in a non-main thread and the main thread manipulates the SWT application by updating the text in the button and stopping the SWT application.

import org.eclipse.jface.window.ApplicationWindow;
import org.eclipse.swt.SWT;
import org.eclipse.swt.layout.FillLayout;
import org.eclipse.swt.widgets.Button;
import org.eclipse.swt.widgets.Composite;
import org.eclipse.swt.widgets.Control;
import org.eclipse.swt.widgets.Display;

public class SWTTest extends ApplicationWindow {
    private Thread uiThread;
    private Button button;
    
    public SWTTest() {
        super(null);
    }
    
    @Override
    protected Control createContents(Composite parent) {
        getShell().setText("SWTTest");
        getShell().setSize(400, 100);
        
        Composite c = new Composite(parent, SWT.NONE);
        c.setLayout(new FillLayout());
        
        button = new Button(c, SWT.NONE);
        button.setText("Hello");
        
        return parent;
    }
    
    public Display getDisplay() {
        // Calling Display.getCurrent() will most likely throw
        // a NUllPointerException if it's called from a main thread.
        // The correct way to get the Display instance is by passing the
        // UI thread
        return Display.findDisplay(uiThread);
    }
    
    public void start() {
        // We store the UI thread for the getDisplay() method
        uiThread= Thread.currentThread();
        setBlockOnOpen(true);
        open();
    }
    
    public void updateText(final String text) {
        // Any SWT operations must be done in a UI thread, so we must
        // use getDisplay().syncExec() or getDisplay().asyncExec().
        getDisplay().syncExec(new Runnable() {
            @Override
            public void run() {
                button.setText(text);
            }
        });
    }
    
    public void stop() {
        // Any SWT operations must be done in a UI thread, so we must
        // use getDisplay().syncExec() or getDisplay().asyncExec().
        getDisplay().syncExec(new Runnable() {
            @Override
            public void run() {
                close();
                getDisplay().dispose();
            }
        });
    }
    
    public static void main(String[] args) throws Exception {
        final SWTTest app = new SWTTest();
        // app.start() blocks, so we need to start it in a new thread.
        new Thread(new Runnable() {
            @Override
            public void run() {
                System.out.println("Starting the GUI");
                app.start();
            }
        }).start();
        
        System.out.println("Sleeping for 3 secs");
        Thread.sleep(3000);
        
        System.out.println("Updating the GUI");
        app.updateText("Bye");
        
        System.out.println("Sleeping for 3 secs");
        Thread.sleep(3000);
        
        System.out.println("Stopping the GUI");
        app.stop();
    }
}

SWT/JFace Examples

This example contains a lot of examples how to use SWT/JFace components with MigLayout. Not all SWT/JFace components are covered here.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

import net.miginfocom.swt.MigLayout;

import org.eclipse.core.runtime.IStatus;
import org.eclipse.core.runtime.MultiStatus;
import org.eclipse.core.runtime.Status;
import org.eclipse.jface.action.Action;
import org.eclipse.jface.action.IAction;
import org.eclipse.jface.action.MenuManager;
import org.eclipse.jface.dialogs.Dialog;
import org.eclipse.jface.dialogs.ErrorDialog;
import org.eclipse.jface.dialogs.IDialogConstants;
import org.eclipse.jface.dialogs.MessageDialog;
import org.eclipse.jface.preference.ColorSelector;
import org.eclipse.jface.viewers.CellEditor;
import org.eclipse.jface.viewers.ColumnWeightData;
import org.eclipse.jface.viewers.ComboBoxCellEditor;
import org.eclipse.jface.viewers.ComboViewer;
import org.eclipse.jface.viewers.ICellModifier;
import org.eclipse.jface.viewers.ILabelProviderListener;
import org.eclipse.jface.viewers.IStructuredContentProvider;
import org.eclipse.jface.viewers.ITableLabelProvider;
import org.eclipse.jface.viewers.ITreeContentProvider;
import org.eclipse.jface.viewers.LabelProvider;
import org.eclipse.jface.viewers.ListViewer;
import org.eclipse.jface.viewers.TableLayout;
import org.eclipse.jface.viewers.TableViewer;
import org.eclipse.jface.viewers.TextCellEditor;
import org.eclipse.jface.viewers.TreeViewer;
import org.eclipse.jface.viewers.Viewer;
import org.eclipse.jface.window.ApplicationWindow;
import org.eclipse.jface.wizard.IWizardPage;
import org.eclipse.jface.wizard.Wizard;
import org.eclipse.jface.wizard.WizardDialog;
import org.eclipse.jface.wizard.WizardPage;
import org.eclipse.swt.SWT;
import org.eclipse.swt.dnd.DND;
import org.eclipse.swt.dnd.DropTarget;
import org.eclipse.swt.dnd.DropTargetAdapter;
import org.eclipse.swt.dnd.DropTargetEvent;
import org.eclipse.swt.dnd.FileTransfer;
import org.eclipse.swt.dnd.Transfer;
import org.eclipse.swt.events.SelectionEvent;
import org.eclipse.swt.events.SelectionListener;
import org.eclipse.swt.graphics.Image;
import org.eclipse.swt.widgets.Button;
import org.eclipse.swt.widgets.Composite;
import org.eclipse.swt.widgets.Control;
import org.eclipse.swt.widgets.DirectoryDialog;
import org.eclipse.swt.widgets.Display;
import org.eclipse.swt.widgets.Group;
import org.eclipse.swt.widgets.Label;
import org.eclipse.swt.widgets.Menu;
import org.eclipse.swt.widgets.MessageBox;
import org.eclipse.swt.widgets.Shell;
import org.eclipse.swt.widgets.TabFolder;
import org.eclipse.swt.widgets.TabItem;
import org.eclipse.swt.widgets.Table;
import org.eclipse.swt.widgets.TableColumn;
import org.eclipse.swt.widgets.TableItem;
import org.eclipse.swt.widgets.Text;

public class SWTApp extends ApplicationWindow {
    public SWTApp() {
        super(null);
        addStatusLine();
    }

    @Override
    protected Control createContents(Composite parent) {
        getStatusLineManager().setMessage("Welcome to SWTApp");

        TabFolder tabFolder = new TabFolder(parent, SWT.NONE);
        TabItem tabItem = new TabItem(tabFolder, SWT.NONE);
        tabItem.setText("Tab 1");
        tabItem.setControl(new MyComposite1(tabFolder));

        tabItem = new TabItem(tabFolder, SWT.NONE);
        tabItem.setText("Tab 2");
        tabItem.setControl(new MyComposite2(tabFolder));

        tabItem = new TabItem(tabFolder, SWT.NONE);
        tabItem.setText("Tab 3");
        tabItem.setControl(new MyComposite3(tabFolder));

        tabItem = new TabItem(tabFolder, SWT.NONE);
        tabItem.setText("Tab 4");
        tabItem.setControl(new MyComposite4(tabFolder));
        
        tabItem = new TabItem(tabFolder, SWT.NONE);
        tabItem.setText("Tab 5");
        tabItem.setControl(new MyComposite5(tabFolder));
        
        getShell().setText("SWTApp");
        getShell().setSize(900, 700);

        return parent;
    };

    static class MyComposite1 extends Composite {
        public MyComposite1(Composite parent) {
            super(parent, SWT.NONE);
            setLayout(new MigLayout("", "[grow][grow]", "[grow, fill]"));

            Group g1 = new Group(this, SWT.SHADOW_ETCHED_IN);
            g1.setLayout(new MigLayout("", "[grow, fill]", "[][grow, fill]"));
            g1.setLayoutData("grow");

            Composite1 c1 = new Composite1(g1);
            c1.setLayoutData("grow, wrap");

            Composite2 c2 = new Composite2(g1);
            c2.setLayoutData("grow");

            Group g2 = new Group(this, SWT.SHADOW_ETCHED_IN);
            g2.setLayout(new MigLayout("", "[grow, fill]", "[grow, fill]"));
            g2.setLayoutData("grow");

            Composite c3 = new Composite3(g2);
            c3.setLayoutData("grow");
        }
    }

    static class Composite1 extends Composite {
        public Composite1(Composite parent) {
            super(parent, SWT.NONE);
            setLayout(new MigLayout("", "[grow, fill][]", "[grow, fill]"));

            Composite c1 = new Composite(this, SWT.NONE);
            c1.setLayout(new MigLayout("", "[][grow]", ""));
            Label field1Label = new Label(c1, SWT.NONE);
            field1Label.setText("Field 1");
            Text field1Text = new Text(c1, SWT.BORDER);
            field1Text.setLayoutData("grow, wrap");

            Label field2Label = new Label(c1, SWT.NONE);
            field2Label.setText("Field 2");
            Text field2Text = new Text(c1, SWT.BORDER);
            field2Text.setLayoutData("grow, wrap");

            Label field3Label = new Label(c1, SWT.NONE);
            field3Label.setText("Field 3");
            Text field3Text = new Text(c1, SWT.BORDER);
            field3Text.setLayoutData("grow, wrap");

            Label field4Label = new Label(c1, SWT.NONE);
            field4Label.setText("Field 4");
            Text field4Text = new Text(c1, SWT.BORDER);
            field4Text.setLayoutData("grow");

            Composite c2 = new Composite(this, SWT.NONE);
            c2.setLayout(new MigLayout("", "", "[grow]"));
            Button startButton = new Button(c2, SWT.NONE);
            startButton.setText("START");
            startButton.setBackground(getDisplay().getSystemColor(SWT.COLOR_GREEN));
            startButton.setLayoutData("grow, wrap");

            Button stopButton = new Button(c2, SWT.NONE);
            stopButton.setText("STOP");
            stopButton.setBackground(getDisplay().getSystemColor(SWT.COLOR_RED));
            stopButton.setLayoutData("grow, wrap");

            Button advancedButton = new Button(c2, SWT.NONE);
            advancedButton.setText("ADVANCED");
            advancedButton.setLayoutData("grow, wrap");

            ColorSelector cs = new ColorSelector(c2);
            Button colorSelectorButton = cs.getButton();
            colorSelectorButton.setText("COLOR");
            colorSelectorButton.setLayoutData("grow");
        }
    }

    static class Composite2 extends Composite {
        public Composite2(Composite parent) {
            super(parent, SWT.NONE);
            setLayout(new MigLayout("", "[grow]", "[grow]"));

            Text statusText = new Text(this, SWT.MULTI | SWT.BORDER);
            statusText.setEditable(false);
            statusText.setLayoutData("grow");
        }
    }

    static class Composite3 extends Composite {
        public Composite3(Composite parent) {
            super(parent, SWT.NONE);
            setLayout(new MigLayout("", "[grow]", "[grow][grow]"));

            Button b1 = new Button(this, SWT.NONE);
            b1.setText("Button 1");
            b1.setLayoutData("grow, wrap");

            Button b2 = new Button(this, SWT.NONE);
            b2.setText("Button 2");
            b2.setLayoutData("grow");
        }
    }

    static class MyComposite2 extends Composite {
        public MyComposite2(Composite parent) {
            super(parent, SWT.NONE);
            setLayout(new MigLayout("", "[grow, fill]", "[grow, fill][]"));

            Composite c1 = new Composite(this, SWT.BORDER);
            c1.setLayout(new MigLayout("", "[grow][grow][grow][grow]", "[grow]"));
            c1.setLayoutData("wrap");

            int[] styles = { SWT.SINGLE, SWT.MULTI };
            for (int style = 0; style < styles.length; style++) {
                ListViewer lv = createListViewer(c1, styles[style]);
                lv.getList().setLayoutData("grow");
            }

            int[] selectionStyle = { SWT.SINGLE, SWT.MULTI };
            int[] checkStyle = { SWT.NONE, SWT.CHECK };

            for (int selection = 0; selection < selectionStyle.length; selection++) {
                for (int check = 0; check < checkStyle.length; check++) {
                    int style = selectionStyle[selection] | checkStyle[check];
                    TreeViewer tv = createTreeViewer(c1, style);
                    tv.getTree().setLayoutData("grow");
                }
            }

            Composite c2 = new Composite(this, SWT.BORDER);
            c2.setLayout(new MigLayout("", "[grow]", ""));
            ComboViewer cv = createComboViewer(c2);
            cv.getCombo().setLayoutData("grow");
        }

        private ComboViewer createComboViewer(Composite parent) {
            ComboViewer viewer = new ComboViewer(parent, SWT.NONE);

            viewer.setLabelProvider(new LabelProvider() {
                @Override
                public String getText(Object element) {
                    return ((ListItem) element).name;
                }
            });

            viewer.setContentProvider(new IStructuredContentProvider() {
                @SuppressWarnings("unchecked")
                @Override
                public Object[] getElements(Object inputElement) {
                    return ((List<ListItem>) inputElement).toArray();
                }

                @Override
                public void dispose() {
                }

                @Override
                public void inputChanged(Viewer viewer, Object oldInput, Object newInput) {
                }
            });

            List<ListItem> input = new ArrayList<ListItem>();
            for (int i = 0; i < 20; i++) {
                input.add(new ListItem("Item " + i, i));
            }
            viewer.setInput(input);

            return viewer;
        }

        private ListViewer createListViewer(Composite parent, int style) {
            ListViewer viewer = new ListViewer(parent, style);

            viewer.setLabelProvider(new LabelProvider() {
                @Override
                public String getText(Object element) {
                    return ((ListItem) element).name;
                }
            });

            viewer.setContentProvider(new IStructuredContentProvider() {
                @SuppressWarnings("unchecked")
                @Override
                public Object[] getElements(Object inputElement) {
                    return ((List<ListItem>) inputElement).toArray();
                }

                @Override
                public void dispose() {
                }

                @Override
                public void inputChanged(Viewer viewer, Object oldInput, Object newInput) {
                }
            });

            List<ListItem> input = new ArrayList<ListItem>();
            for (int i = 0; i < 20; i++) {
                input.add(new ListItem("Item " + i, i));
            }
            viewer.setInput(input);

            return viewer;
        }

        private TreeViewer createTreeViewer(Composite parent, int style) {
            TreeViewer viewer = new TreeViewer(parent, style);

            viewer.setContentProvider(new ITreeContentProvider() {
                public Object[] getChildren(Object parentElement) {
                    return ((TreeNode) parentElement).getChildren().toArray();
                }

                public Object getParent(Object element) {
                    return ((TreeNode) element).getParent();
                }

                public boolean hasChildren(Object element) {
                    return ((TreeNode) element).getChildren().size() > 0;
                }

                public Object[] getElements(Object inputElement) {
                    return ((TreeNode) inputElement).getChildren().toArray();
                }

                public void dispose() {
                }

                public void inputChanged(Viewer viewer, Object oldInput, Object newInput) {
                }
            });

            viewer.setInput(getRootNode());

            return viewer;
        }

        private TreeNode getRootNode() {
            TreeNode root = new TreeNode("root");
            root.addChild(new TreeNode("child 1").addChild(new TreeNode("subchild 1")));
            root.addChild(new TreeNode("child 2").addChild(new TreeNode("subchild 2")
                .addChild(new TreeNode("grandchild 1"))));

            return root;
        }
    }

    static class ListItem {
        public String name;
        public int value;

        public ListItem(String n, int v) {
            name = n;
            value = v;
        }
    }

    static class TreeNode {
        private String name;
        private List<TreeNode> children = new ArrayList<TreeNode>();
        private TreeNode parent;

        public TreeNode(String n) {
            name = n;
        }

        protected Object getParent() {
            return parent;
        }

        public TreeNode addChild(TreeNode child) {
            children.add(child);
            child.parent = this;
            return this;
        }

        public List<TreeNode> getChildren() {
            return children;
        }

        public String toString() {
            return name;
        }
    }

    static class MyComposite3 extends Composite {
        public MyComposite3(Composite parent) {
            super(parent, SWT.NONE);
            setLayout(new MigLayout("", "[grow]", "[grow]"));

            Table table = createTable();
            table.setLayoutData("grow");
        }

        private Table createTable() {
            final String[] VALUE_SET = new String[] {"xxx", "yyy", "zzz"};
            final String NAME_PROPERTY = "name";
            final String VALUE_PROPERTY = "value";

            Table table = new Table(this, SWT.FULL_SELECTION);

            final TableViewer viewer = new TableViewer(table);
            TableLayout layout = new TableLayout();
            layout.addColumnData(new ColumnWeightData(50, 75, true));
            layout.addColumnData(new ColumnWeightData(50, 75, true));
            table.setLayout(layout);

            TableColumn column = new TableColumn(table, SWT.CENTER);
            column.setText("Name");
            column = new TableColumn(table, SWT.NONE);
            column.setText("Value");
            table.setHeaderVisible(true);

            viewer.setLabelProvider(new ITableLabelProvider() {
                @Override
                public void removeListener(ILabelProviderListener lpl) {
                }

                @Override
                public boolean isLabelProperty(Object element, String property) {
                    return false;
                }

                @Override
                public void dispose() {
                }

                @Override
                public void addListener(ILabelProviderListener lpl) {
                }

                @Override
                public String getColumnText(Object element, int columnIndex) {
                    switch (columnIndex) {
                    case 0:
                        return ((EditableTableItem) element).name;
                    case 1:
                        Number index = ((EditableTableItem) element).value;
                        return VALUE_SET[index.intValue()];
                    default:
                        return "Invalid column: " + columnIndex;
                    }
                }

                @Override
                public Image getColumnImage(Object element, int columnIndex) {
                    return null;
                }
            });

            viewer.setContentProvider(new IStructuredContentProvider() {
                @Override
                public void inputChanged(Viewer viewer, Object oldInput, Object newInput) {
                }

                @Override
                public void dispose() {
                }

                @Override
                public Object[] getElements(Object inputElement) {
                    return (Object[]) inputElement;
                }
            });

            viewer.setCellModifier(new ICellModifier() {
                @Override
                public void modify(Object element, String property, Object value) {
                    TableItem tableItem = (TableItem) element;
                    EditableTableItem data = (EditableTableItem) tableItem.getData();
                    if (NAME_PROPERTY.equals(property)) {
                        data.name = value.toString();
                    } else {
                        data.value = (Integer) value;
                    }

                    viewer.refresh(data);
                }

                @Override
                public Object getValue(Object element, String property) {
                    if (NAME_PROPERTY.equals(property)) {
                        return ((EditableTableItem) element).name;
                    } else {
                        return ((EditableTableItem) element).value;
                    }
                }

                @Override
                public boolean canModify(Object element, String property) {
                    return true;
                }
            });

            viewer.setCellEditors(new CellEditor[] {
                new TextCellEditor(table),
                new ComboBoxCellEditor(table, VALUE_SET)
            });

            viewer.setInput(new Object[] {
               new EditableTableItem("Item 1", 0),
               new EditableTableItem("Item 2", 1)
            });

            viewer.setColumnProperties(new String[] {NAME_PROPERTY, VALUE_PROPERTY});

            createMenu(table, viewer);

            return table;
        }

        private void createMenu(Table table, TableViewer viewer) {
            MenuManager popupMenu = new MenuManager();
            IAction newRowAction = new NewRowAction(viewer);
            popupMenu.add(newRowAction);
            Menu menu = popupMenu.createContextMenu(table);
            table.setMenu(menu);
        }
    }

    static class EditableTableItem {
        public String name;
        public Integer value;

        public EditableTableItem(String name, Integer value) {
            this.name = name;
            this.value = value;
        }
    }

    static class NewRowAction extends Action {
        private TableViewer viewer;

        public NewRowAction(TableViewer viewer) {
            super("Insert New Row");
            this.viewer = viewer;
        }

        @Override
        public void run() {
            EditableTableItem newItem = new EditableTableItem(
                "new row", new Integer(2));
            viewer.add(newItem);
        }
    }

    static class MyComposite4 extends Composite {
        public MyComposite4(Composite parent) {
            super(parent, SWT.NONE);
            setLayout(new MigLayout());

            createPasswordDialogButton();
            createMessageDialogButton();
            createMessageBoxButton();
            createErrorDialogButton();
            createWizardDialogButton();
        }

        private Button createPasswordDialogButton() {
            Button dialogButton = new Button(this, SWT.PUSH);
            dialogButton.setText("Password Dialog...");
            dialogButton.addSelectionListener(new SelectionListener() {
                @Override
                public void widgetSelected(SelectionEvent e) {
                    UserNamePasswordDialog d = new UserNamePasswordDialog(getShell());
                    d.open();
                }

                @Override
                public void widgetDefaultSelected(SelectionEvent e) {
                }
            });

            return dialogButton;
        }

        private Button createMessageDialogButton() {
            Button dialogButton = new Button(this, SWT.PUSH);
            dialogButton.setText("Message Dialog...");
            dialogButton.addSelectionListener(new SelectionListener() {
                @Override
                public void widgetSelected(SelectionEvent e) {
                    MessageDialog dialog = new MessageDialog(getShell(),
                        "Greeting Dialog",
                        null, "Hello! How are you today?",
                        MessageDialog.QUESTION,
                        new String[] { "Good", "Been better", "Excited about SWT!" },
                        0);
                    dialog.open();
                }

                @Override
                public void widgetDefaultSelected(SelectionEvent e) {
                }
            });

            return dialogButton;
        }

        private Button createMessageBoxButton() {
            Button dialogButton = new Button(this, SWT.PUSH);
            dialogButton.setText("Message Box...");
            dialogButton.addSelectionListener(new SelectionListener() {
                @Override
                public void widgetSelected(SelectionEvent e) {
                    MessageBox dialog = new MessageBox(getShell(),
                        SWT.OK | SWT.CANCEL);
                    dialog.setMessage("Do you wish to continue?");
                    dialog.open();
                }

                @Override
                public void widgetDefaultSelected(SelectionEvent e) {
                }
            });

            return dialogButton;
        }

        private Button createErrorDialogButton() {
            Button dialogButton = new Button(this, SWT.PUSH);
            dialogButton.setText("Error Dialog...");
            dialogButton.addSelectionListener(new SelectionListener() {
                @Override
                public void widgetSelected(SelectionEvent e) {
                    ErrorDialog errorDialog = new ErrorDialog(getShell(),
                        "Test Error Dialog",
                        "This is a test error dialog",
                        createStatus(),
                        IStatus.ERROR | IStatus.INFO);
                    errorDialog.open();
                }

                @Override
                public void widgetDefaultSelected(SelectionEvent e) {
                }
            });

            return dialogButton;
        }

        private IStatus createStatus() {
            final String dummyPlugin = "some plugin";
            IStatus[] statuses = new IStatus[2];
            statuses[0] = new Status(IStatus.ERROR, dummyPlugin, IStatus.OK,
                "Oh no!  An error occurred!", new Exception());

            statuses[1] = new Status(IStatus.INFO, dummyPlugin, IStatus.OK, "More errors!?!?",
                new Exception());

            MultiStatus multiStatus = new MultiStatus(dummyPlugin, IStatus.OK, statuses,
                "Several errors have occurred.", new Exception());

            return multiStatus;
        }
        
        private Button createWizardDialogButton() {
            Button dialogButton = new Button(this, SWT.PUSH);
            dialogButton.setText("Wizard Dialog...");
            dialogButton.addSelectionListener(new SelectionListener() {
                @Override
                public void widgetSelected(SelectionEvent e) {
                   WizardDialog dialog = new WizardDialog(getShell(),
                       new ProjectWizard());
                   dialog.open();
                }

                @Override
                public void widgetDefaultSelected(SelectionEvent e) {
                }
            });

            return dialogButton;
        }
    }

    static class UserNamePasswordDialog extends Dialog {
        private static final int RESET_ID = IDialogConstants.NO_TO_ALL_ID + 1;
        private Text userNameText;
        private Text passwordText;

        public UserNamePasswordDialog(Shell parentShell) {
            super(parentShell);
        }

        @Override
        protected void configureShell(Shell newShell) {
            super.configureShell(newShell);
            newShell.setText("Username/Password Dialog");
        }
        
        @Override
        protected Control createDialogArea(Composite parent) {
            Composite composite = (Composite) super.createDialogArea(parent);
            composite.setLayout(new MigLayout("", "[][grow]", ""));

            Label userNameLabel = new Label(composite, SWT.NONE);
            userNameLabel.setText("Username: " );
            userNameText = new Text(composite, SWT.SINGLE | SWT.BORDER);
            userNameText.setLayoutData("grow, wrap");

            Label passwordLabel = new Label(composite, SWT.NONE);
            passwordLabel.setText("Password: ");
            passwordText = new Text(composite, SWT.SINGLE | SWT.PASSWORD | SWT.BORDER);
            passwordText.setLayoutData("grow");

            return composite;
        }

        @Override
        protected void createButtonsForButtonBar(Composite parent) {
            super.createButtonsForButtonBar(parent);
            createButton(parent, RESET_ID, "Reset All", false);
        }

        @Override
        protected void buttonPressed(int buttonId) {
            if (buttonId == RESET_ID) {
                userNameText.setText("");
                passwordText.setText("");
            } else {
                super.buttonPressed(buttonId);
            }
        }
    }

    static class DirectoryPage extends WizardPage {
        public static final String PAGE_NAME = "Directory";
        private Button button;

        public DirectoryPage() {
            super(PAGE_NAME, "Directory Page", null);
        }

        @Override
        public void createControl(Composite parent) {
            Composite topLevel = new Composite(parent, SWT.NONE);
            topLevel.setLayout(new MigLayout());

            button = new Button(topLevel, SWT.CHECK);
            button.setText("Use default directory?");

            setControl(topLevel);
            setPageComplete(true);
        }

        public boolean useDefaultDirectory() {
            return button.getSelection();
        }
    }
    
    static class ChooseDirectoryPage extends WizardPage {
        public static final String PAGE_NAME = "Choose Directory";
        private Text text;

        public ChooseDirectoryPage() {
            super(PAGE_NAME, "Choose Directory Page", null);
        }

        @Override
        public void createControl(Composite parent) {
            Composite topLevel = new Composite(parent, SWT.NONE);
            topLevel.setLayout(new MigLayout("", "[][grow][]", ""));

            Label l = new Label(topLevel, SWT.CENTER);
            l.setText("Enter the directory to use:");

            text = new Text(topLevel, SWT.SINGLE | SWT.BORDER);
            text.setEditable(false);
            text.setLayoutData("grow");
            
            Button b = new Button(topLevel, SWT.PUSH);
            b.setText("Choose Directory");
            b.addSelectionListener(new SelectionListener() {
                @Override
                public void widgetSelected(SelectionEvent e) {
                    DirectoryDialog dialog = new DirectoryDialog(getShell());
                    String directory = dialog.open();
                    text.setText(directory);
                }
                
                @Override
                public void widgetDefaultSelected(SelectionEvent e) {
                }
            });

            setControl(topLevel);
            setPageComplete(true);
        }

        public String getDirectory() {
            return text.getText();
        }
    }
    
    static class SummaryPage extends WizardPage {
        public static final String PAGE_NAME = "Summary";
        private Label textLabel;
        private Composite topLevel;

        public SummaryPage() {
            super(PAGE_NAME, "Summary Page", null);
        }

        @Override
        public void createControl(Composite parent) {
            topLevel = new Composite(parent, SWT.NONE);
            topLevel.setLayout(new MigLayout());

            textLabel = new Label(topLevel, SWT.CENTER);
            textLabel.setText("");
            textLabel.setLayoutData("grow");
            
            setControl(topLevel);
            setPageComplete(true);
        }

        public void updateText(String newText) {
            textLabel.setText(newText);
            topLevel.pack();
        }
    }
    
    static class ProjectWizard extends Wizard {
        public void addPages() {
            addPage(new DirectoryPage());
            addPage(new ChooseDirectoryPage());
            addPage(new SummaryPage());
        }

        @Override
        public boolean performFinish() {
            DirectoryPage dirPage = getDirectoryPage();
            if (dirPage.useDefaultDirectory()) {
                System.out.println("Using default directory");
            } else {
                ChooseDirectoryPage choosePage = getChoosePage();
                System.out.println("Using directory: " + choosePage.getDirectory());
            }
            return true;
        }

        private ChooseDirectoryPage getChoosePage() {
            return (ChooseDirectoryPage) getPage(ChooseDirectoryPage.PAGE_NAME);
        }

        private DirectoryPage getDirectoryPage() {
            return (DirectoryPage) getPage(DirectoryPage.PAGE_NAME);
        }

        @Override
        public boolean performCancel() {
            System.out.println("Perform Cancel called");
            return true;
        }

        @Override
        public IWizardPage getNextPage(IWizardPage page) {
            if (page instanceof DirectoryPage) {
                DirectoryPage dirPage = (DirectoryPage) page;
                if (dirPage.useDefaultDirectory()) {
                    SummaryPage summaryPage = (SummaryPage) getPage(SummaryPage.PAGE_NAME);
                    summaryPage.updateText("Using default directory");
                    return summaryPage;
                }
            }

            IWizardPage nextPage = super.getNextPage(page);
            if (nextPage instanceof SummaryPage) {
                SummaryPage summary = (SummaryPage) nextPage;
                DirectoryPage dirPage = getDirectoryPage();
                summary.updateText(dirPage.useDefaultDirectory() ? "Using default directory"
                    : "Using directory: " + getChoosePage().getDirectory());
            }
            return nextPage;
        }
    }
    
    static class MyComposite5 extends Composite {
        public MyComposite5(Composite parent) {
            super(parent, SWT.NONE);
            setLayout(new MigLayout("", "[grow, fill]", "[grow, fill]"));
            
            Text text = createTextArea();
            text.setLayoutData("grow");
        }
        
        private Text createTextArea() {
            Text text = new Text(this, SWT.MULTI | SWT.BORDER);
            
            DropTarget target = new DropTarget(text,
                DND.DROP_MOVE | DND.DROP_COPY | DND.DROP_DEFAULT);
            target.setTransfer(new Transfer[] { FileTransfer.getInstance() });
            target.addDropListener(new DropTargetAdapter() {
                @Override
                public void drop(DropTargetEvent event) {
                    DropTarget target = (DropTarget) event.widget;
                    Text t = (Text) target.getControl();
                    String[] fileList = (String[]) event.data;
                    t.setText(read(fileList[0]));
                } 
            });
            
            return text;
        }
        
        private String read(String path) {
            String text = "";
            BufferedReader br = null;
            try {
                File file = new File(path);
                br = new BufferedReader(new FileReader(file));
                
                String line = "";
                while ((line = br.readLine()) != null) {
                    text += line + System.getProperty("line.separator");
                }
                int lastIndex = text.length() - 
                    System.getProperty("line.separator").length();
                text = text.substring(0, lastIndex);
            } catch (IOException e) {
                e.printStackTrace();
            } finally {
                if (br != null) {
                    try {
                        br.close();
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
            }
            return text;
        }
    }
    
    public static void show() {
        SWTApp app = new SWTApp();
        app.setBlockOnOpen(true);
        app.open();
        Display.getCurrent().dispose();
    }
}