List.h revision f460f19510f9119d7b441403f8f6ba0b7f5fc267
1edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* 2edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Copyright (C) 2005 The Android Open Source Project 3edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * 4edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * you may not use this file except in compliance with the License. 6edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * You may obtain a copy of the License at 7edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * 8edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * 10edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * See the License for the specific language governing permissions and 14edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * limitations under the License. 15edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 16edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 17edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// 18edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// Templated list class. Normally we'd use STL, but we don't have that. 19edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// This class mimics STL's interfaces. 20edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// 21edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// Objects are copied into the list with the '=' operator or with copy- 22edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// construction, so if the compiler's auto-generated versions won't work for 23edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// you, define your own. 24edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// 25cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian// The only class you want to use from here is "List". 26edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// 27edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#ifndef _LIBS_UTILS_LIST_H 28edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#define _LIBS_UTILS_LIST_H 29edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 30cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian#include <stddef.h> 31cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian#include <stdint.h> 32edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 33cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopiannamespace android { 34edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 35edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* 36cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * Doubly-linked list. Instantiate with "List<MyClass> myList". 37cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * 38cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * Objects added to the list are copied using the assignment operator, 39cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * so this must be defined. 40edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 41cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopiantemplate<typename T> 42cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopianclass List 43cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian{ 44cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopianprotected: 45edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* 46cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * One element in the list. 47edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 48cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian class _Node { 49cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian public: 50cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian explicit _Node(const T& val) : mVal(val) {} 51cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian ~_Node() {} 52cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline T& getRef() { return mVal; } 53cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline const T& getRef() const { return mVal; } 54cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline _Node* getPrev() const { return mpPrev; } 55cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline _Node* getNext() const { return mpNext; } 56cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline void setVal(const T& val) { mVal = val; } 57cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline void setPrev(_Node* ptr) { mpPrev = ptr; } 58cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline void setNext(_Node* ptr) { mpNext = ptr; } 59cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian private: 60cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian friend class List; 61cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian friend class _ListIterator; 62cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian T mVal; 63cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian _Node* mpPrev; 64cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian _Node* mpNext; 65cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian }; 66edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 67edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* 68cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * Iterator for walking through the list. 69edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 70cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian 71cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian template <typename TYPE> 72cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian struct CONST_ITERATOR { 73cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian typedef _Node const * NodePtr; 74cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian typedef const TYPE Type; 75cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian }; 76cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian 77cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian template <typename TYPE> 78cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian struct NON_CONST_ITERATOR { 79cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian typedef _Node* NodePtr; 80cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian typedef TYPE Type; 81cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian }; 82cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian 83cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian template< 84cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian typename U, 85cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian template <class> class Constness 86cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian > 87cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian class _ListIterator { 88cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian typedef _ListIterator<U, Constness> _Iter; 89cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian typedef typename Constness<U>::NodePtr _NodePtr; 90cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian typedef typename Constness<U>::Type _Type; 91cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian 92cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian explicit _ListIterator(_NodePtr ptr) : mpNode(ptr) {} 93cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian 94cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian public: 95cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian _ListIterator() {} 96cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian _ListIterator(const _Iter& rhs) : mpNode(rhs.mpNode) {} 97cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian ~_ListIterator() {} 98cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian 99cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian // this will handle conversions from iterator to const_iterator 100cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian // (and also all convertible iterators) 101cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian // Here, in this implementation, the iterators can be converted 102cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian // if the nodes can be converted 103cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian template<typename V> explicit 104cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian _ListIterator(const V& rhs) : mpNode(rhs.mpNode) {} 105cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian 106cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian 107cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian /* 108cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * Dereference operator. Used to get at the juicy insides. 109cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian */ 110cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian _Type& operator*() const { return mpNode->getRef(); } 111cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian _Type* operator->() const { return &(mpNode->getRef()); } 112cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian 113cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian /* 114cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * Iterator comparison. 115cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian */ 116cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline bool operator==(const _Iter& right) const { 117cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return mpNode == right.mpNode; } 118cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian 119cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline bool operator!=(const _Iter& right) const { 120cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return mpNode != right.mpNode; } 121cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian 122cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian /* 123cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * handle comparisons between iterator and const_iterator 124cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian */ 125cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian template<typename OTHER> 126cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline bool operator==(const OTHER& right) const { 127cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return mpNode == right.mpNode; } 128cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian 129cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian template<typename OTHER> 130cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline bool operator!=(const OTHER& right) const { 131cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return mpNode != right.mpNode; } 132cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian 133cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian /* 134cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * Incr/decr, used to move through the list. 135cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian */ 136cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline _Iter& operator++() { // pre-increment 137cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian mpNode = mpNode->getNext(); 138cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return *this; 139cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian } 140cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian const _Iter operator++(int) { // post-increment 141cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian _Iter tmp(*this); 142cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian mpNode = mpNode->getNext(); 143cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return tmp; 144cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian } 145cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline _Iter& operator--() { // pre-increment 146cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian mpNode = mpNode->getPrev(); 147cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return *this; 148cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian } 149cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian const _Iter operator--(int) { // post-increment 150cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian _Iter tmp(*this); 151cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian mpNode = mpNode->getPrev(); 152cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return tmp; 153cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian } 154edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 155cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline _NodePtr getNode() const { return mpNode; } 156edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 157f460f19510f9119d7b441403f8f6ba0b7f5fc267Andy McFadden _NodePtr mpNode; /* should be private, but older gcc fails */ 158cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian private: 159cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian friend class List; 160cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian }; 161edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 162edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectpublic: 163cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian List() { 164edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project prep(); 165edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 166edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project List(const List<T>& src) { // copy-constructor 167edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project prep(); 168edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project insert(begin(), src.begin(), src.end()); 169edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 170cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian virtual ~List() { 171edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project clear(); 172edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project delete[] (unsigned char*) mpMiddle; 173edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 174edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 175cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian typedef _ListIterator<T, NON_CONST_ITERATOR> iterator; 176cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian typedef _ListIterator<T, CONST_ITERATOR> const_iterator; 177edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 178edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project List<T>& operator=(const List<T>& right); 179edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 180edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* returns true if the list is empty */ 181cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline bool empty() const { return mpMiddle->getNext() == mpMiddle; } 182edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 183edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* return #of elements in list */ 184cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian size_t size() const { 185cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return size_t(distance(begin(), end())); 186edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 187edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 188edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* 189edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Return the first element or one past the last element. The 190cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * _Node* we're returning is converted to an "iterator" by a 191edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * constructor in _ListIterator. 192edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 193cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline iterator begin() { 194cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return iterator(mpMiddle->getNext()); 195cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian } 196cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline const_iterator begin() const { 197cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return const_iterator(const_cast<_Node const*>(mpMiddle->getNext())); 198cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian } 199cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline iterator end() { 200cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return iterator(mpMiddle); 201cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian } 202cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian inline const_iterator end() const { 203cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return const_iterator(const_cast<_Node const*>(mpMiddle)); 204cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian } 205edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 206edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* add the object to the head or tail of the list */ 207edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void push_front(const T& val) { insert(begin(), val); } 208edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void push_back(const T& val) { insert(end(), val); } 209edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 210edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* insert before the current node; returns iterator at new node */ 211cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian iterator insert(iterator posn, const T& val) 212cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian { 213edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* newNode = new _Node(val); // alloc & copy-construct 214edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project newNode->setNext(posn.getNode()); 215edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project newNode->setPrev(posn.getNode()->getPrev()); 216edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project posn.getNode()->getPrev()->setNext(newNode); 217edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project posn.getNode()->setPrev(newNode); 218cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return iterator(newNode); 219edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 220edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 221edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* insert a range of elements before the current node */ 222edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void insert(iterator posn, const_iterator first, const_iterator last) { 223edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project for ( ; first != last; ++first) 224edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project insert(posn, *first); 225edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 226edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 227edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* remove one entry; returns iterator at next node */ 228edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project iterator erase(iterator posn) { 229edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* pNext = posn.getNode()->getNext(); 230edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* pPrev = posn.getNode()->getPrev(); 231edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project pPrev->setNext(pNext); 232edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project pNext->setPrev(pPrev); 233edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project delete posn.getNode(); 234cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return iterator(pNext); 235edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 236edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 237edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* remove a range of elements */ 238edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project iterator erase(iterator first, iterator last) { 239edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project while (first != last) 240edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project erase(first++); // don't erase than incr later! 241cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian return iterator(last); 242edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 243edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 244edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* remove all contents of the list */ 245cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian void clear() { 246edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* pCurrent = mpMiddle->getNext(); 247edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* pNext; 248edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 249edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project while (pCurrent != mpMiddle) { 250edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project pNext = pCurrent->getNext(); 251edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project delete pCurrent; 252edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project pCurrent = pNext; 253edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 254edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mpMiddle->setPrev(mpMiddle); 255edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mpMiddle->setNext(mpMiddle); 256edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 257edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 258edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* 259edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Measure the distance between two iterators. On exist, "first" 260edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * will be equal to "last". The iterators must refer to the same 261edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * list. 262edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * 263cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * FIXME: This is actually a generic iterator function. It should be a 264cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * template function at the top-level with specializations for things like 265cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * vector<>, which can just do pointer math). Here we limit it to 266cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * _ListIterator of the same type but different constness. 267edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 268cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian template< 269cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian typename U, 270cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian template <class> class CL, 271cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian template <class> class CR 272cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian > 273cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian ptrdiff_t distance( 274cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian _ListIterator<U, CL> first, _ListIterator<U, CR> last) const 275cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian { 276cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian ptrdiff_t count = 0; 277edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project while (first != last) { 278edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ++first; 279edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ++count; 280edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 281edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return count; 282edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 283edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 284edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectprivate: 285edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* 286cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian * I want a _Node but don't need it to hold valid data. More 287edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * to the point, I don't want T's constructor to fire, since it 288edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * might have side-effects or require arguments. So, we do this 289edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * slightly uncouth storage alloc. 290edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 291cbb0d628438809163e52ec28b40c32eb82c5a233Mathias Agopian void prep() { 292edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mpMiddle = (_Node*) new unsigned char[sizeof(_Node)]; 293edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mpMiddle->setPrev(mpMiddle); 294edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mpMiddle->setNext(mpMiddle); 295edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 296edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 297edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* 298edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * This node plays the role of "pointer to head" and "pointer to tail". 299edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * It sits in the middle of a circular list of nodes. The iterator 300edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * runs around the circle until it encounters this one. 301edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 302edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* mpMiddle; 303edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project}; 304edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 305edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* 306edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Assignment operator. 307edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * 308edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * The simplest way to do this would be to clear out the target list and 309edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * fill it with the source. However, we can speed things along by 310edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * re-using existing elements. 311edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 312edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projecttemplate<class T> 313edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectList<T>& List<T>::operator=(const List<T>& right) 314edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 315edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (this == &right) 316edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return *this; // self-assignment 317edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project iterator firstDst = begin(); 318edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project iterator lastDst = end(); 319edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const_iterator firstSrc = right.begin(); 320edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const_iterator lastSrc = right.end(); 321edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project while (firstSrc != lastSrc && firstDst != lastDst) 322edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project *firstDst++ = *firstSrc++; 323edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (firstSrc == lastSrc) // ran out of elements in source? 324edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project erase(firstDst, lastDst); // yes, erase any extras 325edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project else 326edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project insert(lastDst, firstSrc, lastSrc); // copy remaining over 327edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return *this; 328edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 329edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 330edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project}; // namespace android 331edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 332edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#endif // _LIBS_UTILS_LIST_H 333