TreeSet and HashSet

I have a class, SortedHashSet.

It is supposed to incorporate both TreeSet and HashSet. The class is as below:

import java.io.*;
import java.lang.*;
import java.util.*;

class SortedHashSet<T> extends TreeSet<T>
{
      
}

I have to override the add function such that it will maintain a TreeSet and a HashSet.

Can anyone advise me how it can be done?
For HashSet, I will need to declare a variable of type, HashSet. How about TreeSet?

Thanks in advance.

Regards


yiyi83Asked:
Who is Participating?
 
birthstarCommented:
If you really do want to do this then I think you would want to agregate the treeset and the hash set into a third class that does not extend either of them but does implement the correct interfaces, I think that this is what objects is saying in their post. This method of agregation should give you the greatest flexibility in your code.
 
As a very rough outline the following might be useful

import java.util.*;

public class SortedHashSet implements SortedSet {

private TreeSet myInternalTree;
private HashSet myInternalHashSet;

// Constructors make sure that both internal sets are initialised by every constructor that you implement

// Methods make sure that each method that modifies the SortedHashSet in any way is directed to both internal sets

// for example addAll might be as follows. The general contract for the method is to return true if the set has changed therefore if either of the internal sets return that they have changed then this method will return true. (Since they are both sets they should always both return true together you might want to test for this)

public boolean addAll (Collection c) {

boolean b1 = myInternalTree.addAll(c);
boolean b2 =  myInternalHashSet.addAll(c);

return b1 || b2;
}

}

You would need to perform a similar operation for each of the methods from the Collection, Set and SortedSet interfaces  
Then make sure that the method that you want to have O(1) performace for is directed only at the hash set and make sure that the iterator method is sent only to the treeset

It should be simple to do unless you want to start modifying the data using Iterators (using remove()).

I hope that this helps.
0
 
hoomanvCommented:
Im not sure if you can have both HashSet and TreeSet behavior in one class
hash set does not guarantees the order of iteration
on the other hand adding an elemnet to TreeSet is O(log n) but HashSet is O(1) (Constant time)
how is it possible to have a sorted hash set ?

if you want to be able to iterate through the set in ascending order, try
Set sortedSet= new TreeSet( yourHashSet );
0
 
KantiCommented:
This link will give you how to  use all three HASHSET, LINKEDHASHSET, AND TREESET. You
can see the add methods of all three

http://java.sun.com/developer/JDCTechTips/2002/tt1105.html
0
Cloud Class® Course: Python 3 Fundamentals

This course will teach participants about installing and configuring Python, syntax, importing, statements, types, strings, booleans, files, lists, tuples, comprehensions, functions, and classes.

 
yiyi83Author Commented:
Hi,

Just a general idea.

I will be maintaining one HashSet and one TreeSet. During iteration, I will call the TreeSet. During searching, I will call the HashSet.

However, I am just wondering if anyone can tell me given that I extends TreeSet and contains HashSet, how do I program for the add(Object e) to add an item to both TreeSet and HashSet?

Hope that will give a fair idea.

Thanks.
0
 
CEHJCommented:
>>I will be maintaining one HashSet and one TreeSet.

Why?
0
 
hoomanvCommented:
> how do I program for the add(Object e) to add an item to both TreeSet and HashSet?

class SortedHashSet<T> extends TreeSet<T>
{
      HashSet<T> hs;

      public boolean add(T o) {
            boolean b;
            b = super.add(o);
            b = hs.add(o) & b;
            return b;
      }
}
0
 
CEHJCommented:
Why would you extend TreeSet and not simply use one? A TreeSet is *already* a SortedSet
0
 
Mayank SAssociate Director - Product EngineeringCommented:
You can of course, have your own class that maintains a HashSet and a TreeSet, both pointing to the same objects (so the same objects will have 2 references, one in the TreeSet and one in the HashSet). But what's the use?
0
 
yiyi83Author Commented:
Purpose:

So that it will optimize the search and iteration of items in the TreeSet or HashSet.

Hi Hoomany,

I want to overrides the add function of both TreeSet and HashSet. Hence, within my own add function, I cannot make use of that of theirs.

Regards
0
 
CEHJCommented:
>>So that it will optimize the search ...

When you say 'search' what do you mean? The entries are accessed by key ...
0
 
hoomanvCommented:
> I want to overrides the add function of both TreeSet and HashSet

so you need to inherit your own class from HashSet and override the default add method
then use that derived class instead of HashSet within SortedHashSet class
and call when you call add, the overridden method will be invoked

public boolean add(T o) {
    return super.add(o) & derivedHashSet.add(o);
}

0
 
hoomanvCommented:
>>So that it will optimize the search ...

I think he/she wants both optimized insertion and ordered iteration
0
 
yiyi83Author Commented:
Hi,

Search referring to finding out if an item exists within the HashSet.

Basically, I want to achieve O(1) searching and O(n) sorted iteration.

O(1) searching is achieved through HashSet.
O(n) sorted iteration is achieved through TreeSet.

My class is inheriting from TreeSet. Hence, I am containing the HashSet.
0
 
CEHJCommented:
You might find

http://javolution.org/api/index.html

interesting
0
 
objectsCommented:
> I want to overrides the add function of both TreeSet and HashSet. Hence, within my own add function, I cannot make use of that of theirs.

From what you've said you would appear to only need to override the add() method of TreeSet as hoomanv has posted above.

> O(1) searching is achieved through HashSet.

You'll also need to override contains in that case

public boolean contains(Object o)
{
   return hs.contains(o);
}

You'll also need to override all of TreeSet's methods that modify the TreeSet's content to update both the TreeSet *and* the HashSet similiar to how hoomanv showed for the add() method.
0
 
yiyi83Author Commented:
Hi,

Thanks all for the responses. I been busy trying out the different suggestions. They are all helpful.

Sorry for the lateness in awarding the points. Thank you.

Regards
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.