/************************************************************
 *
 * CSc33200-CCNY
 * Project 0 by FN LN, 10/10/2003
 *
 ***********************************************************/

#include <iostream>
#include <stdlib.h>
#include "project_0.h"


/***********************************************************
 * Implementation of four procedures
 **********************************************************/

/**
 * If value is 0 then numbits is 0
 * else (val & 1) gives us the rightmost bit
 *  plus numbit(val>>1) - the other bits (except the rightmost)
 */

int numbit(int val)
{
  return (val==0) ? 0 : (val & 1) + numbit(val>>1);
}

/**
 * Power of 2 means that only 1 bit is set
 */

bool is2power(int val)
{
  return numbit(val) == 1;
}

/**
 * The following steps are taken to manipulate a URL:
 *
 * 1. counts ' '  and obtins string length -> O(n)
 * 2. replaces all ' ' with "%20"          -> O(n)
 *
 * Tus the complexity of this implementation is O(n).
 */

void urlmanip(char * &url)
{
  int i = 0;
  int count = 0;
  int j;

  // step 1

  while (url[i] != '\0') {
    if (url[i] == ' ')
      count++;
    i++;
  }

  // step 2

  j = i + 2*count;
  while (i>=0) {
    if (url[i]!=' ') {
      url[j--] = url[i--];
    } else {
      url[j--] = '0';
      url[j--] = '2';
      url[j--] = '%';
      i--;
    }
  }

  // step 3 (optional)
  if (j != -1) {
    cout << "Something wrong with the implementation of urlmanip()!";
  }
}

/**
 * merges two sorted linked list na and nb.
 *
 * NOTE:
 * The nodes in the old lists are directly used in the new list.
 * That is the two old lists won't exist after the invocation of 
 * this procedure.
 */

NODE merge_list(NODE na, NODE nb)
{
		
  // if one of the list is empty return the other
  if (na == NULL) return nb;
  if (nb == NULL) return na;

  // p is the prent position in the merged list
  NODE head = NULL, p;
  NODE a = na, b = nb;
  
  // determines the head pointer
  
  if (a->_val < b->_val){
    head = a;
    a = a->next;
  } else {
    head = b;
    b = b->next;
  }
  p = head;
  
  // while both lists have elements
  
  while (a!=NULL && b!=NULL){
    if (a->_val < b->_val) {
      p->next = a;
      a = a->next;		
    } else {
      p->next = b;
      b = b->next;
    }

    p = p->next;
  }

  // if we still have some elements in one of the links

  if (b!=NULL)
  	p->next=b;

  if (a!=NULL)
  	p->next=a;

  // return the head

  return head;
}



/***********************************************************
 * main() and auxiliary procedures
 **********************************************************/


/**
 * internal function to print the content of a sorted list.
 */
 
static void print_list(NODE c)
{
  for (; c!=NULL; c=c->next){
    cout << c->_val<<" ";
  }
}

/**
 * internal function to create a list node with the specified
 * value and next node.
 */
 
static NODE node(int val, NODE next)
{
  NODE a = new NODE_DATA;
  a->_val = val;
  a->next = next;
  return a;
}

/**
 * prints the banner for test cases for one of the four procedures
 */

static void print_banner(const char *banner)
{
	cout << endl;
	cout << "/****************************/" << endl;
	cout << "      " << banner << endl;
	cout << "/****************************/" << endl;
	cout << endl;
}


/**
 * main function
 *
 * tests the implementation of the four functions.
 */

int main(void)
{
  char SEP[] = " => ";
  
  // numbit()

  print_banner("numbit()");
	
  for (int b=7; b<10; b++)
    cout << b << SEP << numbit(b) << endl;
  
  // is2power()

  print_banner("is2power()");
	
  for (int i=0; i<10; i++)
    cout << i << SEP << (is2power(i) ? "true" : "false") << endl;
  
  // urlmanip()

  print_banner("urlmanip()");

  char url[100] = "http://ww w.cc n y. cu ny.edu";
  char *p = url;
  cout << p << SEP;
  urlmanip(p);
  cout << p << endl;

  // merge_list()
  
  print_banner("merge_list()");

  NODE a = node(1,
		node(3,
		     node(5,
			  node(7,
			       node(9, NULL)))));
  
  NODE b=node(2,
	      node(4,
		   node(7,
			node(8, NULL))));
  
  cout << "na: ";
  print_list(a);
  cout << endl;
  
  cout << "nb: ";
  print_list(b);
  cout << endl;
  
  NODE c = merge_list(a, b);
  
  cout << "merged list: ";
  print_list(c);
  cout << endl << endl;
  
  return 0;
}