1 ////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (C) 1996-2021 The Octave Project Developers
4 //
5 // See the file COPYRIGHT.md in the top-level directory of this
6 // distribution or <https://octave.org/copyright/>.
7 //
8 // This file is part of Octave.
9 //
10 // Octave is free software: you can redistribute it and/or modify it
11 // under the terms of the GNU General Public License as published by
12 // the Free Software Foundation, either version 3 of the License, or
13 // (at your option) any later version.
14 //
15 // Octave is distributed in the hope that it will be useful, but
16 // WITHOUT ANY WARRANTY; without even the implied warranty of
17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 // GNU General Public License for more details.
19 //
20 // You should have received a copy of the GNU General Public License
21 // along with Octave; see the file COPYING. If not, see
22 // <https://www.gnu.org/licenses/>.
23 //
24 ////////////////////////////////////////////////////////////////////////
25
26 #if defined (HAVE_CONFIG_H)
27 # include "config.h"
28 #endif
29
30 // Instantiate Arrays of bool values.
31
32 #include "Array.h"
33 #include "Array.cc"
34
35 #define INLINE_ASCENDING_SORT 1
36 #define INLINE_DESCENDING_SORT 1
37 #include "oct-sort.cc"
38
39 // Prevent implicit instantiations on some systems (Windows, others?)
40 // that can lead to duplicate definitions of static data members.
41
42 extern template class OCTAVE_API Array<idx_vector>;
43 extern template class OCTAVE_API Array<octave_idx_type>;
44
45 // Specialize bool sorting (aka stable partitioning).
46
47 template <bool desc>
do_bool_partition(bool * data,octave_idx_type nel)48 static void do_bool_partition (bool *data, octave_idx_type nel)
49 {
50 octave_idx_type k = 0;
51 for (octave_idx_type i = 0; i < nel; i++)
52 if (data[i] == desc)
53 data[k++] = desc;
54 for (octave_idx_type i = k; i < nel; i++)
55 data[i] = ! desc;
56 }
57
58 template <bool desc>
do_bool_partition(bool * data,octave_idx_type * idx,octave_idx_type nel)59 static void do_bool_partition (bool *data, octave_idx_type *idx,
60 octave_idx_type nel)
61 {
62 // FIXME: This is essentially a simple bucket sort.
63 // Can it be efficiently done by std::partition?
64 OCTAVE_LOCAL_BUFFER (octave_idx_type, jdx, nel);
65 octave_idx_type k = 0;
66 octave_idx_type l = 0;
67 for (octave_idx_type i = 0; i < nel; i++)
68 {
69 if (data[i] == desc)
70 {
71 data[k] = desc;
72 idx[k++] = idx[i];
73 }
74 else
75 jdx[l++] = idx[i];
76 }
77
78 for (octave_idx_type i = k; i < nel; i++)
79 {
80 data[i] = ! desc;
81 idx[i] = jdx[i-k];
82 }
83 }
84
85 template <>
86 template <>
87 void
sort(bool * data,octave_idx_type nel,std::less<bool>)88 octave_sort<bool>::sort (bool *data, octave_idx_type nel,
89 std::less<bool>)
90 {
91 do_bool_partition<false> (data, nel);
92 }
93
94 template <>
95 template <>
96 void
sort(bool * data,octave_idx_type nel,std::greater<bool>)97 octave_sort<bool>::sort (bool *data, octave_idx_type nel,
98 std::greater<bool>)
99 {
100 do_bool_partition<true> (data, nel);
101 }
102
103 template <>
104 template <>
105 void
sort(bool * data,octave_idx_type * idx,octave_idx_type nel,std::less<bool>)106 octave_sort<bool>::sort (bool *data, octave_idx_type *idx, octave_idx_type nel,
107 std::less<bool>)
108 {
109 do_bool_partition<false> (data, idx, nel);
110 }
111
112 template <>
113 template <>
114 void
sort(bool * data,octave_idx_type * idx,octave_idx_type nel,std::greater<bool>)115 octave_sort<bool>::sort (bool *data, octave_idx_type *idx, octave_idx_type nel,
116 std::greater<bool>)
117 {
118 do_bool_partition<true> (data, idx, nel);
119 }
120
121 template class OCTAVE_API octave_sort<bool>;
122
123 INSTANTIATE_ARRAY (bool, OCTAVE_API);
124
125 template OCTAVE_API std::ostream& operator << (std::ostream&,
126 const Array<bool>&);
127
128 #include "DiagArray2.h"
129 #include "DiagArray2.cc"
130
131 template class OCTAVE_API DiagArray2<bool>;
132