RE: [Collections] Naming conventions

[Jack, Paul]

> we could even make them public classes and allow users to 
> extend them on 
> their own (using the XXXUtils.whatever methods as convenience methods)

Well, yes...but we'd be adding like 30 classes to the public API.
Maybe have a separate package for decorators?


> FactoryUtils could still be used.  Then, if later we add 
> another type of 
> factory (I have *no* idea what though), we can keep all the factory 
> methods in FactoryUtils.  
> 
> And actually, we could rename SimpleObjectFactory to just 
> plain Factory.  

I'm all for that.  

-Paul


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections] Naming conventions

[Jack, Paul]

> I personally like the Lists, Sets, Collections, etc naming,
> too.  We could put pass-through methods to
> java.util.Collections on the commons.Collections class. 
> That way we can have our cake and eat it too.  

I definitely agree that code like this is nicer:

  Bag bag = Bags.synchronizedBag(Bags.predicatedBag(new HashBag(), pred));

...I mean, how cool is it that all that actually fits on one line?

However, I don't think your idea of using pass-through methods 
can work.  The Collections project is committed to remaining 
JDK1.2 compatible, and methods have been added to java.util.Collections
in JDK1.3, 1.4.  

I'd love it if we could just subclass java.util.Collections,
inheriting all of its static methods and then supplying our own...
But alas, its constructor is private.

And anyway, since we already have the Utils convention, we're 
kind of stuck with it...

-Paul


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections] Naming conventions

[Jack, Paul]

> 2) Subclassing would be more complex. Currently each 
> Predicate decorator
> implementation extends another based on the interface 
> hierarchy. In order to
> continue this, the static nested classes would need to be 
> package scoped,
> not private. Not a big issue, but it should be noted.

I'm even okay with the wrapper classes being package-protected
OUTER classes defined in the same source file.  Having 
package-protected classes still gives us a lot of leeway with
organizing things, as technically users shouldn't be using 
package-protected methods and classes.


> After a little thought, I think I favour adding Utils to all 
> of the above.
> Results in no clashes with Java, and just involves adding methods to
> ListUtils, CollectionUtils and MapUtils.

One other consideration is that ListUtils is deprecated.  We 
could always un-deprecate it, of course.  I'd want to manually
deprecate each method currently in the class though, but that
doesn't seem like a big deal.

But otherwise, I think having:

   BagUtils
   CollectionUtils
   ComparatorUtils
   IteratorUtils
   ListUtils
   MapUtils
   PredicateUtils
   SetUtils
   TransformerUtils
   TreeUtils

is all good.  I'd like FactoryUtils to be SimpleObjectFactoryUtils,
which is a very long name but more consistent with the others.


> On method names, I agree with your implicit use of   yyyedXxx, eg.
> filteredMap or predicatedSet

This is all sounding dangerously close to consensus!  I think this
is probably the only civilized conversation on naming conventions
I've ever had... :)


> BTW: I thought of two more decorator groups - Transform 
> (already discussed a
> little while back) and FixedSize (doesn't allow the size to 
> change). And I
> like the Comparator to Predicate idea.

A while back I suggested:
 
  public static Set setBackedByMap(Map map);
  public static SortedSet sortedSetBackByMap(SortedMap map);

which would let people use things like LRUMap as a set.

Composition patterns galore...

-Paul



--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections] Naming conventions

[Jack, Paul]

Here's an idea.  We can make the source more manageable
and effectively limit the number of public classes by
breaking my One Decorator Class To Rule Them All into
smaller ones based on subinterface:

   Bags (for SortedBags too)
 predicatedBag
 predicatedSortedBag
 synchronizedBag
 synchronizedSortedBag
 unmodifiableBag
 unmodifiableSortedBag
 eventBag
 eventSortedBag
 filterBag 
 filterSortedBag
   Lists
 predicatedList
 eventList
 filterList
   Maps (for SortedMaps and MultiMaps too)
   Sets

It avoids the naming collision, keeps the source in 
distinct places, and prevents us from having another
public class every time somebody comes up with 
another great decorator idea...

Though I guess we would need another public class
every time somebody comes up with another great 
Collection subinterface.  But that doesn't seem like
it would happen as often as new decorators (we already
have 5 new decorator ideas on the table, no 
outstanding Collection subinterfaces...)

Also, the more I think about it, it seems that organizing
the source code according to return type makes a lot of
sense, as a rule of thumb.  For instance, where do we put
this method?

  // Returns a predicate that returns true for objects
  // that are greater than o, according to the sort 
  // order specified by c.
  public Predicate greaterThan(Object o, Comparator c);

It uses a comparator, but produces a predicate.  Does it
go in Comparators or Predicates?  With the 
organize-by-return-type approach, it's obvious that we 
put it in PredicateUtils; and it's hopefully obvious to
a user of the library where to find such a beast.

-Paul

> -Original Message-
> From: Stephen Colebourne [mailto:[EMAIL PROTECTED]]
> Sent: Wednesday, June 12, 2002 2:18 PM
> To: Jakarta Commons Developers List
> Subject: Re: [Collections] Naming conventions [was 
> ComparableComparator
> - nulls OK]
> 
> 
> Good argument, and logical. However the 'Collections' class 
> could have 6 or
> more groups of decorators if the dreams become reality. Maybe 
> this isn't a
> problem, but I wouldn't want that class to contain all the 
> static nested
> classes (for maintainability)
> 
> There is another factor - the classes don't just contain decorators.
> FactoryUtils/PredicateUtils (current names) create 
> Factory/Predicate objects
> not decorate them.
> 
> Some possibilities:
> - CollectionUtils
> ie. add to existing class, probably should merge in ListUtils 
> too - this
> seems quite a big change. And MapUtils doesn't fit well (its rather a
> strange group of methods)
> 
> - Decorators
> - CollectionDecorators
> - DecoratedCollections
> - DecoratorUtils
> these emphasise the role of the resultant classes, but how is 
> the source
> laid out
> 
> - SynchronizedCollections, PredicatedCollections, ... as I originally
> proposed
> these emphasise the particular decorator, and fit well with 
> managable source
> units
> 
> 
> Deciding where the source will go is another factor in this. 
> Nice can of
> worms!
> 
> Stephen

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections] Naming conventions [was ComparableComparator - nulls OK]

[Jack, Paul]

 all of its wrappers in one monolithic class;
> > > what do people think of having just one giant
> > > WrapperUtils?
> >
> > I would encourage the use of the term "Decorator" instead
> > of "Wrapper".  The more concise we can be with language,
> > the better IMHO (Assuming everything that util class would
> > only add decorators. If it starts also doing Adapters and
> > such then a less concise term like wrapper is better).  :-)
> >
> > Jonathan
> >
> >
> > --- "Jack, Paul" <[EMAIL PROTECTED]> wrote:
> > > Actually, that's a good point.  There are some other
> > > considerations behind the long convention...
> > >
> > > Technically it's possible for a collection to implement
> > > both Set and Bag (getCount() would always return 1 or 0;
> > > uniqueSet would return an unmodifiable view of itself)...
> > >
> > > I'm not saying such an implementation would be useful;
> > > but it is legal.  If such a SetBag existed, then these
> > > methods become ambiguous:
> > >
> > > Set predicate(Set, Predicate)
> > > Bag predicate(Bag, Predicate)
> > >
> > > Which method does the compiler pick when I invoke
> > > PredicateUtils.predicate(new SetBag(), pred)?
> > >
> > > You can force one method or the other using an explicit
> > > cast, but it seems cleaner to have altogether distinct
> > > method signatures.
> > >
> > > Not really much of a consideration given our current
> > > API -- like I said, SetBag would be pretty pointless --
> > > but it's conceivable that there may be future Collection
> > > interfaces that can be implemented simultaneously.
> > >
> > > Also, if we wanted to be completely strict, then we'd
> > > use "predicatedSet" instead of "predicateSet" -- the
> > > JDK wrappers are all specified with an adjective.
> > >
> > > Also, in another thread, somebody raised the issue of
> > > providing unmodifiable wrappers for Bag, SortedBag,
> > > Iterator and ListIterator.  And MultiMap.  I'd also like
> > > to see synchronized wrappers for Bag, SortedBag,
> > > MultiMap.
> > > We already have predicate wrappers and lazy wrappers;
> > > the JDK puts all of its wrappers in one monolithic class;
> > > what do people think of having just one giant
> > > WrapperUtils?
> > > It could contain all the predicate, lazy, future
> > > unmodifiable and synchronized wrappers.  (I think it
> > > would
> > > still make sense to organize the source into multiple
> > > files; but the public API would be just one class).
> > >
> > > -Paul
> > >
> > >
> > >
> > > > -Original Message-
> > > > From: Michal Plechawski
> > > [mailto:[EMAIL PROTECTED]]
> > > > Sent: Tuesday, June 11, 2002 5:18 AM
> > > > To: Jakarta Commons Developers List; Stephen Colebourne
> > > > Subject: Re: [Collections] ComparableComparator - nulls
> > > OK
> > > >
> > > >
> > > > Hello,
> > > >
> > > > > > What do you think of
> > > > > > Set predicate(Set set, Predicate predicate)
> > > > > > ?  Is that too nondescript?
> > > > >
> > > > > Actually, there is another factor involved. The
> > > > java.utils.Collections class
> > > > > uses the long form, eg.
> > > > > Collections.unmodifiableMap(Map);
> > > > >
> > > > > Thus I would prefer the long form. We could agree to
> > > differ
> > > > from Sun
> > > > > however, in which case I would submit a patch to the
> > > Predicate
> > > > code.
> > > >
> > > > IMHO Sun has just one argument for leaving the
> > > "Map"-like suffix.
> > > > It gives a possiblity of all the following to coexist:
> > > >
> > > >   List unmodifiableList(List l)
> > > >   Set unmodifiableSet(Set s)
> > > >   Set unmodifiableSet(List l)
> > > >
> > > > However, I do not see this as a strong argument. But
> > > mimicring
> > > > the Sun's conventions should be a good idea.
> > > >
> > > > Michal
> > > >
> > > >
> > > > --
> > > > To unsubscribe, e-mail:
> > > > <mailto:[EMAIL PROTECTED]>
> > > > For additional commands, e-mail:
> > > > <mailto:[EMAIL PROTECTED]>
> > > >
> > >
> > > --
> > > To unsubscribe, e-mail:
> > > <mailto:[EMAIL PROTECTED]>
> > > For additional commands, e-mail:
> > > <mailto:[EMAIL PROTECTED]>
> > >
> >
> >
> > =
> > Jonathan Carlson
> > [EMAIL PROTECTED]
> > Minneapolis, Minnesota
> >
> > __
> > Do You Yahoo!?
> > Yahoo! - Official partner of 2002 FIFA World Cup
> > http://fifaworldcup.yahoo.com
> >
> > --
> > To unsubscribe, e-mail:
> <mailto:[EMAIL PROTECTED]>
> > For additional commands, e-mail:
> <mailto:[EMAIL PROTECTED]>
> >
> >
> 
> 
> --
> To unsubscribe, e-mail:   
<mailto:[EMAIL PROTECTED]>
For additional commands, e-mail:
<mailto:[EMAIL PROTECTED]>

--
To unsubscribe, e-mail:   <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>

RE: [PATCH][Collections] New testing framework, junit compatible

[Jack, Paul]

> I hate ask you to do more work, 

Here to help.  :)


> but can you separate the changes to the Bag implementations from 
> the improvements to the testing framework?

Well, not really.  The problem is that the old Bag implementations
will fail many of the new tests in TestCollection, because those
tests now strictly enforce the Collection contract.  To make the
old Bag implementations work with the new test framework, we'd
have to override a lot of TestCollection methods in TestBag.

In the meantime, you can do this:

A.  Apply the patch;
B.  Blow away TestBag.java;
C.  cvs update TestBag.java;
D.  Make TestBag extend TestObject instead of TestCollection.

That way my new tests won't occur on Bag implementations.

-Paul


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: Collections

[Jack, Paul]

> Filtering collections, that guarantees that only objects that 
> matches an ObjectFilter (sorry, I mean Predicate) are added?

Check the latest code in CVS; there's already a PredicateUtils
that does this.  (But it is a great idea!)


> TypeFilter(Predicate), that only evaluates to true if the 
> object is of a certain type.

PredicateUtils has this too.

 
> (Consequently) Typed collections, that guarantees that only 
> objects of a certain type is stored?

Yup.


> ReadAheadIterator - you know what I mean

Um, it completes and stores the whole iteration sequence when
it's constructed?


> Mixing Iterator - that mixes two or more Iterators either by 
> joining them or shuffling them

There's already an IteratorChain.
 

> Converting iterators (or is it Transformers to you?)

There's already a TransformIterator.


> Listenable collections that throws update events to listeners.

Nifty!

 
> ObjectStream (an iterator with a different contract, no more 
> objects means null, which means that you don\'t have to 
> evaluate until it is needed)

Um, I don't get it.  Could you give an example?
 

-Paul

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections] ComparableComparator - nulls OK

[Jack, Paul]

Actually, that's a good point.  There are some other
considerations behind the long convention...

Technically it's possible for a collection to implement
both Set and Bag (getCount() would always return 1 or 0;
uniqueSet would return an unmodifiable view of itself)...

I'm not saying such an implementation would be useful;
but it is legal.  If such a SetBag existed, then these
methods become ambiguous:

Set predicate(Set, Predicate)
Bag predicate(Bag, Predicate)

Which method does the compiler pick when I invoke
PredicateUtils.predicate(new SetBag(), pred)?

You can force one method or the other using an explicit
cast, but it seems cleaner to have altogether distinct
method signatures.

Not really much of a consideration given our current
API -- like I said, SetBag would be pretty pointless --
but it's conceivable that there may be future Collection
interfaces that can be implemented simultaneously.

Also, if we wanted to be completely strict, then we'd
use "predicatedSet" instead of "predicateSet" -- the
JDK wrappers are all specified with an adjective.

Also, in another thread, somebody raised the issue of
providing unmodifiable wrappers for Bag, SortedBag,
Iterator and ListIterator.  And MultiMap.  I'd also like
to see synchronized wrappers for Bag, SortedBag, MultiMap.
We already have predicate wrappers and lazy wrappers;
the JDK puts all of its wrappers in one monolithic class;
what do people think of having just one giant WrapperUtils?
It could contain all the predicate, lazy, future 
unmodifiable and synchronized wrappers.  (I think it would
still make sense to organize the source into multiple 
files; but the public API would be just one class).

-Paul



> -Original Message-
> From: Michal Plechawski [mailto:[EMAIL PROTECTED]]
> Sent: Tuesday, June 11, 2002 5:18 AM
> To: Jakarta Commons Developers List; Stephen Colebourne
> Subject: Re: [Collections] ComparableComparator - nulls OK
> 
> 
> Hello,
> 
> > > What do you think of
> > > Set predicate(Set set, Predicate predicate)
> > > ?  Is that too nondescript?
> >
> > Actually, there is another factor involved. The
> java.utils.Collections class
> > uses the long form, eg.
> > Collections.unmodifiableMap(Map);
> >
> > Thus I would prefer the long form. We could agree to differ
> from Sun
> > however, in which case I would submit a patch to the Predicate
> code.
> 
> IMHO Sun has just one argument for leaving the "Map"-like suffix.
> It gives a possiblity of all the following to coexist:
> 
>   List unmodifiableList(List l)
>   Set unmodifiableSet(Set s)
>   Set unmodifiableSet(List l)
> 
> However, I do not see this as a strong argument. But mimicring
> the Sun's conventions should be a good idea.
> 
> Michal
> 
> 
> --
> To unsubscribe, e-mail:   
> 
> For additional commands, e-mail: 
> 
> 

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

[PATCH][Collections] New testing framework, junit compatible

[Jack, Paul]

http://www.geocities.com/apachecollections/june10

Rewrote BulkTest so that it extends TestCase.  It now provides
a static makeSuite(Class) method that can be used to create a
TestSuite that's displayed as a hierarchy in the swingui.  The
other code's all the same, except less files needed to be 
tweaked -- classes that don't use bulk test methods don't need
special suite() methods anymore.

Probably should have done it this way to begin with...

-Paul



--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections] ComparableComparator - nulls OK

[Jack, Paul]

> I too like the ComparatorUtils concept outlined below. 
> However, we might
> want to consider whether the method names are nullFirst(Comparator) or
> nullFirstComparator(Comparator) etc. I raise this because 
> PredicateUtils
> uses the latter at the moment, and it would be nice to be 
> consistent (we
> could change PredicateUtils if required).

Hm.  I always favor shorter names, especially when the longer
names are redundant...the ComparatorUtils I submitted uses the
shorter names...

What do you think of 

Set predicate(Set set, Predicate predicate)

?  Is that too nondescript?

-Paul

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

[SUBMIT][Collections] ComparatorUtils

[Jack, Paul]

ComparatorUtils.java
Description: Binary data

RE: [COLLECTIONS/BEANUTILS] Is there a comparator that can dynamically pick a method to call on a bean?

[Jack, Paul]

Why not use a TransformingComparator to transform the objects
into strings before passing them to CASE_INSENSITIVE_ORDER?

I really am just trying to help. :)

-Paul

> -Original Message-
> From: Eric Pugh [mailto:[EMAIL PROTECTED]]
> Sent: Monday, June 10, 2002 2:07 PM
> To: 'Jakarta Commons Developers List'
> Subject: RE: [COLLECTIONS/BEANUTILS] Is there a comparator that can
> dynamically pick a method to call on a bean?
> 
> 
> Now I figured out why I have the Lowercase comparator..  I am 
> using the
> lowercase comparator decorated by BeanCompartor, which 
> sometiems passes
> strings to lowercase comparator and other times passes other 
> objects...
> CASE_INSENSITIVE_ORDER throws classcastexceptions on anything 
> that is not a
> string..
> 
> So, how about changing LowercaseComparator to 
> CaseInsensitiveComparator
> which wraps a call to CASE_INSENSITIVE_ORDER when both args 
> are Strings, and
> otherwise doesn't?  The problem is still that you can't daisy 
> chain any
> furthur..  Maybe only use CaseInsensitiveComparator when the 
> user doesn't
> pass in another comparator, other do the toLowerCase call...
> 
> ERic
> 
> -Original Message-
> From: Jack, Paul [mailto:[EMAIL PROTECTED]]
> Sent: Monday, June 10, 2002 4:45 PM
> To: 'Jakarta Commons Developers List'
> Subject: RE: [COLLECTIONS/BEANUTILS] Is there a comparator that can
> dynamically pick a method to call on a bean?
> 
> 
> FYI, java.lang.String.CASE_INSENSITIVE_ORDER does what your
> LowercaseComparator does, but somewhat more efficiently.
> 
> -Paul
> 
> 
> > -Original Message-
> > From: Eric Pugh [mailto:[EMAIL PROTECTED]]
> > Sent: Monday, June 10, 2002 1:35 PM
> > To: 'Jakarta Commons Developers List'
> > Subject: RE: [COLLECTIONS/BEANUTILS] Is there a comparator that can
> > dynamically pick a method to call on a bean?
> >
> >
> > Hi all,
> >
> > Attached is my first attempt at submitting a BeanComparator,
> > along with the
> > test case..  However, i am running into two issues becomes of
> > my lack of
> > familiarty with beans that are causing me pain.  However, in my app,
> > everything is working great!  My testcase is attached.
> >
> > 1) the test suite fails because my test object which has a
> > getBeanValue and
> > setBeanValue causes the WrapDynaBean class to throw an 
> exception that
> > "value" has no read method..  Yet it does, and in other uses of the
> > BeanComparator in my code it works great.
> >
> > 2) All comparisions are string comparisons..  So when I
> > compare Bigdecimals
> > 2, 12, and 22, the orders is 12, 2, 22!  Do I need to hand in
> > another class
> > to cast the objects to?
> >
> > Also, I would love to see the ComparatorUtils, I created my 
> own one to
> > handle the reversing of my sorts based on the text values
> > ASC/DESC, and
> > removed them from my BeanComparator.
> >
> > I have also attached my LowercaseComparator..  I was sorting
> > columns of
> > String data, and noticed that if I didn't lowercase them, the
> > A versus a
> > differenced caused funny looking ordering.  I also set up
> > LowercaseComparator and BeanComparator to work as decorators
> > (similar to
> > ReverseComparator).  Lastly, for the bean comparator, I am using
> > PropertyUtils, so if you can pass in NESTED properties!  
> customer.name
> > results in getCustomer().getName() being returned!  I would
> > love to add
> > jxPath converter as I build up some more experience!
> >
> > Here is some sample code:
> >
> > public static Comparator sortedBean( String sortProperty, String
> > sortPolarity )
> > throws java.lang.IllegalArgumentException {
> > Comparator c = null;
> > sortPolarity = sortPolarity.toUpperCase();
> > if ( !sortPolarity.equals( ASC ) &&
> > !sortPolarity.equals( DESC ) ) {
> > throw new
> > java.lang.IllegalArgumentException( "The argument:" +
> > sortPolarity + " was invalid." );
> > }
> > if ( sortPolarity.equals( ASC ) ) {
> > c = new BeanComparator( sortProperty,
> > new LowercaseComparator() );
> > }
> > else {
> > c = new ReverseComparator( new
> > BeanComparator( sortProperty, new
> > LowercaseComparator() ) );
> >
> > }
> > 

RE: [COLLECTIONS/BEANUTILS] Is there a comparator that can dynamically pick a method to call on a bean?

[Jack, Paul]

FYI, java.lang.String.CASE_INSENSITIVE_ORDER does what your 
LowercaseComparator does, but somewhat more efficiently.

-Paul


> -Original Message-
> From: Eric Pugh [mailto:[EMAIL PROTECTED]]
> Sent: Monday, June 10, 2002 1:35 PM
> To: 'Jakarta Commons Developers List'
> Subject: RE: [COLLECTIONS/BEANUTILS] Is there a comparator that can
> dynamically pick a method to call on a bean?
> 
> 
> Hi all,
> 
> Attached is my first attempt at submitting a BeanComparator, 
> along with the
> test case..  However, i am running into two issues becomes of 
> my lack of
> familiarty with beans that are causing me pain.  However, in my app,
> everything is working great!  My testcase is attached.
> 
> 1) the test suite fails because my test object which has a 
> getBeanValue and
> setBeanValue causes the WrapDynaBean class to throw an exception that
> "value" has no read method..  Yet it does, and in other uses of the
> BeanComparator in my code it works great.
> 
> 2) All comparisions are string comparisons..  So when I 
> compare Bigdecimals
> 2, 12, and 22, the orders is 12, 2, 22!  Do I need to hand in 
> another class
> to cast the objects to?
> 
> Also, I would love to see the ComparatorUtils, I created my own one to
> handle the reversing of my sorts based on the text values 
> ASC/DESC, and
> removed them from my BeanComparator.
> 
> I have also attached my LowercaseComparator..  I was sorting 
> columns of
> String data, and noticed that if I didn't lowercase them, the 
> A versus a
> differenced caused funny looking ordering.  I also set up
> LowercaseComparator and BeanComparator to work as decorators 
> (similar to
> ReverseComparator).  Lastly, for the bean comparator, I am using
> PropertyUtils, so if you can pass in NESTED properties!  customer.name
> results in getCustomer().getName() being returned!  I would 
> love to add
> jxPath converter as I build up some more experience!
> 
> Here is some sample code:
> 
>   public static Comparator sortedBean( String sortProperty, String
> sortPolarity )
>   throws java.lang.IllegalArgumentException {
>   Comparator c = null;
>   sortPolarity = sortPolarity.toUpperCase();
>   if ( !sortPolarity.equals( ASC ) && 
> !sortPolarity.equals( DESC ) ) {
>   throw new 
> java.lang.IllegalArgumentException( "The argument:" +
> sortPolarity + " was invalid." );
>   }
>   if ( sortPolarity.equals( ASC ) ) {
>   c = new BeanComparator( sortProperty, 
> new LowercaseComparator() );
>   }
>   else {
>   c = new ReverseComparator( new 
> BeanComparator( sortProperty, new
> LowercaseComparator() ) );
> 
>   }
>   return c;
>   }
> 
> 
> Any suggestions/help would be much appreciated, and I would 
> love to see
> these added to the comparators available!
> 
> Eric
> 
> -Original Message-
> From: Michael A. Smith [mailto:[EMAIL PROTECTED]]
> Sent: Friday, June 07, 2002 3:07 PM
> To: Jakarta Commons Developers List
> Subject: RE: [COLLECTIONS/BEANUTILS] Is there a comparator that can
> dynamically pick a method to call on a bean?
> 
> 
> On Fri, 7 Jun 2002, Henri Yandell wrote:
> > Sorry Eric, I'm not sure you got my question.
> >
> > BeanComparator = good, +1. I think it'd be great to commit a
> > BeanComparator.
> >
> > The ASC/DESC bit is unnecessary I think due to 
> ReverseComparator. This is
> > an opinion though, I don't believe in ASC/DESC in 
> Comparators. So I was
> > just -1 on the Polarity part of your BeanComparator :)
> >
> > Morgan or Michael may want to veto that though :)
> 
> Neither of us can veto your veto.  We can try to twist your 
> arm, but in
> this case, I have no reason to: I agree with you.  The reverse
> comparator can provide the complementary ascending or descending
> behavior.
> 
> regards,
> michael
> 
> 
> --
> To unsubscribe, e-mail:
> 
> For additional commands, e-mail:
> 
> 

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections] ReadOnly Collection decorators

[Jack, Paul]

Um, the JDK already provides what you're looking for:

java.util.Collections.unmodifiableSet(Set set)
Collections.unmodifiableList(List list)
Collections.unmodifiableMap(Map map)

and so on.  We should probably provide similar things for
Bag, SortedBag and MultiMap though.

-Paul


> -Original Message-
> From: Jonathan Carlson [mailto:[EMAIL PROTECTED]]
> Sent: Monday, June 10, 2002 11:53 AM
> To: [EMAIL PROTECTED]
> Subject: [Collections] ReadOnly Collection decorators
> 
> 
> I'd really like to see some ReadOnly Collection decorators
> for all of the Collection and Iterator interfaces and
> subinterfaces.  
> 
> When I return a collection or iterator from a framework I
> don't want to trust that no one will modify those
> collections if they represent something internal.  Using
> these have protected me from even my own carelessness at
> least once.
> 
> I have written a few already that I could share (Set, List,
> Map, Iterator etc) but they don't subclass the commons
> collections Proxy* classes (see my previous note on the
> naming of these), which they probably should do if they are
> to be included.
> 
> Thoughts anyone?
> 
> Jonathan
> 
> =
> Jonathan Carlson
> [EMAIL PROTECTED]
> Minneapolis, Minnesota
> 
> __
> Do You Yahoo!?
> Yahoo! - Official partner of 2002 FIFA World Cup
> http://fifaworldcup.yahoo.com
> 
> --
> To unsubscribe, e-mail:   

For additional commands, e-mail:


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [PATCH][Collections] New testing framework, patch #1

[Jack, Paul]

> You've put a lot of work into getting these tests up and 
> running, and it
> has exposed some problems with existing implementations, so your work
> isn't without merit.  In fact, I'm inclined to commit it, I would just
> rather see something that utilizes JUnit's TestSuite (by subclass
> probably since it doesn't support "bulkTest") so that a proper test
> hierarchy can be built.  Therefore, I'm going to hold off a 
> little bit 
> to see if any other collections committers care to comment on 
> the above.  

...actually, it shouldn't be too difficult to make BulkTest extend
TestSuite.  We'd still have the problem that people's suite() methods
would have to be different than usual...I'll see what I can do.

-Paul

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

[PATCH][Collections] New collections testing framework, attempt #3

[Jack, Paul]

Okay, this is a cumulative patch; it includes the previous two.

The point of this patch is that TestMap is now hardcore.  It
fully tests its collection views, by running through the tests
defined in TestSet and TestCollection on keySet(), entrySet()
and values().  

It also fully tests that collection views are backed by the map
and vice versa.  Every time a map test method AND every time a
collection view test method modifies the map, the map AND all 
of its collection views are verified to make sure they reflect
the new state of the map.

I decided to use a website to keep track of everything:

http://www.geocities.com/apachecollections

The above link includes the source for new files; a patch file;
and javadoc for the biggest changes.

The next patch will make TestList hardcore.  

-Paul



--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections] ComparableComparator - nulls OK

[Jack, Paul]

I like the idea of having the functionality provided by 
NullFirstComparator and NullLastComparator, but I have an
additional suggestion.

Currently, all of the classes in the comparators subpackage
are simple, and very useful.  However, it seems that they'd
most often be used in conjunction with each other; typically,
I'd use ReverseComparator with ComparableComparator to get
reverse natural ordering, and I'd probably use a NullSomething
comparator with ComparableComparator to get natural ordering
that accepts nulls.

So my suggestion is, can we fold these all into one static
utility API?  It would make them much more convenient, IMHO.
I'm thinking of something like:

public class ComparatorUtils {

// same as ComparableComparator.getInstance
public static Comparator NATURAL;

public static Comparator nullFirst(Comparator c);
public static Comparator nullLast(Comparator c);

// same as reverseComparator
public static Comparator reverse(Comparator c);

public static Comparator bean(Comparator c, String getterName);
public static Comparator transform(Comparator c, Transformer t);

}

Also, there are operations involving Comparators that I use 
frequently that would be nice to have in the API:

public static Object min(Object o1, Object o2, Comparator c);
public static Object max(Object o1, Object o2, Comparator c);

which would return the higher or lower of the given objects 
according to the comparator.

Any of this make sense?

-Paul



> -Original Message-
> From: Michael A. Smith [mailto:[EMAIL PROTECTED]]
> Sent: Friday, June 07, 2002 1:00 PM
> To: Jakarta Commons Developers List
> Subject: RE: [Collections] ComparableComparator - nulls OK
> 
> 
> On Fri, 7 Jun 2002, Eric Pugh wrote:
> > +1,  In my sorts, having to deal with nulls is causing me 
> difficulties as
> > well..  Although I could see something like any nulls being 
> ignored as a
> > type of behavior..  Sort everything, and drop the nulls!
> 
> consider:  Comparator.compare(null, "x");
> 
> how do you drop or ignore the null when doing this compare?
> 
> 
> > -Original Message-
> > From: Jonathan Carlson [mailto:[EMAIL PROTECTED]]
> > Sent: Friday, June 07, 2002 3:38 PM
> > To: [EMAIL PROTECTED]
> > Subject: [Collections] ComparableComparator - nulls OK
> > 
> > 
> > I'd like to make the case for a ComparableComparator that
> > allows the sorting of nulls to the bottom.  This could be a
> > flag to set on the existing class or another Comparator
> > called something like NullableComparableComparator (or
> > ComparableNullComparator?).
> 
> How about something like this:
> 
> public class NullFirstComparator implements Comparator {
>   private Comparator c;
>   public NullFirstComparator(Comparator nonNullComparator) {
> this.c = nonNullComparator;
>   }
>   public int compare(Object a, Object b) {
> if(a == b) return 0;
> if(a == null) return -1;
> if(b == null) return 1;
> return c.compare(a,b);
>   }
> }
> 
> and
> 
> public class NullLastComparator implements Comparator {
>   private Comparator c;
>   public NullLastComparator(Comparator nonNullComparator) {
> this.c = nonNullComparator;
>   }
>   public int compare(Object a, Object b) {
> if(a == b) return 0;
> if(a == null) return 1;
> if(b == null) return -1;
> return c.compare(a,b);
>   }
> }
> 
> 
> That allows you to adjust the behavior of comparison to null for any 
> comparator and not just the ComparableComparator.  It sounds like in 
> your case (sorting nulls last using ComparableComparator), you'd use:
> 
>new NullLastComparator(ComparableComparator.getInstance())
> 
> 
> If that sounds reasonable, I'll add a full implementation 
> (with a better 
> "Comparator.equals" method) to the list of things on my todo list. 
> 
> regards,
> michael
> 
> p.s.  I just threw together the above implementations. I 
> wouldn't trust
> it to actually sort things properly (or even compile) -- I may have
> things reversed or something where nulls go first instead of last and
> vice-versa.
> 
> 
> --
> To unsubscribe, e-mail:   
> 
> For additional commands, e-mail: 
> 
> 

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

[PATCH][Collections] SequencedHashMap collection view bugs

[Jack, Paul]

Bugs fixed:

1.  keySet().remove(Object) incorrectly returned false after
a successful removal of a null key.

2.  The removeAll(Collection) and retainAll(Collection) methods
of the collection views (keySet, entrySet and values) were not
updating the modCount; therefore an iterator over a collection
view would not raise a ConcurrentModificationException after
those operations.

-Paul





seq_hash_map.diff
Description: Binary data

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: cvs commit: jakarta-commons/collections/src/test/org/apache/commons/collections/primitives TestFloatArrayList.java TestAll.java

[Jack, Paul]

Hi, just so you know, I'm currently working on a 
TestList that your primitive collection TestCases
will be able to extend...

Might save you some work.

-Paul


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

[PATCH][Collections] Bug fix for Bug#9467

[Jack, Paul]

Altered the contract of Bag to conform to Collection.  Altered
the implementations in DefaultMapBag to conform to Collection.

-Paul





bug9467_patch.diff
Description: Binary data

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

[PATCH][Collections] New testing framework, patch #2

[Jack, Paul]

(This patch can be applied independently of patch #1).

Revamped TestCollection.  Most of the old tests relied on 
add() and addAll() to initially populate a collection.  This
won't work for map collection views because they don't support
the add() and addAll() operations.

I also made TestCollection operate more like TestMap; there
are methods that return empty and full collections, and 
separate methods that tell you what elements a full collection
should contain and what elements a full collection should
not contain.

The TestCollection tests are also more strict; they will detect
many more violations of the Collection contract than the old
tests.  As such, applying this patch will introduce 12 failures 
into the build.  All of the failures relate to Bug #9467 (Bag
violates Collection contract).  I'll submit a separate patch
for that bug shortly.

This patch contains:

1.  Massive alterations to TestCollection.java.
2.  Slight alterations to TestCursorableLinkedList, because it does
not support null values; and slight alterations to TestTreeBag,
because it requires mutually comparable elements.

The next patch will alter TestMap to use TestCollection bulk 
tests on its collection views.

-Paul





col_test_patch_2.diff
Description: Binary data

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

[PATCH][Collections] New testing framework, patch #1

[Jack, Paul]

Okay, so the goal was to be able to modularize the 
tests in such a way that objects that return a collection
or map could have those return values tested using
TestMap, TestCollection etc.

How I decided to handle that was to create a new
implementation of junit.framework.Test, that allows
you to specify "bulk test" methods in addition to
the usual simple test methods:

   public BulkTest bulkTestListSubList() {
   return new TestList() {
   public List makeFullList() {
   return outer.makeFullList().subList(2, 12);
   }

   public BulkTest bulkTestSubList() {
   return null; // avoid recursion
   }
   };
   }

The above example would be used to run through ALL of
the tests defined by TestList on its sublists...

A similar approach will be used for Maps and their
collection views.

This patch contains:

1.  The code for the new BulkTest class.
2.  Patch for TestObject to make it extend BulkTest
instead of TestCase.
3.  Patches for almost all of the classes, to replace
their suite() methods.  TestSuite knows nothing about
bulk test methods, so it can't be used.

After this patch, all existing tests still work.

Upcoming patches will have versions of TestList and
TestMap that utilize bulk test methods for their 
subcollections.

-Paul





BulkTest.java
Description: Binary data


col_test_patch_1.diff
Description: Binary data

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [collections] collections of primitives?

[Jack, Paul]

Looks good to me.  I like the separate package approach, and
"primitives" seems descriptive enough.

-Paul

> -Original Message-
> From: Waldhoff, Rodney [mailto:[EMAIL PROTECTED]]
> Sent: Tuesday, May 28, 2002 5:48 AM
> To: 'Jakarta Commons Developers List'
> Subject: [collections] collections of primitives?
> 
> 
> Over at the AxionDB project (http://axion.tigris.org/) we've created a
> handful of ArrayList-like collections that store primitives (for space
> efficiencies), support primitive method signatures like 
> indexOfInt(int) (for
> time efficiencies), but otherwise support the List interface (for
> interoperability).  
> 
> The space savings is substantial.  For example, a 
> ShortArrayList requires
> 1/10th the memory of an ArrayList of Short values (or a Short[]).  A
> LongArrayList requires 2/5ths the memory or an ArrayList of 
> Longs (or a
> Long[]). 
> 
> Someday (JDK1.5?) these will likely be superceded by 
> Java-generics (indeed,
> they make a good case for Java-generics).
> 
> If there are no complaints, I'd like to add these to 
> commons-collections,
> probably packaged as 
> org.apache.commons.collections.primitives (to make room
> for additional primitive-collections implementations and 
> avoid additional
> crowding in org.apache.commons.collections.*). I've already 
> got karma, I
> just thought I'd see if anyone complains or has a better packaging
> suggestion first.  You can browse the code at
> http://axion.tigris.org/source/browse/axion/whiteboard/one/src
/org/axiondb/u
til/

 - Rod

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections][Submit] TreeNode and friends

[Jack, Paul]

My votes:

1.  Eliminate TreeIterator.
2.  Eliminate equals(), hashCode() and clone() from TreeNode.
3.  Have iterator() make no guarantees about order; provide
the utility methods for depth-first and breadth-first.

Should the children be represented by a List or by a 
Collection?  Seems GUI trees would usually want their 
children sorted, so the ability to add a child at an
arbitrary index would be bad (you could manually 
muck up the sort order which could cause algorithms
expecting the List to be sorted to fail).

-Paul

> -Original Message-
> From: Stephen Colebourne [mailto:[EMAIL PROTECTED]]
> Sent: Monday, May 27, 2002 11:19 AM
> To: Jakarta Commons Developers List
> Subject: Re: [Collections][Submit] TreeNode and friends
> 
> 
> From: Kief Morris <[EMAIL PROTECTED]>
> > >I would rather keep the iterator on TreeNode. If there are only two
> standard
> > >ways to iterate then two methods would seem appropriate. 
> But are there
> more
> > >than two ways??
> >
> > I favor a single iterator() method on the interface which 
> returns the
> nodes in an
> > unspecified order. I'm ambivalent about having the specific 
> breadth/depth
> iterator
> > methods on the Interface, but if it seems like there will 
> be more than
> that, forget
> > it; keep just a single iterator() method and leave other options to
> implementations
> > rather than clutter the interface.
> >
> > There's nothing wrong with having a plain iterator() method even if
> there's no
> > default way it needs to be implemented; other Collection (non-List)
> classes
> > have iterators whose return order is unspecified.
> 
> Good argument. How about:
> 
> "iterator() returns an iterator over the tree including this 
> node and all of
> its children. For specificly ordered iterations, use the 
> methods provided on
> TreeUtils."
> 
> Thus we have an iterator() method on TreeNode and
> depthFirstIterator(TreeNode) and 
> breadthFirstIterator(TreeNode) methods on
> TreeUtils.
> 
> The other related question is whether to use TreeIterator, or 
> just Iterator.
> TreeIterator really only provides a typecast nextNode() 
> method. Is this
> enough to justify its existence?
> 
> Stephen
> 
> 
> --
> To unsubscribe, e-mail:   

For additional commands, e-mail:


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [PATCH][Collections] further testing code for Maps

[Jack, Paul]

> > It'd also be nice to reuse the same tests for different 
> > configurations of the same collection, eg, FastArrayList in
> > fast mode vs. FastArrayList in slow mode.
> > 
> > I'm going to go ahead and work on having fully extensible
> > testing suite for collections, if you've no objections...
> 
> No objections from me.  I'd love to do it myself, but time is thin. If
> you've got the time to put in the work, go for it.
> 
> Can you send a patch when you're done though rather than the 
> full source
> files?  That makes merging the changes in a bit easier.

Will do -- But what should I do about any new source files I
need to include?  Right now I'll plan on attaching the cvs diff
as one text file, and including any new source files as a separate
attachment.

Also, would it be easier for you to deal with a series of smaller
incremental patches, or should I just submit one big colossal 
patch when I've finished?

-Paul


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [SUBMIT][Collections] ReferenceMap, take 2

[Jack, Paul]

> Just an ideais it possible to write ReferenceMap as a 
> wrapper around
> another Map? If so, then we could have ReferenceSortedMap, 
> ReferenceList
> etc. all within ReferenceCollections.

Yes, but not efficiently.  For weak or soft keys, you'd have
to create a bunch of Reference objects that you don't actually
need:

   public Object get(Object key) {
  key = toReference(keyType, key);
  Object value = underlyingMap.get(key);
  if (valueType > HARD) return ((Reference)value).get();
  return value;
   }

Also I'm not convinced it's possible to write the iterator
effectively:  The hasNext() method must guarantee that the
next call to next() will return a valid object; however, the
Reference to that object might have cleared between the
call to hasNext() and next().  (Though I haven't spent too
much time thinking about this problem, there may be perfectly
sound solutions to it).

Though it would be nice to have a referenced SequencedHashMap
or LRUMap.

Also purging elements from an arbitrary list would be an
expensive operation (you'd have to traverse the entire list
looking for the purged element, and then invoke remove(index),
which would traverse the list again for a sequential list or
require a memory copy for a random access list).

> Also, in your tests I noted that you call System.gc() to 
> cause the garbage
> collector to run. Does this not just 'suggest' that the gc be 
> run, thus
> making the tests unreliable?

It's true.  The tests should use their own ReferenceQueue
to wait until the objects have been GC'd.  I'll modify the
tests accordingly.

-Paul


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections][Submit] TreeNode and friends

[Jack, Paul]

Some Feedback:

TreeNode:

1.  Should it extend Cloneable?  Some trees might not be
able to be Cloneable effectively (for instance, a Btree
backed by a file).
2.  I think we should allow setValue to throw an 
UnsupportedOperationException for unmodifiable trees.
3.  What's the rationale for having equals and hashCode
be reference based?  
4.  Must tree iterators be depth-first?  The ordered
traversal for a heap tree isn't depth-first.
5.  How about a valuesIterator method that returns an
iterator just for the values?

TreeNodeIterator

1.  What's the difference between getParentNode() and
nextNode().getParentNode()?

Other Thoughts

1.  A BinaryTreeNode implementation with convenient 
getLeftChild() and getRightChild() methods.
2.  Would it be possible for BinaryTreeNode to somehow
have a balance() method that could be overridden to
provide various balancing algorithms?  So then we 
could implement, for instance, RedBlackNode or 
AVLNode.
3.  Along these lines, it would be supersexy to 
provide a SortedMap implementation that could be
backed by any BinaryTreeNode implementation.

-Paul


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [PATCH][Collections] SequencedHashMap: equals, hashCode, toString

[Jack, Paul]

> Extending AbstractMap is not the right way to add an equals, 
> hashcode and 
> toString method.  I just committed real implementations for 
> the methods.

Was there something wrong with AbstractMap's implementations,
or did you just want to keep SequencedHashMap's superclass
as Object?  I'm just wondering if there's something my 
unit tests aren't catching...

-Paul

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

[SUBMIT][Collections] ReferenceMap, take 2

[Jack, Paul]

Now includes a junit test, which revealed several bugs,
which are now fixed.

-Paul






ReferenceMap.java
Description: Binary data


TestReferenceMap.java
Description: Binary data

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

[PATCH][Collections] further testing code for Maps

[Jack, Paul]

Hi,

I completed all the TODO and XXX items in TestMap.  Some of
the Map implementations (notably MultiHashMap) intentionally
violate the Map contract, so I overrode some of the new 
methods in concrete TestMap subclasses.

The only bugs the new methods found were in SequencedHashMap,
which Michael Smith has already patched.

There is still some work to be done in that keySet()
and values() collection views are inadequately tested.

-Paul






TestMapPatch.tar.gz
Description: Binary data

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

[PATCH][Collections] SequencedHashMap: equals, hashCode, toString

[Jack, Paul]

Index: SequencedHashMap.java
===
RCS file:
/home/cvspublic/jakarta-commons/collections/src/java/org/apache/commons/coll
ections/SequencedHashMap.java,v
retrieving revision 1.9
diff -r1.9 SequencedHashMap.java
100c100
< public class SequencedHashMap implements Map, Cloneable, Externalizable {
---
> public class SequencedHashMap extends AbstractMap implements Map,
Cloneable, Externalizable {

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

[SUBMIT] org.apache.commons.collections.ReferenceMap

[Jack, Paul]

Hi all,

Had the idea for this in the thread about SoftRefHashMap,
decided to code it up, as in the past I've often required
maps with phantom keys or values.  (Usually I just 
implemented them by manually placing the references in the
map; but then you have do painful things every time you
iterate...)

The class differs substantially from SoftRefHashMap in 
that it can be configured to use phantom references for
values; and it can be configured to use soft, weak or
phantom keys as well.

The code's based on java.util.WeakHashMap, so it should
be solid.  I'm putting together a junit test, so far 
everything looks good.

Since this class can be configured to act like SoftRefHashMap,
it might make sense to deprecate SoftRefHashMap, for all
the reasons Christopher Marshall has outlined.  

-Paul






ReferenceMap.java
Description: Binary data

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: PATCH : org.apache.commons.collections.SoftRefHashMap

[Jack, Paul]

> Firstly, the Map's innards should not be exposed to the user; 
> what is the 
> point of having a Map which uses a SoftReference 
> implementation if users of 
> the Map have to know this (and thus call the purge() method 
> when memory is 
> low (how will they know?)) - the Map should handle the 
> situation that memory 
> is low itself.

We can patch it to call purge in its mutator methods, 
similar to java.util.WeakHashMap.  


> With all due respect, you are wrong. The whole Map is broken 
> because keys 
> can only be purged "manually" by the user calling the purge() 
> method. There 
> should be no constraint on the user to do this. The only fix 
> for this is to 
> call the "purge()" method EVERY time an Object is added to 
> the Map, which I 
> am sure you will agree is a hopelessly non-performant way of 
> doing things.

Or, someone can invoke purge() on a regular basis, using
a Timer, or after major alterations to the Map.


> It seems odd that I could come across a line of code that said
> 
> SoftRefHashMap m = someAPI.getMeASoftMap();
> 
> But the Object returned to not use SoftRefs at all. Remember that the 
> behaviour of (for example) PhantomRefs is starkly different. 
> Users therefore 
> may be totally unable to understand the behaviour of their 
> code! PhantomRef 
> does not extend SoftRef, so why would PhantomRefHashMap extend 
> SoftRefHashMap?

I really do agree, the class name is misleading.  

Although now that you mention it, the current implementation
won't work for phantom references at all, since the constructor
for PhantomReference requires a ReferenceQueue.


> >Again, only the values() and entrySet() methods are broken.  By
> >all means, we should patch them.  But existing functionality that
> >works, and that people might rely on, should remain.
> 
> No - the Map does not properly reduce in size when the JVM is 
> running low on 
> memory but instead requires a "purge()" method to be called. The 
> implementation of the "purge()" method is terrible because it 
> has to iterate 
> through the whole Map. This needs to be done whenever an 
> Object is put in 
> the Map.
> 
> This Map without my fix (ie. to negate the possibility of having a 
> "createReference()" method to be subclassed) is practically 
> useless. If it 
> is the "done thing" here not to break backwards compatibility 
> then fine --> 
> have someone put my class in as a separate class. But don't 
> leave a daft 
> implementation of a class in Commons because someone didn't design it 
> properly in the first place!

Well, the collections package was created by harvesting
existing Jarkata code, so someone, somewhere is using
this class successfully.

I agree it has bugs.  We can fix the bugs without 
screwing our users.  Here's a two-step migration path
that addresses all of your issues (except the misleading
name, which I just don't see has a killer issue):

Step 1.  For commons 3.0, patch SoftRefHashMap as follows:

1.  Fix these methods to conform to the map contract:
equals(), hashCode(), containsValue(), values(), entrySet()

2.  Deprecate the createReference() method.  Provide a new
constructor that lets people specify the type of reference
to use (probably via static constants); encourage users to
use this approach instead of the deprecated method.

3.  Alter remove(), put() etc to invoke purge().


Step 2.  For commons 4.0, patch SoftRefHashMap as follows:

1.  Eliminate createReference().

2.  Rewrite purge() to use a ReferenceQueue.


If we want to deprecate the entire class, that's fine, but
its replacement should probably go through a design process,
to see if it can provide additional features.  For
instance, why not provide a class that allows for hard,
soft, weak or phantom references for both its keys and its
values?  So that, for instance, keys could be phantom 
references but values could be soft references; mappings
would be removed if the key was garbage collected OR if
memory was low.

-Paul

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: PATCH : org.apache.commons.collections.SoftRefHashMap

[Jack, Paul]

> Well, the existing "purge()" method iterated through the 
> whole Map checking 
> each reference so see if it had been cleared. The new 
> "purge()" method 
> simply calls "processQueue()". This does not iterate through 
> the whole Map, 
> but instead uses the ReferenceQueue to directly get the 
> references that have 
> been cleared and remove them from the Map. This should be 
> much quicker.

I agree that a ReferenceQueue improves performance, but why
deprecate the public purge() method?


> Backwardly compatible? The class is broken as it is! People 
> whose code 
> extends the current version doesn't work anyway...

The entrySet() and values() methods are broken, and should
be patched; the createReference() method works fine,
and there may exist perfectly valid code that requires it. 


> The functionality is questionable not only because 
> composition should be 
> favoured over inheritance; it seems madness that I can extend 
> a class called 
> SoftRefHashMap to NOT be a SoftRefHashMap.

"Madness?"  That's a bit extreme.  I agree the name is misleading
but that could be easily addressed in the documentation, without
breaking anybody's code.

And there are also ways of migrating to a composition pattern
that wouldn't require breaking compatibility.


> The extra "subclass-able" functionality CANNOT exist in my 
> implementation 

Couldn't you use a specialized subclass of ReferenceQueue?

 
> To be fair, given that my PATCH is actually a faithful 
> implementation of the 
> Map interface and the current class is not, I don't see the 
> problem - you 
> would be replacing a broken class that has some unnecessary 
> and questionable 
> functionality with a working version without it. Surely where 
> someone has 
> used a bad design in this instance, the problem can be rectified.

Again, only the values() and entrySet() methods are broken.  By
all means, we should patch them.  But existing functionality that
works, and that people might rely on, should remain.

-Paul


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [collections] Naming of collection wrappers classes (PredicateUtils et al)

[Jack, Paul]

> Thus I propose splitting PredicateUtils in two:
> PredicateCollections  (#1 above)
> PredicateUtils  (#2 above)

Well, that still leaves us with the problem that PredicateUtils
doesn't contain all of the predicate utils.  Other ideas:

1.  Move PredicateUtils.and, .or, .not, .instanceof, .TRUE and
.FALSE into CollectionUtils; rename PredicateUtils to 
PredicateCollections.

2.  Duplicate the static predicate methods in CollectionUtils
in PredicateUtils, so that one class's static methods invoke
the other's.

Also, I noticed that the inner class for the instanceof predicate
was declared public, whereas the other inner classes were declared
private.  Was that deliberate?

-Paul



--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [collections] - Few more collections for the masses... (impor tant for Struts view objects, maybe other projects)

[Jack, Paul]

> 1) What 8 interfaces?... There's only 2 that are valid.

Can't the reserve behavior be applied to:

1.  java.util.Collection
2.  java.util.Set
3.  java.util.SortedSet
4.  java.util.List
5.  java.util.Map
6.  java.util.SortedMap
7.  org.apache.commons.collections.Bag
8.  org.apache.commons.collections.SortedBag

I just like to be complete. :)


> 2) They're currently small and simple. I don't see a need to
over-engineer.

And I want them to remain small and simple, but hidden from the public API.
I just want to add one class to the public API, instead of many.


> 3&4) I'll get onto subList, but I don't fully agree that the rest 
> (Iterators) are relevant. For example, you want an Iterator when you 
> want to run over what is there, not what is "expected" to be there, 
> which is what these are for.

So long as the code obeys the contracts of the List and Iterator
interfaces, it's fine.

-Paul

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: Are FastArrayList/FastHashMap broken (unthreadsafe)

[Jack, Paul]

> So are you saying your patch won't work?
> http://marc.theaimsgroup.com/?l=jakarta-commons-dev&m=101953795432669&w=2
> 
> :)
> 
> 
> That patch is still on my radar.  I just haven't had the chance to do 
> anything with it yet. I've been swamped with too many other things.

*blush*

I thought the patch had been ignored, given that it's controversial.
(The patch alters the advertised behavior of the fast classes).  

However, it really will work on existing JVM platforms (I have confirmed
this with Bill Pugh, the guy who wrote the "Double-Checked Locking is
Broken!" declaration), and it provides a migration path to future JVM
platforms with better memory models...

Anyway, there are two separate issues, one involving sublists/submaps/
collection views, and one involving the Java Memory Model.  I've
opened another bug for the memory model issue...

I'll shut up about the Fast classes now. :)

-Paul



--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [collections] - Few more collections for the masses... (important for Struts view objects, maybe other projects)

[Jack, Paul]

> Obviously, list and map implementations respectively...
> http://www.keyboardmonkey.com/next/ReserveList.java
> http://www.keyboardmonkey.com/next/ReserveMap.java

Haven't looked in-depth at the code, but a few thoughts already:

1.  I'd like to see implementations for all eight collection 
interfaces.

2.  I'd like those implementations to be generated from one class
that uses static factory methods to construct the Reserve 
wrappers, as per the Collections.synchronized* methods.

3.  From the implementation of ReserveList, it doesn't appear
that sublists inherit the reserve behavior; an index accessed
via a sublist won't ever invoke the createObject method.

4.  Similar to #3, but for iterators.

-Paul

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: Are FastArrayList/FastHashMap broken (unthreadsafe)

[Jack, Paul]

> > I have just been looking through the source code to the classes 
> > org.apache.commons.collections.FastHashMap and 
> > org.apache.commons.collections.FastArrayList - these classes seem
totally 
> > broken to me because they are designed for use within a multi-threaded 
> > environment but are not threadsafe within the definition of the Java
memory 
> > model.

> They're not *totally* broken.  Just not really thread safe in highly 
> optimized runtimes.  

Insofar as Java code is supposed to be cross-platform, the fact that
the code isn't really thread safe in highly optimized runtimes really
does mean it's totally broken.

Furthermore, the code won't work in non-highly optimized runtimes either.
The instructions that clone the internal collection and the instructions
that store the reference to the clone can be done or percieved out-of-order
because of optimizing compilers or processor pipelines.  A thread 
invoking a read operation might raise all sorts of unexpected
RuntimeExceptions
because the clone() of a write operation hasn't finished yet.  In theory
this could happen even on single-processor JIT environments (though to be
fair I've only ever tested the code on single-processor 386-based chips,
where everything seems to work just fine).



> ...
> If you don't think the fix for bug 7924 will solve this issue, then file a

> separate bug for it.  

It's a separate issue, and there should be a separate bug.  However, there
is no way to fix the bug:  The Fast collection classes cannot behave
as advertised and be cross-platform, given the current Java Memory Model.

-Paul



--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [collections] Would like to contribute my RangeIterator

[Jack, Paul]

And to use a RangeIterator over a collection that isn't sorted,
you'd probably create a sorted collection first:

   new TreeSet(collection, comparator).subSet(first, last).iterator();

seems like it does what RangeIterator does.

-Paul

-Original Message-
From: James Strachan [mailto:[EMAIL PROTECTED]]
Sent: Tuesday, April 30, 2002 1:00 AM
To: Jakarta Commons Developers List
Subject: Re: [collections] Would like to contribute my RangeIterator


From: "Oliver Fischer" <[EMAIL PROTECTED]>
> Is there a PredicateIterator already?

Actually its called FilterIterator right now.

> Haven't seen it in the API doc
> for the collections? I think the FilterIterator is quite close to it.
> The my RangeIterator will stop, if the right border is reached, while
> (?) the FilterIterator evaluates every object. Think about iterators
> which point to a huge amount of objects...

Though that assumes that the underlying iterator returns objects sorted (in
the right ascending/descending order) that the left & right predicates are
is based on. This sounds a bit specific to me; maybe this should be done
using an 'Index' class of some kind to mimic the sorting and range features.
For the general approach of filtering an iterator the existing Filterterator
seems fine which works on any Predicates and irrespective of sorting...

Predicate predicate = new Predicate() {
public boolean evaluate(Object object) {
Foo foo = (Foo) object;
return foo.getAge() > 12 and foo.getAge() < 67;
}
}
return new FilterIterator( iterator, predicate );

James


_
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com


--
To unsubscribe, e-mail:

For additional commands, e-mail:


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections][SUBMIT] TypedList

[Jack, Paul]

Hi Michal,

In another thread ([SUBMIT] WeakHashSet) we've been discussing
having a two-transformer based approach that would let you handle
strings in the way you describe.  The functionality we were
trying to achieve was the ability for a list or set or map to
transform objects into WeakReferences before adding them to the
collection and transforming the WeakReferences back into their
referents before returning them from the collection...the same
pattern could be used for case-insensitive strings with a class
like this:

   public class CaseInsensitiveString {

   String string;

   public CaseInsensitiveString(String string) {
this.string = string;
   }

   public boolean equals(Object o) {
   return string.equalsIgnoreCase(o);
   }

   public int hashCode() {
   return string.hashCode();
   }
   }

The input transformer could convert the normal string to a 
CaseInsensitiveString, and the output transformer could convert
the CaseInsensitiveString back into a normal string.

You might want to check out the WeakHashSet thread to see if 
you think this approach makes sense...

-Paul


-Original Message-
From: Michal Plechawski [mailto:[EMAIL PROTECTED]]
Sent: Tuesday, April 30, 2002 8:35 AM
To: Jakarta Commons Developers List
Subject: Re: [Collections][SUBMIT] TypedList


Hello,

> Just being Devil's advocate for a moment but
> Couldn't this kind of thing be done with custom Comparators and (say)
> TreeMap?

Of course it could. But everyone knows that HashMap is much more efficient
than TreeMap, and so is the wrapper I described. This allows not to be
constrained to particular Map implementation.
Another thing is that I do not understand the real use case laying behind
the discussed Transform-xxx. I do not see why somebody wants to put
transformed elements into a collection, but ask for them directly. It breaks
some natural laws, like:

map.put(x, y);
map.containsKey(x); // this should be true

I think that this may be very misleading for many people, and be the reason
of hard-to-find errors. IMHO this idea breaks basic Collection Framework
intuitions.

However, this Predicate-xxx stuff is a completely different story and a good
idea I think.

Regards,
Michal



--
To unsubscribe, e-mail:

For additional commands, e-mail:


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections][SUBMIT] WeakHashSet

[Jack, Paul]

> I'm not sure a two transformer approach is all thats needed. Collections
> have three basic types of method:
> - input (add/set)
> - query (indexOf, contains, equals, remove)
> - output (get, toArray)
> The Predicate/Transform proposal covers only the input group at the
moment.
>
> A 'two transformer' approach would cover the output group of methods (but
> would require another 7 classes to do it). This is perfectly possible, but
> naming would be interesting :-)

Well, we could eliminate the need for 1-transformer implementations by
providing an "identity" transform, that doesn't actually alter the object.

And it seems that the "query" group of functions would just use the
"input" transform...here's what the code looks like in my head:

public boolean contains(Object value) {
value = inputTransformer.transform(value);
return wrapped.contains(value);
}

public Object get(int index) {
Object result = wrapped.get(index);
return outputTransformer.transform(result);
}

public Object set(int index, Object value) {
value = inputTransformer.transform(value);
Object result = wrapped.set(index, value);
return outputTransformer.transform(result);
}


> I have looked at the ProxyMap. It is suitable for use by the Predicate and
> Transform classes as it provides protected access to the map, but no
public
> method to access it. Thus ProxyList and ProxySet would also be useful.
> However, that would still only cover 3 of the 7 collections!
 
It's true, we'd be adding six public classes to the API...

> At the moment I'm pausing on the implementation of the predicate/transform
> classes until things clear.

Well the Predicate implementations, at any rate, appear uncontroversial, and
would be extremely useful.

-Paul

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections][SUBMIT] WeakHashSet

[Jack, Paul]

> >   // Creates a Set backed by the given map.  Given
> >   // map must be empty.
> >   public static Set createSet(Map map);
> >
> >   public static SortedSet createSortedSet(SortedMap map);
>
> This kind of depends on how a Set is backed by a Map.  (You'll have to
> forgive me for not knowing how this works.)  For example, in a
WeakHashMap,
> it is the keys that are held with weak references.  If while backing the
Set
> with this Map, the Set's values are stored in the Map's values and not its
> keys, then it may not work as expected.  If it works as expected, I have
no
> objection to this.

The map-to-set wrapper would have to use the map's keys as the set's
elements, as values in a map are not guaranteed to be unique.  The 
WeakHashMap javadoc specifies that it uses "weak keys", so it should
work correctly with such a set wrapper.


> So maybe what I really need to do is write a "weak reference Set wrapper,"
> and encapsulate whatever Set the user passes.  Basically, doing something
> similar to your Transformers and Predicates, that wrap underlying
> collections.  Perhaps the natural extension is to go to Lists, etc. as you
> are discussing with Transformers and Predicates.

As long as the public API is static wrapper methods for each of the 
implementations (as per the java.util.Collections.synchronized methods)
I'm fine with this.

Although it really does feel like we could provide some sort of Transformer-
based approach that would enable weak elements but also other
functionality...
Like...Before I mentioned a two-transformer approach.  If the "read" 
transformer (which would transform weak references back into their referents
before returning the value from the collection) emptied the reference queue
before returning results, the two-transformer approach would probably work.


> Which brings me to another thought - Ultimately, this "weak reference
> Collection wrapper," Transformers and Predicates are all collection
wrappers
> of one sort or another that encapsulate another collection that actually
> stores the objects (or another wrapper).  Perhaps they should all subclass
> from the same class, or implement a common interface?

There already exists a "ProxyMap" class for this purpose for Maps, and 
there's been talk of including "ProxyList", "ProxySet" etc.  My feeling
is if you want to code them up, they'd be accepted.

-Paul

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections][SUBMIT] WeakHashSet

[Jack, Paul]

Hi,

I have a few thoughts regarding your WeakHashSet...

My first thought was to somehow integrate it with the
whole Transformer/Predicate collections we've been 
discussing in another thread.  So you'd have a Transformer
that converted an object into a WeakReference before 
storing it in the set.  However, you'd need *another* 
Transformer to convert those WeakReferences back into
their referents when taking the objects out of the set.
>From what I understand, the proposed Transformer collections
only transform when objects are added.  Furthermore it's
unclear whether a two-Transformer based implementation would
work in all the algorithms for weak references (you'd still
need to empty the ReferenceQueue on a regular basis...)

My second thought is, the two Set implementations in the JDK
are backed by Map implementations.  WeakHashSet could be 
implemented as a Set that's backed by a WeakHashMap.  I'm 
thinking of having a static wrapper method in CollectionUtils
that would provide a Set backed by *any* map:

  // Creates a Set backed by the given map.  Given
  // map must be empty.
  public static Set createSet(Map map);

  public static SortedSet createSortedSet(SortedMap map);

This way, a user could get a weak hash set by calling 
CollectionUtils.createSet(new java.util.WeakHashMap()).
Or, they could use soft references instead of weak 
references in their set by calling 
CollectionUtils.createSet(new
org.apache.commons.collections.SoftRefHashMap()).

This also limits the number of classes we'd have to develop
to provide the Predicate and Transformer collections...

What do you think?

-Paul

-Original Message-
From: Jeff Keyser [mailto:[EMAIL PROTECTED]]
Sent: Tuesday, April 23, 2002 6:40 PM
To: 'Jakarta Commons Developers List'
Subject: [Collections][SUBMIT] WeakHashSet


Trying again...  Perhaps my wrapping the source code into a jar was
confusing.  This time I'm just attaching the source files.

> -Original Message-
> From: Jeff Keyser [mailto:[EMAIL PROTECTED]]
> Sent: Saturday, April 13, 2002 8:10 PM
> To: Jakarta Commons Developers List (E-mail)
> Subject: [SUBMIT] WeakHashSet
>
>
> Attached is a jar containing the three source code files for
> the WeakHashSet
> I mentioned I would like to contribute.  It subclasses the
> Java 1.2 HashSet
> class, and works exactly the same except that the elements
> are held in the
> set with weak references.
>
> Thanks!
>

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections][SUBMIT] TypedList

[Jack, Paul]

> PredicatedList would just take a Predicate in its constructor, and
> anytime someone adds an element it throws an exception if the
> predicate's evalute method returns false on the element.  Then when
> TypedList extends PredicatedList it becomes a very small class that
> simply constructs a TypeCheckPredicate and passes it to its superclass.

I wouldn't even have a subclass for TypedList; I'd just put a static
convience method in the TypeCheckPredicate class:

static List getTypeCheckedList(List list, Class type)
{
 return new PredicateList(list, new TypeCheckPredicate(type));
}

-Paul

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections][SUBMIT] TypedList

[Jack, Paul]

> The way I did this was:
> 
> TypedStructure interface. AbstractTypedStructure class.
> IllegalTypeException exception.
> 
> Then TypedSet/List/Map implement Set/List/Map and extend
> AbstractTypedStructure.

Hehehehe...we *could* use dynamic proxy classes to provide 
one factory method that would work for all collections and
maps...

This isn't a serious suggestion, just proof that I have way
too much time on my hands...

-Paul


package org.apache.commons.collections;

import java.lang.reflect.InvocationHandler;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.lang.reflect.Proxy;
import java.util.Arrays;
import java.util.HashSet;


public class PredicateCollectionFactory
{

static class PredicateInvocationHandler implements InvocationHandler
{
private Predicate predicate;
private Object target;


public PredicateInvocationHandler(Object target, Predicate
predicate)
{
this.target = target;
this.predicate = predicate;
}


public Object invoke(Object proxy, Method method, Object[]
parameters) throws Throwable
{
if (method.getName().equals("equals"))
{
return defaultInvoke(target, method,
parameters);
}
Class[] types = method.getParameterTypes();
for (int i = 0; i < types.length; i++)
{
if ((types[i] == Object.class) &&
!predicate.evaluate(parameters[i]))
{
throw new
IllegalArgumentException();
}
}
return defaultInvoke(target, method, parameters);
}


static Object defaultInvoke(Object target, Method method,
Object[] parameters) throws Throwable
{
try
{
return method.invoke(target, parameters);
}
catch (InvocationTargetException e)
{
throw e.getTargetException();
}
}
}


private static Class[] getAllInterfaces(Object object)
{
HashSet set = new HashSet();
for (Class c = object.getClass(); c != null; c =
c.getSuperclass())
{
set.addAll(Arrays.asList(c.getInterfaces()));
}
return (Class[])set.toArray(new Class[set.size()]);
}


public static Object create(Object collection, Predicate predicate)
{
InvocationHandler handler = new
PredicateInvocationHandler(collection, predicate);
Class[] interfaces = getAllInterfaces(collection);
ClassLoader loader =
PredicateCollectionFactory.class.getClassLoader();
return Proxy.newProxyInstance(loader, interfaces, handler);
}


// Example usage...
public static void main(String args[])
{
java.util.List list = new java.util.ArrayList();
Predicate predicate = new Predicate() {
public boolean evaluate(Object object)
{
return (object instanceof String);
}
};
list = (java.util.List)create(list, predicate);
list.add("Hello, nurse!");  // works fine
list.add(new Integer(4)); // will raise
IllegalArgumentException
}

}


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [Collections][SUBMIT] TypedList

[Jack, Paul]

Hi Steve,

Your TypedList got me thinking...At first I thought, wouldn't
it be nice to specify a parameter that would allow the null 
element (sometimes I need a list that allows nulls)...then I 
got to thinking, actually wouldn't it be nice if the validate()
method could be overridden by a subclass to allow more than one
class type...then I thought, actually, wouldn't it be nice if
the validation were completely generic, so that you supplied the
validation routine in the constructor of the list...then I 
realized, the collections package already defines an interface
for validations (Predicate)...

So...do you think it's a good idea to alter TypedList so that it
takes a Predicate in its constructor?  You could then supply a
concrete Predicate that does the Class.isInstance check...

-Paul

-Original Message-
From: Stephen Colebourne [mailto:[EMAIL PROTECTED]]
Sent: Sunday, April 21, 2002 2:13 PM
To: Jakarta Commons Developers List
Subject: [Collections][SUBMIT] TypedList


Hi,
After a quick check, I could find no implementation of a type checking list
in collections. As I needed it, I have created one. Here is the class
javadoc:
 * TypedList is a list wrapper that supports type checking. Only elements
 * of the specified type (or a subclass) can be added to the list. An
 * attempt to add a different kind of object, or null, will cause an
 * IllegalArgumentException.
 * 
 * Constructing a new instance of this class will use an ArrayList behind
 * the scenes. Alternatively, the static wrap method can be
 * used to wrap any object implementing List.

The code is attached as a zip. Feedback welcome on whether this is suitable
for inclusion in the collections area.

Stephen

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

[PATCH][Collections] Thread-safe fast collection classes

[Jack, Paul]

Attached are modifications to FastArrayList, FastHashMap,
and FastTreeMap...

1.  Sublists, submaps, map collection views, iterators
and list iterators are all thread-safe now.  Many many 
package-protected classes were added to achieve this.

2.  Serialization has been somewhat improved.

3.  toString() methods have been added to FastHashMap and
FastTreeMap -- the previous implementation would always return
an empty map ("{}") if toString() were invoked.

4.  The classes are now, controversially, cross-platform.
The earlier versions were plagued by the same problems as 
the double-checked locking idiom; on some platforms, an
optimizing compiler or pipeline could conceivably write an
object reference before the object was fully modified.  Or,
with multiple processors, some kind of read barrier is needed
to make sure a processor has the most recent object reference...

The attached versions don't have these problems.  But, it's a
controversial fix for the following reasons:

a.  In order to do it, the following fields were demoted from 
protected to private:  FastArrayList.list, FastHashMap.map, 
FastTreeMap.map.  This of course breaks binary compatibility.
However, it's impossible to do the fix if these fields are 
accessible.  There are now protected accessor and mutator 
methods for those fields, so code that uses them can be made to
work with a minimal migration effort.

b.  One new class (SafeReference) and one new interface 
(SafeReferenceFactory) were added to the commons.collection
package.  These classes probably don't belong there however,
as their scope is more generic.  

c.  The new class and interface utilize a system property,
org.apache.SafeReferenceFactoryClass.  

d.  By default, read operation in the fast collection classes now
actually enter a monitor.  I realize the whole point of the
classes was to avoid synchronization on read operations, but it
simply cannot be done in a platform-independent way.  However,
the classes are still "fast" for two reasons:

* The critical section on a read operation is "the shortest 
imaginable".  Basically fast mode reads look like this by default:

public String toString() {
Collection local;
synchronized (this) {
local = this.global;
}
return local.toString();
}

So multiple threads won't have to wait for a lengthy read op like
toString() to complete before acquiring the monitor.  This seemed 
like the next best thing to unsynchronized reads.

* The default synchronization can be overridden, if you know your 
platform can support safe unsynchronized reads.  That's the point of
the SafeReferenceFactory interface and the system property...you
can provide a custom implementation of SafeReference that doesn't
synchronize on reads.  In particular, the forthcoming revision to the
Java Memory Model will probably allow a SafeReference impl based on
the volatile keyword.

Again, it's controversial.  But it seems having platform-independent
code is worth it.  Lemme know what you think...

-Paul




fast_patch.jar
Description: Binary data

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

RE: [SUBMIT] OptimizedFastArrayList

[Jack, Paul]

> Is there any external behavior difference between FastArrayList and your
> OptimizedFastArrayList (other than performance)?  If so, can you
> explicitly specify the differences and why?  If not, is there a reason not

> to just replace the existing FastArrayList with the faster implementation?

Only major difference is that my version has no concept
of "fast" vs. "slow" mode -- no setFast(boolean) method.
It could be added.  The main thing is that the two classes
have different superclasses.  FastArrayList extends from
ArrayList; however, it doesn't use any of ArrayList's state;
it reimplements all the list methods.  So, I thought my 
version would just extend Object and implement List directly.

But conceivably, yes, OptimizedFastArrayList could simply
replace FastArrayList, by adding the fast mode feature and
extending (and also ignoring) ArrayList.


> is it me, or does this behavior suffer from the double checked locking
> problem?  While this isn't the exact same scenario (i.e. the double
> checking of a variable one in and one outside a synchronized block), I
> believe the situation is the same:  it is possible that a non-synchronized
> read can see the cloned object before that cloned object is fully created.

Ew, yes, forgot about that.  The State reference can be assigned before
it's initialized with its constructor...

Code can be rewritten, however, so that the constructor is never called
by using clone() to copy it rather than using a constructor...The docs
you provided don't indicate whether clone() would suffer from the same
problem.  Will have to research...

Good catch!  I never would have thought of that...


> [Paul, I don't mean to pick on you about this.  The existing Fast* classes

> suffer from the exact same problem]

Pick away. :)


> Actually, if the ArrayList implementeds were smart, they aren't "cloning"

> the array each time, they are just adding the element in an existing, but
> empty, slot in the array.  That is, the underlying array is possibly
> larger than ArrayList.size().  An add(Object) only needs to duplicate the
> array if the existing array is full.  

Correct; the set(int, Object) and add(Object) methods are indeed slower
in my implementation.  However...


> An add(int, Object) may need to
> "move" elements, but shouldn't need to clone the entire array.  The actual
> cloning of the array (to grow or shrink the size) can have an amortized
> constant time operation if the the array is doubled when a grow is
> required (and if you add in the shirnking, which I don't think the JDK
> impl does, you would halve the size of the array when it is 1/4 full).

...however, when you're copying the elements for an add(int, Object)
method, you essentially have to clone the array.  Actually when I say
"clone" I really mean "reallocate".  java.util.ArrayList uses 
System.arraycopy in its add(int, Object) implementation; and the javadoc
for System.arraycopy indicates that if the source and target arrays
are the same, a new array is allocated, the source is copied to the 
new array, and then the contents of the new array replace the original:
Essentially, it's been cloned.

Furthermore, *all* of the write methods in ArrayList except add(Object)
and set(int, Object) need to do this.

So you're reallocating the array, because you have to.  FastArrayList, 
however, can wind up reallocating it 3 times:  Once during the explicit
clone() of the internal ArrayList, once when the internal ArrayList 
ensures its capacity, and once during the internal implementation of
add(int, Object).  My version only allocates the array once.

However, I've just completed the performance tests, and plain vanilla
ArrayList's algorithms are still faster in a singlethreaded context.
(To be expected, since it doesn't have to clone State objects all the
time.)  So the javadoc comment that OptimizedFastArrayList should
perform similarly to ArrayList overexaggerates...ahem.


> In your version, you may even be able to get rid of the single clone using
> a similar technique.  For example, if you are adding to the end
> (add(Object)), if the array already has room for one more element, you
> could just increase the size and create a new State rather than a new
> State *and* a new array.  When removing the last element, use the same
> array, but create a new State with the smaller size.  I'm not sure if that
> really buys much though, as it requires excess memory for the empty array
> elements that are only used if an add operation occurs sometime in the
> future.  Considering that the underlying ArrayList impl uses that memory 
> anyway, I'm not sure this is that big of a deal when considered as a 
> replacement of FastArrayList. 

It's true; I can improve the add(Object) implementation.  Thanks again,
I wouldn't have thought of it.

I'll look into the double-checked locking thing.

-Paul


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

[SUBMIT] OptimizedFastArrayList

[Jack, Paul]

Furthering my obsession with FastArrayList...

Attached is a new List implementation inspired by 
but faster than FastArrayList.  From the javadoc:

Optimized thread-safe array-backed dynamic java.util.List
implementation.

The list is backed by a dynamic array; the array will
grow automatically as more elements are added.  This is 
just like java.util.ArrayList; unlike ArrayList, however, 
the array can also *shrink* after a remove operation.  
The internal array is always the same size as the list, 
saving memory.

Read access to this list is not synchronized, but write
access is.  To pull this trick off, the state of the list
is cloned during a write, the changes are applied to the
clone, and then the clone replaces the list's state.  Read
operations use a local reference to the old state, and are
not adversely affected by a write.  This is similar to 
org.apache.commons.collections.FastArrayList.

However, since the list is backed by a dynamic array, *many
of the algorithms that alter the list already require that 
the state be cloned*.  For instance, to remove an element, 
a new array must be allocated, and the elements from the old
array (minus the removed object) must be copied to the new 
array.  FastArrayList essentially performed the cloning twice:
It first clones the entire list, and then performs the costly
remove() operation on the copy.  This implementation is 
optimized such that a new array is only allocated once.  
Assuming no monitor contention, this class should perform 
similarly to java.util.ArrayList, except for the add(Object)
and set(int, Object) methods, which now perform in linear time.

Sublists produced by this class are also thread-safe, and
they are also not synchronized during a read operation.

The iterators produced by this class are *not* "fail-fast".
Read operations on an iterator *never* fail.  A
ConcurrentModificationExcepiton will only be raised if the
original list is modified in some way and somebody subsequently
attempts to modify it via the iterator.

-Paul


Paul Jack
Database Administrator
San Francisco AIDS Foundation
[EMAIL PROTECTED]
(415)487-3075

"As far as we can discern, the sole purpose
of human existence is to kindle a light of
meaning in the darkness of mere being."
 --Carl Jung





OptimizedFastArrayList.java
Description: Binary data

--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

Further thoughts on FastArrayList, FastHashMap, FastTreeMap

[Jack, Paul]

Can we generalize?  It seems that FastHashMap
could just as easily accept any Map implementation
in its constructor.  In other words, it could work
just as well with java.util.IdentityHashMap or 
java.util.WeakHashMap or 
org.apache.commons.collections.DoubleOrderedMap:

public class FastMap implements Map {
public FastMap(Map m) { //... }
}
//...
}

The implementation would be more or less the same,
but would allow you to use specialized maps in a 
fast thread-safe manner.  Seems users could benefit
from a composition model here.

Similar for FastArrayList and FastTreeMap.  In fact
we could create fast wrapper classes for all the basic
Java collection types and the commons' Bag:

FastBag
FastCollection
FastList
FastMap
FastSet
FastSortedSet
FastSortedMap

Would be very useful, IMHO.  Sort of pollutes the 
package though (seven new classes!).  

I'd be happy to code them up since I sort of have
to do some of it anyway for a project I'm working on,
so if everyone thinks it's a good idea I'll do it.

Thoughts?

-Paul


Paul Jack
Database Administrator
San Francisco AIDS Foundation
[EMAIL PROTECTED]
(415)487-3075

"As far as we can discern, the sole purpose
of human existence is to kindle a light of
meaning in the darkness of mere being."
 --Carl Jung


--
To unsubscribe, e-mail:   
For additional commands, e-mail: 

FastArrayList, FastHashMap, FastTreeMap not thread safe

[Jack, Paul]

Hi,

I noticed that version 2.0 of the Commons Collections
has been released so I thought I'd browse through the
code.  While doing so I noticed something about 
FastArrayList, FastHashMap and FastTreeMap.

List and Map objects can return views on their contents
that can be modified.  For instance, elements can be 
removed from an ArrayList via its iterator().  Elements
can be removed from a map via its keySet() or its values()
collection.  A TreeMap can also return a submap that can
be modified.  Generally, changes on a view of a collection
are reflected in the original and vice-versa.

The problem is, with FastArrayList or FastHashMap, in "fast"
mode, if somebody tries to modify a collection view (say, a
keySet() of a FastHashMap) they will never enter the FastHashMap's
monitor.  The state of the FastHashMap can become corrupted if
more than one thread attempts to modify its keySet(); and threads
attempting a fast get(Object) on a FastHashMap while another
thread modifies its keySet() may get faulty data back.

I'd recommend using the "unmodifiable" methods of the 
java.util.Collections class to make the collection views immutable.
This would solve the problem, but technically violate the contract
of java.util.Map and java.util.List (which specify that views on
a map or list must support all operations the original map or list
supported).  

Here's the list of methods that worry me:

FastArrayList.iterator()
FastArrayList.subList(int, int)

FastHashMap.keySet()
FastHashMap.entrySet()
FastHashMap.values()

FastTreeMap.keySet()
FastTreeMap.entrySet()
FastTreeMap.values()
FastTreeMap.subMap(Object, Object)
FastTreeMap.headMap(Object)
FastTreeMap.tailMap(Object)

Here's a sample fixed implementation of FastHashMap.keySet():

public Set keySet() {
if (fast) {
return Collections.unmodifiableSet(map.keySet());
} else {
synchronized (map) {
return map.keySet();
}
}
}


Paul Jack
Database Administrator
San Francisco AIDS Foundation
[EMAIL PROTECTED]
(415)487-3075

"As far as we can discern, the sole purpose
of human existence is to kindle a light of
meaning in the darkness of mere being."
 --Carl Jung


--
To unsubscribe, e-mail:   
For additional commands, e-mail: