.Net Regular Expressions – Finding Decimal Numbers that are Divisible by Three

It’s very easy to check a decimal number is divisible by three using a simple DFA with 3 states.

A regex, therefor, is possible, but not too pretty (source):

(?:[0369]|
[147](?:[0369]*[147][0369]*[258])*(?:[0369]*[258]|[0369]*[147][0369]*[147])|
[258](?:[0369]*[258][0369]*[147])*(?:[0369]*[147]|[0369]*[258][0369]*[258])
)*

Example: http://www.rubular.com/r/ZcRDblHg8M

Here’s another approach, using .Net’s stacks as a simple counter:

\b
(?>             # No regrets - don't backtrack on if/else decisions.
    [0369]      # = 0 (mod 3)
    |
    [147]       # = 1 (mod 3)
    (?:         # if possible pop 2, else push 1
        (?<-Sum>){2}|(?<Sum>)
    )
    |
    [258]       # = 2 (mod 3)
    (?:         # if possible pop 1, else push 2
        (?<-Sum>)|(?<Sum>){2}
    )
)+
\b
(?(Sum)(?!)) # Assert nothing's left in the stack

Why? Well, I was bored while I shaved. Luckily, this regex is simple enough for Mono. Working example: http://ideone.com/Yp6Ti (ok, maybe not, mono is missing 111222)

.Net Regular Expressions – Using the Stack State to Understand Numeric Values

It is common knowledge that regular expressions should handle text and not values. A recent stack overflow question got me thinking though – it is possible to use .Net regular expressions to understand numbers or other values while matching the pattern?
Regular expressions can be used to perform numerical tasks, but that is usually when working in unary base.
It turns out this is possible – .Net keeps a stack for every capture of every matched group while matching the pattern, and that state is available for use while matching. The idea is simple: we can represent numbers as depth of the stack, so the number 0 is an empty stack, 6 is a stack with 6 captures, and so forth.

(?>
    (?=[0-9])   # optimization - don't multiply when we don't have a digit.
    # multiply the content of the stack by 10
    # for each item on Stack, push 10 items to a Temp stack.
    (?(Decimal)
        (?<-Decimal>
            (?<Temp>){10}
        )
    ){100000}
    (?(Decimal)(?!))
    # Push all items from Temp back to Stack
    (?(Temp)
        (?<-Temp>
            (?<Decimal>)
        )
    ){100000}
    (?(Temp)(?!))
    # match a digit, and push its value to the stack
    (?:
        0                 |
        1 (?<Decimal>)    |
        2 (?<Decimal>){2} |
        3 (?<Decimal>){3} |
        4 (?<Decimal>){4} |
        5 (?<Decimal>){5} |
        6 (?<Decimal>){6} |
        7 (?<Decimal>){7} |
        8 (?<Decimal>){8} |
        9 (?<Decimal>){9}
    )
)+

The idea is very simple: when we see a new digit, we multiply the depth of the stack by 10, and add the number represented by the new digit. The value of the number can be verified using:

match.Groups["Decimal"].Captures.Count

A curious bit here is the use of the loop to copy stacks:

(?(Temp)
    (?<-Temp>
        (?<Decimal>)
    )
){100000}

I’d expect this to be enough:

(?<-Temp> (?<Decimal>) )*
(?(Temp)(?!))

It turns out the above loop is only executed once, and the condition always fails. It is probably a documented optimization, I’ll look more into that later. As a proof of concept, the workaround should do.

It is even possible to perform basic arithmetic operations on these stacks such as adding, subtracting, multiplying and such from within the regex engine, but that may be a few extra steps too many.
It should go without saying, of course, that regex isn’t a good option here – this is for recreational use. The run time and complexity are far from ideal.

See also:

SharePoint 2010 – Adding Created, CreatedBy, Modified and ModifiedBy to SPMetal’s Generated Classes

By default, SPMetal doesn’t map the Created, Created By, Modified and Modified By fields to it’s generated objects. To remind SPMetal they exist you can easily add them to your parameters XML file (using /parameters:myfile.xml at command line). Of course. You can selectively add where you need it, or add it to Item:

<Column Name="Editor" Member="CreatedBy" />
<Column Name="Author" Member="ModifiedBy" />
<Column Name="Created" />
<Column Name="Modified" />

Also, here’s a template of the SPMetal command:

"%programfiles%\Common Files\Microsoft Shared\Web Server Extensions\14\BIN\spmetal.exe" "/web:http://myserver/someweb/foo" /language:csharp /code:SPFoo.cs /serialization:unidirectional /parameters:FooSPMetalParameters.xml

See also:

.Net Regular Expressions – Finding Acronyms, and Reversing the Stack

A recent Stack Overflow question asked if you could (not should) use regular expressions to find acronyms, specifically of the form “Original Poster (OP)” – words followed by the acronym in parentheses.

Well, my first try was this:

\b((?<Acronym>\w)\w*\W+)+
\((?<-Acronym>\k<Acronym>)+\)
(?(Acronym)(?!))

Seems simple – the first line captures the words and pushes each first letter to the stack. The second line pops and matches it, and the last line makes sure there aren’t any extra letters. Seems nice, but wrong. The first letter on the stack in this case comes from the last word, so it matches a reversed acronym – “Oops, Wrong (WO)”.

What I had to do is to reverse the stack. I came up with this regex:

\b((?<Acronym>\w)\w*\W+)+
(?<=(?<-Acronym>.(?=.*?(?<Reverse>\k<Acronym>)))+)(?(Acronym)(?!))
\((?<-Reverse>\k<Reverse>)+\)
(?(Reverse)(?!))

Now, I’m not sure that’s the best way, but it works nicely. The second line is the only thing interesting – I won’t explain it too much, because nobody is reading it. Basically, I match every letter on the stack, and push it to a second stack. I match a dot for each letter because the engine has trouble matching a zero-width expression multiple times (though it works with {5}, for example, but not + or {1,5} – it only tries one). I can match backwards because I know I had at least that many letters, and can look forward because I’m optimistic – I expect to match these letters later, so if they aren’t there, I might as well fail now.

Source Code

Source code and test cases can be found on GitHub: https://github.com/kobi/RecreationalRegex

.Net Regex – Matching Mixed Balanced Parentheses

Yesterday I got thinking about matching different types balanced parentheses using .net regular expression. I assumed it was similar to matching quotes or a single kind of parentheses, but soon realized it isn’t quite that simple. The main problem is looking into the stack – when I see a closed curly brace, for example, how can I tell the top of the stack has an open one?

A quick search brought up Linguistic Forms’ Regex Balancing Group in Depth, which has a clever approach to the problem in the best use I’ve seen yet to balancing groups, and taught me a few new tricks. I’d recommend reading it. The tl;dr version is this: when I see a closed bracket I look-behind my current position using whatever was matched since the last open bracket, revisit it, and check it again. So, if I see I had a { (by matching it again), I know I should now match a }.

While reading the post I had an interesting idea – who says I must push what I matched to the stack? What if wanted to push an arbitrary string to the stack? When I see an open bracket I really want to push a closing bracket – but how can I?
The trick is to use a look-ahead: find the next occurrence of the character I want to push, and push it:

{(?=.*?(<Stack>}))

Next, when I want to match a closing brace, I already have the right one in stack.
Using this approach, here’s a regex that matches tokens with matching balanced parentheses of 3 different typed:

(
    [^(){}\[\]]+
    | \( (?=[^)]*  (?<Stack> \) ) )
    | \[ (?=[^\]]* (?<Stack> \] ) )
    | \{ (?=[^}]*  (?<Stack> \} ) )
    | \k<Stack> (?<-Stack>)
)+?
(?(Stack) (?!))

Of course, this approach does have limitations – you may not find the character you’d like to push (which might be a good thing – it allows you to fail early). It also gets much trickier if you want to balance something more complicated than constant strings, but that’s another subject.

Happy matching.

Source Code

Source code and test cases can be found on GitHub: https://github.com/kobi/RecreationalRegex

SharePoint 2010 – Using Document Id to Link to a Specific Version

SharePoint 2010 introduces Document Id, which is an easy way to create document permalinks across a SharePoint Site (SPSite), without worrying about changing names and folders.
This is all nice and well, but what if you’ve enabled versioning, and want to link to a specific version?
It is a shame DocIdRedir.aspx does not accept a version as an optional parameter, but a small shame, as it is easy enough to implement your own handler, using the API method DocumentId.FindUrlById. Alternately, you could have done that yourself and used DocumentId.FindUrlsById, find the appropriate SPListItem and find the version url, if you don’t approve of the way FindUrlById does that for you.
My solution is to create another page, much like DocIdRedir.aspx, and have it accept a version and act accordingly (in this case I’ve created an ASHX handler, but it should be just the same):

public void ProcessRequest(HttpContext context)
{
	string docId = context.Request.QueryString["id"];
	string versionLabel = context.Request.QueryString["v"];
	SPSite currentSite = SPContext.Current.Site;
	string url = null;
	try
	{
		url = GetUrlFromID(currentSite, docId, versionLabel);
	}
	catch (Exception ex)
	{
		string message = String.Format("Error finding document by id {0} and version [{1}], {2}"
			, docId, versionLabel, ex.Message);
		SPUtility.TransferToErrorPage(message);
	}

	if (url == null)
	{
		string message = String.Format("Could not find document with id {0} and version [{1}]"
			, docId, versionLabel);
		SPUtility.TransferToErrorPage(message);
	}
	else
	{
		context.Response.Write(url);
	}
}

private string GetUrlFromID(SPSite site, string docId, string version)
{
	//FindUrlById throws an exception if version is empty or null,
	// so I check it here to make sure it works.
	if (String.IsNullOrEmpty(version))
	{
		string[] urls = DocumentId.FindUrlsById(site, docId);
		return urls.Single(); // think about what you do here
	}
	else
	{
		return DocumentId.FindUrlById(site, docId, version);
	}
}

After creating and deploying your package, which is effortless in Visual Studio 2010, instead of using the default permalinks:

/_layouts/DocIdRedir.aspx?ID=GROOVY-10-2

you can use your own handler (you may want a shorter solution name and handler):

/_layouts/mySolution/VersionedDocumentId.ashx?id=GROOVY-10-2&v=2.5

See also:

Using .Net Regex Balancing Groups to Match Words in Fibonacci Lengths

\b
(?<A>\w)+\s+
(?<A>\w)+\s+
(?<-A>\w)+
(?(A)(?!))
\b

The first example captures three words. Besides spaces and word boundaries, the interesting bits read:

  • (?<A>\w)+ – Capture the first and second word. Push each letter to the A stack. A note here is the it might have been more correct to write (?:\w(?<A>))+, so I don’t push a value I don’t use to the stack, but I think the (?<A>\w) is clearer. I could have also compressed it to ((?<A>\w)+\s+){2}, but then it would have been even less readable.
  • (?<-A>\w)+ – On the third word, this will only match as many letters as matched before. An alternative syntax here would be (\w(?<-A>))+.
  • (?(A)(?!)) – Fail the match if there are still letters in the A stack. This one is a must, in case the third word is shorter than the first two.
  • \b – Last but the least, I need to make sure I match at word boundaries.

Note that In the above regex I don’t care if the second word is longer or of equal length to the first. If this is a problem for you, it can be checked using the following pattern. I won’t explain it too much, but the idea here is to push two letters to the B stack for each letter you remove from the A stack:

\b
(?<A>\w)+   # First word
\s+
(?<B-A>(?<B>)\w)+  # Second word - consume all A's, push an extra B
(?(A)(?!))   # Make sure A is finished
(?<B>\w)*    # Add more B's (or none)
\s+
(?<-B>\w)+ # Third word
(?(B)(?!))
\b

Finally, here’s a regex to capture a sequence of words, where the length of each word is equal to the sum of the lengths of the two previous words:

\b
(?:
    (?<A>\w)+   # First word - push each letter
    \s+
    (?=
        (?<A>\w)+  # Second word - push each letter
        \s+
        (?<-A>\w)+ # Third word - pop letters
        (?(A)(?!))
        \b
    )    #Look Ahead
)+
\w+\s+\w+\b #Capture last two words (already looked at them)

This might look a bit strange: I match a single word at a time, and use the look-ahead to check the following two words. The result is a sequence of words whose lengths make a Fibonacci series.

Source Code

Source code and test cases can be found on GitHub: https://github.com/kobi/RecreationalRegex

See Also:
Regex Balancing Group in Depth – An excellent introduction to balancing groups and the basic concepts and tools used in .Net regular expressions.

jQuery UI Datepicker Slow On IE6

Internet Explorer 6 is, unfortunately, still is widely used in corporate environments. I’ve found the jQuery UI (1.7.2) Datepicker too slow on IE6, taking several seconds to display, and another few seconds to hide.

Looking for a solution, I’ve found this thread, suggesting it’s an IE6 bug that caused it to load the same background images dozens of times. The suggested solution, however, didn’t work for me. I came up with a slightly better solution. Simply add this CSS rule to prevent the background images from loading in IE6:

* html .ui-datepicker tbody a {background-image:none !important;}

The next step is to disable animation. The date picker has many elements – animating them is too much work for IE6, resulting in the animation not showing at all – but still delaying the calendar. Wonderful. The solution is to disable the animation for IE6 by setting its duration to 0. You may also want to set the animation to null, because some animations ignore the zero duration. This is done for IE6 only, as there is no need to penalize modern browsers.

$('input.Calendar').datepicker({
           showAnim: jQuery.support.boxModel ? 'drop' : null, // optional
           duration: jQuery.support.boxModel ? 'normal' : ''
        });

Adding Items to a SharePoint List

Ok, a low-tech post this time. I’ve wasted the better part of my last few days battling Share Point permissions. My goal was to write a web part that lets users add an entry to a Share Point list. So, in case you (or me) need users to add items to a list, this could save us a lot of time…
Continue reading

Sending Meeting Requests to Outlook via ASP.NET Mail Message

Numerous programs on my company deal with event registration. Naturally, that involves sending our employees meeting requests. Here’s the best way I’ve found so far for doing that. The long function at the end is from a web-service already in use for a few months.

Meeting Request

Meeting Request

To make these ICS files dynamically, I use the .Net library DDay.iCal. It’s aewsome.
It took some trial and error, but at the end I was able to create events that work well for all versions of Outlook.
Unlike the solutions I’ve found on the web, this one doesn’t use the office interop thing, so I don’t need outlook installed on the server. I’m using a regular SMTP mail message and add the ICS as attachment.

Anyway, assuming you know how to send mails and how to generate the right ICS for your event (we’ll get to that later), this is the way to send it to Outlook:
First the variables:

//init the message with your defaults (from, to, subject, etc)
MailMessage message = initMailMessage();
string iCal = initICal(parameters ...);

And the code that adds the attachment:

//Add the attachment, specify it is a calendar file.
System.Net.Mail.Attachment attachment =
System.Net.Mail.Attachment.CreateAttachmentFromString(
iCal, new ContentType("text/calendar"));
attachment.TransferEncoding = TransferEncoding.Base64;
attachment.Name = "EventDetails.ics"; //not visible in outlook

message.Attachments.Add(attachment);

sendMailMessage(message);

Ok. That’s probably disappointing, since you can’t just copy-paste this code and make it work. I’m including more code you may want to use, but first some rules for the ICS files you’re about to create:

Rules of Thumb

  • Make sure to specify the Method property – should be Publish or Request. Outlook won’t accept the file without it.
  • Add an Organizer – or Outlook 2007 won’t let people save the event.
  • Add the meeting’s subject and description to the ICS file, but also as the mail’s subject and body. Outlook may display either one.

Now for that extra code.
This one is pretty simple – sends an SMTP message:

private static void sendMailMessage(MailMessage mailMessage)
{
string mailHost = "Ask.Someone.com";
SmtpClient smtpClient = new SmtpClient(mailHost, 25);
smtpClient.DeliveryMethod =
   SmtpDeliveryMethod.PickupDirectoryFromIis;
smtpClient.Send(mailMessage);
}

This fine function creates the ICS:

[WebMethod(Description =
   "Send an appointment with much details.")]
public void SendAppointment(string from, string to,
   string title, string body, DateTime startDate,
   double duration, string location, string organizer,
   bool updatePreviousEvent, string eventId,
   bool allDayEvent,
   int recurrenceDaysInterval, int recurrenceCount)
{
  iCalendar iCal = new iCalendar();

  // outlook 2003 needs this property,
  //  or we'll get an error (a Lunar error!)
  iCal.Method = "PUBLISH";

  // Create the event
  Event evt = iCal.Create();

  evt.Summary = title;

  evt.Start = new iCalDateTime(startDate.Year,
    startDate.Month, startDate.Day, startDate.Hour,
    startDate.Minute, startDate.Second);
  evt.Duration = TimeSpan.FromHours(duration);
  evt.Description = body;
  evt.Location = location;

  if (recurrenceDaysInterval > 0)
  {
    RecurrencePattern rp = new RecurrencePattern();
    rp.Frequency = FrequencyType.Daily;
    rp.Interval = recurrenceDaysInterval; // interval of days

    rp.Count = recurrenceCount;
    evt.AddRecurrencePattern(rp);
  }
  evt.IsAllDay = allDayEvent;

  //organizer is mandatory for outlook 2007 - think about
  // trowing an exception here.
  if (!String.IsNullOrEmpty(organizer))
    evt.Organizer = organizer;


  if (!String.IsNullOrEmpty(eventId))
    evt.UID = eventId;

  //"REQUEST" will update an existing event with the same
  // UID (Unique ID) and a newer time stamp.
  if (updatePreviousEvent)
    iCal.Method = "REQUEST";

  // Save into calendar file.
  iCalendarSerializer serializer =
    new iCalendarSerializer(iCal);
  //serializer.Serialize(@"iCalendar.ics");

  string icalData = serializer.SerializeToString();

  //send the iCal data. Also sends the subject and body
  //on the mail.
  SendAppointmentFromICalWithMailTitle(from, to,
    icalData, title, body);
}

See Also: