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);
  }; 
}

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); }
    };
  }
}

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

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<T>
{
    private RadixCharMap<T> map0; 
    private RadixCharMap<T> map1;
    private T value;
    
    private RadixCharMap<T> getMap(int i){
        if (i > 0) return map1 == null ? (map1 = new RadixCharMap<T>()) : map1;
        else return map0 == null ? (map0 = new RadixCharMap<T>()) : map0;}    
    
    public RadixCharMap<T> 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));}
}

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

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) 

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

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 <stdio.h>

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;
}

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.

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<T>
{
        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();
		}
	}

}