harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Lang Yang <yangl...@gmail.com>
Subject [classlib][ImageIO] Ordering in ServiceRegistry
Date Fri, 16 Apr 2010 06:21:57 GMT
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