File contents
/*ident "@(#)Map.h 1.1.2.2" */
/******************************************************************************
*
* C++ Standard Components, Release 3.0.
*
* Copyright (c) 1991, 1992 AT&T and Unix System Laboratories, Inc.
* Copyright (c) 1988, 1989, 1990 AT&T. All Rights Reserved.
*
* THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T and Unix System
* Laboratories, Inc. The copyright notice above does not evidence
* any actual or intended publication of such source code.
*
******************************************************************************/
/*
* Map is a parameterized type class that stores a table
* of keys and associated data objects. This implementation
* is done using AVL trees (see Knuth, The Art of Computer
* Programming, volume 3, p. 451). The helper classes
* Mapnodebase_ATTLC and Mapbase_ATTLC implement the basic
* insertion and deletion operations (with rebalancing of
* the tree after the modification). The lookup operation
* is implemented by Map(S,T)::operator[].
*
* Each node has three pointers: L_ points to the left
* child, R_ points to the right child, and U_ points to
* the parent node. The predecessor_ and successor_ functions
* in the class Mapbase_ATTLC find the "inorder" predecessor
* and successor of a given node.
*
* A Mapiter (Map iterator) is a pointer into the middle of
* a tree. If there are any iterators active in a Map, any
* deletion operations merely mark the node for deletion.
* Later lookup and iterator operations skip over nodes that
* are marked for deletion. The deletion is actually performed
* when the last iterator for the Map is destroyed.
*
* See the tutorial "Associative Arrays in C++" for information
* on how to use the Map class.
*/
#ifndef MAP_H
#define MAP_H
class Mapnodebase_ATTLC {
protected:
// Really want a declaration by association:
// like this L, R, U;
Mapnodebase_ATTLC *L_, *R_, *U_;
char bal;
char remove_mark;
friend class Mapbase_ATTLC;
// Similarly, this should be declared by association too:
// void attach (like this & p, like this dest)
void attach (Mapnodebase_ATTLC*& p, Mapnodebase_ATTLC* dest)
{ p = dest; if (dest) dest->U_ = this; }
Mapnodebase_ATTLC() { L_ = 0; R_ = 0; bal = 0; remove_mark = 0; }
virtual ~Mapnodebase_ATTLC();
};
class Mapbase_ATTLC {
public:
void make_empty();
protected:
// Also should be declared by association.
// like this head_;
Mapnodebase_ATTLC *head_;
int n;
Mapbase_ATTLC() { head_ = 0; n = 0; }
~Mapbase_ATTLC() { make_empty(); }
void remove_deadwood();
void newnode(Mapnodebase_ATTLC *);
void rotL (Mapnodebase_ATTLC*);
void rotR (Mapnodebase_ATTLC*);
void rot_dir (Mapnodebase_ATTLC*, char);
void removenode(Mapnodebase_ATTLC *);
void del_balance(Mapnodebase_ATTLC *);
// Should be declared by association.
Mapnodebase_ATTLC *successor_(Mapnodebase_ATTLC *) const;
Mapnodebase_ATTLC *predecessor_(Mapnodebase_ATTLC *) const;
};
#ifdef __GNUG__
#pragma interface
#endif
template <class S, class T> class Map;
template <class S, class T> class Mapiter;
template <class S, class T>
struct Map_pair {
const S key;
T value;
Map_pair(const S& s) : key(s) { }
};
template <class S, class T>
class Mapnode_ATTLC : public Mapnodebase_ATTLC {
Mapnode_ATTLC<S,T> *L() const { return (Mapnode_ATTLC<S,T> *)L_; }
Mapnode_ATTLC<S,T> *R() const { return (Mapnode_ATTLC<S,T> *)R_; }
Map_pair<S,T> map_data;
Mapnode_ATTLC(const S&, const T&);
#ifdef __GNUG__
~Mapnode_ATTLC() {}
#else
~Mapnode_ATTLC();
#endif
friend class Map<S,T>;
friend class Mapiter<S,T>;
static const S* default_S();
static const T* default_T();
};
template <class S, class T>
class Mapiter {
friend class Map<S,T>;
Map<S,T>* m;
Mapnode_ATTLC<S,T>* p;
Mapiter<S,T>* iter_next;
Mapiter(const Map<S,T>*, Mapnode_ATTLC<S,T>*);
public:
Mapiter(const Map<S,T>&);
~Mapiter();
operator void*() const { return p; }
void remove();
void reset() { this->p = 0; }
const Map<S,T>* the_map() const { return m; }
Mapiter(const Mapiter<S,T>&);
Mapiter<S,T>& operator=(const Mapiter<S,T>&);
Map_pair<S,T>* next() { operator++(); return (p? &(p->map_data) : 0); }
Map_pair<S,T>* prev() { operator--(); return (p? &(p->map_data) : 0); }
Map_pair<S,T>* curr() { return (p? &(p->map_data) : 0); }
// the following functions have been denigrated
S key() const {
return *(p? &p->map_data.key:
(S*)Mapnode_ATTLC<S,T>::default_S());
}
T value() const {
return *(p? &p->map_data.value:
(T*)Mapnode_ATTLC<S,T>::default_T());
}
void setvalue(const T &t) const {
if (p != 0) ((Mapnode_ATTLC<S,T>*)p)->map_data.value = t;
}
Mapiter<S,T>& operator++();
Mapiter<S,T>& operator--();
};
template <class S, class T>
class Map : public Mapbase_ATTLC {
Mapnode_ATTLC<S,T>* head() const {
return (Mapnode_ATTLC<S,T> *)head_;
}
Mapnode_ATTLC<S,T>* successor(Mapnode_ATTLC<S,T>* p) const {
return (Mapnode_ATTLC<S,T> *)successor_(p);
}
Mapnode_ATTLC<S,T>* predecessor(Mapnode_ATTLC<S,T>* p) const {
return (Mapnode_ATTLC<S,T> *)predecessor_(p);
}
T def;
int mi_count;
char remove_flag;
Mapiter<S,T>* iter_head;
T& newnode(Mapnodebase_ATTLC*&, const S&, Mapnode_ATTLC<S,T>*);
friend class Mapiter<S,T>;
public:
Map();
Map(const T&);
Map(const Map<S,T>&);
~Map();
Map<S,T>& operator= (const Map<S,T>&);
// int operator== (const Map<S,T>&);
T& operator[] (const S&);
const T& operator[] (const S&) const;
int remove(const S&);
int size() const { return n; }
Mapiter<S,T> element (const S&) const;
Mapiter<S,T> first() const;
Mapiter<S,T> last() const;
Mapiter<S,T> lub(const S&) const;
Mapiter<S,T> glb(const S&) const;
};
class ostream;
class istream;
template <class S, class T>
ostream &operator<<(ostream& os, const Map<S,T>& m);
#if defined(__GNUG__)
#include "Map.c"
#else
#if (defined(__edg_att_40) || defined(__GNUG__)) && !defined(__IMPLICIT_INCLUDE)
#include <Map.c>
#endif
#endif
#endif