Coverage for moptipy / spaces / bitstrings.py: 98%

1"""An implementation of a bit string based search space.""" 

2from typing import Final 

3 

4import numpy as np 

5from pycommons.io.csv import CSV_SEPARATOR 

6from pycommons.strings.string_conv import bool_to_str, str_to_bool 

7from pycommons.types import type_error 

8 

9from moptipy.spaces.nparrayspace import NPArraySpace 

10from moptipy.utils.nputils import DEFAULT_BOOL 

11 

12 

13class BitStrings(NPArraySpace): 

14 """ 

15 A space where each element is a bit string (:class:`numpy.ndarray`). 

16 

17 With such a space, discrete optimization can be realized. 

18 

19 >>> s = BitStrings(5) 

20 >>> print(s.dimension) 

21 5 

22 >>> print(s.dtype) 

23 bool 

24 >>> print(s.create()) 

25 [False False False False False] 

26 >>> print(s.to_str(s.create())) 

27 FFFFF 

28 >>> print(s.from_str(s.to_str(s.create()))) 

29 [False False False False False] 

30 """ 

31 

32 def __init__(self, dimension: int) -> None: 

33 """ 

34 Create the vector-based search space. 

35 

36 :param dimension: The dimension of the search space, 

37 i.e., the number of decision variables. 

38 """ 

39 super().__init__(dimension, DEFAULT_BOOL) 

40 

41 def create(self) -> np.ndarray: 

42 """ 

43 Create a bit string filled with `False`. 

44 

45 :return: the string 

46 

47 >>> from moptipy.spaces.bitstrings import BitStrings 

48 >>> s = BitStrings(8) 

49 >>> v = s.create() 

50 >>> print(s.to_str(v)) 

51 FFFFFFFF 

52 >>> print(v.dtype) 

53 bool 

54 """ 

55 return np.zeros(shape=self.dimension, dtype=DEFAULT_BOOL) 

56 

57 def from_str(self, text: str) -> np.ndarray: 

58 """ 

59 Convert a string to a bit string. 

60 

61 :param text: the text 

62 :return: the vector 

63 :raises TypeError: if `text` is not a `str` 

64 :raises ValueError: if `text` cannot be converted to a valid vector 

65 """ 

66 if not (isinstance(text, str)): 

67 raise type_error(text, "text", str) 

68 x: Final[np.ndarray] = self.create() 

69 x[:] = [str_to_bool(t) for t in text] 

70 self.validate(x) 

71 return x 

72 

73 def n_points(self) -> int: 

74 """ 

75 Get the scale of the bit string space. 

76 

77 :return: 2 ** dimension 

78 

79 >>> print(BitStrings(4).n_points()) 

80 16 

81 """ 

82 return 1 << self.dimension # = 2 ** self.dimension 

83 

84 def __str__(self) -> str: 

85 """ 

86 Get the name of this space. 

87 

88 :return: "bits" + dimension 

89 

90 >>> print(BitStrings(5)) 

91 bits5 

92 """ 

93 return f"bits{self.dimension}" 

94 

95 def to_hex_string(self, x: np.ndarray) -> str: 

96 """ 

97 Convert a bit string to a hexadecimal number. 

98 

99 The reverse operator is given as :meth:`from_hex_string`. 

100 

101 :param x: the bit string 

102 :returns: the hexadecimal number 

103 

104 >>> b = BitStrings(134) 

105 >>> xt = b.create() 

106 >>> xt[:] = [((i % 3) == 0) != ((i % 7) == 0) 

107 ... for i in range(b.dimension)] 

108 >>> "".join(reversed(b.to_str(xt))) 

109 'TTFFTFFFFFTFFTTFTFFTFTTFFTFFFFFTFFTTFTFFTFTTFFTFFFFFTFFTTFTFFTFT\ 

110TFFTFFFFFTFFTTFTFFTFTTFFTFFFFFTFFTTFTFFTFTTFFTFFFFFTFFTTFTFFTFTTFFTFFF' 

111 >>> hex(int("11001000001001101001011001000001001101001011001000" 

112 ... "0010011010010110010000010011010010110010000010011010" 

113 ... "01011001000001001101001011001000", 2)) 

114 '0x3209a5904d2c826964134b209a5904d2c8' 

115 >>> b.to_hex_string(xt) 

116 '3209a5904d2c826964134b209a5904d2c8' 

117 """ 

118 self.validate(x) 

119 number: int = 0 

120 adder: int = 1 

121 for i in range(self.dimension): 

122 if x[i]: 

123 number += adder 

124 adder *= 2 

125 return format(number, "x") 

126 

127 def from_hex_string(self, x: np.ndarray, s: str) -> None: 

128 """ 

129 Convert a hexadecimal number to a numpy bit string. 

130 

131 The reverse operator is given as :meth:`to_hex_string`. 

132 

133 :param x: the bit string destination 

134 :param s: the string to convert 

135 

136 >>> b = BitStrings(134) 

137 >>> x1 = b.create() 

138 >>> x1[:] = [((i % 3) == 0) != ((i % 7) == 0) 

139 ... for i in range(b.dimension)] 

140 >>> x2 = b.create() 

141 >>> b.from_hex_string(x2, b.to_hex_string(x1)) 

142 >>> b.is_equal(x1, x2) 

143 True 

144 """ 

145 number: int = int(str.strip(s), 16) # enforce type error 

146 for i in range(self.dimension): 

147 x[i] = (number & 1) != 0 

148 number >>= 1 

149 self.validate(x) 

150 

151 def to_rle_str(self, x: np.ndarray) -> str: 

152 """ 

153 Convert a numpy bit string to a run-length encoded string. 

154 

155 The first bit value is stored, followed by a colon (:), followed by the 

156 run lengths separated with semicolons. 

157 The reverse operator is given as :meth:`from_rle_str`. 

158 

159 :param x: the bit string 

160 :returns: the run-length encoded string 

161 

162 >>> b = BitStrings(134) 

163 >>> xt = b.create() 

164 >>> xt[:] = [((i % 3) == 0) != ((i % 7) == 0) 

165 ... for i in range(b.dimension)] 

166 >>> b.to_rle_str(xt) 

167 'F:3;1;2;2;1;1;2;1;1;2;2;1;5;1;2;2;1;1;2;1;1;2;2;1;5;1;2;2;1;1;2;1;1;\ 

1682;2;1;5;1;2;2;1;1;2;1;1;2;2;1;5;1;2;2;1;1;2;1;1;2;2;1;5;1;2;2;1;1;2;1;1;2;2;\ 

1691;5;1;2;2' 

170 

171 >>> b = BitStrings(5) 

172 >>> xt = b.create() 

173 >>> xt.fill(0) 

174 >>> b.to_rle_str(xt) 

175 'F:5' 

176 >>> xt[1] = 1 

177 >>> b.to_rle_str(xt) 

178 'F:1;1;3' 

179 

180 >>> b = BitStrings(5) 

181 >>> xt = b.create() 

182 >>> xt.fill(1) 

183 >>> b.to_rle_str(xt) 

184 'T:5' 

185 >>> xt[-1] = 0 

186 >>> b.to_rle_str(xt) 

187 'T:4;1' 

188 >>> xt[-1] = 1 

189 >>> xt[-2] = 0 

190 >>> b.to_rle_str(xt) 

191 'T:3;1;1' 

192 """ 

193 self.validate(x) 

194 cur: np.bool = x[0] 

195 sep: str = ":" 

196 rle: list[str] = [bool_to_str(bool(cur))] 

197 start: int = 0 

198 for i, bit in enumerate(x): 

199 if bit != cur: 

200 rle.append(f"{sep}{i - start}") 

201 sep = CSV_SEPARATOR 

202 cur = bit 

203 start = i 

204 rle.extend(f"{sep}{self.dimension - start}") 

205 return "".join(rle) 

206 

207 def from_rle_str(self, x: np.ndarray, s: str) -> None: 

208 """ 

209 Convert a run-length encoded string to a numpy bit string. 

210 

211 The reverse operator is given as :meth:`to_rle_str`. 

212 

213 :param s: string to convert 

214 :param x: the bit string destination 

215 

216 >>> b = BitStrings(134) 

217 >>> x1 = b.create() 

218 >>> x1[:] = [((i % 3) == 0) != ((i % 7) == 0) 

219 ... for i in range(b.dimension)] 

220 >>> x2 = b.create() 

221 >>> b.from_hex_string(x2, b.to_hex_string(x1)) 

222 >>> all(x1 == x2) 

223 True 

224 >>> x1[5] = not x1[5] 

225 >>> b.from_hex_string(x2, b.to_hex_string(x1)) 

226 >>> all(x1 == x2) 

227 True 

228 

229 >>> b = BitStrings(5) 

230 >>> x1 = b.create() 

231 >>> x2 = b.create() 

232 >>> x1.fill(0) 

233 >>> b.from_hex_string(x2, b.to_hex_string(x1)) 

234 >>> all(x1 == x2) 

235 True 

236 

237 >>> x1[1] = 1 

238 >>> b.from_hex_string(x2, b.to_hex_string(x1)) 

239 >>> all(x1 == x2) 

240 True 

241 

242 >>> x1.fill(1) 

243 >>> b.from_hex_string(x2, b.to_hex_string(x1)) 

244 >>> all(x1 == x2) 

245 True 

246 """ 

247 s = str.strip(s) 

248 value: bool = str_to_bool(s[0]) 

249 i: int = 0 

250 for rl in s[s.index(":") + 1:].split(CSV_SEPARATOR): 

251 for _ in range(int(rl)): 

252 x[i] = value 

253 i += 1 

254 value = not value 

255 self.validate(x)