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.fedo...@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 <yangl...@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.fedo...@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.fedo...@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.fedo...@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 <yangl...@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.fedo...@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 <yangl...@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 > >> >>>> > >> >>> > >> >> > >> > > > > > >
