I am designing a simple GUI that will allow a user to create a GPX route by clicking repeatedly on a map panel. I am faced with a design dilemma for how to represent the nodes and route. This construct can be abstracted as follows:
- the user clicks n times on the screen in sequence to create a chain of n nodes
- after a chain has been completed, a user can add more nodes to it, either by selecting nodes in the middle (inserting between existing nodes) or by simply automatically appending to the end with his next click
At first I was determined to use a Java Collections class to represent the chain, but there are unexpected difficulties with that. On the surface, this would appear to be a perfect example of a LinkedList, but consider as follows. If the user wishes to insert a node in the middle of the chain, he first chooses some node on screen that he wishes to insert a new node before. If the node belongs to a linked list, it will need to maintain a reference to its encompassing list (a somewhat unusual practice, I’d think), and even then we will still have to locate the node in the list before we can insert. So we have to:
- find the node (linear time)
- insert the new node (constant time)
Or if I try the same thing with an ArrayList, it also performs at best in linear time.
- find the node (linear time)
- insert the new node (linear time)
But neither case really seems desirable. I briefly flirted with the idea of using a LinkedHashSet, but it does not allow insertion into the middle of the linked list, nor does it seem fundamentally correct to use a set implementation for something like this.
So here is what I came up with:
class Node {
Node previous;
Node next;
Chain chain;
}
A Node maintains only a reference to its previous and next nodes, as well as the chain it belongs to (again, this latter part seems unconventional and possibly even wasteful to me, but I’m convinced it may be necessary here).
class Chain {
Node first;
Node last;
}
The chain knows only what its first and last nodes are.
Now, if a user wants to insert a node in the middle of the chain? He selects the node, which simply updates the first/last references of itself and its neighbors. If he wants to add nodes to the end of a chain? He simply selects any node on screen (which is aware of what chain it belongs to, and therefore what the last node in that chain is), and the chain immediately begins updating link references for the last node and each node added after it, as well as keeping its own “last” reference up to date.
I really wanted to use a Collections class, but this approach seems better to me. But I’d love to here thoughts/criticisms from more experienced programmers. Thanks.
3
Mutable circular references are nasty. Just use an ArrayList and don’t worry about it.
You can see all of the elements on screen: it’s not going to be so long that linear time takes any time.
re dude demanding an explanation why mutable circular references are nasty: like, as in bad code. It’s an inefficient use of programmer-thinky-time, not unavoidably problematic.
7
You really want to leverage Java-provided “list maintenance” functionality. Go with ease of use first and worry about performance later. “pre-optimization” is a dog chasing its tail.
Class Waypoint {
string name;
double lat; // I'm not saying double is necessarily the ideal type here.
double long;
// other stuff as needed for GPX
RouteCollection myRoutes; // all the routes containing this waypoint
}
Class Route {
LinkedList<Waypoint> myRoute;
string name;
Waypoint start { return myRoute[0]; }
Waypoint end { return myRoute[myRoute.Length-1] };
}
Class RouteCollection {
ArrayList<Route> myRoutes;
// maybe a dictionary/hash instead, the key being the Route.name perhaps
// order is not important in this collection, I suspect.
}
Class WaypointJanitor {
// keeps cross references in the various classes in sync
// for example updates the Waypoint.myRoutes when a Route object is edited
// I can see the main add/delete/insert functionality in this class,
// passing routes & waypoint parameters. And all the complexity is contained, keeping your data structure classes clean and simple.
}
The UI Provides Context for Inserting
If the node belongs to a linked list, it will need to maintain a reference to its encompassing list
“if the node belongs..” This is confusing. Seems to me that in the UI I create routes/chains/tracks explicitly, giving each a name probably. Thus there is no question about. When I want to insert a waypoint I designate through the UI what route I’m manipulating. Further, any given waypoint (arbitrary lat/long coordinate) could be part of any number of routes; by explicitly selecting the route to edit there is no ambiguity.
3