1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
//
// A rust binding for the GSL library by Guillaume Gomez (guillaume1.gomez@gmail.com)
//
/*!
#Combinations
This chapter describes functions for creating and manipulating combinations. A combination c is
represented by an array of k integers in the range 0 to n-1, where each value c_i occurs at most
once. The combination c corresponds to indices of k elements chosen from an n element vector.
Combinations are useful for iterating over all k-element subsets of a set.
##References and Further Reading
Further information on combinations can be found in,
Donald L. Kreher, Douglas R. Stinson, Combinatorial Algorithms: Generation, Enumeration and Search,
1998, CRC Press LLC, ISBN 084933988X
!*/
use ffi;
use enums;
use std::fmt;
use std::fmt::{Formatter, Debug};
use c_vec::CSlice;
pub struct Combination {
c: *mut ffi::gsl_combination,
data: CSlice<usize>
}
impl Combination {
/// This function allocates memory for a new combination with parameters n, k. The combination
/// is not initialized and its elements are undefined. Use the function
/// `Combination::new_init_first` if you want to create a combination which is initialized to
/// the lexicographically first combination. A null pointer is returned if insufficient memory
/// is available to create the combination.
pub fn new(n: usize, k: usize) -> Option<Combination> {
let tmp = unsafe { ffi::gsl_combination_alloc(n, k) };
if tmp.is_null() {
None
} else {
unsafe {
if !(*tmp).data.is_null() {
Some(Combination {
c: tmp,
data: CSlice::new((*tmp).data, (*tmp).k as usize)
})
} else {
Some(Combination {
c: tmp,
data: CSlice::new(tmp as *mut usize, 0usize)
})
}
}
}
}
/// This function allocates memory for a new combination with parameters n, k and initializes it
/// to the lexicographically first combination. A null pointer is returned if insufficient
/// memory is available to create the combination.
pub fn new_init_first(n: usize, k: usize) -> Option<Combination> {
let tmp = unsafe { ffi::gsl_combination_calloc(n, k) };
if tmp.is_null() {
None
} else {
unsafe {
if !(*tmp).data.is_null() {
Some(Combination {
c: tmp,
data: CSlice::new((*tmp).data, (*tmp).k as usize)
})
} else {
Some(Combination {
c: tmp,
data: CSlice::new(tmp as *mut usize, 0usize)
})
}
}
}
}
/// This function initializes the combination c to the lexicographically first combination, i.e.
/// (0,1,2,...,k-1).
pub fn init_first(&mut self) {
unsafe { ffi::gsl_combination_init_first(self.c) }
}
/// This function initializes the combination c to the lexicographically last combination, i.e.
/// (n-k,n-k+1,…,n-1).
pub fn init_last(&mut self) {
unsafe { ffi::gsl_combination_init_last(self.c) }
}
/// This function copies the elements of the combination self into the combination dest. The two
/// combinations must have the same size.
pub fn copy(&self, dest: &mut Combination) -> enums::Value {
enums::Value::from(unsafe { ffi::gsl_combination_memcpy(dest.c, self.c) })
}
/// This function returns the value of the i-th element of the combination self. If i lies
/// outside the allowed range of 0 to k-1 then the error handler is invoked and 0 is returned.
pub fn get(&self, i: usize) -> usize {
unsafe { ffi::gsl_combination_get(self.c, i) }
}
/// This function returns the range (n) of the combination self.
pub fn n(&self) -> usize {
unsafe { ffi::gsl_combination_n(self.c) }
}
/// This function returns the number of elements (k) in the combination self.
pub fn k(&self) -> usize {
unsafe { ffi::gsl_combination_k(self.c) }
}
/// This function returns a pointer to the array of elements in the combination self.
pub fn as_slice<'r>(&'r self) -> &'r [usize] {
self.data.as_ref()
}
/// This function returns a pointer to the array of elements in the combination self.
pub fn as_mut_slice<'r>(&'r mut self) -> &'r mut [usize] {
self.data.as_mut()
}
/// This function checks that the combination self is valid. The k elements should lie in the
/// range 0 to n-1, with each value occurring once at most and in increasing order.
pub fn is_valid(&self) -> enums::Value {
enums::Value::from(unsafe { ffi::gsl_combination_valid(self.c) })
}
/// This function advances the combination self to the next combination in lexicographic order
/// and returns `Success`. If no further combinations are available it returns Failure and
/// leaves self unmodified. Starting with the first combination and repeatedly applying this
/// function will iterate through all possible combinations of a given order.
pub fn next(&mut self) -> enums::Value {
enums::Value::from(unsafe { ffi::gsl_combination_next(self.c) })
}
/// This function steps backwards from the combination self to the previous combination in
/// lexicographic order, returning `Success`. If no previous combination is available it returns
/// `Failure` and leaves self unmodified.
pub fn prev(&mut self) -> enums::Value {
enums::Value::from(unsafe { ffi::gsl_combination_prev(self.c) })
}
}
impl Drop for Combination {
fn drop(&mut self) {
unsafe { ffi::gsl_combination_free(self.c) };
self.c = ::std::ptr::null_mut();
}
}
impl ffi::FFI<ffi::gsl_combination> for Combination {
fn wrap(c: *mut ffi::gsl_combination) -> Combination {
unsafe {
Combination {
c: c,
data: CSlice::new((*c).data, (*c).k as usize)
}
}
}
fn soft_wrap(r: *mut ffi::gsl_combination) -> Combination {
Self::wrap(r)
}
fn unwrap_shared(c: &Combination) -> *const ffi::gsl_combination {
c.c as *const _
}
fn unwrap_unique(c: &mut Combination) -> *mut ffi::gsl_combination {
c.c
}
}
impl Debug for Combination {
#[allow(unused_must_use)]
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
write!(f, "[");
for tmp in 0..self.data.len() {
if tmp == 0 {
write!(f, "{}", self.data.get(tmp).unwrap());
} else {
write!(f, ", {}", self.data.get(tmp).unwrap());
}
}
write!(f, "]")
}
}