OrderedSet.h

/*  _________________________________________________________________________
 *
 *  UTILIB: A utility library for developing portable C++ codes.
 *  Copyright (c) 2001, Sandia National Laboratories.
 *  This software is distributed under the GNU Lesser General Public License.
 *  For more information, see the README file in the top UTILIB directory.
 *  _________________________________________________________________________
 */

//
// OrderedSet.h
//
#ifndef __OrderedSet_h
#define __OrderedSet_h

#ifdef __GNUC__
#pragma interface
#endif

#ifdef NON_ANSI
#include <iostream.h>
#else
#include <iostream>
using namespace std;
#endif

#ifndef ANSI_HDRS
#include <stddef.h>
#include <stdlib.h>
#else
#include <cstddef>
#include <cstdlib>
#endif

#include "_math.h"
#include "PackBuf.h"
#include "BasicArray.h"


typedef size_type OrderedSetIndex;


template <class T>
class UTILIB_API OrderedSet
{
public:

  OrderedSet();
  virtual ~OrderedSet() {}

  virtual int add( const T& val , const int unique=FALSE );
  virtual void add( const OrderedSet<T>&, const int unique=FALSE );
  virtual void remove( T& val );

  int empty() const
                {return (Len == 0);}
  operator int() const
                {return (Len > 0);}
  size_type len() const
                {return Len;}


  T& first( OrderedSetIndex& index, int& status);
  T& next( OrderedSetIndex& index, int& status);

  int index(const T& val);
  int is_member(const T& val)
        {return (index(val) != -1);}
  int is_disjoint(const OrderedSet<T>& set);

  const T & operator[](const int i) const
                {return Data[i];}

  void write(ostream& os) const;
  void read(istream& is);
  void write(PackBuffer& os) const;
  void read(UnPackBuffer& is);

protected:

  size_type Len;
  BasicArray<T> Data;

};

template <class T>
inline UTILIB_API OrderedSet<T>& operator>>(OrderedSet<T>& list, T& val)
{list.remove(val); return list;}

template <class T>
inline UTILIB_API OrderedSet<T>& operator<<(OrderedSet<T>& list, const T& val)
{list.add(val); return list;}

template <class T>
inline UTILIB_API ostream& operator<<(ostream& output, const OrderedSet<T>& set)
{ set.write(output); return(output); }

template <class T>
inline UTILIB_API istream& operator>>(istream& input, OrderedSet<T>& set)
{ set.read(input); return(input); }

template <class T>
inline UTILIB_API PackBuffer& operator<<(PackBuffer& output, const OrderedSet<T>& set)
{ set.write(output); return(output); }

template <class T>
inline UTILIB_API UnPackBuffer& operator>>(UnPackBuffer& input, OrderedSet<T>& set)
{ set.read(input); return(input); }





template <class T>
OrderedSet<T>::OrderedSet()
 : Len(0), Data(1)
{ }


//
// Note: in order to make 'removes' effective, you need to be able to deal with
// 'holes' in the array.  This is messy, and I don't need this capability right
// now!  -- WEH
//
template <class T>
void OrderedSet<T>::remove( T& Value )
{
ErrAbort("OrderedSet<T>::remove -- unimplemented method!");
}


template <class T>
int OrderedSet<T>::add( const T& val, const int add_unique )
{
int ndx = index(val);
if (add_unique && (ndx != -1))
   return ndx;

if (Data.size() == Len)
   Data.resize(Len + max((Data.size() / 10),(size_type)10));

Data[Len] = val;
Len++;
return(Len-1);
}



template <class T>
void OrderedSet<T>::add( const OrderedSet<T>& set, const int add_unique )
{
for (size_type i=0; i<set.Len; i++)
  if (!add_unique || !is_member(set.Data[i]))
     add(set.Data[i]);
}



template <class T>
int OrderedSet<T>::index(const T& val)
{
for (size_type i=0; i<Len; i++)
  if (val == Data[i])
     return i;
return -1;
}


template <class T>
T& OrderedSet<T>::first( OrderedSetIndex& index, int& status)
{
if (Len == 0) {
   status = FALSE;
   return Data[0];
}
index = 1;
status=TRUE;
return Data[0];
}


template <class T>
T& OrderedSet<T>::next( OrderedSetIndex& index, int& status)
{
if (status == FALSE) return Data[0];
if (index >= Len) {
   status = FALSE;
   return Data[0];
   }
return Data[index++];
}

template <class T>
int OrderedSet<T>::is_disjoint(const OrderedSet<T>& set)
{
for (size_type i=0; i<Len; i++)
  for (size_type j=0; j<set.Len; j++)
    if (Data[i] == set.Data[j]) return FALSE;
return TRUE;
}


template <class T>
void OrderedSet<T>::write(ostream& os) const
{
os << "{ ";
if (Len > 0) {
   os << Data[0];
   for (size_type i=1; i<Len; i++)
     os << ", " << Data[i];
   os << " ";
   }
os << "}";
}


template <class T>
void OrderedSet<T>::read(istream& /*is*/)
{
}


template <class T>
void OrderedSet<T>::write(PackBuffer& os) const
{
os << Len;
for (size_type i=0; i<Len; i++)
  os << Data[i];
}


template <class T>
void OrderedSet<T>::read(UnPackBuffer& is)
{
is >> Len;
if (Data.len() <= Len)
   Data.resize(max(1,Len));
for (size_type i=0; i<Len; i++)
  is >> Data[i];
}

#define ForAllElements(index,set,elt_type)\
if (set.len() > 0) {\
int index ## __first=TRUE, index ## __status=TRUE;\
OrderedSetIndex index ## __ndx;\
while (index ## __status == TRUE) {\
  const elt_type& index = (index ## __first == TRUE ? set.first(index ## __ndx, index ## __status) : set.next(index ## __ndx, index ## __status));\
  index ## __first = FALSE;\
  if (index ## __status == FALSE) break;


#endif