include/utils/List.h

/*
 * Copyright (C) 2005 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

//
// Templated list class.  Normally we'd use STL, but we don't have that.
// This class mimics STL's interfaces.
//
// Objects are copied into the list with the '=' operator or with copy-
// construction, so if the compiler's auto-generated versions won't work for
// you, define your own.
//
// The only class you want to use from here is "List".
//
#ifndef _LIBS_UTILS_LIST_H
#define _LIBS_UTILS_LIST_H

#include <stddef.h>
#include <stdint.h>

namespace android {

/*
 * Doubly-linked list.  Instantiate with "List<MyClass> myList".
 *
 * Objects added to the list are copied using the assignment operator,
 * so this must be defined.
 */
template<typename T> 
class List 
{
protected:
    /*
     * One element in the list.
     */
    class _Node {
    public:
        explicit _Node(const T& val) : mVal(val) {}
        ~_Node() {}
        inline T& getRef() { return mVal; }
        inline const T& getRef() const { return mVal; }
        inline _Node* getPrev() const { return mpPrev; }
        inline _Node* getNext() const { return mpNext; }
        inline void setVal(const T& val) { mVal = val; }
        inline void setPrev(_Node* ptr) { mpPrev = ptr; }
        inline void setNext(_Node* ptr) { mpNext = ptr; }
    private:
        friend class List;
        friend class _ListIterator;
        T           mVal;
        _Node*      mpPrev;
        _Node*      mpNext;
    };

    /*
     * Iterator for walking through the list.
     */
    
    template <typename TYPE>
    struct CONST_ITERATOR {
        typedef _Node const * NodePtr;
        typedef const TYPE Type;
    };
    
    template <typename TYPE>
    struct NON_CONST_ITERATOR {
        typedef _Node* NodePtr;
        typedef TYPE Type;
    };
    
    template<
        typename U,
        template <class> class Constness
    > 
    class _ListIterator {
        typedef _ListIterator<U, Constness>     _Iter;
        typedef typename Constness<U>::NodePtr  _NodePtr;
        typedef typename Constness<U>::Type     _Type;

        explicit _ListIterator(_NodePtr ptr) : mpNode(ptr) {}

    public:
        _ListIterator() {}
        _ListIterator(const _Iter& rhs) : mpNode(rhs.mpNode) {}
        ~_ListIterator() {}
        
        // this will handle conversions from iterator to const_iterator
        // (and also all convertible iterators)
        // Here, in this implementation, the iterators can be converted
        // if the nodes can be converted
        template<typename V> explicit 
        _ListIterator(const V& rhs) : mpNode(rhs.mpNode) {}
        

        /*
         * Dereference operator.  Used to get at the juicy insides.
         */
        _Type& operator*() const { return mpNode->getRef(); }
        _Type* operator->() const { return &(mpNode->getRef()); }

        /*
         * Iterator comparison.
         */
        inline bool operator==(const _Iter& right) const { 
            return mpNode == right.mpNode; }
        
        inline bool operator!=(const _Iter& right) const { 
            return mpNode != right.mpNode; }

        /*
         * handle comparisons between iterator and const_iterator
         */
        template<typename OTHER>
        inline bool operator==(const OTHER& right) const { 
            return mpNode == right.mpNode; }
        
        template<typename OTHER>
        inline bool operator!=(const OTHER& right) const { 
            return mpNode != right.mpNode; }

        /*
         * Incr/decr, used to move through the list.
         */
        inline _Iter& operator++() {     // pre-increment
            mpNode = mpNode->getNext();
            return *this;
        }
        const _Iter operator++(int) {    // post-increment
            _Iter tmp(*this);
            mpNode = mpNode->getNext();
            return tmp;
        }
        inline _Iter& operator--() {     // pre-increment
            mpNode = mpNode->getPrev();
            return *this;
        }
        const _Iter operator--(int) {   // post-increment
            _Iter tmp(*this);
            mpNode = mpNode->getPrev();
            return tmp;
        }

        inline _NodePtr getNode() const { return mpNode; }

        _NodePtr mpNode;    /* should be private, but older gcc fails */
    private:
        friend class List;
    };

public:
    List() {
        prep();
    }
    List(const List<T>& src) {      // copy-constructor
        prep();
        insert(begin(), src.begin(), src.end());
    }
    virtual ~List() {
        clear();
        delete[] (unsigned char*) mpMiddle;
    }

    typedef _ListIterator<T, NON_CONST_ITERATOR> iterator;
    typedef _ListIterator<T, CONST_ITERATOR> const_iterator;

    List<T>& operator=(const List<T>& right);

    /* returns true if the list is empty */
    inline bool empty() const { return mpMiddle->getNext() == mpMiddle; }

    /* return #of elements in list */
    size_t size() const {
        return size_t(distance(begin(), end()));
    }

    /*
     * Return the first element or one past the last element.  The
     * _Node* we're returning is converted to an "iterator" by a
     * constructor in _ListIterator.
     */
    inline iterator begin() { 
        return iterator(mpMiddle->getNext()); 
    }
    inline const_iterator begin() const { 
        return const_iterator(const_cast<_Node const*>(mpMiddle->getNext())); 
    }
    inline iterator end() { 
        return iterator(mpMiddle); 
    }
    inline const_iterator end() const { 
        return const_iterator(const_cast<_Node const*>(mpMiddle)); 
    }

    /* add the object to the head or tail of the list */
    void push_front(const T& val) { insert(begin(), val); }
    void push_back(const T& val) { insert(end(), val); }

    /* insert before the current node; returns iterator at new node */
    iterator insert(iterator posn, const T& val) 
    {
        _Node* newNode = new _Node(val);        // alloc & copy-construct
        newNode->setNext(posn.getNode());
        newNode->setPrev(posn.getNode()->getPrev());
        posn.getNode()->getPrev()->setNext(newNode);
        posn.getNode()->setPrev(newNode);
        return iterator(newNode);
    }

    /* insert a range of elements before the current node */
    void insert(iterator posn, const_iterator first, const_iterator last) {
        for ( ; first != last; ++first)
            insert(posn, *first);
    }

    /* remove one entry; returns iterator at next node */
    iterator erase(iterator posn) {
        _Node* pNext = posn.getNode()->getNext();
        _Node* pPrev = posn.getNode()->getPrev();
        pPrev->setNext(pNext);
        pNext->setPrev(pPrev);
        delete posn.getNode();
        return iterator(pNext);
    }

    /* remove a range of elements */
    iterator erase(iterator first, iterator last) {
        while (first != last)
            erase(first++);     // don't erase than incr later!
        return iterator(last);
    }

    /* remove all contents of the list */
    void clear() {
        _Node* pCurrent = mpMiddle->getNext();
        _Node* pNext;

        while (pCurrent != mpMiddle) {
            pNext = pCurrent->getNext();
            delete pCurrent;
            pCurrent = pNext;
        }
        mpMiddle->setPrev(mpMiddle);
        mpMiddle->setNext(mpMiddle);
    }

    /*
     * Measure the distance between two iterators.  On exist, "first"
     * will be equal to "last".  The iterators must refer to the same
     * list.
     *
     * FIXME: This is actually a generic iterator function. It should be a 
     * template function at the top-level with specializations for things like
     * vector<>, which can just do pointer math). Here we limit it to
     * _ListIterator of the same type but different constness.
     */
    template<
        typename U,
        template <class> class CL,
        template <class> class CR
    > 
    ptrdiff_t distance(
            _ListIterator<U, CL> first, _ListIterator<U, CR> last) const 
    {
        ptrdiff_t count = 0;
        while (first != last) {
            ++first;
            ++count;
        }
        return count;
    }

private:
    /*
     * I want a _Node but don't need it to hold valid data.  More
     * to the point, I don't want T's constructor to fire, since it
     * might have side-effects or require arguments.  So, we do this
     * slightly uncouth storage alloc.
     */
    void prep() {
        mpMiddle = (_Node*) new unsigned char[sizeof(_Node)];
        mpMiddle->setPrev(mpMiddle);
        mpMiddle->setNext(mpMiddle);
    }

    /*
     * This node plays the role of "pointer to head" and "pointer to tail".
     * It sits in the middle of a circular list of nodes.  The iterator
     * runs around the circle until it encounters this one.
     */
    _Node*      mpMiddle;
};

/*
 * Assignment operator.
 *
 * The simplest way to do this would be to clear out the target list and
 * fill it with the source.  However, we can speed things along by
 * re-using existing elements.
 */
template<class T>
List<T>& List<T>::operator=(const List<T>& right)
{
    if (this == &right)
        return *this;       // self-assignment
    iterator firstDst = begin();
    iterator lastDst = end();
    const_iterator firstSrc = right.begin();
    const_iterator lastSrc = right.end();
    while (firstSrc != lastSrc && firstDst != lastDst)
        *firstDst++ = *firstSrc++;
    if (firstSrc == lastSrc)        // ran out of elements in source?
        erase(firstDst, lastDst);   // yes, erase any extras
    else
        insert(lastDst, firstSrc, lastSrc);     // copy remaining over
    return *this;
}

}; // namespace android

#endif // _LIBS_UTILS_LIST_H