[net.lang] Why compare pointers in Pascal?

pdbain@wateng.UUCP (Peter Bain) (01/28/85)

Say I had a set of records, which I represented as a vector of pointers.
Suppose further that I wanted to test for set membership by comparing
pointers. If I keep the vector sorted by increasing pointer value,
I can do the test in O(lg(N)), using a binary search, but I need
< and > on pointers. If all I have is == and !=, it takes O(N) time.
-- 
   - peter bain
...!{allegra|decvax|clyde|ihnp4 }!watmath!wateng!pdbain
hard mail:	CCNG, CPH-2369A, University of Waterloo,
	Waterloo, Ont. Canada N2M 5G4
telephone:	(519) 885-1211 x2810

gvcormack@watdaisy.UUCP (Gordon V. Cormack) (01/29/85)

> Say I had a set of records, which I represented as a vector of pointers.
> Suppose further that I wanted to test for set membership by comparing
> pointers. If I keep the vector sorted by increasing pointer value,
> I can do the test in O(lg(N)), using a binary search, but I need
> < and > on pointers. If all I have is == and !=, it takes O(N) time.
>    - peter bain

If one could get the representation of the pointer (say, as an integer)
one could test for membership in O(1) time using hashing.
-- 
 
Gordon V. Cormack      CS Department, University of Waterloo
   gvcormack@watdaisy.uucp     gvcormack%watdaisy@waterloo.csnet

ndiamond@watdaisy.UUCP (Norman Diamond) (01/29/85)

> > Say I had a set of records, which I represented as a vector of pointers.
> > Suppose further that I wanted to test for set membership by comparing
> > pointers. If I keep the vector sorted by increasing pointer value,
> > I can do the test in O(lg(N)), using a binary search, but I need
> > < and > on pointers. If all I have is == and !=, it takes O(N) time.
> >    - peter bain
> 
> If one could get the representation of the pointer (say, as an integer)
> one could test for membership in O(1) time using hashing.
> -- Gordon V. Cormack

Of course, one could compare the "pointees", or some component of the pointees.
Or, one could hash on some component of the pointees.

If only one component is compared, then the test slows down to compare the
remaining components.  Hey, we've found another "methodology" bug in the
datatypes provided by Pascal.

Still, the problem is not only that the language doesn't "want" to let you
do < and > on pointers.  On some machines, an address requires more bits than
an integer, and a comparison requires several machine instructions.  Also,
Pascal run-time support might incorporate a suggestion someone published a
few years ago, to check for dereferencing nil or "disposed" pointers;
then a comparison might require even more instructions to mask out the extra
information.  If that's not enough, extending this technique a little bit
would make automatic garbage collection feasible (with no change to the
source language).  Comparisons other than == and != do not provide you with
any useful information, unless you take advantage of machine and compiler
dependencies.

-- Norman Diamond

UUCP:  {decvax|utzoo|ihnp4|allegra|clyde}!watmath!watdaisy!ndiamond
CSNET: ndiamond%watdaisy@waterloo.csnet
ARPA:  ndiamond%watdaisy%waterloo.csnet@csnet-relay.arpa

"Opinions are those of the keyboard, and do not reflect on me or higher-ups."

crs@lanl.ARPA (02/01/85)

Oops!  Sorry.

russell@muddcs.UUCP (Russell Shilling) (02/09/85)

	I may be full of blue mud, but I think the original question which
prompted the mass of 'pointer' articles was actually about comparing the
*values pointed to* rather than the *pointer value*. For example, the
question contained:
	if p < q ...
I think the solution might be to recode as:
	if p^ < q^ ...
This compares the items pointed to, rather than the address.  Anyway, I think
that's what was meant.
-- 
	Russell Shilling
		UUCP:	{ allegra, ihnp4, seismo }!scgvaxd!muddcs!russell
		ARPA:	muddcs!russell@ucla-cs
	Always eat from the four basic food groups:
		Beer, Ice Cream, Chips and Salsa