#include "oop.h"
#include "minmax.h"

Set::Set(int size)
{
  mTally= 0;
  mArray= new Array(size);
}

oop Set::classNew(int size)
{
  return new Set(size);
}

int Set::scanFor(oop anObject)
{
  // Scan the key array for the first slot containing either a nil
  // (indicating an empty slot) or an element that matches anObject.
  // Answer the index of that slot or -1 if no slot is found.  This
  // method will be overridden in various subclasses that have
  // different interpretations for matching elements.
  int finish= mArray->size();
  int start= anObject->hash() % finish;
  // Search from (hash mod size) to the end.
  for (int index= start;  index < finish;  ++index)
    {
      oop element= mArray->at(index);
      if ((!element) || (*element == anObject))
	return index;
    }
  for (int index= 0;  index < start;  ++index)
    {
      oop element= mArray->at(index);
      if ((!element) || (*element == anObject))
	return index;
    }
  return -1;  // No match AND no empty slot
}

int Set::findElementOrNil(oop anObject)
{
  // Answer the index of a first slot containing either a nil
  // (indicating an empty slot) or an element that matches the given
  // object.  Answer the index of that slot or zero.  Fail if neither a
  // match nor an empty slot is found.
  int index= scanFor(anObject);
  if (index < 0)
    error("There is no free space in this set");
  return index;
}

int Set::growSize(void)
{
  return ::max(3, mArray->size() + 1);
}

oop Set::grow(void)
{
  // Grow the elements array and reinsert the old elements
  oop oldElements= mArray, tmp;
  int oldSize= mArray->size();
  mArray= new Array(oldSize + growSize());
  mTally= 0;
  for (int i= 0;  i < oldSize;  ++i)
    if ((tmp= oldElements->at(i)))
      noCheckAdd(tmp);
  return this;
}

oop Set::fullCheck(void)
{
  // Keep array at least 1/4 free for decent hash behavior
  if ((mArray->size() - mTally) < (::max(1, mArray->size() / 4)))
    grow();
  return this;
}

oop Set::noCheckAdd(oop anObject)
{
  mArray->atPut(findElementOrNil(anObject), anObject);
  mTally += 1;
  return this;
}

oop Set::atNewIndexPut(int index, oop anObject)
{
  mArray->atPut(index, anObject);
  mTally += 1;
  return fullCheck();
}

oop Set::add(oop newObject)
{
  if (!newObject) error("Sets cannot meaningfully contain nil as an element");
  int index= findElementOrNil(newObject);
  if (!mArray->at(index))
    atNewIndexPut(index, newObject);
  return newObject;
}

int Set::size(void)
{
  return mTally;
}

int Set::includes(oop anObject)
{
  return !!mArray->at(findElementOrNil(anObject));
}

oop Set::like(oop anObject)
{
  int index= scanFor(anObject);
  return (index < 0) ? 0 : mArray->at(index);
}

oop Set::iterator(void)
{
  return new SetIterator(this);
}

oop Set::array(void)
{
  return mArray;
}