Christopher Arthur

Ranch Hand

Posts: 149

posted 11 years ago

Hello,

It seems that the Set interface in 1.4.2 does not come extensively implemented, so before I dive into coding what I want, I thought that I would post here to see if anyone knows if I'll be reinventing the wheel.

Basically, I'm wanting to develop an interface for a relation on a set or pair of sets, which in the hierarchy of types should be either an interface or a superclass of the Comparator interface--if we take our meaning akin to mathematical definitions. For some applications a total ordering (given by comparator) is too strong (but probably the easiest to program), and instead we would like to take an arbitrary relation on sets and determine if it meets certain criteria; e.g., is it reflexive? symmetric? transitive? functional? etc...

For my own problem I'm just considering a finite set of integers, and a collection of pairs of integers taken from the set, and i want to know if the all the pairs together define an equivalence relation and more importantly, what are the equivalence classes of the set?

I figure that I could code something quick and dirty to suit my own purpose, but it seems more sensible to try to do something that fits nicely into the larger context of the API (meaning: if I call it a set, then I should use the Set Interface).

Any thoughts?

It seems that the Set interface in 1.4.2 does not come extensively implemented, so before I dive into coding what I want, I thought that I would post here to see if anyone knows if I'll be reinventing the wheel.

Basically, I'm wanting to develop an interface for a relation on a set or pair of sets, which in the hierarchy of types should be either an interface or a superclass of the Comparator interface--if we take our meaning akin to mathematical definitions. For some applications a total ordering (given by comparator) is too strong (but probably the easiest to program), and instead we would like to take an arbitrary relation on sets and determine if it meets certain criteria; e.g., is it reflexive? symmetric? transitive? functional? etc...

For my own problem I'm just considering a finite set of integers, and a collection of pairs of integers taken from the set, and i want to know if the all the pairs together define an equivalence relation and more importantly, what are the equivalence classes of the set?

I figure that I could code something quick and dirty to suit my own purpose, but it seems more sensible to try to do something that fits nicely into the larger context of the API (meaning: if I call it a set, then I should use the Set Interface).

Any thoughts?

posted 11 years ago

Although I can't tell for certain what you have in mind, I just want to point out that very few abstractions are really universal. Just because the API defines a "Set" interface doesn't mean that you could use it to represent any possible interpretation of the definition of a "set" in the mathematical sense. For example, Venn diagrams show sets of points -- infinite sets, but sets just the same.

So my point is that looking to see if java.util.Set is useful is a good idea. Contorting your implementation to fit into it is not, especially if (as it sounds like here) your implementation will have many special methods and so pure "programming to the interface" won't really be feasible.

So my point is that looking to see if java.util.Set is useful is a good idea. Contorting your implementation to fit into it is not, especially if (as it sounds like here) your implementation will have many special methods and so pure "programming to the interface" won't really be feasible.

Christopher Arthur

Ranch Hand

Posts: 149

posted 11 years ago

This is a good point. I suppose that the API is intended to make things easier for the programmer, not harder.

With regard to infinite sets, of course we don't ever list explicitly their contents, but often we do describe them by a rule. I suppose that such a rule is like defining a java class and asking how many distinct ways can the class be instantiated modulo some notion of equivalence. In this way, I suppose that AbstractSet could be implemented so that an instance would contain explicitly only a reference to a class, but that some call to toArray() could be tailored to construct a some finite collection of instances on the fly. But now I am just with my head in the clouds.

My real problem is that my set contains the numbers 1 to 6. I have another set that contains pairs of these numbers 1 to 6. (This second set is the relation on the first set). I want to know if the relation contains loops, and if so, what they are. For example, (1,2),(2,3) and (3,1) together make a loop since 1 goes to 2, 2 goes to 3, and 3 goes back to 1. As you can see, for an object.equals() method, this property (transitivity) is necessary but not sufficient to fulfill the contract.

On the other hand, if object.equals() with proper implementation is the only method that I have for comparison, then I will not get the result that I want. For example, (1,2),(3,1) is not a cycle by my definition, but 1=2 and 3=1 imply 3=2, so the virtual machine might want to identify it incorrecty.

My intuitive approach to this problem would probably involve some kind of graph as a generalization of a linked list or tree, with members like this:

public class node {

short data;

boolean cycle = false

Set children;

Set ancestry;

public node(short data){

this.data = data;

children = new Set();

ancestry = new Set();

}

public void addChild(short data){

Node child = new Node(data);

children.add(child);

If(this.ancestry.contains(child)) then this.cycle = true;

child.ancestry.addAll(this.ancestry);

child.ancestry.add(this);

}

public boolean equals(Node n) {

if(this.data = n.data) return true;

else return false;

}

}

}

[ March 08, 2006: Message edited by: Christopher Arthur ]

With regard to infinite sets, of course we don't ever list explicitly their contents, but often we do describe them by a rule. I suppose that such a rule is like defining a java class and asking how many distinct ways can the class be instantiated modulo some notion of equivalence. In this way, I suppose that AbstractSet could be implemented so that an instance would contain explicitly only a reference to a class, but that some call to toArray() could be tailored to construct a some finite collection of instances on the fly. But now I am just with my head in the clouds.

My real problem is that my set contains the numbers 1 to 6. I have another set that contains pairs of these numbers 1 to 6. (This second set is the relation on the first set). I want to know if the relation contains loops, and if so, what they are. For example, (1,2),(2,3) and (3,1) together make a loop since 1 goes to 2, 2 goes to 3, and 3 goes back to 1. As you can see, for an object.equals() method, this property (transitivity) is necessary but not sufficient to fulfill the contract.

On the other hand, if object.equals() with proper implementation is the only method that I have for comparison, then I will not get the result that I want. For example, (1,2),(3,1) is not a cycle by my definition, but 1=2 and 3=1 imply 3=2, so the virtual machine might want to identify it incorrecty.

My intuitive approach to this problem would probably involve some kind of graph as a generalization of a linked list or tree, with members like this:

public class node {

short data;

boolean cycle = false

Set children;

Set ancestry;

public node(short data){

this.data = data;

children = new Set();

ancestry = new Set();

}

public void addChild(short data){

Node child = new Node(data);

children.add(child);

If(this.ancestry.contains(child)) then this.cycle = true;

child.ancestry.addAll(this.ancestry);

child.ancestry.add(this);

}

public boolean equals(Node n) {

if(this.data = n.data) return true;

else return false;

}

}

}

[ March 08, 2006: Message edited by: Christopher Arthur ]