Category : OS/2 Files
Archive   : GPPDEV8F.ZIP
Filename : SKIPSET.HP

// This may look like C code, but it is really -*- C++ -*-
/*
Copyright (C) 1991 Free Software Foundation

This file is part of the GNU C++ Library. This library is free
software; you can redistribute it and/or modify it under the terms of
the GNU Library General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your
option) any later version. This library is distributed in the hope
that it will be useful, but WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the GNU Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free Software
Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
*/

/*
* Sets implemented via William Pugh SkipList algorithms.
* CACM, June 1990, p 668-676.
*
*/

#ifndef _SkipSet_h
#ifdef __GNUG__
#pragma interface
#endif
#define _SkipSet_h 1

#include ".Set.h"

#include
#include

class SkipSet;
class RealSkipSetNode;

class SkipSetNode
{
friend class SkipSet;
private:
RealSkipSetNode * * forward;
SkipSetNode(int size);
};

class RealSkipSetNode : public SkipSetNode
{
friend class SkipSet;
private:
item;
RealSkipSetNode( h, int size);
};

typedef RealSkipSetNode* SkipSetNodePtr;

inline SkipSetNode::SkipSetNode(int size)
: forward(new SkipSetNodePtr[size+1])
{
}

inline RealSkipSetNode::RealSkipSetNode( h, int size)
: item(h),
SkipSetNode(size)
{
}

class SkipSet : public Set
{
friend class SkipSetinit;
protected:
SkipSetNode* header;
int level;
int max_levels;
int randoms_left;
long random_bits;

static MLCG* gen;
int random_level(void);


SkipSetNodePtr leftmost(void);
SkipSetNodePtr rightmost(void);
SkipSetNodePtr pred(SkipSetNodePtr t);
SkipSetNodePtr succ(SkipSetNodePtr t);
void _kill(void);

private:
enum { BITS_IN_RANDOM = LONGBITS-1 };
public:
SkipSet(long size=DEFAULT_INITIAL_CAPACITY);
SkipSet(SkipSet& a);
~SkipSet();

Pix add( i);
void del( i);
int contains( i);

void clear(void);

Pix first(void);
void next(Pix& i);
& operator () (Pix i);
Pix seek( i);

Pix last(void);
void prev(Pix& i);

void operator |= (SkipSet& b);
void operator -= (SkipSet& b);
void operator &= (SkipSet& b);

int operator == (SkipSet& b);
int operator != (SkipSet& b);
int operator <= (SkipSet& b);

int OK(void);
};

/*
* A little overkill on the inlines.
*
*/

inline SkipSet::~SkipSet(void)
{
_kill();
delete header;
}

inline int SkipSet::operator != (SkipSet& b)
{
return ! (*this == b);
}

inline SkipSetNodePtr SkipSet::leftmost(void)
{
return header->forward[0];
}

inline SkipSetNodePtr SkipSet::succ(SkipSetNodePtr t)
{
SkipSetNodePtr result = 0;
if (t->forward[0]!=header) result = t->forward[0];
return result;
}

inline Pix SkipSet::first(void)
{
return Pix(leftmost());
}

inline Pix SkipSet::last(void)
{
return Pix(rightmost());
}

inline void SkipSet::next(Pix& i)
{
if (i != 0) i = Pix(succ((SkipSetNodePtr)i));
}

inline void SkipSet::prev(Pix& i)
{
if (i != 0) i = Pix(pred((SkipSetNodePtr)i));
}

inline & SkipSet::operator () (Pix i)
{
if (i == 0) error("null Pix");
return ((SkipSetNodePtr)i)->item;
}


inline int SkipSet::contains( key)
{
return seek(key) != 0;
}

static class SkipSetinit
{
public:
SkipSetinit();
~SkipSetinit();
private:
static int count;
} skipSetinit;

#endif