/*ident	"@(#)Map.c	1.1.2.3" */
/******************************************************************************
*
* 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.
*
******************************************************************************/

#ifndef _MAP_C_
#define _MAP_C_

template <class S, class T>
Mapnode_ATTLC<S,T>::~Mapnode_ATTLC()
{
}

template <class S, class T>
Map<S,T>::~Map()
{
	Mapiter<S,T>* p = iter_head;
	while (p) {
		p->m = 0;
		p = p->iter_next;
	}
}

template <class S, class T>
Mapiter<S,T>::Mapiter (const Map<S,T>* map, Mapnode_ATTLC<S,T>* n): p(n)
{
	m = (Map<S,T>*)map;
	m->mi_count++;
	iter_next = m->iter_head;
	m->iter_head = this;
}

template <class S, class T>
Mapiter<S,T>::Mapiter (const Map<S,T>& map): p(0)
{
	m = (Map<S,T>*)(&map);
	m->mi_count++;
	iter_next = m->iter_head;
	m->iter_head = this;
}

template <class S, class T>
Mapiter<S,T>::~Mapiter ()
{
	if (m==0 || m->iter_head == 0) return;
	if (--m->mi_count == 0 && m->remove_flag) {
		m->remove_deadwood();
		m->remove_flag = 0;
	}
	if (this == m->iter_head) {
		m->iter_head = iter_next;
	} else {
		Mapiter<S,T>* _p = m->iter_head;
		while (_p->iter_next!=this) {
			_p = _p->iter_next;
		}
		_p->iter_next = iter_next;
	}
}

template <class S, class T>
Mapnode_ATTLC<S,T>::Mapnode_ATTLC(const S& xs, const T& xt): map_data (xs)
{
	map_data.value = xt;
}

template <class S, class T>
Map<S,T>::Map() : def (*Mapnode_ATTLC<S,T>::default_T())
{
	mi_count = 0; 
	remove_flag = 0; 
	iter_head = 0;
}

template <class S, class T>
Map<S,T>::Map(const T& d) : def (d)
{
	mi_count = 0; 
	remove_flag = 0; 
	iter_head = 0;
}

template <class S, class T>
Map<S,T>&
Map<S,T>::operator= (const Map<S,T>& m)
{
	if (this != &m) {
		make_empty();
		for (Mapiter<S,T> p (m); ++p; ) {
			// S s = p.key();	/* sidestep a cfront bug */
			// (*this) [s] = p.value();
			(*this) [p.key()] = p.value();
		}
//		iter_head=0;
//		mi_count = 0;
		/* march through the iterator list, setting each to vacuous */
		for (Mapiter<S,T> *ip = iter_head; ip; ip = ip->iter_next) {
			/* ip->m = this; */ /* unnecessary */
			ip->p = 0;
		}
   		remove_flag = 0;
	}
	return *this;
}
/**
template <class S, class T>
int
Map<S,T>::operator== (const Map<S,T>& m)
{
	if (m.size() != n) {
		cout << "aaa\n";
		return 0;
	}

	if (this != &m) {
		Mapiter<S,T> q(*this);
		Mapiter<S,T> p(m);
		while (++p) {
			if (++q == 0) 
			    return 0;

			if (q.key() != p.key()) {
			    cout << "bbb:q=" << q.key() << " p=" << p.key() << "\n";
			    return 0;
			}
			if (q.value() != p.value()) {
			    cout << "bbb:q=" << q.value().value() << " p=" << p.value().value() << "\n";
			    return 0;
			}
		}
		if (++q == 0) 
			return 1;
		
		cout << "ccc:" << (void*)p << " " << (void*)q << "\n";
	  	return 0;
	}
	cout << "ddd\n";
	return 1;
}
**/
template <class S, class T>
Map<S,T>::Map (const Map<S,T>& m): def (m.def), mi_count(0), remove_flag(0), iter_head(0)
{
	operator= (m);
}

template <class S, class T>
T&
Map<S,T>::newnode (Mapnodebase_ATTLC*& ptr, const S& s, Mapnode_ATTLC<S,T>* parent)
{
	Mapnode_ATTLC<S,T>* p = new Mapnode_ATTLC<S,T> (s, def);
	ptr = p;
	T& retval = p->map_data.value;

	p->U_ = parent;
	n++;

	Mapbase_ATTLC::newnode(ptr);
	
	return retval;
}

template <class S, class T>
T&
Map<S,T>::operator[] (const S& s)
{
	if (head()) {
		Mapnode_ATTLC<S,T>* t = head();
		for(;;) {
			if (s < t->map_data.key) {
				if (t->L())
					t = t->L();
				else
					return newnode (t->L_, s, t);
			} else if (t->map_data.key < s) {
				if (t->R())
					t = t->R();
				else
					return newnode (t->R_, s, t);
			} else
				break;
		}
		if (t->remove_mark != 0) {
			t->remove_mark = 0;
			t->map_data.value = def;
			n++;
		}
		return t->map_data.value;
	} else
		return newnode (head_, s, 0);
}

template <class S, class T>
const T&
Map<S,T>::operator[] (const S& s) const
{
	return (const T&)(((Map<S,T>*)this)->operator[](s));
}

template <class S, class T>
Mapiter<S,T>
Map<S,T>::element (const S& s) const
{
	Mapnode_ATTLC<S,T>* t = head();
	while (t) {
		if (s < t->map_data.key)
			t = t->L();
		else if (t->map_data.key < s)
			t = t->R();
		else
			break;
	}
	if (t && t->remove_mark == 0)
		return Mapiter<S,T> (this, t);
	else
		return Mapiter<S,T> (this, 0);
}

template <class S, class T>
Mapiter<S,T>
Map<S,T>::lub (const S& s) const
{
	Mapnode_ATTLC<S,T>* t = head();

	while(t){
		if(s < t->map_data.key){
			if(t->L())
				t = t->L();
			else
				break;
		}
		else if(t->map_data.key < s){
			if(t->R())
				t = t->R();
			else {
				t = successor(t);
				break;
			}
		}
		else
			break;
	}
	while (t && t->remove_mark){
		t = successor(t);
	}
	if(t)
		return Mapiter<S,T> (this, t);
	else
		return Mapiter<S,T> (this, 0);
}

template <class S, class T>
Mapiter<S,T>
Map<S,T>::glb (const S& s) const
{
	Mapnode_ATTLC<S,T>* t = head();

	while(t){
		if(t->map_data.key < s){
			if(t->R())
				t = t->R();
			else
				break;
		}
		else if (s < t->map_data.key){
			if(t->L())
				t = t->L();
			else {
				t = predecessor(t);
				break;
			}
		}
		else
			break;
	}
	while (t && t->remove_mark){
		t = predecessor(t);
	}
	if(t)
		return Mapiter<S,T> (this, t);
	else
		return Mapiter<S,T> (this, 0);
}

template <class S, class T>
int
Map<S,T>::remove(const S& s)
{
	Mapnode_ATTLC<S,T>* t = head();
	while (t) {
		if (s < t->map_data.key)
			t = t->L();
		else if (t->map_data.key < s)
			t = t->R();
		else break;
	}
	if (t) {
		if (mi_count > 0) {
			remove_flag = 1;
			if (!t->remove_mark) {
				t->remove_mark = 1;
				n--;
			}
			return (1);
		}
		else {
			removenode(t);
			delete t;
			n--;
			return (1);
		}
	}
	else {
		return (0);
	}
}

template <class S, class T>
Mapiter<S,T> Map<S,T>::first() const {
	return ++Mapiter<S,T> (*this);
}
 
template <class S, class T>
Mapiter<S,T> Map<S,T>::last() const {
	return --Mapiter<S,T> (*this);
}

template <class S, class T>
void
Mapiter<S,T>::remove()
{
	if (p) {
		m->remove_flag = 1;
		p->remove_mark = 1;
		m->n--;
	}
}

template <class S, class T>
Mapiter<S,T>&
Mapiter<S,T>::operator++()
{
	while (1) {
		p = m->successor(p);
		if (p == 0 || p->remove_mark == 0) {
			return (*this);
		}
	}
}

template <class S, class T>
Mapiter<S,T>&
Mapiter<S,T>::operator--()
{
	while (1) {
		p = m->predecessor(p);
		if (p == 0 || p->remove_mark == 0) {
			return (*this);
		}
	}
}

template <class S, class T>
Mapiter<S,T>::Mapiter(const Mapiter<S,T>& mi) : m(mi.m),p(mi.p)
{
	m->mi_count++;
	iter_next = m->iter_head;
	m->iter_head = this;
}

template <class S, class T>
Mapiter<S,T>&
Mapiter<S,T>::operator=(const Mapiter<S,T>& mi)
{
	if (this == m->iter_head) {
		m->iter_head = iter_next;
	} else {
		Mapiter<S,T>* _p = m->iter_head;
		while (_p && _p->iter_next!=this) {
			_p = _p->iter_next;
		}
		if (_p) {
			_p->iter_next = iter_next;
		}
	}
	((Map<S,T>*)m)->mi_count--;
	((Map<S,T>*)mi.m)->mi_count++;
	m = (Map<S,T>*)(mi.m);
	p = mi.p;
	iter_next = m->iter_head;
	m->iter_head = this;
	return *this;
}

template <class S, class T>
const S*
Mapnode_ATTLC<S,T>::default_S()
{
	static S S_default_item;
	return (&S_default_item);
}

template <class S, class T>
const T*
Mapnode_ATTLC<S,T>::default_T()
{
	static T T_default_item;
	return (&T_default_item);
}

template <class S, class T>
ostream &operator<<(ostream& os, const Map<S,T>& m) {
	Mapiter<S,T> mi(m);
	os << '{';
	while (++mi) {
		os << "[ " << mi.curr()->key << ' '
		   << mi.curr()->value << " ]";
	}
	os << '}';
	return os;
}

#endif