重构算法 [英] Refactoring an algorithm
问题描述
我正在尝试为自己的MVC应用程序在C ++中重新实现ASP.NET MVC路由规则.
当前,在最佳情况下,代码至少需要 O(N),如果访问unordered_map内部的控制器/动作不是 O(1),则代码会花费更多.
我希望我的代码更喜欢使用URI中已有控制器的路由,例如,如果当前URI为'projects/2/show'并且我具有'[Controller]/[动作]/[ID]/','[控制器]/[ID]/[动作]/','项目/[ID]/[动作]/'和'projects/[ID]/show',我更喜欢先测试最后一条路线是否匹配.
我的问题是怎么做?
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.
// 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;
}
算法如下:
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 love for any suggestions for improvements, including in formatting and code structure but mainly in runtime efficiency.
推荐答案
尝试将其发布在 http://refactormycode.com/
也就是说,有几个指针(不是双关语):
That said, a couple of pointers (no pun intended):
- 尝试将行数保持在80-120个字符以内,当它们太长时,很难阅读.
- 在行前而不是行后 发表评论
- if .. then .. else树也使它难以阅读.将其拆分为功能或按类型使用功能对象.
- typedef模板(重复的
boost::tokenizer<boost::char_separator<char> >
不可读)
- 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 ;).
这篇关于重构算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!