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