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.fedotov@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.telecomexpress.ru/
> http://harmony.apache.org/
> http://dataved.ru/ http://klsh.ru/
>
>
>
> On Fri, Apr 23, 2010 at 9:05 AM, Lang Yang <yanglang@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 reuse 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.fedotov@gmail.com> wrote:
> >>
> >> Lang,
> >> Thanks for the nice contribution!
> >> 1. Can we reuse 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.telecomexpress.ru/
> >> http://harmony.apache.org/
> >> http://dataved.ru/ http://klsh.ru/
> >>
> >>
> >>
> >> On Fri, Apr 16, 2010 at 10:21 AM, Lang Yang <yanglang@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 nonempty 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 redo 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
> >>
> >
>
