Prev: I have almost given up on lisp
Next: question regarding hash tables
From: Scott Burson on 22 Dec 2009 22:36
On Dec 22, 2:41 pm, rkk <rajesh.ko...(a)gmail.com> wrote:
> I have an application where I create and store triangles, a triangle
> being a set of 3 points,
> (p0 p1 p2).

I strongly recommend you take a look at FSet, my functional set-
theoretic collections library for Common Lisp:

http://common-lisp.net/project/fset/

It makes the kind of thing you're trying to do very easy, as it has
many built-in set operations including equality testing, and maps can
be keyed by sets with no special effort.

-- Scott
From: Willem Broekema on 22 Dec 2009 17:57
On Dec 22, 11:41 pm, rkk <rajesh.ko...(a)gmail.com> wrote:
> I know the standard does not allow this, but has anyone implemented
> custom hash tables where this can be done?

Many implementations allow this. You need to define both an equality
and a hash function, and they must be consistent (two objects equal =>
their hashes identical).

This is what I use to implement Python hash tables in 5 common
implementations:

;;; Python dicts are hash tables with custom equality (py-==) and hash
functions (py-hash).

#+sbcl
(sb-ext:define-hash-table-test py-==->lisp-val py-hash)
#+cmu
(extensions:define-hash-table-test 'py-hash-table-test #'py-==->lisp-
val #'py-hash)

(defun make-py-hash-table ()
(or #+(or allegro ccl lispworks) (make-hash-table :test 'py-==->lisp-
val :hash-function 'py-hash)
#+cmu (make-hash-table :test 'py-hash-table-test)
#+sbcl (make-hash-table :test 'py-==->lisp-val)
#-(or allegro ccl lispworks cmu sbcl) (error "Creating python
dict not suported in this environment.")))
From: Joshua Taylor on 22 Dec 2009 20:25
rkk wrote:
> I have an application where I create and store triangles, a triangle
> being a set of 3 points,
> (p0 p1 p2). The triangles are created and stored using something along
> the lines of
>
> (defun make-triangle (p0 p1 p2)
> (setf (get-hash (get-next-id) *TRIANGLES*) (list p0 p1 p2)))
>
> where (get-next-id) returns a unique id. *TRIANGLES* is defined as
>
> (defvar *TRIANGLES* (make-hash-table))
>
> Two triangles are "equal" if they have the same points. The order of
> the points is not important,
[...]
> I know the standard does not allow this, but has anyone implemented
> custom hash tables where this can be done?
>
> Thanks in advance
> rkk

Willem Boekema responded with a way to do this with hash tables
directly, as many implementations do have extensions for hash-tables.

Without adding reader conditionals in lots of places though, you can
portably do what you're doing by putting your points in some canonical
order (since you said that the order doesn't matter), and hashing with a
test that can compare the list of points. Of course, how you represent
your points will determine how easily this can be done. Some
representations might require interning your points too. For instance,
let's assume points are conses each of whose CAR and CDR is a real.
We'll sort points lexicographically (i.e., sort by CAR, and when CARs
are the same, sort by CDR).


(defun point< (p1 p2)
(cond
((< (car p1) (car p2)) t)
((> (car p1) (car p2)) nil)
((< (cdr p1) (cdr p2)))))

(defvar *polygons*
(make-hash-table :test 'equal))

(defun intern-polygon (&rest points)
(let ((points (sort points 'point<)))
(multiple-value-bind (polygon presentp)
(gethash points *polygons*)
(if presentp polygon
(setf (gethash points *polygons*) points)))))


Since we hashed on a list of points, it's easier to take an arbitrary
number of points as an &rest list, but a variant for exactly three
points wouldn't be hard. Here, interned polygons are EQ comparable,
which might save you the need for those unique ids too, and you don't
need to be mapping back and forth between polygons and ids.


(let ((p1 (intern-polygon '(3 . 8) '(2 . 3) '(1 . 3)))
(p2 (intern-polygon '(2 . 3) '(1 . 3) '(3 . 8)))
(p3 (intern-polygon '(2 . 3) '(1 . 3) '(3 . 8)))
(p4 (intern-polygon '(3 . 4) '(9 . 3) '(0 . 3))))
(list (eq p1 p2)
(eq p1 p3)
(eq p1 p4)))
;=> (T T NIL)


//JT
From: Gene on 23 Dec 2009 21:43
On Dec 22, 5:41 pm, rkk <rajesh.ko...(a)gmail.com> wrote:
> I have an application where I create and store triangles, a triangle
> being a set of 3 points,
> (p0 p1 p2). The triangles are created and stored using something along
> the lines of
>
> (defun make-triangle (p0 p1 p2)
>   (setf (get-hash (get-next-id) *TRIANGLES*) (list p0 p1 p2)))
>
> where (get-next-id) returns a unique id. *TRIANGLES* is defined as
>
> (defvar *TRIANGLES* (make-hash-table))
>
> Two triangles are "equal" if they have the same points. The order of
> the points is not important,
> and hence I defined the following:
>
> (defun set-equal? (set1 set2)
>   (and (eql (set-difference set1 set2) nil) (eql (set-difference set2
> set1) nil)))
>
> Two triangles share an edge / are said to be connected if (= 2 (length
> (intersection tr1 tr2))) etc.
>
> In my application, I cannot have duplicate triangles, so right now,
> before I call make-triangle, I check
> if *TRIANGLES* already has an existing triangle with the same points
> by walking through the hashtable.
>
> Currently my (key,value) corresponds to (id, (p0,p1,p2)). My question
> is can I invert this and instead have
> (key,value) correspond to ((p0,p1,p2), id). To do this, I would need
> to have something like
>
> (defvar *TRIANGLES* (make-hash-table :test #'set-equal?))
>
> I know the standard does not allow this, but has anyone implemented
> custom hash tables where this can be done?

One note if performance is any kind of issue: If you give points
unique integer ids, then any triangle can be easily be placed in a
canonical form: with the points in (say) ascending id order. This
simplifies equality and common edge tests. A list of the 3 sorted
integer ids makes a nice hash key, so a hash table with #'equal
predicate implements content-addressable memory.

 | 
Pages: 1
Prev: I have almost given up on lisp
Next: question regarding hash tables