2 * PROJECT: ReactOS Console Configuration DLL
3 * LICENSE: GPL - See COPYING in the top level directory
4 * FILE: dll/cpl/console/utils.c
5 * PURPOSE: Utility functions
6 * PROGRAMMERS: Hermes Belusca-Maito (hermes.belusca@sfr.fr)
16 * A function that locates the insertion point (index) for a given value 'Value'
17 * in a list 'List' to maintain its sorted order by increasing values.
19 * - When 'BisectRightOrLeft' == TRUE, the bisection is performed to the right,
20 * i.e. the returned insertion point comes after (to the right of) any existing
21 * entries of 'Value' in 'List'.
22 * The returned insertion point 'i' partitions the list 'List' into two halves
24 * all(val <= Value for val in List[start:i[) for the left side, and
25 * all(val > Value for val in List[i:end+1[) for the right side.
27 * - When 'BisectRightOrLeft' == FALSE, the bisection is performed to the left,
28 * i.e. the returned insertion point comes before (to the left of) any existing
29 * entries of 'Value' in 'List'.
30 * The returned insertion point 'i' partitions the list 'List' into two halves
32 * all(val < Value for val in List[start:i[) for the left side, and
33 * all(val >= Value for val in List[i:end+1[) for the right side.
35 * The exact value of List[i] may, or may not, be equal to Value, depending on
36 * whether or not 'Value' is actually present on the list.
39 BisectListSortedByValueEx(
44 OUT PUINT pValueItem OPTIONAL
,
45 IN BOOL BisectRightOrLeft
)
47 UINT iItemStart
, iItemEnd
, iItem
;
51 if (itemStart
> itemEnd
)
52 return CB_ERR
; // Fail
55 iItemStart
= itemStart
;
62 while (iItemStart
<= iItemEnd
)
65 * Bisect. Note the following:
66 * - if iItemEnd == iItemStart + 1, then iItem == iItemStart;
67 * - if iItemStart == iItemEnd, then iItemStart == iItem == iItemEnd.
68 * In all but the last case, iItemStart <= iItem < iItemEnd.
70 iItem
= (iItemStart
+ iItemEnd
) / 2;
72 itemData
= ListCtl
->GetData(ListCtl
, iItem
);
73 if (itemData
== CB_ERR
)
74 return CB_ERR
; // Fail
76 if (Value
== itemData
)
78 /* Found a candidate */
83 * Try to find the last element (if BisectRightOrLeft == TRUE)
84 * or the first element (if BisectRightOrLeft == FALSE).
86 if (BisectRightOrLeft
)
88 iItemStart
= iItem
+ 1; // iItemStart may be > iItemEnd
92 if (iItem
<= itemStart
) break;
93 iItemEnd
= iItem
- 1; // iItemEnd may be < iItemStart, i.e. iItemStart may be > iItemEnd
96 else if (Value
< itemData
)
98 if (iItem
<= itemStart
) break;
99 /* The value should be before iItem */
100 iItemEnd
= iItem
- 1; // iItemEnd may be < iItemStart, i.e. iItemStart may be > iItemEnd, if iItem == iItemStart.
102 else // if (itemData < Value)
104 /* The value should be after iItem */
105 iItemStart
= iItem
+ 1; // iItemStart may be > iItemEnd, if iItem == iItemEnd.
108 /* Here, iItemStart may be == iItemEnd */
115 BisectListSortedByValue(
116 IN PLIST_CTL ListCtl
,
118 OUT PUINT pValueItem OPTIONAL
,
119 IN BOOL BisectRightOrLeft
)
121 INT iItemEnd
= ListCtl
->GetCount(ListCtl
);
122 if (iItemEnd
== CB_ERR
|| iItemEnd
<= 0)
123 return CB_ERR
; // Fail
125 return BisectListSortedByValueEx(ListCtl
, Value
,
126 0, (UINT
)(iItemEnd
- 1),