SortedAr.H

// SortedAr.H       $Revision: 1.9 $    $Date: 2005/05/24 11:39:40 $ 

#if !defined __SortedAr_H

#define __SortedAr_H

#include <mix/Types.h>
#include <mix/DynAr.H>

/*************************************************************
 * Abstract Dynamyc Array with sorting feature
 *************************************************************/

class SortedAr : public DynAr
{
protected:

  // Recursive function of quick sort.
  void  quick_sort (Compar order, unsigned L, unsigned R);

  // Recursive function of binary search procedure.  Returns
  // index of found item or -1 is search failed.
  int   quick_find (const char* item, Compar order,
            unsigned L, unsigned R) const;

public:

  SortedAr (const SortedAr& sortedar)
    : DynAr(sortedar) {};
  SortedAr (unsigned size, unsigned quant, unsigned volume)
    : DynAr(size, quant, volume) {};

  // NO_ORDER, EQUAL - no sorting
  // ASCENT_ORDER, LESS - ascent order: a(i)<=a(i+1)
  // DESCENT_ORDER, GREATER - descent order: a(i)>=a(i+1)
  virtual void  sort (Compar order);

  // Usual compare between two elements; dummy version
  virtual Compar    compare (const char* item1,
                 const char* item2) const;

  // Search for needed item, meaning array is already sorted in
  // ascent order.  Returns -1 if item is not found.
  virtual int   quick_find_ascent (const char* item) const {
    if(0 == count())  return -1;
    return quick_find(item, ASCENT_ORDER, 0, count() - 1);
  }

  // Search for needed item, meaning array is already sorted in
  // descent order.  Returns -1 if item is not found.
  virtual int   quick_find_descent (const char* item) const {
    if(0 == count())  return -1;
    return quick_find(item, DESCENT_ORDER, 0, count() - 1);
  }

  // Find item and return index of it or -1 if search failed.
  // Redefines DynAr version of method with type specific comparation
  // by compare() virtual method.
  virtual int   slow_find (const char* item) const;

  // Search for the range, which includes given item value.  Ascent
  // order of the array is expected.  EQUAL is returned in case of
  // existent range (returned in L..R, L<=R).  LESS and GREATER means
  // the value is out of the whole range of array.
  virtual Compar    find_range_ascent (const char* value,
                       unsigned& L,
                       unsigned& R) const;

  // Search for the range, which includes given item value.  Descent
  // order of the array is expected.  EQUAL is returned in case of
  // existent range (returned in L..R, L<=R).  LESS and GREATER means
  // the value is out of the whole range of array.
  virtual Compar    find_range_descent (const char* value,
                        unsigned& L,
                        unsigned& R) const;

};


#endif  // SortedAr.H