home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
OS/2 Shareware BBS: 10 Tools
/
10-Tools.zip
/
tlx501.zip
/
SRC
/
INTSET.CPP
< prev
next >
Wrap
C/C++ Source or Header
|
1996-07-08
|
10KB
|
328 lines
/****************************************************************************
$Id: intset.cpp 501.0 1995/03/07 12:26:16 RON Exp $
Copyright (c) 1991-95 Tarma Software Research. All rights reserved.
Project: Tarma Library for C++ V5.0
Author: Ron van der Wal
Implementation of class TLIntSet.
$Log: intset.cpp $
Revision 501.0 1995/03/07 12:26:16 RON
Updated for TLX 5.01
Revision 1.6 1995/01/31 16:30:14 RON
Update for release 012
Added partial support for SunPro C++ compiler
Revision 1.5 1995/01/06 15:57:53 ron
Corrected Revision keyword
Revision 1.4 1994/11/16 15:39:58 ron
Added module info; rearranged #include directives
Revision 1.3 1994/10/05 18:39:10 ron
Renamed TLx...() functions to tl...()
Revision 1.2 1994/09/27 20:22:32 ron
Changed path separator from / to \
Revision 1.1 1994/09/26 15:43:28 ron
Initial revision
****************************************************************************/
#include <tlx\501\_build.h>
TLX_MODULE_INFO("$Revision: 501.0 $");
#include <tlx\501\except.h>
#include <tlx\501\intset.h>
#include <tlx\501\template\valiter.cpp>
/*-------------------------------------------------------------------------*/
TLIntSet::Iter::Iter(const TLIntSet &aSet)
/* Constructor. Links to the given set of integers and resets the iterator.
---------------------------------------------------------------------------*/
: mSet(aSet)
{
}
/*-------------------------------------------------------------------------*/
bool TLIntSet::Iter::FirstPos()
/* Sets the iterator to the first element (if any) in the associated
set, returning true if that operation succeeds, else false.
---------------------------------------------------------------------------*/
{
return SearchFrom(mSet.First());
}
/*-------------------------------------------------------------------------*/
bool TLIntSet::Iter::NextPos()
/* Advances the iterator to the next element (if any) in the associated
set, returning true if that operation succeeds, else false.
---------------------------------------------------------------------------*/
{
if (mPos < mSet.Last())
return SearchFrom(mPos + 1);
else
return false;
}
/*-------------------------------------------------------------------------*/
const int &TLIntSet::Iter::Peek() const
/* Returns a reference to the current element. It is an error to call this
function if the last call to Next() wasn't successful, or if there has
been no call to Next() since construction or the last Reset().
---------------------------------------------------------------------------*/
{
TLX_ASSERT(IsValid());
return mPos;
}
/*-------------------------------------------------------------------------*/
bool TLIntSet::Iter::SearchFrom(int aPos)
/* Searches for the next element in the set, starting at the given
position. It updates mPos, and returns true if successful, else false.
---------------------------------------------------------------------------*/
{
index_t lastpos = mSet.Last();
while (!mSet.Contains(aPos))
{
if (aPos < lastpos)
aPos++;
else
return false;
}
mPos = aPos;
return true;
}
/*-------------------------------------------------------------------------*/
TLIntSet::TLIntSet(size_t aSize)
/* Constructor. Creates an empty set with the capacity to hold [0, aSize>.
---------------------------------------------------------------------------*/
: mSet(aSize)
{
mBase = 0;
}
/*-------------------------------------------------------------------------*/
TLIntSet::TLIntSet(int aLower, int aUpper)
/* Constructor. Creates an empty set with the given lower and upper bounds
(inclusive) and the capacity to hold [aLower, aUpper].
---------------------------------------------------------------------------*/
: mSet(aUpper - aLower + 1)
{
TLX_ASSERT(aUpper >= aLower);
mBase = aLower;
}
/*-------------------------------------------------------------------------*/
TLIntSet::TLIntSet(int *aVector, size_t aSize)
/* Constructor. Creates a set with the values in the given vector as its
initial contents. The resulting set has a capacity that matches the
lowest and highest elements from the set.
---------------------------------------------------------------------------*/
: mSet(0U)
{
TLX_ASSERT_PTR(aVector);
// We start with an empty bit vector, and first determine the required
// capacity.
int min = INT_MAX;
int max = INT_MIN;
for (size_t i = 0; i <= aSize; i++)
{
min = tlMin(min, aVector[i]);
max = tlMax(max, aVector[i]);
}
// Resize the bit vector and fill its contents
if (min > max) tlSwap(min, max);
// The following relies on the 2-complement property that max - min
// will result in a valid unsigned number even if their difference
// is larger than INT_MAX.
size_t sz = (size_t)(max - min + 1);
mSet.Resize(sz);
mBase = min;
Insert(aVector, aSize);
}
/*-------------------------------------------------------------------------*/
size_t TLIntSet::Count() const
/* Returns the number of elements in the set.
---------------------------------------------------------------------------*/
{
return mSet.Test();
}
/*-------------------------------------------------------------------------*/
bool TLIntSet::Contains(int aValue) const
/* Tests for the presence of the given element, returning true if it
appears in the set, else false.
---------------------------------------------------------------------------*/
{
if (aValue < LowerBound() || aValue > UpperBound())
THROW(TLXIndex(LOCUS, aValue));
return mSet.Test(aValue - mBase) != 0;
}
/*-------------------------------------------------------------------------*/
int TLIntSet::First() const
/* Returns the value of the smallest element in the set. It is an error
to call this function if the set is empty.
---------------------------------------------------------------------------*/
{
if (IsEmpty())
THROW(TLXEmpty(LOCUS));
return mSet.First() + mBase;
}
/*-------------------------------------------------------------------------*/
void TLIntSet::Insert(int aValue)
/* Adds a value to the set.
---------------------------------------------------------------------------*/
{
if (aValue < LowerBound() || aValue > UpperBound())
THROW(TLXIndex(LOCUS, aValue));
mSet.Set(aValue - mBase);
}
/*-------------------------------------------------------------------------*/
void TLIntSet::Insert(int aLower, int aUpper)
/* Adds a range of values to the set: [aLower,aUpper].
---------------------------------------------------------------------------*/
{
if (aLower > aUpper)
return; // Empty range
if (aLower < LowerBound())
THROW(TLXIndex(LOCUS, aLower));
if (aUpper > UpperBound())
THROW(TLXIndex(LOCUS, aUpper));
mSet.Set(aLower - mBase, aUpper - mBase);
}
/*-------------------------------------------------------------------------*/
void TLIntSet::Insert(int *aVector, size_t aSize)
/* Adds a number of individual elements to the set.
---------------------------------------------------------------------------*/
{
for (size_t i = 0; i < aSize; i++)
Insert(aVector[i]);
}
/*-------------------------------------------------------------------------*/
void TLIntSet::InsertAll()
/* Adds all elements to the set.
---------------------------------------------------------------------------*/
{
mSet.Set();
}
/*-------------------------------------------------------------------------*/
int TLIntSet::Last() const
/* Returns the value of the largest element in the set. It is an error
to call this function if the set is empty.
---------------------------------------------------------------------------*/
{
if (IsEmpty())
THROW(TLXEmpty(LOCUS));
return mSet.Last() + mBase;
}
/*-------------------------------------------------------------------------*/
int TLIntSet::LowerBound() const
/* Returns the lower bound (i.e. lowest valid member value) of the set.
---------------------------------------------------------------------------*/
{
return mBase;
}
/*-------------------------------------------------------------------------*/
void TLIntSet::Remove(int aValue)
/* Removes the given element from the set.
---------------------------------------------------------------------------*/
{
if (aValue < LowerBound() || aValue > UpperBound())
THROW(TLXIndex(LOCUS, aValue));
mSet.Reset(aValue - mBase);
}
/*-------------------------------------------------------------------------*/
void TLIntSet::Remove(int aLower, int aUpper)
/* Removes a range of values from the set: [aLower,aUpper].
---------------------------------------------------------------------------*/
{
if (aLower > aUpper)
return; // Empty range
if (aLower < LowerBound())
THROW(TLXIndex(LOCUS, aLower));
if (aUpper > UpperBound())
THROW(TLXIndex(LOCUS, aUpper));
mSet.Reset(aLower - mBase, aUpper - mBase);
}
/*-------------------------------------------------------------------------*/
void TLIntSet::Remove(int *aVector, size_t aSize)
/* Removes a number of individual elements to the set.
---------------------------------------------------------------------------*/
{
for (size_t i = 0; i < aSize; i++)
Remove(aVector[i]);
}
/*-------------------------------------------------------------------------*/
void TLIntSet::RemoveAll()
/* Removes all elements from the set.
---------------------------------------------------------------------------*/
{
mSet.Reset();
}
/*-------------------------------------------------------------------------*/
int TLIntSet::UpperBound() const
/* Returns the upper bound (i.e. highest valid member value) of the set.
---------------------------------------------------------------------------*/
{
return mBase + mSet.Size() - 1;
}