Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: Notesfiles $Revision: 1.6.2.17 $; site uiucdcsb.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!ihnp4!inuxc!pur-ee!uiucdcsb!mcnabb
From: mcnabb@uiucdcsb.UUCP
Newsgroups: net.lang.pascal
Subject: Re: Comparing pointers in Pascal
Message-ID: <9300010@uiucdcsb.UUCP>
Date: Tue, 29-Jan-85 10:40:00 EST
Article-I.D.: uiucdcsb.9300010
Posted: Tue Jan 29 10:40:00 1985
Date-Received: Thu, 31-Jan-85 02:03:10 EST
References: <3161@ucla-cs.UUCP>
Lines: 37
Nf-ID: #R:ucla-cs:-316100:uiucdcsb:9300010:000:1994
Nf-From: uiucdcsb!mcnabb    Jan 29 09:40:00 1985


	/* Written Jan 28, 1985 by pdbain@wateng in net.lang.pascal */

	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
	/* End of text from net.lang.pascal */


It seems to me that the important point here is that Pascal objects to the
use of the value of a pointer in any attempt to ascertain information about
where the "pointee" lies in memory.  Pascal does not object to the use of
an assumption that every unique pointer has a corresponding unique scalar
value, which may be sorted, compared, etc. just like any integer.  Why not
use "ord (your_pointer)" for the problem above?  Pascal permits the conversion
of (unique?)* pointers into (unique?)* integers, but tries to prevent direct
arithmetic on pointers because this is clearly implementation-dependent.
BTW, ord (pointer) is a freebie (i.e. NOP) in most Pascal compilers.

* I am not sure, and rather doubt, that Pascal guarantees that pointers and
integers will always be the same size.  In an implementation with pointers
larger than integers, the uniqueness assumption of the "ord" solution might
not hold.  Still, this kind of implementation-dependency seems both less
likely and less serious.

I guess that to be completely safe, one would have to use some other
mechanism to obtain a unique key for each pointer.  These keys could be kept
with the pointers in the sorted vector (now a vector of records), or could
be stored in the "pointee" records.  Either way, it would be dead easy to
keep your sorted vector - with only a small space (one integer) and perhaps
time penalty (need extra indirection on compares if key stored with pointee).
Either approach is still O(ln(N)), but is now implementation-independent.