BList_func.h

Go to the documentation of this file.

/*******************************************************************************
 *  BList_func.h    BEAM List implementation based upong stdc++ lists
 *          T.Barnaby,  BEAM Ltd,   4/8/00
 *  Copyright (c) 2012 All Right Reserved, Beam Ltd, http://www.beam.ltd.uk
 *******************************************************************************
 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <memory.h>

template <class T> BList<T>::BList() {
    onodes = nodeCreate();
    onodes->next = onodes;
    onodes->prev = onodes;
    olength = 0;
}

template <class T> BList<T>::BList(const BList<T>& l) {
    onodes = nodeCreate();
    onodes->next = onodes;
    onodes->prev = onodes;
    olength = 0;
    append((BList<T>&)l);
}

template <class T> BList<T>::~BList() {
    clear();
    delete [] (char*)onodes;
}

template <class T> void BList<T>::start(BIter& i) const {
    i = onodes->next;
}

template <class T> BIter BList<T>::begin() const {
    return onodes->next;
}

template <class T> BIter BList<T>::end() const {
    return onodes->prev;
}

template <class T> BIter BList<T>::end(BIter& i) const {
    i = onodes->prev;
    return onodes->prev;
}

template <class T> void BList<T>::next(BIter& i) const {
    BNode*  n = i;
    
    if(n != onodes)
        n = n->next;
    i = n;
}

template <class T> void BList<T>::prev(BIter& i) {
    BNode*  n = i;
    
    if(n != onodes)
        n = n->prev;
    i = n;
}

template <class T> BIter BList<T>::goTo(int pos) const {
    BIter   i;
    int c;

    for(i = begin(), c = 0; (c < pos) && !isEnd(i); next(i), c++);
    return i;
}
    
template <class T> int BList<T>::position(BIter i) {
    BIter   ii;
    int c;

    for(ii = begin(), c = 0; !isEnd(ii); next(ii), c++){
        if(ii == i)
            return c;
    }
    return -1;
}

template <class T> unsigned int BList<T>::number() const {
    return olength;
}

template <class T> unsigned int BList<T>::size() const {
    return number();
}

template <class T> int BList<T>::isStart(BIter& i) const {
    Node*   n = (Node*)(BNode*)i;

    return (n == onodes->next);
}

template <class T> int BList<T>::isEnd(BIter& i) const {
    Node*   n = (Node*)(BNode*)i;

    return (n == onodes);
}

template <class T> void BList<T>::clear(){
    BIter   i;
    
    for(start(i); !isEnd(i); )
        del(i);
}

template <class T> T& BList<T>::front(){
    return get(begin());
}

template <class T> T& BList<T>::rear(){
    return get(end());
}

template <class T> T& BList<T>::get(BIter i){
    return nodeGet(i)->item;
}
    
template <class T> const T& BList<T>::get(BIter i) const {
    return nodeGet(i)->item;
}
    
template <class T> void BList<T>::append(const T& item){
    BIter   i = end();
    
    insertAfter(i, item);
}

template <class T> void BList<T>::insert(BIter& i, const T& item){
    Node*   c = (Node*)(BNode*)i;
    Node*   n = nodeCreate(item);
    
    n->next = c;
    n->prev = c->prev;
    c->prev->next = n;
    c->prev = n;
    olength++;
    i = n;
}

template <class T> void BList<T>::insertAfter(BIter& i, const T& item){
    next(i);
    insert(i, item);
}

template <class T> void BList<T>::del(BIter& i){
    Node*   n = (Node*)(BNode*)i;
    
    if(olength){
        i = n->next;
        n->prev->next = n->next;
        n->next->prev = n->prev;
        delete n;
        olength--;
    }
}

template <class T> void BList<T>::deleteLast(){
    BIter   i = end();
    
    del(i);
}

template <class T> void BList<T>::deleteFirst(){
    BIter   i = begin();
    del(i);
}

template <class T> void BList<T>::push(const T& item){
    append(item);
}

template <class T> T BList<T>::pop(){
    T   t = rear();

    deleteLast();
    return t;
}

template <class T> void BList<T>::queueAdd(const T& i){
    append(i);
}

template <class T> T BList<T>::queueGet(){
    T   t = front();
    
    deleteFirst();
    return t;
}

template <class T> void BList<T>::append(const BList<T>& l){
    BIter   i;
                    
    for(l.start(i); !l.isEnd(i); l.next(i)){
        append(l.get(i));
    }
}

template <class T> int BList<T>::has(const T& v) const {
    BIter       i;

    for(start(i); !isEnd(i); next(i)){
        if(get(i) == v)
            return 1;
    }
    return 0;
}

template <class T> void BList<T>::swap(BIter i1, BIter i2){
    BNode*  n1 = (BNode*)i1;
    BNode*  n2 = (BNode*)i2;
    BNode*  n1p = n1->prev;
    BNode*  n1n = n1->next;
    BNode*  n2p = n2->prev;
    BNode*  n2n = n2->next;

    if(n1->next == n2){
        n1p->next = n2;
        n2n->prev = n1;

        n1->prev = n2;
        n2->prev = n1p;
        n1->next = n2n;
        n2->next = n1;
    }
    else if(n1->prev == n2){
        n2p->next = n1;
        n1n->prev = n2;

        n1->prev = n2p;
        n2->prev = n1;
        n1->next = n2;
        n2->next = n1n;
    }
    else {
        n1p->next = n2;
        n1n->prev = n2;
        n2p->next = n1;
        n2n->prev = n1;

        n1->prev = n2p;
        n2->prev = n1p;
        n1->next = n2n;
        n2->next = n1n;
    }
}

template <class T> void BList<T>::sort(){
    BIter       i;
    BIter       s;
    int     n = number();
    int     c;
    
    while(n){
        for(c = n - 1, i = begin(); c > 0; c--, next(i)){
            s = i;
            next(s);
            if(get(i) > get(s)){
                swap(i, s);
                i = s;
            }
        }
        n--;
    }
}

template <class T> void BList<T>::sort(SortFunc func){
    BIter       i;
    BIter       s;
    int     n = number();
    int     c;

    while(n){
        for(c = n - 1, i = begin(); c > 0; c--, next(i)){
            s = i;
            next(s);
            if(func(get(i), get(s)) > 0){
                swap(i, s);
                i = s;
            }
        }
        n--;
    }
}

template <class T> T& BList<T>::operator[](BIter i){
    return get(i);
}

template <class T> const T& BList<T>::operator[](const BIter& i) const {
    return get(i);
}

template <class T> T& BList<T>::operator[](int i){
    BIter   ii;
    
    if((ii = goTo(i))){
        return get(ii);
    }
    else {
        fprintf(stderr, "BList over range\n");
        exit(1);
    }
}

template <class T> const T& BList<T>::operator[](int i) const {
    BIter   ii;
    
    if((ii = goTo(i))){
        return get(ii);
    }
    else {
        fprintf(stderr, "BList over range\n");
        exit(1);
    }
}

template <class T> BList<T>& BList<T>::operator=(const BList<T>& l){
    BIter   i;
    
    if(this != &l){
        clear();
        for(l.start(i); !l.isEnd(i); l.next(i)){
            append(l[i]);
        }
    }
    
    return *this;
}

template <class T> BList<T> BList<T>::operator+(const BList<T>& l) const {
    BList<T>    rl = *this;
    BIter       i;
    
    for(l.start(i); !l.isEnd(i); l.next(i)){
        rl.append(l[i]);
    }
    return rl;
}

template <class T> typename BList<T>::Node* BList<T>::nodeGet(BIter i){
    return (Node*)(BNode*)i;
}

template <class T> const typename BList<T>::Node* BList<T>::nodeGet(BIter i) const{
    return (Node*)(BNode*)i;
}

template <class T> typename BList<T>::Node* BList<T>::nodeCreate(const T& item){
    return new Node(item);
}
template <class T> typename BList<T>::Node* BList<T>::nodeCreate(){
    Node*   n;
    
    n = (Node*)new char [ sizeof(Node) ];
    // WARNING: This is not ideal. However only used for the list start/end Node where the object is not valid anyway.
    memset((void*)n, 0, sizeof(Node));
    return n;
}