kodiak-sets

Get things organized with these powerful, yet easy to use sets. The first set implemented in 0.1.0 was Sequence. From a generic perspective, sequences are ordered sets of elements, with each element at a unique position. Sequence allows to add and remove elements at any position, virtually infinitely.

At first, a Vec<T> looks most appropriate for implementing a sequence. However, when thinking about persisting the sequence, there are some challenges in practice:

• How to store a sequence in a database and retrieve it efficiently?
• How to add elements to a sequence at an arbitrary position efficiently, e.g. without having to change the position of all following elements?
• How to change the position of a single element without the need to change other elements' positions?
• How to avoid the need to re-balance the sequence, i.e. having to rewrite the position of all elements?
• How to scale the approach to hundreds of thousands of operations on the sequence, such as adding, moving and removing elements?

The objective of kodiak-sets implementation of Sequence is to solve these challenges. In 0.1.0 it only offers support for Sequence. In the future, other types of sets might be added.

We use the "mediant fraction" algorithm to define a position within a Sequence. The mediant fraction is a mathematical concept that has been known and used for a long time. It is a method of finding a fraction that lies between two given fractions by taking the sum of the numerators and denominators separately.

The crate is a building block of the Kodiak project, thus the naming of the crate. Kodiak supports sequences of entities at a very large scale. However, the functionality provided by kodiak-sets is useful on its own and might be of interest for other projects as well. That's why we deliver it as a separate crate. So, feel free to use it. If you consider using kodiak-sets in your project but are missing something or have any other concerns, don't hesitate to file an issue on GitHub.

We are looking forward to your feedback.

You may be looking for:

• API documentation
• Release notes

Impressions

todo: show two examples of sequences supported by kodiak-sets.

Provide additional examples in EXAMPLES.md and link to it.

Demonstrate capabilities!

Known issues / limitations

• 🏗️ Version 0.2.0 does not yet power other projects, so API has not yet proven it's power in practice.
• 🚧 Code is fully covered by unit tests, however, some integration tests are still missing.
• Documentation has still some room for improvement.
• 🐧 Version 0.2.x is developed and tested on Linux only.

Roadmap and future considerations

Version 0.4.0 (planned)

• Example showing how to use this library with MySQL.

Version 0.3.0 (planned)

• Reimplement using std::collections::BTreeMap.
• Complete docs #![deny(missing_docs)].
• Example showing how to use this library with PostgreSQL.

Version 0.2.0 (delivered)

• Implement Iterator and IntoIterator for Sequence.
• Support serde's #[derive(Serialize, Deserialize)].
• Support the trait Clone.
• Introduce benchmarking and publish results on GitHub (see benchmarks).

Version 0.1.0 (delivered)

• Initial release.
• Examples to demonstrate the power of fraction based positioning.
• Examples showing how to use this library with SQlite.

Additional resources

• Homepage polarlabs: polarlabs.io
• Crate: crates.io/kodiak-sets
• API documentation: docs.rs/kodiak-sets

Contributing

See CONTRIBUTING for more details.

Appendix

Cargo Geiger Safety Report

Metric output format: x/y
    x = unsafe code used by the build
    y = total unsafe code found in the crate

Symbols: 
    🔒  = No `unsafe` usage found, declares #![forbid(unsafe_code)]
    ❓  = No `unsafe` usage found, missing #![forbid(unsafe_code)]
    ☢️  = `unsafe` usage found

Functions  Expressions  Impls  Traits  Methods  Dependency

0/0        0/0          0/0    0/0     0/0      🔒  kodiak-sets 0.2.0
0/0        0/0          0/0    0/0     0/0      ❓  ├── num-integer 0.1.45
0/0        0/0          0/0    0/0     0/0      ❓  │   └── num-traits 0.2.16
0/0        0/5          0/0    0/0     0/0      ❓  └── serde 1.0.183
0/0        0/0          0/0    0/0     0/0      ❓      └── serde_derive 1.0.183

0/0        0/5          0/0    0/0     0/0    

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or https://opensource.org/licenses/Apache-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Links

[https://www.figma.com/blog/realtime-editing-of-ordered-sequences/]

[https://crates.io/crates/fractional_index]

[https://cs.stackexchange.com/questions/14708/maintaining-an-efficient-ordering-where-you-can-insert-elements-in-between-any]

[https://ccssmathanswers.com/inserting-a-fraction-between-two-given-fractions/]