🗃️ Non-empty AVL-tree-based look-up. Elements and keys can be of any type

import KeysSet exposing (KeysSet)
import Stack
import User exposing (User(..))


users : Emptiable (KeysSet User User.ByName N1) never_
users =
    KeysSet.fromStack User.byName
        (Stack.topBelow
            (User { name = "Alice", age = 28, height = 1.65 })
            [ User { name = "Bob", age = 19, height = 1.82 }
            , User { name = "Chuck", age = 33, height = 1.75 }
            ]
        )

where

-- module User exposing (ByName, User(..), byName)




import Char.Order
import Keys exposing (Key, Keys)
import KeysSet
import Map exposing (Mapping)
import N exposing (N1)
import Order
import String.Order


type User
    = User { name : String, age : Int, height : Float }


type Name
    = Name


name : Mapping User Name String
name =
    Map.tag Data (\(User userData) -> userData.name)


type alias ByName =
    { name :
        Key
            User
            (Order.By
                Name
                (String.Order.Earlier
                    (Char.Order.AToZ Char.Order.LowerUpper)
                )
            )
            String
            N1
    }


byName : Keys User ByName N1
byName =
    Keys.for (\name_ -> { name = name_ })
        |> Keys.by ( identity, Map.identity )
            (String.Order.earlier
                (Char.Order.aToZ Char.Order.lowerUpper)
            )

KeysSet containing a single given element.

You don't need to provide Keys

Convert to a KeysSet, ⚠️ ignoring elements whose keys already exist earlier in the Stack

KeysSet.fromStack User.byHandle
    (Stack.topBelow
        -- ↓ won't be part of the KeysSet
        { handle = "cr", shown = "chris \\o/" }
        [ { handle = "ann", shown = "Ann in stand by" }
        , -- ↓ will be part of the KeysSet
          { handle = "cr", shown = "creeper" }
        ]
    )

Convert to a KeysSet, ⚠️ ignoring elements whose keys already exist earlier in the List

KeysSet.fromList User.byHandle
    [ -- ↓ won't be part of the KeysSet
      { handle = "cr", shown = "chris \\o/" }
    , { handle = "ann", shown = "Ann in stand by" }
    , -- ↓ will be part of the KeysSet
      { handle = "cr", shown = "creeper" }
    ]

For construction, use fromStack instead, proving to the compiler what you already know about its (non-)emptiness

Number of elements in the KeysSet. Runtime 1

KeysSet.one { name = "Helium", symbol = "He", atomicNumber = 2 }
    |> KeysSet.size
--> 1

Access the element associated with a given key. If no element with the given key is not present, Emptiable.empty

import Emptiable exposing (Emptiable, filled)
import Typed
import Stack
import N exposing (N1)
import Keys exposing (Keys, Key)
import KeysSet exposing (KeysSet)
import Map exposing (Mapping)
import Order
import Char.Order
import String.Order


type alias Animal =
    { name : String
    , kind : AnimalKind
    }


type AnimalKind
    = Mouse
    | Cat


type alias ByName =
    { name :
        Key
            Animal
            (Order.By
                Name
                (String.Order.Earlier
                    (Char.Order.AToZ Char.Order.LowerUpper)
                )
            )
            String
            N1
    }


animals : Emptiable (KeysSet Animal ByName N1) never_
animals =
    KeysSet.fromStack animalByName
        (Stack.topBelow
            { name = "Tom", kind = Cat }
            [ { name = "Jerry", kind = Mouse }
            ]
        )


type Name
    = Name -- not exposed


name : Mapping Animal Name String
name =
    Map.tag Name .name


animalByName : Keys Animal ByName N1
animalByName =
    Keys.for (\name_ -> { name = name_ })
        |> Keys.by ( .name, name )
            (String.Order.earlier
                (Char.Order.aToZ Char.Order.lowerUpper)
            )


animals |> KeysSet.element ( animalByName, .name ) "Tom" |> Emptiable.map .kind
--> filled Cat


animals |> KeysSet.element ( animalByName, .name ) "Jerry" |> Emptiable.map .kind
--> filled Mouse


animals |> KeysSet.element ( animalByName, .name ) "Spike" |> Emptiable.map .kind
--> Emptiable.empty

The element associated with the lowest key

import Linear exposing (Direction(..))
import Emptiable exposing (Emptiable)
import N exposing (N1)
import Stack
import KeysSet exposing (KeysSet)
import Map exposing (Mapping)
import Order
import Char.Order
import String.Order
import Keys exposing (Keys, Key)


users : Emptiable (KeysSet User ByName N1) never_
users =
    KeysSet.fromStack userByName
        (Stack.topBelow
            { name = "Bob", age = 19, height = 1.80 }
            [ { name = "Alia", age = 28, height = 1.69 }
            , { name = "Chucki", age = 33, height = 1.75 }
            ]
        )


users |> KeysSet.end ( userByName, .name ) Down
--> { name = "Alia", age = 28, height = 1.69 }


users |> KeysSet.end ( userByName, .name ) Up
--> { name = "Chucki", age = 33, height = 1.75 }


type alias User =
    { name : String
    , age : Int
    , height : Float
    }


type alias ByName =
    { name :
        Key
            User
            (Order.By
                Name
                (String.Order.Earlier
                    (Char.Order.AToZ Char.Order.LowerUpper)
                )
            )
            String
            N1
    }


type Name
    = Name -- not exposed


name : Mapping User Name String
name =
    Map.tag Name .name


userByName : Keys User ByName N1
userByName =
    Keys.for (\name_ -> { name = name_ })
        |> Keys.by ( .name, name )
            (String.Order.earlier
                (Char.Order.aToZ Char.Order.lowerUpper)
            )

Notice how we safely avoided returning a Maybe through the use of Emptiable ... Never

If you don't know whether the KeysSet will be empty

users
    |> Emptiable.map (filled >> KeysSet.end ( userByName, .name ) Down)
--: Emptiable element Possibly

Insert a given element. If the element you wanted to insert already has elements with a matching key (collisions), keep the existing collision elements instead. To replace collisions instead → insertReplacingCollisions

import BracketPair
import Emptiable


Emptiable.empty
    |> KeysSet.insertIfNoCollision BracketPair.keys
        { open = 'b', closed = 'C' }
    |> KeysSet.insertIfNoCollision BracketPair.keys
        { open = 'c', closed = 'A' }
    |> KeysSet.insertIfNoCollision BracketPair.keys
        { open = 'c', closed = 'C' }
    |> KeysSet.toList ( BracketPair.keys, .open )
--> [ { open = 'b', closed = 'C' }, { open = 'c', closed = 'A' } ]

Insert a given element. If the element you wanted to insert already has elements with a matching key (collisions), replace all collisions. To keep collisions instead → insertIfNoCollision

import BracketPair
import Emptiable


Emptiable.empty
    |> KeysSet.insertReplacingCollisions BracketPair.keys
        { open = 'b', closed = 'C' }
    |> KeysSet.insertReplacingCollisions BracketPair.keys
        { open = 'c', closed = 'A' }
    |> KeysSet.insertReplacingCollisions BracketPair.keys
        { open = 'c', closed = 'C' }
    |> KeysSet.toList ( BracketPair.keys, .open )
--> [ { open = 'c', closed = 'C' } ]

Remove its element whose key matches the given one. If the key is not found, no changes are made

import Character


KeysSet.fromList Character.keys
    [ { id = 0, char = 'A' }
    , { id = 1, char = 'B' }
    ]
    |> KeysSet.insertIfNoCollision Character.keys
        { id = 2, char = 'C' }
    |> KeysSet.remove ( Character.keys, .id ) 2
    |> KeysSet.toList ( Character.keys, .id )
--> [ { id = 0, char = 'A' }
--> , { id = 1, char = 'B' }
--> ]

Change the element with a given key in a given way Only actually alter the element if the result doesn't have existing elements with a matching key (collisions). To replace collisions with the result instead → elementAlterReplacingCollisions

import Character


KeysSet.fromList Character.keys
    [ { id = 0, char = 'A' }, { id = 1, char = 'B' } ]
    |> KeysSet.elementAlterIfNoCollision ( Character.keys, .id )
        1
        (\c -> { c | char = 'C' })
        -- gets changed
    |> KeysSet.elementAlterIfNoCollision ( Character.keys, .id )
        1
        (\c -> { c | id = 0 })
        -- doesn't get changed
    |> KeysSet.toList ( Character.keys, .id )
    --> [ { id = 0, char = 'A' }, { id = 1, char = 'C' } ]

If you want to sometimes remove or insert a new value on empty for example, first ask for the element with the same key, then match the Emptiable and operate as you like

Change the element with a given key in a given way If the result has existing elements with a matching key (collisions), replace them. To not alter the element if there are collisions with the result instead → elementAlterIfNoCollision

import Character


KeysSet.fromList Character.keys
    [ { id = 0, char = 'A' }, { id = 1, char = 'B' } ]
    |> KeysSet.elementAlterIfNoCollision ( Character.keys, .id )
        1
        (\c -> { c | char = 'C' })
        -- gets changed
    |> KeysSet.elementAlterIfNoCollision ( Character.keys, .id )
        1
        (\c -> { c | id = 0 })
        -- doesn't get changed
    |> KeysSet.toList ( Character.keys, .id )
    --> [ { id = 0, char = 'A' }, { id = 1, char = 'C' } ]

If you want to sometimes remove or insert a new value on empty for example, first ask for the element with the same key, then match the Emptiable and operate as you like

Change each element based on its current value.

Runtime n * log n because mapped keys could be different (many other dicts/sets have runtime n)

If the keys of the mapped elements collide, there's no promise of which element will be in the final mapped KeysSet

Try to change each element based on its current value. Often, this is called "filterMap"

Runtime n * log n just like KeysSet.map because mapped keys could be different

If the keys of the mapped elements collide, there's no promise of which element will be in the final mapped KeysSet

{-| Keep only elements that pass a given test.
Often called "filter"
-}
when orderKey isGood =
    KeysSet.fillsMap
        (\element ->
            if element |> isGood then
                Just element


            else
                Nothing
        )
        orderKey

Combine with another KeysSet. On key collision, keep the current KeysSet's element.

(To instead replace current elements with incoming elements, swap the arguments)

Keep only those elements whose keys don't appear in the given KeysSet

import Character


KeysSet.fromList Character.keys
    [ { id = 0, char = 'A' }
    , { id = 1, char = 'B' }
    , { id = 2, char = 'c' }
    , { id = 3, char = 'd' }
    ]
    |> KeysSet.except ( Character.keys, .id )
        (KeysSet.fromList Character.keys
            [ { id = 2, char = 'c' }
            , { id = 3, char = 'd' }
            , { id = 4, char = 'e' }
            , { id = 5, char = 'f' }
            ]
            |> KeysSet.toKeys ( Character.keys, .id )
        )
    |> KeysSet.toList ( Character.keys, .id )
--> [ { id = 0, char = 'A' }
--> , { id = 1, char = 'B' }
--> ]

Keep each element whose key also appears in a given KeysSet

Most powerful way of combining 2 KeysSets

Traverses all the keys from both KeysSets from lowest to highest, accumulating whatever you want for when a key appears in the first AndOr second KeysSet.

You will find this as "merge" in most other dictionaries/sets, except that you have the diff as a value you can reduce with instead of separate functions for "only first", "only second" and "both".

To handle the AndOr cases, use a case..of or the helpers in elm-and-or

Most powerful way of combining 2 KeysSets

Traverses all the keys from both KeysSets from lowest to highest, accumulating whatever you want for when a key appears in the first AndOr second KeysSet.

You will find this as "merge" in most other dictionaries/sets, except that you have the diff as a value you can reduce with instead of separate functions for "only first", "only second" and "both".

To handle the AndOr cases, use a case..of or the helpers in elm-and-or

A KeysSet sorted by the identity of one of the keys of the original set. Runtime is O(n).

Convert to a List sorted by a given key

import Stack
import Order
import Char.Order
import String.Order
import Keys exposing (Keys, Key)
import KeysSet


nameAlphabetical : Keys.Identity String (String.Order.Earlier (Char.Order.AToZ Char.Order.LowerUpper))
nameAlphabetical =
    Keys.identity
        (String.Order.earlier
            (Char.Order.aToZ Char.Order.lowerUpper)
        )


KeysSet.fromStack nameAlphabetical
    (Stack.topBelow "Bob" [ "Alice" ])
    |> KeysSet.toStack ( nameAlphabetical, identity )
--> Stack.topBelow "Alice" [ "Bob" ]


KeysSet.fromStack nameAlphabetical
    (Stack.topBelow "Bob" [ "Alice", "Christoph" ])
    |> KeysSet.toStack ( nameAlphabetical, identity )
    |> Stack.reverse
--> Stack.topBelow "Christoph" [ "Bob", "Alice" ]

The cool thing is that information about (non-)emptiness is carried over to the stack

Use this to fold over its elements

import Stack
import Int.Order
import Keys exposing (Keys, Key)
import KeysSet
import Linear exposing (Direction(..))


intUp : Keys.Identity Int Int.Order.Up
intUp =
    Keys.identity Int.Order.up


KeysSet.fromStack intUp
    (Stack.topBelow 345 [ 234, 543 ])
    |> KeysSet.toStack ( intUp, identity )
--> Stack.topBelow 234 [ 345, 543 ]
--  the type knows it's never empty


KeysSet.fromStack intUp
    (Stack.topBelow 1 [ 2, 8, 16 ])
    |> KeysSet.toStack ( intUp, identity )
    |> Stack.fold Down (\n soFar -> soFar - n)
--> 5

Convert to a List

import Stack
import Keys exposing (Keys, Key)
import KeysSet
import Char.Order
import String.Order


nameAlphabetical : Keys.Identity String (String.Order.Earlier (Char.Order.AToZ Char.Order.LowerUpper))
nameAlphabetical =
    Keys.identity
        (String.Order.earlier
            (Char.Order.aToZ Char.Order.lowerUpper)
        )


KeysSet.fromStack nameAlphabetical
    (Stack.topBelow "Bob" [ "Alice" ])
    |> KeysSet.toList ( nameAlphabetical, identity )
--> [ "Alice", "Bob" ]


KeysSet.fromStack nameAlphabetical
    (Stack.topBelow "Bob" [ "Alice" ])
    |> KeysSet.toList ( nameAlphabetical, identity )
    |> List.reverse
--> [ "Bob", "Alice" ]

to carry over information about (non-)emptiness → toStack

Using == on KeysSets will be slower than toList if you have more than 2 keys.

Fold over its elements from an initial accumulator value in a given Direction

import Linear exposing (Direction(..))
import Stack
import Int.Order
import KeysSet
import Keys


KeysSet.fromStack intUp
    (Stack.topBelow 234 [ 345, 543 ])
    |> KeysSet.foldFrom ( intUp, identity ) [] Down (::)
--> [ 234, 345, 543]


KeysSet.fromStack intUp
    (Stack.topBelow 5 [ 7, -6 ])
    |> KeysSet.foldFrom ( intUp, identity ) 0 Up (+)
--> 6


intUp : Keys.Identity Int Int.Order.Up
intUp =
    Keys.identity Int.Order.up

Fold, starting from one end element transformed to the initial accumulation value, then reducing what's accumulated in a given Direction

import Linear exposing (Direction(..))
import Stack
import Int.Order
import Keys
import KeysSet


KeysSet.fromStack intUp
    (Stack.topBelow 234 [ 345, 543 ])
    |> KeysSet.foldFromOne ( intUp, identity )
        Stack.one
        Up
        Stack.onTopLay
--> Stack.topBelow 543 [ 345, 234 ]


intUp : Keys.Identity Int Int.Order.Up
intUp =
    Keys.identity Int.Order.up

foldFrom with the ability to stop early once a given reduce function returns a Complete value.

import Linear exposing (Direction(..))
import Stack
import Int.Order
import KeysSet
import Keys
-- from lue-bird/partial-or-complete
import PartialOrComplete exposing (PartialOrComplete(..))


KeysSet.fromList intUp [ 11, 21, 31, 41, 51 ]
    -- do we have a sum >= 100?
    |> KeysSet.foldUntilCompleteFrom ( intUp, identity )
        0
        Up
        (\n sumSoFar ->
            if sumSoFar >= 100 then
                -- no need to sum the rest!
                () |> Complete
            else
                sumSoFar + n |> Partial
        )
    |> PartialOrComplete.isComplete
--> True




intUp : Keys.Identity Int Int.Order.Up
intUp =
    Keys.identity Int.Order.up

foldFromOne with the ability to stop early once a given reduce function returns a Complete value.

import Linear exposing (Direction(..))
import Stack
import Int.Order
import KeysSet
import Keys
-- from lue-bird/partial-or-complete
import PartialOrComplete exposing (PartialOrComplete(..))


KeysSet.fromStack intUp
    (Stack.topBelow 11 [ 21, 31, 41, 51 ])
    -- take the last 3
    |> KeysSet.foldUntilCompleteFromOne ( intUp, identity )
        (\lastElement ->
            { stack = lastElement |> Stack.one
            , length = 1
            }
                |> Partial
        )
        Down
        (\element soFar ->
            if soFar.length >= 3 then
                soFar.stack |> Complete
            else
                { stack = soFar.stack |> Stack.onTopLay element
                , length = soFar.length + 1
                }
                    |> Partial
        )
    -- if we have less than 3 elements, that's fine, too
    |> PartialOrComplete.completeElseOnPartial .stack
--> Stack.topBelow 31 [ 41, 51 ]




intUp : Keys.Identity Int Int.Order.Up
intUp =
    Keys.identity Int.Order.up