<commit_before>module CollectionsNg.Hamt
    exposing
        ( Tree
        , empty
        , hashPositionWithShift
        , countBits
        , get
        , set
        , remove
        , foldl
        , size
        )

import Array
import Bitwise
import List.Extra exposing (find)

type alias Blobs comparable v =
    Array.Array (Node comparable v)

type alias Tree comparable v =
    { positionMap : Int
    , blobs : Blobs comparable v
    }


type Node comparable v
    = Empty
    | Element Int comparable v
    | SubTree (Tree comparable v)
    | Collision Int (List ( comparable, v ))


empty : Tree comparable v
empty =
    { positionMap = 0
    , blobs = Array.repeat 32 Empty
    }


valueByIndex : Int -> Tree comparable v -> Node comparable v
valueByIndex idx ls =
    case Array.get idx ls.blobs of
        Just node ->
            node
        Nothing ->
            Debug.crash "Index out of bounds"


setByIndex : Int -> Node comparable v -> Tree comparable v -> Tree comparable v
setByIndex idx val ls =
    let
        mask =
            0x01 `Bitwise.shiftLeft` idx

        alteredBitmap =
            case val of
                Empty ->
                    ls.positionMap `Bitwise.xor` mask

                _ ->
                    ls.positionMap `Bitwise.or` mask
    in
        { ls | positionMap = alteredBitmap, blobs = Array.set idx val ls.blobs}


hashPositionWithShift : Int -> Int -> Int
hashPositionWithShift shift hash =
    Bitwise.and 0x1F <| Bitwise.shiftRightLogical hash shift


{-| No idea how this works. Stole code from stack overflow.
-}
countBits : Int -> Int
countBits bitmap =
    let
        b1 =
            bitmap - ((bitmap `Bitwise.shiftRightLogical` 1) `Bitwise.and` 0x55555555)

        b2 =
            (b1 `Bitwise.and` 0x33333333) + ((b1 `Bitwise.shiftRightLogical` 2) `Bitwise.and` 0x33333333)
    in
        (((b2 + (b2 `Bitwise.shiftRightLogical` 4)) `Bitwise.and` 0x0F0F0F0F) * 0x01010101) `Bitwise.shiftRightLogical` 24


get : Int -> comparable -> Tree comparable v -> Maybe v
get hash key ls =
    get' 0 hash key ls


get' : Int -> Int -> comparable -> Tree comparable v -> Maybe v
get' shift hash key ls =
    let
        pos =
            hashPositionWithShift shift hash

        node =
            valueByIndex pos ls
    in
        case node of
            Empty ->
                Nothing

            Element _ eKey value ->
                if key == eKey then
                    Just value
                else
                    Nothing

            SubTree nodes ->
                get' (shift + 5) hash key nodes

            Collision _ vals ->
                case find (\( k, _ ) -> k == key) vals of
                    Just ( _, value ) ->
                        Just value

                    Nothing ->
                        Nothing


set : Int -> comparable -> v -> Tree comparable v -> Tree comparable v
set hash key val ls =
    set' 0 hash key val ls


set' : Int -> Int -> comparable -> v -> Tree comparable v -> Tree comparable v
set' shift hash key val ls =
    let
        pos =
            hashPositionWithShift shift hash

        currValue =
            valueByIndex pos ls

        newShift =
            shift + 5
    in
        case currValue of
            Empty ->
                setByIndex pos (Element hash key val) ls

            Element xHash xKey xVal ->
                if xHash == hash then
                    if xKey == key then
                        setByIndex pos (Element hash key val) ls
                    else
                        let
                            element =
                                [ ( key, val ), ( xKey, xVal ) ]
                                    |> List.sortBy fst
                                    |> Collision hash
                        in
                            setByIndex pos element ls
                else
                    let
                        subNodes =
                            empty
                                |> set' newShift xHash xKey xVal
                                |> set' newShift hash key val
                                |> SubTree
                    in
                        setByIndex pos subNodes ls

            Collision xHash nodes ->
                if xHash == hash then
                    let
                        newNodes =
                            nodes
                                |> List.filter (\( k, _ ) -> k /= key)<commit_msg>dont use listSortby for a list of 2 elements<commit_after>module CollectionsNg.Hamt
    exposing
        ( Tree
        , empty
        , hashPositionWithShift
        , countBits
        , get
        , set
        , remove
        , foldl
        , size
        )

import Array
import Bitwise
import List.Extra exposing (find)

type alias Blobs comparable v =
    Array.Array (Node comparable v)

type alias Tree comparable v =
    { positionMap : Int
    , blobs : Blobs comparable v
    }


type Node comparable v
    = Empty
    | Element Int comparable v
    | SubTree (Tree comparable v)
    | Collision Int (List ( comparable, v ))


empty : Tree comparable v
empty =
    { positionMap = 0
    , blobs = Array.repeat 32 Empty
    }


valueByIndex : Int -> Tree comparable v -> Node comparable v
valueByIndex idx ls =
    case Array.get idx ls.blobs of
        Just node ->
            node
        Nothing ->
            Debug.crash "Index out of bounds"


setByIndex : Int -> Node comparable v -> Tree comparable v -> Tree comparable v
setByIndex idx val ls =
    let
        mask =
            0x01 `Bitwise.shiftLeft` idx

        alteredBitmap =
            case val of
                Empty ->
                    ls.positionMap `Bitwise.xor` mask

                _ ->
                    ls.positionMap `Bitwise.or` mask
    in
        { ls | positionMap = alteredBitmap, blobs = Array.set idx val ls.blobs}


hashPositionWithShift : Int -> Int -> Int
hashPositionWithShift shift hash =
    Bitwise.and 0x1F <| Bitwise.shiftRightLogical hash shift


{-| No idea how this works. Stole code from stack overflow.
-}
countBits : Int -> Int
countBits bitmap =
    let
        b1 =
            bitmap - ((bitmap `Bitwise.shiftRightLogical` 1) `Bitwise.and` 0x55555555)

        b2 =
            (b1 `Bitwise.and` 0x33333333) + ((b1 `Bitwise.shiftRightLogical` 2) `Bitwise.and` 0x33333333)
    in
        (((b2 + (b2 `Bitwise.shiftRightLogical` 4)) `Bitwise.and` 0x0F0F0F0F) * 0x01010101) `Bitwise.shiftRightLogical` 24


get : Int -> comparable -> Tree comparable v -> Maybe v
get hash key ls =
    get' 0 hash key ls


get' : Int -> Int -> comparable -> Tree comparable v -> Maybe v
get' shift hash key ls =
    let
        pos =
            hashPositionWithShift shift hash

        node =
            valueByIndex pos ls
    in
        case node of
            Empty ->
                Nothing

            Element _ eKey value ->
                if key == eKey then
                    Just value
                else
                    Nothing

            SubTree nodes ->
                get' (shift + 5) hash key nodes

            Collision _ vals ->
                case find (\( k, _ ) -> k == key) vals of
                    Just ( _, value ) ->
                        Just value

                    Nothing ->
                        Nothing


set : Int -> comparable -> v -> Tree comparable v -> Tree comparable v
set hash key val ls =
    set' 0 hash key val ls


set' : Int -> Int -> comparable -> v -> Tree comparable v -> Tree comparable v
set' shift hash key val ls =
    let
        pos =
            hashPositionWithShift shift hash

        currValue =
            valueByIndex pos ls

        newShift =
            shift + 5
    in
        case currValue of
            Empty ->
                setByIndex pos (Element hash key val) ls

            Element xHash xKey xVal ->
                if xHash == hash then
                    if xKey == key then
                        setByIndex pos (Element hash key val) ls
                    else
                        let
                            element =
                                if key < xKey then
                                    Collision hash [ ( key, val ), ( xKey, xVal ) ]
                                else
                                    Collision hash [ ( xKey, xVal ), ( key, val ) ]
                        in
                            setByIndex pos element ls
                else
                    let
                        subNodes =
                            empty
                                |> set' newShift xHash xKey xVal
                                |> set' newShift hash key val
                                |> SubTree
                    in
                        setByIndex pos subNodes ls

            Collision xHash nodes ->
                if xHash == hash then
                    let
                        newNodes =
                            nodes
                                |> List.filter (\( k, _ ) -> k /= key)
{'fraction_non_alphanumeric': 0.06685821637750028, 'fraction_numerical': 0.014255718863962869, 'mean_word_length': 1.1374586679263108, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 91, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 6, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3485743', 'n_tokens_mistral': 2489, 'n_tokens_neox': 2227, 'n_words': 814}