Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
150 lines (122 sloc) 3.2 KB
/*
Copyright © 2016 the InMAP authors.
This file is part of InMAP.
InMAP is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
InMAP is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with InMAP. If not, see <http://www.gnu.org/licenses/>.
*/
package inmap
import (
"fmt"
"sort"
)
// cellRefs holds a cell, a reference to the next and previous
// adjacent cells in a cellList, and potentially information about the
// cell's relationship to a neighbor.
type cellRef struct {
*Cell
info *neighborInfo
}
// cellList is a list of cells.
type cellList []*cellRef
func (l *cellList) len() int {
return len(*l)
}
// array returns a sorted array of the cells in this list.
func (l *cellList) array() []*Cell {
o := make([]*Cell, len(*l))
for i, c := range *l {
o[i] = c.Cell
}
return o
}
// delete deletes this cellRef from the list.
func (l *cellList) delete(c *cellRef) {
l.deleteCell(c.Cell)
}
// deleteCell deletes this Cell from the list
func (l *cellList) deleteCell(c *Cell) {
// Find the index where the cell should be.
i := sort.Search(len(*l), func(i int) bool {
return c.before((*l)[i].Cell)
})
cref := (*l)[i]
if cref.Cell != c {
panic("tried to delete cell that is not in list")
}
copy((*l)[i:], (*l)[i+1:])
(*l)[len(*l)-1] = nil
(*l) = (*l)[:len(*l)-1]
}
// addToList adds the cell to the beginning of the list.
func (l *cellList) add(c *Cell) *cellRef {
cc := &cellRef{Cell: c}
// Find the correct location to insert the cell
i := sort.Search(len(*l), func(i int) bool {
return c.before((*l)[i].Cell)
})
// Insert the cell.
(*l) = append((*l), nil)
copy((*l)[i+1:], (*l)[i:])
(*l)[i] = cc
return cc
}
// index returns the index of c and whether it was found
func (l *cellList) index(c *Cell) (int, bool) {
// Find the index where the cell should be.
i := sort.Search(len(*l), func(i int) bool {
return c.before((*l)[i].Cell)
})
cref := (*l)[i]
if cref.Cell != c {
return -1, false
}
return i, true
}
func (l *cellList) ref(c *Cell) *cellRef {
// Find the index where the cell should be.
i := sort.Search(len(*l), func(i int) bool {
return c.before((*l)[i].Cell)
})
cref := (*l)[i]
if cref.Cell != c {
panic("tried to retrieve cell that is not in list")
}
return cref
}
func (l *cellList) String() string {
s := ""
for i, c := range *l {
if i != 0 {
s += "\n"
}
s += fmt.Sprint(c.Cell)
}
return s
}
// before returns whether c should be sorted before c2.
func (c *Cell) before(c2 *Cell) bool {
if c == c2 {
return true
}
if c.Layer != c2.Layer {
return c.Layer < c2.Layer
}
icent := c.Centroid()
jcent := c2.Centroid()
if icent.X != jcent.X {
return icent.X < jcent.X
}
if icent.Y != jcent.Y {
return icent.Y < jcent.Y
}
// We apparently have concentric cells if we get to here.
panic(fmt.Errorf("problem sorting: i: %v, j: %v", c, c2))
}
You can’t perform that action at this time.