Refactoring an algorithm

I'm trying to re-implement ASP.NET MVC routing rules in C++ for my own MVC application.

Currently the code takes at least O(N) at best case and more if accessing the controller/action inside an unordered_map is not O(1).

I would like my code to prefer a route with a controller that's already in the URI, for instance if the current URI is 'projects/2/show' and I have '[Controller]/[Action]/[ID]/', '[Controller]/[ID]/[Action]/', 'projects/[ID]/[Action]/' and 'projects/[ID]/show' I prefer the last route to be tested for a match first.

My question is how can it be done?

As of now it will iterate through all of the routes and try to match it.

I tried to document the code as much as possible but let me know if something is unclear.

My current code looks like this:

// handlePathChange() is called whenever the URI changes

void MVCApplication::handlePathChange()
{
 // Right now I'm iterating a list (O(N) runtime)
 RoutesListType::iterator iter = routes.begin(); 

 // If there are no routes then something is wrong
 if ( iter == routes.end() )
 {
  log("Error") << "No routes found";
  return;
 }

 bool pageFound = false;

 // iterate until a route matches or until the routes end
 while ( iter != routes.end() ) 
 {
  if ( matches(*iter) )
  {
   pageFound = true;
   break;
  }

  iter++;
 }

 // If a page is not found then log it
 if (!pageFound)
  log("Error") << "404, page at url " << internalPath() << " not found";
}

bool MVCApplication::matches(Route &r)
{
 log("Notice") << "Matching route pattern " << r.getPattern() + " to url " << internalPath();

  // gets the URI
 const string url = internalPath();

 char_separator<char> urlSep("/");
 char_separator<char> patternSep("[]/");

 boost::tokenizer<boost::char_separator<char> > patternTokens(r.getPattern(), patternSep);
 tokenizer<char_separator<char> > urlTokens(url, urlSep);

 int pos = 1;

 bool actionFound = false;

 Route::RouteDefaultsType &defaults = r.getDefaults(); // unordered_set<string, string>
 ControllerMapType &controllers = getControllers(); // unordered_set<string, shared_ptr<Controller> >

 ControllerType currentController; // shared_ptr<Controller>
 Controller::ActionType action; // boost::function that returns a view

 for (tokenizer<char_separator<char> >::iterator pattern_iter = patternTokens.begin(), url_iter = urlTokens.begin(); pattern_iter != patternTokens.end(); ++pattern_iter, pos++)
 {
  if ( url_iter == urlTokens.end() ) // If the number of URI tokens is lower then route tokens seek default values
  {
   if ( *pattern_iter == "Controller" || pos == 1) // Map controller to default
   {
    if ( defaults.find(*pattern_iter) != defaults.end() )
     currentController = controllers[defaults[*pattern_iter]];
    else
    {
     log("Error") << "No default controller found";

     return false;
    }
   }
   else if ( *pattern_iter == "Action" ) // Map action to default
   {
    Route::RouteDefaultsType::const_iterator iter = defaults.find(*pattern_iter);
    if ( iter != defaults.end() )
    {
     if ( currentController->getActions().find(iter->second) != currentController->getActions().end() )
     {
      action = currentController->getActions()[iter->second];
      actionFound = true;
     }
    }
   }
   // Checks whether the hard-coded value in the route is an action or a parameter 
   else
   {
    Route::RouteDefaultsType::const_iterator iter = defaults.find(*pattern_iter);
    // Search for a static action eg. /[Controller]/edit/
    if ( currentController->getActions().find(iter->second) != currentController->getActions().end() ) 
    {
     action = currentController->getActions()[iter->second];
     actionFound = true;
    }
    else // Maps parameters to defualt values
    {
     boost::unordered_map<string, string>::const_iterator iter = defaults.find(*pattern_iter);
     if ( iter != defaults.end() )
      currentController->addParameter(*pattern_iter, iter->second);
    }
   }
  }
  else // Match non-default values
  {
   if ( *pattern_iter == "Controller" || pos == 1) // Match controller
   {
    if ( getControllers().find(*url_iter) != getControllers().end() )
     currentController = controllers[*url_iter];
    else
     return false;
   }
   else if ( *pattern_iter == "Action" ) // Match action
   {
    if ( currentController->getActions().find(*url_iter) != currentController->getActions().end() )
    {
     action = currentController->getActions()[*url_iter];
     actionFound = true;
    }
   }
   // Checks whether the hard-coded value in the route is an action or a parameter
   else 
   {

    if ( currentController->getActions().find(*url_iter) != currentController->getActions().end() )
    {
     action = currentController->getActions()[*url_iter];
     actionFound = true;
    }
    else // If not, as a parameter
     currentController->addParameter(*pattern_iter, *url_iter);
   }

   ++url_iter;
  }
 }
// If controller action found show view
 if ( actionFound )
 {
  if ( currentView )
   root()->removeWidget(currentView);

  currentView = action(); // Perform action
  root()->addWidget(currentView);
 }
 else
 {
  log("Error") << "No action found";
  return false;
 }

 return true;
}

The algorithm is the following:

foreach route:
  if the route matches then: break.

  if number of url tokens < number of route pattern tokens then:
    if pattern token == "Controller" or it is the first token then:
      if the default controller exists then:
        assign it as the current controller.
      else:
        return false
    else if pattern token == "Action" then:
        if the default action exists in the current controller then:
          assign it as the current action.
          set actionFound to true.
    else:
        if the hard-coded action in the routes exists in the current controller then:
          assign it as the current action.
          set actionFound to true.
        else:
          if a default value for this parameter exists:
            add a parameter with a default value and route token as name to the current controller.
  else:
    if pattern token == "Controller" or it is the first token then:
      if the url token matches a controller name then:
        assign it as the current controller.
      else:
        return false
    else if pattern token == "Action" then:
      if the url token matches an action name inside the current controller then:
        assign it as the current action.
        set actionFound to true.
    else:
        if the hard-coded action in the uri token exists in the current controller then:
          assign it as the current action.
          set actionFound to true.
        else:
            add a parameter with a uri token as value and route token as name to the current controller.

if actionFound == true then:
  perform controller action.
  render view.

return actionFound

I would lov开发者_高级运维e for any suggestions for improvements, including in formatting and code structure but mainly in runtime efficiency.

Try posting it on http://refactormycode.com/

That said, a couple of pointers (no pun intended):

• try to keep the lines no longer than 80-120 characters, it gets hard to read when they are so long.
• comment before the line, not after
• the if .. then .. else tree also makes it hard to read. Split it into functions or use functional objects per type.
• typedef templates (boost::tokenizer<boost::char_separator<char> > repeated is unreadable )

Those are only style tips. It's hard to read the code itself with such a structure ;).