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 Sat, 24 Apr 2010 22:15:55 GMT
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