Re: [xml-dev] Re: Discover data patterns or Create data patterns?

["Dimitre Novatchev" <dnovatchev@gmail.com>]

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