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 Fri, 23 Apr 2010 13:44:34 GMT
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