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 Tue, 27 Apr 2010 08:27:21 GMT
Hi Alexei,

Task HARMONY-6507[1] has been created for this issue. I have attached a
patch to that.

That implementation is still missing one functionality: avoid cycle in the
sorting algorithm. I will work on that

Thanks,

Lang


[1] - https://issues.apache.org/jira/browse/HARMONY-6507

On Mon, Apr 26, 2010 at 7:52 AM, Alexei Fedotov <alexei.fedotov@gmail.com>wrote:

> 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
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message