[prev in list] [next in list] [prev in thread] [next in thread] 

List:       gimp-print-devel
Subject:    Re: [Fwd: Re: [Gimp-print-devel] PhotoPrint 0.2.2]
From:       Michael Sweet <mike () easysw ! com>
Date:       2005-01-20 1:21:35
Message-ID: 41EF079F.3080805 () easysw ! com
[Download RAW message or body]

Mike Porter wrote:
> ...
>> No, actually, we don't check conflicts when the file is loaded,
>> only when an option is marked via the public API or you
>> explicitly call ppdConflicts().
> 
> 
> I believe CUPS did when I wrote this code in 2001.

We've never called ppdMarkDefaults() or ppdConflicts() from the
load function.  Prior to CUPS 1.1.something we sorted the choices
for each option which would add another O(n log n), however we
dropped that when Apple started using CUPS.

>> Anyways, the ppdLoad*() code probably works out to be O(n log n)
>> since we sort the options but not the choices.
> 
> 
> If you are using lists, you do not have O( n log n ) code.  You only
> get that by using a splitting search of some type.  Either a sorted
> array or a tree, for instance.

Since we don't sort until the end, adding an option or group to
the end of the current array is O(1).  The option sorting uses
qsort() which is O(n log n), and that is done once after the PPD
file is completely loaded.

-- 
______________________________________________________________________
Michael Sweet, Easy Software Products           mike at easysw dot com
Internet Printing and Publishing Software        http://www.easysw.com


-------------------------------------------------------
This SF.Net email is sponsored by: IntelliVIEW -- Interactive Reporting
Tool for open source databases. Create drag-&-drop reports. Save time
by over 75%! Publish reports on the web. Export to DOC, XLS, RTF, etc.
Download a FREE copy at http://www.intelliview.com/go/osdn_nl
_______________________________________________
Gimp-print-devel mailing list
Gimp-print-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gimp-print-devel
[prev in list] [next in list] [prev in thread] [next in thread]