Lang, 1. Could you please describe a scenario when setOrdering() would be called? Currently there are no examples in the code base [1], are they?
2. Any request to getServiceProviders() returns a list, not a graph. Even if two elements are not comparable, the function will return them in some order. Could the list collection be sufficient to handle complexity of the task? [1] http://www.google.com/codesearch?hl=ru&lr=&q=setOrdering&exact_package=http://svn.apache.org/repos/asf/harmony/enhanced/classlib/trunk -- With best regards / с наилучшими пожеланиями, Alexei Fedotov / Алексей Федотов, http://www.telecom-express.ru/ http://harmony.apache.org/ http://dataved.ru/ http://klsh.ru/ On Fri, Apr 23, 2010 at 9:05 AM, Lang Yang <yangl...@gmail.com> wrote: > > Hello Alexei, > Thanks for those suggestions. I have been busy these few days as this > semester is ending in these two weeks in Canada. > From description of setOrdering and unsetOrdering methods, we have to save > all the preferences between two objects in order to tell these functions > whether a preference is set or not. I don't think there's something I could > re-use directly. So, I am thinking of use Map to store the preferences. And > still stick with this Topological Sorting algorithm. > I agree with the second idea, cache the sorting result. Every time when > getServiceProviders() is called, check if there was any change made. If there > was, performance the sorting function again, if there wasn't, just return the > cached result. > I will implement this idea in few days, and post updates to this mailing list. > Kind Regards, > Lang > > On Mon, Apr 19, 2010 at 6:53 AM, Alexei Fedotov <alexei.fedo...@gmail.com> > wrote: >> >> 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 >> >
