| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.IntSet.Internal.IntTreeCommons
Description
WARNING
This module is considered internal.
The Package Versioning Policy does not apply.
The contents of this module may change in any way whatsoever and without any warning between minor versions of this package.
Authors importing this module are expected to track development closely.
Description
This module defines common constructs used by both Data.IntSet and Data.IntMap.
Since: containers-0.8
Synopsis
- type Key = Int
- newtype Prefix = Prefix {}
- nomatch :: Int -> Prefix -> Bool
- left :: Int -> Prefix -> Bool
- signBranch :: Prefix -> Bool
- data TreeTreeBranch
- treeTreeBranch :: Prefix -> Prefix -> TreeTreeBranch
- mask :: Key -> Int -> Int
- branchMask :: Int -> Int -> Int
- i2w :: Int -> Word
- data Order
- = A_LT_B
- | A_Prefix_B
- | A_EQ_B
- | B_Prefix_A
- | A_GT_B
Documentation
A Prefix represents some prefix of high-order bits of an Int.
A Prefix is usually considered in the context of a
Bin or Bin.
nomatch :: Int -> Prefix -> Bool Source #
Whether the Int does not start with the given Prefix.
An Int starts with a Prefix if it shares the high bits with the internal
Int value of the Prefix up to the mask bit.
nomatch is usually used to determine whether a key belongs in a Bin,
since all keys in a Bin share a Prefix.
left :: Int -> Prefix -> Bool Source #
Whether the Int is to the left of the split created by a Bin with this
Prefix.
This does not imply that the Int belongs in this Bin. That fact is
usually determined first using nomatch.
signBranch :: Prefix -> Bool Source #
Whether this Prefix splits a Bin at the sign bit.
This can only be True at the top level. If it is true, the left child contains non-negative keys and the right child contains negative keys.
data TreeTreeBranch Source #
A TreeTreeBranch is returned by treeTreeBranch to indicate how two
Bins relate to each other.
Consider that A and B are the Bins whose Prefixes are given to
treeTreeBranch as the first and second arguments respectively.
treeTreeBranch :: Prefix -> Prefix -> TreeTreeBranch Source #
mask :: Key -> Int -> Int Source #
The prefix of key i up to (but not including) the switching
bit m.
branchMask :: Int -> Int -> Int Source #
The first switching bit where the two prefixes disagree.
Precondition for defined behavior: p1 /= p2
Constructors
| A_LT_B | |
| A_Prefix_B | |
| A_EQ_B | |
| B_Prefix_A | |
| A_GT_B |