You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
sorted/set.go

156 lines
3.1 KiB

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
}