[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Splice Function

Posted on 2011-04-20
16
Medium Priority
?
653 Views
Last Modified: 2012-05-11
Can someone help me write a splice function. Splice moves the elements in [first, last) from lst to *this, inserting them before position. All iterators remain valid, including iterators that point to elements of lst.

For example, if *this list contains {aa, bb, cc} and 'position' is pointing at bb, and the parameter list 'lst' contains {xx, yy, zz} and 'first' is pointing at yy and 'last' is pointing at the end of lst (i.e., after zz), the call to this method should produce {aa, yy, zz, bb, cc} for *this list, and {xx} for 'lst'.

This is what I have so far but I don't know what to do next.
//slist1.splice(it, slist2, it2, slist2.end());
	void splice(iterator position, List & lst, iterator first, iterator last)
	{
		Node* ptr = position.current;
		Node* ptrFirst = first.current; //new
		Node* ptrLast = last.current; //new
		Node* lstHead = lst.head;
		Node* lstTail = lst.tail;

		ptr->prev->next = ptrFirst->prev->next;
		ptrFirst->prev = ptr->prev;

		ptrLast->prev->next = ptrFirst->next;
		ptrFirst = ptrLast->next;

		ptrLast->prev->next = ptr;
		ptr->prev = ptrLast->prev;
		
		lstHead->next = lstTail;
		lstTail->prev = lstHead;

		theSize += lst.size();
		lst.theSize = lst.size();
	}

Open in new window

0
Comment
Question by:villmund
  • 10
  • 5
16 Comments
 
LVL 35

Expert Comment

by:sarabande
ID: 35435113
principally before do any setting you should check that the iterators were valid (current must not be NULL and first.current, last.current within range list.head and lst.tail.

i would assume you want to make copies of the nodes from lst and not use the original nodes. otherwise you never could delete/free the nodes which are used in two lists.

what do you expect from the expression  'ptrFirst->prev->next' when it is at the right side of an assignment? isn't it easier to simply use 'ptrFirst' instead?

Sara
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35437770
Could you provide your definition of iterator and any other relevant definitions related to iterator. In your usage, could you explain how current gets set (and modified).

I take it from your code snippet that your List is a circular list.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35437815
If the lst.tail is part of the lst first..last range, then you appear to be missing a boundary condition where you have to define lst.tail to be the new tail of lst. That would be (approximately) ptrFirst->prev (a guess).

Of course, I'm making assumptions which may not be correct since you haven't posted the List class.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 32

Expert Comment

by:phoffric
ID: 35438031
Consider this example: 'position' is still pointing at bb, and 'first' is still pointing at yy; but now, suppose 'last' is pointing at zz. Then, the call to this method should produce {aa, yy, bb, cc} for *this list, and {xx, zz} for 'lst'.

But, you are not setting the xx node to point to the zz node.

====

I agree with first post:
     ptr->prev->next = ptrFirst;  // ptrFirst->prev->next;
Just using ptrFirst seems to make more sense since it appears that
ptrFirst and ptrFirst->prev->next are both pointing to the same node.

But that is just a nicer way of doing things.

===
0
 

Author Comment

by:villmund
ID: 35443852
This is the code I as given. I changed a few things in the splice function with the four parameters. It prints out the list in the right order but doesn't update the list size and there is an error at the end of run time.
#ifndef WEISSLIST_H
#define WEISSLIST_H

/*============================================================
 * Template class List -- mimics STL list
 *
 * Doubly-linked list with head and tail pointers and dummy nodes.
 * The type name 'Object' is a place holder symbol for the data type
 * which instantiates the element type of the linked list.
 *===========================================================*/
template <typename Object>
class List
{
private:
  /*-------------------------------------------------------
   * Class Node (as a nested class)
   * ------------------------------
   * It is in the private section of the List, so only the members
   * in List can use 'Node' as a data type.
   * However the members in Node are public (because struct), so
   * List can access members in a Node object freely.
   *------------------------------------------------------*/
  struct Node
  {
    Object data;
    Node *prev, *next;

    Node( const Object & d = Object( ), Node *p = NULL, Node *n = NULL )
      : data( d ), prev( p ), next( n ) { }
  };
  //--- end struct Node

public:
  /*-------------------------------------------------------
   * Class const_iterator (as a nested class)
   * ----------------------------------------
   * The const version of the iterator for List.
   * It is in the public section of the List, so anyone outside e.g.
   * application can use this data type, as: List<T>::const_iterator
   * It has only one data member 'current', which points to a Node in
   * a List.  Several overloaded operators: *, ++, --, == and !=.
   * It has the enclosing List<T> as a friend class -- so List can access
   * private members of this class.
   *------------------------------------------------------*/
  class const_iterator
  {
  public:
    const_iterator( ) : current( NULL ) { }

    // Overloaded operator* -- for dereferencing
    const Object & operator* ( ) const { return retrieve( ); }

    // Overloaded pre-increment operator++
    const_iterator & operator++ ( )
    {
      current = current->next;
      return *this;
    }

    // Overloaded post-increment operator++
    const_iterator operator++ ( int )
    {
      const_iterator old = *this;
      ++( *this );
      return old;
    }

    // Overloaded pre-decrement operator--
    const_iterator & operator-- ( )
    {
      current = current->prev;
      return *this;
    }

    // Overloaded post-decrement operator--
    const_iterator operator-- ( int )
    {
      const_iterator old = *this;
      --( *this );
      return old;
    }

    bool operator== ( const const_iterator & rhs ) const
      { return current == rhs.current; }
    bool operator!= ( const const_iterator & rhs ) const
      { return !( *this == rhs ); }

  protected:
    Node *current;

    Object & retrieve( ) const { return current->data; }
    const_iterator( Node *p ) : current( p ) { }

    friend class List<Object>;
  };
  //--- end class const_iterator

  /*-------------------------------------------------------
   * Class iterator (as a nested class)
   * ----------------------------------
   * The non-const version of the iterator for List.
   * It is implemented as a derived class from const_iterator only so that
   * some members don't have to be duplicated from const_iterator.
   * Most functions are same as those in const_iterator, except
   * const_iterator is changed to iterator, and some 'const' are removed.
   *------------------------------------------------------*/
  class iterator : public const_iterator
  {
  public:
    iterator( ) { }
    Object & operator* ( ) { return retrieve( ); }
    const Object & operator* ( ) const { return const_iterator::operator*( ); }

    iterator & operator++ ( )
    {
      current = current->next;
      return *this;
    }

    iterator operator++ ( int )
    {
      iterator old = *this;
      ++( *this );
      return old;
    }

    iterator & operator-- ( )
    {
      current = current->prev;
      return *this;
    }

    iterator operator-- ( int )
    {
      iterator old = *this;
      --( *this );
      return old;
    }

  protected:
    iterator( Node *p ) : const_iterator( p ) { }
    friend class List<Object>;
  };
  //--- end class iterator

/*========================
 * now back to class List
 *=======================*/
public:
  List();
  List(const List & rhs);
  ~List();
  const List & operator=(const List & rhs);

  iterator begin() { return iterator(head->next); }
  const_iterator begin() const { return const_iterator(head->next); }
  iterator end() { return iterator(tail); }
  const_iterator end() const { return const_iterator(tail); }

  //
  // Additional functions which return an iterator to the (dummy) tail and head nodes
  //
  iterator rbegin() { return iterator(tail->prev); }
  const_iterator rbegin() const { return const_iterator(tail->prev); }
  iterator rend() { return iterator(head); }
  const_iterator rend() const { return const_iterator(head); }

  int size() const { return theSize; }
  bool empty() const { return size() == 0; }

  void clear()
  {
    while (!empty())
        pop_front();
  }

  Object & front( ) { return *begin( ); }
  const Object & front( ) const { return *begin( ); }
  Object & back( ) { return *--end( ); }
  const Object & back( ) const { return *--end( ); }

  void push_front( const Object & x ) { insert( begin( ), x ); }
  void push_back( const Object & x ) { insert( end( ), x ); }

  void pop_front( ) { erase( begin( ) ); }
  void pop_back( ) { erase( --end( ) ); }

  // Insert x before itr.
  iterator insert( iterator itr, const Object & x )
  {
    Node *p = itr.current;
    theSize++;
    return iterator( p->prev = p->prev->next = new Node( x, p->prev, p ) );
  }

  // Erase item/node at itr.
  iterator erase( iterator itr )
  {
    Node *p = itr.current;
    iterator retVal( p->next );
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    theSize--;

    return retVal;
  }

  iterator erase( iterator from, iterator to )
  {
    for( iterator itr = from; itr != to; )
      itr = erase( itr );

    return to;
  }

  //---------------------------------------------------------
  // Some additions from the class exercises
  //---------------------------------------------------------
  void splice(iterator position, List & lst)
  {
    Node* ptr = position.current;
    Node* lstHead = lst.head;
    Node* lstTail = lst.tail;

    ptr->prev->next = lstHead->next;
    lstHead->next->prev = ptr->prev;

    lstTail->prev->next = ptr;
    ptr->prev = lstTail->prev;

    lstHead->next = lstTail;
    lstTail->prev = lstHead;

    theSize += lst.theSize;
    lst.theSize = 0;
  }

  void remove(const Object& val)
  {
    iterator it = begin();
    while (it != end()) {
      if (*it == val)
        it = erase(it); // it is updated to the next element (thus no ++ needed)
      else
        it++;
    }
  }
  //********************************************************
  
	//slist1.splice(it, slist2, it2, slist2.end());
	void splice(iterator position, List & lst, iterator first, iterator last)
	{
		
		Node* ptr = position.current;
		Node* ptrFirst = first.current;
		Node* ptrLast = last.current->prev;
		Node* lstHead = lst.head;
		Node* lstTail = lst.tail;

		ptr->prev->next = ptrFirst;
		lstTail->prev = ptrFirst->prev;

		ptrFirst->prev->next = lstTail;
		ptrFirst->prev = ptr->prev;

		ptrLast->next=ptr;
		ptr->prev = ptrLast;
			
		theSize += lst.size();
		lst.theSize = lst.size();
		
	}
  //********************************************************
private:
  int theSize;
  Node *head, *tail;

  void init( );
};
// -- end class List

/*===========================================
 * member function definitions for class List
 *===========================================*/
template <typename Object>
List<Object>::List( ) { init( ); }

template <typename Object>
List<Object>::List( const List & rhs )
{
  init( );
  *this = rhs;
}

template <typename Object>
List<Object>::~List( )
{
  clear( );
  delete head;
  delete tail;
}

template <typename Object>
const List<Object> & List<Object>::operator= ( const List & rhs )
{
  if( this == &rhs )
    return *this;
  clear( );
  for( const_iterator itr = rhs.begin( ); itr != rhs.end( ); ++itr )
    push_back( *itr );
  return *this;
}

template <typename Object>
void List<Object>::init( )
{
  theSize = 0;
  head = new Node;
  tail = new Node;
  head->next = tail;
  tail->prev = head;
}

#endif

Open in new window

#include <iostream>
#include <string>
#include <list>
using namespace std;

#include "List2.h"

template<class T>
void printListForward(const List<T> & lst);
template<class T>
void printListBackward(const List<T> & lst);

int main()
{
  const int SIZE = 6;
  string sarray[SIZE] = {"aa", "bb", "cc", "xx", "yy", "zz"};

  List<string> slist1, slist2;
  slist1.push_back(sarray[0]);
  slist1.push_back(sarray[1]);
  slist1.push_back(sarray[2]);
  cout << "slist1 (size = " << slist1.size() << "): \n";
  cout << " Forward:  ";
  printListForward(slist1); cout << endl;

  slist2.push_back(sarray[3]);
  slist2.push_back(sarray[4]);
  slist2.push_back(sarray[5]);
  cout << "slist2 (size = " << slist2.size() << "): \n";
  cout << " Forward:  ";
  printListForward(slist2); 
  
  cout << endl;

  List<string>::iterator it = slist1.begin();
  it++; // it points to "bb"

  List<string>::iterator it2 = slist2.begin();
  it2++; // it2 points to "yy"


  cout << "=== After splice between " << *it2 << " and " << *(--(slist2.end())) << " ===\n\n";
  slist1.splice(it, slist2, it2, slist2.end()); ///////////////////////////////////////////////////////////////////

  cout << "slist1 (size = " << slist1.size() << "): \n";
  cout << " Forward:  ";
  printListForward(slist1); //cout << endl;
  cout << " Backward: ";
  printListBackward(slist1); cout << endl;
  cout << "slist2 (size = " << slist2.size() << "): \n";
  cout << " Forward:  ";
  printListForward(slist2); //cout << endl;
  cout << " Backward: ";
  printListBackward(slist2); cout << endl;


  // Set up slist1 for testing unique()
  slist1.push_front(sarray[0]); slist1.push_front(sarray[0]);
  slist1.insert(it, *it);
  slist1.push_back(*(--slist1.end()));

  cout << " => Slist2 is added with some elements.\n\n";
  cout << "slist1 (size = " << slist1.size() << "): \n";
  cout << " Forward:  ";
  printListForward(slist1); cout << endl;


  cout << "=== After unique() ===\n\n";
  //slist1.unique(); ///////////////////////////////////////////////////////////////////////////////
  cout << "slist1 (size = " << slist1.size() << "): \n";
  cout << " Forward:  ";
  printListForward(slist1); //cout << endl;
  cout << " Backward: ";
  printListBackward(slist1); cout << endl;

  system("Pause");
  return 0;
}

template<class T>
void printListForward(const List<T> & lst)
{
  List<T>::const_iterator it = lst.begin();
  while (it != lst.end()) 
    cout << *it++ << " ";
  cout << endl;
}

template<class T>
void printListBackward(const List<T> & lst)
{
  List<T>::const_iterator it = lst.rbegin();
  while (it != lst.rend()) 
    cout << *it-- << " ";
  cout << endl;
}

Open in new window

0
 
LVL 32

Expert Comment

by:phoffric
ID: 35443865
I have to leave now. But I'll be back before 2 hours.
0
 

Author Comment

by:villmund
ID: 35443897
ok
0
 

Author Comment

by:villmund
ID: 35444681
I solved my problem
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35444719
I'm back and was looking at your last post. Do you want to post your latest for us to review?
0
 

Author Comment

by:villmund
ID: 35444780
Sure, the only thing I changed was the way the size of both lists are calculated inside of the splice function. The rest of the code I didn't touch.
//slist1.splice(it, slist2, it2, slist2.end());
	void splice(iterator position, List & lst, iterator first, iterator last)
	{
		
		Node* ptr = position.current;
		Node* ptrFirst = first.current; //new
		Node* ptrLast = last.current->prev; //new
		Node* lstHead = lst.head;
		Node* lstTail = lst.tail;

		ptr->prev->next = ptrFirst;
		lstTail->prev = ptrFirst->prev;

		ptrFirst->prev->next = lstTail;
		ptrFirst->prev = ptr->prev;

		ptrLast->next=ptr;
		ptr->prev = ptrLast;

		int i=0;
		while (lstHead->next != lstTail)
		{
			i++;
			lstHead= lstHead->next;
		}
			
		theSize += lst.size()-i;
		lst.theSize = i;

	}

Open in new window

0
 
LVL 32

Expert Comment

by:phoffric
ID: 35445646
Pretty decent job, for what I've seen. BTW, since you are writing pseudo-STL code, if you have time, you may as well include a List constructor that accepts a slice of an array to initialize the List.

I'm going to look again tomorrow with fresher eyes. I didn't expect to see a while loop in the splice -  maybe it is needed; maybe not. Could you explain the reason for it.

But, I will need to double-check a test I wrote to make sure I set it up correctly. The program crashed (which suggest that if the user does something wrong in their setup, then your api should include proper error handling).
    List<string>::iterator it = slist1.begin(); 
    it++; // it points to "bb" 

    List<string>::iterator it2 = slist2.begin(); 
    it2++; // it2 points to "yy" 
    List<string>::iterator it3 = it2;
    it3++; // it3 points to "zz"

    //cout << "=== After splice between " << *it2 << " and " << *(--(slist2.end())) << " ===\n\n"; 
    //slist1.splice(it, slist2, it2, slist2.end()); 
    cout << "=== After splice between " << *it2 << " and " << *(--it3) << " ===\n\n";
    slist1.splice(it, slist2, it2, it3); 

Open in new window

The crash occurs inside the splice while loop due to a null pointer. Here is the output before the crash:
slist1 (size = 3):
 Forward:  aa bb cc

slist2 (size = 3):
 Forward:  xx yy zz

=== After splice between yy and yy ===

Open in new window

0
 
LVL 32

Expert Comment

by:phoffric
ID: 35455183
You could add an overloaded insert following the 2nd case in
     http://www.cplusplus.com/reference/stl/list/insert/
in order to insert one List object into the middle of another destination List object.

You could define an append operation to append one List object to another List object.

You could define a split operation that creates 3 List objects (with potentially, the first or third List object being empty) by giving the range of the middle List object.

Then you can use these methods in the splice method.

These additional methods not only are helper methods to simplify the splice code, but serve in their own right to add to the useful functionality of your List class.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35455988
Some good news. As I said, I would double-check my additional test scenario. Your splice did not crash! The test scenario problem was that in trying to be consistent with your previous cout statement, I wrote:
cout << "=== After splice between " << *it2 << " and " << *(--it3) << " ===\n\n";
slist1.splice(it, slist2, it2, it3);


I corrected this by adding this line between the above two statements:
++it3; // get back to where we belong before the cout statement.
0
 
LVL 32

Accepted Solution

by:
phoffric earned 2000 total points
ID: 35456200
I see that you compute the length of the decreased lst by traversing from it from the head to the tail. This is not very efficient if the lst is large. Why not just traverse from first to last and count the number of nodes that are being moved from slist2 to slist1. You can accomplish this with a simple for-loop having no body, just using an iterator and a counter. Then add the count to the size of slist1 and subtract from slist2.

You should do this first thing in the splice function, and update the sizes before returning.

===

But I did find other problems with the splice function which will be discussed below.

I think the problem is partly naming conventions. I try to give meaningful names to entities as they are created. You are initially given a src sequence and a destination sequence. The src (lst) sequence is broken up into three sequences, where the first or third sequence can be empty. The lst's 2nd sequence from first to last-1 will become the destination's 2nd sequence after the splice.

So, with that idea in mind, I made a few name substitutions, which may help you understand what problem you have. What you should be doing is this:
// fix up the src (i.e., link sequence 1 end to sequence 3 begin)
// fix up the dst: link dst sequence 1 with src sequence 2
// fix up the dst: link dst sequence 3 with src sequence 2

As you can see, there are no loops in these operations. The only loop required is to count the number of nodes in the middle src sequence (and that could have been done probably as an iterator difference overloaded opeartion) to emulate pointer difference operation.

Now, what I am listing below shows your code with naming conventions changes to clearly indicate the source vs destination and the segment number. Hopefully, when you look at it, you will see the problem. I did add a comment where you should look. I left out the code to update the size using a simple for-loop. Give it a try if you wish. If you do not fix the code, then you may get a crash in your destructors as you exit the program.

With the code as is, you may see inconsistencies when printing out the list both forwards and backwards - it may be correct in one direction, but not the other.

If you fix the program, then you can post, and I'll be happy to review what you have. When you get a working program, then if you have time, you can ask another question on the general software engineering of your program. I'm sure many experts will be happy to lend you some good advice.

====

A quick requirements question that is of relatively minor importance. When you do a push_back, you throw away non-unique values. But in the splice, you do not require uniqueness.
// NOTE: This is your code, but I changed the names to help make it clearer
void splice(iterator itDstPosition, List & srcLst, iterator itSrcFirst, iterator itSrcLast) 
{
    // Count the number of nodes in src sequence 2:
     ...
    Node* pDstBeg3   = itDstPosition.current;
    Node* pDstEnd1   = pDstBeg3->prev;          // added end of 1st src segment
    Node* pSrcBeg2   = itSrcFirst.current; //new 
    Node* pSrcBeg3   = itSrcLast.current;       // added beginning of 3rd src segment 
    Node* pSrcEnd1   = pSrcBeg2->prev;          // added end of 1st src segment
    Node* pSrcEnd2   = pSrcBeg3->prev;     //new 
    Node* srcLstHead = srcLst.head; 
    Node* srcLstTail = srcLst.tail; 

    pDstEnd1->next = pSrcBeg2; 
    srcLstTail->prev = pSrcEnd1; // splicing using Tail ??

    pSrcEnd1->next = srcLstTail; // splicing using Tail ??
    pSrcEnd1 = pDstEnd1; 

    pSrcEnd2->next = pDstBeg3; 
    pDstEnd1 = pSrcEnd2; 

    // Update the sizes
    ...
}

Open in new window

0
 

Author Comment

by:villmund
ID: 35494846
Thanks for all the help.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 35494852
If you have any questions or wish to post your program for review, do not hesitate to do so.
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
Suggested Courses

873 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question