twitchapon-anim

Basic Twitchapon Receiver/Visuals
git clone git://bsandro.tech/twitchapon-anim
Log | Files | Refs | README | LICENSE

packing.go (6665B)


      1 // Copyright 2018 The Ebiten Authors
      2 //
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //     http://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 // See the License for the specific language governing permissions and
     13 // limitations under the License.
     14 
     15 // Package packing offers a packing algorithm in 2D space.
     16 package packing
     17 
     18 import (
     19 	"errors"
     20 )
     21 
     22 const (
     23 	minSize = 1
     24 )
     25 
     26 type Page struct {
     27 	root    *Node
     28 	size    int
     29 	maxSize int
     30 
     31 	rollbackExtension func()
     32 }
     33 
     34 func NewPage(initSize int, maxSize int) *Page {
     35 	return &Page{
     36 		size:    initSize,
     37 		maxSize: maxSize,
     38 	}
     39 }
     40 
     41 func (p *Page) IsEmpty() bool {
     42 	if p.root == nil {
     43 		return true
     44 	}
     45 	return !p.root.used && p.root.child0 == nil && p.root.child1 == nil
     46 }
     47 
     48 type Node struct {
     49 	x      int
     50 	y      int
     51 	width  int
     52 	height int
     53 	used   bool
     54 
     55 	parent *Node
     56 	child0 *Node
     57 	child1 *Node
     58 }
     59 
     60 func (n *Node) canFree() bool {
     61 	if n.used {
     62 		return false
     63 	}
     64 	if n.child0 == nil && n.child1 == nil {
     65 		return true
     66 	}
     67 	return n.child0.canFree() && n.child1.canFree()
     68 }
     69 
     70 func (n *Node) Region() (x, y, width, height int) {
     71 	return n.x, n.y, n.width, n.height
     72 }
     73 
     74 // square returns a float value indicating how much the given rectangle is close to a square.
     75 // If the given rectangle is square, this return 1 (maximum value).
     76 // Otherwise, this returns a value in [0, 1).
     77 func square(width, height int) float64 {
     78 	if width == 0 && height == 0 {
     79 		return 0
     80 	}
     81 	if width <= height {
     82 		return float64(width) / float64(height)
     83 	}
     84 	return float64(height) / float64(width)
     85 }
     86 
     87 func (p *Page) alloc(n *Node, width, height int) *Node {
     88 	if n.width < width || n.height < height {
     89 		return nil
     90 	}
     91 	if n.used {
     92 		return nil
     93 	}
     94 	if n.child0 == nil && n.child1 == nil {
     95 		if n.width == width && n.height == height {
     96 			n.used = true
     97 			return n
     98 		}
     99 		if square(n.width-width, n.height) >= square(n.width, n.height-height) {
    100 			// Split vertically
    101 			n.child0 = &Node{
    102 				x:      n.x,
    103 				y:      n.y,
    104 				width:  width,
    105 				height: n.height,
    106 				parent: n,
    107 			}
    108 			n.child1 = &Node{
    109 				x:      n.x + width,
    110 				y:      n.y,
    111 				width:  n.width - width,
    112 				height: n.height,
    113 				parent: n,
    114 			}
    115 		} else {
    116 			// Split holizontally
    117 			n.child0 = &Node{
    118 				x:      n.x,
    119 				y:      n.y,
    120 				width:  n.width,
    121 				height: height,
    122 				parent: n,
    123 			}
    124 			n.child1 = &Node{
    125 				x:      n.x,
    126 				y:      n.y + height,
    127 				width:  n.width,
    128 				height: n.height - height,
    129 				parent: n,
    130 			}
    131 		}
    132 		return p.alloc(n.child0, width, height)
    133 	}
    134 	if n.child0 == nil || n.child1 == nil {
    135 		panic("packing: both two children must not be nil at alloc")
    136 	}
    137 	if node := p.alloc(n.child0, width, height); node != nil {
    138 		return node
    139 	}
    140 	if node := p.alloc(n.child1, width, height); node != nil {
    141 		return node
    142 	}
    143 	return nil
    144 }
    145 
    146 func (p *Page) Size() int {
    147 	return p.size
    148 }
    149 
    150 func (p *Page) SetMaxSize(size int) {
    151 	if p.maxSize > size {
    152 		panic("packing: maxSize cannot be decreased")
    153 	}
    154 	p.maxSize = size
    155 }
    156 
    157 func (p *Page) Alloc(width, height int) *Node {
    158 	if width <= 0 || height <= 0 {
    159 		panic("packing: width and height must > 0")
    160 	}
    161 	if p.root == nil {
    162 		p.root = &Node{
    163 			width:  p.size,
    164 			height: p.size,
    165 		}
    166 	}
    167 	if width < minSize {
    168 		width = minSize
    169 	}
    170 	if height < minSize {
    171 		height = minSize
    172 	}
    173 	n := p.alloc(p.root, width, height)
    174 	return n
    175 }
    176 
    177 func (p *Page) Free(node *Node) {
    178 	if node.child0 != nil || node.child1 != nil {
    179 		panic("packing: can't free the node including children")
    180 	}
    181 	node.used = false
    182 	if node.parent == nil {
    183 		return
    184 	}
    185 	if node.parent.child0 == nil || node.parent.child1 == nil {
    186 		panic("packing: both two children must not be nil at Free: double free happened?")
    187 	}
    188 	if node.parent.child0.canFree() && node.parent.child1.canFree() {
    189 		node.parent.child0 = nil
    190 		node.parent.child1 = nil
    191 		p.Free(node.parent)
    192 	}
    193 }
    194 
    195 func walk(n *Node, f func(n *Node) error) error {
    196 	if err := f(n); err != nil {
    197 		return err
    198 	}
    199 	if n.child0 != nil {
    200 		if err := walk(n.child0, f); err != nil {
    201 			return err
    202 		}
    203 	}
    204 	if n.child1 != nil {
    205 		if err := walk(n.child1, f); err != nil {
    206 			return err
    207 		}
    208 	}
    209 	return nil
    210 }
    211 
    212 func (p *Page) Extend(count int) bool {
    213 	if p.rollbackExtension != nil {
    214 		panic("packing: Extend cannot be called without rolling back or committing")
    215 	}
    216 
    217 	if p.size >= p.maxSize {
    218 		return false
    219 	}
    220 	newSize := p.size
    221 	for i := 0; i < count; i++ {
    222 		newSize *= 2
    223 	}
    224 	edgeNodes := []*Node{}
    225 	abort := errors.New("abort")
    226 	aborted := false
    227 	_ = walk(p.root, func(n *Node) error {
    228 		if n.x+n.width < p.size && n.y+n.height < p.size {
    229 			return nil
    230 		}
    231 		if n.used {
    232 			aborted = true
    233 			return abort
    234 		}
    235 		edgeNodes = append(edgeNodes, n)
    236 		return nil
    237 	})
    238 	if aborted {
    239 		origRoot := *p.root
    240 
    241 		leftUpper := p.root
    242 		leftLower := &Node{
    243 			x:      0,
    244 			y:      p.size,
    245 			width:  p.size,
    246 			height: newSize - p.size,
    247 		}
    248 		left := &Node{
    249 			x:      0,
    250 			y:      0,
    251 			width:  p.size,
    252 			height: p.size,
    253 			child0: leftUpper,
    254 			child1: leftLower,
    255 		}
    256 		leftUpper.parent = left
    257 		leftLower.parent = left
    258 
    259 		right := &Node{
    260 			x:      p.size,
    261 			y:      0,
    262 			width:  newSize - p.size,
    263 			height: newSize,
    264 		}
    265 		p.root = &Node{
    266 			x:      0,
    267 			y:      0,
    268 			width:  newSize,
    269 			height: newSize,
    270 			child0: left,
    271 			child1: right,
    272 		}
    273 		left.parent = p.root
    274 		right.parent = p.root
    275 
    276 		origSize := p.size
    277 		p.rollbackExtension = func() {
    278 			p.size = origSize
    279 			p.root = &origRoot
    280 		}
    281 	} else {
    282 		origSize := p.size
    283 		origWidths := map[*Node]int{}
    284 		origHeights := map[*Node]int{}
    285 
    286 		for _, n := range edgeNodes {
    287 			if n.x+n.width == p.size {
    288 				origWidths[n] = n.width
    289 				n.width += newSize - p.size
    290 			}
    291 			if n.y+n.height == p.size {
    292 				origHeights[n] = n.height
    293 				n.height += newSize - p.size
    294 			}
    295 		}
    296 
    297 		p.rollbackExtension = func() {
    298 			p.size = origSize
    299 			for n, w := range origWidths {
    300 				n.width = w
    301 			}
    302 			for n, h := range origHeights {
    303 				n.height = h
    304 			}
    305 		}
    306 	}
    307 
    308 	p.size = newSize
    309 	return true
    310 }
    311 
    312 // RollbackExtension rollbacks Extend call once.
    313 func (p *Page) RollbackExtension() {
    314 	if p.rollbackExtension == nil {
    315 		panic("packing: RollbackExtension cannot be called without Extend")
    316 	}
    317 	p.rollbackExtension()
    318 	p.rollbackExtension = nil
    319 }
    320 
    321 // CommitExtension commits Extend call.
    322 func (p *Page) CommitExtension() {
    323 	if p.rollbackExtension == nil {
    324 		panic("packing: RollbackExtension cannot be called without Extend")
    325 	}
    326 	p.rollbackExtension = nil
    327 }