Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Help with Searching TreeMaps containing range objects

Reply
Thread Tools

Help with Searching TreeMaps containing range objects

 
 
tim felton
Guest
Posts: n/a
 
      01-09-2004
Hi, I am somewhat of a noob when it comes to Java but some assistance would
be great.

I have two TreeSet objects. They each hold instances of objects that
implement the following interface :

abstract interface IBioFeature extends Comparable, Serializable
{
public String getUID();
public int getStart();
public int getStop();
public int getStrand();
public String getSequence() throws SQLException,
ClassNotFoundException;
public String getContigIdentifier();
}

Note that this interface represents a range in a genomic sequence - that for
all purposes
may be regarded as a large String.

I would like to find elements in each TreeSet whose ranges partially
overlap. I do not want to search both collections and compare values from
getStart() and getStop() as this is very inefficient for large collections
of IBioFeature objects.

Any ideas would be greatly appreciated








 
Reply With Quote
 
 
 
 
Boris Stumm
Guest
Posts: n/a
 
      01-13-2004
tim felton wrote:

> I have two TreeSet objects. They each hold instances of objects that
> implement the following interface :
> abstract interface IBioFeature extends Comparable, Serializable {
> public String getUID();
> public int getStart();
> public int getStop();
> public int getStrand();
> public String getSequence() throws SQLException,
> ClassNotFoundException;
> public String getContigIdentifier();
> }
>
> I would like to find elements in each TreeSet whose ranges partially
> overlap. I do not want to search both collections and compare values from
> getStart() and getStop() as this is very inefficient for large collections
> of IBioFeature objects.


Do the elements in _one_ of the TreeSets overlap (1), or can this only happen
if I take two elements of different TreeSets (2)? What is the sort key?

In the first case, it would be helpful to know the maximum element length to be
able to optimize and get an O(n) performance. In the second case thats much
easier. If in the first case (overlapping in _one_ TreeSet) there is no
maximum element length, i doubt you will get better than O(n^2) or O(n log n),
but i may be wrong.

So, for an efficient solution there is some more information required, as
stated above.

Boris Stumm
 
Reply With Quote
 
 
 
 
Ray Tayek
Guest
Posts: n/a
 
      01-14-2004
tim felton wrote:
> Hi, I am somewhat of a noob when it comes to Java but some assistance would
> be great.
>
> I have two TreeSet objects. They each hold instances of objects...
> abstract interface IBioFeature extends Comparable, Serializable
> public String getUID(); public int getStart(); public int getStop(); public int getStrand(); public String getSequence() .. public String getContigIdentifier();
>


how are you sorting them? the same way?

> I would like to find elements in each TreeSet whose ranges partially
> overlap. I do not want to search both collections and compare values from
> getStart() and getStop() as this is very inefficient for large collections
> of IBioFeature objects. ...
>


consider combining the two into another with perhaps another sort order.
you could maybe define < if max 1 < min 2 and > if max 2 < min 1
otherwise consider them equal. this would get the overlapping ones into
one set perhaps? or refine the above ordering into a total ordering some
way.

or, since the collections just hold refrences, maybe make lists (from/or
sorted sets) of these guys in different sort orders? or find a useful
total ordering on the ones that do overlap, and put others in an other
collection?

just some thoughts off the top of my head.

thanks
---
ray tayek http://tayek.com/ actively seeking telecommuting work
vice chair orange county java users group http://www.ocjug.org/
hate spam? http://samspade.org/ssw/
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Windows 7, searching for all files containing a text string Matty F NZ Computing 25 12-14-2011 06:16 PM
treemaps Javi Jimenez Ruby 8 05-06-2008 03:10 PM
Objects containing objects Steve Perl Misc 2 01-13-2008 12:39 PM
Objects containing a smart ptr (pimpl) and stored in STL containers - help please JackC C++ 3 08-13-2004 11:17 AM
Regular expressions when searching for string containing brackets or parans .. Joe Halbrook Perl Misc 2 10-22-2003 12:27 AM



Advertisments