DZone Snippets: Drmaciver's Code Snippets

Statically enforced range types in scala

DRMacIver (David R. MacIver) — Tue, 11 Dec 2007 22:42:26 GMT

Cute piece of code for statically checking array index accesses.



package ranges;



class Range(val start : Int, val end : Int){

  if (start >= end) throw new IndexOutOfBoundsException();



  def checkRange(min : Int, max : Int){

    if (min < start || max > end) throw new IndexOutOfBoundsException();

  }



  def inBounds(x : Int) : Index = unsafeFromInt(Math.min(end - 1, Math.max(x, start)));

  def checkBounds (x : Int) : Index = if (x < start || x >= end) throw new IndexOutOfBoundsException() else unsafeFromInt(x);



  private[Range] def unsafeFromInt (i : Int) = Index(i); // Separated into a method for refactoring and unsafe declaration.



  val range = start until end;

  val length = end - start;



  val maxIndex = unsafeFromInt(end - 1);

  val minIndex = unsafeFromInt(start);

  val indices = range.map(unsafeFromInt(_));



  trait Slice[T] extends Iterable[T] {

    def apply(i : Index) : T = unsafeApply(i);     

    def update(i : Index, t : T) = unsafeUpdate(i, t);



    private[Range] def unsafeApply(i : Int) : T;

    private[Range] def unsafeUpdate(i : Int, t : T) : Unit;



    def elements = range.elements.map(unsafeApply(_)); 

  } 



  class ArraySlice[T](array : Array[T]) extends Slice[T]{

    if (length < end) throw new IndexOutOfBoundsException();

    private[Range] def unsafeApply(i : Int) = array(i);

    private[Range] def unsafeUpdate(i : Int, t : T) : Unit = array(i) = t;



    override def foreach(f : T => Unit) = for (val i <- range) array(i);

  }



  class CheckedArray[T] extends Slice[T]{

    private val array = new Array[T](length);

    

    private[Range] def unsafeApply(i : Int) = array(i - start);

    private[Range] def unsafeUpdate(i : Int, t : T) : Unit = array(i - start) = t;

    

    override def foreach(f : T => Unit) = array.foreach(f);

  }



  implicit def toInteger(i : Index) = i.toInt;



  case class Index private[Range] (val toInt : Int){

    def max(y : Index) = unsafeFromInt(Math.max(this, y));

    def min(y : Index) = unsafeFromInt(Math.min(this, y));

    def mid(y : Index) = unsafeFromInt((this + y) >>> 1);

    def opposite = unsafeFromInt(end + start - 1 - this);

  }; 

}

Creating a circular reference between two objects in Java

DRMacIver (David R. MacIver) — Wed, 22 Aug 2007 22:03:41 GMT

This is in some sense the 'right' way of doing it as far as I can figure. Nothing else I've been able to come up with works even close to as well.



public class LazyModules 

{

  static int i = 0;



  static abstract class A{

    abstract B getB();

    int k = i++;

    public String toString() { return "" + k; }

  }



  static abstract class B{

    abstract A getA();

    int k = i++;

    public String toString() { return "" + k; }

  }



  public static void doStuff(A foo, B bar){

    System.out.println("foo = " + foo);

    System.out.println("foo.b = " + foo.getB());

    System.out.println("bar = " + bar);

    System.out.println("bar.a = " + bar.getA()); 

  }



  public static void main(String[] args){

    new Object(){

      final A foo = new A() { B getB() { return bar; }  };

      final B bar = new B() { A getA() { return foo; }  };



      { doStuff(foo, bar); }

    };

  }

}

Haskell Regular Expression Matcher

DRMacIver (David R. MacIver) — Sun, 19 Aug 2007 20:57:56 GMT

Basic implementation of Regular Expressions based on "Derivatives of Regular Expressions" by Janusz A. Brzozowski (Journal of Association for Computing Machinery, October 1964)

Not really intended for serious use. Just a proof of concept.



module Regexp

where



import Data.Set (Set)

import Data.Map (Map)

import Monad

import List

import Maybe

import qualified Data.Set as Set

import qualified Data.Map as Map



data Regexp = 

    Zero

  | Match Char       -- matches a single char

  | Not Regexp       -- matches the negation of its argument

  | Prod [Regexp]    -- matches a concatentation of its arguments

  | Sum (Set Regexp) -- matches either of its arguments

  | Star Regexp      -- matches repetitions of its argument (including 0 repetitions)

  deriving (Eq, Ord)



instance Show Regexp where

  show Zero = "0"

  show (Match c) = [c]

  show (Not x)   = '~' : show x

  show (Prod x) = join . (map show)  $ x

  show (Sum x) = "(" ++ ( join . intersperse "|" . (map show) . Set.toList $ x ) ++ ")"

  show (Star x) = "(" ++ show x ++ ")*" 



-- Flagrant abuse of type classes to allow implicit conversion of datatypes into regular

-- expressions.

class Match a where

  match :: a -> Regexp



instance Match Char where

  match c = Match c



instance (Match a) => Match [a] where

  match = con



instance Match Regexp where

  match = id



-- "smart" versions of the constructors, which perform normalisation of the datatype.

-- As long as all regular expressions are built up using these and the match instance

-- for char we can guarantee that structural equality of terms == similarity.

-- This is important to make sure we only generate a finite number of states.

zero :: Regexp 

zero = Zero 



one :: Regexp

one = Prod []



(<+>) :: (Match a, Match b) => a -> b -> Regexp

x <+> y = 

  case (match x, match y) of

    (Zero, b)      -> b

    (a, Zero)      -> a

    (Sum a, Sum b) -> Sum (Set.union a b)

    (Sum a, b)     -> Sum (Set.insert b a)

    (a, Sum b)     -> Sum (Set.insert a b)    

    (a, b)         -> Sum $ Set.fromList [a, b]

  

oneOf :: (Match a) => [a] -> Regexp

oneOf = foldr (<+>) zero



(<*>) :: (Match a, Match b) => a -> b -> Regexp

u <*> v = 

  case (match u, match v) of 

    (Zero, _)         -> zero

    (_, Zero)         -> zero

    (Prod x, Prod y)  -> Prod (x ++ y)

    (Prod x, y)       -> Prod (x ++ [y])

    (x, Prod y)       -> Prod (x : y)

    (x, y)            -> Prod [x, y]



con :: (Match a) => [a] -> Regexp

con = foldr (<*>) one



neg :: (Match a) => a -> Regexp

neg x = 

  case (match x) of

  (Not y) -> y

  y       -> Not y



star :: (Match a) => a -> Regexp

star x =

  case (match x) of

    (Zero)   -> Zero

    (Star y) -> Star y

    y        -> Star y



-- Returns if the regex matches the empty string.

del :: Regexp -> Bool

del (Zero)    = False

del (Sum x)   = or . map del $ Set.toList x

del (Prod x)  = and . map del $ x

del (Match _) = False

del (Not x)   = not $ del x;

del (Star _)  = True



-- The derivative of a regular language A with respect to a character

-- c is dA/dc = { s : cs \in A } 

diff :: Char -> Regexp -> Regexp

diff _ (Zero)  = zero

diff c (Match d) | (c == d) = one

diff c (Match d) = zero

diff c (Sum x) = oneOf $ (map $ diff c) (Set.toList x)

diff c (Prod []) = zero

diff c (Prod (x:xs)) | del x = (diff c x <*> xs) <+> diff c (Prod xs)

diff c (Prod (x:xs)) = diff c x <*> xs

diff c (Not x) = Not (diff c x)

diff c (Star x) = diff c x <*> Star x



flattenSet :: (Ord a) => Set (Set a) -> Set a

flattenSet = Set.fold Set.union Set.empty



(/>>=) :: (Ord a, Ord b) => Set a -> (a -> Set b) -> Set b

x />>= f = flattenSet (Set.map f x)



-- The alphabet of all characters that appear in this regexp

alphabet :: Regexp -> Set Char

alphabet (Zero) = Set.empty

alphabet (Sum x) = flattenSet (Set.map alphabet x) 

alphabet (Prod x) = Set.unions $ map alphabet x

alphabet (Not x) = alphabet x

alphabet (Star x) = alphabet x

alphabet (Match c) = Set.singleton c



-- Set of all derivatives of a regular expression (including itself, and higher order derivatives).

derivatives :: Regexp -> [Regexp]

derivatives exp = Set.toList $ enlarge (Set.singleton exp) (Set.singleton exp) 

  where

    alpha = alphabet exp

    firstDerivatives x = Set.map (`diff` x) alpha 

    enlarge :: Set Regexp -> Set Regexp -> Set Regexp

    enlarge new found = 

      if Set.null new

        then found

        else

          let nextNew   = (new />>= firstDerivatives) Set.\\ found

              nextFound = found `Set.union` nextNew

          in enlarge nextNew nextFound



-- A simple finite state machine type 

data FSM = State { transitions :: (Map Char FSM), isFinal :: Bool } 



-- Converts a Regexp into a finite state machine by using the derivatives

-- with respect to specific characters as the transitions. Essentially at 

-- each stage we build up a regular expression that the remaining characters

-- have to match. Due to Cunning Mathematics, only finitely many such regular

-- expressions (up to similarity) result.

compile :: Regexp -> FSM

compile x = fromJust $ Map.lookup x states

  where

    states :: Map Regexp FSM

    states = Map.fromList $

      do re <- derivatives x -- Totally gratuitious use of list monad. :)

         let trans = do c <- Set.toList $ alphabet re

                        let d = diff c re

                        return (c, fromJust $ Map.lookup d states)

         let state = State (Map.fromList trans) (del re) 

         return (re, state) 



runFSM :: FSM -> String -> Bool

runFSM x []     = isFinal x

runFSM x (c:cs) = case (Map.lookup c $ transitions x) of

                    Nothing -> False

                    Just y  -> runFSM y cs

               

matches :: (Match a) => String -> a -> Bool

matches cs exp = runFSM (compile $  match exp) cs

Simple CharMap based on a Radix binary tree

DRMacIver (David R. MacIver) — Thu, 02 Aug 2007 15:07:55 GMT

Very simple Java implementation of a map from characters to objects based on a radix tree.

It's not actually that fast, as I've not bothered to optimise it at all (a brief attempt didn't work very well and I lost interest after that). It seems to be a little slower than a HashMap using boxed Characters and a little faster than a TreeMap (when the JIT gets up to speed anyway. Before the JIT has done any optimisation the hashmap is 2 or 3 times faster). I might at some point implement a HashMap using unboxed characters for keys to see what kind of performance improvement it gives.

Using a large array is of course faster than all of the options by an order of magnitude, but has the downside of being a bit too large to be useful. :-)



public class RadixCharMap

{

    private RadixCharMap map0; 

    private RadixCharMap map1;

    private T value;

    

    private RadixCharMap getMap(int i){

        if (i > 0) return map1 == null ? (map1 = new RadixCharMap()) : map1;

        else return map0 == null ? (map0 = new RadixCharMap()) : map0;}    

    

    public RadixCharMap put(char key, T value){

        if (key == '\0') this.value = value;

        else getMap(key & 1).put((char)(key >> 1), value);

        return this;}

    

    public T get(char key){

        RadixCharMap current = this;

        if (key == '\0') return this.value;

        else return getMap(key & 1).get((char)(key >> 1));}

}

Simple Haskell script for word counting

DRMacIver (David R. MacIver) — Thu, 05 Jul 2007 13:52:45 GMT

This is just a simple piece of code I put together to play with some Haskell when I realised I've not been writing nearly enough of the stuff.

It reads text from stdin and prints the words it finds together with how many times each one occurred.



module Main

where



import List

import Control.Arrow



type Comparator a = (a -> a -> Ordering)



ascending :: (Ord a) => (b -> a) -> Comparator b

ascending f x y = compare (f x) (f y)



descending :: (Ord a) => (b -> a) -> Comparator b

descending = flip . ascending



secondary :: Comparator a -> Comparator a -> Comparator a

secondary f g x y = case f x y of {

                    EQ -> g x y;

                    z  -> z; }



-- Returns a list of unique elements together with their frequency. Listed in decreasing order of frequency, followed by

increasing order of the elements.

count :: (Ord a) => [a] -> [(a, Int)]

count = map (head &&& length) . sortBy (descending length `secondary` ascending head) . group . sort



main :: IO ()

main = interact $ unlines . map (\(x, y) -> (take 20 $ x ++ repeat ' ')  ++ " : " ++ show y) . count . words

Putlines in Haskell

DRMacIver (David R. MacIver) — Sat, 12 May 2007 15:17:04 GMT

This is an illustrative example of

a) Point free style
b) How Haskell IO works.

If you don't understand Haskell IO, it might be helpful to try and unpick the definition here to see how it works. :-)



import System



main :: IO ()

main = getArgs >>= sequence_ . (map putStrLn)

Goto in Java

DRMacIver (David R. MacIver) — Fri, 13 Apr 2007 08:01:42 GMT

After my C finite state machine, I figured I'd sink to new levels of depravity by figuring out how to write GOTO in Java. Here's the result.

Usual disclaimer about "if you use this code then the baby Jesus will cut kittens".

Update: Thanks to roots_ on freenode ##java for the suggestion of using a do { } while(false) instead, and cybereal for pointing out that I didn't need the label.



public class Goto

{

    public static int END = Integer.MAX_VALUE;



    public static void main(String[] args)

    {

        int _goto = 0;



        do

        {

            switch(_goto)

            {

                case 0:

                case 1:

                    System.out.println("Foo");

                    _goto = 3;

                    continue;

                

                case 2:

                     System.out.println("Baz");

                    _goto = END;

                    continue;

                case 3:

                     System.out.println("Bar");

                    _goto = 2;

                    continue;

             }

        } while(false)

    }

}

Simple finite state machine in C

DRMacIver (David R. MacIver) — Tue, 10 Apr 2007 17:28:00 GMT

I'm vaguely plotting a finite state machine -> C compiler (as toy code, not for a serious project - I know there are plenty already out there), so thought I'd write a sample one by hand to see how it should look. Here's the code for it.

This checks if stdin contains the phrase 'foo' or 'bar'



#include 



main()

{

    int c;



    START: 

        switch(c = getchar()){

            case 'f' : goto F;

            case 'b' : goto B;

            case EOF : goto FAIL;

            default: goto START; }



    F:

        switch(c = getchar()){

            case 'o' : goto FO;

            case EOF : goto FAIL;

            default  : goto START;}

    

    FO:

        switch(c = getchar()){

            case 'o' : goto SUCCESS;

            case EOF : goto FAIL;

            default  : goto START;}



    B:

        switch(c = getchar()){

            case 'a' : goto BA;

            case EOF : goto FAIL;

            default  : goto START;}



    BA:

        switch(c = getchar()){

            case 'r' : goto SUCCESS;

            case EOF : goto FAIL;

            default  : goto START;}



    FAIL: 

        printf("Does not match.\n");

        return;

    SUCCESS:

        printf("Matches.\n");

        return;

}

Non-code snippet: Licensing

DRMacIver (David R. MacIver) — Thu, 05 Apr 2007 07:30:18 GMT

I've just realised that I should really be worrying about licensing more than I do.

So, in the unlikely event that you want to use any of my code on here, it should be considered to be released under a WTFPL. Do what you please with it.

Class for faking Using in Java

DRMacIver (David R. MacIver) — Fri, 30 Mar 2007 11:28:13 GMT

This is a class for faking the 'using' syntax in Java. The idea is that you subclass it to provide your resource initialisation and finalisation code, providing protected final methods for resource access you don't want to be publically available. Users then create an anonymous inner class that overrides the body() method and has access to these resources only within the method. Sensitive resources should throw an exception if invoked when isLive returns false.

Now updated to include significantly less evil. (It no longer needs the _return method...)



public abstract class Use

{

        private boolean live = false;



        protected final void isLive()

        {

            return live;

        } 



	/**

	 * Override this to provide initialisation code for this Use class. This will always be called before

	 * the body is executed.

	 */

	protected void start()

	{

	}



	/**

	 * Override this to provide finalisation code for this Use class. This will always be called at the end

	 * of use() execution.

	 */

	protected void finish()

	{

	}



	/**

	 * The body of the code to execute. Returning a value from this should execute _return(T value).

         */

	protected abstract T body();



	/**

	 * Returns body(), or null if this was never invoked. This will call

	 * all neccessary initialisation and finalisation code.

 	 */

	public final T use()

	{

		try

		{

			start();

                        live = true;



			return body();

		}

		finally

		{

                        live = false;

			finish();

		}

	}



}