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

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

Working with an array of TreeSet

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

Contents

  Working with an array of TreeSet Cecil Westerhof <Cecil@decebal.nl> - 2016-05-10 13:37 +0200
    Re: Working with an array of TreeSet Eric Douglas <e.d.programmer@gmail.com> - 2016-05-10 04:52 -0700
      Re: Working with an array of TreeSet Cecil Westerhof <Cecil@decebal.nl> - 2016-05-10 15:07 +0200
    Re: Working with an array of TreeSet Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-05-10 08:03 -0400
    Re: Working with an array of TreeSet Marcel Mueller <news.5.maazl@spamgourmet.org> - 2016-05-10 18:19 +0200
      Re: Working with an array of TreeSet Cecil Westerhof <Cecil@decebal.nl> - 2016-05-10 23:22 +0200
        Re: Working with an array of TreeSet Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-05-10 20:14 -0400
          Re: Working with an array of TreeSet Cecil Westerhof <Cecil@decebal.nl> - 2016-05-11 09:05 +0200
            Re: Working with an array of TreeSet FredK <fred.l.kleinschmidt@gmail.com> - 2016-05-11 14:33 -0700
              Re: Working with an array of TreeSet Lew <lewbloch@gmail.com> - 2016-05-11 14:45 -0700

#34273 — Working with an array of TreeSet

I would like to have an array of TreeSet<Integer>. But that is not
possible in Java.
So I use:
    TreeSet<?>[] allNodes;
I fill this with:
    for (int i = 1; i < maxNode; ++i) {
        allNodes[i] = new TreeSet<Integer>();
    }

And to add an Integer I use:
    @SuppressWarnings("unchecked")
    private static void addConnection(int from, int to) {
        TreeSet<Integer> treeSet;

        treeSet = (TreeSet<Integer>) allNodes[from];
        treeSet.add(to);
    }

Is this a correct way of doing this, or is there a better way?

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

[toc] | [next] | [standalone]

#34274

On Tuesday, May 10, 2016 at 7:43:59 AM UTC-4, Cecil Westerhof wrote:
> I would like to have an array of TreeSet<Integer>. But that is not
> possible in Java.

Why not just put them in ArrayList?

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

#34276

On Tuesday 10 May 2016 13:52 CEST, Eric Douglas wrote:

> On Tuesday, May 10, 2016 at 7:43:59 AM UTC-4, Cecil Westerhof wrote:
>> I would like to have an array of TreeSet<Integer>. But that is not
>> possible in Java.
>
> Why not just put them in ArrayList?

You are right, that is much cleaner. Thanks.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

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

#34275

On 5/10/2016 7:37 AM, Cecil Westerhof wrote:
> I would like to have an array of TreeSet<Integer>. But that is not
> possible in Java.
> So I use:
>     TreeSet<?>[] allNodes;
> I fill this with:
>     for (int i = 1; i < maxNode; ++i) {
>         allNodes[i] = new TreeSet<Integer>();
>     }
>
> And to add an Integer I use:
>     @SuppressWarnings("unchecked")
>     private static void addConnection(int from, int to) {
>         TreeSet<Integer> treeSet;
>
>         treeSet = (TreeSet<Integer>) allNodes[from];
>         treeSet.add(to);
>     }
>
> Is this a correct way of doing this, or is there a better way?

     Evading the issue, you might instead try

	BitSet[] allNodes;

... but this (1) won't work for negative values, (2) will work
poorly with widely-scattered values, and (3) doesn't generalize
to other element types.  Nonetheless ....

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

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

#34277

On 10.05.16 13.37, Cecil Westerhof wrote:
> I would like to have an array of TreeSet<Integer>. But that is not
> possible in Java.
> So I use:
>      TreeSet<?>[] allNodes;

Since Java uses ->type erasure the types TreeSet<?>[] and 
TreeSet<Integer>[] are identical.
The strong typing is mainly a hint for the compiler to check whether you 
inserted the correct type and to avoid the downcast required otherwise.

> I fill this with:
>      for (int i = 1; i < maxNode; ++i) {
>          allNodes[i] = new TreeSet<Integer>();
>      }

Well, if you really intend to insert a large number of consecutive 
integers TreeSet<Integer> is amazingly inefficient. Each Integer wraps 
an int with an Object. Each entry in the TreeSet wraps the Integer 
Object with another Object. So you get an overhead of at least one order 
of magnitude.

> And to add an Integer I use:
>      @SuppressWarnings("unchecked")
>      private static void addConnection(int from, int to) {
>          TreeSet<Integer> treeSet;
>
>          treeSet = (TreeSet<Integer>) allNodes[from];
>          treeSet.add(to);
>      }
>
> Is this a correct way of doing this, or is there a better way?

This is syntactically OK.

The more interesting question is why you need an array of TreeSet.
What is the semantic meaning of from? And what is the meaning of to?
It looks like an 1:n or m:n mapping. If the number of entries in one 
TreeSet is small a sorted list would perform better. Unfortunately such 
a type is missing from the Java class library. So you need to deal with 
an array or ArrayList and maintain the sort order by your own.


Marcel

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

#34280

On Tuesday 10 May 2016 18:19 CEST, Marcel Mueller wrote:

> On 10.05.16 13.37, Cecil Westerhof wrote:
>> I would like to have an array of TreeSet<Integer>. But that is not
>> possible in Java.
>> So I use:
>> TreeSet<?>[] allNodes;
>
> Since Java uses ->type erasure the types TreeSet<?>[] and
> TreeSet<Integer>[] are identical. The strong typing is mainly a hint

I got a compiler error on TreeSet<Integer>[]. But ArrayList saved my
day.


>> And to add an Integer I use:
>> @SuppressWarnings("unchecked")
>> private static void addConnection(int from, int to) {
>> TreeSet<Integer> treeSet;
>>
>> treeSet = (TreeSet<Integer>) allNodes[from];
>> treeSet.add(to);
>> }
>>
>> Is this a correct way of doing this, or is there a better way?
>
> This is syntactically OK.
>
> The more interesting question is why you need an array of TreeSet.
> What is the semantic meaning of from? And what is the meaning of to?

I am mapping the connections of paths between nodes in a graph. From a
node to a node.


> It looks like an 1:n or m:n mapping. If the number of entries in one
> TreeSet is small a sorted list would perform better. Unfortunately
> such a type is missing from the Java class library. So you need to
> deal with an array or ArrayList and maintain the sort order by your
> own.

I prefer an algorithm that is clear. Only when there is a real problem
with performance I would sacrifice clearness of code.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

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

#34281

On 5/10/2016 5:22 PM, Cecil Westerhof wrote:
> On Tuesday 10 May 2016 18:19 CEST, Marcel Mueller wrote:
> [...]
>> The more interesting question is why you need an array of TreeSet.
>> What is the semantic meaning of from? And what is the meaning of to?
>
> I am mapping the connections of paths between nodes in a graph. From a
> node to a node.

     Perhaps a

	Map<Node,Set<Node>>

or (if there can be more than one Edge from Node X to Node Y)

	Map<Node,Collection<Node>>

might be a more direct representation?

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

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

#34282

On Wednesday 11 May 2016 02:14 CEST, Eric Sosman wrote:

> On 5/10/2016 5:22 PM, Cecil Westerhof wrote:
>> On Tuesday 10 May 2016 18:19 CEST, Marcel Mueller wrote:
>> [...]
>>> The more interesting question is why you need an array of TreeSet.
>>> What is the semantic meaning of from? And what is the meaning of
>>> to?
>>
>> I am mapping the connections of paths between nodes in a graph.
>> From a node to a node.
>
> Perhaps a
>
> 	Map<Node,Set<Node>>

All values from 1 to maxNode are there, but with Map I do not need a
dummy with a null. So this is better I think, yes. Also when I get a
situation where not every node number exists, this is certainly
better. Thanks.


> or (if there can be more than one Edge from Node X to Node Y)
>
> 	Map<Node,Collection<Node>>

There is only one. That is why I used TreeSet.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

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

#34283

On Wednesday, May 11, 2016 at 12:13:59 AM UTC-7, Cecil Westerhof wrote:
>I would like to have an array of TreeSet<Integer>. But that is not 
>possible in Java.

Why do you say it is not possible? This works fine for me:

      TreeSet<Integer>[] tsia = new TreeSet[5];

      for (int i = 0; i < tsia.length; i++) {
         tsia[i] = new TreeSet<Integer>();
      }

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

#34284

On Wednesday, May 11, 2016 at 2:33:21 PM UTC-7, FredK wrote:
> On Wednesday, May 11, 2016 at 12:13:59 AM UTC-7, Cecil Westerhof wrote:
> >I would like to have an array of TreeSet<Integer>. But that is not 
> >possible in Java.
> 
> Why do you say it is not possible? This works fine for me:
> 
>       TreeSet<Integer>[] tsia = new TreeSet[5];

Because you used a raw type. Shame.

> 
>       for (int i = 0; i < tsia.length; i++) {
>          tsia[i] = new TreeSet<Integer>();
>       }

[toc] | [prev] | [standalone]

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

csiph-web