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/list.go

90 lines
1.8 KiB

package sorted
import "fmt"
type Num float64
type List struct {
elems []*listElem
}
type listElem struct {
value Num
elem interface{}
}
func (sl *List) Insert(elem interface{}, value Num) {
newElem := listElem{
value,
elem,
}
if len(sl.elems) == 0 {
sl.elems = append(sl.elems, &newElem)
} else {
//find i such that sl.elems[i].value < newElen.value
var i int
for i = 0; i < len(sl.elems) && sl.elems[i].value < newElem.value; i++ {
}
//actual instertion at index = i
previousElems := sl.elems[:i]
forwardElems := make([]*listElem, len(sl.elems[i:]))
copy(forwardElems, sl.elems[i:])
sl.elems = append(previousElems, &newElem)
sl.elems = append(sl.elems, forwardElems...)
}
}
func (sl *List) Nearest(value Num) (interface{}, error) {
if len(sl.elems) == 0 {
return listElem{}, &ErrListEmpty{}
}
if sl.elems[0].value > value {
return sl.elems[0].elem, nil
} else if len(sl.elems) == 1 {
return sl.elems[0].elem, nil
} else {
//Find i such that sl.elems[i].value > value
var i int
for i = 1; i < len(sl.elems) && sl.elems[i].value < value; i++ {
}
//If there is no bigger elemet return last element
if i == len(sl.elems) {
return sl.elems[i-1].elem, nil
}
biggerElem := sl.elems[i]
smallerElem := sl.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 (sl *List) String() string {
str := "["
for i, v := range sl.elems {
if i != 0 {
str += " "
}
str += fmt.Sprintf("%v", v.elem)
}
str += "]"
return str
}
func (sl *List) Elems() []*listElem {
return sl.elems
}