///////////////////////////////////////////////////////////////////////////////
//                                                                           //
//  Copyright (C) 1995-1998 by the Board of Trustees of Leland Stanford      //
//  Junior University.  See LICENSE for details.                             //
//                                                                           //
///////////////////////////////////////////////////////////////////////////////

#ifndef _sortedlist_h_
#define _sortedlist_h_

#include "arraylist.h"

template <class _Data>
class Sorted_List {
private:
  Array_List<_Data> _sorted;
  Array_List<_Data> _unsorted;
  Bool (*_LessThan)(_Data, _Data);
  Bool _ascending : 1;
  Bool _isSorted    : 1;

  void Copy(const Sorted_List&);
  void Merge(const Array_List<_Data>& mlist);
  void Sort() const;

public:
  Sorted_List(Bool (*LessThan)(_Data, _Data), Bool ascending = TRUE,
	      int size=DEFAULT_ARRAY_SIZE)
    : _sorted(size), _unsorted(size), _LessThan(LessThan),
      _ascending(ascending), _isSorted(TRUE) {}
  Sorted_List(const Sorted_List &a) { Copy(a); }
  Sorted_List& operator=(const Sorted_List&);

  void Insert(_Data);
  void Merge(const Sorted_List&);
  void Delete(int);
  int NumItems() const { return _sorted.NumItems() + _unsorted.NumItems(); }
  _Data& operator[](int i) const
    { if (!_isSorted) Sort(); return _sorted[i]; }
  friend ostream& operator<<(ostream&, const Sorted_List&);
};


template <class _Data>
void Sorted_List<_Data>::Copy(const Sorted_List<_Data> &a) 
{
  if (!a._isSorted)
    a.Sort();
  _sorted = a._sorted;
  _unsorted.Shrink(0);
  _LessThan = a._LessThan;
  _ascending = a._ascending;
  _isSorted = TRUE;
}


template <class _Data>
void Sorted_List<_Data>::Merge(const Array_List<_Data>& mlist)
{
  ASSERT(mlist.NumItems() != 0);
  int numItems = _sorted.NumItems() + mlist.NumItems();
  _sorted.Grow(numItems);
  for (int i = numItems-1; i >= mlist.NumItems(); i--)
    _sorted[i] = _sorted[i-mlist.NumItems()];
  int position = 0;
  int sposition = mlist.NumItems();
  int mposition = 0;
  Bool m_lt_s;
  while (mposition < mlist.NumItems()) {
    if (!(sposition == numItems))
      m_lt_s = (*_LessThan)(mlist[mposition],_sorted[sposition]);
    if (sposition == numItems || m_lt_s && _ascending ||
	!m_lt_s && !_ascending) {
      _sorted[position++] = mlist[mposition++];
    }
    else {
      _sorted[position++] = _sorted[sposition++];
    }
  }
}


template <class _Data>
void Sorted_List<_Data>::Sort() const
{
  Sorted_List<_Data>& non_const_ref = *((Sorted_List<_Data>*)this);
  if (_ascending) {
    non_const_ref._unsorted.Sort(_LessThan);
  }
  else {
    non_const_ref._unsorted.SortReverse(_LessThan);
  }
  non_const_ref.Merge(_unsorted);
  non_const_ref._unsorted.Shrink(0);
  non_const_ref._isSorted = TRUE;
}


template <class _Data>
Sorted_List<_Data>& Sorted_List<_Data>::operator=(const Sorted_List<_Data> &a)
{
  if (&a!=this) {
    Copy(a);
  }
  return *this;
}


template <class _Data>
void Sorted_List<_Data>::Insert(_Data d)
{
  _unsorted.Append(d);
  _isSorted =FALSE;
}    


template <class _Data>
void Sorted_List<_Data>::Merge(const Sorted_List<_Data>& mlist)
{
  if (!_isSorted)
    Sort();
  if (!mlist._isSorted)
    mlist.Sort();
  Merge(mlist._sorted);
}


template <class _Data>
void Sorted_List<_Data>::Delete(int index)
{
  ASSERT(_isSorted);
  _sorted.Delete(index);
}    


template <class _Data>
ostream& operator<<(ostream &os, const Sorted_List<_Data> &a)
{
  if (!_isSorted)
    Sort();
  os << _sorted;
}


#endif