public
Created

Random list generation program (with comments :)

  • Download Gist
gistfile1.cpp
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
#include <iostream>
using namespace std;
 
struct list_item
{
list_item *next;
list_item *rand;
};
 
void deep_copy(list_item* src, list_item* &dst)
{
// interleave src with dst such that src_1-->dst_1-->src_2-->dst_2 etc.
list_item *current = src, *temp;
dst = NULL;
while (current != NULL)
{
// allocate a matching dst element
list_item* li = new list_item;
// if it's the first ever, assign it as the output
if (dst == NULL)
dst = li;
// assign the element's next, but null the rand for now
li->next = current->next;
li->rand = NULL;
// rearrange the pointers for src_n->dst_n and move on
current->next = li;
current = li->next;
}
// for a given src element, its rand->next is the projected dst element
for (current = src; current != NULL; current = current->next->next)
{
// guard against the (unlikely) case of the rand not pointing anywhere :)
if (current->rand != NULL)
current->next->rand = current->rand->next;
}
// now separate the src|dst list into two lists
for (current = src; current != NULL;)
{
// cache the next item's address (it may very well be NULL)
temp = current->next->next;
// is there a next src+dst pair?
bool have_next = temp != NULL;
// if there is, do the forward pointers, otherwise null
current->next->next = have_next ? temp->next : NULL;
current->next = have_next ? temp : NULL;
// move forward
current = temp;
}
}
 
// utility function for deleting a list
void delete_list(list_item* first)
{
if (first->next != NULL)
delete_list(first->next);
delete first;
}
 
void main()
{
cout.setf(ios_base::boolalpha);
 
// test 1 - copy single element with rand=null
list_item* first = new list_item;
first->next = first->rand = NULL;
 
list_item* copied;
deep_copy(first, copied);
cout << "test 1 - copy single element with rand=null: " << (copied->next == NULL) << " " << (copied->rand == NULL) << endl;
delete_list(first);
delete_list(copied);
 
// test 2 - copy single element with rand=self
first = new list_item;
first->next = NULL;
first->rand = first;
 
deep_copy(first, copied);
 
cout << "test 2 - copy single element with rand=self: " << (copied->next == NULL) << " " << (copied->rand == copied) << endl;
delete_list(first);
delete_list(copied);
 
// test 3 - copy two elements with mutually referencing rand's
first = new list_item;
list_item* second = new list_item;
first->next = first->rand = second;
second->next = NULL;
second->rand = first;
 
deep_copy(first, copied);
 
cout << "test 3 - copy two elements with mutually referencing rand's: " <<
(copied->rand == copied->next) << " " <<
(copied->next->next == NULL) << " " <<
(copied->next->rand == copied) << " " << endl;
delete_list(first);
delete_list(copied);
 
getchar();
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.