Which datastructure for this issue
Hello there!
Starting point as follows:
I have a class Track. This Track consists of a bunch of Sectors.
Each Sector consits of a start point (x1,y1) and an end point (x2,y2).
For two successive Sectors s1 and s2 it follows, that:
s1.x2 +1 == s2.x1
We have something like that:
s1.x1->s1.x2 -> s2.x1 -> s2.x2 -> s3.x1 -> ...
Now I have two demands, which should be accomplished very efficiently:
1) I want to access a specific Sector by its x-coordinate, i.e. something like that:
track.getSector(xCoordinate)
where xCoordinate lies between x1 and x2 of the wanted Sector.
2) I want to sequentially traverse through the Track. In particular, I want
start at a specific Sector. Sometimes at the first Sector, more often at some Sector in the middle.
These demands are crying for a B* tree (or B+tree) with the x-coordinate as index and the leafs as the actual Sector-objects.
Unfortunately, Java didn't serve any B*tree implementation. So I was wondering, if I could achieve my goals through a "supported" datastructure, maybe a TreeMap or something out of the Collection Framework.
Unfortunately the second, I haven't much experience with TreeMap and his friends ;-)
What would you recommend? Are you d'accord with my tendency toward B*trees or do you have another idea?
Thanks!
A LinkedHashMap may suit your purposes. It's a map that also maintains a doubly linked list of the elements, so you can iterate them in a predictable order. You could store the sectors in the map with the Point as the key, although having two points per sector may be tricky. (Perhaps implement Sector.equals() so that if either the start or end coordinates match the given coordinates, return true?) To traverse the track, just iterate over the values (the Sectors), they'll be returned in the order you added them.
> Hello there!
>
> Starting point as follows:
>
> I have a class Track. This Track consists of a bunch
> of Sectors.
> Each Sector consits of a start point (x1,y1) and an
> end point (x2,y2).
How are they connected? In one straight line, or two lines in a right angle along the x- and y-axis?
> For two successive Sectors s1 and s2 it follows,
> that:
> s1.x2 +1 == s2.x1
>
> We have something like that:
> s1.x1->s1.x2 -> s2.x1 -> s2.x2 -> s3.x1 -> ...
Not sure what you mean by that. Could you elaborate?
Also, when are Sector's the same? How would you compare them? I see you're only talking about x's, does th y-coordinate play a less important role?
Ok, I'll try my best:
The subject is a heightprofile calculated out of GPS-coordinates (not interesting for the problem). I tried to sketch it down:
http://img522.imageshack.us/img522/4748/trackls0.jpg
All Sectors of the Track are DIFFERENT. The two points of a Sector are connected through a straight line.
The y-coordinate is indeed less important, at least in terms of accessing a Sector.
Hope you understand now...
> Ok, I'll try my best:
> The subject is a heightprofile calculated out of
> GPS-coordinates (not interesting for the problem). I
> tried to sketch it down:
>
> http://img522.imageshack.us/img522/4748/trackls0.jpg
>
> All Sectors of the Track are DIFFERENT. The two
> points of a Sector are connected through a straight
> line.
> The y-coordinate is indeed less important, at least
> in terms of accessing a Sector.
>
> Hope you understand now...
Is the second coord. of one sector always the same as the first coord of the next? Which x will you use to retrieve a Sector, the first one or the second one?
If you use a LinkedHashMap, the x-coord is the key, and the Sector is the value. Add them in order (s1, s2, s3, etc.) and you can iterate over them in the same order. You can retrieve a Sector using the same x-coord you stored it with.
> Is the second coord. of one sector always the same as
> the first coord of the next? Which x will you use to
> retrieve a Sector, the first one or the second one?
I think the OP is interested in providing an arbitrary x (let's call it AX) and get the Sector S where S.start.x < AX <= S.end.x, or S.start.x <= AX < S.end.x. But that's just guessing since it still is not clear to me (and maybe you too, I guess).
import java.awt.Point;
import java.util.*;
public class Sector {
public Point start;
public Point end;
public Sector(Point start, Point end) {
this.start = start;
this.end = end;
}
public Sector(int x1, int y1, int x2, int y2) {
this(new Point(x1, y1), new Point(x2, y2));
}
public boolean equals(Object obj) {
if (obj instanceof Sector) {
Sector that = (Sector) obj;
return this.start.equals(that.start) && this.end.equals(that.end);
} else
return false;
}
public int hashCode() {
return start.hashCode() ^ end.hashCode();
}
public String toString() {
return "(" + start.x + "," + start.y + ")-(" + end.x + "," + end.y + ")";
}
public static void main(String[] args) {
NavigableMap < Integer , Sector > map = new TreeMap < Integer , Sector > ();
map.put(0, new Sector(0, 10, 4, 20));
map.put(5, new Sector(5, 10, 9, 20));
map.put(10, new Sector(10, 10, 14, 20));
map.put(15, new Sector(15, 10, 19, 20));
System.out.println(map);
System.out.println();
System.out.println(map.floorEntry(5));
System.out.println(map.floorEntry(9));
System.out.println(map.floorEntry(10));
}
}
So let me get this straight.
You have a data structure, B-tree, that will do what you want. Persumably you even know what a B-tree which is what allowed you to conclude that it was the proper datastructure for what it is that you want to do. AND YET, because no one has wrapped those ten or twenty lines of B-tree code into a "supported" data structure, you are not allowed to build a B-tree and must instead kludge something together our of say, a HashMap, which you don't understand.
Some how, tens and twenty lines of glue code sticking together "supported" **** is OK, but the same number of lines building a data structure that you want is NOT OK?
In any case, a B-tree is NOT what you want. What you have is a sorted list, a list of sectors, sorted by their x1 value. What you are doing is binary searching through that list. An x value that is not the actual x value for one of the elements will, using the standard binary search algorithm (which you will have to write yourself) fail (if you build it correctly) pointing to the sector that contains the desired x value (which is where you would insert that x value if you were actually building a dynamic list which you are not). No need for trees, hash tables, or any of that overhead. Your impulse was correct, that you should get logN behavior, but the "treeness" should be in the search process, not in the data structure.
And of course your other problem, traversal, is pretty easy over a sorted list.
Well. I went to sleep too early, I guess :-)
Thanks so far for the answers:
@hunter9000:
> Is the second coord. of one sector always the same as the first coord of the next?
Yes, it is.
> Which x will you use to retrieve a Sector, the first one or the second one?
I need to use both. The problem is this: I have a x coordinate, i.e. a vertical line that cuts through my track and I need to have the Sector where that happens.
@prometheuzz :
Yes, that's what I want.
@BigDaddyLoveHandles:
Thanks, I will take a look at it. I didn't know the NavigableMap so far. I'll check it out.
@marlin314
> You have a data structure, B-tree...
No, I haven't. But I thought it would be ideal.
> ...you are not allowed to build a B-tree and must instead kludge something together our of say, a HashMap, which you don't understand.
Well, I am allowed, but I would have to do the impl of the B-tree on my own or I would have to search one via google. As I wrote, I'm no expert of the Java Collection Framework and I wanted to know if it already brings some solution along.
> In any case, a B-tree is NOT what you want.
Yeah, you're right. I didn't thought of the sector-x-coordinates beeing sorted. A B tree would bring no extra efficiency.
> (which you will have to write yourself)
And how do I start with this the best? The algorithm is clear, I think. But I don't know where to start. Should I extend some existing List, e.g. ArrayList and only overwrite some methods or what? What is the most clever way to do that?
> ...
> @prometheuzz :
> Yes, that's what I want.
I see, then you can have a look at what BigDaddy posted. Note that you need Java 1.6 for this to work (NavigableMap is not in Java 1.5 and older versions).
And if your sectors are inserted from small to large (w.r.t. their x-coordinates) then you can also use a List and do a binary search on them as marlin suggested.
> And if your sectors are inserted from small to large (w.r.t. their x-coordinates) then you can also use a List and do a binary search on them as marlin suggested.
Indeed. I would reserve the TreeMap for when data must be added (or removed) in a random way.
// assuming that you can figure out how to put your sectors in an array and sort them.
int binarySearch(Sector[] s, int x){ // returns index of relevant sector in sector list or -1
int lo = 0; int hi = s.length; // index of first and last sectors in list
if(x<s[lo].x1 || x>s[hi].x2) return -1; // bail if we are out of bounds.
// now the invariant is that lo and hi bound the x we are seeking,
// we squeeze lo and hi until they are the same
while(lo < hi){
int mid = (lo+hi)/2;
if(x < s[mid].x1){hi = mid - 1;}
else if (x > s[mid].x2) {lo = mid + 1;}
else return mid;
}
return lo; // which == hi if we get here.
}
presumably this code is easy enough to write (and debug) that one saves time by just writing the code rather than by groveling about in some collections architecture looking for something that you can hack up.
