In article <(E-Mail Removed)>,

http://www.velocityreviews.com/forums/(E-Mail Removed) (Richard Harter) wrote:

> On Sat, 17 Sep 2011 07:40:54 +0200, jacob navia <(E-Mail Removed)>

> wrote:

>

> >Le 17/09/11 05:15, Tony a écrit :

> >>>> Maybe at one time lack of argument checking could have been

> >>>> considered a "quality of implementation" issue, but today (and long

> >>>> has been) that is a difference between professional code and

> >>>> Programming 101 student

> >>>> code.

> >>>

> >Ben wrote:

> >

> >>> How do conclude, from what I said, that I am advocating a lack of due

> >>> diligence or not checking arguments?

> >>

> >And Tony answered:

> >> By suggesting that documentation can preclude doing argument checking,

> >> thereby "throwing the problem over the wall" making it the programmer's

> >> problem for not reading "the directions".

> >>

> >>

> >

> >Not all preconditions can be tested. For instance I proposed a routine

> >to test if a list is circular. It involves examining all the list.

> >

> >If a library (like the C Containers library) would do that, its

> >performance would be close to zero.

>

> Well, no, it wouldn't. The cost of checking whether a linked list

> terminates in a cycle is of the same order as the cost of reversing

> the list. One could even integrate cycle checking into the reversal

> code. If one does that one could also reverse a cycle terminated

> linked list by defining the new head as the node that joined the

> cycle. I don't suppose you would want to do that but it could be done

> cheaply enough.
Here is the canonical linked list reversal.

struct ure

{

struct ure *link;

int data;

};

struct ure *list_head = NULL;

...

/* Build up the linked list. */

...

{

struct ure *tail;

tail = list_head;

list_head = NULL;

for(; tail != NULL; tail = next)

{

struct ure *next;

next = tail->link;

tail->link = list_head;

list_head = tail;

}

}

Given a linked list with a loop, this code terminates;

reversing the cycle, and leaving invariant the

transient and the node that has two nodes pointing at it.

list_head -> a -> b -> c -> d -> e -> c

list_head -> NULL | tail -> a -> b -> c -> d -> e -> c

list_head -> a -> NULL | tail -> b -> c -> d -> e -> c

list_head -> b -> a -> NULL | tail -> c -> d -> e -> c

list_head -> c -> b -> a -> NULL | tail -> d -> e -> c

list_head -> d -> c -> b -> a -> NULL | tail -> e -> c

list_head -> e -> d -> c -> b -> a -> NULL | tail -> c

list_head -> c -> e -> d -> c | tail -> b -> a -> NULL

list_head -> b -> c -> e -> d -> c | tail -> a -> NULL

list_head -> a -> b -> c -> e -> d -> c | tail -> NULL

We can analyze a linked list with a loop in O(1) space

and O(n) time. This is done in three stages using two

separate variables to traverse the list:

Leader

Follower

In Stage 1 we need to test for a NULL that will show

that the linked list is NULL terminated, and prevent

dereferencing NULL.

Stage 1:

L <- list_head

F <- list_head

At each step F traverses one node, and L traverses two

nodes. Eventually we have F = L, and F and L are

pointing at a node in the cycle.

Stage 2:

Save the value of L, then let L traverse nodes until L

is back at its saved value. Now we know the value of c,

the length of the cycle.

Stage 3:

L <- list_head

F <- list_head

Let L traverse c nodes. Now L and F step in tandem, one

node each for each step until L = F. Now L and F point

at the node that has two nodes pointing at it.

--

Michael Press