michael@0: /*
michael@0:  * Copyright (C) 2005 The Android Open Source Project
michael@0:  *
michael@0:  * Licensed under the Apache License, Version 2.0 (the "License");
michael@0:  * you may not use this file except in compliance with the License.
michael@0:  * You may obtain a copy of the License at
michael@0:  *
michael@0:  *      http://www.apache.org/licenses/LICENSE-2.0
michael@0:  *
michael@0:  * Unless required by applicable law or agreed to in writing, software
michael@0:  * distributed under the License is distributed on an "AS IS" BASIS,
michael@0:  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
michael@0:  * See the License for the specific language governing permissions and
michael@0:  * limitations under the License.
michael@0:  */
michael@0: 
michael@0: //
michael@0: // Templated list class.  Normally we'd use STL, but we don't have that.
michael@0: // This class mimics STL's interfaces.
michael@0: //
michael@0: // Objects are copied into the list with the '=' operator or with copy-
michael@0: // construction, so if the compiler's auto-generated versions won't work for
michael@0: // you, define your own.
michael@0: //
michael@0: // The only class you want to use from here is "List".
michael@0: //
michael@0: #ifndef _LIBS_UTILS_LIST_H
michael@0: #define _LIBS_UTILS_LIST_H
michael@0: 
michael@0: #include <stddef.h>
michael@0: #include <stdint.h>
michael@0: 
michael@0: namespace android {
michael@0: 
michael@0: /*
michael@0:  * Doubly-linked list.  Instantiate with "List<MyClass> myList".
michael@0:  *
michael@0:  * Objects added to the list are copied using the assignment operator,
michael@0:  * so this must be defined.
michael@0:  */
michael@0: template<typename T> 
michael@0: class List 
michael@0: {
michael@0: protected:
michael@0:     /*
michael@0:      * One element in the list.
michael@0:      */
michael@0:     class _Node {
michael@0:     public:
michael@0:         explicit _Node(const T& val) : mVal(val) {}
michael@0:         ~_Node() {}
michael@0:         inline T& getRef() { return mVal; }
michael@0:         inline const T& getRef() const { return mVal; }
michael@0:         inline _Node* getPrev() const { return mpPrev; }
michael@0:         inline _Node* getNext() const { return mpNext; }
michael@0:         inline void setVal(const T& val) { mVal = val; }
michael@0:         inline void setPrev(_Node* ptr) { mpPrev = ptr; }
michael@0:         inline void setNext(_Node* ptr) { mpNext = ptr; }
michael@0:     private:
michael@0:         friend class List;
michael@0:         friend class _ListIterator;
michael@0:         T           mVal;
michael@0:         _Node*      mpPrev;
michael@0:         _Node*      mpNext;
michael@0:     };
michael@0: 
michael@0:     /*
michael@0:      * Iterator for walking through the list.
michael@0:      */
michael@0:     
michael@0:     template <typename TYPE>
michael@0:     struct CONST_ITERATOR {
michael@0:         typedef _Node const * NodePtr;
michael@0:         typedef const TYPE Type;
michael@0:     };
michael@0:     
michael@0:     template <typename TYPE>
michael@0:     struct NON_CONST_ITERATOR {
michael@0:         typedef _Node* NodePtr;
michael@0:         typedef TYPE Type;
michael@0:     };
michael@0:     
michael@0:     template<
michael@0:         typename U,
michael@0:         template <class> class Constness
michael@0:     > 
michael@0:     class _ListIterator {
michael@0:         typedef _ListIterator<U, Constness>     _Iter;
michael@0:         typedef typename Constness<U>::NodePtr  _NodePtr;
michael@0:         typedef typename Constness<U>::Type     _Type;
michael@0: 
michael@0:         explicit _ListIterator(_NodePtr ptr) : mpNode(ptr) {}
michael@0: 
michael@0:     public:
michael@0:         _ListIterator() {}
michael@0:         _ListIterator(const _Iter& rhs) : mpNode(rhs.mpNode) {}
michael@0:         ~_ListIterator() {}
michael@0:         
michael@0:         // this will handle conversions from iterator to const_iterator
michael@0:         // (and also all convertible iterators)
michael@0:         // Here, in this implementation, the iterators can be converted
michael@0:         // if the nodes can be converted
michael@0:         template<typename V> explicit 
michael@0:         _ListIterator(const V& rhs) : mpNode(rhs.mpNode) {}
michael@0:         
michael@0: 
michael@0:         /*
michael@0:          * Dereference operator.  Used to get at the juicy insides.
michael@0:          */
michael@0:         _Type& operator*() const { return mpNode->getRef(); }
michael@0:         _Type* operator->() const { return &(mpNode->getRef()); }
michael@0: 
michael@0:         /*
michael@0:          * Iterator comparison.
michael@0:          */
michael@0:         inline bool operator==(const _Iter& right) const { 
michael@0:             return mpNode == right.mpNode; }
michael@0:         
michael@0:         inline bool operator!=(const _Iter& right) const { 
michael@0:             return mpNode != right.mpNode; }
michael@0: 
michael@0:         /*
michael@0:          * handle comparisons between iterator and const_iterator
michael@0:          */
michael@0:         template<typename OTHER>
michael@0:         inline bool operator==(const OTHER& right) const { 
michael@0:             return mpNode == right.mpNode; }
michael@0:         
michael@0:         template<typename OTHER>
michael@0:         inline bool operator!=(const OTHER& right) const { 
michael@0:             return mpNode != right.mpNode; }
michael@0: 
michael@0:         /*
michael@0:          * Incr/decr, used to move through the list.
michael@0:          */
michael@0:         inline _Iter& operator++() {     // pre-increment
michael@0:             mpNode = mpNode->getNext();
michael@0:             return *this;
michael@0:         }
michael@0:         const _Iter operator++(int) {    // post-increment
michael@0:             _Iter tmp(*this);
michael@0:             mpNode = mpNode->getNext();
michael@0:             return tmp;
michael@0:         }
michael@0:         inline _Iter& operator--() {     // pre-increment
michael@0:             mpNode = mpNode->getPrev();
michael@0:             return *this;
michael@0:         }
michael@0:         const _Iter operator--(int) {   // post-increment
michael@0:             _Iter tmp(*this);
michael@0:             mpNode = mpNode->getPrev();
michael@0:             return tmp;
michael@0:         }
michael@0: 
michael@0:         inline _NodePtr getNode() const { return mpNode; }
michael@0: 
michael@0:         _NodePtr mpNode;    /* should be private, but older gcc fails */
michael@0:     private:
michael@0:         friend class List;
michael@0:     };
michael@0: 
michael@0: public:
michael@0:     List() {
michael@0:         prep();
michael@0:     }
michael@0:     List(const List<T>& src) {      // copy-constructor
michael@0:         prep();
michael@0:         insert(begin(), src.begin(), src.end());
michael@0:     }
michael@0:     virtual ~List() {
michael@0:         clear();
michael@0:         delete[] (unsigned char*) mpMiddle;
michael@0:     }
michael@0: 
michael@0:     typedef _ListIterator<T, NON_CONST_ITERATOR> iterator;
michael@0:     typedef _ListIterator<T, CONST_ITERATOR> const_iterator;
michael@0: 
michael@0:     List<T>& operator=(const List<T>& right);
michael@0: 
michael@0:     /* returns true if the list is empty */
michael@0:     inline bool empty() const { return mpMiddle->getNext() == mpMiddle; }
michael@0: 
michael@0:     /* return #of elements in list */
michael@0:     size_t size() const {
michael@0:         return size_t(distance(begin(), end()));
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Return the first element or one past the last element.  The
michael@0:      * _Node* we're returning is converted to an "iterator" by a
michael@0:      * constructor in _ListIterator.
michael@0:      */
michael@0:     inline iterator begin() { 
michael@0:         return iterator(mpMiddle->getNext()); 
michael@0:     }
michael@0:     inline const_iterator begin() const { 
michael@0:         return const_iterator(const_cast<_Node const*>(mpMiddle->getNext())); 
michael@0:     }
michael@0:     inline iterator end() { 
michael@0:         return iterator(mpMiddle); 
michael@0:     }
michael@0:     inline const_iterator end() const { 
michael@0:         return const_iterator(const_cast<_Node const*>(mpMiddle)); 
michael@0:     }
michael@0: 
michael@0:     /* add the object to the head or tail of the list */
michael@0:     void push_front(const T& val) { insert(begin(), val); }
michael@0:     void push_back(const T& val) { insert(end(), val); }
michael@0: 
michael@0:     /* insert before the current node; returns iterator at new node */
michael@0:     iterator insert(iterator posn, const T& val) 
michael@0:     {
michael@0:         _Node* newNode = new _Node(val);        // alloc & copy-construct
michael@0:         newNode->setNext(posn.getNode());
michael@0:         newNode->setPrev(posn.getNode()->getPrev());
michael@0:         posn.getNode()->getPrev()->setNext(newNode);
michael@0:         posn.getNode()->setPrev(newNode);
michael@0:         return iterator(newNode);
michael@0:     }
michael@0: 
michael@0:     /* insert a range of elements before the current node */
michael@0:     void insert(iterator posn, const_iterator first, const_iterator last) {
michael@0:         for ( ; first != last; ++first)
michael@0:             insert(posn, *first);
michael@0:     }
michael@0: 
michael@0:     /* remove one entry; returns iterator at next node */
michael@0:     iterator erase(iterator posn) {
michael@0:         _Node* pNext = posn.getNode()->getNext();
michael@0:         _Node* pPrev = posn.getNode()->getPrev();
michael@0:         pPrev->setNext(pNext);
michael@0:         pNext->setPrev(pPrev);
michael@0:         delete posn.getNode();
michael@0:         return iterator(pNext);
michael@0:     }
michael@0: 
michael@0:     /* remove a range of elements */
michael@0:     iterator erase(iterator first, iterator last) {
michael@0:         while (first != last)
michael@0:             erase(first++);     // don't erase than incr later!
michael@0:         return iterator(last);
michael@0:     }
michael@0: 
michael@0:     /* remove all contents of the list */
michael@0:     void clear() {
michael@0:         _Node* pCurrent = mpMiddle->getNext();
michael@0:         _Node* pNext;
michael@0: 
michael@0:         while (pCurrent != mpMiddle) {
michael@0:             pNext = pCurrent->getNext();
michael@0:             delete pCurrent;
michael@0:             pCurrent = pNext;
michael@0:         }
michael@0:         mpMiddle->setPrev(mpMiddle);
michael@0:         mpMiddle->setNext(mpMiddle);
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Measure the distance between two iterators.  On exist, "first"
michael@0:      * will be equal to "last".  The iterators must refer to the same
michael@0:      * list.
michael@0:      *
michael@0:      * FIXME: This is actually a generic iterator function. It should be a 
michael@0:      * template function at the top-level with specializations for things like
michael@0:      * vector<>, which can just do pointer math). Here we limit it to
michael@0:      * _ListIterator of the same type but different constness.
michael@0:      */
michael@0:     template<
michael@0:         typename U,
michael@0:         template <class> class CL,
michael@0:         template <class> class CR
michael@0:     > 
michael@0:     ptrdiff_t distance(
michael@0:             _ListIterator<U, CL> first, _ListIterator<U, CR> last) const 
michael@0:     {
michael@0:         ptrdiff_t count = 0;
michael@0:         while (first != last) {
michael@0:             ++first;
michael@0:             ++count;
michael@0:         }
michael@0:         return count;
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     /*
michael@0:      * I want a _Node but don't need it to hold valid data.  More
michael@0:      * to the point, I don't want T's constructor to fire, since it
michael@0:      * might have side-effects or require arguments.  So, we do this
michael@0:      * slightly uncouth storage alloc.
michael@0:      */
michael@0:     void prep() {
michael@0:         mpMiddle = (_Node*) new unsigned char[sizeof(_Node)];
michael@0:         mpMiddle->setPrev(mpMiddle);
michael@0:         mpMiddle->setNext(mpMiddle);
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * This node plays the role of "pointer to head" and "pointer to tail".
michael@0:      * It sits in the middle of a circular list of nodes.  The iterator
michael@0:      * runs around the circle until it encounters this one.
michael@0:      */
michael@0:     _Node*      mpMiddle;
michael@0: };
michael@0: 
michael@0: /*
michael@0:  * Assignment operator.
michael@0:  *
michael@0:  * The simplest way to do this would be to clear out the target list and
michael@0:  * fill it with the source.  However, we can speed things along by
michael@0:  * re-using existing elements.
michael@0:  */
michael@0: template<class T>
michael@0: List<T>& List<T>::operator=(const List<T>& right)
michael@0: {
michael@0:     if (this == &right)
michael@0:         return *this;       // self-assignment
michael@0:     iterator firstDst = begin();
michael@0:     iterator lastDst = end();
michael@0:     const_iterator firstSrc = right.begin();
michael@0:     const_iterator lastSrc = right.end();
michael@0:     while (firstSrc != lastSrc && firstDst != lastDst)
michael@0:         *firstDst++ = *firstSrc++;
michael@0:     if (firstSrc == lastSrc)        // ran out of elements in source?
michael@0:         erase(firstDst, lastDst);   // yes, erase any extras
michael@0:     else
michael@0:         insert(lastDst, firstSrc, lastSrc);     // copy remaining over
michael@0:     return *this;
michael@0: }
michael@0: 
michael@0: }; // namespace android
michael@0: 
michael@0: #endif // _LIBS_UTILS_LIST_H