[collections] Name that data structure

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

[collections] Name that data structure

Wendy Smoak-4
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: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [collections] Name that data structure

Silas Snider
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 <[hidden email]> 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: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>


--
--------------------------------------------------------------------------      
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: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [collections] Name that data structure

Mattias Jiderhamn
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 <[hidden email]> 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: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [collections] Name that data structure

tobrien
In reply to this post by Wendy Smoak-4
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: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>
>
>




---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [collections] Name that data structure

tobrien
In reply to this post by Mattias Jiderhamn
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 <[hidden email]> 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: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>
>
>




---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [collections] Name that data structure

tobrien
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: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [collections] Name that data structure

Wendy Smoak-4
In reply to this post by tobrien
From: "Tim O'Brien" <[hidden email]>
>
> 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: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [collections] Name that data structure

Wendy Smoak-4
In reply to this post by tobrien
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: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [collections] Name that data structure

Stephen Colebourne
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: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [collections] Name that data structure

Wendy Smoak-4
From: "Stephen Colebourne" <[hidden email]>

> 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: [hidden email]
For additional commands, e-mail: [hidden email]