I need a data structure that has keyed entries like a hash table, but also
preserves order like a list (with inserting, sorting, etc.)
CLtL2 states that for both the loop hash clauses and the hashtable
iteration callback that their order of access is undefined. Which is a
problem, I need guaranteed first to last processing. Also, the hashtable
seems a tad opaque, but that may be just because I've not used them much (in
Lisp).
I've begun looking at using property lists for this, since they remain lists
yet will have the key-value access. But its beginning to look like I might
end up writing a lot of macros that are just variations on dolist, mapcar,
nth, etc. for property lists.
Any advice? Are there already mapping functions for property lists that I've
overlooked? Are lists coercable as hashtables? This seems like there
should be a simple solution that I'm just overlooking.
Thanks,
Chris Perkins
"Chris Perkins" <········@medialab.com> writes:
> I need a data structure that has keyed entries like a hash table, but also
> preserves order like a list (with inserting, sorting, etc.)
>
> CLtL2 states that for both the loop hash clauses and the hashtable
> iteration callback that their order of access is undefined. Which is a
> problem, I need guaranteed first to last processing. Also, the hashtable
> seems a tad opaque, but that may be just because I've not used them much (in
> Lisp).
>
> I've begun looking at using property lists for this, since they remain lists
> yet will have the key-value access. But its beginning to look like I might
> end up writing a lot of macros that are just variations on dolist, mapcar,
> nth, etc. for property lists.
>
> Any advice? Are there already mapping functions for property lists that I've
> overlooked? Are lists coercable as hashtables? This seems like there
> should be a simple solution that I'm just overlooking.
>
You need balanced trees. You loose in access time, but you retain the
ability to do ordered traversals and Min and Max operation in O(lg n).
There is a (shameful plug) implementation for Red Black Trees in the
CMU AI.Repository (don't have the link handy).
Cheers
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.
"Chris Perkins" <········@medialab.com> writes:
> I need a data structure that has keyed entries like a hash table,
> but also preserves order like a list (with inserting, sorting, etc.)
Then it appears you need to build a "MAKE-BTREE" set of functions.
--
(concatenate 'string "cbbrowne" ·@acm.org")
http://www3.sympatico.ca/cbbrowne/unix.html
It is impossible to sharpen a pencil with a blunt axe. It is equally
vain to try to do it with ten blunt axes instead.
-- Edsger W. Dijkstra
The C++ Standard Library and the Java Collections library have
Associative Containers, in particular Maps, which provide keyed access.
If there is a total ordering on the keys, you can use a tree-based map
which sorts the entries based on a comparison function applied to the
keys (which you can specify). These are usually implemented as
red-black trees. There is also a hashed map which acts like at CL
hashtable. There is a uniform interface to Maps of both kinds.
The tree-based map (as mentioned in other responses to your post) is
probably the best solution in your case. Sometimes, however, a solution
involving a sequence (of keys or key-value pairs) and a hashtable works
well. For example, you might have a cache implementation for which
lookup in the cache is done via a hashtable, but flushing the oldest
cache entries as new ones are added is done using a sequence (or a
struct holding a list and both its ends). Similarly, flushing the least
recently used can be facilitated by moving the most recently used item
to one end of the list or deque and flushing from the other.
Jeff
"Chris Perkins" <········@medialab.com> wrote in message
·························@news.uswest.net...
> I need a data structure that has keyed entries like a hash table, but
also
> preserves order like a list (with inserting, sorting, etc.)
>
In article <····················@news.uswest.net>, "Chris Perkins"
<········@medialab.com> wrote:
> I need a data structure that has keyed entries like a hash table, but
> also
> preserves order like a list (with inserting, sorting, etc.)
>
> CLtL2 states that for both the loop hash clauses and the hashtable
> iteration callback that their order of access is undefined. Which is a
> problem, I need guaranteed first to last processing. Also, the
> hashtable seems a tad opaque, but that may be just because I've not
> used them much (in Lisp).
>
> I've begun looking at using property lists for this
How many items are you likely to have? How common is traversal,
relative to insertion/deletion?
If there are very few items then a property list might be OK, but
otherwise you'll really want something with random access.
If the frequency of traversal is not that great then it's not hard to
use the Perl solution of "for (sort keys %myHash){...}". It's a bit
longer to express in CL because there isn't a built in function that
returns the key collection (is there?), but you can easily enough build
it using loop/collect/sort:
(dolist
(k (sort (loop for a being the hash-keys of my-table collect a) #'<))
(print k))
If traversal is really common and updating not, then you might be better
to use a tree data structure (AVL, RedBlack, B- etc).
-- Bruce
From: Thomas A. Russ
Subject: Re: Ordered Hash Table? Mapping/Iteration of prop list?
Date:
Message-ID: <ymik7vibti9.fsf@sevak.isi.edu>
What about Association Lists, also known as Alists?
They are ordered like lists, have keyed entries, etc. It does require
some macrology to do things like inserting, but sorting (for sorting you
will need to supply the :key keyword parameter -- typically #'car) and
iteration pretty much come for free , particularly if you use loop:
(loop for (key . value) on alist do ....)
Insertion as noted is a bit trickier, since what you need to do depends
a lot on whether your Alist already has a key for the given value. That
often means doing something like the following:
(let ((value (assoc search-key *my-data-structure*)))
(if (null value)
(setq *my-data-structure*
(acons search-key new-value *my-data-structure*)
(setf (rest value) new-value)))
Of course, this solution does have O(n) search and insertion time, but
unless N is large, this may not be a problem.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
From: Steve Long
Subject: Re: Ordered Hash Table? Mapping/Iteration of prop list?
Date:
Message-ID: <3C23C382.26104E88@isomedia.com>
A general idea...functionality of a hash-table with a list of keys in reverse
order of insertion ;)
(defstruct (hash-pipe
(:conc-name hash-pipe-)
(:constructor mk-hash-pipe)
(:print-function
(lambda(inst print-stream print-depth)
(declare (ignore print-depth))
(format
print-stream
"#s(hash-pipe ~a)"
(hash-table-count (hash-pipe-table inst))))))
(test #'eql :read-only? t)
(key #'identity :read-only?t)
(table (make-hash-table :size 100 :test #'eql))
(ordered-keys nil))
(defmacro do-hash-pipe
(((key val) hp &optional result) form)
"Hash-pipe iterator"
`(let* ((fnc #'(lambda(,key ,val) ,form)))
(maphash fnc (hash-pipe-table ,hp))
,result))
(defun make-hash-pipe
(&key
(size 100)
(test #'eql)
(key #'identity)
(rehash-size 100)
(rehash-threshold 0.9)
(initial-values nil))
"Public constructor"
(let* ((ht (make-hash-table
:size size
:test test
:rehash-size rehash-size
:rehash-threshold rehash-threshold))
(hp (mk-hash-pipe
:table ht
:test test
:key key)))
(dolist (val initial-values hp)
(hp-set hp val))))
(defun hp-keys
(hp)
"Public time-ordered key reader."
(hash-pipe-ordered-keys hp))
(defun hp-set
(hp val)
"Public value accessor."
(let ((keyval (funcall (hash-pipe-key hp) val)))
(pushnew keyval (hash-pipe-ordered-keys hp) :test (hash-pipe-test hp))
(setf (gethash keyval (hash-pipe-table hp)) val)
val))
(defun hp-get
(hp keyval)
"Public value reader."
(gethash keyval (hash-pipe-table hp)))
(defun hp-rem
(hp keyval)
"Public value destructor."
(let ((val (hp-get hp keyval)))
(remhash keyval (hash-pipe-table hp))
(remove keyval (hash-pipe-ordered-keys hp) :test (hash-pipe-test hp))
val))
(defun hp-pop
(hp)
"Public last-value popper."
(let* ((keyval (pop (hash-pipe-ordered-keys hp)))
(val (hp-get hp keyval)))
(remhash keyval (hash-pipe-table hp))
val))
(defun hp-clear
(hp)
"Public reset."
(clrhash (hash-pipe-table hp)))
slong
Chris Perkins wrote:
> I need a data structure that has keyed entries like a hash table, but also
> preserves order like a list (with inserting, sorting, etc.)
>
> CLtL2 states that for both the loop hash clauses and the hashtable
> iteration callback that their order of access is undefined. Which is a
> problem, I need guaranteed first to last processing. Also, the hashtable
> seems a tad opaque, but that may be just because I've not used them much (in
> Lisp).
>
> I've begun looking at using property lists for this, since they remain lists
> yet will have the key-value access. But its beginning to look like I might
> end up writing a lot of macros that are just variations on dolist, mapcar,
> nth, etc. for property lists.
>
> Any advice? Are there already mapping functions for property lists that I've
> overlooked? Are lists coercable as hashtables? This seems like there
> should be a simple solution that I'm just overlooking.
>
> Thanks,
>
> Chris Perkins