OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]
Re: [xml-dev] Re: Discover data patterns or Create data patterns?

> Do you have a feel for whether Java is powerful enough to implement finger
> trees in?

I have used Java only occasionally and even that was many years ago.

Good support of generics is required for the inplementation of a
finger tree. In particular, a finger tree is a recursive structure.
The following class definition (C#):

    public class DeepFTree<T> : FTree<T>
        protected Digit<T> frontDig;
        protected FTree<Node<T>> innerFT;
        protected Digit<T> backDig;

        .   .   .   .   .   .   .   .   .   .   .


defines a DeepFTree<T> to have an "innerFT" member, which is of type

This "innerFT" may have its own "innerFT" of type  FTree<Node<Node<T>>>

and this second "innerFT" may have its own "innerFT" of type

 ...  , etc.

The types    Node<T>,     Node<Node<T>>,     Node<Node<Node<T>>>, ...
will need to be created at runtime, as it is impossible to know at
compile time how deep the type nesting will need to be (although in
the case of a finger tree we know this will be close to log2(N), where
N is the number of leaf nodes of the tree).

So, I am sure this cannot be achieved with C++ generics, which is
supported entirely at compile time. As for Java, I am not even aware
if it has any generics support at all.

A Scala implementation of the finger tree object is said to exist.

Dimitre Novatchev
Truly great madness cannot be achieved without significant intelligence.
To invent, you need a good imagination and a pile of junk
Never fight an inanimate object
You've achieved success in your field when you don't know whether what
you're doing is work or play

On Sun, Sep 21, 2008 at 11:55 PM, Rick Jelliffe
<rjelliffe@allette.com.au> wrote:
> Dimitre Novatchev wrote:
>>  A good example of a problem that can be completely eliminated: use a
>> Finger-Tree-based sequence for all sequences, then there is no need to
>> worry
>> to convert from one sequence type to another (of course, the items still
>> need to be of the same type). Not to mention the gains in efficiency.
> Do you have a feel for whether Java is powerful enough to implement finger
> trees in?
> Cheers
> Rick Jelliffe

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]

News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 1993-2007 XML.org. This site is hosted by OASIS