home top contents previous up next

//=================================================================================
//
//  Copy One-Directed Bi-Linked List.with "next" branch wich covers all list.
//  This version of program has failed "algorithm"
//   Wrong place is marked with lines 	//FFFFFFFFFFFFFFFFFF.....
//   
//  Copyright (C) 2009 Konstantin Kirillov.
//
//=================================================================================


/* 
2.2.1 One directional (possibly multilinked) list.

    A. There can be one order-branch (call it "next-branch") which covers an entire tree.
       It will be sufficient to traverse this branch.

*/


#include <stdlib.h>
#include "nbranch.h"



//=================================================================================
//
//  Procedure do_copy
//
//---------------------------------------------------------------------------------
//Input:        the list is terminated by the node with next=NULL;
//              there are no repetitions in next-branch.
//              Assumed: given and new lists to be in own "memory page".

//Returns:      entry link of copy of the list:
//Optimization: we allocate memory in size of one structure.
//              In production version, some dynamically growing chunks should be
//              allocated.
//Algorithm:    allocating memory for list by traversing branch next and
//              in second traversing, setting links "random".
//				No recursion, no any extra memory except few variables.
//----------------------------------------------------------------------------------

NBList* do_copy( NBList* entry ){

  //Prepare to traverse original tree:
  NBList* current=entry;

  //Prepare to create target tree:
  NBList* twin_entry=NULL;
  NBList* twin_current;
  NBList* twin_previous;

  //-----------------------------------
  //Spawn nbranch
  //- - - - - - - - - - - - - - - - - - 
  while(current!=NULL){
	  twin_current=(NBList*)malloc(sizeof(NBList));
	  if(twin_entry==NULL)
	  {
   	      twin_entry=twin_current;
	  }else{
          (*twin_previous).next=twin_current;
	  }
	  (*twin_current).next=NULL;

	  //Make step along the nbranch:
      current=(*current).next;
      twin_previous=twin_current;
  }
  //- - - - - - - - - - - - - - - - - - 
  //Spawn nbranch
  //-----------------------------------


  //-----------------------------------
  //Spawn rbranches
  //- - - - - - - - - - - - - - - - - - 
  current=entry;
  twin_current=twin_entry;

  while(current!=NULL){

     if((*current).random==NULL)
	 {
        (*twin_current).random=NULL;
     }else{

		//FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
		//
        //To convert pointers to own link addressspace:
        int reference=(int)( ((NBList*)(*current).random) - (NBList*)entry);

        //HERE IS A PLACE WHERE ALGORITHM FAILS.
        //reference IS USELESS BECAUSE OF IT CAN BE DIFFERENT BETWEEN ORIGINAL AND
		//          NEW TREEE.

        (*twin_current).random=twin_entry+reference;

        //IN A MEAN TIME WE JUST DISCARDING ALL RANDOM LINKS:
        (*twin_current).random=NULL;

		//FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
     }
     
	 //test:
     (*twin_current).data=(*current).data;
     
     //Make step:
     current=(*current).next;
	 twin_current=(*twin_current).next;
  }
  //- - - - - - - - - - - - - - - - - - 
  //Spawn rbranches
  //-----------------------------------


  return twin_entry;
}
//=================================================================================
      


   
      


Copyright (C) 2009 Konstantin Kirillov