BorlandTalk.com Borland discussion newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Sort valiation rules - how should a function handle an incon Goto page 1, 2  Next          BorlandTalk.com Forum Index -> Delphi Language BASM View previous topic :: View next topic   Author Message Avatar Zondertau Guest Posted: Sun Oct 02, 2005 5:56 pm    Post subject: Sort valiation rules - how should a function handle an incon Currently the Sort B&V tests if the sort function survives an inconsistent compare function (validator 3). I think a good sort function should be able to cope with this. Aleksander doesn't agree with this, since he thinks more optimization is possible if the sort function can assume the compare function is consistent. I think we should vote on a rule for this. 1) A sort function should execute successfully for any compare function. 2) A sort function may raise an exception (including EAccessViolation) when passed an invalid compare function, but must still terminate on every compare function. 3) A sort function may raise an exception or go into an infinite loop or infinite recursion state when passed an invalid compare function (so basically the result would be undefined). I vote for (1). I would also like to add that i sometimes use a random compare function to get an easy implementation of a good list shuffle function. If we choose to allow failure for inconsistent compare functions we should agree what a consistent compare function is. It seems to me that a consistent compare function has these properties: A) Result of Compare(A, B) is the same everytime B) Compare(A, A) = 0 C) If Compare(A, B) > 0 then Compare(B, A) < 0 If Compare(A, B) = 0 then Compare(B, A) = 0 If Compare(A, B) < 0 then Compare(B, A) > 0 D) If Compare(A, B) > 0 and Compare(B, C) > 0 then Compare(A, C) > 0 If Compare(A, B) > 0 and Compare(B, C) = 0 then Compare(A, C) > 0 If Compare(A, B) = 0 and Compare(B, C) > 0 then Compare(A, C) > 0 If Compare(A, B) < 0 and Compare(B, C) < 0 then Compare(A, C) < 0 If Compare(A, B) < 0 and Compare(B, C) = 0 then Compare(A, C) < 0 If Compare(A, B) = 0 and Compare(B, C) < 0 then Compare(A, C) < 0 If Compare(A, B) = 0 and Compare(B, C) = 0 then Compare(A, C) = 0 If anyone disagrees with this definition please say so. Back to top Pierre le Riche Guest Posted: Sun Oct 02, 2005 6:16 pm    Post subject: Re: Sort valiation rules - how should a function handle an i Quote: 1) A sort function should execute successfully for any compare function. 2) A sort function may raise an exception (including EAccessViolation) when passed an invalid compare function, but must still terminate on every compare function. 3) A sort function may raise an exception or go into an infinite loop or infinite recursion state when passed an invalid compare function (so basically the result would be undefined). I vote 3. Invalid compare function = broken compare function. I don't think we should have to cater for bugs in other parts of the application. Back to top Aleksandr Sharahov Guest Posted: Sun Oct 02, 2005 6:31 pm    Post subject: Re: Sort valiation rules - how should a function handle an i I vote 3: A sort function may raise an exception or go into an infinite loop -- regards Aleksandr Back to top John Herbster Guest Posted: Sun Oct 02, 2005 7:41 pm    Post subject: Re: Sort valiation rules - how should a function handle an i "Avatar Zondertau" wrote Quote: ... 3) A sort function may ... or go into an infinite loop or infinite recursion state when passed an invalid compare function ... If implemented, this possibility would make for a lot of work on the part of programmers and support staff quite a few questions to be answered in the news groups. --JohnH Back to top John Herbster Guest Posted: Sun Oct 02, 2005 7:46 pm    Post subject: Re: Sort valiation rules - how should a function handle an i "Avatar Zondertau" wrote Quote: ... 3) A sort function may ... or go into an infinite loop or infinite recursion state when passed an invalid compare function ... If implemented, this possibility would cause a lot of work on the part of programmers and support staff and quite a few difficult questions to be answered in the newsgroups. --JohnH Back to top Anders Isaksson Guest Posted: Sun Oct 02, 2005 7:49 pm    Post subject: Re: Sort valiation rules - how should a function handle an i Avatar Zondertau wrote: Quote: 3) A sort function may raise an exception or go into an infinite loop or infinite recursion state when passed an invalid compare function (so basically the result would be undefined). I think this is the only thing we can ever guarantee about a program. It may work, and it may not. The sort function cannot analyze the compare function, only trust it. If the user supplied compare function AV:s this should definitely not be handled or revamped into something else by the sort function. Of course it would be good if the sort function could solve The Halting Problem, but I doubt it... -- Anders Isaksson, Sweden BlockCAD: http://web.telia.com/~u16122508/proglego.htm Gallery: http://web.telia.com/~u16122508/gallery/index.htm Back to top Avatar Zondertau Guest Posted: Mon Oct 03, 2005 6:26 am    Post subject: Re: Sort valiation rules - how should a function handle an i Quote: 3) A sort function may raise an exception or go into an infinite loop or infinite recursion state when passed an invalid compare function (so basically the result would be undefined). I think this is the only thing we can ever guarantee about a program. It may work, and it may not. The sort function cannot analyze the compare function, only trust it. If the user supplied compare function AV:s this should definitely not be handled or revamped into something else by the sort function. Of course it would be good if the sort function could solve The Halting Problem, but I doubt it... This is not a Halting Problem situation. The sort function could use an algorithm that terminates regardless of the compare function. It could also explicitly check the boundaries of the array to avoid access violations. Back to top Avatar Zondertau Guest Posted: Mon Oct 03, 2005 6:30 am    Post subject: Re: Sort valiation rules - how should a function handle an i Quote: I vote 3: A sort function may raise an exception or go into an infinite loop This would mean we'd also have to agree on criteria for a consistent compare function and include this into the specification for our function. Someone should also analyze the RTL function to see what can be the worst that happens when it is passed an inconsistent sort function. IMO the Fastcode sort should not be less secure than the RTL sort. Back to top Eric Grange Guest Posted: Mon Oct 03, 2005 7:40 am    Post subject: Re: Sort valiation rules - how should a function handle an i I vote 2). Sort methods/functions implemented in the VCL follow 3), to implement 1) you would have to limit yourself to sorting algorithms with an execution path independant from the data (like BubbleSort) or implement a lot of extra comparisons. However "pure" infinite loop should be avoidable all the time, meaning that the worst you might be faced with would be infinite recursion and going out of stack space or a bounds check failure, which are exceptions, and thus fall under 2) Eric Back to top Aleksandr Sharahov Guest Posted: Mon Oct 03, 2005 7:46 am    Post subject: Re: Sort valiation rules - how should a function handle an i Hi Avatar, Quote: I vote for (1). I would also like to add that i sometimes use a random compare function to get an easy implementation of a good list shuffle function. Now all QuickSort functions in our challenge fails on ;-) function CompareAlwaysLess(Item1, Item2: Pointer): Integer; begin Result := -1; end; Quote: If we choose to allow failure for inconsistent compare functions we should agree what a consistent compare function is. It seems to me that a consistent compare function has these properties: A) Result of Compare(A, B) is the same everytime B) Compare(A, A) = 0 C) If Compare(A, B) > 0 then Compare(B, A) < 0 If Compare(A, B) = 0 then Compare(B, A) = 0 If Compare(A, B) < 0 then Compare(B, A) > 0 D) If Compare(A, B) > 0 and Compare(B, C) > 0 then Compare(A, C) > 0 If Compare(A, B) > 0 and Compare(B, C) = 0 then Compare(A, C) > 0 If Compare(A, B) = 0 and Compare(B, C) > 0 then Compare(A, C) > 0 If Compare(A, B) < 0 and Compare(B, C) < 0 then Compare(A, C) < 0 If Compare(A, B) < 0 and Compare(B, C) = 0 then Compare(A, C) < 0 If Compare(A, B) = 0 and Compare(B, C) < 0 then Compare(A, C) < 0 If Compare(A, B) = 0 and Compare(B, C) = 0 then Compare(A, C) = 0 If anyone disagrees with this definition please say so. It is OK. -- regards Aleksandr Back to top Aleksandr Sharahov Guest Posted: Mon Oct 03, 2005 8:07 am    Post subject: Re: Sort valiation rules - how should a function handle an i Hi Avatar, Quote: This would mean we'd also have to agree on criteria for a consistent compare function and include this into the specification for our function. It must have all properties of comparison. Quote: Someone should also analyze the RTL function to see what can be the worst that happens when it is passed an inconsistent sort function. IMO the Fastcode sort should not be less secure than the RTL sort. Obviosly RTL sort (and any QuickSort without checking bounds) fails, if compare return always -1 or 1. -- regards Aleksandr Back to top Avatar Zondertau Guest Posted: Mon Oct 03, 2005 4:36 pm    Post subject: Re: Sort valiation rules - how should a function handle an i Quote: Currently the Sort B&V tests if the sort function survives an inconsistent compare function (validator 3). I think a good sort function should be able to cope with this. Aleksander doesn't agree with this, since he thinks more optimization is possible if the sort function can assume the compare function is consistent. I think we should vote on a rule for this. Current votes: 1) A sort function should execute successfully for any compare function. Avatar 2) A sort function may raise an exception (including EAccessViolation) when passed an invalid compare function, but must still terminate on every compare function. Eric 3) A sort function may raise an exception or go into an infinite loop or infinite recursion state when passed an invalid compare function (so basically the result would be undefined). Aleksander, Pierre I'm not sure about Anders and John. Did they vote for (3) or against it? Back to top Anders Isaksson Guest Posted: Mon Oct 03, 2005 5:01 pm    Post subject: Re: Sort valiation rules - how should a function handle an i Avatar Zondertau wrote: Quote: I'm not sure about Anders and John. Did they vote for (3) or against it? I vote for 3, as I can't see any feasible way to fulfil 1 or 2 (without re-formulation). -- Anders Isaksson, Sweden BlockCAD: http://web.telia.com/~u16122508/proglego.htm Gallery: http://web.telia.com/~u16122508/gallery/index.htm Back to top Hrvoje Brozovic Guest Posted: Tue Oct 04, 2005 8:03 am    Post subject: Re: Sort valiation rules - how should a function handle an i Avatar Zondertau wrote: Quote: 1) A sort function should execute successfully for any compare function. 2) A sort function may raise an exception (including EAccessViolation) when passed an invalid compare function, but must still terminate on every compare function. 3) A sort function may raise an exception or go into an infinite loop or infinite recursion state when passed an invalid compare function (so basically the result would be undefined). 1) I believe that this is fundamentaly impossible. 2) Is great, if achievable. 3) is normal way of things, it works that way even without rule. Even, I don't know what infinite recursion means. It is expected to eat whole stack in finite number of reentries. I won't vote, since I am not a contributor. Back to top Dennis Guest Posted: Tue Oct 04, 2005 8:20 am    Post subject: Re: Sort valiation rules - how should a function handle an i Hi Hrvoje Quote: I won't vote, since I am not a contributor. Please vote anyway. Regards Dennis Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         BorlandTalk.com Forum Index -> Delphi Language BASM All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum C++ Builder Newsgroups----------------C++ BuilderC++ Builder (ActiveX)C++ Builder (Announcements)C++ Builder (Command Line Tools)C++ Builder DatabasesC++ Builder Databases (ADO)C++ Builder Databases (Desktop)C++ Builder Databases (InterBase Express)C++ Builder Databases (Multi-Tier)C++ Builder Databases (SQL Servers)C++ Builder (Graphics)C++ Builder (IDE)C++ Builder (Internet)C++ Builder (Internet Socket)C++ Builder (Internet Web)C++ Builder (Jobs)C++ Builder (Language)C++ Builder (Language C++)C++ Builder (Compatibility with MFC)C++ Builder (Native API)C++ Builder (Non-Technical)C++ Builder (Students)C++ Builder (Third Party Tools)C++ Builder (Upgrade)C++ Builder (VCL)C++ Builder (VCL Components Usage)C++ Builder (VCL Components Development)C++ Builder (VCL Usage)C++ Builder (WinAPI)C++ Builder Installation Delphi Newsgroups----------------Delphi (General)Delphi ActiveX Controls UsageDelphi ActiveX Controls DevelopmentDelphi As400Delphi DatabasesDelphi Databases (ADO)Delphi Databases (dbExpress)Delphi Databases (Desktop)Delphi Databases (InterBase Express)Delphi Databases (Multi-Tier)Delphi Databases (SQL Servers)Delphi DeploymentDelphi GraphicsDelphi IDEDelphi InternationalizationDelphi InternetDelphi Internet Isapi-WebBrokerDelphi Internet WebSnapDelphi Internet WinsockDelphi JobsDelphi Language BASMDelphi Language ObjectPascalDelphi Model Driven Architecture (General)Delphi Model Driven Architecture (Third Party)Delphi MultimediaDelphi Native APIDelphi Non-TechnicalDelphi ObjectPascalDelphi OLE AutomationDelphi OO designDelphi OpenToolsAPIDelphi Reporting-ChartingDelphi RTLDelphi StudentsDelphi TeamSourceDelphi Thirdparty ToolsDelphi Thirdparty Tools (General)Delphi Thirdparty Tools (IntraWeb)Delphi Thirdparty Tools (RaveReports)Delphi UpgradeDelphi VCLDelphi VCL ComponentsDelphi VCL Components UsingDelphi VCL Components WritingDelphi WebServices SOAPDelphi WinAPIDelphi XMLDelphi Installationcomp.lang.pascal.delphi.components.misccomp.lang.pascal.delphi.components.usagecomp.lang.pascal.delphi.components.writingcomp.lang.pascal.delphi.databasescomp.lang.pascal.delphi.misccomp.sources.delphi JBuilder Newsgroups----------------JBuilderJBuilder AnnouncementsJBuilder Applet IssuesJBuilder As400JBuilder CompilerJBuilder CORBA/RMIJBuilder DatabasesJBuilder DB SwingJBuilder DebuggerJBuilder DeploymentJBuilder DocumentationJBuilder EnterpriseJBuilder HandheldJBuilder IDEJBuilder JavaJBuilder JavaAPIJBuilder Java LanguageJBuilder Java SwingJBuilder Java BeansJBuilder Java Beans UsageJBuilder Java Beans DevelopmentJBuilder JBCLJBuilder JDataStoreJBuilder JobsJBuilder LinuxJBuilder MacintoshJBuilder & MobileSetJBuilder MultiLingual AppsJBuilder Non-TechnicalJBuilder OpenToolsJBuilder Servlets (JSP)JBuilder StudentsJBuilder Team DevelopmentJBuilder Thirdparty ToolsJBuilder UpgradeJBuilder Installation InterBase Newsgroups----------------InterBaseInterBase Bug DiscussionInterBase GeneralInterBase IBConsoleInterBase OpenSourceInterBase ReplicationInterBase SQLInterBase ThirdpartyInterBase Installation Miscellaneous Borland Newsgroups----------------AppCenterAppServerEnteraVisiBroker  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.