harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Alexei Fedotov <alexei.fedo...@gmail.com>
Subject Re: [classlib][ImageIO] Ordering in ServiceRegistry
Date Mon, 19 Apr 2010 10:53:53 GMT
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