//================================================================================= // // Copy One-Directed Bi-Linked List.with "next" branch wich covers all list. // // Copyright (C) 2009 Konstantin Kirillov. // In response to quiz from it-dominanta.ru // // Credit: http://discuss.joelonsoftware.com/default.asp?interview.11.395216.4 // Algorithm details follows below. // // Program is tested briefly only. // //================================================================================= /* 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: //Algorithm: Traverses origin and calculates size L of the list. // Allocates arrary twin[L] // Traverses origin and // sets twin.next to origin.random // sets oritin.random to twin // optionally sets twin.data (if any) // Traverses origin and sets twin.random to value from twin. // Traversss origin and restores its random and sets twin.next //Drawbacks: During operation only traversion of nbranch and data read/modif // is enabled. // Other operations on origin like traversion of rbranch are not // permitted. //Advantages: No memory proportional to size of a list is required during copying. // Time ~ size of the list. //---------------------------------------------------------------------------------- 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; //Auxiliary variables: NBList* random; int count; //----------------------------------- //Count the lengh of the list //- - - - - - - - - - - - - - - - - - count=0; while(current!=NULL){ count++; current=(*current).next; } //----------------------------------- //----------------------------------- //Allocate linear space for twin: //- - - - - - - - - - - - - - - - - - twin_entry=(NBList*)malloc(count*sizeof(NBList)); //----------------------------------- //----------------------------------- //Spawn nbranch //- - - - - - - - - - - - - - - - - - current=entry; count=-1; while(current!=NULL){ twin_current=twin_entry+(++count); //Remember original random link in the twin list: (*twin_current).next=(*current).random; //Preserve map: (*current).random=twin_current; //At least enable data for read/modify access: (*twin_current).data=(*current).data; //Make step along the nbranch: current=(*current).next; } //- - - - - - - - - - - - - - - - - - //Spawn nbranch //----------------------------------- //----------------------------------- //Spawn rbranch //- - - - - - - - - - - - - - - - - - current=entry; count=-1; while(current!=NULL){ twin_current=twin_entry+(++count); //Establisch twin/random; random=(*twin_current).next; if(random==NULL) { (*twin_current).random=NULL; }else{ (*twin_current).random=(*random).random; } //Make step along the nbranch: current=(*current).next; } //- - - - - - - - - - - - - - - - - - //Spawn rbranch //----------------------------------- //----------------------------------- //Restore origin/random and twin/next //- - - - - - - - - - - - - - - - - - current=entry; count=-1; while(current!=NULL){ twin_current=twin_entry+(++count); //Restore origin/random: (*current).random=(*twin_current).next; //Make step along the nbranch: current=(*current).next; //Restore twin/next: if(current==NULL) { (*twin_current).next=NULL; }else{ (*twin_current).next=twin_entry+(count+1); } } //- - - - - - - - - - - - - - - - - - //Restore origin/random ... //----------------------------------- return twin_entry; } //================================================================================= Copyright (C) 2009 Konstantin Kirillov