#ifndef OrdColl_First
#define OrdColl_First
#ifdef __GNUG__
#pragma interface
#endif

#include "SeqColl.h"

class OrdCollectionIter;
class RevOrdCollectionIter;

//----- OrdCollection ----------------------------------------------------------

class OrdCollection : public SeqCollection {
friend OrdCollectionIter;
friend RevOrdCollectionIter;
public:
	MetaDef(OrdCollection);
	OrdCollection(int aCapacity= 1);
	~OrdCollection();
	void InitNew();
	void Empty(int newCapacity= cContainerInitCap);
	void FreeAll();

	//---- accessing
	Iterator *MakeIterator(bool forward= cIterForward, void *placement= 0);

	//---- sorting/searching
	void Sort();                    // based on Equal
	int BinarySearch(Object *);     // receiver must be sorted! -1 == not found

	//---- instrumentation
	virtual void CheckInvariant();

public:
	static const cDefaultCapacity;
	static const cMinExpand;
	static const cShrinkFactor;

protected:
	//---- primitives
	Object *primAddAt(Object *op, int idx);
	Object *primRemoveAt(int idx);
	Object *primPutAt(Object *op, int idx);
	Object *primAt(int idx);
	Object *primIndexOf(Object *op, int offset, int *idx);
	Object *primIndexOfPtr(Object *op, int offset, int *idx);

	//---- implementation
	int PhysIndex(int idx);
	int LogIndex(int phx);
	void MoveGapTo(int newGapstart);
	void Init(int aCapacity);
	bool LowWaterMark();
	void SetCapacity(int newCapacity);

protected:
	Object **cont;
	int capacity;
	int gapStart;
	int gapSize;
};

//---- OrdCollectionIter -------------------------------------------------------

class OrdCollectionIter : public Iterator {
friend OrdCollection;
public:
	OrdCollectionIter(OrdCollection *s);
	~OrdCollectionIter();

	Object *operator()();
protected:
	Container *GetContainer();
	void Detach();

	//---- robust iterators
	virtual void OnEmpty();
	virtual void OnAddAt(int idx);
	virtual void OnRemoveAt(int idx);

protected:
	OrdCollection *seq;
	int ce;
};

//---- RevOrdCollectionIter ----------------------------------------------------

class RevOrdCollectionIter : public OrdCollectionIter {
public:
	RevOrdCollectionIter(OrdCollection *s);

	Object *operator()();
protected:
	//---- robust iterators
	void OnEmpty();
	void OnAddAt(int idx);
	void OnRemoveAt(int idx);
};

//---- OrdCollection inlines ---------------------------------------------------

inline bool OrdCollection::LowWaterMark()
	{  return (bool) (size < (capacity / 4) && size > cContainerInitCap); }

inline int OrdCollection::PhysIndex(int idx)
	{ return (idx < gapStart) ? idx : idx + gapSize; }

inline int OrdCollection::LogIndex(int phx)
	{ return (phx < gapStart) ? phx : phx - gapSize; }

#endif