Code Monkey home page Code Monkey logo

segmentmap's Introduction

SegmentMap

A self-balancing binary search tree for mapping discrete, disjoint segments to values.

segmentmap's People

Stargazers

 avatar

Watchers

 avatar  avatar

segmentmap's Issues

Iterator structs are not exported.

Segments, Values, ValuesMut, Iter, IterMut, and IntoIter are not exported.

Workarounds:

  • There are none, these iterators are temporarily unavailable.

Entries sometimes go missing

I need to find a minimum reproducible example of this (I found this bug at the end of a bit of a marathon debugging session)

It seems to happen during tree-rebalance and in my use-case specifically when deleting a number of entries. In my use case the entries being deleted were mostly, though not exclusively, adjacent

It doesn't make sense to have enumerated types implement `num::One`, `num::Zero`, or `std::ops::Add`.

The convenience constructors (e.g. closed or all) were originally designed for numeric types. The same traits used for numeric types do not work well with enumerated types. A better set of traits would include std::iter::Step (available only with nightly) and std::default::Default. The num::Bounded trait could still be used, but it might be a little confusing because enumerated types are not numeric.

Workarounds:

  • The Segment struct does not require the use of convenience constructors to operate correctly (they are there for convenience). If your type cannot implement num::One, num::Zero, or std::ops::Add, then just use the new constructor which makes a closed-open interval.

Segment map is not self-balancing.

Given the level of effort that it took just to get the segment map working without self-balancing, this hasn't been implemented yet. The plan is to use AVL-style self-balancing in the future. The current testing suite forcibly constructs trees in multiple ways so all tree arrangements should be correct no matter in what order operations are called.

Workarounds:

  • The correctness of the segment map is not dependent on whether it is self-balancing or not. However, without self-balancing, the performance of operations is not the desired O(log n). In fact, my observations suggest the tree is typically linear in practice.

Segments cannot contain maximum value.

Unfortunately, given how segments are represented as closed-open intervals, the maximum value cannot be included in the segment. I have not yet determined a simple, consistent way to address this. For now, this is not a main concern for me as the current implementation fits my needs well enough.

Workarounds:

  • For any of the numeric types, the maximum value should just not be considered a valid value. For example, valid Unicode is from U+0000 to U+10FFFF. Therefore, when representing Unicode using u32, it is safe to ignore 0xFFFFFFFF.
  • For an enumerated type (support for convenience constructors--like closed and all--coming soon with #1), simply append an Unused (or similar) variant to the list of variants. Then, the default #[derive(Ord, PartialOrd)] will have that as the maximum value.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.