harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Lang Yang <yangl...@gmail.com>
Subject Re: [classlib][ImageIO] Ordering in ServiceRegistry
Date Sat, 24 Apr 2010 22:13:18 GMT
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.telecom-express.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 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.fedotov@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 <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 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
> >>
> >
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message