XML.orgXML.org
FOCUS AREAS |XML-DEV |XML.org DAILY NEWSLINK |REGISTRY |RESOURCES |ABOUT
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
FTree<Node<T>>

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

and this second "innerFT" may have its own "innerFT" of type
FTree<Node<Node<Node<T>>>>,

 ...  , 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.

-- 
Cheers,
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