When life gives you an O(nk) algorithm, it's time to get creative and respond with your own logarithmic algorithm.

At DevResults we do a lot of work with maps. One such activity involves kml shape files of things like countries, states / provinces, cities, etc. While learning how to set up a new site, we grabbed the shape files for the United States off of GADM and started the import process.

An hour later, the process still hadn’t finished the first (and largest) shape file. Something was definitely wrong and so I dug in and found out where the code was stuck at and found that the code was iterating through all the points and combining them together into one big SqlGeography instance via the STUnion method. Below is an example of the code that was doing this

SqlGeography shape = polygons[0];
for (int i = 1; i < polygons.Length; i++) {
	shape = shape.STUnion(polygons[i]);
}

return shape;

When I started searching around for some alternatives to STUnion, I found this graph:

Classic O(nk) problem from the look of it.

Taming the beast

From the graph, we know that we can combine small shapes very quickly, and large shapes take a very long time. This means for our algorithm we want to minimize the number of operations we do on large shapes. With this optimization goal in mind, we can make a divide and conquer algorithm that will combine shapes into increasingly larger shapes where finally at the end we only have two shapes to merge.

First, lets get the implementation out of the way.

public static SqlGeography CombinePolygons(List<SqlGeography> polygons, int start, int end)
{
    if (start > end) return null;
    if (start == end) return polygons[start];

    int midpoint = (start + end) / 2;

    SqlGeography left = CombinePolygons(polygons, start, midpoint);
    SqlGeography right = CombinePolygons(polygons, midpoint + 1, end);

    // if both values have shapes, combine
    if (left != null && right != null)
        return left.STUnion(right);

    // if only one has a shape, pick whichever has a value
    return left ?? right;
}

So, the way this works is it recursively splits the list of polygons until it gets down to two single polygons, unions them together, then returns that shape, which then gets unioned with another, until in the end we have one shape. This means that most of our operations are done on small objects, thus minimizing the large objects we have to merge.

For example, consider 512 polygons.

Operation CountLeft SizeRight Size
25611
12822
6444
3288
161616
83232
46464
2128128
1256256

We can easily see that we are now minimizing the number of operations that we are doing on large shapes.

Reviewing the solution

So how well does this work out? Well the first time I ran this, it never finished the first shape file in over and hour and a half while this algorithm lets me process this shape file in just under 4 minutes. A great result from a simple change in how we process the polygon shapes.

Although there are already other projects that wrap libsass, they don't appear to be maintained anymore, so I fork'd NSass and fixed some of the maintainability problems with it. From that, libsass-net was born.

Introduction

Recently there have been a few bugs that Sassy Studio users have been running into related to libsass that have been fixed for a while, but the wrapper I had been using (NSass) had not been updated in over 6 months. Since NSass was just a fork of libsass and then moved the files, getting the updates from libsass would not be an easy process.

To solve this issue, I created a new project on GitHub and brought in the code using a git submodule which should allow me to very easily grab updates as the roll out and become stable.

Roadmap

Currently, I’m a bit bogged down with a new job and a basement project so right now libsass-net is the bare minimum amount of work that I needed to do to get it working for Sassy Studio. In the somewhat near future I plan on adding support for the following (pull requests welcome):

  • NuGet packages
  • x64 support (currently it works, must a manual process)
  • ASP.NET handler
  • System.Web.Optimization integration
It's that time of the year again when we look back and reflect on what we accomplished during the previous year and set goals for the next year. Here are the highlights from my 2013.

2013 shaped up to be an amazing year. I started blogging again and was able to write about 18 blog posts which is pretty good for not blogging in years. I learned quite a bit of basic German using Memrise and Duolingo while running on the treadmill during my lunch break. I also went through a lot of interviews, some that turned out really well, others that didn’t turn out so great.

In the development realm, I learned about Sass and began to use it in production. I made Sassy Studio, my first Visual Studio extension that helped me out with all the work I was doing with Sass. At the time of writing, Sassy Studio has been downloaded over 4,300 times!

I also made murmurhash-net which helped me overcome some performance and storage problems we hit with SHA1. This also happens to be my first NuGet package, which was fun to do as well.

On the non-technical side, I read all of the Ender’s Game series and started the Ender’s Shadow series. I also started reviewing an upcoming technical book about Visual Studio 2013.

A new year and a new job

After 8 years, I’ll be leaving my post as lead developer at hh2 and moving on to DevResults. It’s kind of crazy to be moving into a different industry, but I’m really excited about the new tasks that await me and I’m looking forward to seeing what impact I can make in the international development and humanitarian communities.

I’m also excited about keeping focussed on Sassy Studio both on resolving issues and adding new features. Hopefully I’ll be able to refactor major portions of the SassyStudio code into a full-blown Sass compiler.

On the side of things I’m not looking forward to, but definitely am going to get accomplished, this year will be the year that I get my dog new hips to fix her hip displaysia which will hopefully let her live a pain free rest of her life.

Goodbye 2013, hello 2014

As with everything, I hope this year we can all live in the present but be mindful of all the things we learned in 2013. Happy new years everyone!

It’s been a little while since the last blog talking about what’s new in SassyStudio there has been a lot of new features.

Nested Property Intellisense

The major new feature in v0.8 is smarter css property intellisense for nested properties. Consider the following style, you will now get intellisense suggesting values like family and weight when in the font block.

body {
	font: {
		size: 14px;
	}
}

Format Document support

There is some basic support for automatically formatting a document. Right now, it only supports fixing indentation issues, and the indentation options are configurable in the same place as all other languages (Tools > Options > Text Languages > SCSS). Thanks to @Unt1tled for requesting this.

Compilation of file when dependent document changed

Now when you modify a document that is imported by another root level document, the root document will be generated. This was a long overdue feature and I’d like to thank @funzeye for requesting it.

Basic Compass Support

If you are a compass user, you’ll be glad to know that SassyStudio now bootstraps compass and will use it to generate your css files when you save them. All you need to do to enable support for compass is to provide the path to your ruby installation path in the options (Tools > Options > SassyStudio > Ruby Install Path). Thanks to @okoetter for requesting this.

Various Intellisense / Parsing Improvements

As usual there have been some various bug fixes.

  • Fix CSS intellisense not working when only VS2013 installed
  • Fix @if directive not parsing correctly when immediately followed by (
  • Improve CSS property detection and fix properties declarations not followed by a space not being highlighted correctly
  • Fix incorrect highlighting after using comment/uncomment selection command

Moving Forward

As usual, I’ll keep enhancing the existing functionality and work on adding more intellisense support. I’ll continue tweaking intellisense to get it to the point where I feel comfortable enough enabling it by default. If you find anything broken or confusing, please feel free to reach out to me on Twitter or file an issue on GitHub.

The first SassyStudio specific feature is support for the functionality to get intellisense in other files without the using the @import directive.

Update: Looks like the LESS functionality in visual studio supports the same syntax as this, which is awesome! Originally I was using the attribute file but have since updated it to use the attribute path to match.

With large applications you’ll typically find yourself breaking your SCSS files into logical groups, typically centered around functional components. This is clean and efficient, but you lose intellisense when you do… until now.

To accomplish this, I have started support for the reference tag in a triple slash (///) comment. An example of this would be

/// <reference path="variables" /> 

To get intellisense for multiple files, just add multiple references

/// <reference path="variables" />
/// <reference path="mixins" />

The reference tag works the same as a @import statement, and it can serve as documentation for what files the current file you are working on depends on.

If you have any other ideas for what you would like to see supported in SassyStudio, please feel free to submit a feature request on GitHub