Sunday, 17 March 2013

Properties design pattern and Prototype-based programming in Java

After reading Steve Yegge's post about the properties design pattern and how it can be used to create a prototype-based object system, I thought I'd have a go at an implementation in Java to understand more.

If you haven't read the above post already, it definitely worth a read (or two), and makes everything below make more sense, give it a go.

First, I wanted to define the minimum API needed to get a working properties object as described in the Overview section. A basic properties interface:

Properties.java

package org.adrianwalker.propertiespattern;

interface Properties<N, V> {

  V get(N name);

  V put(N name, V value);

  boolean has(N name);

  V remove(N name);
}

I'll defer describing the implementation until the end, because as soon as you have the basic functionality done there is a load more you're going to want to add.

Once you've got your Properties implementation storing name/value pairs and inheriting from a prototype Properties object stored against a reserved key name, at that point, your going to want to add some way for your objects to simulate methods to manipulate the property values.

Because Java doesn't have first class functions, a methods functionality needs to be encapsulated using the Strategy pattern.

Strategy.java

package org.adrianwalker.propertiespattern;

interface Strategy<N, V, T, A> {

  T execute(Properties<N, V> properties, A... args);
}

In addition to the Strategy interface, I extended the basic Properties interface with an execute method to call a Strategy property:

ExecutableProperites.java

package org.adrianwalker.propertiespattern;

interface ExecutableProperites<N, V, T, A> extends Properties<N, V> {

  T execute(N name, A... args);
}

You're also probably going to want a way of returning an object's property names, possibly filtered with by a regex, or a globing pattern, or partial string match or some kind object comparison. So another extension to the Properties interface:

FilterableProperties.java

package org.adrianwalker.propertiespattern;

import java.util.Set;

interface FilterableProperties<N, V> extends Properties<N, V> {

  Set<N> filter(N filter);
}

And it would be good to have an interface for cloning prototype-based objects:

CloneableProperties.java

package org.adrianwalker.propertiespattern;

interface CloneableProperties<N, V> extends Properties<N, V>, Cloneable {

  CloneableProperties<N, V> clone();
}

Implementation

With all of that out of the way it's time for an implementation. This implementation stores property name/value pairs in a HashMap, and filters using regular expressions:

HashMapProperties.java

package org.adrianwalker.propertiespattern;

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.regex.Pattern;

public final class HashMapProperties<V, T, A> implements
        Properties<String, V>,
        ExecutableProperites<String, V, T, A>,
        CloneableProperties<String, V>,
        FilterableProperties<String, V> {

  public static final String PROTOTYPE = "prototype";
  private final Map<String, V> properties;

  public HashMapProperties() {

    this.properties = Collections.synchronizedMap(new HashMap());
  }

  private HashMapProperties(final Map<String, V> map) {

    this.properties = Collections.synchronizedMap(new HashMap<String, V>(map));
  }

  @Override
  public V get(final String name) {

    if (properties.containsKey(name)) {

      return properties.get(name);
    }

    if (properties.containsKey(PROTOTYPE)) {

      Properties<String, V> prototype =
              (Properties<String, V>) properties.get(PROTOTYPE);

      return prototype.get(name);
    }

    return null;
  }

  @Override
  public V put(final String name, final V value) {

    if (PROTOTYPE.equals(name) && !(value instanceof Properties)) {

      throw new IllegalArgumentException(
              "prototype must be an instance of Properties");
    }

    return properties.put(name, value);
  }

  @Override
  public boolean has(final String name) {

    if (properties.containsKey(name)) {

      return null != properties.get(name);
    }

    if (properties.containsKey(PROTOTYPE)) {

      Properties<String, V> prototype =
              (Properties<String, V>) properties.get(PROTOTYPE);

      return prototype.has(name);
    }

    return false;
  }

  @Override
  public V remove(final String name) {

    if (properties.containsKey(PROTOTYPE)) {

      Properties<String, V> prototype =
              (Properties<String, V>) properties.get(PROTOTYPE);

      if (prototype.has(name)) {

        properties.put(name, null);

        return prototype.get(name);
      }
    }

    if (properties.containsKey(name)) {

      return properties.remove(name);
    }

    return null;
  }

  @Override
  public HashMapProperties<V, T, A> clone() {

    return new HashMapProperties<V, T, A>(properties);
  }

  @Override
  public T execute(final String name, final A... args) {

    V property = get(name);

    if (property instanceof Strategy) {

      return ((Strategy<String, V, T, A>) property).execute(this, args);
    }

    return null;
  }

  @Override
  public Set<String> filter(final String regex) {

    Pattern pattern = Pattern.compile(regex);

    Set<String> filteredNames = new HashSet<String>();

    Set<String> names = properties.keySet();

    synchronized (properties) {
      for (String name : names) {
        if (!PROTOTYPE.equals(name) && pattern.matcher(name).matches()) {
          filteredNames.add(name);
        }
      }
    }

    if (properties.containsKey(PROTOTYPE)) {
      FilterableProperties<String, V> prototype =
              (FilterableProperties<String, V>) properties.get(PROTOTYPE);
      filteredNames.addAll(prototype.filter(regex));
    }

    return filteredNames;
  }
}

Example Usage

The following example shows how you might use the above implementation. A prototype Properties object is created with a 'greeting' property and a 'getGreeting' Strategy property. These properties are inherited by a new Properties object.

The Properties object is cloned and it's greeting property is overridden.

The cloned Properties object's properties are filtered to return the getter Strategy's property name, then this is executed for the Properties object and it's clone:

Example.java

package org.adrianwalker.propertiespattern;

import java.util.Set;
import static org.adrianwalker.propertiespattern.HashMapProperties.PROTOTYPE;

public final class Example {

  public static void main(final String[] args) {
 
    // create a prototype properties object with a greeting and a 
    // strategy which returns the greeting and an argument
 
    Properties prototype = new HashMapProperties();
    prototype.put("greeting", "Hello");
    prototype.put("getGreeting", new Strategy() {
      @Override
      public String execute(final Properties properties, final Object... args) {

        return String.format("%s %s", properties.get("greeting"), args[0]);
      }
    });
 
    // create a properties object which inherit the greeting and 
    // strategy from the prototype

    HashMapProperties properties = new HashMapProperties();
    properties.put(PROTOTYPE, prototype);

    // clone the properties object and override the greeting property

    HashMapProperties clone = properties.clone();
    clone.put("greeting", "Ahoy");

    // filter for the getter properties, then execute the getter
    // on each properties object with a message argument and
    // print the message

    Set<String> getters = clone.filter("get.*");
    for (String getter : getters) {
      System.out.println(properties.execute(getter, "World"));
      System.out.println(clone.execute(getter, "Sailor"));
    }
  }
}

The example above should print the output:

Hello World
Ahoy Sailor

Finally

I've not implemented half of the functionality mentioned in original post, and not a fraction of a fraction of the possible applications for this pattern. The above code and a set of unit tests are available for download at the bottom of this page.

If you need the level of flexibility to warrant using this pattern, then, to quote the original article "use a programming language better suited for implementing the pattern: ideally, one that supports it from the ground up". So expect some JavaScript related posts in the future.

Source Code

Usage

Compile the project with 'mvn clean install'.

Tuesday, 5 February 2013

Email Sky Router Public IP Address with Gmail in Python

As far as I know, Sky Broadband don't offer a static IP address. You're going to want a way of keeping track of your externally available dynamic IP, so you can access your machine from outside of your network.

The python script below scrapes your Sky router's status page for your current IP and emails it your Gmail account.

Remember to change the Gmail username and password variables from '????????' to your Gmail authentication credentials. Run this script periodically as a cron job, and as long as you have Gmail access you'll know your IP.

#!/usr/bin/python

import smtplib
from email.mime.text import MIMEText
import urllib2
import re

# router login page
router_login = "http://192.168.0.1"
# router status url
router_status = "http://192.168.0.1/sky_router_status.html"
# router logout page
router_logout = "http://192.168.0.1/sky_logout.html"
# default sky router username and password
router_username = "admin"
router_password = "sky"
# gmail email address
email = "????????@gmail.com"
# gmail password
email_password = "????????"
# gmail smtp settings
server = "smtp.gmail.com"
port = 587
# email subject
subject = "Server IP"

# login to router
passman = urllib2.HTTPPasswordMgrWithDefaultRealm()
passman.add_password(None, router_login, router_username, router_password)
authhandler = urllib2.HTTPBasicAuthHandler(passman)
opener = urllib2.build_opener(authhandler)
urllib2.install_opener(opener)
urllib2.urlopen(router_login)

# get the first ip on the status page
ip = urllib2.urlopen(router_status).read()
ip = re.findall(r"[0-9]+(?:\.[0-9]+){3}", ip)
ip = ip[0]

# logout of router
urllib2.urlopen(router_logout)

# check for last ip address
f = open(".last_ip", "a+")
f.seek(0, 0)
last_ip = f.readline()

# has ip changed
if ip != last_ip:

  # store the new ip
  f.truncate(0)
  f.write(ip)

  session = smtplib.SMTP(server, port)

  session.ehlo()
  session.starttls()
  session.login(email, email_password)

  body = "http://" + ip

  msg = MIMEText(body)
  msg['Subject'] = subject
  msg['From'] = email
  msg['To'] = email

  session.sendmail(email, email, msg.as_string())
  session.quit()

f.close()

Sunday, 26 August 2012

Iterate over first n files in a directory with Java 6 and JNA on Linux

I needed to be able to iterate over the first n number of files in a directory, without bringing them all back at once using File.list(). This is simple enough to do in Java 7 using the new DirectoryStream interface, but I only had access to Java 6 for this project.

Similar functionality can be reproduced using calls to native operating system functions using Java Native Access.

This example works on Linux but could easily be adapted for Windows.

DirectoryStream.java

package org.adrianwalker;

import com.sun.jna.Library;
import com.sun.jna.Native;
import com.sun.jna.Pointer;
import com.sun.jna.Structure;
import java.io.Closeable;
import java.io.File;
import java.io.IOException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public final class DirectoryStream implements Iterable<File>, Closeable {

  private String dirName;
  private POSIX posix;
  private Pointer dirp;

  public DirectoryStream(final String dirName) {
    this.dirName = dirName;
    this.posix = (POSIX) Native.loadLibrary("c", POSIX.class);
  }

  @Override
  public Iterator<File> iterator() {

    return new Iterator<File>() {
      private boolean gotNext = false;
      private Dirent file;

      @Override
      public boolean hasNext() {

        if (!gotNext) {
          getNext();
        }

        return file != null;
      }

      @Override
      public File next() {

        if (!gotNext) {
          getNext();
        }

        if (null == file) {
          throw new NoSuchElementException();
        }

        gotNext = false;

        return new File(dirName, file.getName());
      }

      @Override
      public void remove() {
        throw new UnsupportedOperationException();
      }

      private void getNext() {
        if (null == dirp) {
          dirp = posix.opendir(dirName);
        }

        file = posix.readdir(dirp);

        gotNext = true;
      }
    };
  }

  @Override
  public void close() throws IOException {
    posix.closedir(dirp);
  }

  public interface POSIX extends Library {

    public Pointer opendir(String dirname);

    Dirent readdir(Pointer dirp);

    int closedir(Pointer dirp);
  }

  public static final class Dirent extends Structure {

    public long d_ino;
    public long d_off;
    public short d_reclen;
    public char d_type;
    public char[] d_name = new char[256];

    public String getName() {
      return getPointer().getString(8 + 8 + 2 + 1, false);
    }

    public long getInode() {
      return getPointer().getLong(0);
    }

    public void setUseMemory(Pointer p) {
      useMemory(p);
    }
  }
}

Example usage:-

Main.java

package org.adrianwalker;

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

public final class Main {

  private static final int MAX_FILES = 10;
  private static final String CURRENT_DIR = ".";
  private static final String PARENT_DIR = "..";

  public static void main(final String[] args) throws IOException {

    String dirName = "/tmp/files";
    DirectoryStream directoryStream = new DirectoryStream(dirName);

    int fileCount = 0;
    for (File file : directoryStream) {

      String name = file.getName();
      if (name.equals(CURRENT_DIR) || name.equals(PARENT_DIR)) {
        continue;
      }      
      
      if (fileCount++ == MAX_FILES) {
        break;
      }

      System.out.println(file);
    }
  }
}

Source Code

Usage

Build the project with 'mvn clean install' and run the Main class.

Sunday, 15 July 2012

Java EE 6 Cookbook for Securing, Tuning, and Extending Enterprise Applications Review

Java Enterprise Edition is Oracle's enterprise Java computing platform. The platform provides an API and runtime environment for developing and running enterprise software, including network and web services. Java EE extends the Java Standard Edition providing an API for object-relational mapping, distributed and multi-tier architectures, and web services.

Packt Publishing requested that I review one of their titles about Java EE: Java EE 6 Cookbook for Securing, Tuning, and Extending Enterprise Applications by Mick Knutson, available to buy from Packt's website.

Java EE 6 Cookbook for Securing, Tuning, and Extending Enterprise Applications is an OK book, the breadth of topics covered is vast, but outside of the scope of the book at times. It feels like the book is trying to be an introductory tutorial to most aspects of Java development. Not that this is a bad thing, lots of the topics covered are important to day to day Java development and the advice given is pragmatic. Using the information as a starting point to expand your knowledge would make you a Java jack of all trades.

I found parts of it very informative and other parts frustrating, overall I'd say its worth a read but might not be what you expect. It not a book about JEE development as much as about peripheral concerns around JEE development which you might encounter in a project.

The information is presented in recipes - how-to examples focusing on a specific JEE feature, or other topic, put together to form a cookbook. Each recipe is presented in a formulaic way, with information under the sub-headings: 'Getting ready', 'How to do it...', 'How it works...' and 'There's more'.

A Java EE 6 installation, application server, and an editor are requirements to reproduce the examples in the book. GlassFish application server is used in a number of recipes, and some recipes are specific to the IntelliJ IDEA editor, but for the majority of the book any IDE and app server could be used.

The code to accompany the book available as a download isn't great. The Maven project pom.xml files needed altering before the code would build, and source code examples for some chapters seemed to be altogether missing.

Chapter one highlights key changes in Java EE 6 and how new features will improve performance and ease of development. The chapter first covers old JEE APIs, showing examples of what older technologies in old applications might need replacing, and what to replace those older technologies with. Covered next are introductions to the specifications and APIs including, Context and Dependency Injection (CDI), EJB 3.1, JPA 2.0, JAX-RS 1.1, Sevlet 3.0, WebBeans 1.0, and JSF 2.0.

Chapter two covers JPA persistence, some good recipes in this chapter are the 'Understanding @CollectionTable' recipe, covering the new annotation in the JPA 2.0 specification, and the JPA audit pattern in recipe 'Auditing historical JPA Operations'. The chapter finishes with an introduction to profiling JPA operations with the IntelliJ IDEA profile. I've never gotten on board with IntelliJ IDEA, and much prefer NetBeans and its profiler.

Chapter three covers JEE security, starting with definitions of security terms and deployment descriptors for role definitions and mapping in GlassFish. Next is a pointlessly detailed description of Java EE authentication methods complete with activity diagrams and HTML request/response headers.

XML based authorization configuration is introduced, then new programmatic and annotation based security in the next recipe.

A recipe I found useful later in the chapter was 'Configuring Linux firewall rules' - using iptables to configure access to SSH on Linux. Although I found it informative, I can't help thinking it doesn't really belong in this book - and the same with the next recipe 'Securely obfuscating Java byte-code', I fail to see how obfuscating code makes an application any more secure.

Chapter 4 deals with testing. Testing is clearly an important topic, and consideration of testing strategies, frameworks, tools and libraries should part of any Java project, but I was surprised to see this as a chapter in this book. It's more of a general software development topic which probably needs a book in its own right, I'm not sure it should be in a book about Securing, Tuning and Extending Enterprise Java apps.

The chapter starts with a good recipe demonstrating the use of the Maven Surefire plugin to enable a remote debugging session.

The rest of the chapter gives examples of testing frameworks and libraries, not just applicable to JEE testing but also to Java SE. JUnit and DBUnit are used automate database testing, along with test object mocking libraries Mockito, Powermock and Hamcrest.

Selenium and soapUI testing tools are introduced at the end of the chapter, with some good information on how to integrate these tools into your build and test process with Maven.

Chapter 5 uses the Groovy and Scala scripting languages running on the JVM, integrated with existing Java code, to write more concise unit test code. There is also a Jython servlet recipe demonstrating how to create a simple web page. Although not strictly JEE related, I enjoyed these recipes and can see how using them to write less code can have productivity increases.

The rest of the chapter deals with Aspect Orient Programming with AspectJ and CDI, and starts by describing some AOP terms: Cross-cutting-concerns, Advice, Pointcut, Aspect Joinpoint and Weaving. Recipes include weaving AspectJ advice into your own code and using AspectJ with existing 3rd party libraries, and using CDI interceptors. The AspectJ recipes in this chapter are not limited to JEE programming, and would be applicable to Java SE projects also.

Chapter 6 goes a totally off track with mobile development recipes. Recipes cover mobile web frameworks, native code generators, native web runtime frameworks, development considerations for iOS, Objective-C, mobile development IDEs, Android development, online emulators and other totally random mobile development things which should have been way out of the scope of this book!

Chapter 7 explores configuration and management, the important recipes from this chapter cover the use of VisualVM to remotely interact with and monitor Tomcat and GlassFish servers using JMX.

There is a recipe in this chapter on the use of JRebel for rapid redeployment. JRebel is a non-free, closed source product, although a free 14-day trial download is available. I try not to use non-free, closed source software, and could not promote the use of this product on my blog.

With Chapter 8 the book finishes with some useful tutorials for using profiling tools to monitor JVM memory usage and utilities to monitor HTTP activity. It covers the use of VisualVM and the jstatd plugin, monitoring TCP connections with Netstat, proxying connection with TCPMon to observe HTTP traffic, and server monitoring with Munin.

Unfortunately the chapter finishes with another recipe for a closed source, non-free product, HTTP Debugger. Again a 14 day trial download is available, but as the software is not FOSS I did not use it.

Overall I think there are some good tips in this book, but some chapters just feel like filler. If you're not experienced already with JEE development, then this isn't the book to start to learn with. If you are experienced then some chapters will seem a bit basic, and I'm sure some will seem a bit off topic. But all JEE developers will take at least a handful of useful recipes from this book.

This is an OK book but not what I was expecting. I'm not sure if the author is trying to take systems approach to JEE development, or just picked some of his favorite topics on the periphery of JEE development and put them together. I'd make sure you have a flick through it before you buy.


Downloads From Packt

Friday, 29 June 2012

HTML5 Video Pseudostreaming with Java 7

Adapted from the byte range request servlet code from the The BalusC Code, here is a Java 7 pseudostreaming servlet for playing video using the HTML5 video tag.

The servlet takes the name of a video file to play as a request parameter and the byte range of the video to stream in the Range header field.

PseudostreamingServlet.java

package org.adrianwalker.pseudostreaming;

import java.io.IOException;
import java.io.OutputStream;
import java.net.URLDecoder;
import java.nio.ByteBuffer;
import java.nio.channels.SeekableByteChannel;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import static java.nio.file.StandardOpenOption.READ;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import javax.servlet.ServletException;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

public final class PseudostreamingServlet extends HttpServlet {

  private static final int BUFFER_LENGTH = 1024 * 16;
  private static final long EXPIRE_TIME = 1000 * 60 * 60 * 24;
  private static final Pattern RANGE_PATTERN = Pattern.compile("bytes=(?<start>\\d*)-(?<end>\\d*)");
  private String videoPath;

  @Override
  public void init() throws ServletException {
    videoPath = getInitParameter("videoPath");
  }

  @Override
  protected void doGet(final HttpServletRequest request, final HttpServletResponse response) throws ServletException, IOException {
    processRequest(request, response);
  }

  private void processRequest(final HttpServletRequest request, final HttpServletResponse response) throws IOException {

    String videoFilename = URLDecoder.decode(request.getParameter("video"), "UTF-8");
    Path video = Paths.get(videoPath, videoFilename);

    int length = (int) Files.size(video);
    int start = 0;
    int end = length - 1;

    String range = request.getHeader("Range");
    Matcher matcher = RANGE_PATTERN.matcher(range);
    
    if (matcher.matches()) {
      String startGroup = matcher.group("start");
      start = startGroup.isEmpty() ? start : Integer.valueOf(startGroup);
      start = start < 0 ? 0 : start;

      String endGroup = matcher.group("end");
      end = endGroup.isEmpty() ? end : Integer.valueOf(endGroup);
      end = end > length - 1 ? length - 1 : end;
    }

    int contentLength = end - start + 1;

    response.reset();
    response.setBufferSize(BUFFER_LENGTH);
    response.setHeader("Content-Disposition", String.format("inline;filename=\"%s\"", videoFilename));
    response.setHeader("Accept-Ranges", "bytes");
    response.setDateHeader("Last-Modified", Files.getLastModifiedTime(video).toMillis());
    response.setDateHeader("Expires", System.currentTimeMillis() + EXPIRE_TIME);
    response.setContentType(Files.probeContentType(video));
    response.setHeader("Content-Range", String.format("bytes %s-%s/%s", start, end, length));
    response.setHeader("Content-Length", String.format("%s", contentLength));
    response.setStatus(HttpServletResponse.SC_PARTIAL_CONTENT);

    int bytesRead;
    int bytesLeft = contentLength;
    ByteBuffer buffer = ByteBuffer.allocate(BUFFER_LENGTH);

    try (SeekableByteChannel input = Files.newByteChannel(video, READ);
            OutputStream output = response.getOutputStream()) {

      input.position(start);

      while ((bytesRead = input.read(buffer)) != -1 && bytesLeft > 0) {
        buffer.clear();
        output.write(buffer.array(), 0, bytesLeft < bytesRead ? bytesLeft : bytesRead);
        bytesLeft -= bytesRead;
      }
    }
  }
}

The location of the videos on the file system is configurable in the web.xml via the videoPath parameter for the stream servlet.

web.xml

<?xml version="1.0" encoding="UTF-8"?>
<web-app version="3.0" xmlns="http://java.sun.com/xml/ns/javaee" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://java.sun.com/xml/ns/javaee http://java.sun.com/xml/ns/javaee/web-app_3_0.xsd">
    <servlet>
        <servlet-name>stream</servlet-name>
        <servlet-class>org.adrianwalker.pseudostreaming.PseudostreamingServlet</servlet-class>
        <init-param>
            <param-name>videoPath</param-name>
            <param-value>/tmp/videos</param-value>
        </init-param>
    </servlet>
    <servlet-mapping>
        <servlet-name>stream</servlet-name>
        <url-pattern>/stream</url-pattern>
    </servlet-mapping>
    <session-config>
        <session-timeout>
            30
        </session-timeout>
    </session-config>
</web-app>

Some simple HTML5 uses the servlet as the source for the video tag. The name of the video files is provided by the video URL parameter.

index.html

<!DOCTYPE html>
<html>
  <head>
    <title>HTML5 Video Pseudostreaming</title>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  </head>
  <body>
    <div>
      <video id="video" controls>  
        <source src="stream?video=video.webm" />  
      </video>
    </div>
  </body>
</html>

You're going to need a video to play, so download a trailer or something:

http://trailers.apple.com/movies/sony_pictures/theamazingspiderman/amazingspiderman-tlr2b-USA_h480p.mov

The QuickTime trailer video file isn't supported by my target browser, so I need to convert it to another format, for this example WebM. ffmpeg can be used for the conversion:

ffmpeg -i amazingspiderman-tlr2b-USA_h480p.mov /tmp/videos/video.webm

Source Code

Usage

Run the project with 'mvn clean install jetty:run-war' and point your brower at http://localhost:8080/pseudostreaming.

C Legs

Every now and again I vow to learn C, and now seems like a good time to have another go.

My plan for learning C is always the same:

  1. Read K&R
  2. ?
  3. Profit

Where step 2 might as well be 'Don't use C and forget everything in K&R'. The problem is that I'm not a systems programmer, so everything I want to program is just easier to do in Java.

This time round I'm having a go with Learn C The Hard Way. It takes a way more modern and pragmatic approach than K&R, and introduces tools like make and valgrind early on.

I'm going to try and not fall back on more familiar languages, and see if I can knock out interesting things in C where appropriate, and blog about them to help me learn.

First off a simple Sudoku solver:

main.c

#include <stdio.h>
#include <stdlib.h>

#define _ 0
#define GRID_SIZE 9
#define SQUARE_SIZE 3
#define FALSE 0
#define TRUE !FALSE

void print(int grid[GRID_SIZE][GRID_SIZE]);
int complete(int grid[GRID_SIZE][GRID_SIZE]);
int contains(int array[GRID_SIZE], int value);
void row(int grid[GRID_SIZE][GRID_SIZE], int rowIndex, int row[GRID_SIZE]);
void column(int grid[GRID_SIZE][GRID_SIZE], int columnIndex, int column[GRID_SIZE]);
void square(int grid[GRID_SIZE][GRID_SIZE], int rowIndex, int columnIndex, int square[GRID_SIZE]);

int main(int argc, char** argv) {

  int grid[GRID_SIZE][GRID_SIZE] ={
    {_, 3, 6, _, 5, _, _, 8, 7},
    {9, _, 1, 7, 8, _, _, 6, 2},
    {_, _, 7, _, _, _, 1, 4, _},
    {_, _, 5, _, 9, _, _, _, 3},
    {_, _, _, _, 1, _, _, _, _},
    {8, _, _, _, 7, _, 6, _, _},
    {_, 2, 9, _, _, _, 5, _, _},
    {5, 7, _, _, 2, 9, 8, _, 6},
    {6, 1, _, _, 3, _, 2, 9, _}
  };

  int rowIndex;
  int columnIndex;
  int value;
  int possibleValue;
  int possibleValueCount;
  int inRow;
  int inColumn;
  int inSquare;
  int tmp[GRID_SIZE];

  while (!complete(grid)) {
    for (rowIndex = 0; rowIndex < GRID_SIZE; rowIndex++) {
      for (columnIndex = 0; columnIndex < GRID_SIZE; columnIndex++) {

        if (grid[rowIndex][columnIndex] != _) {
          continue;
        }

        possibleValue = _;
        possibleValueCount = 0;

        for (value = 1; value <= GRID_SIZE; value++) {

          row(grid, rowIndex, tmp);
          inRow = contains(tmp, value);
          if (inRow) {
            continue;
          }

          column(grid, columnIndex, tmp);
          inColumn = contains(tmp, value);
          if (inColumn) {
            continue;
          }

          square(grid, rowIndex, columnIndex, tmp);
          inSquare = contains(tmp, value);
          if (inSquare) {
            continue;
          }

          possibleValue = value;
          possibleValueCount++;
        }

        if (possibleValueCount == 1) {
          grid[rowIndex][columnIndex] = possibleValue;
        }
      }
    }
  }

  print(grid);

  return (EXIT_SUCCESS);
}

void print(int grid[GRID_SIZE][GRID_SIZE]) {

  int rowIndex;
  int columnIndex;

  for (rowIndex = 0; rowIndex < GRID_SIZE; rowIndex++) {
    for (columnIndex = 0; columnIndex < GRID_SIZE; columnIndex++) {
      if (columnIndex != 0) {
        printf(", ");
      }
      printf("%d", grid[rowIndex][columnIndex]);
    }
    printf("\n");
  }
}

int complete(int grid[GRID_SIZE][GRID_SIZE]) {
  int tmp[GRID_SIZE];
  int rowIndex;
  int inRow;

  for (rowIndex = 0; rowIndex < GRID_SIZE; rowIndex++) {
    row(grid, rowIndex, tmp);
    inRow = contains(tmp, _);
    if (inRow) {
      return FALSE;
    }
  }
  return TRUE;
}

int contains(int array[GRID_SIZE], int value) {

  int i;

  for (i = 0; i < GRID_SIZE; i++) {
    if (array[i] == value) {
      return TRUE;
    }
  }
  return FALSE;
}

void row(int grid[GRID_SIZE][GRID_SIZE], int rowIndex, int row[GRID_SIZE]) {

  int columnIndex;

  for (columnIndex = 0; columnIndex < GRID_SIZE; columnIndex++) {
    row[columnIndex] = grid[rowIndex][columnIndex];
  }
}

void column(int grid[GRID_SIZE][GRID_SIZE], int columnIndex, int column[GRID_SIZE]) {

  int rowIndex;

  for (rowIndex = 0; rowIndex < GRID_SIZE; rowIndex++) {
    column[rowIndex] = grid[rowIndex][columnIndex];
  }
}

void square(int grid[GRID_SIZE][GRID_SIZE], int rowIndex, int columnIndex, int square[GRID_SIZE]) {

  int i;
  int j;

  int x = SQUARE_SIZE * (rowIndex / SQUARE_SIZE);
  int y = SQUARE_SIZE * (columnIndex / SQUARE_SIZE);

  for (i = 0; i < SQUARE_SIZE; i++) {
    for (j = 0; j < SQUARE_SIZE; j++) {
      square[(i * SQUARE_SIZE) + j] = grid[x + i][y + j];
    }
  }
}

Saturday, 28 April 2012

Filtered JTree

The solutions (1, 2) out there for filtering a JTree's nodes weren't suitable for me, so I rolled by own FilteredTreeModel class which wraps a JTree's underlying TreeModel and applies a string filter to the node names.

The tree model recurses over the tree nodes, from the root to the leaf nodes, checking if the nodes toString() value contains the filter value:

FilteredTreeModel.java

package org.adrianwalker.filteredjtree;

import javax.swing.event.TreeModelListener;
import javax.swing.tree.TreeModel;
import javax.swing.tree.TreePath;

public final class FilteredTreeModel implements TreeModel {

  private TreeModel treeModel;
  private String filter;

  public FilteredTreeModel(final TreeModel treeModel) {
    this.treeModel = treeModel;
    this.filter = "";
  }

  public TreeModel getTreeModel() {
    return treeModel;
  }

  public void setFilter(final String filter) {
    this.filter = filter;
  }

  private boolean recursiveMatch(final Object node, final String filter) {

    boolean matches = node.toString().contains(filter);

    int childCount = treeModel.getChildCount(node);
    for (int i = 0; i < childCount; i++) {
      Object child = treeModel.getChild(node, i);
      matches |= recursiveMatch(child, filter);
    }
    
    return matches;
  }

  @Override
  public Object getRoot() {
    return treeModel.getRoot();
  }

  @Override
  public Object getChild(final Object parent, final int index) {
    int count = 0;
    int childCount = treeModel.getChildCount(parent);
    for (int i = 0; i < childCount; i++) {
      Object child = treeModel.getChild(parent, i);
      if (recursiveMatch(child, filter)) {
        if (count == index) {
          return child;
        }
        count++;
      }
    }
    return null;
  }

  @Override
  public int getChildCount(final Object parent) {
    int count = 0;
    int childCount = treeModel.getChildCount(parent);
    for (int i = 0; i < childCount; i++) {
      Object child = treeModel.getChild(parent, i);
      if (recursiveMatch(child, filter)) {
        count++;
      }
    }
    return count;
  }

  @Override
  public boolean isLeaf(final Object node) {
    return treeModel.isLeaf(node);
  }

  @Override
  public void valueForPathChanged(final TreePath path, final Object newValue) {
    treeModel.valueForPathChanged(path, newValue);
  }

  @Override
  public int getIndexOfChild(final Object parent, final Object childToFind) {
    int childCount = treeModel.getChildCount(parent);
    for (int i = 0; i < childCount; i++) {
      Object child = treeModel.getChild(parent, i);
      if (recursiveMatch(child, filter)) {
        if (childToFind.equals(child)) {
          return i;
        }
      }
    }
    return -1;
  }

  @Override
  public void addTreeModelListener(final TreeModelListener l) {
    treeModel.addTreeModelListener(l);
  }

  @Override
  public void removeTreeModelListener(final TreeModelListener l) {
    treeModel.removeTreeModelListener(l);
  }
}

Example Application

JTree before and after filtering

Below is a simple example of how the FilteredTreeModel can be used. The tree is filtered using the value of the text field as characters are typed.

FilteredJTreeExample.java

package org.adrianwalker.filteredjtree;

import java.awt.Container;
import java.awt.GridBagConstraints;
import java.awt.GridBagLayout;
import javax.swing.JFrame;
import javax.swing.JScrollPane;
import javax.swing.JTextField;
import javax.swing.JTree;
import javax.swing.event.DocumentEvent;
import javax.swing.event.DocumentListener;
import javax.swing.tree.DefaultMutableTreeNode;
import javax.swing.tree.DefaultTreeModel;

public final class FilteredJTreeExample {

  public static void main(final String[] args) {
    javax.swing.SwingUtilities.invokeLater(new Runnable() {

      @Override
      public void run() {
        createAndShowGUI();
      }
    });
  }

  private static void createAndShowGUI() {
    JFrame frame = new JFrame("Filtered JTree Demo");
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

    addComponentsToPane(frame.getContentPane());

    frame.pack();
    frame.setVisible(true);
  }

  private static void addComponentsToPane(final Container pane) {
    pane.setLayout(new GridBagLayout());

    JTree tree = createTree(pane);
    JTextField filter = createFilterField(pane);

    filter.getDocument().addDocumentListener(createDocumentListener(tree, filter));
  }

  private static JTree createTree(final Container pane) {
    DefaultMutableTreeNode root = new DefaultMutableTreeNode("JTree");
    FilteredTreeModel model = new FilteredTreeModel(new DefaultTreeModel(root));
    JTree tree = new JTree(model);
    JScrollPane scrollPane = new JScrollPane(tree);
    GridBagConstraints c = new GridBagConstraints();
    c.weightx = 1;
    c.weighty = 1;
    c.fill = GridBagConstraints.BOTH;
    c.gridx = 0;
    c.gridy = 1;
    pane.add(scrollPane, c);
    createTreeNodes(root);
    expandTree(tree);

    return tree;
  }

  private static JTextField createFilterField(final Container pane) {
    JTextField filter = new JTextField();
    GridBagConstraints c = new GridBagConstraints();
    c.weightx = 0;
    c.weighty = 0;
    c.fill = GridBagConstraints.HORIZONTAL;
    c.gridx = 0;
    c.gridy = 0;
    pane.add(filter, c);

    return filter;
  }
  
  private static DocumentListener createDocumentListener(final JTree tree, final JTextField filter) {
    return new DocumentListener() {

      @Override
      public void insertUpdate(final DocumentEvent e) {
        applyFilter();
      }

      @Override
      public void removeUpdate(final DocumentEvent e) {
        applyFilter();
      }

      @Override
      public void changedUpdate(final DocumentEvent e) {
        applyFilter();
      }

      public void applyFilter() {
        FilteredTreeModel filteredModel = (FilteredTreeModel) tree.getModel();
        filteredModel.setFilter(filter.getText());
        
        DefaultTreeModel treeModel = (DefaultTreeModel) filteredModel.getTreeModel();
        treeModel.reload();
        
        expandTree(tree);
      }
    };
  }

  private static void expandTree(final JTree tree) {
    for (int i = 0; i < tree.getRowCount(); i++) {
      tree.expandRow(i);
    }
  }

  private static void createTreeNodes(final DefaultMutableTreeNode node) {
    DefaultMutableTreeNode ab = new DefaultMutableTreeNode("ab");
    DefaultMutableTreeNode cd = new DefaultMutableTreeNode("cd");
    DefaultMutableTreeNode ef = new DefaultMutableTreeNode("ef");
    DefaultMutableTreeNode gh = new DefaultMutableTreeNode("gh");
    DefaultMutableTreeNode ij = new DefaultMutableTreeNode("ij");
    DefaultMutableTreeNode kl = new DefaultMutableTreeNode("kl");
    DefaultMutableTreeNode mn = new DefaultMutableTreeNode("mn");
    DefaultMutableTreeNode op = new DefaultMutableTreeNode("op");
    DefaultMutableTreeNode qr = new DefaultMutableTreeNode("qr");
    DefaultMutableTreeNode st = new DefaultMutableTreeNode("st");
    DefaultMutableTreeNode uv = new DefaultMutableTreeNode("uv");
    DefaultMutableTreeNode wx = new DefaultMutableTreeNode("wx");
    DefaultMutableTreeNode yz = new DefaultMutableTreeNode("yz");

    node.add(ab);
    node.add(cd);
    ab.add(ef);
    ab.add(gh);
    cd.add(ij);
    cd.add(kl);
    ef.add(mn);
    ef.add(op);
    gh.add(qr);
    gh.add(st);
    ij.add(uv);
    ij.add(wx);

    node.add(yz);
  }
}

Source Code

Usage

Build and install the Filtered JTree project, using 'mvn clean install'.

Run the FilteredJTreeExample class, and enter characters in the filter text field.