1 /*
2  * Copyright (c) 2022 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 /**
17  * @addtogroup GraphicGeometry
18  * @brief Defines Arc
19  * @since 1.0
20  * @version 1.0
21  */
22 
23 #ifndef GRAPHIC_LTE_GEOMETRY_RANGE_ADAPTER_H
24 #define GRAPHIC_LTE_GEOMETRY_RANGE_ADAPTER_H
25 
26 #include "gfx_utils/diagram/common/common_basics.h"
27 #include "gfx_utils/heap_base.h"
28 #include "securec.h"
29 
30 namespace OHOS {
31 const int32_t QUICK_SORT_THRESHOLD = 9;
32 
33 /**
34  *
35  * @brief Exchange data.
36  * @since 1.0
37  * @version 1.0
38  */
39 template <class T>
SwapElements(T & firstValue,T & secondValue)40 inline void SwapElements(T& firstValue, T& secondValue)
41 {
42     T temp = firstValue;
43     firstValue = secondValue;
44     secondValue = temp;
45 }
46 
47 template <class Array, class Less>
ToCompareLess(Array & arr,Less less,int32_t iIndex,int32_t jIndex,int32_t base)48 void ToCompareLess(Array& arr, Less less, int32_t iIndex, int32_t jIndex, int32_t base)
49 {
50     while (true) {
51         do {
52             iIndex++;
53         } while (less(arr[iIndex], arr[base]));
54         do {
55             jIndex--;
56         } while (less(arr[base], arr[jIndex]));
57 
58         if (iIndex > jIndex) {
59             break;
60         }
61         SwapElements(arr[iIndex], arr[jIndex]);
62     }
63 }
64 
65 template <class Array, class Less>
CompareLessThreshold(Array & arr,Less less,int32_t iIndex,int32_t jIndex,int32_t base,int32_t limit,int32_t * top,int32_t * stack)66 bool CompareLessThreshold(Array& arr, Less less, int32_t iIndex, int32_t jIndex,
67                           int32_t base, int32_t limit, int32_t* top, int32_t* stack)
68 {
69     auto e1 = &arr[0];
70     auto e2 = &arr[0];
71     jIndex = base;
72     iIndex = jIndex + 1;
73     for (; iIndex < limit; iIndex++) {
74         for (; less(*(e1 = &(arr[jIndex + 1])), *(e2 = &(arr[jIndex]))); jIndex--) {
75             SwapElements(*e1, *e2);
76             if (jIndex == base) {
77                 break;
78             }
79         }
80         jIndex = iIndex;
81     }
82     if (top > stack) {
83         top -= TWO_STEP;
84         base = top[0];
85         limit = top[1];
86         return false;
87     } else {
88         return true;
89     }
90 }
91 
92 /**
93  *
94  * @brief Quick sort algorithm.
95  * @param arr Array to sort, less sort condition
96  * @since 1.0
97  * @version 1.0
98  */
99 template <class Array, class Less>
100 void QuickSort(Array& arr, Less less);
101 
102 /**
103  *
104  * @brief Deletes duplicate elements according to the specified criteria.
105  *
106  * @param arr Specify the array, equal specify the condition.
107  * @since 1.0
108  * @version 1.0
109  */
110 template <class Array, class Equal>
111 uint32_t RemoveDuplicates(Array& arr, Equal equal);
112 
113 /**
114  *
115  * @brief Invert an array.
116  *
117  * @since 1.0
118  * @version 1.0
119  */
120 template <class Array>
InvertContainer(Array & arr)121 void InvertContainer(Array& arr)
122 {
123     int32_t iIndex = 0;
124     int32_t jIndex = arr.size() - 1;
125     while (iIndex < jIndex) {
126         SwapElements(arr[iIndex++], arr[jIndex--]);
127     }
128 }
129 
130 /**
131  *
132  * @brief Dichotomy search algorithm.
133  *
134  * @since 1.0
135  * @version 1.0
136  */
137 template <class Array, class Value, class Less>
138 uint32_t BinarySearchPos(const Array& arrData, const Value& val, Less less);
139 
140 template <class Array, class Less>
QuickSort(Array & arr,Less less)141 void QuickSort(Array& arr, Less less)
142 {
143     if (arr.Size() < 2) {
144         return;
145     }
146     int32_t stack[80];
147     int32_t* top = stack;
148     int32_t limit = arr.Size();
149     int32_t baseLimit = 0;
150     while (true) {
151         int32_t len = limit - baseLimit;
152         int32_t iIndex = 0;
153         int32_t jIndex = 0;
154         int32_t pivot;
155         if (len > QUICK_SORT_THRESHOLD) {
156             pivot = static_cast<int32_t>(baseLimit + len * HALFNUM);
157             SwapElements(arr[baseLimit], arr[pivot]);
158             iIndex = baseLimit + 1;
159             jIndex = limit - 1;
160             auto firstElement = &(arr[jIndex]);
161             auto secondElement = &(arr[iIndex]);
162             if (less(*firstElement, *secondElement)) {
163                 SwapElements(*firstElement, *secondElement);
164             }
165             firstElement = &(arr[baseLimit]);
166             secondElement = &(arr[iIndex]);
167             if (less(*firstElement, *secondElement)) {
168                 SwapElements(*firstElement, *secondElement);
169             }
170             firstElement = &(arr[jIndex]);
171             secondElement = &(arr[baseLimit]);
172             if (less(*firstElement, *secondElement))
173                 SwapElements(*firstElement, *secondElement);
174             ToCompareLess(arr, less, iIndex, jIndex, baseLimit);
175             SwapElements(arr[baseLimit], arr[jIndex]);
176             if (jIndex - baseLimit > limit - iIndex) {
177                 top[0] = baseLimit;
178                 top[1] = jIndex;
179                 baseLimit = iIndex;
180             } else {
181                 top[0] = iIndex;
182                 top[1] = limit;
183                 limit = jIndex;
184             }
185             top += TWO_STEP;
186         } else {
187             if (CompareLessThreshold(arr, less, iIndex, jIndex, baseLimit, limit, top, stack)) {
188                 break;
189             }
190         }
191     }
192 }
193 
194 template <class Array, class Value, class Less>
BinarySearchPos(const Array & arrData,const Value & val,Less less)195 uint32_t BinarySearchPos(const Array& arrData, const Value& val, Less less)
196 {
197     if (arrData.size() == 0) {
198         return 0;
199     }
200 
201     uint32_t arrayBegin = 0;
202     uint32_t arrayEnd = arrData.size() - 1;
203 
204     if (less(val, arrData[0])) {
205         return 0;
206     }
207     if (less(arrData[arrayEnd], val)) {
208         return arrayEnd + 1;
209     }
210 
211     while (arrayEnd - arrayBegin > 1) {
212         uint32_t mid = (arrayEnd + arrayBegin) >> 1;
213         if (less(val, arrData[mid])) {
214             arrayEnd = mid;
215         } else {
216             arrayBegin = mid;
217         }
218     }
219 
220     return arrayEnd;
221 }
222 
223 template <class Array, class Equal>
RemoveDuplicates(Array & arr,Equal equal)224 uint32_t RemoveDuplicates(Array& arr, Equal equal)
225 {
226     const int32_t number = 2;
227     if (arr.Size() < number) {
228         return arr.Size();
229     }
230     uint32_t jIndex = 1;
231     for (uint32_t iIndex = 1; iIndex < arr.Size(); iIndex++) {
232         auto& element = arr[iIndex];
233         if (!equal(element, arr[iIndex - 1])) {
234             arr[jIndex++] = element;
235         }
236     }
237     return jIndex;
238 }
239 } // namespace OHOS
240 #endif