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, 26 Apr 2010 11:52:49 GMT
Lang,
I'm looking forward for your next patch.



--
With best regards / с наилучшими пожеланиями,
Alexei Fedotov / Алексей Федотов,
http://www.telecom-express.ru/
http://harmony.apache.org/
http://dataved.ru/ http://klsh.ru/




On Sun, Apr 25, 2010 at 2:15 AM, Lang Yang <yanglang@gmail.com> wrote:
> Yes, I have noticed this issue when I was trying to implement it today. The
> iterator should be able to run more than once. Keep a copy of incomingEdges
> Map within the iterator class would be good solution?
>
> Thanks,
>
> Lang
>
> On Fri, Apr 23, 2010 at 10:11 AM, Alexei Fedotov <alexei.fedotov@gmail.com>
> wrote:
>>
>> 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