Lang, Thanks for the nice contribution! 1. Can we re-use any other JDK classes to implement service ordering? Maybe some collection method can do? 2. I don't think we need the whole set of providers to be sorted. Ordering is used to answer getServiceProviders() Maybe finding out this particular answer and cache it until the next registration/reordering would suffice?
-- With best regards / с наилучшими пожеланиями, Alexei Fedotov / Алексей Федотов, http://www.telecom-express.ru/ http://harmony.apache.org/ http://dataved.ru/ http://klsh.ru/ On Fri, Apr 16, 2010 at 10:21 AM, Lang Yang <yangl...@gmail.com> wrote: > 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 > >
