Hello Alexei, The ordering is set in pairwise, collision might happen. Let's say we have 3 service providers (A,B, and C) in a certain category. We set the following preferences:
setOrdering(category, A, B); // means A > B setOrdering(category, B, C); setOrdering(category, C, A); Under this certain situation, A cycle occurs (A>B>C>A). According to the description: If the graph of pairwise orderings contains cycles, any providers that belong to a cycle will not be returned [1]. I think the implementation would be more complicated to let a List collection class comply this rule. I will think of the solution and see which way is better. Thanks, Lang [1] - http://java.sun.com/j2se/1.4.2/docs/api/javax/imageio/spi/ServiceRegistry.html#getServiceProviders(java.lang.Class, boolean) On Fri, Apr 23, 2010 at 9:01 AM, Alexei Fedotov <alexei.fedo...@gmail.com>wrote: > 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 > >> > > >
