1cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project/* 2cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * Copyright (C) 2005 The Android Open Source Project 3cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * 4cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * you may not use this file except in compliance with the License. 6cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * You may obtain a copy of the License at 7cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * 8cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * 10cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * See the License for the specific language governing permissions and 14cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * limitations under the License. 15cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project */ 16cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 17cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// 18cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// Templated list class. Normally we'd use STL, but we don't have that. 19cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// This class mimics STL's interfaces. 20cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// 21cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// Objects are copied into the list with the '=' operator or with copy- 22cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// construction, so if the compiler's auto-generated versions won't work for 23cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// you, define your own. 24cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// 250077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian// The only class you want to use from here is "List". 26cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// 27cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#ifndef _LIBS_UTILS_LIST_H 28cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#define _LIBS_UTILS_LIST_H 29cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 300077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian#include <stddef.h> 310077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian#include <stdint.h> 32cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 330077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopiannamespace android { 34cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 35cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project/* 360077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * Doubly-linked list. Instantiate with "List<MyClass> myList". 370077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * 380077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * Objects added to the list are copied using the assignment operator, 390077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * so this must be defined. 40cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project */ 410077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopiantemplate<typename T> 420077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopianclass List 430077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian{ 440077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopianprotected: 45cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /* 460077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * One element in the list. 47cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project */ 480077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian class _Node { 490077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian public: 500077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian explicit _Node(const T& val) : mVal(val) {} 510077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian ~_Node() {} 520077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline T& getRef() { return mVal; } 530077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline const T& getRef() const { return mVal; } 540077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline _Node* getPrev() const { return mpPrev; } 550077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline _Node* getNext() const { return mpNext; } 560077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline void setVal(const T& val) { mVal = val; } 570077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline void setPrev(_Node* ptr) { mpPrev = ptr; } 580077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline void setNext(_Node* ptr) { mpNext = ptr; } 590077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian private: 600077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian friend class List; 610077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian friend class _ListIterator; 620077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian T mVal; 630077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian _Node* mpPrev; 640077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian _Node* mpNext; 650077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian }; 66cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 67cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /* 680077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * Iterator for walking through the list. 69cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project */ 700077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian 710077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian template <typename TYPE> 720077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian struct CONST_ITERATOR { 730077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian typedef _Node const * NodePtr; 740077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian typedef const TYPE Type; 750077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian }; 760077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian 770077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian template <typename TYPE> 780077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian struct NON_CONST_ITERATOR { 790077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian typedef _Node* NodePtr; 800077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian typedef TYPE Type; 810077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian }; 820077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian 830077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian template< 840077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian typename U, 850077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian template <class> class Constness 860077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian > 870077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian class _ListIterator { 880077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian typedef _ListIterator<U, Constness> _Iter; 890077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian typedef typename Constness<U>::NodePtr _NodePtr; 900077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian typedef typename Constness<U>::Type _Type; 910077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian 920077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian explicit _ListIterator(_NodePtr ptr) : mpNode(ptr) {} 930077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian 940077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian public: 950077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian _ListIterator() {} 960077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian _ListIterator(const _Iter& rhs) : mpNode(rhs.mpNode) {} 970077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian ~_ListIterator() {} 980077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian 990077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian // this will handle conversions from iterator to const_iterator 1000077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian // (and also all convertible iterators) 1010077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian // Here, in this implementation, the iterators can be converted 1020077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian // if the nodes can be converted 1030077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian template<typename V> explicit 1040077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian _ListIterator(const V& rhs) : mpNode(rhs.mpNode) {} 1050077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian 1060077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian 1070077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian /* 1080077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * Dereference operator. Used to get at the juicy insides. 1090077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian */ 1100077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian _Type& operator*() const { return mpNode->getRef(); } 1110077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian _Type* operator->() const { return &(mpNode->getRef()); } 1120077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian 1130077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian /* 1140077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * Iterator comparison. 1150077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian */ 1160077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline bool operator==(const _Iter& right) const { 1170077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return mpNode == right.mpNode; } 1180077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian 1190077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline bool operator!=(const _Iter& right) const { 1200077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return mpNode != right.mpNode; } 1210077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian 1220077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian /* 1230077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * handle comparisons between iterator and const_iterator 1240077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian */ 1250077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian template<typename OTHER> 1260077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline bool operator==(const OTHER& right) const { 1270077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return mpNode == right.mpNode; } 1280077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian 1290077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian template<typename OTHER> 1300077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline bool operator!=(const OTHER& right) const { 1310077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return mpNode != right.mpNode; } 1320077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian 1330077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian /* 1340077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * Incr/decr, used to move through the list. 1350077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian */ 1360077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline _Iter& operator++() { // pre-increment 1370077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian mpNode = mpNode->getNext(); 1380077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return *this; 1390077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian } 1400077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian const _Iter operator++(int) { // post-increment 1410077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian _Iter tmp(*this); 1420077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian mpNode = mpNode->getNext(); 1430077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return tmp; 1440077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian } 1450077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline _Iter& operator--() { // pre-increment 1460077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian mpNode = mpNode->getPrev(); 1470077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return *this; 1480077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian } 1490077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian const _Iter operator--(int) { // post-increment 1500077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian _Iter tmp(*this); 1510077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian mpNode = mpNode->getPrev(); 1520077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return tmp; 1530077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian } 154cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 1550077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline _NodePtr getNode() const { return mpNode; } 156cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 15734ed82706a56c94993efa2b679ff1520e5db5bb7Andy McFadden _NodePtr mpNode; /* should be private, but older gcc fails */ 1580077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian private: 1590077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian friend class List; 1600077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian }; 161cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 162cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectpublic: 1630077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian List() { 164cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project prep(); 165cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 166cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project List(const List<T>& src) { // copy-constructor 167cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project prep(); 168cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project insert(begin(), src.begin(), src.end()); 169cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 1700077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian virtual ~List() { 171cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project clear(); 172cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project delete[] (unsigned char*) mpMiddle; 173cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 174cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 1750077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian typedef _ListIterator<T, NON_CONST_ITERATOR> iterator; 1760077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian typedef _ListIterator<T, CONST_ITERATOR> const_iterator; 177cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 178cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project List<T>& operator=(const List<T>& right); 179cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 180cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /* returns true if the list is empty */ 1810077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline bool empty() const { return mpMiddle->getNext() == mpMiddle; } 182cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 183cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /* return #of elements in list */ 1840077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian size_t size() const { 1850077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return size_t(distance(begin(), end())); 186cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 187cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 188cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /* 189cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * Return the first element or one past the last element. The 1900077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * _Node* we're returning is converted to an "iterator" by a 191cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * constructor in _ListIterator. 192cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project */ 1930077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline iterator begin() { 1940077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return iterator(mpMiddle->getNext()); 1950077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian } 1960077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline const_iterator begin() const { 1970077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return const_iterator(const_cast<_Node const*>(mpMiddle->getNext())); 1980077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian } 1990077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline iterator end() { 2000077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return iterator(mpMiddle); 2010077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian } 2020077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian inline const_iterator end() const { 2030077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return const_iterator(const_cast<_Node const*>(mpMiddle)); 2040077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian } 205cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 206cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /* add the object to the head or tail of the list */ 207cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void push_front(const T& val) { insert(begin(), val); } 208cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void push_back(const T& val) { insert(end(), val); } 209cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 210cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /* insert before the current node; returns iterator at new node */ 2110077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian iterator insert(iterator posn, const T& val) 2120077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian { 213cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _Node* newNode = new _Node(val); // alloc & copy-construct 214cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project newNode->setNext(posn.getNode()); 215cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project newNode->setPrev(posn.getNode()->getPrev()); 216cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project posn.getNode()->getPrev()->setNext(newNode); 217cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project posn.getNode()->setPrev(newNode); 2180077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return iterator(newNode); 219cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 220cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 221cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /* insert a range of elements before the current node */ 222cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void insert(iterator posn, const_iterator first, const_iterator last) { 223cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project for ( ; first != last; ++first) 224cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project insert(posn, *first); 225cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 226cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 227cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /* remove one entry; returns iterator at next node */ 228cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project iterator erase(iterator posn) { 229cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _Node* pNext = posn.getNode()->getNext(); 230cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _Node* pPrev = posn.getNode()->getPrev(); 231cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project pPrev->setNext(pNext); 232cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project pNext->setPrev(pPrev); 233cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project delete posn.getNode(); 2340077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return iterator(pNext); 235cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 236cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 237cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /* remove a range of elements */ 238cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project iterator erase(iterator first, iterator last) { 239cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project while (first != last) 240cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project erase(first++); // don't erase than incr later! 2410077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian return iterator(last); 242cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 243cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 244cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /* remove all contents of the list */ 2450077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian void clear() { 246cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _Node* pCurrent = mpMiddle->getNext(); 247cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _Node* pNext; 248cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 249cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project while (pCurrent != mpMiddle) { 250cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project pNext = pCurrent->getNext(); 251cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project delete pCurrent; 252cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project pCurrent = pNext; 253cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 254cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mpMiddle->setPrev(mpMiddle); 255cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mpMiddle->setNext(mpMiddle); 256cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 257cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 258cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /* 259cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * Measure the distance between two iterators. On exist, "first" 260cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * will be equal to "last". The iterators must refer to the same 261cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * list. 262cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * 2630077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * FIXME: This is actually a generic iterator function. It should be a 2640077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * template function at the top-level with specializations for things like 2650077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * vector<>, which can just do pointer math). Here we limit it to 2660077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * _ListIterator of the same type but different constness. 267cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project */ 2680077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian template< 2690077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian typename U, 2700077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian template <class> class CL, 2710077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian template <class> class CR 2720077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian > 2730077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian ptrdiff_t distance( 2740077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian _ListIterator<U, CL> first, _ListIterator<U, CR> last) const 2750077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian { 2760077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian ptrdiff_t count = 0; 277cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project while (first != last) { 278cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ++first; 279cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ++count; 280cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 281cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return count; 282cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 283cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 284cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectprivate: 285cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /* 2860077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian * I want a _Node but don't need it to hold valid data. More 287cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * to the point, I don't want T's constructor to fire, since it 288cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * might have side-effects or require arguments. So, we do this 289cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * slightly uncouth storage alloc. 290cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project */ 2910077a0dd692e38ee7d90725727f311f0f9c24d04Mathias Agopian void prep() { 292cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mpMiddle = (_Node*) new unsigned char[sizeof(_Node)]; 293cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mpMiddle->setPrev(mpMiddle); 294cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mpMiddle->setNext(mpMiddle); 295cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 296cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 297cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /* 298cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * This node plays the role of "pointer to head" and "pointer to tail". 299cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * It sits in the middle of a circular list of nodes. The iterator 300cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * runs around the circle until it encounters this one. 301cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project */ 302cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _Node* mpMiddle; 303cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project}; 304cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 305cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project/* 306cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * Assignment operator. 307cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * 308cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * The simplest way to do this would be to clear out the target list and 309cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * fill it with the source. However, we can speed things along by 310cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * re-using existing elements. 311cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project */ 312cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projecttemplate<class T> 313cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source ProjectList<T>& List<T>::operator=(const List<T>& right) 314cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 315cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (this == &right) 316cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return *this; // self-assignment 317cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project iterator firstDst = begin(); 318cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project iterator lastDst = end(); 319cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const_iterator firstSrc = right.begin(); 320cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const_iterator lastSrc = right.end(); 321cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project while (firstSrc != lastSrc && firstDst != lastDst) 322cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project *firstDst++ = *firstSrc++; 323cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (firstSrc == lastSrc) // ran out of elements in source? 324cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project erase(firstDst, lastDst); // yes, erase any extras 325cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project else 326cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project insert(lastDst, firstSrc, lastSrc); // copy remaining over 327cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return *this; 328cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 329cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 330cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project}; // namespace android 331cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 332cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#endif // _LIBS_UTILS_LIST_H 333