sorted/set.go

package sorted

import (
	"fmt"

	"gitlab.com/Pixdigit/uniqueID"
)

// Set is optimized for Set.Elems() to be fast.
// This is why it doesnt implement the functionality with a map
// This of course makes almost all other operations slow

type Set struct {
	elems []*setElem
}

type uniqueElem interface {
	ID() uniqueID.ID
}

type setElem struct {
	value Num
	elem  uniqueElem
}

func (se *setElem) ID() uniqueID.ID {
	return se.elem.ID()
}

func (s *Set) Insert(uElem uniqueElem, value Num) error {
	for _, elem := range s.elems {
		if elem.ID() == uElem.ID() {
			return &ErrDuplicateElem{elem.ID()}
		}
	}

	newElem := setElem{
		value,
		uElem,
	}

	if len(s.elems) == 0 {
		s.elems = append(s.elems, &newElem)
	} else {

		//find i such that s.elems[i].value < newElen.value
		var i int
		for i = 0; i < len(s.elems) && s.elems[i].value < newElem.value; i++ {
		}

		//actual instertion at index = i
		previousElems := s.elems[:i]
		forwardElems := make([]*setElem, len(s.elems[i:]))
		copy(forwardElems, s.elems[i:])

		s.elems = append(previousElems, &newElem)
		s.elems = append(s.elems, forwardElems...)
	}
	return nil
}

func (s *Set) SetValue(elem uniqueElem, value Num) error {
    elemID := elem.ID()
	for i, elem := range s.elems {
		if elem.ID() == elemID {
			elem.value = value
			//remove elem from array
			s.elems = append(s.elems[:i], s.elems[i+1:]...)
			//insert it again at new position
			s.Insert(elem.elem, elem.value)
			return nil
		}
	}
	return ErrNoElem{elemID}
}

func (s *Set) Nearest(value Num) (interface{}, error) {

	if len(s.elems) == 0 {
		return setElem{}, &ErrListEmpty{}
	}

	if s.elems[0].value > value {
		return s.elems[0].elem, nil
	} else if len(s.elems) == 1 {
		return s.elems[0].elem, nil
	} else {
		//Find i such that s.elems[i].value > value
		var i int
		for i = 1; i < len(s.elems) && s.elems[i].value < value; i++ {
		}
		//If there is no bigger elemet return last element
		if i == len(s.elems) {
			return s.elems[i-1].elem, nil

		}
		biggerElem := s.elems[i]
		smallerElem := s.elems[i-1]

		//Return the element closer to value
		switch {
		case (value - smallerElem.value) <= (biggerElem.value - value):
			return smallerElem.elem, nil
		case (value - smallerElem.value) > (biggerElem.value - value):
			return biggerElem.elem, nil
		}
	}
	panic("reached unreachable statement")
}

func (s *Set) String() string {
	str := "["
	for i, v := range s.elems {
		if i != 0 {
			str += " "
		}
		str += fmt.Sprintf("%v", v.elem)
	}
	str += "]"
	return str
}

func (s *Set) Elems() []interface{} {
	copy := make([]interface{}, len(s.elems))
	for i, elem := range s.elems {
		copy[i] = interface{}(elem.elem)
	}
	return copy
}

func (s *Set) Len() int {
	return len(s.elems)
}

func (s *Set) Contains(testElem uniqueElem) bool {
	elemID := testElem.ID()
	for _, elem := range s.elems {
		if elem.ID() == elemID {
			return true
		}
	}
	return false
}

func (s *Set) Remove(elemToRemove uniqueElem) (success bool) {
	elemID := elemToRemove.ID()
	for i, elem := range s.elems {
		if elem.ID() == elemID {
			s.elems = append(s.elems[:i], s.elems[i+1:]...)
			//element can only occur once so exit if one has been found
			return true
		}
	}
	return false
}