btree.go

Documentation: github.com/gobwas/glob/match

     1  package match
     2  
     3  import (
     4  	"fmt"
     5  	"unicode/utf8"
     6  )
     7  
     8  type BTree struct {
     9  	Value            Matcher
    10  	Left             Matcher
    11  	Right            Matcher
    12  	ValueLengthRunes int
    13  	LeftLengthRunes  int
    14  	RightLengthRunes int
    15  	LengthRunes      int
    16  }
    17  
    18  func NewBTree(Value, Left, Right Matcher) (tree BTree) {
    19  	tree.Value = Value
    20  	tree.Left = Left
    21  	tree.Right = Right
    22  
    23  	lenOk := true
    24  	if tree.ValueLengthRunes = Value.Len(); tree.ValueLengthRunes == -1 {
    25  		lenOk = false
    26  	}
    27  
    28  	if Left != nil {
    29  		if tree.LeftLengthRunes = Left.Len(); tree.LeftLengthRunes == -1 {
    30  			lenOk = false
    31  		}
    32  	}
    33  
    34  	if Right != nil {
    35  		if tree.RightLengthRunes = Right.Len(); tree.RightLengthRunes == -1 {
    36  			lenOk = false
    37  		}
    38  	}
    39  
    40  	if lenOk {
    41  		tree.LengthRunes = tree.LeftLengthRunes + tree.ValueLengthRunes + tree.RightLengthRunes
    42  	} else {
    43  		tree.LengthRunes = -1
    44  	}
    45  
    46  	return tree
    47  }
    48  
    49  func (self BTree) Len() int {
    50  	return self.LengthRunes
    51  }
    52  
    53  // todo?
    54  func (self BTree) Index(s string) (int, []int) {
    55  	return -1, nil
    56  }
    57  
    58  func (self BTree) Match(s string) bool {
    59  	inputLen := len(s)
    60  
    61  	// self.Length, self.RLen and self.LLen are values meaning the length of runes for each part
    62  	// here we manipulating byte length for better optimizations
    63  	// but these checks still works, cause minLen of 1-rune string is 1 byte.
    64  	if self.LengthRunes != -1 && self.LengthRunes > inputLen {
    65  		return false
    66  	}
    67  
    68  	// try to cut unnecessary parts
    69  	// by knowledge of length of right and left part
    70  	var offset, limit int
    71  	if self.LeftLengthRunes >= 0 {
    72  		offset = self.LeftLengthRunes
    73  	}
    74  	if self.RightLengthRunes >= 0 {
    75  		limit = inputLen - self.RightLengthRunes
    76  	} else {
    77  		limit = inputLen
    78  	}
    79  
    80  	for offset < limit {
    81  		// search for matching part in substring
    82  		index, segments := self.Value.Index(s[offset:limit])
    83  		if index == -1 {
    84  			releaseSegments(segments)
    85  			return false
    86  		}
    87  
    88  		l := s[:offset+index]
    89  		var left bool
    90  		if self.Left != nil {
    91  			left = self.Left.Match(l)
    92  		} else {
    93  			left = l == ""
    94  		}
    95  
    96  		if left {
    97  			for i := len(segments) - 1; i >= 0; i-- {
    98  				length := segments[i]
    99  
   100  				var right bool
   101  				var r string
   102  				// if there is no string for the right branch
   103  				if inputLen <= offset+index+length {
   104  					r = ""
   105  				} else {
   106  					r = s[offset+index+length:]
   107  				}
   108  
   109  				if self.Right != nil {
   110  					right = self.Right.Match(r)
   111  				} else {
   112  					right = r == ""
   113  				}
   114  
   115  				if right {
   116  					releaseSegments(segments)
   117  					return true
   118  				}
   119  			}
   120  		}
   121  
   122  		_, step := utf8.DecodeRuneInString(s[offset+index:])
   123  		offset += index + step
   124  
   125  		releaseSegments(segments)
   126  	}
   127  
   128  	return false
   129  }
   130  
   131  func (self BTree) String() string {
   132  	const n string = "<nil>"
   133  	var l, r string
   134  	if self.Left == nil {
   135  		l = n
   136  	} else {
   137  		l = self.Left.String()
   138  	}
   139  	if self.Right == nil {
   140  		r = n
   141  	} else {
   142  		r = self.Right.String()
   143  	}
   144  
   145  	return fmt.Sprintf("<btree:[%s<-%s->%s]>", l, self.Value, r)
   146  }
   147
View as plain text