Lists Home |
Date Index |
- From: Toby Speight <Toby.Speight@streapadair.freeserve.co.uk>
- To: "XML developers' list" <email@example.com>
- Date: 03 Feb 2000 12:54:44 +0000
Miles> Miles Sabin <URL:mailto:firstname.lastname@example.org>
0> In article
0> Miles wrote:
Miles> Toby Speight wrote,
>> You would have to create as many MyFilterImpl objects as you
>> have parsers, and try each one. With my example (3 parsers, 2
>> filters), that's only 15 different possibilities, but the
>> combinatorial explosion gets you pretty quickly as the number
>> of stacked filters increases.
Miles> You want to be able to enumerate _all_ the parser+filter
Miles> combinations that support "q" and "r", not just find some
Miles> _one_ parser+filter that fits the bill.
That's not quite right. The problem as I see it is that you don't
know which filters to try with which parsers, and so you have to
iterate through all the combinations until you find a match.
A reminder of the example:
> Feature p q r
> A no no no
> B provides no no
> C no provides no
> F passthru passthru provides
> G provides blocks provides
> We require q and r.
The factory can ask A, B and C what they support; none of them has the
required feature-set. But it can't ask the filters directly what they
support - it has to ask the pipelines AF, BF, CF, AFG, BFG, ..., AG,
BG, CG, AGF, ..., etc.
With knowledge of the filters, it can straightaway see that ending in G
is always going to fail (because it blocks q), so it can eliminate half
the options in a stroke. Furthermore, it can hypothesize ending in F,
which provides r and passes q, so it just needs to find something that
provides q, to plug in upstream of F. This is a recursive call, and it
finds C. So CF is a viable result.
This is all just using standard search algorithms; the advantage of
knowing the filters' capabilities separately from the underlying
parsers is that it enables the search-space to be reduced much more
quickly than a brute-force search would.
There's are different benefits to the two approaches I suggested: having
the factory do it all allows a breadth-first search, which should lead to
shorter pipelines as results; recursing mutually between factory and
filters means that more complicated relationships between features are
possible (e.g. filter supports feature x only if upstream parser supports
This discussion could probably use some concrete examples at this
point; a Namespace filter is one reasonably complex kind - what else?