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