Category : OS/2 Files
Archive   : GPPDEV8F.ZIP
Filename : SKIPMAP.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.
*/

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

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

#include "..Map.h"

#include
#include

class SkipMap;
class RealSkipMapNode;

class SkipMapNode
{
friend class SkipMap;
private:
RealSkipMapNode * * forward;
protected:
SkipMapNode(int size);
};

class RealSkipMapNode : public SkipMapNode
{
friend class SkipMap;
private:
item;
cont;
RealSkipMapNode( h, i, int size);
};

typedef RealSkipMapNode* SkipMapNodePtr;

inline SkipMapNode::SkipMapNode(int size)
: forward(new SkipMapNodePtr[size+1])
{
}

inline RealSkipMapNode::RealSkipMapNode( h, i, int size)
: item(h), cont(i),
SkipMapNode(size)
{
}

class SkipMap : public Map
{
friend class SkipMapinit;
protected:
SkipMapNode* header;
int level;
int max_levels;

int randoms_left;
long random_bits;

static MLCG* gen;
int random_level(void);

SkipMapNodePtr leftmost();
SkipMapNodePtr rightmost();
SkipMapNodePtr pred(SkipMapNodePtr t);
SkipMapNodePtr succ(SkipMapNodePtr t);
void _kill();
private:
enum { BITS_IN_RANDOM = LONGBITS-1 };

public:
SkipMap( dflt, long size=DEFAULT_INITIAL_CAPACITY);
SkipMap(SkipMap& a);
~SkipMap();

& operator [] ( key);

void del( key);

Pix first();
void next(Pix& i);
& key(Pix i);
& contents(Pix i);

Pix seek( key);
int contains( key);
void clear();

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

int OK();
};

inline SkipMap::~SkipMap()
{
_kill();
delete header;
}

inline SkipMapNodePtr SkipMap::leftmost()
{
return header->forward[0]==header ? 0 : header->forward[0];
}

inline Pix SkipMap::first()
{
return Pix(leftmost());
}

inline Pix SkipMap::last()
{
return Pix(rightmost());
}

inline SkipMapNodePtr SkipMap::succ(SkipMapNodePtr t)
{
return t->forward[0]==header ? 0 : t->forward[0];
}

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

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

inline & SkipMap::key (Pix i)
{
if (i == 0) error("null Pix");
return ((SkipMapNodePtr)i)->item;
}

inline & SkipMap::contents (Pix i)
{
if (i == 0) error("null Pix");
return ((SkipMapNodePtr)i)->cont;
}

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

static class SkipMapinit
{
public:
SkipMapinit();
~SkipMapinit();
private:
static int count;
} skipMapinit;

#endif