Path: utzoo!censor!geac!torsqnt!lethe!yunexus!ists!helios.physics.utoronto.ca!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!wuarchive!zaphod.mps.ohio-state.edu!rpi!batcomputer!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Partial Orders
Message-ID: <4861@goanna.cs.rmit.oz.au>
Date: 1 Mar 91 07:05:03 GMT
References: <1991Feb27.032403.23920@comp.vuw.ac.nz>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 25

In article <1991Feb27.032403.23920@comp.vuw.ac.nz>, steve@comp.vuw.ac.nz (Steve Cassidy) writes:
[He has a set of terms with a partial order "generality" defined on them,
 the comparison is expensive.]

> I need to do three operations [on collections of 5 to 50 such terms]:
>   'traverse' -- look at the least general rule first, and so on
>                 until a match is found (ie maybe not to the end)
	[most frequent]
>   insert -- insert a new object into the partial ordering
>   delete -- delete an object from the partial ordering
	[these two less frequent but common]

The bad news is that when you insert the next term into a collection
of 49 terms, you may find that *none* of them is comparable to the
new term.  That means that the worst case of anything you come up with
is going to be as bad as linear search.

This is not a Prolog problem, and I would like to know of a good data
structure for it myself.  There was one time when I had to maintain a
collection of sets, but in that case it dawned on me that ordering
sets by cardinality also ordered them by inclusion.  Can a similar
trick be used?

-- 
The purpose of advertising is to destroy the freedom of the market.