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

import KeysSet exposing (KeySet)
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 Order
import String.Order


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


type Name
    = Name


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


type alias ByName =
    Keys.Key
        User
        (Order.By
            Name
            (String.Order.Earlier
                (Char.Order.AToZ Char.Order.LowerUpper)
            )
        )
        String
        N1


byName : Keys User ByName N1
byName =
    Keys.oneBy name
        (String.Order.earlier
            (Char.Order.aToZ Char.Order.lowerUpper)
        )

Use IdentitySet when you just want a Set with non-comparable element.

The type allows you to just annotate a KeysSet without creating an alias for the keys:

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


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


sumbers : Emptiable (IdentitySet Int Int.Order.Up) never_
sumbers =
    KeysSet.fromStack intUp (Stack.topBelow 345 [ 234, 543 ])


sumbers |> KeysSet.toStack intUp
--> Stack.topBelow 234 [ 345, 543 ]

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 =
    Keys.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.oneBy name
        (String.Order.earlier
            (Char.Order.aToZ Char.Order.lowerUpper)
        )


animals |> KeysSet.element animalByName "Tom" |> Emptiable.map .kind
--> filled Cat


animals |> KeysSet.element animalByName "Jerry" |> Emptiable.map .kind
--> filled Mouse


animals |> KeysSet.element animalByName "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 Down
--> { name = "Alia", age = 28, height = 1.69 }


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


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


type alias ByName =
    Keys.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.oneBy 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 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
import Keys exposing (key)


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 (key .open BracketPair.keys)
--> [ { 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
import Keys exposing (key)


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 (key .open BracketPair.keys)
--> [ { 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
import Keys exposing (key)


KeysSet.fromList Character.keys
    [ { id = 0, char = 'A' }
    , { id = 1, char = 'B' }
    ]
    |> KeysSet.insertIfNoCollision Character.keys
        { id = 2, char = 'C' }
    |> KeysSet.remove (key .id Character.keys) 2
    |> KeysSet.toList (key .id Character.keys)
--> [ { 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
import Keys exposing (key)


KeysSet.fromList Character.keys
    [ { id = 0, char = 'A' }, { id = 1, char = 'B' } ]
    |> KeysSet.elementAlterIfNoCollision (key .id Character.keys)
        1
        (\c -> { c | char = 'C' })
        -- gets changed
    |> KeysSet.elementAlterIfNoCollision (key .id Character.keys)
        1
        (\c -> { c | id = 0 })
        -- doesn't get changed
    |> KeysSet.toList (key .id Character.keys)
    --> [ { 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
import Keys exposing (key)


KeysSet.fromList Character.keys
    [ { id = 0, char = 'A' }, { id = 1, char = 'B' } ]
    |> KeysSet.elementAlterIfNoCollision (key .id Character.keys)
        1
        (\c -> { c | char = 'C' })
        -- gets changed
    |> KeysSet.elementAlterIfNoCollision (key .id Character.keys)
        1
        (\c -> { c | id = 0 })
        -- doesn't get changed
    |> KeysSet.toList (key .id Character.keys)
    --> [ { 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
import Keys exposing (key)


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


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


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


KeysSet.fromStack nameAToZ
    (Stack.topBelow "Bob" [ "Alice", "Christoph" ])
    |> KeysSet.toStack nameAToZ
    |> 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 (IdentityKeys)
import KeysSet
import Linear exposing (Direction(..))


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


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


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

Convert to a List

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


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


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


KeysSet.fromStack nameAToZ
    (Stack.topBelow "Bob" [ "Alice" ])
    |> KeysSet.toList nameAToZ
    |> 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 exposing (IdentityKeys)


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


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


intUp : IdentityKeys 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 exposing (IdentityKeys)
import KeysSet


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


intUp : IdentityKeys 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 exposing (IdentityKeys)
-- 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
        0
        Up
        (\n sumSoFar ->
            if sumSoFar >= 100 then
                -- no need to sum the rest!
                () |> Complete
            else
                sumSoFar + n |> Partial
        )
    |> PartialOrComplete.isComplete
--> True




intUp : IdentityKeys 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 exposing (IdentityKeys)
-- 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
        (\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 : IdentityKeys Int Int.Order.Up
intUp =
    Keys.identity Int.Order.up