For a (very) long time I’ve been googling, binging, stackoverflowing, [your-search-engine]ing for a simple yet complete example showing how to implement a one-to-one relationship using Fluent NHibernate.

Fluent NHibernate and lambda expressions as data

If you don’t already know, Fluent NHibernate is a fantastic open-source library to be used in conjunction with NHibernate, a powerful O/RM library for .NET. NHibernate works by reading a (usually) manually created XML file that represents the mapping between the Object Oriented and Relational models. There are obvious annoying problems related to the fact of using this XML file, such as not being refactoring-friendly.

Fluent NHibernate is based on the power and expressiviness of lambda expressions to allow for a concise, strongly-type, refactoring-friendly mappings, that eliminates the need of hand-crafted XML files.

It is a very nice example of a somewhat modern pattern, borrowed from functional programming, now possible in C#: using lambda expressions as data. For more details about such emerging patterns, I strongly recommend you this excelent article on MSDN Magazine.

The problem is that I’ve not yet found an example that fits my needs, and Fluent NHibernate’s documentation is somewhat scarce (a big drawback of Fluent NHibernate, I’d say, specially when using it inside a company). What you will most certainly find is people telling you that you might actually need a many-to-one relationship. No, I was needing a one-to-one relationship, I swear, and couldn’t find a single example on how to correctly implement it with NHibernate and Fluent NHibernate. Note that I have almost no experience with NHibernate without Fluent NHibernate. I’ve never created an XML mapping that was more complex than almost-trivial. Had I had some more experience with it, I might had been able to solve this problem more easily.

So I present here a scenario, similar to the one I was facing, involving a one-to-one relationship and how I managed to implement it with Fluent NHibernate.

The scenario

Let’s say you have a project that deals with Clients. You normally would have a class to represent this entity, such as:

public class Client {

    protected virtual int Id { get; set; }

    public virtual string Name { get; set; }

    /* ... */

}

(note that the protected id and the virtual modifiers are there to please NHibernate; it creates a proxy class around your model class, so it needs to be able to override getters and setters)

Using Fluent NHibernate, you need no XML file to manage the mappings, all you need is this:

using FluentNHibernate.Mapping;

public class ClientMap : ClassMap<Client> {

    Id(x => x.Id);

    Map(x => x.Name);

    /* ... */

}

And that’s it! Should you need to refactor Name and call it, say, FullName, the mapping would be automatically updated accordingly (given that you use any minimally-competent refactoring tool).

Here is the corresponding database (the names are slightly modified, not following the standard Fluent NHibernate convention):

Adding some relationships

With NHibernate you are free to model your domain in the object-oriented world, with all the kinds of relationships you might want, and it will take care of the database for you.

One such relationship is a many-to-one relationship. Let’s say you want to possibly classify your clients according to some Profiles. A client may have one profile, or no profile at all (if you have not yet decided what is his profile). You would have something like this:

public class Client {

    /* ... */

    public virtual Profile Profile { get; private set; }

    /* ... */

}

public class Profile {

    protected virtual int Id { get; set; }

    public virtual string ProfileName { get; private set; }

    /* ... */

}

The mappings would be:

public class ProfileMap : ClassMap<Profile> {

    Id(x => x.Id);

    Map(x => x.ProfileName);

    /* ... */

}

public class ClientMap : ClassMap<Client> {

    /* ... */

    References(x => x.Profile);

    /* ... */

}

And this is the database, as expected:

And that’s all. Should you want, Fluent NHibernate can automatically generate the database for you as well, with one extra line of code on the configuration of the connection to the database.

Simple, huh?

The problem – a one-to-one relationship

Now suppose you have your system running, in production. Everything is fine, not too many bugs (and the ones found not too scary), the business (that partly relies on your software) is running OK.

One day, your boss calls you and (as you can expect) tells you he needs a new feature. Let’s say he needs to gather some more details about clients, about their alimentary habits.

You, as the developer, decide that you shall not modify the whole Client class, adding many alimentary properties to it. You’d rather create a new class AlimentaryHabits. However this data is still part of the client, you just decide to separate the classes not to burden the client.

The same argument applies to the database: you want to create a separate table not to burden the Clients table. Should you want to have two classes but only one table, you can create your mappings using Component(), but I won’t discuss this here since it is already well documented elsewhere.

What we want in the database is two tables, a Clients with its primary key Id, and a AlimentaryHabits table, with a primary key ClientId that is also a foreign key, referring to Client’s primary key:

What you would like to have is a model that looks like this:

public class Client {

    /* ... */

    public virtual AlimentaryHabits AlimentaryHabits

        { get; private set; }

    /* ... */

}

public class AlimentaryHabits {

    public virtual bool LikesPasta { get; set; }

    public virtual bool LikesPizza { get; set; }

    public virtual int AverageDailyCalories { get; set; }

}

This is what we would like to have. But it is not that easy. No. To please NHibernate and allow Fluent NHibernate to correctly create our mappings, we need to change things a bit. And this is my problem, I couldn’t find any example on how to implement this mapping.

The solution

To implement this model and the corresponding fluent mapping, we need to modify things a bit. This is the domain:

public class AlimentaryHabits {

    private int ClientId { get; set; }

    private Client Client { get; set; }



    protected AlimentaryHabits() { }



    public AlimentaryHabits(Client client) {

        Client = client;

    }



    public virtual bool LikesPasta { get; set; }

    public virtual bool LikesPizza { get; set; }

    public virtual int AverageDailyCalories { get; set; }

}

We need two things to satisfy our OR/M solution:

• an id of the same type as the main class; and
• a reference to the main object;

This reference would represent a bidirectional relationship, although we wanted a unidirectional one (you could want something different for your domain). However we could make it private, and it is not even used inside the class, it’s just used by NHibernate. Also, note that now we have two constructors. The public constructor, taking a Client parameter, is the one you will use in your code whenever you want to assign a client some alimentary habits, such as: AlimentaryHabits = new AlimentaryHabits(this);. The protected constructor is used internally by NHibernate, and must be present. You can completely ignore it.

This is the corresponding mapping:

public class AlimentaryHabitsMap : ClassMap<AlimentaryHabits>

{

    Id(Reveal.Property<AlimentaryHabits>("ClientId"))

        .GeneratedBy.Foreign("Client");



    HasOne(

      Reveal.Property<AlimentaryHabits, Client>("Client"))

            .Constrained()

            .ForeignKey();



    Map(x => x.LikesPasta);

    Map(x => x.LikesPizza);

    Map(x => x.AverageDailyCalories);

}

public class ClientMap : ClassMap<Client> {

    /* ... */

    HasOne(x => x.AlimentaryHabits)

        .Cascade.All();

    /* ... */

}

(the Reveal.Property thing is because both ClientId and Client properties are private, and thus not accessible from the mapping class; they will be accessed through reflection by NHibernate)

This model setup, along with this mapping, will create almost the model we initially wanted to, and the exact database representation we wanted!

Conclusion

This involved more effort than I initially thought it would, but now I have a neat solution. And the next time I will need this, it will be easy to implement, following this directions.

If you know a way to simplify this further, or if you like it, or if you have any questions, leave a comment, I’d be glad to further improve this article!

Good luck!

No tags

Project Euler’s problem 24 deals with permutation of symbols.

More specifically, given the initial sequence of symbols (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), it asks its 1.000.000th lexicographic permutation.

The nth lexicographic permutation of a sequence of symbols is defined as the nth element of the lexicographically ordered set of permutations of that symbols.

To help clarify this definition, take for example the symbols (a, b, c). The lexicographically ordered set of permutations is computed by determining all the permutations, and then sorting them according to the lexicographical order (a.k.a. alphabetical order):

1. abc
2. acb
3. bac
4. bca
5. cab
6. cba

So, in this case, the 4th lexicograph permutation of (a, b, c) is “bca”.

A solution to the initial problem is then rather simple to construct in very naive way: list all the (10! = 3628800) permutations, sort them all, and take the 1.000.000th. However this may take a lot of memory and time. And most importantly, for any given sequence of symbols, it can be done in O(1).

The constant-complexity algorithm is rather simple and can be easily implemented in F# as follows:

// You can use your own factorial

// factorial : BigInteger -> BigInteger

let factorial n = Seq.fold ( * ) 1I [ 1I .. n ]



let nthPermutation n (symbols:#seq<'S>) =

    let symbols = new ResizeArray<'S>(symbols)

    let rec aux n acc = function

        | sz when sz = 0I -> acc |> List.rev

        | sz ->

            let sz' = sz - 1I

            let k = factorial sz'

            let i = n / k

            let s = symbols.[int i]

            symbols.RemoveAt(int i)

            aux (n%k) (s::acc) sz'

    aux n [] (BigInteger (symbols.Count))



let problem24 =

    [ 0 .. 9 ]

    |> nthPermutation 999999I // 0-based index!!

This algorithm might be much more powerful than what is needed to solve problem 24, but it is much more generic in nature.

Indeed, it does not generate only lexicographically ordered permutations. The permutationsare generated in an order defined by that of the input sequence. So, let’s say you wanted the 1.000.000th reverse-lexicographic order, you would obtain it as follows:

[ 9 .. -1 .. 0 ] |> nthPermutation 999999I

If you would like the 15th permutation of the sequence (a, 1, b, 2, f, z, 3), you could do:

[ box 'a'; box 1; box 'b'; box 2; box 'f'; box 'z';

  box 3 ]

|> nthPermutation 14I

Finally, this algorithm provides an easy way to obtain random permutations. Simply generate a random integer to be used as the permutation index:

let symbols = [ 0 .. 9 ]



let totalPermutations = 

    symbols

    |> List.length

    |> BigInteger

    |> factorial



open System



let random = new Random(int DateTime.Now.Ticks)

symbols

|> nthPermutation (BigInteger (random.Next(totalPermutations)))

That’s it! I hope this can be useful to someone!

No tags

Hello!

Today in the company I’m working, a colleague was saying he had found a very very strange behaviour in JavaScript. I think he was parsing string representing dates by means of the parseInt function.

The problem is that his strings were like “23/04/2008″, “17/08/2005″, and so on. If you split those strings in the slash character, and then try to parseInt each part obtained, you will end up trying to do a

var day = parseInt("17");

var month = parseInt("08");

var year = parseInt("2005");

For those who would expect to get:

• day = 17,
• month = 8, and
• year = 2005,

they will have a surprise, if you run the script in most browsers. What you will get is:

• day = 17,
• month = 0, and
• year = 2005,

By playing around for less than one minute, you can find out what is happening: JavaScript sees that the string starts with a “0″ and is very smart (sarcasm) and decides to parse it as an octal.

Googling (or Binging, nowadays…) a bit, you will see very old threads on forums discussing this bug. Some people say “JavaScript is broken”, others reply “JavaScript is not broken. RTFM.”, and then the usual flame war is started, people invoking flame war laws, and all.

So, what is really happening here? Who is correct?

The ECMA-262 standard

As tend to I dislike unfounded discussions, my first reaction was to look for a copy of the ECMA-262 standard, which can be downloaded here: http://www.ecma-international.org/publications/standards/Ecma-262.htm.

Page 77, paragraph 15.1.2.2, states the definition of the parseInt function. THAT is authoritative information, isn’t it?

So, the definition of parseInt, which actually takes 2 arguments (string and radix) reads:

The parseInt function produces an integer value dictated by interpretation of the contents of the string argument according to the specified radix. Leading whitespace in the string is ignored. If radix is undefined or 0, it is assumed to be 10 except when the number begins with the character pairs 0x or 0X, in which case a radix of 16 is assumed. Any radix-16 number may also optionally begin with the character pairs 0x or 0X.

As you can see, the standard states that JavaScript plays the smart guy when dealing with strings starting with “0x”, that is, hexadecimal string representation of numbers. Now, where does it say JavaScript should also be smart about octals?

Conclusion: JavaScript is indeed not implemented in the standard way in most browsers nowadays.

Actually, the specs, in the next page, permits implementations to interpret strings beginning by “0″ without and “x” or “X” right after as octals. However, in encourages them to interpret it as decimal. Why would leading browsers diverge from the official recommendations?

Workarounds

A number of simple workarounds are available. First, you can simply use the radix argument and specify it should be 10:

var day = parseInt("08", 10)

Another solution, the one I prefer (and use all the time) when converting strings to numbers is

var day = "08" - 0

Yes, you subtract the INTEGER 0 from a string. To see why it is syntactically correct, you can go the the page 31, section 9.3.1 of the same document and read the ToNumber function, and then read the section 11.6.2 on the page 50, about the subtraction operator. Firstly it converts both operands to numbers with the ToNumber function. After that it calculates the result.

The point is, at leasts in Firefox, the implementation of ToNumber (which deals with “0x” as parseInt) works correctly when dealing with strings such as “08″, and correctly parses it to 8.

Now, I ask: why does Firefox correctly implement ToNumber but gives unexpected results on the parseInt function, when the specs says it is recommended to use base 10?

Comment!

No tags

The last time I presented a method to generate a random permutation of a given list, in linear time, based on another article.

The problem with that approach is that the algorithm used does not provide a uniform distribution of the resulting lists, for a number of reasons. Actually, call the set of the permutations of the input list, the function randPermutateArray is not even surjective! This can easily be verified by noting that the function will always swap the element of index i by another one, of index between 0 and i-1, and thus the last element will always be displaced.

Although this can be desired for some applications, it is definitely not what I need.

A linear, unformly distributed random list permutation algorithm

A function with the desired properties (surjective, uniformly distributed permutations, linear complexity) would be like constructing a list with elements randomly extracted from a source set. The easiest way to achieve this is to use the input array (size n) as the source set, randomly select an index (from 0 up to the last one) and swap it with the last element, and then loop this considering an array of size n-1:

let randPermuteArray a =

    let n = Array.length a

    let rec aux = function

        | 0 -> a

        | k ->

            let i = rand(k+1)

            let tmp = a.[i]

            a.[i] <- a.[k]

            a.[k] <- tmp

            aux (k-1)

    aux (n-1)

As you can see, the key difference is the random index we select. With this approach, every permutation of the input sequence (the input sequence itself as well!) is as likely to be yielded as the others.

At least if your randomness source is really random… but that’s for another article!

No tags

Hello!

I was working on a F# project doing some maths, and I needed a time-efficient way to generate random permutations of the list [0; 1; ...; n ], for a positive integer n.

First attempt

My first attempt was very naive, poor in performance. It’s complexity was O(n²).

Start with a random integer generator:

let rand =

    let rndGen = new System.Random(int System.DateTime.Now.Ticks)

    (fun max -> rndGen.Next(max))

The idea was to randomly extract elements from a “source” and use them to construct the list. The code looks like this:

let randUniqueIntList max =

    let rec aux l s =

        match List.length s with

        | 0 -> l

        | n ->

            let i = rand(n)

            let r = s.[i]

            aux (r::l) (List.filter (fun x -> x <> r) s)

    let l0 = [0 .. (max - 1)]

    aux [] l0

The recursive aux function takes an accumulator list and a source list. It is recursively called roughly max times. The bottleneck in each run of aux is clearly the call to List.filter, which is O(List.length s) in complexity. Therefore, the overall complexity of this function is O(n²)!

More efficient solution

In this thread at hubFS, I was pointed to an article showing an efficient function that randomly permutes an array (using the fact that an array is a mutable structure), as follows:

let randPermutateArray a =

    let n = Array.length a

    for x in 1 .. n do

        let i = n - x

        let j = rand(i)

        let tmp = a.[i]

        a.[i] <- a.[j]

        a.[j] <- tmp

    a

Since I wanted to work only with immutable data in my code, I wrapped that function around another one in order to encapsulate the mutable array, as follows:

let randPermutateList l =

    let a = Array.of_list l

    a |> randPermutateArray |> List.of_array

Voilà, a function to randomly permutate a generic list with O(n) complexity!

To generate the random permutation of [ 0 .. n ], the code is straightforward:

let genRandomIntList n =

    [ 0 .. n ] |> randPermutateList

Can you further improve the algorithm on performance? Comment on it!

No tags