trie_test.go

Documentation: github.com/grpc-ecosystem/grpc-gateway/utilities

     1  package utilities_test
     2  
     3  import (
     4  	"reflect"
     5  	"testing"
     6  
     7  	"github.com/grpc-ecosystem/grpc-gateway/utilities"
     8  )
     9  
    10  func TestMaxCommonPrefix(t *testing.T) {
    11  	for _, spec := range []struct {
    12  		da     utilities.DoubleArray
    13  		tokens []string
    14  		want   bool
    15  	}{
    16  		{
    17  			da:     utilities.DoubleArray{},
    18  			tokens: nil,
    19  			want:   false,
    20  		},
    21  		{
    22  			da:     utilities.DoubleArray{},
    23  			tokens: []string{"foo"},
    24  			want:   false,
    25  		},
    26  		{
    27  			da: utilities.DoubleArray{
    28  				Encoding: map[string]int{
    29  					"foo": 0,
    30  				},
    31  				Base:  []int{1, 1, 0},
    32  				Check: []int{0, 1, 2},
    33  			},
    34  			tokens: nil,
    35  			want:   false,
    36  		},
    37  		{
    38  			da: utilities.DoubleArray{
    39  				Encoding: map[string]int{
    40  					"foo": 0,
    41  				},
    42  				Base:  []int{1, 1, 0},
    43  				Check: []int{0, 1, 2},
    44  			},
    45  			tokens: []string{"foo"},
    46  			want:   true,
    47  		},
    48  		{
    49  			da: utilities.DoubleArray{
    50  				Encoding: map[string]int{
    51  					"foo": 0,
    52  				},
    53  				Base:  []int{1, 1, 0},
    54  				Check: []int{0, 1, 2},
    55  			},
    56  			tokens: []string{"bar"},
    57  			want:   false,
    58  		},
    59  		{
    60  			// foo|bar
    61  			da: utilities.DoubleArray{
    62  				Encoding: map[string]int{
    63  					"foo": 0,
    64  					"bar": 1,
    65  				},
    66  				Base:  []int{1, 1, 2, 0, 0},
    67  				Check: []int{0, 1, 1, 2, 3},
    68  				// 0: ^
    69  				// 1: ^foo
    70  				// 2: ^bar
    71  				// 3: ^foo$
    72  				// 4: ^bar$
    73  			},
    74  			tokens: []string{"foo"},
    75  			want:   true,
    76  		},
    77  		{
    78  			// foo|bar
    79  			da: utilities.DoubleArray{
    80  				Encoding: map[string]int{
    81  					"foo": 0,
    82  					"bar": 1,
    83  				},
    84  				Base:  []int{1, 1, 2, 0, 0},
    85  				Check: []int{0, 1, 1, 2, 3},
    86  				// 0: ^
    87  				// 1: ^foo
    88  				// 2: ^bar
    89  				// 3: ^foo$
    90  				// 4: ^bar$
    91  			},
    92  			tokens: []string{"bar"},
    93  			want:   true,
    94  		},
    95  		{
    96  			// foo|bar
    97  			da: utilities.DoubleArray{
    98  				Encoding: map[string]int{
    99  					"foo": 0,
   100  					"bar": 1,
   101  				},
   102  				Base:  []int{1, 1, 2, 0, 0},
   103  				Check: []int{0, 1, 1, 2, 3},
   104  				// 0: ^
   105  				// 1: ^foo
   106  				// 2: ^bar
   107  				// 3: ^foo$
   108  				// 4: ^bar$
   109  			},
   110  			tokens: []string{"something-else"},
   111  			want:   false,
   112  		},
   113  		{
   114  			// foo|bar
   115  			da: utilities.DoubleArray{
   116  				Encoding: map[string]int{
   117  					"foo": 0,
   118  					"bar": 1,
   119  				},
   120  				Base:  []int{1, 1, 2, 0, 0},
   121  				Check: []int{0, 1, 1, 2, 3},
   122  				// 0: ^
   123  				// 1: ^foo
   124  				// 2: ^bar
   125  				// 3: ^foo$
   126  				// 4: ^bar$
   127  			},
   128  			tokens: []string{"foo", "bar"},
   129  			want:   true,
   130  		},
   131  		{
   132  			// foo|foo\.bar|bar
   133  			da: utilities.DoubleArray{
   134  				Encoding: map[string]int{
   135  					"foo": 0,
   136  					"bar": 1,
   137  				},
   138  				Base:  []int{1, 3, 1, 0, 4, 0, 0},
   139  				Check: []int{0, 1, 1, 3, 2, 2, 5},
   140  				// 0: ^
   141  				// 1: ^foo
   142  				// 2: ^bar
   143  				// 3: ^bar$
   144  				// 4: ^foo.bar
   145  				// 5: ^foo$
   146  				// 6: ^foo.bar$
   147  			},
   148  			tokens: []string{"foo"},
   149  			want:   true,
   150  		},
   151  		{
   152  			// foo|foo\.bar|bar
   153  			da: utilities.DoubleArray{
   154  				Encoding: map[string]int{
   155  					"foo": 0,
   156  					"bar": 1,
   157  				},
   158  				Base:  []int{1, 3, 1, 0, 4, 0, 0},
   159  				Check: []int{0, 1, 1, 3, 2, 2, 5},
   160  				// 0: ^
   161  				// 1: ^foo
   162  				// 2: ^bar
   163  				// 3: ^bar$
   164  				// 4: ^foo.bar
   165  				// 5: ^foo$
   166  				// 6: ^foo.bar$
   167  			},
   168  			tokens: []string{"foo", "bar"},
   169  			want:   true,
   170  		},
   171  		{
   172  			// foo|foo\.bar|bar
   173  			da: utilities.DoubleArray{
   174  				Encoding: map[string]int{
   175  					"foo": 0,
   176  					"bar": 1,
   177  				},
   178  				Base:  []int{1, 3, 1, 0, 4, 0, 0},
   179  				Check: []int{0, 1, 1, 3, 2, 2, 5},
   180  				// 0: ^
   181  				// 1: ^foo
   182  				// 2: ^bar
   183  				// 3: ^bar$
   184  				// 4: ^foo.bar
   185  				// 5: ^foo$
   186  				// 6: ^foo.bar$
   187  			},
   188  			tokens: []string{"bar"},
   189  			want:   true,
   190  		},
   191  		{
   192  			// foo|foo\.bar|bar
   193  			da: utilities.DoubleArray{
   194  				Encoding: map[string]int{
   195  					"foo": 0,
   196  					"bar": 1,
   197  				},
   198  				Base:  []int{1, 3, 1, 0, 4, 0, 0},
   199  				Check: []int{0, 1, 1, 3, 2, 2, 5},
   200  				// 0: ^
   201  				// 1: ^foo
   202  				// 2: ^bar
   203  				// 3: ^bar$
   204  				// 4: ^foo.bar
   205  				// 5: ^foo$
   206  				// 6: ^foo.bar$
   207  			},
   208  			tokens: []string{"something-else"},
   209  			want:   false,
   210  		},
   211  		{
   212  			// foo|foo\.bar|bar
   213  			da: utilities.DoubleArray{
   214  				Encoding: map[string]int{
   215  					"foo": 0,
   216  					"bar": 1,
   217  				},
   218  				Base:  []int{1, 3, 1, 0, 4, 0, 0},
   219  				Check: []int{0, 1, 1, 3, 2, 2, 5},
   220  				// 0: ^
   221  				// 1: ^foo
   222  				// 2: ^bar
   223  				// 3: ^bar$
   224  				// 4: ^foo.bar
   225  				// 5: ^foo$
   226  				// 6: ^foo.bar$
   227  			},
   228  			tokens: []string{"foo", "bar", "baz"},
   229  			want:   true,
   230  		},
   231  	} {
   232  		got := spec.da.HasCommonPrefix(spec.tokens)
   233  		if got != spec.want {
   234  			t.Errorf("%#v.HasCommonPrefix(%v) = %v; want %v", spec.da, spec.tokens, got, spec.want)
   235  		}
   236  	}
   237  }
   238  
   239  func TestAdd(t *testing.T) {
   240  	for _, spec := range []struct {
   241  		tokens [][]string
   242  		want   utilities.DoubleArray
   243  	}{
   244  		{
   245  			want: utilities.DoubleArray{
   246  				Encoding: make(map[string]int),
   247  			},
   248  		},
   249  		{
   250  			tokens: [][]string{{"foo"}},
   251  			want: utilities.DoubleArray{
   252  				Encoding: map[string]int{"foo": 0},
   253  				Base:     []int{1, 1, 0},
   254  				Check:    []int{0, 1, 2},
   255  				// 0: ^
   256  				// 1: ^foo
   257  				// 2: ^foo$
   258  			},
   259  		},
   260  		{
   261  			tokens: [][]string{{"foo"}, {"bar"}},
   262  			want: utilities.DoubleArray{
   263  				Encoding: map[string]int{
   264  					"foo": 0,
   265  					"bar": 1,
   266  				},
   267  				Base:  []int{1, 1, 2, 0, 0},
   268  				Check: []int{0, 1, 1, 2, 3},
   269  				// 0: ^
   270  				// 1: ^foo
   271  				// 2: ^bar
   272  				// 3: ^foo$
   273  				// 4: ^bar$
   274  			},
   275  		},
   276  		{
   277  			tokens: [][]string{{"foo", "bar"}, {"foo", "baz"}},
   278  			want: utilities.DoubleArray{
   279  				Encoding: map[string]int{
   280  					"foo": 0,
   281  					"bar": 1,
   282  					"baz": 2,
   283  				},
   284  				Base:  []int{1, 1, 1, 2, 0, 0},
   285  				Check: []int{0, 1, 2, 2, 3, 4},
   286  				// 0: ^
   287  				// 1: ^foo
   288  				// 2: ^foo.bar
   289  				// 3: ^foo.baz
   290  				// 4: ^foo.bar$
   291  				// 5: ^foo.baz$
   292  			},
   293  		},
   294  		{
   295  			tokens: [][]string{{"foo", "bar"}, {"foo", "baz"}, {"qux"}},
   296  			want: utilities.DoubleArray{
   297  				Encoding: map[string]int{
   298  					"foo": 0,
   299  					"bar": 1,
   300  					"baz": 2,
   301  					"qux": 3,
   302  				},
   303  				Base:  []int{1, 1, 1, 2, 3, 0, 0, 0},
   304  				Check: []int{0, 1, 2, 2, 1, 3, 4, 5},
   305  				// 0: ^
   306  				// 1: ^foo
   307  				// 2: ^foo.bar
   308  				// 3: ^foo.baz
   309  				// 4: ^qux
   310  				// 5: ^foo.bar$
   311  				// 6: ^foo.baz$
   312  				// 7: ^qux$
   313  			},
   314  		},
   315  		{
   316  			tokens: [][]string{
   317  				{"foo", "bar"},
   318  				{"foo", "baz", "bar"},
   319  				{"qux", "foo"},
   320  			},
   321  			want: utilities.DoubleArray{
   322  				Encoding: map[string]int{
   323  					"foo": 0,
   324  					"bar": 1,
   325  					"baz": 2,
   326  					"qux": 3,
   327  				},
   328  				Base:  []int{1, 1, 1, 5, 8, 0, 3, 0, 5, 0},
   329  				Check: []int{0, 1, 2, 2, 1, 3, 4, 7, 5, 9},
   330  				// 0: ^
   331  				// 1: ^foo
   332  				// 2: ^foo.bar
   333  				// 3: ^foo.baz
   334  				// 4: ^qux
   335  				// 5: ^foo.bar$
   336  				// 6: ^foo.baz.bar
   337  				// 7: ^foo.baz.bar$
   338  				// 8: ^qux.foo
   339  				// 9: ^qux.foo$
   340  			},
   341  		},
   342  	} {
   343  		da := utilities.NewDoubleArray(spec.tokens)
   344  		if got, want := da.Encoding, spec.want.Encoding; !reflect.DeepEqual(got, want) {
   345  			t.Errorf("da.Encoding = %v; want %v; tokens = %#v", got, want, spec.tokens)
   346  		}
   347  		if got, want := da.Base, spec.want.Base; !compareArray(got, want) {
   348  			t.Errorf("da.Base = %v; want %v; tokens = %#v", got, want, spec.tokens)
   349  		}
   350  		if got, want := da.Check, spec.want.Check; !compareArray(got, want) {
   351  			t.Errorf("da.Check = %v; want %v; tokens = %#v", got, want, spec.tokens)
   352  		}
   353  	}
   354  }
   355  
   356  func compareArray(got, want []int) bool {
   357  	var i int
   358  	for i = 0; i < len(got) && i < len(want); i++ {
   359  		if got[i] != want[i] {
   360  			return false
   361  		}
   362  	}
   363  	if i < len(want) {
   364  		return false
   365  	}
   366  	for ; i < len(got); i++ {
   367  		if got[i] != 0 {
   368  			return false
   369  		}
   370  	}
   371  	return true
   372  }
   373
View as plain text