//=================================================================================
//
// 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