Modules 31
Data.IntSet.Internal.IntTreeCommons
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.
1 generation diagnostics
- unattached documentation comment at 113:1
newtype Prefix
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.
Prefix :: Int -> Prefix
unPrefix :: Prefix -> Int
nomatch :: Int -> Prefix -> Bool
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
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
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
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.
ABL :: TreeTreeBranch
A contains B in the left child
ABR :: TreeTreeBranch
A contains B in the right child
BAL :: TreeTreeBranch
B contains A in the left child
BAR :: TreeTreeBranch
B contains A in the right child
EQL :: TreeTreeBranch
A and B have equal prefixes
NOM :: TreeTreeBranch
A and B have prefixes that do not match
treeTreeBranch :: Prefix -> Prefix -> TreeTreeBranch
Calculates how two Bins relate to each other by comparing their
Prefixes.
mask :: Int -> Int -> Prefix
The prefix of Int i up to the switching bit m.
branchMask :: Int -> Int -> Int
The first switching bit where the two Ints disagree.
Precondition for defined behavior: i1 /= i2
branchPrefix :: Int -> Int -> Prefix
The shared prefix of two Ints.
Precondition for defined behavior: i1 /= i2
i2w :: Int -> Word
data Order
A_LT_B :: Order
A_Prefix_B :: Order
A_EQ_B :: Order
B_Prefix_A :: Order
A_GT_B :: Order
Instances
2
instance Eq Prefixinstance Lift Prefix
Build record and source files
Community contribution. The service has not verified this documentation. The generator reported 15 diagnostics.
Target: Linux on x86-64. Some inferred types and resolved links are not available.
Generator: aihc-haddock-aa6debbd-web-3
Metadata snapshot: 634f718c0d8cd970c4e2c511d2345d8fd36c6dc32b06343c2b4e914ffccbce7f
Open the dependency plan · Download the documentation model
- aihc-base-4.21.2.0 · Core library · Cabal file
- aihc-internal-9.1204.0 · Core library · Cabal file
- aihc-prim-0.13.0 · Core library · Cabal file
- aihc-rts-1.0.2 · Core library · Cabal file
- aihc-template-haskell-2.23.0.0 · Core library · Cabal file
- array-0.5.8.0 · Cabal revision 2 · Cabal file · Source archive
- containers-0.8.1 · Cabal revision 0 · Cabal file · Source archive
- deepseq-1.5.2.0 · Cabal revision 0 · Cabal file · Source archive