#pragma ident "%Z%%M% %I% %E% SMI"

#ifndef PointerTable_DEF_INCLUDED

#define PointerTable_DEF_INCLUDED 1

#include <stdlib.h>

#ifdef SP_NAMESPACE

namespace SP_NAMESPACE {

#endif

template<class P, class K, class HF, class KF>

PointerTable<P, K, HF, KF>::PointerTable()

: used_(0), usedLimit_(0), null_(0)

{

}

template<class P, class K, class HF, class KF>

void PointerTable<P, K, HF, KF>::clear()

{

vec_.clear();

used_ = 0;

usedLimit_ = 0;

}

template<class P, class K, class HF, class KF>

P PointerTable<P, K, HF, KF>::insert(P p, Boolean replace)

{

size_t h;

if (vec_.size() == 0) {

vec_.assign(8, P(0));

usedLimit_ = 4;

h = startIndex(KF::key(*p));

}

else {

for (h = startIndex(KF::key(*p)); vec_[h] != 0 ; h = nextIndex(h))

if (KF::key(*vec_[h]) == KF::key(*p)) {

if (replace) {

P tem(vec_[h]);

vec_[h] = p;

return tem;

}

else

return vec_[h];

}

if (used_ >= usedLimit_) {

if (vec_.size() > size_t(-1)/2) {

if (usedLimit_ == vec_.size() - 1)

abort(); // FIXME throw an exception

else

usedLimit_ = vec_.size() - 1;

}

else {

// rehash

Vector<P> oldVec(vec_.size()*2, P(0));

vec_.swap(oldVec);

usedLimit_ = vec_.size() / 2;

for (size_t i = 0; i < oldVec.size(); i++)

if (oldVec[i] != 0) {

size_t j;

for (j = startIndex(KF::key(*oldVec[i]));

vec_[j] != 0;

j = nextIndex(j))

;

vec_[j] = oldVec[i];

}

for (h = startIndex(KF::key(*p)); vec_[h] != 0; h = nextIndex(h))

;

}

}

}

used_++;

vec_[h] = p;

return 0;

}

template<class P, class K, class HF, class KF>

const P &PointerTable<P, K, HF, KF>::lookup(const K &k) const

{

if (used_ > 0) {

for (size_t i = startIndex(k); vec_[i] != 0; i = nextIndex(i))

if (KF::key(*vec_[i]) == k)

return vec_[i];

}

return null_;

}

template<class P, class K, class HF, class KF>

P PointerTable<P, K, HF, KF>::remove(const K &k)

{

if (used_ > 0) {

for (size_t i = startIndex(k); vec_[i] != 0; i = nextIndex(i))

if (KF::key(*vec_[i]) == k) {

P p = vec_[i];

do {

vec_[i] = P(0);

size_t j = i;

size_t r;

do {

i = nextIndex(i);

if (vec_[i] == 0)

break;

r = startIndex(KF::key(*vec_[i]));

} while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));

vec_[j] = vec_[i];

} while (vec_[i] != 0);

--used_;

return p;

}

}

return 0;

}

template<class P, class K, class HF, class KF>

void PointerTable<P, K, HF, KF>::swap(PointerTable<P, K, HF, KF> &to)

{

vec_.swap(to.vec_);

size_t tem = to.used_;

to.used_ = used_;

used_ = tem;

tem = to.usedLimit_;

to.usedLimit_ = usedLimit_;

usedLimit_ = tem;

}

template<class P, class K, class HF, class KF>

PointerTableIter<P, K, HF, KF>::PointerTableIter(const PointerTable<P, K, HF, KF> &table)

: tablePtr_(&table), i_(0)

{

}

template<class P, class K, class HF, class KF>

const P &PointerTableIter<P, K, HF, KF>::next()

{

for (; i_ < tablePtr_->vec_.size(); i_++)

if (tablePtr_->vec_[i_] != 0)

return tablePtr_->vec_[i_++];

return tablePtr_->null_;

}

#ifdef SP_NAMESPACE

}

#endif

#endif /* not PointerTable_DEF_INCLUDED */