1 /* Sorting objects for which copies cost more than swaps.
2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)
4
5 This file is part of the Parma Polyhedra Library (PPL).
6
7 The PPL is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 The PPL is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software Foundation,
19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
20
21 For the most up-to-date information see the Parma Polyhedra Library
22 site: http://bugseng.com/products/ppl/ . */
23
24 #ifndef PPL_swapping_sort_templates_hh
25 #define PPL_swapping_sort_templates_hh 1
26
27 #include <vector>
28 #include <algorithm>
29
30 namespace Parma_Polyhedra_Library {
31
32 namespace Implementation {
33
34 template <typename RA_Container, typename Compare>
35 struct Indirect_Sort_Compare {
36 typedef typename RA_Container::size_type size_type;
37
Indirect_Sort_CompareParma_Polyhedra_Library::Implementation::Indirect_Sort_Compare38 Indirect_Sort_Compare(const RA_Container& cont,
39 size_type base = 0,
40 Compare comp = Compare())
41 : container(cont), base_index(base), compare(comp) {
42 }
43
operator ()Parma_Polyhedra_Library::Implementation::Indirect_Sort_Compare44 bool operator()(size_type i, size_type j) const {
45 return compare(container[base_index + i], container[base_index + j]);
46 }
47
48 const RA_Container& container;
49 const size_type base_index;
50 const Compare compare;
51 }; // struct Indirect_Sort_Compare
52
53 template <typename RA_Container>
54 struct Indirect_Unique_Compare {
55 typedef typename RA_Container::size_type size_type;
56
Indirect_Unique_CompareParma_Polyhedra_Library::Implementation::Indirect_Unique_Compare57 Indirect_Unique_Compare(const RA_Container& cont, size_type base = 0)
58 : container(cont), base_index(base) {
59 }
60
operator ()Parma_Polyhedra_Library::Implementation::Indirect_Unique_Compare61 bool operator()(size_type i, size_type j) const {
62 return container[base_index + i] == container[base_index + j];
63 }
64
65 const RA_Container& container;
66 const size_type base_index;
67 }; // struct Indirect_Unique_Compare
68
69 template <typename RA_Container>
70 struct Indirect_Swapper {
71 typedef typename RA_Container::size_type size_type;
72
Indirect_SwapperParma_Polyhedra_Library::Implementation::Indirect_Swapper73 Indirect_Swapper(RA_Container& cont, size_type base = 0)
74 : container(cont), base_index(base) {
75 }
76
operator ()Parma_Polyhedra_Library::Implementation::Indirect_Swapper77 void operator()(size_type i, size_type j) const {
78 using std::swap;
79 swap(container[base_index + i], container[base_index + j]);
80 }
81
82 RA_Container& container;
83 const size_type base_index;
84 }; // struct Indirect_Swapper
85
86 template <typename RA_Container1, typename RA_Container2>
87 struct Indirect_Swapper2 {
88 typedef typename RA_Container1::size_type size_type;
89
Indirect_Swapper2Parma_Polyhedra_Library::Implementation::Indirect_Swapper290 Indirect_Swapper2(RA_Container1& cont1, RA_Container2& cont2)
91 : container1(cont1), container2(cont2) {
92 }
93
operator ()Parma_Polyhedra_Library::Implementation::Indirect_Swapper294 void operator()(size_type i, size_type j) const {
95 using std::swap;
96 swap(container1[i], container1[j]);
97 swap(container2[i], container2[j]);
98 }
99
100 RA_Container1& container1;
101 RA_Container2& container2;
102 }; // struct Indirect_Swapper2
103
104 template <typename Sort_Comparer, typename Unique_Comparer, typename Swapper>
105 typename Sort_Comparer::size_type
indirect_sort_and_unique(typename Sort_Comparer::size_type num_elems,Sort_Comparer sort_cmp,Unique_Comparer unique_cmp,Swapper indirect_swap)106 indirect_sort_and_unique(typename Sort_Comparer::size_type num_elems,
107 Sort_Comparer sort_cmp,
108 Unique_Comparer unique_cmp,
109 Swapper indirect_swap) {
110 typedef typename Sort_Comparer::size_type index_type;
111 // `iv' is a vector of indices for the portion of rows to be sorted.
112 PPL_ASSERT(num_elems >= 2);
113 std::vector<index_type> iv;
114 iv.reserve(num_elems);
115 for (index_type i = 0, i_end = num_elems; i != i_end; ++i) {
116 iv.push_back(i);
117 }
118
119 typedef typename std::vector<index_type>::iterator Iter;
120 const Iter iv_begin = iv.begin();
121 Iter iv_end = iv.end();
122
123 // Sort `iv' by comparing the rows indexed by its elements.
124 std::sort(iv_begin, iv_end, sort_cmp);
125
126 // Swap the indexed rows according to `iv':
127 // for each index `i', the element that should be placed in
128 // position dst = i is the one placed in position src = iv[i].
129 for (index_type i = num_elems; i-- > 0; ) {
130 if (i != iv[i]) {
131 index_type dst = i;
132 index_type src = iv[i];
133 do {
134 indirect_swap(src, dst);
135 iv[dst] = dst;
136 dst = src;
137 src = iv[dst];
138 } while (i != src);
139 iv[dst] = dst;
140 }
141 }
142
143 // Restore `iv' indices to 0 .. num_elems-1 for the call to unique.
144 for (index_type i = num_elems; i-- > 0; ) {
145 iv[i] = i;
146 }
147
148 // Unique `iv' by comparing the rows indexed by its elements.
149 iv_end = std::unique(iv_begin, iv_end, unique_cmp);
150
151 const index_type num_sorted = static_cast<index_type>(iv_end - iv_begin);
152 const index_type num_duplicates = num_elems - num_sorted;
153 if (num_duplicates == 0) {
154 return 0;
155 }
156
157 // There were duplicates: swap the rows according to `iv'.
158 index_type dst = 0;
159 while (dst < num_sorted && dst == iv[dst]) {
160 ++dst;
161 }
162 if (dst == num_sorted) {
163 return num_duplicates;
164 }
165 do {
166 const index_type src = iv[dst];
167 indirect_swap(src, dst);
168 ++dst;
169 }
170 while (dst < num_sorted);
171 return num_duplicates;
172 }
173
174 template <typename Iter>
175 Iter
swapping_unique(Iter first,Iter last)176 swapping_unique(Iter first, Iter last) {
177 return swapping_unique(first, last, std::iter_swap<Iter, Iter>);
178 }
179
180 } // namespace Implementation
181
182 } // namespace Parma_Polyhedra_Library
183
184 #endif // !defined(PPL_swapping_sort_templates_hh)
185