Comparators for ordering collection elements

If your collection requires automatic (internal) sorting, as in the case of sorted sequences, you will require a more sophisticated comparator than TMCollectibleComparator. Comparators for ordered collections provide a Compare function, that also returns an enumerated type. However, the Compare function for TMOrderableCollectibleComparator yields a broader set of return values. Ordered comparators can return kEqual in the same way comparators for unordered collections, but instead of returning kNotEqual, ordered comparators return either kLessThan or kGreaterThan.

Note that the objects compared by TMOrderableCollectibleComparator must descend from MOrderableCollectible. In addition to defining an IsEqual member function, orderable collectible objects must define protocol for IsLessThan and IsGreaterThan. The basic algorithm for TMOrderableCollectibleComparator::Compare looks something like this.

          if (leftObject->IsEqual(rightObject))
          return kEqual;
      if (leftObject->IsLessThan(rightObject))
          return kLessThan;
      else
          return kGreaterThan;
Of course, you don't have to worry about any of this unless you plan to subclass TComparator or one of its descendants. However you are likely to define your own classes whose instances may wind up as elements of collections. It's therefore important to understand that the way you implement the member functions IsEqual, IsSame, IsLessThan, IsGreaterThan, Compare, and Hash for any class you define will affect they way your objects perform as collection elements. In most cases you will only need to worry about overriding Compare and Hash.

The following program should clarify the use of ordered comparators with sorted sequences.

Sample program using a comparator for sorted sequences of text

      // Copyright (c) 1994 Taligent, Inc. All Rights Reserved.
  
  #ifndef Taligent_STANDARDTEXT
  #include <StandardText.h>
  #endif
  
  #ifndef _H_STDIO
  #include <stdio.h>
  #endif
  
  void printCollection(TCollectionOf<TStandardText>* collection)
  {
      int i = 0;                          // tracks order of elements
      TIteratorOver<TStandardText>* iterator = collection->CreateIterator();
      for (TStandardText* text = iterator->First();
           text != NIL;
           text = iterator->Next(), i++) {
  
          ////////////////////////////////////////////////////
          // buffer must be large enough for
          // longest possible string + zero terminator
          ////////////////////////////////////////////////////
          static const int kBufferSize = 256;
          static char extractBuffer[kBufferSize];
  
          text->Extract(TTextRange::GetMaximumRange(),
                        extractBuffer,
                        kBufferSize - 1);
          printf("\n%3d> %s", i, extractBuffer);
      }
      printf("\n");
  
      delete iterator;
  }
  
  int main()
  {
      TMOrderableCollectibleComparator<TStandardText>* comparator =
          new TMOrderableCollectibleComparator<TStandardText>();
  
      TSortedSequenceOf<TStandardText>* collection =
          new TSortedSequenceOf<TStandardText>(comparator, NIL);
  
      collection->Add(new TStandardText("one"));
      collection->Add(new TStandardText("two"));
      collection->Add(new TStandardText("three"));
  
      collection->Add(new TStandardText("one"));
      collection->Add(new TStandardText("two"));
      collection->Add(new TStandardText("three"));
  
      printCollection(collection);
  
      delete collection;
      return 0;
  }
The output shows lexical sorting based on calls by the ordered comparator to member functions of TStandardText (IsEqual, IsLessThan, IsLessThan).

      0> one
  1> one
  2> three
  3> three
  4> two
  5> two
There is no requirement that you specify a comparator in the constructor of a TSortedSequenceOf. If you don't, however, sorting will be based on comparison of address pointers to collection elements and the resulting collection order will make little sense unless you are explicitly managing a collection of pointers.

[Contents] [Previous] [Next]
Click the icon to mail questions or corrections about this material to Taligent personnel.
Copyright©1995 Taligent,Inc. All rights reserved.

Generated with WebMaker