* Create Screen Shot 2021-05-17 at 7.15.09 PM.png

* Delete Screen Shot 2021-05-17 at 7.15.09 PM.png

* Create BitArray.swift

* Update BitArray.swift

* Update BitArray.swift

* Update BitArray.swift

* Added BitArray as a product to the package

* Update Package.swift

* Update Package.swift

* Update Package.swift

* Update BitArray.swift

* Update Package.swift

* Update Collections.swift

* Update Collections.swift

* Update Package.swift

* Create BitArray.xcscheme

* Update BitArray.swift

* Update BitArray.swift

* Update BitArray.swift

* build: add a CMake based build system (#42)

Add a CMake based build system to enable bootstrapping the toolchain
with the ability to use Swift Collections in SPM.

* Update BitArray.swift

* Update BitArray.swift

* git: ignore vim swap files (#41)

* Initial conformation to Collection. Lots of faulty code right now

* Update BitArray.swift

* Update BitArray.swift

* Update BitArray.swift

* Update BitArray.swift

* Update BitArray.swift

* Update BitArray.swift

* Update BitArray.swift

* Update BitArray.swift

* [Deque] Work around stdlib issue with Array.withContiguousStorageIfAvailable (#44)

Resolves #27.

* [manifest] Ignore CMake files (#47)

The package manager doesn’t like it when it finds unexpected non-source files in source directories.

* [meta] Update dependencies (#48)

(This only affects local development.)

* [Deque][NFC] Remove unused code (#49)

* Changes to support OpenBSD. (#52)

* [cmake] Support amd64 architecture name.

On OpenBSD, "x86_64" is called "amd64", and therefore recognition of this
name is required for the cmake build.

* [cmake] Add missing file.

This is required since, for example, `Deque+Extras` requires
`_withContiguousStorageIfAvailable_SR14663`.

* ManagedBuffer.capacity is unavailable on OpenBSD.

ManagedBuffer requires nonstandard API to implement `capacity` and
subsequently is unavailable on OpenBSD. For portability, just use
`minimumCapacity` on this platform.

* Fixed subscript to have bit manipulations

* Update BitArray.swift

* Update BitArray.swift

* Moved Collection Conformance into appropriate file

* Implements some bit manip

* Fixed issue with endIndex resetting when storage element is full

When an element of the storage array in the BitArray filled, the endIndex would reset to 0, but then would be the correct value at any other time. This was due to a calculation error in endIndex

* Update invalid OrderedDictionary invariant check. (#53)

* Added XCTests, MutableCollection Conformance, Fixed endIndex bug

MutableCollection conformance still has bugs to be fixed
Additionally, the code is still very rough
endIndex had an issue where it was 0 when the array was empty. Fixed this by switching the code for count and endIndex, and making endIndex = 1 when count is 0

* Update BitArrayTests.swift

* Fixed subscript bug

Wouldn't work sometimes when current value was true because the return for `storage[index] & mask` could be anything >= 1, and not == 1, hence resulting in a unwanted toggle of the value. Fixed by comparing a boolean value of the current value to the boolean value of the newValue instead of the integers

* Code clean up ish

* Fixing a small typo on quick help documentation. (#55)

* Modifying Existing Code From Feedback

- `endIndex` corrected
- changed `remaining` in `count` to use ternary operator instead of being a computed local variable
- added `_split` as a helper function to `subscript`
- modified `set{...}` portion of `subscript` and included comments of the different options
- removed `clear()` as `removeAll()` seems to already exist somewhere
- modified unit tests to have a new BitArray for every test instead of a shared one
- Improved `testSubscriptSetOnly()` to hopefully be more thorough

* Added Bitwise Operations (No Tests)

Both mutable and immutable OR, AND, XOR operations

* Mark OrderedSetDiffingTests with availability (#54)

* Added Rough Bitwise Operation UnitTests

* Added BitSet Files

Did not add methods as I know a lot will go in BitStorage, which Im still figuring out

* Beginning implementations for BitSet

* Mutating Bitwise Operations

Performance-UNfriendly starter implementations

* Fixed subscript set mask for the &= operation and changed fatalErrors to preconditions

changed mask on &= operation from 0 to ~mask

* Also corrected subscript set test to fail if mask of 0 was used (instead of ~mask)

* Implemented BitSet with BitArray storage type and some tests

Tests are not yet passing. Pushing early so mentor can see progress
So sorry for waiting to push so late!

* Fixed error in first BitSet test ( which is testAppend() ) so it passes!

* BitSet formUnion initial implementation

* formUnion() test added and implementation modified to pass test

formUnion() is still incomplete and needs more tests atm

* Finished formUnion() for BitSet

* Modified formUnion() to use bit shifts instead

* Initial formIntersection function for BitSet

Untested

* Added an array view for BitSet, fixed BitSet.count bug, added and modified tests

* Initial Cartesian Product implementation and unfinished test

* Update BitArrayConformances.swift

* [CMake] swift-collections → SwiftCollections (#60)

* [CMake] swift-collections → SwiftCollections

This is an integration FIXME for SwiftPM: swiftlang/swift-package-manager#3595 (comment)

* [CMake] Generate exports under cmake/modules/SwiftCollectionsConfig.cmake

* Work around another MergeModules crash (#62)

* [utils] Add utility for shuffling sources to help reproduce MergeModules issues

* [Deque] Collapse Sequence/Collection conformances into a single file

The MergeModules phase in the compiler is broken: it isn’t always able to correctly handle circular dependencies across source files, like the ones that keep organically popping up with Sequence/Collection conformances that are defined in separate files.

Such dependencies sometimes triggers a compiler crash, depending on some (unknown) environmental parameters.

Trying to manually find and eliminate these circular dependencies has not proved productive. Instead, roll all Collection conformances into a single, huge source file.

* [Deque] Update CMakeLists

* [test] checkCollection: Don’t pass decreasing indices to distance(from:to:) (#63)

Also, try running the conformance checkers on the minimal collection types to catch similar issues.

* Attempting to make an Index

* First steps in implementing Index struct for BitSet

* Fixed up endIndex

* Last tweaks of tonight

Tomorrow: fix up Index implementations, SetAlgebra, Unit Testing

* Adding index function preconditions

* Altered index(_ index: Index, offsetBy distance: Int) -> Index

* Update BitSetConformances.swift

* Update BitSetBitwiseOperations.swift

* Time for SetAlgebra!

* Transitioning to using CollectionsTestSupport

* Conformance to Set Algebra (without bringing in bitarray methods)

* Overloaded Bitwise Operators on BitArray

* Tilday (bitwiseNOT operations)

* Fixed coding style - 2 space indents

* Initial implementation od initializers

Bug found

* Fixed count bug

* Completed and XCTested BitArray initializers

By"XCTested" I mean using my own XCTests without the thorough CollectionsTestSupport

* Update BitArray.swift

* BitSet Initializers -- XCTested

By "XCTested" I mean not thoroughly tested with the CollectionsTestSupport methods

* BitSet's "custom" SetAlgebra

* contains(Int) and dropExcessFalses() methods for BitSet

* Consistently use UNIT.bitWidth instead of the number 8

This will be useful for benchmarking purposes

* Modified BitArray.swift according to feedback

Also added more typealias consistencies (using `UNIT.max` instead of hardcoded 255)

* Modified BitArray bitwise operations according to feedback

Added overloaded mutating operators

* Modified BitArrayConformances.swift according to feedback

* Modified BitArrayOperations.swift according to feedbacl

* Adjust Bitwise Operations' naming to be consistent with that of the atomics package

* .

* Modified According to Feedback

* testing

* First working test using CollectionsTestSupport

Testing sequence initializer

* All initializer tests for BitArray (except using BitSet)

* Update BitArrayTests.swift

* BitArray Append test

* Improved BitArray append() test to test multiple appends

* Untested remove functions

Also updated any UInt8 usages to use the UNIT typealias instead

* BitArray removeLast() Test

* Update BitArrayTests.swift

* BitArray removeAll() test

* BitArray removeLast(_ rangeSize: Int) function test and bug fix

* BitArray removet(at: Int) tests

Also added test for discardable results for current and existing remove tests

* BitArray removeFirst(_ rangeSize: Int) test implemented and passing

Current method has terrible run time for now as I can't get the optimized version to work yet

* BitArray first and last true index functions TEST and BUG FIX

firstTrueIndex()
lastTrueIndex()

* Failing OR and AND bitwise operations test on BitArray

* Update BitArrayTests.swift

* Update BitArrayTests.swift

* Update BitArrayTests.swift

* PUSHHHHH

* removeFirst(_ rangeSize: Int) optimization/bugFix

* BitArray bitwise operations tests and bug fixes

* BitSet tests, bug fixes, and name changes

sequence init test and bug fix
change "UNIT" to "WORD"

* Update BitArrayTests.swift

* add BitSet layout to test support

* BitSet testExpressibleByArrayLiteralAndArrayLiteralInit()

* testExpressibleByArrayLiteralAndArrayLiteralInit()

* BitSet insert and contains functions test + bug fixes

* forceInsert test for BitSet

* BitSet remove function test and improvements

* Update BitSetSetAlgebra.swift

* BitSet intersection tests and bug fixes

* BitSet symmetricDifference test and bug fix

* starting index test and found interesting bug...

* BitArray init(BitSet) test

* Update BitSetTests.swift

* patch

* bug fix in BitSet index after

* BitSet index before test

* Clean up unneeded code

* Delete BitArrayBenchmarks.swift

* My added, not-working benchmark

* BitSet init from BitArray benchmark

* BiSet insert benchmark

* BitSet forceInsert benchmark

* Passing BitSet index offset by test

I plan to add more to the test to test offsets from indices in the middle and not just start and end

* BitArray testing modification to accommodate varying WORD sizes

* Minor comment clean-up

* Correcting bitset tests for varying WORD sizes

* Headers with License info

* simple set operation comparison

incomplete

* .

* adjustments

* Update BitSetOperations.swift

* Benchmarks and preconditions

* Update BitArrayOperations.swift

* Update BitSetTests.swift

* quick edits

* .

* Documentation for bitwise operations and some initializers

* Testing `==` operator to ensure bug fix

* BitSet SetAlgebra and Operations Documentation

* Update BitSetOperations.swift

Co-authored-by: Saleem Abdulrasool <compnerd@compnerd.org>
Co-authored-by: Karoy Lorentey <klorentey@apple.com>
Co-authored-by: 3405691582 <dsk@google.com>
Co-authored-by: Vihan <vihan_bhargava@apple.com>
Co-authored-by: Rodrigo Kreutz <8869678+rkreutz@users.noreply.github.com>
Co-authored-by: Andrew Monshizadeh <1282845+amonshiz@users.noreply.github.com>