TAG | code
Project Euler is an awesome website that I found out about a while back via this question on StackOverflow. Basically, it’s a website that poses a ton of programmer related challenges and it keeps track of the problems that you solve.
The problems start out relatively easy (Add all the natural numbers below one thousand that are multiples of 3 or 5.) and progress all the way to insane (Caradano Triplets and Covex Holes).
I’m on the easy side, I just started working through them tonight and thought it would be cool to post how I build the solution to each problem as I complete them.
Problem 2 is pretty easy:
“Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.”
So first things first, I’ll need to pick a language to use to solve this. I chose javascript simply because it was something I knew I could get running pretty quickly.
Next I’ll need some variables. (note: if you’re not familiar with Fibonacci numbers Wikipedia has an awesome article on them.)
var start = 1, end = 4000000, current = 1, previous = 1, sum = 0, temp = 0;
That should do. I’ve got my start variable (dropping the 0 in favor of more readable code), my end counter, and my “where-am-i” variables: current, previous, temp and my sum variable.
Obviously we’ll need some kind of loop. How about a while loop?
while( current <= end )
{
}
Cool. Now when the loop is running I'll need a way to keep track of the current value, the previous value and I need to add the current value to the sum. So....
while( current <= end )
{
temp = current;
current = current + previous;
sum += current;
previous = temp;
}
And there we hav... Oh Wait!
I overlooked a pretty important part of the problem description: "sum of all the even-valued terms"!!!
So given this new(ish) piece of info my solution end sup being:
var start = 1, end = 4000000, current = 1, previous = 1, sum = 0, temp = 0;
while( current <= end )
{
temp = current;
current = current + previous;
if( current%2 == 0 )
sum += current;
previous = temp;
}
alert(sum);
Download the source code mentioned in this blog post.
A few weeks ago on the StackOverflow podcast, something Jeff said got me thinking. Jeff was discussing how the stackoverflow team implemented their route mappings:
Those routes are… the way we implemented them are actually like decorators. Attributes on the methods. - Jeff Atwood (stackoverflow episode #54)
This instantly piqued my interest and I completely zoned out for the rest of the podcast: caught up in working out the details of how I could do this for my own Asp.net MVC projects.
Coming up with the actual attribute code was easy; writing the code to set up all the Routes using only data defined in by the attribute was tricky.
Being new to attributes, and reflection in general, it took me a few hours until I had a very basic demo working. However, I was really starting to like where it was going.
As a side note: There are lot of “helper” classes and objects in the route attribute project (it feels cluttered to me) and the reason I did this was to make the code in AssemblyExtensions.GetRoutes() easier to read.
After a few nights of Mtn Dew and convenience-store cherry-pie I finished the rough code, tests and demo project (included in this blog post) and I was starting to realize that:
- Using the attributes is more declaritive and it feels cleaner
- Having your route information right above your actions is incredibly useful
- I had no more need to switch back and forth between your controller and the Global.asax.cs
How does it work?
All of the real work for the RouteAttribute is done in the AssemblyExtensions class. This class uses extension methods to augment the System.Reflection.Assembly class with two methods: GetControllers() and GetRoutes().
GetRoutes is the only method that is used by other classes, I made GetControllers public for unit testing.
GetRoutes()
GetRoutes’ first order of business is to make a list of data that it will need to build out all the routes for the assembly it was passed. After thats done GetRoutes will loop through the collected route data, build up each route and add it to the dictionary that will eventually be returned.
namespace CodeImpossible.Mvc.Routing
{
public static class AssemblyExtensions
{
public static BindingFlags ActionFlags =
BindingFlags.Instance |
BindingFlags.Public |
BindingFlags.DeclaredOnly;
public static IList<ControllerMetaData> GetControllers(this Assembly assembly)
{
var controllers = assembly.GetTypes().ToList().FindAll(type =>
{
var isValidController = type.IsClass &&
type.IsPublic &&
type.IsSubclassOf<Controller>();
var hasValidActions = type.GetMethods(ActionFlags).ToList().Any(m =>
{
var valid = false;
if (m.ReturnParameter != null && m.ReturnParameter.ParameterType == typeof(ActionResult))
{
valid = m.GetAttributesOfType<RouteAttribute>().Count > 0;
}
return valid;
});
return isValidController && hasValidActions;
}).Select<Type, ControllerMetaData>((t) => new ControllerMetaData(t)).ToList();
return controllers;
}
public static IDictionary<string, Route> GetRoutes(this Assembly assembly)
{
var Routes = new Dictionary<string, Route>();
var data = (from c in assembly.GetControllers()
from a in c.GetActions()
from r in a.Data
select new
{
ControllerName = c.Name,
ActionName = a.Name,
RouteData = r,
RouteParams = a.Params
}).ToList();
foreach (var r in data)
{
var route = new Route(r.RouteData.RoutePath, new MvcRouteHandler());
route.Constraints = new RouteValueDictionary();
route.Defaults = new RouteValueDictionary(new {
controller = r.ControllerName,
action = r.ActionName
});
if (r.RouteData.RequireRouteParams && r.RouteParams.Count() == 0)
{
throw new MissingRouteParameterException("Unknown", r.RouteData.RoutePath);
}
var missingParams = new List<ParameterMetaData>();
if (r.RouteData.RequireRouteParams)
{
missingParams = (from p in r.RouteParams
where r.RouteData.RoutePath.IndexOf("{" + p.Name + "}") == -1
select p).ToList();
}
if (missingParams.Count > 0)
{
var param = missingParams.First();
throw new MissingRouteParameterException(param.Name, r.RouteData.RoutePath);
}
foreach (var param in r.RouteParams)
{
if (param.Data != null)
{
if (param.Data.DefaultValue != null)
{
route.Defaults.Add(param.Name, param.Data.DefaultValue);
}
if (param.Data.Constraint != null)
{
route.Constraints.Add(param.Name, param.Data.Constraint);
}
}
}
Routes.Add(r.RouteData.Name ?? r.RouteData.RoutePath, route);
}
return Routes;
}
}
}
Getting the Routes into the RouteTable
Slapping route attributes onto your classes and methods is all well and good but it doesn’t mean anything unless we can get those routes into the RouteTable object easliy. Originally I had the code to add the routes looking something like
var routes = Assembly.GetCurrentExecutingAssembly().GetRoutes();
routes.ForEach(r => RouteTable.Add(r));
This, although pretty easy, wasn’t as readible as I wanted. So I added some extension methods to the RouteTable class:
RouteTable.Routes.IncludeRoutesFromAssembly();
I think both of these are much clearer than doing:
RouteTable.Routes.MapRoute("Root",
"",
new { controller = "Test", action = "GetItem", id = 1 });
RouteTable.Routes.MapRoute("Search",
"Search/{id}",
new { controller = "Test", action = "Search", id = 1 });
//.. SNIP ...
Using the RouteAttribute and RouteParamAttribute
In the controller “TestController” below there are three actions: Index, FindByText, and GetItem. Using the RouteAttribute and RouteParamAttribute makes it pretty clear that the routes for FindByText and GetItem are the same but use different RouteContraints.
So a request for /Test/Search/Hello will go to FindByText while /Test/Search/1 will go to GetItem. Also notice how GetItem has a default value of 2 for the id argument.
public class TestController : Controller
{
[Route(RoutePath = "Test")]
public ActionResult Index()
{
return View();
}
[Route(RoutePath = "Test/Search/{query}")]
public ActionResult FindByText(
[RouteParam(Constraint="[a-zA-Z]{1,}")]
string query)
{
return View();
}
[Route(RoutePath = "Test/Search/{id}")]
public virtual ActionResult GetItem(
[RouteParam(Constraint=@"\d{1,}", DefaultValue=2)]
int id)
{
return View();
}
}There is support for binding multiple routes to the same action; just add another Route attribute:
[Route("Products/Search/{id}")]
[Route("Products/{id}")]
public ActionResult GetProductById(int id)
{
return View();
}
Downsides or things I haven’t gotten to yet
Just some gotchas that I think people might raise issue with.
All of your controllers must inherit from the System.Web.Mvc.Controller class
This isn’t really a big deal because if you are using Asp.net MVC then you really should inherit from the Controller class, but for those of you using FubuMVC or another MVC framework this should be easy to change.
Attributes can be ugly
I know a few people out there are against attributes but I think that this is a more than acceptable use because it made the code much easier to understand.
Reflection can be slow
Honestly, when I first started working on this demo I was sort of turned off by the use of Reflection myself. After weighing the possible performance loss against the gains in both readability and maintenance I decided this was definitely worth it. I haven’t performance tested this code so, as always YMMV.
As always, if I screwed up or there is a better way to do this, please let me know in the comments.
Download the source code mentioned in this blog post.
asp.net · c# · code · MVC · Open Source
Due to me being insanely sick this week I’m going to be changing up the format for the Works On My Machine weekly project post for this week.
Instead of presenting a project that I’ve worked on I’d like to highlight some .Net OSS projects / source code that I’ve been working with / looking at lately.
- The More Linq project – An extension library for LinqToObjects run by Jon Skeet.
- MusikCube – Awesome music player that uses SqlLite to allow “smart playlists” (eg. show me all songs that were added this week that have fewer than 4 stars and have been played less than 10 times).
- Moq – IMHO the best mocking framework for .net development.
- Scott Hanselman posted some code on his website a while back about how to Zip Compress your Session and Cache data in Asp.net.
Feel free to send me any code that you come across and I’ll feature it in a future post.
