D
Daniel Pitts
You're right, that was uncalled for by me. I apologize.Twisted said:
D
djthomp
using lists at all.
2) If you don't mind some temporary storage,
LinkedList merge(List multipleLists) {
LinkedList newList = new LinkedList();
Set newListSet = new HashSet();
for(Iterator li = multipleLists.iterator(); li.hasNext(){
List l = (List)li.next();
for(Iterator i = l.iterator(); i.hasNext()
Object o = i.next();
if(!newListSet.contains(o)) {
newListSet.add(o);
newList.add(o);
}
}
}
return newList;
}may serve (untested code)
I'm assuming your multiple lists are held in a list...
I think that's O(N).
It also kind of retains the order of the input lists
BugBear
It can be simpler if you take advantage of set's addAll method:
LinkedList merge(List multipleLists) {
Set newListSet = new HashSet();
for(Iterator li = multipleLists.iterator(); li.hasNext()
newListSet.addAll((List)li.next());
return new LinkedList(newListSet);
}
D
Daniel Pitts
djthomp said:It can be simpler if you take advantage of set's addAll method:
LinkedList merge(List multipleLists) {
Set newListSet = new HashSet();
for(Iterator li = multipleLists.iterator(); li.hasNext()
newListSet.addAll((List)li.next());
return new LinkedList(newListSet);
}
Or, using a more type safe, Java 1.5 approach:
public static <E> List<E> merge(
Iterable<? extends Collection<? extends E>> collections) {
final Set<E> set = new LinkedHashSet<E>();
for (Collection<? extends E> collection: collections) {
set.addAll(collection);
}
return new LinkedList<E>(set);
}
D
Damo
hello all,
I was'nt ignoring you're advice. I was just exploring all the options,
seeing as I need some of the advantages of Linked Lists and Sets. In
particular the no duplicate feature of sets and i needed to keep the
order items were added(not necessarlly sorted)(Linked Lists), and
inserting into a particulaar point in the colection(Linked Lists).
I have been trying to work with sets but they dont seem to suit my
needs. Its too convoluted to retain the ordering of the collection
Anyway you're words of advice are appreciated.
I was'nt ignoring you're advice. I was just exploring all the options,
seeing as I need some of the advantages of Linked Lists and Sets. In
particular the no duplicate feature of sets and i needed to keep the
order items were added(not necessarlly sorted)(Linked Lists), and
inserting into a particulaar point in the colection(Linked Lists).
I have been trying to work with sets but they dont seem to suit my
needs. Its too convoluted to retain the ordering of the collection
Anyway you're words of advice are appreciated.
D
djthomp
Before choosing not to use a Set because of order retention problems,
you might take at LinkedHashSet. It keeps track of item order by using
saving the insertion order with an internal linked list. Iterating
over the LinkedHashSet gives you its contents in their original order.
http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedHashSet.html
O
Oliver Wong
Damo said:
Maybe you can elaborate on this requirement to help us provide you with
better advice.
- Oliver
D
djthomp
....you might take -a look- at LinkedHashSet. Sigh.
P
Patricia Shanahan
djthomp said:
More generally, there are java.util.Set implementations that provide
each of the common forms of ordering, so I tend to think Set as soon as
I know I want to avoid duplicates, even if it needs to be ordered.
Don't care about order: HashSet
Insertion order: LinkedHashSet
Natural order: TreeSet
Comparator-specified order: TreeSet
Patricia
B
bugbear
Daniel said:
Yeah - sorry, we're still using Java 1.4 here, for reasons
of install base compatibility.
BugBear
J
John Ersatznom
Patricia said:
Can any of these support inserting a new element into the middle of the
ordering? Well, the first can't, and the third and fourth can if you do
the "BASIC line numbering trick" and give every item a position number,
where you leave gaps so you can fill in missing positions later. That's
a bit of a hack (but it can be done, e.g. using doubles and suggesting
the client code insert baz between foo and bar by setting
(foo.getPosition() + bar.getPosition())/2 as the position for baz.
Of course, once you are comparing stuff using a position number field
you set to suit, you're looking at a comparator that isn't consistent
with equals, which is going to bomb your TreeSet anyway. Now you need
the objects to use their position number to decide equality (and hash
code) too. You probably actually want to wrap them with a
public class PositionalHolder<T>
implements Comparable<PositionalHolder<T>> {
public double position;
public T object;
public PositionalHolder (T object, double position) {
this.object = object;
this.position = position;
}
@SuppressWarnings("unchecked")
public void equals (Object x) {
return (x == this)
||(x instanceof PositionalHolder
&& ((PositionalHolder)x).position
== position);
}
public int hashCode () {
return Double.valueOf(position).hashCode();
}
public int compareTo (PositionalHolder<T> other) {
return (position < other.position)
?-1
(position > other.position)?1:0);}
public void putBetween (PositionalHolder<T> x,
PositionalHolder<T> y) {
// Convenience method.
position = (x.position + y.position)/2;
}
}
Of course, Bad Things will likely happen if you a) use infs or nans as
positions, b) use the same position for multiple objects in the same
ordered collection, or c) change something's position while it's in one
rather than remove it, change its position, and then reinsert it. You
might want to prevent the last by making the PositionalHolder immutable
with a (x, object, y) "between" constructor, a just-an-object
constructor (position gets zero), a "before" constructor (object, y)
that uses y.position - 1, and an "after" constructor (x, object) that
uses x.position + 1. (This overload is clearly ambiguous if you try to
put a PositionalHolder inside another PositionalHolder but why the hell
would you?)
J
John Ersatznom
John said:public class PositionalHolder<T>
implements Comparable<PositionalHolder<T>> {
public double position;
public T object;
public PositionalHolder (T object, double position) {
this.object = object;
this.position = position;
}
@SuppressWarnings("unchecked")
public void equals (Object x) {
return (x == this)
||(x instanceof PositionalHolder
&& ((PositionalHolder)x).position
== position);
}
public int hashCode () {
return Double.valueOf(position).hashCode();
}
public int compareTo (PositionalHolder<T> other) {
return (position < other.position)
?-1
}
public void putBetween (PositionalHolder<T> x,
PositionalHolder<T> y) {
// Convenience method.
position = (x.position + y.position)/2;
}
}
Naturally, it was right after posting this that I came up with the
ArbitraryHolder, which holds one object it "holds" and a second whose
equals(), hashCode(), and compareTo() get used. And can be constructed
with an explicit comparator to use. On either the "held" object or the
object used to define the "equals" and "hashCode" behavior...
D
Daniel Pitts
bugbear said:
I feel really sorry for you. Java 1.5 is a vast improvement over 1.4.
In my opinion, the distance between 1.1 and 1.4 is the same as 1.4 to
1.5.
I find it a lot easier to upgrade an install base, than to maintain 1.4
code.
Daniel.
J
John Ersatznom
Daniel said:
Agreed. All those casts! They make pre-1.5 Java the first runner up for
the Too Damn Many Parentheses Award. (We all know who the actual winner
is, I trust.)
D
Daniel Pitts
John said:
Whitespace's cousin Parentheses?