[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Re: Discover data patterns or Create data patterns?

  • From: "Dimitre Novatchev" <dnovatchev@g...>
  • To: "Rick Jelliffe" <rjelliffe@a...>
  • Date: Mon, 22 Sep 2008 07:15:07 -0700

Re:  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@a...> 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]


Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
First Name
Last Name
Subscribe in XML format
RSS 2.0
Atom 0.3

Stylus Studio has published XML-DEV in RSS and ATOM formats, enabling users to easily subcribe to the list from their preferred news reader application.

Stylus Studio Sponsored Links are added links designed to provide related and additional information to the visitors of this website. they were not included by the author in the initial post. To view the content without the Sponsor Links please click here.

Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.