// file dlist.cpp
// methods for class Dlist

#include "dlist.h"
#include <stdlib.h>
#include <assert.h>
#include <iostream.h>

Dlist::Dlist()
{
	leftend = NULL;
	rightend = NULL;
}

Dnode *Dlist::firstnode()
{
	return leftend;
}

Dnode *Dlist::lastnode()
{
	return rightend;
}

void Dlist::insertfirst(Type x)
{
	Dnode *p;
	p = new Dnode (x);
	assert(p);
	p->setright(leftend);
	if (leftend)
		leftend->setleft(p);
	else
		rightend = p;
	leftend = p;

}

void Dlist::insertlast(Type x)
{
	Dnode *p;
	p = new Dnode (x);
	assert(p);
	p->setleft(rightend);
	if (rightend)
		rightend->setright(p);
	else
		leftend = p;
	rightend = p;
}

void Dlist::insertleft(Type x, Dnode *p)
{
	Dnode *q, *r;

	assert (p);
	q = new Dnode(x);
	assert (q);
	r = p->getleft();
	p->setleft(q);
	q->setleft(r);
	q->setright(p);
	if (r)
		r->setright(q);
	else
		leftend = q;
}

void Dlist::insertright(Type x, Dnode *p)
{
	Dnode *q, *r;

	assert (p);
	q = new Dnode(x);
	assert (q);
	r = p->getright();
	p->setright(q);
	q->setright(r);
	q->setleft(p);
	if (r)
		r->setleft(q);
	else
		rightend = q;
}

Type Dlist::removefirst()
{
	Dnode *p;
	Type x;

	assert(!isempty());

	p = leftend;
	x = p->getinfo();
	leftend = p->getright();
	if (leftend)
		leftend->setleft(NULL);
	else
		rightend = NULL;

	delete p;
	return x;
}

Type Dlist::removelast()
{
	Dnode *p;
	Type x;

	assert(!isempty());

	p = rightend;
	x = p->getinfo();
	rightend = p->getleft();
	if (rightend)
		rightend->setright(NULL);
	else
		leftend = NULL;

	delete p;
	return x;
}

Type Dlist::removeleft(Dnode *p)
{
	Type x;
	Dnode *q, *r;

	assert(p);
	q = p->getleft();
	assert(q);
	r = q->getleft();
	x = q->getinfo();
	p->setleft(r);
	if (r)
		r->setright(p);
	else
		leftend = p;

	delete q;
	return x;
}

Type Dlist::removeright(Dnode *p)
{
	Type x;
	Dnode *q, *r;

	assert(p);
	q = p->getright();
	assert(q);
	r = q->getright();
	x = q->getinfo();
	p->setright(r);
	if (r)
		r->setleft(p);
	else
		rightend = p;

	delete q;
	return x;
}

Type Dlist::remove(Dnode *p)
{
	Dnode *q,*r;
	Type x;

	assert(p);
	x = p->getinfo();

	q = p->getleft();
	r = p->getright();

	if (q)
		q->setright(r);
	else
		leftend = r;

	if (r)
		r->setleft(q);
	else
		rightend = q;

	delete (p);
	return x;
}

int Dlist::isempty()
{
	return (leftend == NULL);
}


void Dlist::print()
{
	Dnode *p;

	p = leftend;
	while (p){
		cout << p-> getinfo()<<' ';
		p = p->getright();
	}
	cout<<endl;
}

Dlist::~Dlist()
{
	Dnode *p,*q;

	p = leftend;
	while (p) {
		q = p;
		p = p->getright();
		delete q;
	}
}

int Dlist::find(Type x)
{
	Dnode *p;

	p=leftend;
	while (p) {
		if (p->getinfo()==x)
			return 1;
		p = p->getright();
	}
	return 0;
}