Skip to content

Instantly share code, notes, and snippets.

@oblitum
Last active February 19, 2016 18:33
Show Gist options
  • Save oblitum/e7e65e4a214aa8345073 to your computer and use it in GitHub Desktop.
Save oblitum/e7e65e4a214aa8345073 to your computer and use it in GitHub Desktop.
// Better POST-MORTEM than never! 💀
package main
import (
"errors"
"fmt"
)
type RelationshipSet struct {
integers map[string]int
strings []string
dependencies [][]int
exclusions [][]int
}
func NewRelationshipSet() *RelationshipSet {
return &RelationshipSet{
map[string]int{},
[]string{},
[][]int{},
[][]int{},
}
}
func DependsOn(a string, b string, s *RelationshipSet) *RelationshipSet {
aNum := s.addElement(a)
bNum := s.addElement(b)
s.dependencies[aNum] = setAppend(s.dependencies[aNum], bNum)
return s
}
func AreExclusive(a string, b string, s *RelationshipSet) *RelationshipSet {
aNum := s.addElement(a)
bNum := s.addElement(b)
s.exclusions[aNum] = setAppend(s.exclusions[aNum], bNum)
s.exclusions[bNum] = setAppend(s.exclusions[bNum], aNum)
return s
}
func CheckRelationships(s *RelationshipSet) bool {
n := len(s.strings)
for i := 0; i < n; i++ {
turnedON := make([]bool, n)
turnedOFF := make([]bool, n)
turnON(turnedON, i, s)
for k, v := range turnedON {
if v {
turnOFFconjugates(turnedOFF, k, s)
}
}
if hasIntersection(turnedON, turnedOFF) {
return false
}
}
return true
}
func NewSet() []string {
return []string{}
}
func Toggle(already_selected []string, o string, s *RelationshipSet) []string {
if _, ok := s.integers[o]; !ok {
return already_selected
}
selected, err := toIntegersWithMap(s.integers, already_selected)
if err != nil {
return already_selected
}
oNum := s.integers[o]
turnedON := make([]bool, len(s.strings))
turnedOFF := make([]bool, len(s.strings))
turningON := !isElement(selected, oNum)
if turningON {
turnON(turnedON, oNum, s)
for k, v := range turnedON {
if v {
turnOFFconjugates(turnedOFF, k, s)
}
}
} else {
turnOFF(turnedOFF, oNum, s)
}
if hasIntersection(turnedON, turnedOFF) {
return already_selected
}
selectedAsBooleanMap := make([]bool, len(s.strings))
if integersToBooleans(selected, selectedAsBooleanMap) != nil {
return already_selected
}
useTurnOFF(turnedOFF, selectedAsBooleanMap)
useTurnON(turnedON, selectedAsBooleanMap)
result, err := toStringsWithMap(s.strings, booleansToIntegers(selectedAsBooleanMap))
if err != nil {
return already_selected
}
return result
}
func hasIntersection(a []bool, b []bool) bool {
var n int
if len(a) < len(b) {
n = len(a)
} else {
n = len(b)
}
for i := 0; i < n; i++ {
if a[i] && b[i] {
return true
}
}
return false
}
func turnON(elements []bool, element int, s *RelationshipSet) {
if elements[element] {
return
}
elements[element] = true
for _, v := range s.dependencies[element] {
turnON(elements, v, s)
}
}
func turnOFFconjugates(elements []bool, element int, s *RelationshipSet) {
for _, v := range s.exclusions[element] {
turnOFF(elements, v, s)
}
}
func turnOFF(elements []bool, element int, s *RelationshipSet) {
if elements[element] {
return
}
elements[element] = true
for k, v := range s.dependencies {
if isElement(v, element) {
turnOFF(elements, k, s)
}
}
}
func isElement(set []int, element int) bool {
for _, v := range set {
if v == element {
return true
}
}
return false
}
func useTurnON(on []bool, elements []bool) {
var n int
if len(on) < len(elements) {
n = len(on)
} else {
n = len(elements)
}
for i := 0; i < n; i++ {
if on[i] {
elements[i] = true
}
}
}
func useTurnOFF(off []bool, elements []bool) {
var n int
if len(off) < len(elements) {
n = len(off)
} else {
n = len(elements)
}
for i := 0; i < n; i++ {
if off[i] {
elements[i] = false
}
}
}
func (rs *RelationshipSet) addElement(element string) int {
if _, ok := rs.integers[element]; ok {
return rs.integers[element]
}
rs.integers[element] = len(rs.integers)
rs.strings = append(rs.strings, element)
rs.dependencies = append(rs.dependencies, []int{})
rs.exclusions = append(rs.exclusions, []int{})
return rs.integers[element]
}
func setAppend(set []int, elements ...int) []int {
for _, e := range elements {
for _, v := range set {
if v == e {
break
}
}
set = append(set, e)
}
return set
}
func toIntegersWithMap(mapping map[string]int, elements []string) ([]int, error) {
response := make([]int, 0, len(elements))
for _, v := range elements {
if _, ok := mapping[v]; !ok {
return nil, errors.New(fmt.Sprintf("There's no key %v in map.", v))
}
response = append(response, mapping[v])
}
return response, nil
}
func toStringsWithMap(mapping []string, elements []int) ([]string, error) {
response := make([]string, 0, len(elements))
for _, v := range elements {
if v < 0 || v >= len(mapping) {
return nil, errors.New(fmt.Sprintf("There's no key %v in map.", v))
}
response = append(response, mapping[v])
}
return response, nil
}
func booleansToIntegers(booleanMap []bool) []int {
response := make([]int, 0, len(booleanMap))
for k, on := range booleanMap {
if on {
response = append(response, k)
}
}
return response
}
func integersToBooleans(integers []int, booleanMap []bool) error {
for _, v := range integers {
if v < 0 || v >= len(booleanMap) {
return errors.New(fmt.Sprintf("Index %v is larger than booleanMap", v))
}
booleanMap[v] = true
}
return nil
}
func main() {}
// Fail
package main
import (
"container/list"
)
type elements []string
type RelationshipSet struct {
equals []elements
opposites []elements
}
func (e elements) Contains(element string) (int, bool) {
for k, v := range e {
if v == element {
return k, true
}
}
return -1, false
}
func NewRelationshipSet() *RelationshipSet {
return &RelationshipSet{[]elements{}, []elements{}}
}
func relate(a string, b string, related []elements) []elements {
first := -1
second := -1
var conjugate string
for k, v := range related {
if _, contains := v.Contains(a); contains {
if _, contains := v.Contains(b); contains {
return related
} else if first == -1 {
first = k
conjugate = b
} else if second == -1 {
second = k
break
}
}
if _, contains := v.Contains(b); contains {
if _, contains := v.Contains(a); contains {
return related
} else if first == -1 {
first = k
conjugate = a
} else if second == -1 {
second = k
break
}
}
}
if first == -1 && second == -1 {
if a == b {
return append(related, elements{a})
}
return append(related, elements{a, b})
}
if first != -1 && second == -1 {
related[first] = append(related[first], conjugate)
return related
}
related[first] = append(related[first], related[second]...)
return append(related[:second], related[second+1:]...)
}
func DependsOn(a string, b string, s *RelationshipSet) *RelationshipSet {
s.equals = relate(a, b, s.equals)
return s
}
func AreExclusive(a string, b string, s *RelationshipSet) *RelationshipSet {
s.opposites = relate(a, b, s.opposites)
return s
}
func CheckRelationships(s *RelationshipSet) bool {
for _, equals := range s.equals {
for _, opposites := range s.opposites {
counter := 0
for _, opposite := range opposites {
if _, contains := equals.Contains(opposite); contains {
if counter == 1 {
return false
}
counter++
}
}
}
}
return true
}
// Stub not implemented yet
func NewSet() []string {
return []string{}
}
func Toggle(already_selected []string, o string, s *RelationshipSet) []string {
l := list.New()
for _, v := range already_selected {
l.PushBack(v)
}
if _, contains := elements(already_selected).Contains(o); contains {
for _, equals := range s.equals {
if _, contains := equals.Contains(o); contains {
for _, equal := range equals {
var next *list.Element
for e := l.Front(); e != nil; e = next {
next = e.Next()
if e.Value.(string) == equal {
l.Remove(e)
}
}
}
new_selection := make([]string, 0, l.Len())
for e := l.Front(); e != nil; e = e.Next() {
new_selection = append(new_selection, e.Value.(string))
}
return new_selection
// return append(already_selected[:k], already_selected[k+len(equals):]...)
}
}
return already_selected
}
for _, opposites := range s.opposites {
if _, contains := opposites.Contains(o); contains {
for _, opposite := range opposites {
var next *list.Element
for e := l.Front(); e != nil; e = next {
next = e.Next()
if e.Value.(string) == opposite {
l.Remove(e)
}
}
}
}
}
new_selection := make([]string, 0, l.Len())
for e := l.Front(); e != nil; e = e.Next() {
new_selection = append(new_selection, e.Value.(string))
}
for _, equals := range s.equals {
if _, contains := equals.Contains(o); contains {
new_selection = append(new_selection, equals...)
}
}
return new_selection
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment