Data Structure Choice for DOM

Data Structure Choice for DOM

[chris.danx]

Hi all,

In the DOM Level 3 spec, a NamedNodeMap is defined.  What's the best way 
to implement this? I'm implementing an OO version of the DOM Level 3 
spec (in Ada*) and this one is posing a problem just choosing the right 
implementation.  Under considering is a chained hash table and an AVL 
tree.  Both have their advantage but there may be a more appropriate 
choice of which I'm not aware.


Chris

*gives me something to keep programming skills in Ada sharp

Re: Data Structure Choice for DOM

[Simon Wright]

"chris.danx" <spamoff.danx@ntlworld.com> writes:

> In the DOM Level 3 spec, a NamedNodeMap is defined.  What's the best
> way to implement this? I'm implementing an OO version of the DOM
> Level 3 spec (in Ada*) and this one is posing a problem just
> choosing the right implementation.  Under considering is a chained
> hash table and an AVL tree.  Both have their advantage but there may
> be a more appropriate choice of which I'm not aware.

Do it the way that gets you working code quickest, profile it (speed
and memory), and choose another implementation for this part if it's
justified.

Aside from anything else, this will be much more fun (cos the DOM
application you have in mind will be able to _do_ something!)

Re: Data Structure Choice for DOM

[chris.danx]

Simon Wright wrote:
> 
> Do it the way that gets you working code quickest, profile it (speed
> and memory), and choose another implementation for this part if it's
> justified.

:)  "Premature optimisation is the root of all evil" or something like that?

Linked list is easiest & quickest.  It'll be O(n) in worst case but 
it'll work.  Later I'll change it to an AVL tree or something else.


> Aside from anything else, this will be much more fun (cos the DOM
> application you have in mind will be able to _do_ something!)

True.  I suppose I should have just did it, rather than search for the 
right data structure.  That's one of my big problems, looking for the 
"best" solution to a problem rather than getting stuck in and improving 
the deficiencies later!


Thanks,
Chris

Re: Data Structure Choice for DOM

[Stephen Leake]

"chris.danx" <spamoff.danx@ntlworld.com> writes:

> Simon Wright wrote:
> > Do it the way that gets you working code quickest, profile it (speed
> > and memory), and choose another implementation for this part if it's
> > justified.
> 
> :)  "Premature optimisation is the root of all evil" or something like that?
> 
> Linked list is easiest & quickest.  It'll be O(n) in worst case but
> it'll work.  Later I'll change it to an AVL tree or something else.

Be sure to use a good library of data structures, like Booch, Charles,
or SAL. They have consistent interfaces to similar data structures, so
changing from a linked list to an AVL tree is not hard.

In addition, they make it no harder to use an AVL tree instead of a
linked list in the first place, since the hard part is already done.

Write the requirements for the code, including the time behavior (is
O(n) really ok?). That makes it easy to pick from the available,
implemented and tested data structures.

-- 
-- Stephe

Re: Data Structure Choice for DOM

[Kevin Cline]

"chris.danx" <spamoff.danx@ntlworld.com> wrote in message news:<oQ5aa.16185$EN3.130845@newsfep4-glfd.server.ntli.net>...
> Hi all,
> 
> In the DOM Level 3 spec, a NamedNodeMap is defined.  What's the best way 
> to implement this? I'm implementing an OO version of the DOM Level 3 
> spec (in Ada*) and this one is posing a problem just choosing the right 
> implementation.  Under considering is a chained hash table and an AVL 
> tree.  Both have their advantage but there may be a more appropriate 
> choice of which I'm not aware.

Do whichever is easiest.  The maps typically contain only a few entries,
so the slight differences in performance will probably be undetectable.

Re: Data Structure Choice for DOM

[chris.danx]

Kevin Cline wrote:
> 
> Do whichever is easiest.

If only! ;)

I had a nice set of data structures I'd written around 6 months ago 
backed up and the CD is now jiggered!  Going to have to rewrite them, 
which is a shame since they used Safe Pointers (ala Mr Grein) to make 
iterators on structures safe :(

 > The maps typically contain only a few entries,
> so the slight differences in performance will probably be undetectable.

Hadn't thought of that, you're right!  Who's going to notice 2 accesses 
with an AVL in comparison to 5 with a list?

Re: Data Structure Choice for DOM

[Matthew Heaney]

"chris.danx" <spamoff.danx@ntlworld.com> wrote in message news:<oQ5aa.16185$EN3.130845@newsfep4-glfd.server.ntli.net>...
> 
> In the DOM Level 3 spec, a NamedNodeMap is defined.  What's the best way 
> to implement this? I'm implementing an OO version of the DOM Level 3 
> spec (in Ada*) and this one is posing a problem just choosing the right 
> implementation.  Under considering is a chained hash table and an AVL 
> tree.  Both have their advantage but there may be a more appropriate 
> choice of which I'm not aware.

The Charles library has both kinds of map structures.

charles.maps.sorted.unbounded
charles.maps.hashed.unbounded

There are also versions that have type String as the key.

charles.maps.sorted.strings.unbounded
charles.maps.hashed.strings.unbounded

The sorted versions is implemented using a red-black tree, which has
properties similar to an AVL tree.

http://home.earthlink.net/~matthewjheaney/charles/index.html