I am working through some general algorithm questions and I came upon a java solution that uses the following code to sort a collection of edges. Each edge is an x position and a height.
Collections.sort(edges, new Comparator<Edge>() {
public int compare(Edge a, Edge b) {
if (a.x != b.x)
return Integer.compare(a.x, b.x);
if (a.isStart && b.isStart) {
return Integer.compare(b.height, a.height);
}
if (!a.isStart && !b.isStart) {
return Integer.compare(a.height, b.height);
}
return a.isStart ? -1 : 1;
}
I would like to do something similar in python, but I'm not sure where to start. At first I thought I could just add a key function, but I don't see how I would do that in this case. My current quick and dirty implementation is far from efficient. I represent each edge as a list, [x, height] and I represent "start edges" as a positive value and "end edges" as a negative value (that isn't too relevant here).
def sort_edges(edges):
edges.sort(key=lambda x: x[0])
for i in range(len(edges)-1):
edge_one = edges[i]
edge_two = edges[i+1]
# Continue if edges are not on same x
if edge_one[0] != edge_two[0]:
continue
# Compare height if both are start edges
if edge_one[1] > 0 and edge_two[1] > 0:
if edge_two[1] > edge_one[1]:
temp = edge_one
edges[i] = edge_two
edges[i+1] = temp
# Compare height if both are end edges
if edge_one[1] < 0 and edge_two[1] < 0:
if edge_two[1] > edge_one[1]:
temp = edge_one
edges[i] = edge_two
edges[i+1] = temp
# Start edges come first
if edge_two[1] > 0 and edge_one[1] < 0:
temp = edge_one
edges[i] = edge_two
edges[i+1] = temp
edges = [[1, 3], [2, 5], [5, -3], [4, -5]]
old = None
while old != edges:
old = copy(edges)
sort_edges(edges)
