public Enumeration incidentEdges() {
SequenceEnumeration S = new SequenceEnumeration();
Position p = adjacencyList.first();

for (int i = 0; i < adjacencyList.size();i++) {
S.insert(p.element());
p = adjacencyList.after(p);
}

return S;
}

public void addIncidentEdge(Edge e) {
adjacencyList.insertLast(e);

degree++;
}
public void draw(Graphics g) {
g.setColor(Color.orange);
g.fill3DRect (x-9,y-9,17,17,true);
g.setColor(Color.black);
g.draw3DRect(x-10,y-10,18,18,true);
g.setColor(Color.black );
g.drawString(element.toString(), x-5, y+5);
}
}

//-------------------

public void colorDFS(Vertex v) {
markedVerts = new Hashtable();
markedEdges = new Hashtable();
DFS(v);
}
private void DFS(Vertex v) {
mark(v);
Enumeration inEdges = incidentEdges(v);
while(inEdges.hasMoreElements()){
Edge nextEdge = (Edge)inEdges.nextElement();
if (!isMarked(nextEdge)) {
mark(nextEdge);
Vertex w = opposite(v, nextEdge);
if (!isMarked(w)) { // color tree edge
nextEdge.setColor(Color.red);
DFS(w);
} else // color back edge
nextEdge.setColor(Color.blue);
}
}
}
public void colorBFS(Vertex v) {
markedVerts = new Hashtable();
markedEdges = new Hashtable();

Enumeration inEdges;
Vertex temp;
Sequence tempseq = new Sequence();
tempseq.insertLast(v);

while (!tempseq.isEmpty()) {
temp = ((Vertex)tempseq.first().element());
tempseq.remove(tempseq.first());
inEdges = incidentEdges(temp);

while (inEdges.hasMoreElements()) {
Edge nextEdge = (Edge)inEdges.nextElement();
if (!isMarked(nextEdge)) {
mark(nextEdge);
Vertex w = opposite(temp,nextEdge);
if (!isMarked(w)) {
mark(w);
tempseq.insertLast(w);
nextEdge.setColor(Color.red);
}
else
nextEdge.setColor(Color.blue);

}
}
}
}

public void draw(Graphics g) {
// draw edges
Position current = E.first();
while(current != null) {
Edge edge = (Edge) current.element();
edge.draw(g);
current = E.after(current);
}
// draw vertices
current = V.first();
while(current != null) {
Vertex vertex = (Vertex) current.element();
vertex.draw(g);
current = V.after(current);
}
}
}

//------------------------------

public class RestructurableNodeBinaryTree extends LinkedBinaryTree{

public Position restructure(Position xPos){
Position yPos = parent(xPos);
Position zPos = parent(yPos);
Stack xyzStack = new Stack();
Stack TStack = new Stack();

BTNode a,b,c,T0,T1,T2,T3;

traverse(xyzStack,TStack,zPos,xPos,yPos,zPos);

c = (BTNode)xyzStack.pop(); b = (BTNode)xyzStack.pop(); a = (BTNode)xyzStack.pop();
T3 = (BTNode)TStack.pop(); T2 = (BTNode)TStack.pop();
T1 = (BTNode)TStack.pop(); T0 = (BTNode)TStack.pop();
BTNode x,y,z;
x = (BTNode)xPos; y = (BTNode)yPos; z = (BTNode)zPos;

if (!isRoot(zPos)){
if (zPos == leftChild(parent(zPos))){
((BTNode)parent(zPos)).setLeft(b);
b.setParent((BTNode)parent(zPos));
}
else{
((BTNode)parent(zPos)).setRight(b);
b.setParent((BTNode)parent(zPos));
}
}
else{
super.root = b;
b.setParent(null);
}




b.setLeft(a); a.setParent(b);
a.setLeft(T0); T0.setParent(a);
a.setRight(T1); T1.setParent(a);

b.setRight(c); c.setParent(b);
c.setLeft(T2); T2.setParent(c);
c.setRight(T3); T3.setParent(c);
return b;
}

protected void traverse(Stack xyzStack, Stack TStack, Position current,Position x, Position y, Position z){
if (current != x && current != y && current != z){
TStack.push(current);
}
else{
traverse(xyzStack,TStack,leftChild(current),x,y,z);
xyzStack.push(current);
traverse(xyzStack,TStack,rightChild(current),x,y,z);
}
}


}

//------------------------------------------------------------------

private void bubbleDownHeap(Item[] A,int r, int n) {Item rItem = A[r];
Object kr = rItem.key();
int s = 2*r + 1;
while(s < n) {
Object ks = A[s].key();
int t = s + 1;
if(t < n) {
Object kt = A[t].key();
if(comparator.isGreaterThan(ks,kt)) {
s = t; ks = kt;
}
}
if(comparator.isLessThanOrEqualTo(kr,ks)) break;
A[r] = A[s];
r = s; s = 2*r + 1;
}
A[r] = rItem;
}
//------------------------------------------------------------------

//------------------------------------------------------------------
private void clone(Item[] A, BinaryTree T,int i, Position v,int n) {
if (i < n) {
T.expandExternal(v);
T.replace(v,A[i]);
if (i == n-1) last = v;
clone(A,T,i*2+1,T.leftChild(v),n);
clone(A,T,i*2+2,T.rightChild(v),n);
}
}
//------------------------------------------------------------------

//-------------------------------------------------------------------
private boolean isRightChild(Position p) {
return T.rightChild(T.parent(p)) == p;
}
//-------------------------------------------------------------------

//-------------------------------------------------------------------
private Position newLastPosition(Position z) {
while (!T.isRoot(z) && !isRightChild(z)){
z = T.parent(z);
}
if (!T.isRoot(z)) {
z = T.leftChild(T.parent(z));
}
while (T.isInternal(z)) {
z = T.rightChild(z);
}
return T.parent(z);
}
//-------------------------------------------------------------------

//-----------------------------------------------------------------------

private boolean isRightChild(Position p) {
return rightChild(parent(p)) == p;
}
//-------------------------------------------------------------------

public void removeAboveExternal(Position w) {
BTNode v = (BTNode)parent(w);
if (!isRoot(v)){
BTNode u = (BTNode)parent(v);
if (isRightChild(v)){
u.setRight((BTNode)sibling(w));
}
else{ u.setLeft((BTNode)sibling(w));
}
((BTNode)sibling(w)).setParent(u);
}
else{
v.setLeft(null);
v.setRight(null);
}
}
//-----------------------------------------------------------------------

//-----------------------------------------------------------------------
public Position sibling(Position v) {
Position p = parent(v);
Position l = leftChild(p);
Position r = rightChild(p);
if (l == v) return r;
else return l;
}
//-----------------------------------------------------------------------