chain.cpp University of British Columbia CPSC 221

#include "chain.h"
#include "chain_given.cpp"

// PA1 functions

/**
* Destroys the current Chain. This function should ensure that
* memory does not leak on destruction of a chain.
*/
Chain::~Chain(){
/*your code here*////////////////////
length_ = 0;
clear();
}

/**
* Inserts a new node at the back of the List.
* This function **SHOULD** create a new ListNode.
*
* @param ndata The data to be inserted.
*/
void Chain::insertBack(const Block & ndata){
/*your code here*/
if (length_ == 0) {
width_ = ndata.width();
height_ = ndata.height();
}
else if (ndata.width() != width_ || ndata.height() != height_) {
return; //If dimensions of block to insert do not match, return and do
nothing
}

Node* new_node = new Node(ndata);
Node* last_node = tail_->prev;
//Insert new node:
last_node->next = new_node;
new_node->prev = last_node;
tail_->prev = new_node;
new_node->next = tail_;
length_++; //Increment chain length
}

/**
* Modifies the Chain by moving a contiguous subset of len Nodes
* dist nodes toward the end of the chain beginning from startPos
* (maintaining the sentinel at the end). Their order is
* not changed in the move. You may assume that the startPos and
* len parameters are kind: startPos + len -1 <= length. If there
* are not enough nodes to shift by dist, just shift as many as
* possible.
*/
void Chain::moveBack(int startPos, int len, int dist){
/*your code here*/
if(startPos + len > length_||dist == 0||length_==0){
return;} else if(startPos + dist > length_){
return;}
if (startPos == 0) {
startPos = 1;
len--;
}

Node * before = walk(head_,startPos-1); // node before startPos
Node * first = walk(head_, startPos); // node at startPos
Node * end = walk(first,len-1); // last node of subset

This study source was downloaded by 100000850872992 from CourseHero.com on 02-14-2023 22:10:52 GMT -06:00


https://www.coursehero.com/file/34809024/chaincpp/

, //if not enough nodes to shift by dist, update new end
while(walk(end,dist)->next==NULL){
end=end->prev;
}
Node * after = walk(end,1); // node after last node of subset
Node * newbefore = walk(end,dist);
Node * newafter = walk(end,dist+1);

before->next = after;
after->prev = before;
newbefore ->next= first;
first->prev= newbefore;
end->next= newafter;
newafter->prev=end;


}


/**
* Rolls the current Chain by k nodes: removes the last
* k nodes from the Chain and attaches them, in order, at
* the start of the chain (maintaining the sentinel at the front).
*/
void Chain::roll(int k){
/*your code here*/
if(k==0 || k> length_){return;} //include the guards?
else{
Node * subhead = walk(head_, length_-k+1);
Node * subtail = walk(head_, length_);
Node * front1 = walk(head_, 1);
subhead->prev->next=tail_;
tail_->prev = subhead->prev;
head_->next = subhead;
subhead->prev = head_;
front1->prev = subtail;
subtail->next= front1;
}

}

/**
* Modifies the current chain by reversing the subchain
* between pos1 and pos2, inclusive. The positions are
* 1-based. You may assume that pos1 and pos2 are valid
* locations in the Chain, and that pos2 >= pos1.
*/
void Chain::reverseSub(int pos1, int pos2){
/*your code here */
if(pos1==pos2){return;}
Node* front = walk(head_,pos1);
Node* before = front->prev;
Node* end = walk(head_,pos2);
Node* after = end-> next;
Node* curr= end;
Node* pcurr = before;

front->next = after;
after->prev=front;

while ( curr!= before) {
Node* temp = curr->prev;
pcurr->next=curr;
curr->prev=pcurr;

This study source was downloaded by 100000850872992 from CourseHero.com on 02-14-2023 22:10:52 GMT -06:00


https://www.coursehero.com/file/34809024/chaincpp/