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 14:11:44 GMT
As for particalr algortithm, I like the idea to forget about the list
and return the iterator - that makes logic simpler. I'm not sure the
logic calculating incoming edges is correct. Would the iterator work
more than once? It would reduce incoming node caunts to zero on the
first run, wouldn't it?

--
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 5:44 PM, Alexei Fedotov
<alexei.fedotov@gmail.com> wrote:
> Well, I don't mind  using the algorithm from wiki. Why I have asked
> all that questions?
>
> The actual complexity depends on the typical use case. For example, if
> no algoritms intend to use setOrdeirng(), then no sorting is required.
>
> If we have small number of setOrdering() calls, then we can just keep
> the list of providers sorted after each setOrdering() call, thus no
> cache would be needed.
>
>
>
> --
> 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 5:01 PM, 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
View raw message