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 Fri, 23 Apr 2010 13:01:25 GMT
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
View raw message