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 Fri, 23 Apr 2010 05:05:46 GMT
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