1/* 2 * Copyright (C) 2010 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#include "SortedListImpl.h" 18 19namespace android { 20namespace uirenderer { 21 22/////////////////////////////////////////////////////////////////////////////// 23// Sorted list implementation, not for direct use 24/////////////////////////////////////////////////////////////////////////////// 25 26SortedListImpl::SortedListImpl(size_t itemSize, uint32_t flags): VectorImpl(itemSize, flags) { 27} 28 29SortedListImpl::SortedListImpl(const VectorImpl& rhs): VectorImpl(rhs) { 30} 31 32SortedListImpl::~SortedListImpl() { 33} 34 35SortedListImpl& SortedListImpl::operator =(const SortedListImpl& rhs) { 36 return static_cast<SortedListImpl&> 37 (VectorImpl::operator =(static_cast<const VectorImpl&> (rhs))); 38} 39 40ssize_t SortedListImpl::indexOf(const void* item) const { 41 return _indexOrderOf(item); 42} 43 44size_t SortedListImpl::orderOf(const void* item) const { 45 size_t o; 46 _indexOrderOf(item, &o); 47 return o; 48} 49 50ssize_t SortedListImpl::_indexOrderOf(const void* item, size_t* order) const { 51 // binary search 52 ssize_t err = NAME_NOT_FOUND; 53 ssize_t l = 0; 54 ssize_t h = size() - 1; 55 ssize_t mid; 56 const void* a = arrayImpl(); 57 const size_t s = itemSize(); 58 while (l <= h) { 59 mid = l + (h - l) / 2; 60 const void* const curr = reinterpret_cast<const char *> (a) + (mid * s); 61 const int c = do_compare(curr, item); 62 if (c == 0) { 63 err = l = mid; 64 break; 65 } else if (c < 0) { 66 l = mid + 1; 67 } else { 68 h = mid - 1; 69 } 70 } 71 if (order) { 72 *order = l; 73 } 74 return err; 75} 76 77ssize_t SortedListImpl::add(const void* item) { 78 size_t order; 79 ssize_t index = _indexOrderOf(item, &order); 80 index = VectorImpl::insertAt(item, order, 1); 81 return index; 82} 83 84ssize_t SortedListImpl::merge(const VectorImpl& vector) { 85 // naive merge... 86 if (!vector.isEmpty()) { 87 const void* buffer = vector.arrayImpl(); 88 const size_t is = itemSize(); 89 size_t s = vector.size(); 90 for (size_t i = 0; i < s; i++) { 91 ssize_t err = add(reinterpret_cast<const char*> (buffer) + i * is); 92 if (err < 0) { 93 return err; 94 } 95 } 96 } 97 return NO_ERROR; 98} 99 100ssize_t SortedListImpl::merge(const SortedListImpl& vector) { 101 // we've merging a sorted vector... nice! 102 ssize_t err = NO_ERROR; 103 if (!vector.isEmpty()) { 104 // first take care of the case where the vectors are sorted together 105 if (do_compare(vector.itemLocation(vector.size() - 1), arrayImpl()) <= 0) { 106 err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&> (vector), 0); 107 } else if (do_compare(vector.arrayImpl(), itemLocation(size() - 1)) >= 0) { 108 err = VectorImpl::appendVector(static_cast<const VectorImpl&> (vector)); 109 } else { 110 // this could be made a little better 111 err = merge(static_cast<const VectorImpl&> (vector)); 112 } 113 } 114 return err; 115} 116 117ssize_t SortedListImpl::remove(const void* item) { 118 ssize_t i = indexOf(item); 119 if (i >= 0) { 120 VectorImpl::removeItemsAt(i, 1); 121 } 122 return i; 123} 124 125}; // namespace uirenderer 126}; // namespace android 127