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 >> >>>> >> >>> >> >> >> > > >
