Re: [collections] Name that data structure
Wendy Smoak wrote: I put together a simple example that demonstrates the problem: http://wiki.wendysmoak.com/cgi-bin/wiki.pl?CircularFifoBuffer Bug? Surely I'm not doing anything wrong by calling remove(...) on a Collection? (Inefficient though it may be, first I just want to see it work.) Your wiki indicates that this is solved in SVN. Is this the case? Meanwhile, is there another way I can get the buffer to be in the correct LRU order? The LRUMap did work, but it's ugly having to put the empty String into the Map, when I don't need key/value pairs. Our only LRU implementation is LRUMap at present. Stephen - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [collections] Name that data structure
From: Stephen Colebourne [EMAIL PROTECTED] Your wiki indicates that this is solved in SVN. Is this the case? It looks like it. I only got as far as creating the test case and seeing it NOT fail. (After I posted the original message.) I need the LRU behavior, though, so I don't think CircularFifoBuffer is really going to do it. I'll probably go back to LRUMap; it beats having to write and maintain it myself. :) Thanks, Wendy Smoak - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [collections] Name that data structure
Tim,
I'm using your suggestion, and thanks for providing a complete example! I
needed that. :)
(It's here if anyone needs to refer to it:
http://www.mail-archive.com/commons-user%40jakarta.apache.org/msg11963.html )
As written, however, it doesn't rearrange the values when you re-visit an
item. In your example, after '1' gets added for the second time, the list
should be 2,3,4,1 and instead it is still 1,2,3,4. (And that means '1' will
be evicted too soon.)
To fix that, I tried to simply remove any item before I add it, so it will
always go to the end of the list as a new item:
public static void add(Buffer recentVisited, String page) {
recentVisited.remove( page );
try {
recentVisited.add( page );
} catch( IllegalArgumentException iae ) {
// do nothing, buffer will complain if predicate fails.
}
System.out.println( recentVisited );
}
And was surprised to get :
run:
[java] [Page 1]
[java] [Page 1, Page 2]
[java] [Page 1, Page 2, Page 3]
[java] [Page 1, Page 2, Page 3, Page 4]
[java] [Page 2, Page 3, Page 4, Page 1] --- it's working!
[java] [Page 3, Page 4, Page 1, Page 2]
[java] java.lang.ArrayIndexOutOfBoundsException: -1
...
[java] Caused by: java.lang.ArrayIndexOutOfBoundsException: -1
[java] at
org.apache.commons.collections.buffer.BoundedFifoBuffer$1.remove(BoundedFifo
Buffer.java:347)
[java] at
java.util.AbstractCollection.remove(AbstractCollection.java:255)
[java] at
org.apache.commons.collections.collection.AbstractCollectionDecorator.remove
(AbstractCollectionDecorator.java:103)
[java] at RecentlyVisited.add(RecentlyVisited.java:53)
[java] at RecentlyVisited.main(RecentlyVisited.java:39)
It's coming from the third instance of
add( recentVisited, Page 1 );
in the example code.
I put together a simple example that demonstrates the problem:
http://wiki.wendysmoak.com/cgi-bin/wiki.pl?CircularFifoBuffer
Bug? Surely I'm not doing anything wrong by calling remove(...) on a
Collection? (Inefficient though it may be, first I just want to see it
work.)
Meanwhile, is there another way I can get the buffer to be in the correct
LRU order? The LRUMap did work, but it's ugly having to put the empty
String into the Map, when I don't need key/value pairs.
Thanks,
--
Wendy Smoak
-
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
Re: [collections] Name that data structure
From: Tim O'Brien [EMAIL PROTECTED] Or you could do something that takes more work, but I think it more fun: A belated thank you for the suggestions... I haven't gotten back around to working on this requirement yet, but I'm sure one or more of the things in this thread will help tremendously. -- Wendy Smoak - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [collections] Name that data structure
Wendy, you could most certainly use a LRUMap with a fixed size. Give
each item a unique key and let the Map take care of uniqueness. LRUMap
will take care of discarding the least recently used entry once it
reached the maximum defined size, and the Iterator returns most recently
used to least recently used. This would be the easiest way to do this,
by far.
Or you could do something that takes more work, but I think it more fun:
Define a Predicate:
import java.util.Collection;
mport org.apache.commons.collections.Predicate;
public class UniqueInCollection implements Predicate {
private Collection collection;
public UniqueInCollection(Collection collection) {
this.collection = collection;
}
public boolean evaluate(Object o) {
return !collection.contains( o );
}
}
Then use a CircularFifoBuffer married to the Predicate. Only downside
is that you have to catch IllegalArgumentException throw by
PredicatedBuffer:
import java.util.Iterator;
import org.apache.commons.collections.Buffer;
import org.apache.commons.collections.Predicate;
import org.apache.commons.collections.buffer.CircularFifoBuffer;
import org.apache.commons.collections.buffer.PredicatedBuffer;
public class RecentlyVisited {
public static void main(String[] args) {
Buffer buffer = new CircularFifoBuffer(5);
Predicate unique = new UniqueInCollection(buffer);
Buffer recentVisited = PredicatedBuffer.decorate(buffer, unique);
add( recentVisited, Page 1 );
add( recentVisited, Page 2 );
add( recentVisited, Page 3 );
add( recentVisited, Page 4 );
add( recentVisited, Page 1 );
add( recentVisited, Page 2 );
add( recentVisited, Page 1 );
add( recentVisited, Page 21 );
add( recentVisited, Page 22 );
add( recentVisited, Page 1 );
Iterator i = buffer.iterator();
while( i.hasNext() ) {
String value = (String) i.next();
System.out.println( value );
}
}
public static void add(Buffer recentVisited, String page) {
try {
recentVisited.add( page );
} catch( IllegalArgumentException iae ) {
// do nothing, buffer will complain if predicate fails.
}
}
}
Mattias Jiderhamn wrote:
Possibly it could also be a MRU (Most Recently Used) cache.
At 2005-07-03 23:39, you wrote:
I'd say you were looking for an ordinary priority queue, where the
priority=the timestamp. Try the Heap class.
Sincerely,
Silas Snider
On 7/3/05, Wendy Smoak [EMAIL PROTECTED] wrote:
I'm looking through the Collections API, but not finding exactly
what I
want... hoping someone who's more familiar with it can point me in
the right
direction.
What I'm trying to do is more or less what you see on catalog sites
where
they'll list the most recent items you've looked at, newest on
top. So it's
ordered (List), but has no duplicates (Set), and I need to have a
max size.
ListOrderedSet is almost there, except that it retains the 'old'
position if
you add the same item again. (And has no max length.)
So... before I either write it myself or extend ListOrderedSet to
make it do
what I want, does anyone have another suggestion? And what would
_you_ call
it?
Thanks,
Wendy Smoak
-
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
-
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
Re: [collections] Name that data structure
Tim O'Brien wrote:
Wendy, you could most certainly use a LRUMap with a fixed size. Give
each item a unique key and let the Map take care of uniqueness.
LRUMap will take care of discarding the least recently used entry once
it reached the maximum defined size, and the Iterator returns most
recently used to least recently used. This would be the easiest way
to do this, by far.
Sorry, hit send too quickly, so that code compared to the LRUMap solution:
Map map = new LRUMap(5);
map.put( Page 1, );
map.put( Page 2, );
map.put( Page 3, );
map.put( Page 4, );
map.put( Page 5, );
map.put( Page 6, );
map.put( Page 7, );
map.put( Page 8, );
map.put( Page 9, );
map.put( Page 1, );
Iterator i = map.keySet().iterator();
while (i.hasNext()) {
String value = (String) i.next();
System.out.println(value);
}
-
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
Re: [collections] Name that data structure
Possibly it could also be a MRU (Most Recently Used) cache. At 2005-07-03 23:39, you wrote: I'd say you were looking for an ordinary priority queue, where the priority=the timestamp. Try the Heap class. Sincerely, Silas Snider On 7/3/05, Wendy Smoak [EMAIL PROTECTED] wrote: I'm looking through the Collections API, but not finding exactly what I want... hoping someone who's more familiar with it can point me in the right direction. What I'm trying to do is more or less what you see on catalog sites where they'll list the most recent items you've looked at, newest on top. So it's ordered (List), but has no duplicates (Set), and I need to have a max size. ListOrderedSet is almost there, except that it retains the 'old' position if you add the same item again. (And has no max length.) So... before I either write it myself or extend ListOrderedSet to make it do what I want, does anyone have another suggestion? And what would _you_ call it? Thanks, Wendy Smoak - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: [collections] Name that data structure
Hmmm
* Ordered
* No duplicates
* Max Size
icky
Buffer boundedBuffer = new BoundedFifoBuffer(10);
Predicate uniqueness = new UniquePredicate();
Buffer buffer = new PredicatedBuffer( boundedBuffer, uniqueness );
/icky
Then you can iterate over the content's of the Buffer. But, that might
not work exactly as you want it because the Bounded FIFO buffer will
discard things, but the UniquePredicate won't allow duplicates into the
List. You could write your own Predicate that looks at the contents of
the Buffer on each add(), only succesfully adding if
So,
public class UniqueInCollection implements Predicate {
private Collection collection;
public UniqueInCollection(Collection collection) {
this.collection = collection;
}
public void evaluate(Object o) {
return !collection.contains( o );
}
}
Buffer boundedBuffer = new BoundedFifoBuffer( 10 );
Predicate uniqueness = new UniqueInCollection( boundedBuffer );
Buffer buffer = new PredicatedBuffer( boundedBuffer, uniqueness );
// add stuff to it, buffer will take care of discarding stuff automagically
Then to iterate, do what you would normally do, buffer.iterator();
Wendy Smoak wrote:
I'm looking through the Collections API, but not finding exactly what
I want... hoping someone who's more familiar with it can point me in
the right direction.
What I'm trying to do is more or less what you see on catalog sites
where they'll list the most recent items you've looked at, newest on
top. So it's ordered (List), but has no duplicates (Set), and I need
to have a max size.
ListOrderedSet is almost there, except that it retains the 'old'
position if you add the same item again. (And has no max length.)
So... before I either write it myself or extend ListOrderedSet to make
it do what I want, does anyone have another suggestion? And what
would _you_ call it?
Thanks,
Wendy Smoak
-
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
-
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
Re: [collections] Name that data structure
I'd say you were looking for an ordinary priority queue, where the priority=the timestamp. Try the Heap class. Sincerely, Silas Snider On 7/3/05, Wendy Smoak [EMAIL PROTECTED] wrote: I'm looking through the Collections API, but not finding exactly what I want... hoping someone who's more familiar with it can point me in the right direction. What I'm trying to do is more or less what you see on catalog sites where they'll list the most recent items you've looked at, newest on top. So it's ordered (List), but has no duplicates (Set), and I need to have a max size. ListOrderedSet is almost there, except that it retains the 'old' position if you add the same item again. (And has no max length.) So... before I either write it myself or extend ListOrderedSet to make it do what I want, does anyone have another suggestion? And what would _you_ call it? Thanks, Wendy Smoak - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] -- -- Silas Snider is a proud member of the Association of Wikipedians Who Dislike Making Broad Judgements About the Worthiness of a General Category of Article, and Who Are In Favor of the Deletion of Some Particularly Bad Articles, but That Doesn't Mean They are Deletionist (AWWDMBJAWGCAWAIFDSPBATDMTD) , and the Harmonious Editing Club of Wikipedia. -- - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
