// list.cc -- C++ implementation of GWG list classes
// written by Bruce J. Bell on April 13, 1996
//
// update history:
//   April 22: complete update -- see list.h for documentation.
//             All template methods are in .h file, leaving only node methods

#include "list.h"


// node methods:

void node::link_next(node &B) {
  node *tmp= next;  // save this->next
  next= B.next; B.next->prev= this;  // link *this and B.next
  B.next= tmp; tmp->prev= &B;  // link B and this->next
}

void node::link_prev(node &B) {
  node *tmp= prev;  // save this->prev
  prev= B.prev; B.prev->next= this;  // link *this and B.prev
  B.prev= tmp; tmp->next= &B;  // link B and this->prev
}

void node::unlink() {
  // this can also be done with link_next or link_prev,

  next->prev= prev; prev->next= next;  // link *prev and *next
  prev=next= this;  // link *this to itself
}

bool node::unlinked() const {
  return (next==this);
}

int node::len() const {
  // count total #of nodes in ring, including *this
  int i=1;
  for(const node* p=this; p!=prev; p=p->next,++i)
    ;
  return i;
}

bool node::find(node &N) const {
  // loop until you find N (by pointer address only...)
  for(const node* p=this; p!=&N; p=p->next)
    if(p==prev)  return false;  // searched ring without finding target
  return true;
}

int node::find_fwd(node &N) const {
  int i=0;
  for(const node* p=this; p!=&N; p=p->next,++i)
    if(p==prev)  return -1;  // searched ring without finding target
  return i;
}

int node::find_back(node &N) const {
  int i=0;
  for(const node* p=this; p!=&N; p=p->prev,++i)
    if(p==next)  return -1;  // searched ring without finding target
  return i;
}

node& node::walk_fwd(int idx) const {
  assert(idx>=0);
  const node* p=this;
  for(int i=0; i<idx; ++i)
    p=p->next;
  return *const_cast<node*>(p); // discards const
}

node& node::walk_back(int idx) const {
  assert(idx>=0);
  const node* p=this;
  for(int i=0; i<idx; ++i)
    p=p->prev;
  return *const_cast<node*>(p); // discards const
}

node& node::index_fwd(int idx) const {
  assert(idx>=0);
  const node* p=this;
  for(int i=0; i<idx; ++i,p=p->next)
    assert(p!=prev); // or else p->next==this
  return *const_cast<node*>(p); // discards const
}

node& node::index_back(int idx) const {
  assert(idx>=0);
  const node* p=this;
  for(int i=0; i<idx; ++i,p=p->prev)
    assert(p!=next); // or else p->prev==this
  return *const_cast<node*>(p); // discards const
}

void node::Dump(ostream &out) const {
  out<<"(node: this="<<this<<" next="<<next<<" prev="<<prev<<")";
}

bool node::Check() const {
  const node *p= this;
  do {
    if(p->next->prev!=p)  return false;
    p=p->next;
  } while( p!=this );
  return true;
}

bool node::Verify(ostream &out) const {
  out<<"(verify node: this=";
  Dump(out);

  if(this->next->prev!=this) {
    out<<" error\n";
    return false;
  } else {
    out<<" OK\n";
  }

  const node *p= next;
  while( p!=this ){
    out<<"next=";
    p->Dump(out);

    if(p->next->prev!=p) {
      out<<" error\n";
      return false;
    } else {
      out<<" OK\n";
    }
    p=p->next;
  }
  out<<"ring verified)\n";
  return true;
}