Subject: [ldapext] Java LDAP API, sorting

From: "Steve Sonntag" <[email-masked]>
Date: Mon, 15 Apr 2002 16:20:35 -0600

Rob,

I have been reviewing the changes associated
with the addition of the Java Collections
Framework.  I believe the specification is
incomplete relative to the use of this framework.

Specifically I am looking at how one performs sorts
using the collections framework and have reviewed
the statements in Appendix 9.2 that relate to sorting.

>  LDAPAttributeSet 
>      
>          Implements Cloneable and java.util.Set. Removed the methods

>          made redundant by implementing Set: add(LDAPAttribute attr),

>          elementAt(), getAttributes(), remove(String name), 
>          removeElementAt(), and size().
>  
>  LDAPCompareAttrNames 
>           
>          Implements java.util.Comparator instead of
LDAPEntryComparator.
>  
>  LDAPSearchResults 
>      
>          Does not implement Enumeration. 
>           
>          Removed nextElement(). 
>           
>          Renamed hasMoreElements() to hasMore(). 
>           
>          Removed sort() (sorting can now be done with
classes/interfaces 
>          of the Collections framework now that LDAPAttributeSet 
>          implements Set).

The collections framework has two interfaces and two classes
that facilitate sorting.  These are:

-  The Comparable interface - an implementing
    object can be compared with another implementing
    object, determining the natural ordering of
    the objects.
-  The Comparator interface - implementers can
    compare and order two objects, called specific ordering.
-  The Arrays class - allows sorting of objects
    contained in an array using either natural
    or specific ordering.
-  The Collections class - allows sorting of
    objects contained in a class that implements the
    List interface using natural or specific ordering.

There seem to be three obvious kinds of data
that one might consider sorting:

1)	Values of a multi-valued attribute.
2)	Attribute Names
3)	Search Entries

Let's see how the Collections Framework
can be used to sort these items:

Sort values from a multivalued binary attribute:

	byte[][] values = attr.getByteValueArray( )
	Arrays.sort( values[]);                         // Order by byte
values
	Arrays.sort( values[], myComparator) // Specific ordering

Sort values from a multivalued String attribute:

	String[] values = attr.getStringValueArray();
	Arrays.sort(values);                            // Natural
ordering
	Arrays.sort(values, myComparator);  // Specific Ordering

Sort Attribute objects

	LDAPEntry entry = results.next();
	LDAPAttributeSet aset = entry.getAttributeSet()
	LDAPAttribute[] attrs = new LDAPAttribute[20];
	attrs = aset.toArray(attrs);            // from Set
	Arrays.sort(attrs);                           // Natural
ordering by attribute name
	Arrays.sort(attrs, myComparator); // Specific ordering

    Note: Currently natural ordering between
    LDAPAttribute objects is undefined since
    LDAPAttribute does not implement the Comparable
    interface.  I suggest that LDAPAttribute implement
    the Comparable interface with natural ordering
    based on attribute name.

Sort LDAPEntry objects

    It is not possible to sort Entries, since
    there is no way to get either a List or an
    Array from LDAPSearchResults.  I suggest
    that LDAPEntry implement the Comparable
    interface with natural ordering based on the
    dn, and that LDAPSearchResults implement
    a nextArray() method (see below).  If this
    were done, sorting of LDAPEntry objects
    could be done as follows:

    LDAPEntry[] entries = results.nextArray();
    Arrays.sort(entries);                           // Sort by dn
    Arrays.sort(entries, myComparator);	// Specific ordering.
    
    Note: myComparator is probably of type LDAPCompareAttrNames,
    but an application could implement their own Comparator class.
 
-----------------------------------------------------------------------------
Suggested changes to the draft:

2.1 public class LDAPAttribute
        implements Cloneable, Serializable, Comparable
  ------------------------
2.2.2 compareTo

	public int compareTo(Object obj)

    Compares this object with the specified object for
    order.  Ordering is determined by comparing attribute
    names (see getName()) using the compareTo() method of
    the String class. Returns a negative integer, zero, or
    a positive integer as this object is less than, equal
    to, or greater than the specified object.

     obj		The object to be compared to this object.
  ------------------------

2.14 public classs LDAPEntry
        implements Serializable, Comparable
  ------------------------
2.14.2 compareTo

	public int compareTo(Object obj)

    Compares this object with the specified object for
    order.  Ordering is determined by comparing dn values
    (see getDN) using the compareTo() method of the String
    class.  Returns a negative integer, zero, or a
    positive integer as this object is less than, equal
    to, or greater than the specified object.

     obj		The object to be compared to this object.

  ------------------------
(in class LDAPSearchResults)

2.35.5 nextArray 

	public LDAPEntry[] nextArray() throws LDAPException

Returns an array containing all LDAPEntries in the
order they were received. If automatic referral
following is disabled or a referral was not
followed, nextArray() will throw an
LDAPReferralException when the referral is received.

It should be noted that only those Entries which
have been received and not retrieved via next()
or nextArray() are placed in the array.  This will
generally be the number of entries specified by
batchsize. The size of the array returned will
equal the number of entries returned. If all
entries have already been returned, nextArray()
throws NoSuchElementException.  If a sort of all
entries returned by a search is desired, batchsize
should be set to zero so that all entries are received
by the API before control is returned to the application.
(see LDAPSearchConstraints.setBatchSize()).  Sorting
can be performed using the sort method of the Arrays class.
  ------------------------

-Steve

------------------------
Steven Sonntag
Novell, Inc., The leading provider of Net business solutions
http://www.novell.com 

_______________________________________________
Ldapext mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ldapext

---

From: "Steve Sonntag" <[email-masked]>
Date: Wed, 17 Apr 2002 13:34:24 -0600

Rob,

I realize I overlooked something in the discussion on sorting,
specifically
the two classes TreeSet and TreeMap that order objects as they are
added into the to the Tree object.  Objects are sorted either by 
their natural order or as specified by a Comparator object.

With that information, the following changes are in order.

>>> "Steve Sonntag" <[email-masked]> 15-Apr-02 4:20:35 PM >>>

> The collections framework has two interfaces and two classes
	Four Classes
>     List interface using natural or specific ordering.

-	The TreeSet class, an implementation of the SortedSet interface
 	sorts objects as they are added to the object, and
 	uses natural or specific ordering.
-	The TreeMap class, an implementation of the SortedMap interface
 	sorts objects by keys as they are added to the object, and
 	uses natural or specific ordering.
> 	Arrays.sort( values[]);      // Order by byte values
    TreeSet can be used to order values by looping through
	values and adding them to the set using natural ordering
	or a specific comparator.

> 	Arrays.sort(values);              // Natural ordering
    TreeSet can be used to order values by looping through
	values and adding them to the set using natural ordering
	or a specific comparator.

>     the Comparable interface with natural ordering

    TreeSet can be used to order attributes by looping
	through the name and adding each to the set using natural
	ordering or a specific comparator.

	If LDAPAttribute objects implement Comparable as I
	suggest, one can simply say "new TreeSet(attributeSet)"
	to create a naturally sorted collection of attributes.

>     but an application could implement their own Comparator class.

	Using TreeSet, Entries can be sorted by adding the Entries
	to the TreeSet object.  This has the advantage over nextArray()
	in that no fiddling need be done with batchsize.  It is up
	to the application to determine which Entries are sorted and
	how to deal with ensuring adequate memory for large sorts.

	I see no need for the above described nextArray method.

>     (see getDN) using the compareTo() method of the
StringaringValueArray();
> 	Array

Eliminate nextArray, but do have LDAPEntry and LDAPAttribute
implement Comparable.

The description of LDAPCompareAttrNames should be clarified to
something like the following:

2.7 public class LDAPCompareaAttrNames
			implements Comparator

   An object of this class defines the ordering when sorting
   search results. LDAPEntry objects are sorted by the value
   of the specified attribute name(s) in ascending or descending
   order.  This object is typically supplied to an implementation
   of the collection interfaces like TreeSet which performs the sort.

 -----------------------------------------------

In summary what I suggest is,

 add "implement Comparable" for classes LDAPAttribute and LDAPEntry
   (with appropriate description of natural compare mechanism)

 Clarify description for LDAPCompareAttrNames

-Steve