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.
90 lines
1.8 KiB
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
|
|
}
|