Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #30663 > unrolled thread

Which data structure would you recommend?

Back to article view | Back to comp.lang.java.programmer

Contents

  Which data structure would you recommend? Doug Mika <dougmmika@gmail.com> - 2015-01-08 14:25 -0800
    Re: Which data structure would you recommend? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-01-08 17:51 -0500
    Re: Which data structure would you recommend? Silvio <silvio@internet.com> - 2015-01-09 17:21 +0100
      Re: Which data structure would you recommend? Magnus Warker <magnux@mailinator.com> - 2015-01-11 20:03 +0100
        Re: Which data structure would you recommend? Martin Gregorie <martin@address-in-sig.invalid> - 2015-01-11 23:03 +0000
          Re: Which data structure would you recommend? Lew <lewbloch@gmail.com> - 2015-01-11 15:17 -0800
            Re: Which data structure would you recommend? Silvio <silvio@internet.com> - 2015-01-12 15:05 +0100
          Re: Which data structure would you recommend? Silvio <silvio@internet.com> - 2015-01-12 10:13 +0100
            Re: Which data structure would you recommend? Martin Gregorie <martin@address-in-sig.invalid> - 2015-01-12 14:35 +0000
          Re: Which data structure would you recommend? Gene Wirchenko <genew@telus.net> - 2015-01-13 10:02 -0800
            Re: Which data structure would you recommend? Arne Vajhøj <arne@vajhoej.dk> - 2015-01-19 20:11 -0500
              Re: Which data structure would you recommend? Gene Wirchenko <genew@telus.net> - 2015-01-20 09:25 -0800
        Re: Which data structure would you recommend? Silvio <silvio@internet.com> - 2015-01-12 08:58 +0100
          Re: Which data structure would you recommend? Silvio <silvio@internet.com> - 2015-01-12 14:54 +0100
    Re: Which data structure would you recommend? Jeff Higgins <jeff@invalid.invalid> - 2015-01-09 18:36 -0500
      Re: Which data structure would you recommend? Jeff Higgins <jeff@invalid.invalid> - 2015-01-09 19:54 -0500
    Which data structure would you recommend? ynseo <yeori.seo@gmail.com> - 2015-01-12 04:52 -0800

#30663 — Which data structure would you recommend?

Hi

I need to create a structure similar to a tree but the tree can have two parent nodes and has 2 child nodes.  The nodes are to be of arbitrary class type.  It would be nice if I could traverse the data structure from parent to node, and that I could reach any node by its "key" or "name".  Which data structure would you recommend?

Much Thanks

[toc] | [next] | [standalone]

#30665

On 1/8/2015 5:25 PM, Doug Mika wrote:
> Hi
>
> I need to create a structure similar to a tree but the tree can have two parent nodes and has 2 child nodes.  The nodes are to be of arbitrary class type.  It would be nice if I could traverse the data structure from parent to node, and that I could reach any node by its "key" or "name".  Which data structure would you recommend?

     Could you explain how this arrangement is "similar to a tree?"
The resemblance completely escapes me.

     More to the point: Could you explain your requirement in more
detail, perhaps with an actual example to help people like me who
are slow on the uptake?

     Even more to the point: What problem are you trying to solve?
There may be a better approach than constructing some kind of weird
bonsai with both its roots and twigs stuck in the earth ...

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[toc] | [prev] | [next] | [standalone]

#30669

On 01/08/2015 11:45 PM, Stefan Ram wrote:
> Doug Mika <dougmmika@gmail.com> writes:
>> I need to create a structure similar to
>> a tree but the tree can have two parent
>> nodes and has 2 child nodes.
>
> class Tree
> { java.lang.Object left_super;
>    java.lang.Object right_super;
>    java.lang.Object left_sub;
>    java.lang.Object right_sub; };
>
>    But this is low-level thinking.
>    In OOP, we have no data structures.
>    We have objects with behavior.

I disagree strongly.

First of all, without data structures we are like fish in the desert.

Often we do hide a complete data structure behind an instance of a 
class. But even then the semantics of the data structure define the 
semantics of said class interface.

Hiding a complete data structure behind an object only works well if you 
are talking about either a mutable structure or some sort of "atomic" 
value class. If you want to have immutable collections like they exist 
in the Scala standard library (for example lists, sets, maps) then the 
operations on the collection are exposed by returning new instances of 
the same collection type. That makes the semantics of the data structure 
shine through even more.

I hate the idea that something is OOP or not or that OOP defines the one 
and only way a thing can/should look. OOP does NOT mean anything on its 
own and at the same time means many different things in the minds of 
different people.

[toc] | [prev] | [next] | [standalone]

#30676

On 01/09/2015 05:21 PM, Silvio wrote:

> I hate the idea that something is OOP or not or that OOP defines the one
> and only way a thing can/should look. OOP does NOT mean anything on its
> own and at the same time means many different things in the minds of
> different people.

I strongly agree!

Your words remind me of a time, when some people thought, their C code 
would be OOP when saved in files ending with "cpp". :-)

Magnus

[toc] | [prev] | [next] | [standalone]

#30678

On Sun, 11 Jan 2015 20:03:42 +0100, Magnus Warker wrote:

> On 01/09/2015 05:21 PM, Silvio wrote:
> 
>> I hate the idea that something is OOP or not or that OOP defines the
>> one and only way a thing can/should look. OOP does NOT mean anything on
>> its own and at the same time means many different things in the minds
>> of different people.
> 
> I strongly agree!
> 
> Your words remind me of a time, when some people thought, their C code
> would be OOP when saved in files ending with "cpp". :-)
>
And there's still a huge amount of 'C++' code around that is in reality 
little more than ANSI C with // comments, a .cpp extension and nary a 
class declaration to be seen. Quite depressing, really, if its a valid 
indication of the state of the programming art.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#30679

> > Silvio wrote:
> > 
> >> I hate the idea that something is OOP or not or that OOP defines the
> >> one and only way a thing can/should look. OOP does NOT mean anything on
> >> its own and at the same time means many different things in the minds
> >> of different people.

"There's no crying in baseball!"

Defining program correctness in terms of "OOP/not OOP" is both cargo-cult engineering and begging the question. "OOP" is not a metric, let alone of correctness, but a tool. Like all tools one must pragmatically and skilfully apply it appropriately. In the end you want to model everything a program has to accomplish, eliminate crashes, and keep the maintenance costs to a minimum. Theological debates cannot correct your [Ss]wing.

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#30686

On 01/12/2015 12:17 AM, Lew wrote:
>>> Silvio wrote:
>>>
>>>> I hate the idea that something is OOP or not or that OOP defines the
>>>> one and only way a thing can/should look. OOP does NOT mean anything on
>>>> its own and at the same time means many different things in the minds
>>>> of different people.
>
> "There's no crying in baseball!"
>
> Defining program correctness in terms of "OOP/not OOP" is both cargo-cult engineering and begging the question. "OOP" is not a metric, let alone of correctness, but a tool. Like all tools one must pragmatically and skilfully apply it appropriately. In the end you want to model everything a program has to accomplish, eliminate crashes, and keep the maintenance costs to a minimum. Theological debates cannot correct your [Ss]wing.
>

I agree with what you say about OOP. My crying stems from the fact that 
too many people who post here (among other places) drag "OOP" into 
discussions where it does not belong, simply because they think (their 
image of) OOP-ness equals program(mer) quality and it makes them sound 
smart.

[toc] | [prev] | [next] | [standalone]

#30682

On 01/12/2015 12:03 AM, Martin Gregorie wrote:
> On Sun, 11 Jan 2015 20:03:42 +0100, Magnus Warker wrote:
>
>> On 01/09/2015 05:21 PM, Silvio wrote:
>>
>>> I hate the idea that something is OOP or not or that OOP defines the
>>> one and only way a thing can/should look. OOP does NOT mean anything on
>>> its own and at the same time means many different things in the minds
>>> of different people.
>>
>> I strongly agree!
>>
>> Your words remind me of a time, when some people thought, their C code
>> would be OOP when saved in files ending with "cpp". :-)
>>
> And there's still a huge amount of 'C++' code around that is in reality
> little more than ANSI C with // comments, a .cpp extension and nary a
> class declaration to be seen. Quite depressing, really, if its a valid
> indication of the state of the programming art.
>
>

True, I have come across such code bases as well and it has not always 
been pleasant.

On the other hand I have come across lots of programs that where written 
in very strict OOP patterns that where absolute abominations as well. 
And some of the most brilliant and ingeniously written programs I have 
ever encountered where written in procedural C (and done in a very 
structured and consistent way).

My point is that the level of OOP-ness (which is a subjective score on 
its own) does not equal the quality of a program. Doing everything the 
"proper" OOP way, putting in the right tests, etc. is easy. Writing good 
programs is an art.

[toc] | [prev] | [next] | [standalone]

#30687

On Mon, 12 Jan 2015 10:13:17 +0100, Silvio wrote:

> On 01/12/2015 12:03 AM, Martin Gregorie wrote:
>> On Sun, 11 Jan 2015 20:03:42 +0100, Magnus Warker wrote:
>>
>>> On 01/09/2015 05:21 PM, Silvio wrote:
>>>
>>>> I hate the idea that something is OOP or not or that OOP defines the
>>>> one and only way a thing can/should look. OOP does NOT mean anything
>>>> on its own and at the same time means many different things in the
>>>> minds of different people.
>>>
>>> I strongly agree!
>>>
>>> Your words remind me of a time, when some people thought, their C code
>>> would be OOP when saved in files ending with "cpp". :-)
>>>
>> And there's still a huge amount of 'C++' code around that is in reality
>> little more than ANSI C with // comments, a .cpp extension and nary a
>> class declaration to be seen. Quite depressing, really, if its a valid
>> indication of the state of the programming art.
>>
>>
>>
> True, I have come across such code bases as well and it has not always
> been pleasant.
> 
> On the other hand I have come across lots of programs that where written
> in very strict OOP patterns that where absolute abominations as well.
> And some of the most brilliant and ingeniously written programs I have
> ever encountered where written in procedural C (and done in a very
> structured and consistent way).
> 
> My point is that the level of OOP-ness (which is a subjective score on
> its own) does not equal the quality of a program. Doing everything the
> "proper" OOP way, putting in the right tests, etc. is easy. Writing good
> programs is an art.

Good points and well made. 

Depending on what the program's purpose is, I agree that a well 
structured and commented ANSI C program can sometimes be easier to 
understand than its OO equivalent. 

IME the one place where OO provides a clear win over well-structured non-
OO programming is in code re-usability. 

Its generally easier to write a re-usable set of classes, and often 
easier to enhance/extend them too, than it is to do the same job in 
vanilla C or equivalent languages. 

I, anyway, tend to end up writing C library code in a semi-OO way. I put 
instance-related variables in typedefed structs (think FILE in standard 
C) that are created and destroyed with malloc/free. Global variables are 
accessable only from within the source module that contains them and all 
all the functions that provide the set of closely related actions. 

FWIW I was using this style, self-taught, before my first brush with 
either C++ or Java, but both Wirth's "Algorithms + Data Structures = 
Programs" and Kernighan & Plauger's "Software Tools In Pascal" were very 
influential in developing my personal programming style.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#30690

On Sun, 11 Jan 2015 23:03:49 +0000 (UTC), Martin Gregorie
<martin@address-in-sig.invalid> wrote:

[snip]

>And there's still a huge amount of 'C++' code around that is in reality 
>little more than ANSI C with // comments, a .cpp extension and nary a 
>class declaration to be seen. Quite depressing, really, if its a valid 
>indication of the state of the programming art.

     The state of the programming art should not be using one way to
the exclusion of all others.  OOP (or anything else) is not a hammer.

     I remember one assignment in my degree.  It was to compare
throughput of various CPU allocation algorithms.  Since it was to be
written in Java, I thought that I would see what I could do to make
the program use OOP.

     It did not work out.  The more I thought about it, the less I saw
how I could write anything that would have been maintainable.  I ended
up writing procedural code.  My program worked great.  Another student
who did try going OOP ended up scrapping his effort about two days
before the assignment was due and did not complete the whole
assignment.

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

#30753

On 1/13/2015 1:02 PM, Gene Wirchenko wrote:
> On Sun, 11 Jan 2015 23:03:49 +0000 (UTC), Martin Gregorie
> <martin@address-in-sig.invalid> wrote:
>
> [snip]
>
>> And there's still a huge amount of 'C++' code around that is in reality
>> little more than ANSI C with // comments, a .cpp extension and nary a
>> class declaration to be seen. Quite depressing, really, if its a valid
>> indication of the state of the programming art.
>
>       The state of the programming art should not be using one way to
> the exclusion of all others.  OOP (or anything else) is not a hammer.
>
>       I remember one assignment in my degree.  It was to compare
> throughput of various CPU allocation algorithms.  Since it was to be
> written in Java, I thought that I would see what I could do to make
> the program use OOP.
>
>       It did not work out.  The more I thought about it, the less I saw
> how I could write anything that would have been maintainable.  I ended
> up writing procedural code.  My program worked great.  Another student
> who did try going OOP ended up scrapping his effort about two days
> before the assignment was due and did not complete the whole
> assignment.

I completely agree that there are cases where OOP is not the optimal
paradigm.

But I can not understand the example. Computer/system class, CPU/core
class, process/thread class, queue class and strategy pattern seems
a natural model to me.

Arne

[toc] | [prev] | [next] | [standalone]

#30759

On Mon, 19 Jan 2015 20:11:05 -0500, Arne Vajhøj <arne@vajhoej.dk>
wrote:

[snip]

>I completely agree that there are cases where OOP is not the optimal
>paradigm.
>
>But I can not understand the example. Computer/system class, CPU/core
>class, process/thread class, queue class and strategy pattern seems
>a natural model to me.

     The algorithms were very simple.  Had I tried to break them up,
the resulting code would have been longer and convoluted.
Procedurally, it went rather easily.

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

#30681

On 01/11/2015 08:03 PM, Magnus Warker wrote:
> On 01/09/2015 05:21 PM, Silvio wrote:
>
>> I hate the idea that something is OOP or not or that OOP defines the one
>> and only way a thing can/should look. OOP does NOT mean anything on its
>> own and at the same time means many different things in the minds of
>> different people.
>
> I strongly agree!
>
> Your words remind me of a time, when some people thought, their C code
> would be OOP when saved in files ending with "cpp". :-)
>
> Magnus
>

Your words remind me of programmers that think that a piece of code, 
however small, is either OOP or it is not and if it is then it is good.

Programming is first of all breaking down problems the right way and 
applying the proper algorithms. OOP is a coding style that helps to do 
so in a structured and explicit way. It is a means to an end.

You seem to think it is the other way around.

[toc] | [prev] | [next] | [standalone]

#30685

On 01/12/2015 08:58 AM, Silvio wrote:
> On 01/11/2015 08:03 PM, Magnus Warker wrote:
>> On 01/09/2015 05:21 PM, Silvio wrote:
>>
>>> I hate the idea that something is OOP or not or that OOP defines the one
>>> and only way a thing can/should look. OOP does NOT mean anything on its
>>> own and at the same time means many different things in the minds of
>>> different people.
>>
>> I strongly agree!
>>
>> Your words remind me of a time, when some people thought, their C code
>> would be OOP when saved in files ending with "cpp". :-)
>>
>> Magnus
>>
>
> Your words remind me of programmers that think that a piece of code,
> however small, is either OOP or it is not and if it is then it is good.
>
> Programming is first of all breaking down problems the right way and
> applying the proper algorithms. OOP is a coding style that helps to do
> so in a structured and explicit way. It is a means to an end.
>
> You seem to think it is the other way around.
>

Sorry, I meant to say "They" instead of "You".

[toc] | [prev] | [next] | [standalone]

#30670

On 01/08/2015 05:25 PM, Doug Mika wrote:
> Hi
>
> I need to create a structure similar to a tree but the tree can have two parent nodes and has 2 child nodes.  The nodes are to be of arbitrary class type.  It would be nice if I could traverse the data structure from parent to node, and that I could reach any node by its "key" or "name".  Which data structure would you recommend?
>
<http://jgrapht.org/>

[toc] | [prev] | [next] | [standalone]

#30671

On 01/09/2015 06:36 PM, Jeff Higgins wrote:
> On 01/08/2015 05:25 PM, Doug Mika wrote:
>> Hi
>>
>> I need to create a structure similar to a tree but the tree can have
>> two parent nodes and has 2 child nodes.  The nodes are to be of
>> arbitrary class type.  It would be nice if I could traverse the data
>> structure from parent to node, and that I could reach any node by its
>> "key" or "name".  Which data structure would you recommend?
>>
> <http://jgrapht.org/>
>
<http://www.graphclasses.org/index.html>

[toc] | [prev] | [next] | [standalone]

#30684

you might need graph-like data structure, not tree.

but it is not clear how it should be implemented because you didn't specify what you want to do with that.

- is order of traversing nodes important?
- how many nodes are expected?
- read-oriented or update-oriented?
- where should it be stored?(file, db, or im-memory?)

For simplicity, hashmap would be suitable material for implementation, but you need a way to choose a node from many children for traversing, for which java.util.Comparator is well suited.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web