/* clistf.cpp    v1.0  (C) 2000 adolfo&di-mare.com */

#include "clistf.h"

const FALSE = 0;
const TRUE  = !FALSE;

void clistf::link_after( // Links after a position
    clistf::itr         where,  // where to link
    clistf::list_link&  what    // what to link
) /*
result:
  Links node "what" after "where" in the list.
  - To link at the beginning, use where==0.
  - To append, use where==last().
  - Takes O(1) time always. Does not allocate memory.
requires:
  -"where" must be a valid position in the list, or 0.
*/ {
    if (_last == end()) {     // empty list
        what.next = &what;    // => link at the beginning
        what.next.mark();
        _last = what.next;
    }
    else if (where == end()) {    // link as first
        _last.unmark();
        list_link * last = _last.ai();
        what.next  = last->next.um(); // first()
        last->next = &what;
        assert(ptrbit::aligned(&what));  // debug
        last->next.mark();
    }
    else if (where == _last) { // links at the end
        list_link *last = _last.um();

        what.next = last->next;
        what.next.mark();
        last->next = &what;   // unmarked
        _last      = &what;
    }
    else { // links in the middle of the list
        what.next = where.ai()->next;  // where is unmarked
        where.ai()->next = &what;
    }
}  // clistf::link_after()

clistf::itr clistf::unlink_after(
    clistf::itr where  // where to unlink
) /*
result:
  Unlinks node "what" that comes after "where" in the list.
  - To unlink the first, use where==0.
  - Cannot unlink the last node.
  - Takes O(1) time always. Does not deallocate memory.
returns:
  - pointer to unlinked node
requires:
  -  where != last()
  - "where" must be a valid position in the list, or 0.
*/ {
    list_link * last = _last.um();    // unmarked

    if (where == end()) {        // unlink first
        list_link * first =  last->next.um();
        if (last == first) { // last node
            _last = end();
            return last;     // already unmarked
        }
        else {
            last->next = first->next;
            last->next.mark();
            return first;
        }
    }
    else {   /*  // where != 0
        if ((last == last->next.um()) || (where == _last)) {
        //  throw("cannot clistf::unlink_after() last node");
            return 0;
        }
        else */  { // unlinks in the middle
            list_link * whr = where.um();   // both unmarked
            list_link * tmp = whr->next.um();
            whr->next = tmp->next;
            if (tmp == last) {
                whr->next.mark();
                if (tmp->next.ai() == whr) {
                    _last = whr->next;  // marked
                } else {
                    _last = whr;        // unmarked
                }
            }
            return tmp;
        }
    }
}  // clistf::unlink_after()

unsigned clistf::count()
/*
returns:
  Returns the number of nodes in the list.
  - Takes O(n) time to run.
*/ {
    if (_last == end()) {
        return 0;
    } else {
        unsigned n = 1;
        list_link * last = _last.um();
        list_link * p =     last->next.um();
        while (p != last) {
            p = p->next.ai();  // avoids .um() for p++
            n++;
        }
        return n;
    }
}  // clistf::count()

int clistf::valid(itr i)
/*
returns:
  Returns true when "i" points into the list.
  - valid(0) is always false.
  - Takes O(n) time to run.
*/ {
    if (_last != end()) {
        if (_last == i) {
            return TRUE;
        }
        list_link * last = _last.um();
        list_link * q    =  last->next.um();  // first()
        while (q != last) {
            if (i.ai() == q) {
                return TRUE;
            }
            q = q->next.ai();
        }
    }
    return FALSE;
} // clistf::valid()

clistf::itr clistf::itr::prev()
/*
returns:
  The itr that comes before "i" in the list.
  - prev(begin()) == 0
  - q = p.prev() ==> q++ == p
  - Takes O(n) time to run.
requires:
  - "i" must be a valid position in the list.
  - prev(end()) is always undefined and incorrect.
*/ {

    list_link * p =  this->um();    // find-me
    list_link * q =  p->next.um();  // first()
    list_link * qn;                 // q-next

    for (;;) {
        qn = q->next.um();
        if (qn == p) {      // found?
            return ( q->next.marked() ? 0 : q );
        }
        q = qn;   // q++
    }
}  // itr::prev()

clistf::itr clistf::nth(
    unsigned n
/*
returns:
  an itr to the n-th list element.
  - Counting begins in 0.
  - L.nth(L.count()) == L.end()
  - Takes O(n) time to run.
requires:
  - n < L.count()
*/ ) {
    itr tmp = begin();
    for (unsigned i=0; i<n; i++) {
        tmp++;
    }
    return tmp;
} // clistf::nth()

unsigned clistf::pos(
    clistf::itr i
/*
returns:
   the relative position of the item in the list.
   - L.pos(L.begin()) == 0
  - Takes O(n) time to run.
requires:
   - L.pos(L.end()) is always invalid
*/ ) {
    unsigned n = 0;
    for (itr p=begin(); p!=end(); p++, n++) {
        if (i==p) {
            return n;
        }
    }
    return n;
} // clistf::pos()

/* EOF:   clistf.cpp */