Hello guys,
I mentioned that the ordering feature in ServiceRegistry is missing from
Harmony JDK on my GSoC proposal. I have been working on this in past few
days and come up with this rough idea. I don’t know if this way works or
not, I need your input ;)
So, the background is that user can have several SPIs in certain category.
Sometime they would also like to set preferences for those SPIs. Preference
is always set in pairwise. With ordering feature enabled, when user gets
service providers, the results should be in order (respect all the
preferences that set by user).
Because the preference is set in pairwise, I think this problem could be
treated as Directed Acyclic Graph (DAG) [1] ordering problem: SPIs would be
vertices and pairwise preferences would be directed edges that connect two
SPIs. Topological Sorting algorithm would be implemented for DAG sorting
issue (this is the easiest one?).
I had looked up in Wikipedia and got the detailed steps for Topological
Sorting [2]:
First, find a list of "start nodes" which have no incoming edges and insert
them into a set S; at least one such node must exist if graph is acyclic.
Then:
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
output error message (graph has at least one cycle)
else
output message (proposed topologically sorted order: L)
So, I guess for each service providers, we need to store at least two
things: the number of incoming edges, and outgoing nodes. I came up with a
class like this:
private static class ProviderNode {
private int incomingEdges; // number of incoming edges
private Set<Object> outgoingNodes; // all the outgoing nodes
private Object provider;
public ProviderNode(Object provider) {
incomingEdges = 0;
outgoingNodes = new HashSet<Object>();
this.provider = provider;
}
public Object getProvider() ;
public Iterator getOutgoingNodes();
public boolean addOutEdge(Object provider);
public boolean removeOutEdge(Object provider);
public void addInEdge();
public void removeInEdge();
public int getIncomingEdges();
public boolean contains(Object provider);
}
And we also need to add some fields and methods to ProviderMap class (this
class stores SPIs within given category):
private static class ProvidersMap {
// create a ProviderNode for each service provider
Map<Object, ProviderNode> nodeMap = new HashMap<Object, ProviderNode>();
public boolean setOrdering(Object firstProvider, Object secondProvider)
{
ProviderNode firstNode = nodeMap.get(firstProvider);
ProviderNode secondNode = nodeMap.get(secondProvider);
// if the ordering is already set, return false
if (firstNode.contains(secondProvider)) {
return false;
}
// put secondProvider into firstProvider's outgoing nodes list
firstNode.addOutEdge(secondProvider);
// increase secondNode's incoming edge by 1
secondNode.addInEdge();
return true;
}
public boolean unsetOrdering(Object firstProvider, Object
secondProvider) {
ProviderNode firstNode = nodeMap.get(firstProvider);
ProviderNode secondNode = nodeMap.get(secondProvider);
// if the ordering is not set, return false
if (!firstNode.contains(secondProvider)) {
return false;
}
// remove secondProvider from firstProvider's outgoing nodes list
firstNode.removeOutEdge(secondProvider);
// decrease secondNode's incoming edge by 1
secondNode.removeInEdge();
return true;
}
}
There is also an Iterator for ordered list, this basically implemented
sorting part of Topological Sorting:
private static class OrderedProviderIterator implements Iterator {
// store nodes which has 0 incoming edge
private List<ProviderNode> emptyList = new ArrayList<ProviderNode>();
public OrderedProviderIterator(Iterator it) {
// find all the nodes that with 0 incoming edge
while (it.hasNext()) {
ProviderNode node = (ProviderNode)it.next();
if (node.getIncomingEdges()==0) {
emptyList.add(node);
}
}
}
public boolean hasNext() {
return !emptyList.isEmpty();
}
public Object next() {
if (emptyList.isEmpty()) {
throw new NoSuchElementException();
}
// get the first node from emptyList
ProviderNode node = emptyList.get(0);
// find all the outgoing nodes
Iterator it = node.getOutgoingNodes();
while (it.hasNext()) {
ProviderNode outNode = (ProviderNode) it.next();
// remove the incoming edge from the node.
outNode.removeInEdge();
// add to the emptyList if this node's incoming edge is equal to 0
if (outNode.getIncomingEdges() == 0) {
emptyList.add(outNode);
}
}
return node.getProvider();
}
public void remove() {
throw new UnsupportedOperationException();
}
}
This is just my thought, I haven’t tested it yet. I don’t know if there
anything I need to re-do or improve? Please let me know your opinion.
Thank you,
Lang
[1]: http://en.wikipedia.org/wiki/Directed_acyclic_graph
[2]: http://en.wikipedia.org/wiki/Topological_sorting
