Почему моя функция слияния карт объединяет все?

Question

У меня есть довольно простая программа Go, которая определяет, есть ли совпадения в чьем-либо расписании событий. По сути, это то, что он делает:

У нас есть 3 события, скажем, для продуктового магазина:

            day   0  1  2  3  4  5     
apple sale        [-----------]
banana sale             [--------]
pickle sale                [-------------]

Вот мой код:

package main

import (
    "fmt"
)

type event struct {
    start int
    end int
    groups map[string]bool
}

func main(){
    //Create Events
    campaigns := []event{
        event{
            start: 0,
            end: 4,
            groups: map[string]bool{
                "apple sale": true,
            },
        },
        event{
            start: 2,
            end: 5,
            groups: map[string]bool{            
                "banna sale": true,         
            },
        },
        event{
            start: 3,
            end: 10,
            groups: map[string]bool{
                "pickle sale": true,
            },
        },
    }

    fmt.Printf("\n-------------\n| Events    |\n-------------\n\n")

    for _, c := range campaigns {
        fmt.Printf("Name: ")
        for name, _ := range c.groups {
            fmt.Printf("%v, ", name)
        }
        fmt.Printf("\nStart:%v\nEnd:%v\n\n", c.start, c.end)
    }

    overlaps := recursiveOverlaps(campaigns, make([]event, 0))

    fmt.Printf("\n-------------\n| Overlaps  |\n-------------\n\n")

    for _, c := range overlaps {
        fmt.Printf("Events: ")
        for name, _ := range c.groups {
            fmt.Printf("%v, ", name)
        }
        fmt.Printf("\nStart:%v\nEnd:%v\n\n", c.start, c.end)
    }
}

func recursiveOverlaps(events []event, overlaps []event) []event {

    //pop comparisonEvent (first item in array)
    comparisonEvent, events := events[len(events)-1], events[:len(events)-1]


    if len(events) == 0 {//check base case
        return overlaps;
    }

    //Find overlaps
    for _, eventItem := range events {

        overlaping, overlapCase := overlapExists(comparisonEvent, eventItem)

        if overlaping {

            groups := mergeKeys(comparisonEvent.groups, eventItem.groups)

            switch overlapCase {

                case 1:
                    overlaps = append( overlaps, event{eventItem.start, eventItem.end, groups} )

                case 2:
                    overlaps = append( overlaps, event{comparisonEvent.start, comparisonEvent.end, groups} )

                case 3:
                    overlaps = append( overlaps, event{eventItem.start, comparisonEvent.end, groups} )

                case 4:
                    overlaps = append( overlaps, event{comparisonEvent.start, eventItem.end, groups} )
            }

            //reset groups so we don't get any funny business
            groups = map[string]bool{}

        }
    }

    return recursiveOverlaps(events, overlaps)
}

func overlapExists(a event, b event) (bool, int) {

    if between(a.start, a.end, b.start) && between(a.start, a.end, b.end) {
    // [----------]
    //    [-----]
        return true, 1
    }

    if between(b.start, b.end, a.start) && between(b.start, b.end, a.end) {
    //    [-----]
    // [----------]
        return true, 2
    }

    if between(a.start, a.end, b.start) {
    // [----------]
    //    [--------------
        return true, 3
    }

    if between(a.start, a.end, b.end) {
    //            [----------]
    //    --------------]
        return true, 4
    }

    return false, 0
}

func between(a, b, c int) bool {
    //is c between a and b?
    if c > a && c < b {
        return true
    }
    return false
}

// Given two maps merge right into left
func mergeKeys(left, right map[string]bool) map[string]bool {
    for key, rightVal := range right {
        left[key] = rightVal
    }
    return left
}

Код почти работает .... но проблема в том, что, по логике вещей, я запрограммировал это только для сравнения двух событий. Не три одновременно. Однако результат таков:

-------------
| Events    |
-------------

Name: apple sale,
Start:0
End:4

Name: banna sale,
Start:2
End:5

Name: car sale,
Start:3
End:10


-------------
| Overlaps  |
-------------

Events: banna sale, car sale, apple sale,
Start:3
End:4

Events: car sale, apple sale, banna sale,
Start:3
End:5

Events: banna sale, apple sale,
Start:2
End:4

Каким-то образом я думаю, что функция mergeKeys() делает что-то странное. Есть идеи?

Answer 1

Хорошо. Поэтому я выяснил, что происходит не так:

карты в go передаются по ссылке .... вроде. Не совсем.

, хотя карты не имеют указателя перед ними ... они передаются по ссылке ... вроде. На самом деле это не так, но вы можете прочитать больше об этом в этой статье , "нет передачи по ссылке в go" и этой статье , "если карта не существует" t эталонная переменная что это такое ". Я дам вам этот отрывок, чтобы прояснить, что происходит:

Значение карты - это указатель на структуру runtime.hmap.

Даже если карты не передается не по ссылке, а по значению ... Исходная переменная карты, которую вы передали в функцию, модифицируется. Это означает, что когда я изменял левую карту в своей функции mergeKeys, я фактически также менял карту сравнениеEvent.groups.

Чтобы учесть это, я создал карту tra sh, которую я мог изменять и не иметь Последствия:

if overlaping {

    trashMap := make(map[string]bool)
    for key, value := range comparisonEvent.groups {
        trashMap[key] = value
    }

    groups := mergeKeys(trashMap, eventItem.groups)

    switch overlapCase {

        case 1:
            overlaps = append( overlaps, event{eventItem.start, eventItem.end, groups} )

        case 2:
            overlaps = append( overlaps, event{comparisonEvent.start, comparisonEvent.end, groups} )

        case 3:
            overlaps = append( overlaps, event{eventItem.start, comparisonEvent.end, groups} )

        case 4:
            overlaps = append( overlaps, event{comparisonEvent.start, eventItem.end, groups} )
    }
}

Я все еще открыт для обсуждения и более эффективных решений, прежде чем принять этот ответ. Я надеюсь, что это поможет кому-то там!