File: BitArray%2BInitializers.swift

package info (click to toggle)
swiftlang 6.0.3-2
  • links: PTS, VCS
  • area: main
  • in suites: forky, sid, trixie
  • size: 2,519,992 kB
  • sloc: cpp: 9,107,863; ansic: 2,040,022; asm: 1,135,751; python: 296,500; objc: 82,456; f90: 60,502; lisp: 34,951; pascal: 19,946; sh: 18,133; perl: 7,482; ml: 4,937; javascript: 4,117; makefile: 3,840; awk: 3,535; xml: 914; fortran: 619; cs: 573; ruby: 573
file content (271 lines) | stat: -rw-r--r-- 10,857 bytes parent folder | download
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
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Collections open source project
//
// Copyright (c) 2021 - 2024 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//

extension BitArray {
  /// Initialize a bit array from a bit set.
  ///
  /// The result contains exactly as many bits as the maximum item in
  /// the source set, plus one. If the set is empty, the result will
  /// be empty, too.
  ///
  ///     BitArray([] as BitSet)        // (empty)
  ///     BitArray([0] as BitSet)       // 1
  ///     BitArray([1] as BitSet)       // 10
  ///     BitArray([1, 2, 4] as BitSet) // 1011
  ///     BitArray([7] as BitSet)       // 1000000
  ///
  /// - Complexity: O(1)
  public init(_ set: BitSet) {
    guard let l = set.last else { self.init(); return }
    self.init(_storage: set._storage, count: l + 1)
  }

  /// Initialize a bit array from the binary representation of an integer.
  /// The result will contain exactly `value.bitWidth` bits.
  ///
  ///     BitArray(bitPattern: 3 as UInt8)  // 00000011
  ///     BitArray(bitPattern: 42 as Int8)  // 00101010
  ///     BitArray(bitPattern: -1 as Int8)  // 11111111
  ///     BitArray(bitPattern: 3 as Int16)  // 0000000000000111
  ///     BitArray(bitPattern: 42 as Int16) // 0000000000101010
  ///     BitArray(bitPattern: -1 as Int16) // 1111111111111111
  ///     BitArray(bitPattern: 3 as Int)    // 0000000000...0000000111
  ///     BitArray(bitPattern: 42 as Int)   // 0000000000...0000101010
  ///     BitArray(bitPattern: -1 as Int)   // 1111111111...1111111111
  ///
  /// - Complexity: O(value.bitWidth)
  public init(bitPattern value: some BinaryInteger) {
    var words = value.words.map { _Word($0) }
    let count = value.bitWidth
    if words.isEmpty {
      precondition(count == 0, "Inconsistent bitWidth")
    } else {
      let (w, b) = _UnsafeHandle._BitPosition(count).endSplit
      precondition(words.count == w + 1, "Inconsistent bitWidth")
      words[w].formIntersection(_Word(upTo: b))
    }
    self.init(_storage: words, count: count)
  }

  /// Creates a new, empty bit array with preallocated space for at least the
  /// specified number of elements.
  public init(minimumCapacity: Int) {
    self.init()
    reserveCapacity(minimumCapacity)
  }
}

extension BinaryInteger {
  @inlinable
  internal static func _convert(
    _ source: BitArray
  ) -> (value: Self, isNegative: Bool) {
    var value: Self = .zero
    let isNegative = source._foreachTwosComplementWordDownward(
      isSigned: Self.isSigned
    ) { _, word in
      value <<= UInt.bitWidth
      value |= Self(truncatingIfNeeded: word)
      return true
    }
    return (value, isNegative)
  }

  /// Creates a new instance by truncating or extending the bits in the given
  /// bit array, as needed. The bit at position 0 in `source` will correspond
  /// to the least-significant bit in the result.
  ///
  /// If `Self` is an unsigned integer type, then the result will contain as
  /// many bits from `source` it can accommodate, truncating off any extras.
  ///
  ///     UInt8(truncatingIfNeeded: "" as BitArray) // 0
  ///     UInt8(truncatingIfNeeded: "0" as BitArray) // 0
  ///     UInt8(truncatingIfNeeded: "1" as BitArray) // 1
  ///     UInt8(truncatingIfNeeded: "11" as BitArray) // 3
  ///     UInt8(truncatingIfNeeded: "11111111" as BitArray) // 255
  ///     UInt8(truncatingIfNeeded: "1100000001" as BitArray) // 1
  ///     UInt8(truncatingIfNeeded: "1100000101" as BitArray) // 5
  ///
  /// If `Self` is a signed integer type, then the contents of the bit array
  /// are interpreted to be a two's complement representation of a signed
  /// integer value, with the last bit in the array representing the sign of
  /// the result.
  ///
  ///     Int8(truncatingIfNeeded: "" as BitArray) // 0
  ///     Int8(truncatingIfNeeded: "0" as BitArray) // 0
  ///     Int8(truncatingIfNeeded: "1" as BitArray) // -1
  ///     Int8(truncatingIfNeeded: "01" as BitArray) // 1
  ///     Int8(truncatingIfNeeded: "101" as BitArray) // -3
  ///     Int8(truncatingIfNeeded: "0101" as BitArray) // 5
  ///
  ///     Int8(truncatingIfNeeded: "00000001" as BitArray) // 1
  ///     Int8(truncatingIfNeeded: "00000101" as BitArray) // 5
  ///     Int8(truncatingIfNeeded: "01111111" as BitArray) // 127
  ///     Int8(truncatingIfNeeded: "10000000" as BitArray) // -128
  ///     Int8(truncatingIfNeeded: "11111111" as BitArray) // -1
  ///
  ///     Int8(truncatingIfNeeded: "000011111111" as BitArray) // -1
  ///     Int8(truncatingIfNeeded: "111100000000" as BitArray) // 0
  ///     Int8(truncatingIfNeeded: "111100000001" as BitArray) // 1
  @inlinable
  public init(truncatingIfNeeded source: BitArray) {
    self = Self._convert(source).value
  }

  /// Creates a new instance from the bits in the given bit array, if the
  /// corresponding integer value can be represented exactly.
  /// If the value is not representable exactly, then the result is `nil`.
  ///
  /// If `Self` is an unsigned integer type, then the contents of the bit array
  /// are interpreted to be the binary representation of a nonnegative
  /// integer value. The bit array is allowed to contain bits in unrepresentable
  /// positions, as long as they are all cleared.
  ///
  ///     UInt8(exactly: "" as BitArray) // 0
  ///     UInt8(exactly: "0" as BitArray) // 0
  ///     UInt8(exactly: "1" as BitArray) // 1
  ///     UInt8(exactly: "10" as BitArray) // 2
  ///     UInt8(exactly: "00000000" as BitArray) // 0
  ///     UInt8(exactly: "11111111" as BitArray) // 255
  ///     UInt8(exactly: "0000000000000" as BitArray) // 0
  ///     UInt8(exactly: "0000011111111" as BitArray) // 255
  ///     UInt8(exactly: "0000100000000" as BitArray) // nil
  ///     UInt8(exactly: "1111111111111" as BitArray) // nil
  ///
  /// If `Self` is a signed integer type, then the contents of the bit array
  /// are interpreted to be a two's complement representation of a signed
  /// integer value, with the last bit in the array representing the sign of
  /// the result.
  ///
  ///     Int8(exactly: "" as BitArray) // 0
  ///     Int8(exactly: "0" as BitArray) // 0
  ///     Int8(exactly: "1" as BitArray) // -1
  ///     Int8(exactly: "01" as BitArray) // 1
  ///     Int8(exactly: "101" as BitArray) // -3
  ///     Int8(exactly: "0101" as BitArray) // 5
  ///
  ///     Int8(exactly: "00000001" as BitArray) // 1
  ///     Int8(exactly: "00000101" as BitArray) // 5
  ///     Int8(exactly: "01111111" as BitArray) // 127
  ///     Int8(exactly: "10000000" as BitArray) // -128
  ///     Int8(exactly: "11111111" as BitArray) // -1
  ///
  ///     Int8(exactly: "00000000000" as BitArray) // 0
  ///     Int8(exactly: "00001111111" as BitArray) // 127
  ///     Int8(exactly: "00010000000" as BitArray) // nil
  ///     Int8(exactly: "11101111111" as BitArray) // nil
  ///     Int8(exactly: "11110000000" as BitArray) // -128
  ///     Int8(exactly: "11111111111" as BitArray) // -1
  @inlinable
  public init?(exactly source: BitArray) {
    let (value, isNegative) = Self._convert(source)
    guard isNegative == (value < 0) else { return nil }
    let words = value.words
    var equal = true
    _ = source._foreachTwosComplementWordDownward(isSigned: Self.isSigned) { i, word in
      assert(equal)
      let w = (
        i < words.count ? words[i]
        : isNegative ? UInt.max
        : UInt.zero)
      equal = (w == word)
      return equal
    }
    guard equal else { return nil }
    self = value
  }

  /// Creates a new instance from the bits in the given bit array, if the
  /// corresponding integer value can be represented exactly.
  /// If the value is not representable exactly, then a runtime error will
  /// occur.
  ///
  /// If `Self` is an unsigned integer type, then the contents of the bit array
  /// are interpreted to be the binary representation of a nonnegative
  /// integer value. The bit array is allowed to contain bits in unrepresentable
  /// positions, as long as they are all cleared.
  ///
  ///     UInt8("" as BitArray) // 0
  ///     UInt8("0" as BitArray) // 0
  ///     UInt8("1" as BitArray) // 1
  ///     UInt8("10" as BitArray) // 2
  ///     UInt8("00000000" as BitArray) // 0
  ///     UInt8("11111111" as BitArray) // 255
  ///     UInt8("0000000000000" as BitArray) // 0
  ///     UInt8("0000011111111" as BitArray) // 255
  ///     UInt8("0000100000000" as BitArray) // ERROR
  ///     UInt8("1111111111111" as BitArray) // ERROR
  ///
  /// If `Self` is a signed integer type, then the contents of the bit array
  /// are interpreted to be a two's complement representation of a signed
  /// integer value, with the last bit in the array representing the sign of
  /// the result.
  ///
  ///     Int8("" as BitArray) // 0
  ///     Int8("0" as BitArray) // 0
  ///     Int8("1" as BitArray) // -1
  ///     Int8("01" as BitArray) // 1
  ///     Int8("101" as BitArray) // -3
  ///     Int8("0101" as BitArray) // 5
  ///
  ///     Int8("00000001" as BitArray) // 1
  ///     Int8("00000101" as BitArray) // 5
  ///     Int8("01111111" as BitArray) // 127
  ///     Int8("10000000" as BitArray) // -128
  ///     Int8("11111111" as BitArray) // -1
  ///
  ///     Int8("00000000000" as BitArray) // 0
  ///     Int8("00001111111" as BitArray) // 127
  ///     Int8("00010000000" as BitArray) // ERROR
  ///     Int8("11101111111" as BitArray) // ERROR
  ///     Int8("11110000000" as BitArray) // -128
  ///     Int8("11111111111" as BitArray) // -1
  @inlinable
  public init(_ source: BitArray) {
    guard let value = Self(exactly: source) else {
      fatalError("""
        BitArray value cannot be converted to \(Self.self) because it is \
        outside the representable range
        """)
    }
    self = value
  }
}

extension BitArray {
  @usableFromInline
  internal func _foreachTwosComplementWordDownward(
    isSigned: Bool,
    body: (Int, UInt) -> Bool
  ) -> Bool {
    self._read {
      guard $0._words.count > 0 else { return false }

      var isNegative = false
      let end = $0.end.endSplit
      assert(end.bit > 0)
      let last = $0._words[end.word]
      if isSigned, last.contains(end.bit - 1) {
        // Sign extend last word
        isNegative = true
        if !body(end.word, last.union(_Word(upTo: end.bit).complement()).value) {
          return isNegative
        }
      } else if !body(end.word, last.value) {
        return isNegative
      }
      for i in stride(from: end.word - 1, through: 0, by: -1) {
        if !body(i, $0._words[i].value) { return isNegative }
      }
      return isNegative
    }
  }
}