#define __MINMAX_DEFINED        // use STL's generic min and max templates

#include "list.h"               // include STL-list implementation

#include <iostream.h>

// Since the output loop is often used, we can form a template function
// which does the job.

template <class InputIterator>
void copy_to_cout (InputIterator first, InputIterator last) {

  while (first != last) cout << *first++;
  cout << endl;
}

// The template class "InputIterator" gets a meaning when you study
// chapter 4.2 in iterators.

void main (void)
{
  list<int> bit_seq;            // define a list of int
  int input = 0;                // value read from cin
  int count_1 = 0;              // counter for number of 1's

  cout << "Insert values 0 and 1, another value to stop input..." << endl;

  while (cin >> input) {
	 if (!(input == 0 || input == 1)) break;
	 bit_seq.push_back (input);             // list member function push_back
  }

  // output loop
  cout << "Original bit sequence:" << endl;
  copy_to_cout (bit_seq.begin(), bit_seq.end());

  // create a new list for bit_stuffing
  list<int> bit_stuffed_seq (bit_seq);

  // define loop iterators
  list<int>::iterator first = bit_stuffed_seq.begin();
  list<int>::iterator last  = bit_stuffed_seq.end();

  // bit stuff loop

  while (first != last) {
			if (*first == 0)
					 count_1 = 0;    	// reset 1's-counter
			else if (*first == 1)
					 count_1++;      	// increment number of  
                                                                //  consecutive 1's
			first++;                        // go to the next list element
			if (count_1 == 5) {
                                       // insert a 0 after the fifth consecutive 1
			  bit_stuffed_seq.insert (first, 0);
			  count_1 = 0;				// reset counter
			}
  }

  // output loop
  cout << "Bit-stuffed bit sequence:" << endl;
  copy_to_cout (bit_stuffed_seq.begin(), bit_stuffed_seq.end());

  double rel_exp;               // relative expansion (in percent)
  rel_exp = (double) bit_stuffed_seq.size() / bit_seq.size();
  rel_exp = (rel_exp - 1) * 100;
  cout.precision (4);

  cout << "Relative expansion: " << rel_exp << "%" << endl;
  cout << "Absolute expansion: " << (bit_stuffed_seq.size()-bit_seq.size());
  cout << " bit" << endl;

  // bit unstuff loop
  first = bit_stuffed_seq.begin();
  last  = bit_stuffed_seq.end();
  list<int>::iterator erase_it;    // used because the erase-iterator
                                   // gets invalid

  count_1 = 0;

  while (first != last) {
		if (*first == 0) count_1 = 0; else count_1++;
		if (count_1 == 5) {
			erase_it = first;
			if (*(++erase_it) != 0) {	// error in input bit sequence
			  cout << "not a valid bit-stuffed sequence!" << endl;
			  exit(0);
			}
			bit_stuffed_seq.erase (erase_it);       // erase zero
			count_1 = 0;
		}
		++first;
  }

  cout << "After bit-unstuffing: ";

  // check for success (using operator==)
  bit_stuffed_seq == bit_seq ?  cout << "sequences are equal" :  \
                                cout << "sequences are not equal";

  cout << endl;
}

Back to index