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