Making hash table behave like array inside loop

Discussion of Common Lisp

Making hash table behave like array inside loop

Postby wvxvw » Thu Jul 07, 2011 11:29 pm

Hi, I'm not even sure how to formulate the question, so I didn't find much help by searching the forum / online resources. Here's what I'm trying to do and maybe you could advise:
I'm writing a parser for AMF format (Flash object serialization). This format has record for what it's calling `array'. Yet this isn't an array in common understanding, it's rather a composition of an array part and a sort of a hash table, so, I'll call it further ecma-array. Now, the problem with ecma-array is that it may be as they call it `sparse', which means, that it may have indices 0 through 10 set, for example, and then indices 20 through 30 set, but 10 through 20 are empty. This looks on the wire as if the indices 20 through 30 were all string keys into hash table. When parsing such thing, I could probably find out those `sub-arrays', and even consolidate them or create separate sub-arrays etc.
My problem however is that I will need to create a special ecma-array class to perform like normal array, while it would fetch the data from different places when it's iterated over, or, when it's requested to tell what it's length is etc. I've looked at macroexpand of (loop ...) macro and it looks like it is implementation specific. I could however roll my own iterator for example. The thing I'm not sure is what is considered proper to do in this situation: should I try to make it usable with (loop ...) or is there any certain pattern one would write an iterator and that is believed to be easily understood by others? Lastly, if I want it to be usable in the loop, then what functionality exactly do I have to implement to make it work?

Thanks!
wvxvw
 
Posts: 125
Joined: Sat Mar 26, 2011 6:23 am

Re: Making hash table behave like array inside loop

Postby marcoxa » Fri Jul 08, 2011 1:48 am

The problem I have with your post is that you (or the AMF 3.0 people) have to define what is the result of roundtripping the "array-type". From the spec, reading an array-type will tell you how big the "dense" part is, plus it will tell you whether the "array" is "associative" (read: at least one non-ordinal index entry; hence a hash-table). You have to do some "data driven" reading.

Cheers
Marco Antoniotti
marcoxa
 
Posts: 58
Joined: Thu Aug 14, 2008 6:31 pm

Re: Making hash table behave like array inside loop

Postby wvxvw » Fri Jul 08, 2011 2:25 am

True, but it is also true that on the AS side if a hash-table key may be interpreted as integer, it is considered an array index...
So, for example:
Code: Select all
var array:Array = [];
array["100"] = 1;

Will be considered an array of the length of 101. And if you then do:
Code: Select all
for (var i:int; i < array.length; i++) trace(array[i]);

You will get `undefined' 100 times, and then `1'.
Why would anyone want to do it like this is beyond my comprehension, and if I had to use that only for myself, I'd simply discard the hash-table part and use only the dense array part... well, it's not possible :) So, I'm saying it's not really possible to map ecma-array to any of existing (or at least those that I could remember) standard Lisp sequences. I'd have to make one of my own, yet, I want to make sure it fits into the language the best it can.
wvxvw
 
Posts: 125
Joined: Sat Mar 26, 2011 6:23 am

Re: Making hash table behave like array inside loop

Postby Konfusius » Fri Jul 08, 2011 7:01 am

you might iterate over all entries of a hash table by the form with-hash-table-iterator but then you cannot make any assumptions about iteration order. the only solution i can think of is writing your own functions (make-sparse-array, sparse-aref etc.) i would implement it as an assoc list first and optimize it later if necessary.
Konfusius
 
Posts: 62
Joined: Fri Jun 10, 2011 6:38 am

Re: Making hash table behave like array inside loop

Postby marcoxa » Fri Jul 08, 2011 7:46 am

wvxvw wrote:True, but it is also true that on the AS side if a hash-table key may be interpreted as integer, it is considered an array index...
So, for example:
Code: Select all
var array:Array = [];
array["100"] = 1;

Will be considered an array of the length of 101. And if you then do:
Code: Select all
for (var i:int; i < array.length; i++) trace(array[i]);

You will get `undefined' 100 times, and then `1'.
Why would anyone want to do it like this is beyond my comprehension, and if I had to use that only for myself, I'd simply discard the hash-table part and use only the dense array part... well, it's not possible :) So, I'm saying it's not really possible to map ecma-array to any of existing (or at least those that I could remember) standard Lisp sequences. I'd have to make one of my own, yet, I want to make sure it fits into the language the best it can.


Yes. I see what you mean. Yep it is a bitch as you can do things like

Code: Select all
a = [];
a["42"] = 123;
writeln("> " + a.length);
a["123"] = 42;
writeln("> " + a.length);
a["foo"] = 0;
writeln("> " + a.length);


This is a very nasty semantics to deal with; perlite gravis obvously struck with a vengeance. I think there's no way around but to implement a js-sequence type of some sort. You may want to look at parenscript to see what they did. YMMV

Cheers
Marco Antoniotti
marcoxa
 
Posts: 58
Joined: Thu Aug 14, 2008 6:31 pm

Re: Making hash table behave like array inside loop

Postby wvxvw » Mon Jul 11, 2011 4:48 am

I finally have it as something like this:
Code: Select all
(defclass amf-object ()
  ((constructor
    :initarg :constructor
    :initform (make-as3-fqname :name "Object")
    :type as3-fqname)
   (properties
    :initform (make-hash-table :test 'equal)
    :type hash-table)))

(defgeneric get-property (container name)
  (:documentation "Generic method for reading from `amf-object' properties"))

(defmethod get-property ((container amf-object) (name string))
  (gethash name (slot-value container 'properties)))

(defclass amf-array (amf-object)
  ((constructor
    :initform (make-as3-fqname :name "Array"))
   (members
    :initform nil
    :initarg :members
    :type list)))

(defgeneric amf-length (container)
  (:documentation "Calculates the length of the `container', note,
this operation is O(n) complex, try not to abuse it"))

(defmethod amf-length ((container amf-array))
  (car (first (last (slot-value container 'members)))))

(defgeneric item (container index)
  (:documentation "Fetches an item at specified `index'."))

(defmethod item ((container amf-array) (index integer))
  (assoc index (slot-value container 'members)))

(defmethod get-property ((container amf-array) (name string))
  (multiple-value-bind (possible-int stopped-at)
      (parse-integer name :junk-allowed t)
    (if (= (length name) stopped-at)
   (item container possible-int)
   (gethash name (slot-value container 'properties)))))

Where on similar 'set-property I'll have to insert the pair into pairlist if it may be read as an integer, else, push it into hash table. Since this isn't expected to show good performance anyway, it'll probably fit for now.
wvxvw
 
Posts: 125
Joined: Sat Mar 26, 2011 6:23 am


Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 2 guests