From: charlieb
Subject: Am I pushing my luck with this?
Date: 
Message-ID: <2tsncoF235560U1@uni-berlin.de>
My aim was to maintain two lists with the same elements sorted by cadr 
and cddr (a point is (cons x y)) then tag ('tag (x . y)) them so that I 
can change the tags in one list and they'll change in the other. The 
point is to split both lists in kd-aux based on the data in one list and 
never have to re-sort them.

The first problem seems to arise in the inner let of kd-tree which is 
where the hairy(?) mutation begins. It seems that cmucl and sbcl (debian 
unstable versions) like to give a truncated y-points list most (but not 
all) of the time. I think that there is more horror like this in kd-aux 
but I haven't had time to look into it yet. The funny thing is I 
actually developed this on a Clisp + XP machine and it works fine there.

(defun tag-points (points)
   (mapcar (lambda (point) (cons t point)) points))

(defun kd-tree (points)
   (let ((tagged-points (tag-points points)))
     (let ((x-points (sort tagged-points #'> :key #'cadr))
	  (y-points (sort (copy-list tagged-points) #'> :key #'cddr)))
       (print x-points)
       (print y-points)
       (kd-aux x-points y-points))))

(defun kd-aux (x-points y-points)
   (let* ((rx) (ry) (lx) (ly)
	 (mid (ash (length x-points) -1))
	 (count 0)
	 (node))
     (dolist (pt x-points)
       (cond
        ((> count mid) (setf (car pt) 'r) (push pt rx))
        ((< count mid) (setf (car pt) 'l) (push pt lx))
        (t (setq node pt) (setf (car pt) nil)))
       (incf count))
     (dolist (pt y-points)
       (case (car pt)
	('r (push pt ry))
	('l (push pt ly))))
     (if (zerop mid)
	(list (point node))
	(list (point node)
	    (kd-aux (reverse ly) (reverse lx))
	    (kd-aux (reverse ry) (reverse rx))))))

(defun random-points (num)
   (let ((res))
     (dotimes (i num res)
       (push (cons (random 400)
		  (random 400))
     res))))

Try (kd-tree (random-points 10)) and look at the prints' output. They 
might have different lengths.

Charlieb.

From: Marco Baringer
Subject: Re: Am I pushing my luck with this?
Date: 
Message-ID: <m23c06ycio.fsf@bese.it>
just a few quick notes, i haven't actually tried runnig it.

charlieb <··@privacy.net> writes:

> (defun kd-tree (points)
>   (let ((tagged-points (tag-points points)))
>     (let ((x-points (sort tagged-points #'> :key #'cadr))
>           (y-points (sort (copy-list tagged-points) #'> :key #'cddr)))

1) sort is a destructive operation.

2) copy-list only copyies the list of cons cells, not their contents.

>       (print x-points)
>       (print y-points)
>       (kd-aux x-points y-points))))

> (defun kd-aux (x-points y-points)
>   (let* ((rx) (ry) (lx) (ly)

in this let* none of the inits depend on a previous init, i'd use let
(just so that people don't keep trying to see what init depends on
what).

> 	 (mid (ash (length x-points) -1))

what's wrong with (/ (length x-points) 2)?

> 	 (count 0)
> 	 (node))
>     (dolist (pt x-points)
>       (cond
>        ((> count mid) (setf (car pt) 'r) (push pt rx))
>        ((< count mid) (setf (car pt) 'l) (push pt lx))
>        (t (setq node pt) (setf (car pt) nil)))
>       (incf count))
>     (dolist (pt y-points)
>       (case (car pt)
> 	('r (push pt ry))
> 	('l (push pt ly))))

the values in case clauses are not evaluated. what you've actually
written is:

(case (car pt)
  ((quote r) (push pt ry))
  ((quote l) (push pt ly)))

the presence of the symbol QUOTE in both clauses gives (afair)
undefined behaviour.

>     (if (zerop mid)
> 	(list (point node))
> 	(list (point node)
> 	    (kd-aux (reverse ly) (reverse lx))
> 	    (kd-aux (reverse ry) (reverse rx))))))
>
> (defun random-points (num)
>   (let ((res))
>     (dotimes (i num res)
>       (push (cons (random 400)
> 		  (random 400))
>     res))))
>
> Try (kd-tree (random-points 10)) and look at the prints' output. They 
> might have different lengths.

hth.

-- 
-Marco
Ring the bells that still can ring.
Forget your perfect offering.
There is a crack in everything.
That's how the light gets in.
     -Leonard Cohen
From: Kalle Olavi Niemitalo
Subject: Re: Am I pushing my luck with this?
Date: 
Message-ID: <877jpi90t4.fsf@Astalo.kon.iki.fi>
"Marco Baringer" <··@bese.it> writes:

> (case (car pt)
>   ((quote r) (push pt ry))
>   ((quote l) (push pt ly)))
>
> the presence of the symbol QUOTE in both clauses gives (afair)
> undefined behaviour.

"Each of the normal-clauses is then considered in turn."
So I think the first QUOTE merely hides the second one.
From: Paul Foley
Subject: Re: Am I pushing my luck with this?
Date: 
Message-ID: <m2sm86cmvy.fsf@mycroft.actrix.gen.nz>
On Fri, 22 Oct 2004 16:30:29 +0100, charlieb  wrote:

> The first problem seems to arise in the inner let of kd-tree which is 
> where the hairy(?) mutation begins. It seems that cmucl and sbcl (debian 
> unstable versions) like to give a truncated y-points list most (but not 
> all) of the time. I think that there is more horror like this in kd-aux 
> but I haven't had time to look into it yet. The funny thing is I 
> actually developed this on a Clisp + XP machine and it works fine there.

> (defun tag-points (points)
>   (mapcar (lambda (point) (cons t point)) points))

> (defun kd-tree (points)
>   (let ((tagged-points (tag-points points)))
>     (let ((x-points (sort tagged-points #'> :key #'cadr))

This call to SORT destroys TAGGED-POINTS.

> 	  (y-points (sort (copy-list tagged-points) #'> :key #'cddr)))

This call to COPY-LIST copies the list you just destroyed.


-- 
Malum est consilium quod mutari non potest             -- Publilius Syrus

(setq reply-to
  (concatenate 'string "Paul Foley " "<mycroft" '(··@) "actrix.gen.nz>"))
From: charlieb
Subject: Re: Am I pushing my luck with this?
Date: 
Message-ID: <349511f4.0410240231.5860a1a9@posting.google.com>
Thanks for the info, everyone. Does this mean that destructive
operations like sort can not only mess with the top-level of the list
they are dealing with but also the elements in the list so copying the
list both times is also unsafe:

(let ((x-points (sort (copy-list tagged-points) #'> :key #'cadr))
      (y-points (sort (copy-list tagged-points) #'> :key #'cddr)))
...)

Cheers for the case info as well.

Thanks
Charlieb
From: Svein Ove Aas
Subject: Re: Am I pushing my luck with this?
Date: 
Message-ID: <clg1cs$mb5$5@services.kq.no>
charlieb wrote:

> Thanks for the info, everyone. Does this mean that destructive
> operations like sort can not only mess with the top-level of the list
> they are dealing with but also the elements in the list so copying the
> list both times is also unsafe:
> 
No, sort only moves around the top-level elements of a list; it doesn't
touch any sublists except for reading the key.

The point was that copy-list will only copy the top level, but that's enough
to make sort work without altering the original list.

> (let ((x-points (sort (copy-list tagged-points) #'> :key #'cadr))
>       (y-points (sort (copy-list tagged-points) #'> :key #'cddr)))
> ...)

This should work just fine. 
From: Svein Ove Aas
Subject: Re: Am I pushing my luck with this?
Date: 
Message-ID: <clg1et$mb5$6@services.kq.no>
charlieb wrote:

> (let ((x-points (sort (copy-list tagged-points) #'> :key #'cadr))
>       (y-points (sort (copy-list tagged-points) #'> :key #'cddr)))
> ...)

This works fine, but FYI x-points and y-points will share structure in the
sub-lists. This isn't neccessarily a problem, but you ought to be aware of
it.
From: charlieb
Subject: Re: Am I pushing my luck with this?
Date: 
Message-ID: <349511f4.0410240914.10077b33@posting.google.com>
Svein Ove Aas <·········@aas.no> wrote in message news:<············@services.kq.no>...
> charlieb wrote:
> 
> > (let ((x-points (sort (copy-list tagged-points) #'> :key #'cadr))
> >       (y-points (sort (copy-list tagged-points) #'> :key #'cddr)))
> > ...)
> 
> This works fine, but FYI x-points and y-points will share structure in the
> sub-lists. This isn't neccessarily a problem, but you ought to be aware of
> it.

Excellent, that was my plan.
Cheers,
Charlie