List.h revision edbf3b6af777b721cd2a1ef461947e51e88241e1
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// 25edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// The only class you want to use from here is "List". Do not use classes 26edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// starting with "_" directly. 27edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// 28edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#ifndef _LIBS_UTILS_LIST_H 29edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#define _LIBS_UTILS_LIST_H 30edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 31edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectnamespace android { 32edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 33edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* 34edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * One element in the list. 35edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 36edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projecttemplate<class T> class _ListNode { 37edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectpublic: 38edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project typedef _ListNode<T> _Node; 39edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 40edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _ListNode(const T& val) : mVal(val) {} 41edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ~_ListNode(void) {} 42edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 43edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project T& getRef(void) { return mVal; } 44edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void setVal(const T& val) { mVal = val; } 45edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 46edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* getPrev(void) const { return mpPrev; } 47edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void setPrev(_Node* ptr) { mpPrev = ptr; } 48edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* getNext(void) const { return mpNext; } 49edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void setNext(_Node* ptr) { mpNext = ptr; } 50edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 51edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectprivate: 52edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project T mVal; 53edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* mpPrev; 54edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* mpNext; 55edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project}; 56edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 57edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* 58edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Iterator for walking through the list. 59edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 60edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projecttemplate<class T, class Tref> class _ListIterator { 61edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectpublic: 62edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project typedef _ListIterator<T,Tref> _Iter; 63edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project typedef _ListNode<T> _Node; 64edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 65edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _ListIterator(void) {} 66edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _ListIterator(_Node* ptr) : mpNode(ptr) {} 67edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ~_ListIterator(void) {} 68edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 69edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* 70edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Dereference operator. Used to get at the juicy insides. 71edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 72edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project Tref operator*() const { return mpNode->getRef(); } 73edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 74edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* 75edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Iterator comparison. 76edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 77edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project bool operator==(const _Iter& right) const { return mpNode == right.mpNode; } 78edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project bool operator!=(const _Iter& right) const { return mpNode != right.mpNode; } 79edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 80edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* 81edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Incr/decr, used to move through the list. 82edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 83edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Iter& operator++(void) { // pre-increment 84edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mpNode = mpNode->getNext(); 85edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return *this; 86edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 87edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Iter operator++(int) { // post-increment 88edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Iter tmp = *this; 89edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ++*this; 90edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return tmp; 91edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 92edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Iter& operator--(void) { // pre-increment 93edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mpNode = mpNode->getPrev(); 94edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return *this; 95edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 96edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Iter operator--(int) { // post-increment 97edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Iter tmp = *this; 98edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project --*this; 99edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return tmp; 100edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 101edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 102edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* getNode(void) const { return mpNode; } 103edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 104edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectprivate: 105edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* mpNode; 106edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project}; 107edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 108edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 109edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* 110edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Doubly-linked list. Instantiate with "List<MyClass> myList". 111edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * 112edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Objects added to the list are copied using the assignment operator, 113edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * so this must be defined. 114edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 115edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projecttemplate<class T> class List { 116edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectpublic: 117edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project typedef _ListNode<T> _Node; 118edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 119edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project List(void) { 120edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project prep(); 121edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 122edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project List(const List<T>& src) { // copy-constructor 123edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project prep(); 124edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project insert(begin(), src.begin(), src.end()); 125edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 126edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project virtual ~List(void) { 127edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project clear(); 128edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project delete[] (unsigned char*) mpMiddle; 129edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 130edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 131edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project typedef _ListIterator<T,T&> iterator; 132edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project typedef _ListIterator<T, const T&> const_iterator; 133edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 134edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project List<T>& operator=(const List<T>& right); 135edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 136edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* returns true if the list is empty */ 137edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project bool empty(void) const { return mpMiddle->getNext() == mpMiddle; } 138edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 139edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* return #of elements in list */ 140edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project unsigned int size(void) const { 141edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return distance(begin(), end()); 142edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 143edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 144edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* 145edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Return the first element or one past the last element. The 146edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * _ListNode* we're returning is converted to an "iterator" by a 147edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * constructor in _ListIterator. 148edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 149edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project iterator begin() { return mpMiddle->getNext(); } 150edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const_iterator begin() const { return mpMiddle->getNext(); } 151edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project iterator end() { return mpMiddle; } 152edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const_iterator end() const { return mpMiddle; } 153edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 154edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* add the object to the head or tail of the list */ 155edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void push_front(const T& val) { insert(begin(), val); } 156edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void push_back(const T& val) { insert(end(), val); } 157edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 158edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* insert before the current node; returns iterator at new node */ 159edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project iterator insert(iterator posn, const T& val) { 160edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* newNode = new _Node(val); // alloc & copy-construct 161edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project newNode->setNext(posn.getNode()); 162edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project newNode->setPrev(posn.getNode()->getPrev()); 163edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project posn.getNode()->getPrev()->setNext(newNode); 164edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project posn.getNode()->setPrev(newNode); 165edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return newNode; 166edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 167edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 168edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* insert a range of elements before the current node */ 169edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void insert(iterator posn, const_iterator first, const_iterator last) { 170edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project for ( ; first != last; ++first) 171edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project insert(posn, *first); 172edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 173edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 174edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* remove one entry; returns iterator at next node */ 175edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project iterator erase(iterator posn) { 176edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* pNext = posn.getNode()->getNext(); 177edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* pPrev = posn.getNode()->getPrev(); 178edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project pPrev->setNext(pNext); 179edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project pNext->setPrev(pPrev); 180edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project delete posn.getNode(); 181edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return pNext; 182edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 183edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 184edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* remove a range of elements */ 185edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project iterator erase(iterator first, iterator last) { 186edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project while (first != last) 187edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project erase(first++); // don't erase than incr later! 188edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return last; 189edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 190edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 191edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* remove all contents of the list */ 192edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void clear(void) { 193edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* pCurrent = mpMiddle->getNext(); 194edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* pNext; 195edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 196edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project while (pCurrent != mpMiddle) { 197edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project pNext = pCurrent->getNext(); 198edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project delete pCurrent; 199edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project pCurrent = pNext; 200edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 201edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mpMiddle->setPrev(mpMiddle); 202edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mpMiddle->setNext(mpMiddle); 203edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 204edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 205edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* 206edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Measure the distance between two iterators. On exist, "first" 207edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * will be equal to "last". The iterators must refer to the same 208edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * list. 209edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * 210edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * (This is actually a generic iterator function. It should be part 211edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * of some other class, possibly an iterator base class. It needs to 212edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * know the difference between a list, which has to march through, 213edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * and a vector, which can just do pointer math.) 214edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 215edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project unsigned int distance(iterator first, iterator last) { 216edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project unsigned int count = 0; 217edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project while (first != last) { 218edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ++first; 219edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ++count; 220edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 221edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return count; 222edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 223edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project unsigned int distance(const_iterator first, const_iterator last) const { 224edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project unsigned int count = 0; 225edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project while (first != last) { 226edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ++first; 227edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ++count; 228edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 229edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return count; 230edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 231edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 232edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectprivate: 233edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* 234edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * I want a _ListNode but don't need it to hold valid data. More 235edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * to the point, I don't want T's constructor to fire, since it 236edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * might have side-effects or require arguments. So, we do this 237edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * slightly uncouth storage alloc. 238edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 239edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void prep(void) { 240edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mpMiddle = (_Node*) new unsigned char[sizeof(_Node)]; 241edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mpMiddle->setPrev(mpMiddle); 242edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mpMiddle->setNext(mpMiddle); 243edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 244edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 245edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project /* 246edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * This node plays the role of "pointer to head" and "pointer to tail". 247edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * It sits in the middle of a circular list of nodes. The iterator 248edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * runs around the circle until it encounters this one. 249edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 250edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _Node* mpMiddle; 251edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project}; 252edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 253edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* 254edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Assignment operator. 255edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * 256edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * The simplest way to do this would be to clear out the target list and 257edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * fill it with the source. However, we can speed things along by 258edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * re-using existing elements. 259edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 260edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projecttemplate<class T> 261edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectList<T>& List<T>::operator=(const List<T>& right) 262edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 263edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (this == &right) 264edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return *this; // self-assignment 265edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project iterator firstDst = begin(); 266edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project iterator lastDst = end(); 267edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const_iterator firstSrc = right.begin(); 268edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const_iterator lastSrc = right.end(); 269edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project while (firstSrc != lastSrc && firstDst != lastDst) 270edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project *firstDst++ = *firstSrc++; 271edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (firstSrc == lastSrc) // ran out of elements in source? 272edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project erase(firstDst, lastDst); // yes, erase any extras 273edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project else 274edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project insert(lastDst, firstSrc, lastSrc); // copy remaining over 275edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return *this; 276edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 277edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 278edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project}; // namespace android 279edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 280edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#endif // _LIBS_UTILS_LIST_H 281