miss-align when show some diff file
zzjin opened this issue · 4 comments
zzjin commented
Hello, I'm trying to use this tool to show git diffs but find at my diff file, the side-by-side is not aligned.
diff file:
Click to expand!
--- btree.go 2022-06-18 01:44:55.608132000 +0800
+++ btree_generic.go 2022-06-18 01:44:55.608132000 +0800
@@ -1,4 +1,4 @@
-// Copyright 2014 Google Inc.
+// Copyright 2014-2022 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
@@ -12,8 +12,13 @@
// See the License for the specific language governing permissions and
// limitations under the License.
-//go:build !go1.18
-// +build !go1.18
+//go:build go1.18
+// +build go1.18
+
+// In Go 1.18 and beyond, a BTreeG generic is created, and BTree is a specific
+// instantiation of that generic for the Item interface, with a backwards-
+// compatible API. Before go1.18, generics are not supported,
+// and BTree is just an implementation based around the Item interface.
// Package btree implements in-memory B-Trees of arbitrary degree.
//
@@ -48,6 +53,11 @@
// Its functions, therefore, exactly mirror those of
// llrb.LLRB where possible. Unlike gollrb, though, we currently don't
// support storing multiple equivalent values.
+//
+// There are two implementations; those suffixed with 'G' are generics, usable
+// for any type, and require a passed-in "less" function to define their ordering.
+// Those without this prefix are specific to the 'Item' interface, and use
+// its 'Less' function for ordering.
package btree
import (
@@ -72,32 +82,27 @@
DefaultFreeListSize = 32
)
-var (
- nilItems = make(items, 16)
- nilChildren = make(children, 16)
-)
-
-// FreeList represents a free list of btree nodes. By default each
+// FreeListG represents a free list of btree nodes. By default each
// BTree has its own FreeList, but multiple BTrees can share the same
-// FreeList.
+// FreeList, in particular when they're created with Clone.
// Two Btrees using the same freelist are safe for concurrent write access.
-type FreeList struct {
+type FreeListG[T any] struct {
mu sync.Mutex
- freelist []*node
+ freelist []*node[T]
}
-// NewFreeList creates a new free list.
+// NewFreeListG creates a new free list.
// size is the maximum size of the returned free list.
-func NewFreeList(size int) *FreeList {
- return &FreeList{freelist: make([]*node, 0, size)}
+func NewFreeListG[T any](size int) *FreeListG[T] {
+ return &FreeListG[T]{freelist: make([]*node[T], 0, size)}
}
-func (f *FreeList) newNode() (n *node) {
+func (f *FreeListG[T]) newNode() (n *node[T]) {
f.mu.Lock()
index := len(f.freelist) - 1
if index < 0 {
f.mu.Unlock()
- return new(node)
+ return new(node[T])
}
n = f.freelist[index]
f.freelist[index] = nil
@@ -106,9 +111,7 @@
return
}
-// freeNode adds the given node to the list, returning true if it was added
-// and false if it was discarded.
-func (f *FreeList) freeNode(n *node) (out bool) {
+func (f *FreeListG[T]) freeNode(n *node[T]) (out bool) {
f.mu.Lock()
if len(f.freelist) < cap(f.freelist) {
f.freelist = append(f.freelist, n)
@@ -118,37 +121,55 @@
return
}
-// ItemIterator allows callers of Ascend* to iterate in-order over portions of
+// ItemIteratorG allows callers of {A/De}scend* to iterate in-order over portions of
// the tree. When this function returns false, iteration will stop and the
// associated Ascend* function will immediately return.
-type ItemIterator func(i Item) bool
+type ItemIteratorG[T any] func(item T) bool
-// New creates a new B-Tree with the given degree.
+// Ordered represents the set of types for which the '<' operator work.
+type Ordered interface {
+ ~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~float32 | ~float64 | ~string
+}
+
+// Less[T] returns a default LessFunc that uses the '<' operator for types that support it.
+func Less[T Ordered]() LessFunc[T] {
+ return func(a, b T) bool { return a < b }
+}
+
+// NewOrderedG creates a new B-Tree for ordered types.
+func NewOrderedG[T Ordered](degree int) *BTreeG[T] {
+ return NewG[T](degree, Less[T]())
+}
+
+// NewG creates a new B-Tree with the given degree.
//
-// New(2), for example, will create a 2-3-4 tree (each node contains 1-3 items
+// NewG(2), for example, will create a 2-3-4 tree (each node contains 1-3 items
// and 2-4 children).
-func New(degree int) *BTree {
- return NewWithFreeList(degree, NewFreeList(DefaultFreeListSize))
+//
+// The passed-in LessFunc determines how objects of type T are ordered.
+func NewG[T any](degree int, less LessFunc[T]) *BTreeG[T] {
+ return NewWithFreeListG(degree, less, NewFreeListG[T](DefaultFreeListSize))
}
-// NewWithFreeList creates a new B-Tree that uses the given node free list.
-func NewWithFreeList(degree int, f *FreeList) *BTree {
+// NewWithFreeListG creates a new B-Tree that uses the given node free list.
+func NewWithFreeListG[T any](degree int, less LessFunc[T], f *FreeListG[T]) *BTreeG[T] {
if degree <= 1 {
panic("bad degree")
}
- return &BTree{
+ return &BTreeG[T]{
degree: degree,
- cow: ©OnWriteContext{freelist: f},
+ cow: ©OnWriteContext[T]{freelist: f, less: less},
}
}
// items stores items in a node.
-type items []Item
+type items[T any] []T
// insertAt inserts a value into the given index, pushing all subsequent values
// forward.
-func (s *items) insertAt(index int, item Item) {
- *s = append(*s, nil)
+func (s *items[T]) insertAt(index int, item T) {
+ var zero T
+ *s = append(*s, zero)
if index < len(*s) {
copy((*s)[index+1:], (*s)[index:])
}
@@ -157,100 +178,61 @@
// removeAt removes a value at a given index, pulling all subsequent values
// back.
-func (s *items) removeAt(index int) Item {
+func (s *items[T]) removeAt(index int) T {
item := (*s)[index]
copy((*s)[index:], (*s)[index+1:])
- (*s)[len(*s)-1] = nil
+ var zero T
+ (*s)[len(*s)-1] = zero
*s = (*s)[:len(*s)-1]
return item
}
// pop removes and returns the last element in the list.
-func (s *items) pop() (out Item) {
+func (s *items[T]) pop() (out T) {
index := len(*s) - 1
out = (*s)[index]
- (*s)[index] = nil
+ var zero T
+ (*s)[index] = zero
*s = (*s)[:index]
return
}
// truncate truncates this instance at index so that it contains only the
// first index items. index must be less than or equal to length.
-func (s *items) truncate(index int) {
- var toClear items
+func (s *items[T]) truncate(index int) {
+ var toClear items[T]
*s, toClear = (*s)[:index], (*s)[index:]
- for len(toClear) > 0 {
- toClear = toClear[copy(toClear, nilItems):]
+ var zero T
+ for i := 0; i < len(toClear); i++ {
+ toClear[i] = zero
}
}
// find returns the index where the given item should be inserted into this
// list. 'found' is true if the item already exists in the list at the given
// index.
-func (s items) find(item Item) (index int, found bool) {
+func (s items[T]) find(item T, less func(T, T) bool) (index int, found bool) {
i := sort.Search(len(s), func(i int) bool {
- return item.Less(s[i])
+ return less(item, s[i])
})
- if i > 0 && !s[i-1].Less(item) {
+ if i > 0 && !less(s[i-1], item) {
return i - 1, true
}
return i, false
}
-// children stores child nodes in a node.
-type children []*node
-
-// insertAt inserts a value into the given index, pushing all subsequent values
-// forward.
-func (s *children) insertAt(index int, n *node) {
- *s = append(*s, nil)
- if index < len(*s) {
- copy((*s)[index+1:], (*s)[index:])
- }
- (*s)[index] = n
-}
-
-// removeAt removes a value at a given index, pulling all subsequent values
-// back.
-func (s *children) removeAt(index int) *node {
- n := (*s)[index]
- copy((*s)[index:], (*s)[index+1:])
- (*s)[len(*s)-1] = nil
- *s = (*s)[:len(*s)-1]
- return n
-}
-
-// pop removes and returns the last element in the list.
-func (s *children) pop() (out *node) {
- index := len(*s) - 1
- out = (*s)[index]
- (*s)[index] = nil
- *s = (*s)[:index]
- return
-}
-
-// truncate truncates this instance at index so that it contains only the
-// first index children. index must be less than or equal to length.
-func (s *children) truncate(index int) {
- var toClear children
- *s, toClear = (*s)[:index], (*s)[index:]
- for len(toClear) > 0 {
- toClear = toClear[copy(toClear, nilChildren):]
- }
-}
-
// node is an internal node in a tree.
//
// It must at all times maintain the invariant that either
// * len(children) == 0, len(items) unconstrained
// * len(children) == len(items) + 1
-type node struct {
- items items
- children children
- cow *copyOnWriteContext
+type node[T any] struct {
+ items items[T]
+ children items[*node[T]]
+ cow *copyOnWriteContext[T]
}
-func (n *node) mutableFor(cow *copyOnWriteContext) *node {
+func (n *node[T]) mutableFor(cow *copyOnWriteContext[T]) *node[T] {
if n.cow == cow {
return n
}
@@ -258,20 +240,20 @@
if cap(out.items) >= len(n.items) {
out.items = out.items[:len(n.items)]
} else {
- out.items = make(items, len(n.items), cap(n.items))
+ out.items = make(items[T], len(n.items), cap(n.items))
}
copy(out.items, n.items)
// Copy children
if cap(out.children) >= len(n.children) {
out.children = out.children[:len(n.children)]
} else {
- out.children = make(children, len(n.children), cap(n.children))
+ out.children = make(items[*node[T]], len(n.children), cap(n.children))
}
copy(out.children, n.children)
return out
}
-func (n *node) mutableChild(i int) *node {
+func (n *node[T]) mutableChild(i int) *node[T] {
c := n.children[i].mutableFor(n.cow)
n.children[i] = c
return c
@@ -280,7 +262,7 @@
// split splits the given node at the given index. The current node shrinks,
// and this function returns the item that existed at that index and a new node
// containing all items/children after it.
-func (n *node) split(i int) (Item, *node) {
+func (n *node[T]) split(i int) (T, *node[T]) {
item := n.items[i]
next := n.cow.newNode()
next.items = append(next.items, n.items[i+1:]...)
@@ -294,7 +276,7 @@
// maybeSplitChild checks if a child should be split, and if so splits it.
// Returns whether or not a split occurred.
-func (n *node) maybeSplitChild(i, maxItems int) bool {
+func (n *node[T]) maybeSplitChild(i, maxItems int) bool {
if len(n.children[i].items) < maxItems {
return false
}
@@ -308,70 +290,70 @@
// insert inserts an item into the subtree rooted at this node, making sure
// no nodes in the subtree exceed maxItems items. Should an equivalent item be
// be found/replaced by insert, it will be returned.
-func (n *node) insert(item Item, maxItems int) Item {
- i, found := n.items.find(item)
+func (n *node[T]) insert(item T, maxItems int) (_ T, _ bool) {
+ i, found := n.items.find(item, n.cow.less)
if found {
out := n.items[i]
n.items[i] = item
- return out
+ return out, true
}
if len(n.children) == 0 {
n.items.insertAt(i, item)
- return nil
+ return
}
if n.maybeSplitChild(i, maxItems) {
inTree := n.items[i]
switch {
- case item.Less(inTree):
+ case n.cow.less(item, inTree):
// no change, we want first split node
- case inTree.Less(item):
+ case n.cow.less(inTree, item):
i++ // we want second split node
default:
out := n.items[i]
n.items[i] = item
- return out
+ return out, true
}
}
return n.mutableChild(i).insert(item, maxItems)
}
// get finds the given key in the subtree and returns it.
-func (n *node) get(key Item) Item {
- i, found := n.items.find(key)
+func (n *node[T]) get(key T) (_ T, _ bool) {
+ i, found := n.items.find(key, n.cow.less)
if found {
- return n.items[i]
+ return n.items[i], true
} else if len(n.children) > 0 {
return n.children[i].get(key)
}
- return nil
+ return
}
// min returns the first item in the subtree.
-func min(n *node) Item {
+func min[T any](n *node[T]) (_ T, found bool) {
if n == nil {
- return nil
+ return
}
for len(n.children) > 0 {
n = n.children[0]
}
if len(n.items) == 0 {
- return nil
+ return
}
- return n.items[0]
+ return n.items[0], true
}
// max returns the last item in the subtree.
-func max(n *node) Item {
+func max[T any](n *node[T]) (_ T, found bool) {
if n == nil {
- return nil
+ return
}
for len(n.children) > 0 {
n = n.children[len(n.children)-1]
}
if len(n.items) == 0 {
- return nil
+ return
}
- return n.items[len(n.items)-1]
+ return n.items[len(n.items)-1], true
}
// toRemove details what item to remove in a node.remove call.
@@ -384,27 +366,27 @@
)
// remove removes an item from the subtree rooted at this node.
-func (n *node) remove(item Item, minItems int, typ toRemove) Item {
+func (n *node[T]) remove(item T, minItems int, typ toRemove) (_ T, _ bool) {
var i int
var found bool
switch typ {
case removeMax:
if len(n.children) == 0 {
- return n.items.pop()
+ return n.items.pop(), true
}
i = len(n.items)
case removeMin:
if len(n.children) == 0 {
- return n.items.removeAt(0)
+ return n.items.removeAt(0), true
}
i = 0
case removeItem:
- i, found = n.items.find(item)
+ i, found = n.items.find(item, n.cow.less)
if len(n.children) == 0 {
if found {
- return n.items.removeAt(i)
+ return n.items.removeAt(i), true
}
- return nil
+ return
}
default:
panic("invalid type")
@@ -424,8 +406,9 @@
// We use our special-case 'remove' call with typ=maxItem to pull the
// predecessor of item i (the rightmost leaf of our immediate left child)
// and set it into where we pulled the item from.
- n.items[i] = child.remove(nil, minItems, removeMax)
- return out
+ var zero T
+ n.items[i], _ = child.remove(zero, minItems, removeMax)
+ return out, true
}
// Final recursive call. Once we're here, we know that the item isn't in this
// node and that the child is big enough to remove from.
@@ -451,7 +434,7 @@
// We then simply redo our remove call, and the second time (regardless of
// whether we're in case 1 or 2), we'll have enough items and can guarantee
// that we hit case A.
-func (n *node) growChildAndRemove(i int, item Item, minItems int, typ toRemove) Item {
+func (n *node[T]) growChildAndRemove(i int, item T, minItems int, typ toRemove) (T, bool) {
if i > 0 && len(n.children[i-1].items) > minItems {
// Steal from left child
child := n.mutableChild(i)
@@ -495,6 +478,18 @@
ascend = direction(+1)
)
+type optionalItem[T any] struct {
+ item T
+ valid bool
+}
+
+func optional[T any](item T) optionalItem[T] {
+ return optionalItem[T]{item: item, valid: true}
+}
+func empty[T any]() optionalItem[T] {
+ return optionalItem[T]{}
+}
+
// iterate provides a simple method for iterating over elements in the tree.
//
// When ascending, the 'start' should be less than 'stop' and when descending,
@@ -502,13 +497,13 @@
// will force the iterator to include the first item when it equals 'start',
// thus creating a "greaterOrEqual" or "lessThanEqual" rather than just a
// "greaterThan" or "lessThan" queries.
-func (n *node) iterate(dir direction, start, stop Item, includeStart bool, hit bool, iter ItemIterator) (bool, bool) {
+func (n *node[T]) iterate(dir direction, start, stop optionalItem[T], includeStart bool, hit bool, iter ItemIteratorG[T]) (bool, bool) {
var ok, found bool
var index int
switch dir {
case ascend:
- if start != nil {
- index, _ = n.items.find(start)
+ if start.valid {
+ index, _ = n.items.find(start.item, n.cow.less)
}
for i := index; i < len(n.items); i++ {
if len(n.children) > 0 {
@@ -516,12 +511,12 @@
return hit, false
}
}
- if !includeStart && !hit && start != nil && !start.Less(n.items[i]) {
+ if !includeStart && !hit && start.valid && !n.cow.less(start.item, n.items[i]) {
hit = true
continue
}
hit = true
- if stop != nil && !n.items[i].Less(stop) {
+ if stop.valid && !n.cow.less(n.items[i], stop.item) {
return hit, false
}
if !iter(n.items[i]) {
@@ -534,8 +529,8 @@
}
}
case descend:
- if start != nil {
- index, found = n.items.find(start)
+ if start.valid {
+ index, found = n.items.find(start.item, n.cow.less)
if !found {
index = index - 1
}
@@ -547,7 +542,7 @@
return hit, false
}strang output:
rtfpessoa commented
👋 Can you explain what you mean by not aligned or how you would expect it to look?
zzjin commented
👋 Can you explain what you mean by not aligned or how you would expect it to look?
Updated. the diff file left and right are not aligenment same line. other diff files are one the same line like below:
rtfpessoa commented
I think you have to be more specific, I still cannot see what you mean.
m-masaki72 commented
I had the same problem with MisAlign, and I solved it by putting the following condition in the CSS.
I have submitted a PR to Diff2HTML, so please merge it if you want.