2019-08-18 19:46:12 +00:00
|
|
|
package tried
|
|
|
|
|
|
|
|
import (
|
2019-08-19 11:03:58 +00:00
|
|
|
"bytes"
|
|
|
|
"encoding/gob"
|
|
|
|
"os"
|
2019-08-20 03:11:10 +00:00
|
|
|
"sort"
|
2019-08-18 19:46:12 +00:00
|
|
|
"testing"
|
2019-08-19 06:30:24 +00:00
|
|
|
|
2019-08-20 03:11:10 +00:00
|
|
|
"github.com/davecgh/go-spew/spew"
|
|
|
|
|
2019-08-19 06:30:24 +00:00
|
|
|
"github.com/Pallinder/go-randomdata"
|
2019-08-18 19:46:12 +00:00
|
|
|
)
|
|
|
|
|
2019-08-20 07:03:05 +00:00
|
|
|
func CompareSliceWithSorted(source, words []string) (bool, string) {
|
|
|
|
sort.Slice(words, func(i, j int) bool {
|
|
|
|
if words[i] < words[j] {
|
|
|
|
return true
|
|
|
|
}
|
|
|
|
return false
|
|
|
|
})
|
|
|
|
|
|
|
|
// source := tried.WordsArray()
|
|
|
|
sort.Slice(source, func(i, j int) bool {
|
|
|
|
if source[i] < source[j] {
|
|
|
|
return true
|
|
|
|
}
|
|
|
|
return false
|
|
|
|
})
|
|
|
|
result1 := spew.Sprint(source)
|
|
|
|
result2 := spew.Sprint(words)
|
|
|
|
|
|
|
|
if result1 != result2 {
|
|
|
|
return false, spew.Sprint(result1, " != ", result2)
|
|
|
|
}
|
|
|
|
return true, ""
|
|
|
|
}
|
|
|
|
|
|
|
|
func TestTried_Has(t *testing.T) {
|
|
|
|
var tried *Tried
|
|
|
|
tried = NewWithWordType(WordIndexLower)
|
|
|
|
tried.Put("ads")
|
|
|
|
tried.Put("zadads")
|
|
|
|
tried.Put("asdgdf")
|
|
|
|
if !tried.Has("ads") {
|
|
|
|
t.Error("ads is exist, but not has")
|
|
|
|
}
|
|
|
|
|
|
|
|
if !tried.HasPrefix("ad") {
|
|
|
|
t.Error("ads is exist, but not HasPrefix")
|
|
|
|
}
|
|
|
|
|
|
|
|
if !tried.HasPrefix("za") {
|
|
|
|
t.Error("ads is exist, but not HasPrefix")
|
|
|
|
}
|
|
|
|
|
|
|
|
if tried.HasPrefix("fsdf") {
|
|
|
|
t.Error("fsdf is not exist, but HasPrefix")
|
|
|
|
}
|
|
|
|
|
|
|
|
if len(tried.String()) < 10 {
|
|
|
|
t.Error(tried.WordsArray())
|
|
|
|
}
|
|
|
|
}
|
|
|
|
func TestTried_PrefixWords(t *testing.T) {
|
|
|
|
|
|
|
|
var tried *Tried
|
|
|
|
var wordsCollection []string
|
|
|
|
var input []string
|
|
|
|
|
|
|
|
var wordsList [][]string
|
|
|
|
var inputParams [][]string
|
|
|
|
var triedList []*Tried
|
|
|
|
|
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexLower))
|
|
|
|
inputParams = append(inputParams, []string{"ad", "adf"})
|
|
|
|
wordsList = append(wordsList, []string{"ad", "adfsxzcdas", "adfadsasd"})
|
|
|
|
|
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexUpper))
|
|
|
|
inputParams = append(inputParams, []string{"AD", "ADF"})
|
|
|
|
wordsList = append(wordsList, []string{"AD", "ADFSXZCDAS", "ADFADSASD"})
|
|
|
|
|
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexUpperLower))
|
|
|
|
inputParams = append(inputParams, []string{"aD", "aDf"})
|
|
|
|
wordsList = append(wordsList, []string{"aDF", "aDfsxzcdas", "aDfadsasd"})
|
|
|
|
|
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexUpperDigital))
|
|
|
|
inputParams = append(inputParams, []string{"A09D", "A09DF"})
|
|
|
|
wordsList = append(wordsList, []string{"A09D", "A09DFSXZCD312AS", "A09DFA32DSASD"})
|
|
|
|
|
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexLowerDigital))
|
|
|
|
inputParams = append(inputParams, []string{"a09d", "a09df"})
|
|
|
|
wordsList = append(wordsList, []string{"a09d", "a09dfsxzcd312as", "a09dfa32dsasd"})
|
|
|
|
|
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexUpperLowerDigital))
|
|
|
|
inputParams = append(inputParams, []string{"A09d", "A09dZ"})
|
|
|
|
wordsList = append(wordsList, []string{"A09d", "A09dZsxzcd312as", "A09dZa32dsasd"})
|
|
|
|
|
|
|
|
triedList = append(triedList, NewWithWordType(WordIndex256))
|
|
|
|
inputParams = append(inputParams, []string{"阿萨德", "阿萨德!"})
|
|
|
|
wordsList = append(wordsList, []string{"阿萨德", "阿萨德!@$*#))(#*", "阿萨德!╜╝╞╟╠╡╢╣╤╥╦╧╨╩╪╫╬╭╮╯╰╱╲╳▁▂▃▄▅▆▇█ ▉ ▊▋▌▍▎▏"})
|
|
|
|
|
|
|
|
triedList = append(triedList, NewWithWordType(WordIndex32to126))
|
|
|
|
inputParams = append(inputParams, []string{" `", " `<"})
|
|
|
|
wordsList = append(wordsList, []string{" `21`3tcdbxcfhyop8901zc[]\\'/?()#$%^&**! ", " `<AZaz09~ dys!@#$)(*^$#", " `<>.,?/"})
|
|
|
|
|
|
|
|
for i := 0; i < len(triedList); i++ {
|
|
|
|
tried = triedList[i]
|
|
|
|
input = inputParams[i]
|
|
|
|
wordsCollection = wordsList[i]
|
|
|
|
for _, words := range wordsCollection {
|
|
|
|
tried.Put(words)
|
|
|
|
}
|
|
|
|
var prefixWords []string
|
|
|
|
prefixWords = tried.PrefixWords(input[0])
|
|
|
|
if ok, errorResult := CompareSliceWithSorted(prefixWords, wordsCollection); !ok {
|
|
|
|
t.Error(errorResult)
|
|
|
|
}
|
|
|
|
|
|
|
|
prefixWords = tried.PrefixWords(input[1])
|
|
|
|
if ok, _ := CompareSliceWithSorted(prefixWords, wordsCollection); ok {
|
|
|
|
t.Error("should be not ok")
|
|
|
|
}
|
|
|
|
if len(prefixWords) != 2 {
|
|
|
|
t.Error(prefixWords, " Size of Array should be 2")
|
|
|
|
}
|
|
|
|
|
|
|
|
if ok, errorResult := CompareSliceWithSorted(prefixWords, wordsCollection[1:]); !ok {
|
|
|
|
t.Error(errorResult)
|
|
|
|
}
|
|
|
|
|
|
|
|
// t.Error(tried.WordsArray())
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2019-08-19 11:03:58 +00:00
|
|
|
func TestTried_NewWith(t *testing.T) {
|
2019-08-19 17:39:14 +00:00
|
|
|
var tried *Tried
|
2019-08-20 03:11:10 +00:00
|
|
|
var wordsCollection []string
|
|
|
|
var wordsList [][]string
|
|
|
|
var triedList []*Tried
|
2019-08-19 11:03:58 +00:00
|
|
|
|
2019-08-20 03:11:10 +00:00
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexLower))
|
|
|
|
wordsList = append(wordsList, []string{"adazx", "assdfhgnvb", "ewqyiouyasdfmzvxz"})
|
2019-08-19 11:03:58 +00:00
|
|
|
|
2019-08-20 03:11:10 +00:00
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexUpper))
|
|
|
|
wordsList = append(wordsList, []string{"ADFSZ", "DEFASEWRQWER", "GFHJERQWREWTNBVFGFH"})
|
2019-08-19 11:03:58 +00:00
|
|
|
|
2019-08-20 03:11:10 +00:00
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexUpperLower))
|
|
|
|
wordsList = append(wordsList, []string{"adazxAZDSAFASZRETHGFTUIPK", "assdfhgDSFGnvb", "yaXZLMPOIQsdGHFfmFBzvxz"})
|
2019-08-19 17:39:14 +00:00
|
|
|
|
2019-08-20 03:11:10 +00:00
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexUpperDigital))
|
|
|
|
wordsList = append(wordsList, []string{"AZ3428934470193", "ZPQPDEK09876543629812", "AZEWIRU0192456FDEWR9032"})
|
2019-08-19 17:39:14 +00:00
|
|
|
|
2019-08-20 03:11:10 +00:00
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexLowerDigital))
|
|
|
|
wordsList = append(wordsList, []string{"az3428934470193", "zpqwe0987654362sf9812", "az21301az09azdstr540"})
|
2019-08-19 17:39:14 +00:00
|
|
|
|
2019-08-20 03:11:10 +00:00
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexUpperLowerDigital))
|
|
|
|
wordsList = append(wordsList, []string{"azAZ09", "aRGFDSFDSzAasdZ06789", "A28374JHFudfsu09qwzzdsw874FDSAZfer"})
|
2019-08-19 17:39:14 +00:00
|
|
|
|
2019-08-20 03:11:10 +00:00
|
|
|
triedList = append(triedList, NewWithWordType(WordIndex256))
|
|
|
|
wordsList = append(wordsList, []string{"21`3tcdbxcfhyop8901zc[]\\'/?()#$%^&**! 09-阿萨德发生的官方说的对符合规定", "符号!@$*#))(#*", "╜╝╞╟╠╡╢╣╤╥╦╧╨╩╪╫╬╭╮╯╰╱╲╳▁▂▃▄▅▆▇█ ▉ ▊▋▌▍▎▏"})
|
2019-08-19 17:39:14 +00:00
|
|
|
|
2019-08-20 03:11:10 +00:00
|
|
|
triedList = append(triedList, NewWithWordType(WordIndex32to126))
|
|
|
|
wordsList = append(wordsList, []string{" 21`3tcdbxcfhyop8901zc[]\\'/?()#$%^&**! ", "AZaz09~ dys!@#$)(*^$#", "<>.,?/"})
|
|
|
|
|
|
|
|
for i := 0; i < len(triedList); i++ {
|
|
|
|
tried = triedList[i]
|
|
|
|
wordsCollection = wordsList[i]
|
|
|
|
for _, words := range wordsCollection {
|
|
|
|
tried.Put(words)
|
|
|
|
|
|
|
|
if tried.Get(words) == nil {
|
|
|
|
t.Error("should be not nil the type is ", tried.wiStore.Type)
|
|
|
|
}
|
|
|
|
}
|
|
|
|
// t.Error(tried.WordsArray())
|
2019-08-19 17:39:14 +00:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
func TestTried_String(t *testing.T) {
|
|
|
|
var tried *Tried
|
|
|
|
var wordsCollection []string
|
|
|
|
var wordsList [][]string
|
|
|
|
var triedList []*Tried
|
|
|
|
|
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexLower))
|
|
|
|
wordsList = append(wordsList, []string{"adazx", "assdfhgnvb", "ewqyiouyasdfmzvxz"})
|
|
|
|
|
2019-08-20 03:11:10 +00:00
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexUpper))
|
|
|
|
wordsList = append(wordsList, []string{"ADFSZ", "DEFASEWRQWER", "GFHJERQWREWTNBVFGFH"})
|
|
|
|
|
2019-08-20 03:13:26 +00:00
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexDigital))
|
|
|
|
wordsList = append(wordsList, []string{"093875239457", "09123406534", "0912340846"})
|
|
|
|
|
2019-08-20 03:11:10 +00:00
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexUpperLower))
|
|
|
|
wordsList = append(wordsList, []string{"adazxAZDSAFASZRETHGFTUIPK", "assdfhgDSFGnvb", "yaXZLMPOIQsdGHFfmFBzvxz"})
|
|
|
|
|
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexUpperDigital))
|
|
|
|
wordsList = append(wordsList, []string{"AZ3428934470193", "ZPQPDEK09876543629812", "AZEWIRU0192456FDEWR9032"})
|
|
|
|
|
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexLowerDigital))
|
|
|
|
wordsList = append(wordsList, []string{"az3428934470193", "zpqwe0987654362sf9812", "az21301az09azdstr540"})
|
|
|
|
|
|
|
|
triedList = append(triedList, NewWithWordType(WordIndexUpperLowerDigital))
|
|
|
|
wordsList = append(wordsList, []string{"azAZ09", "aRGFDSFDSzAasdZ06789", "A28374JHFudfsu09qwzzdsw874FDSAZfer"})
|
|
|
|
|
|
|
|
triedList = append(triedList, NewWithWordType(WordIndex256))
|
2019-08-20 03:38:24 +00:00
|
|
|
wordsList = append(wordsList, []string{"21`3tcdbxcf囉hyop打算8901zc[]\\'/?()#$%^&**!\x01 09-213", "的支持中文", "!@$*#)中文)(#*", `\/213dsfsdf`})
|
2019-08-20 03:11:10 +00:00
|
|
|
|
|
|
|
triedList = append(triedList, NewWithWordType(WordIndex32to126))
|
|
|
|
wordsList = append(wordsList, []string{" 21`3tcdbxcfhyop8901zc[]\\'/?()#$%^&**! ", "AZaz09~ dys!@#$)(*^$#", "<>.,?/"})
|
|
|
|
|
2019-08-19 17:39:14 +00:00
|
|
|
for i := 0; i < len(triedList); i++ {
|
|
|
|
tried = triedList[i]
|
|
|
|
wordsCollection = wordsList[i]
|
|
|
|
for _, words := range wordsCollection {
|
|
|
|
tried.Put(words)
|
|
|
|
if tried.Get(words) == nil {
|
2019-08-20 03:11:10 +00:00
|
|
|
t.Error("should be not nil the type is ", tried.wiStore.Type)
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
resultArray := tried.WordsArray()
|
2019-08-20 07:03:05 +00:00
|
|
|
if ok, errorResult := CompareSliceWithSorted(resultArray, wordsCollection); !ok {
|
|
|
|
t.Error(errorResult)
|
2019-08-19 17:39:14 +00:00
|
|
|
}
|
2019-08-20 07:03:05 +00:00
|
|
|
|
2019-08-20 03:11:10 +00:00
|
|
|
// t.Error(tried.WordsArray())
|
2019-08-19 17:39:14 +00:00
|
|
|
}
|
2019-08-19 11:03:58 +00:00
|
|
|
}
|
|
|
|
|
2019-08-19 07:28:09 +00:00
|
|
|
func TestTried_PutAndGet1(t *testing.T) {
|
|
|
|
tried := New()
|
|
|
|
|
|
|
|
tried.Put(("asdf"))
|
|
|
|
tried.Put(("hehe"), "hehe")
|
|
|
|
tried.Put(("xixi"), 3)
|
|
|
|
|
|
|
|
var result interface{}
|
|
|
|
|
|
|
|
result = tried.Get("asdf")
|
|
|
|
if result != tried {
|
|
|
|
t.Error("result should be 3")
|
|
|
|
}
|
|
|
|
|
|
|
|
result = tried.Get("xixi")
|
|
|
|
if result != 3 {
|
|
|
|
t.Error("result should be 3")
|
|
|
|
}
|
|
|
|
|
|
|
|
result = tried.Get("hehe")
|
|
|
|
if result != "hehe" {
|
|
|
|
t.Error("result should be hehe")
|
|
|
|
}
|
|
|
|
|
|
|
|
result = tried.Get("haha")
|
|
|
|
if result != nil {
|
|
|
|
t.Error("result should be nil")
|
|
|
|
}
|
|
|
|
|
|
|
|
result = tried.Get("b")
|
|
|
|
if result != nil {
|
|
|
|
t.Error("result should be nil")
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
func TestTried_Traversal(t *testing.T) {
|
|
|
|
tried := New()
|
|
|
|
tried.Put("asdf")
|
|
|
|
tried.Put(("abdf"), "ab")
|
|
|
|
tried.Put(("hehe"), "hehe")
|
|
|
|
tried.Put(("xixi"), 3)
|
|
|
|
|
|
|
|
var result []interface{}
|
|
|
|
tried.Traversal(func(idx uint, v interface{}) bool {
|
|
|
|
// t.Error(idx, v)
|
|
|
|
result = append(result, v)
|
|
|
|
return true
|
|
|
|
})
|
|
|
|
|
|
|
|
if result[0] != "ab" {
|
|
|
|
t.Error(result[0])
|
|
|
|
}
|
|
|
|
|
|
|
|
if result[1] != tried {
|
|
|
|
t.Error(result[1])
|
|
|
|
}
|
|
|
|
|
|
|
|
if result[2] != "hehe" {
|
|
|
|
t.Error(result[2])
|
|
|
|
}
|
|
|
|
|
|
|
|
if result[3] != 3 {
|
|
|
|
t.Error(result[3])
|
|
|
|
}
|
|
|
|
}
|
2019-08-19 06:30:24 +00:00
|
|
|
|
2019-08-19 11:03:58 +00:00
|
|
|
func TesStoreData(t *testing.T) {
|
|
|
|
var l []string
|
|
|
|
const N = 1000000
|
|
|
|
for i := 0; i < N; i++ {
|
2019-08-19 07:24:22 +00:00
|
|
|
var content []rune
|
|
|
|
for c := 0; c < randomdata.Number(5, 15); c++ {
|
|
|
|
char := randomdata.Number(0, 26) + 'a'
|
|
|
|
content = append(content, rune(byte(char)))
|
|
|
|
}
|
2019-08-19 11:03:58 +00:00
|
|
|
l = append(l, (string(content)))
|
2019-08-19 06:30:24 +00:00
|
|
|
}
|
|
|
|
|
2019-08-19 11:03:58 +00:00
|
|
|
var result bytes.Buffer
|
|
|
|
encoder := gob.NewEncoder(&result)
|
|
|
|
encoder.Encode(l)
|
|
|
|
lbytes := result.Bytes()
|
|
|
|
f, _ := os.OpenFile("tried.log", os.O_CREATE|os.O_TRUNC|os.O_WRONLY, 0666)
|
|
|
|
f.Write(lbytes)
|
|
|
|
}
|
|
|
|
|
|
|
|
func Load() []string {
|
|
|
|
var result []string
|
2019-08-20 07:37:35 +00:00
|
|
|
f, err := os.Open("tried.log")
|
|
|
|
if err != nil {
|
|
|
|
panic("先执行TesStoreData 然后再测试Benchmark")
|
|
|
|
}
|
2019-08-19 11:03:58 +00:00
|
|
|
gob.NewDecoder(f).Decode(&result)
|
|
|
|
return result
|
|
|
|
}
|
|
|
|
|
|
|
|
func BenchmarkTried_Put(b *testing.B) {
|
|
|
|
|
|
|
|
var data []string
|
|
|
|
b.N = 1000000
|
|
|
|
count := 10
|
|
|
|
|
|
|
|
// for i := 0; i < b.N; i++ {
|
|
|
|
// var content []rune
|
|
|
|
// for c := 0; c < randomdata.Number(5, 15); c++ {
|
|
|
|
// char := randomdata.Number(0, 26) + 'a'
|
|
|
|
// content = append(content, rune(byte(char)))
|
|
|
|
// }
|
|
|
|
// data = append(data, (string(content)))
|
|
|
|
// }
|
|
|
|
|
|
|
|
data = Load()
|
|
|
|
|
2019-08-19 06:30:24 +00:00
|
|
|
b.ResetTimer()
|
|
|
|
b.N = b.N * count
|
|
|
|
for c := 0; c < count; c++ {
|
|
|
|
tried := New()
|
|
|
|
for _, v := range data {
|
|
|
|
tried.Put(v)
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
2019-08-18 19:46:12 +00:00
|
|
|
|
2019-08-19 06:30:24 +00:00
|
|
|
func BenchmarkTried_Get(b *testing.B) {
|
2019-08-19 11:03:58 +00:00
|
|
|
b.StopTimer()
|
2019-08-19 07:28:09 +00:00
|
|
|
var data []string
|
2019-08-19 07:24:22 +00:00
|
|
|
b.N = 1000000
|
|
|
|
count := 10
|
2019-08-19 06:30:24 +00:00
|
|
|
|
2019-08-19 11:03:58 +00:00
|
|
|
// for i := 0; i < b.N; i++ {
|
|
|
|
// var content []rune
|
|
|
|
// for c := 0; c < randomdata.Number(5, 15); c++ {
|
|
|
|
// char := randomdata.Number(0, 26) + 'a'
|
|
|
|
// content = append(content, rune(byte(char)))
|
|
|
|
// }
|
|
|
|
// data = append(data, string(content))
|
|
|
|
// }
|
|
|
|
data = Load()
|
2019-08-19 06:30:24 +00:00
|
|
|
|
|
|
|
b.N = b.N * count
|
|
|
|
|
|
|
|
tried := New()
|
|
|
|
for _, v := range data {
|
|
|
|
tried.Put(v)
|
|
|
|
}
|
|
|
|
|
2019-08-19 11:03:58 +00:00
|
|
|
b.StartTimer()
|
2019-08-19 06:30:24 +00:00
|
|
|
for c := 0; c < count; c++ {
|
|
|
|
for _, v := range data {
|
|
|
|
tried.Get(v)
|
|
|
|
}
|
|
|
|
}
|
2019-08-18 19:46:12 +00:00
|
|
|
}
|