indexmanager.go 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909
  1. /*
  2. * EliasDB
  3. *
  4. * Copyright 2016 Matthias Ladkau. All rights reserved.
  5. *
  6. * This Source Code Form is subject to the terms of the Mozilla Public
  7. * License, v. 2.0. If a copy of the MPL was not distributed with this
  8. * file, You can obtain one at http://mozilla.org/MPL/2.0/.
  9. */
  10. package util
  11. import (
  12. "bytes"
  13. "crypto/md5"
  14. "encoding/gob"
  15. "fmt"
  16. "math"
  17. "sort"
  18. "strings"
  19. "unicode"
  20. "devt.de/krotik/common/bitutil"
  21. "devt.de/krotik/common/sortutil"
  22. "devt.de/krotik/common/stringutil"
  23. "devt.de/krotik/eliasdb/hash"
  24. )
  25. /*
  26. MaxKeysetSize is the maximum number of keys for a single word lookup.
  27. */
  28. const MaxKeysetSize = 1000
  29. /*
  30. CaseSensitiveWordIndex is a flag to indicate if the index should be case sensitive.
  31. */
  32. var CaseSensitiveWordIndex = false
  33. /*
  34. PrefixAttrWord is the prefix used for word index entries
  35. */
  36. const PrefixAttrWord = string(0x01)
  37. /*
  38. PrefixAttrHash is the prefix used for hashes of attribute values
  39. */
  40. const PrefixAttrHash = string(0x02)
  41. /*
  42. IndexManager data structure
  43. */
  44. type IndexManager struct {
  45. htree *hash.HTree // Persistent HTree which stores this index
  46. }
  47. /*
  48. indexEntry data structure
  49. */
  50. type indexEntry struct {
  51. WordPos map[string]string // Node id to word position array
  52. }
  53. func init() {
  54. // Make sure we can use indexEntry in a gob operation
  55. gob.Register(&indexEntry{})
  56. }
  57. /*
  58. NewIndexManager creates a new index manager instance.
  59. */
  60. func NewIndexManager(htree *hash.HTree) *IndexManager {
  61. return &IndexManager{htree}
  62. }
  63. /*
  64. Index indexes (inserts) a given object.
  65. */
  66. func (im *IndexManager) Index(key string, obj map[string]string) error {
  67. return im.updateIndex(key, obj, nil)
  68. }
  69. /*
  70. Reindex reindexes (updates) a given object.
  71. */
  72. func (im *IndexManager) Reindex(key string, newObj map[string]string,
  73. oldObj map[string]string) error {
  74. return im.updateIndex(key, newObj, oldObj)
  75. }
  76. /*
  77. Deindex deindexes (removes) a given object.
  78. */
  79. func (im *IndexManager) Deindex(key string, obj map[string]string) error {
  80. return im.updateIndex(key, nil, obj)
  81. }
  82. /*
  83. LookupPhrase finds all nodes where an attribute contains a certain phrase. This
  84. call returns a list of node keys which contain the phrase at least once.
  85. */
  86. func (im *IndexManager) LookupPhrase(attr, phrase string) ([]string, error) {
  87. // Chop up the phrase into words
  88. phraseWords := strings.FieldsFunc(phrase, func(r rune) bool {
  89. return !stringutil.IsAlphaNumeric(string(r)) && (unicode.IsSpace(r) || unicode.IsControl(r) || unicode.IsPunct(r))
  90. })
  91. // Lookup every phrase word
  92. results := make([]map[string][]uint64, len(phraseWords))
  93. for i, phraseWord := range phraseWords {
  94. res, err := im.LookupWord(attr, phraseWord)
  95. if err != nil {
  96. return nil, &GraphError{ErrIndexError, err.Error()}
  97. }
  98. results[i] = res
  99. }
  100. if len(results) == 0 || len(results[0]) == 0 {
  101. return nil, nil
  102. }
  103. ret := make([]string, 0, len(results[0]))
  104. // Go through all found nodes and try to find a path
  105. path := make([]uint64, 0, len(phraseWords))
  106. for key := range results[0] {
  107. path = path[:0]
  108. foundWords := im.findPhrasePath(key, 0, path, phraseWords, results)
  109. if foundWords == len(phraseWords) {
  110. // Add key to results if a path was found
  111. ret = append(ret, key)
  112. }
  113. }
  114. // Guarantee a stable result
  115. sort.StringSlice(ret).Sort()
  116. return ret, nil
  117. }
  118. /*
  119. findPhrasePath tries to find a phrase in a given set of lookup results.
  120. */
  121. func (im *IndexManager) findPhrasePath(key string, index int, path []uint64,
  122. phraseWords []string, results []map[string][]uint64) int {
  123. // Get the results for this word index
  124. result := results[index]
  125. // Check if there is a result for the given key
  126. if posArr, ok := result[key]; ok {
  127. // Check if any of the positions is at the right place
  128. if index > 0 {
  129. // Check with previous result
  130. for _, pos := range posArr {
  131. // Check if the position array contains the expected next word position
  132. if pos == path[index-1]+1 {
  133. path = append(path, pos)
  134. break
  135. }
  136. // Abort if the expected position cannot be there
  137. if pos > path[index-1] {
  138. return len(path)
  139. }
  140. }
  141. // Do the next iteration if a position was found and
  142. // there are more words in the phrase to match
  143. if len(path) == index+1 && index < len(phraseWords)-1 {
  144. return im.findPhrasePath(key, index+1, path, phraseWords, results)
  145. }
  146. return index + 1
  147. }
  148. // Try every position as start position in the first iteration
  149. for _, pos := range posArr {
  150. path = path[:0]
  151. path = append(path, pos)
  152. // Test if the phrase only contained one word
  153. if len(phraseWords) == 1 {
  154. return 1
  155. }
  156. // Find the rest
  157. ret := im.findPhrasePath(key, 1, path, phraseWords, results)
  158. if ret == len(phraseWords) {
  159. return ret
  160. }
  161. }
  162. }
  163. return len(path)
  164. }
  165. /*
  166. LookupWord finds all nodes where an attribute contains a certain word. This call returns
  167. a map which maps node key to a list of word positions.
  168. */
  169. func (im *IndexManager) LookupWord(attr, word string) (map[string][]uint64, error) {
  170. var s string
  171. if CaseSensitiveWordIndex {
  172. s = word
  173. } else {
  174. s = strings.ToLower(word)
  175. }
  176. entry, err := im.htree.Get([]byte(PrefixAttrWord + attr + s))
  177. if err != nil {
  178. return nil, &GraphError{ErrIndexError, err.Error()}
  179. } else if entry == nil {
  180. return nil, nil
  181. }
  182. ret := make(map[string][]uint64)
  183. for k, l := range entry.(*indexEntry).WordPos {
  184. ret[k] = bitutil.UnpackList(l)
  185. }
  186. return ret, nil
  187. }
  188. /*
  189. LookupValue finds all nodes where an attribute has a certain value. This call
  190. returns a list of node keys.
  191. */
  192. func (im *IndexManager) LookupValue(attr, value string) ([]string, error) {
  193. var entry *indexEntry
  194. var sum [16]byte
  195. if CaseSensitiveWordIndex {
  196. sum = md5.Sum([]byte(value))
  197. } else {
  198. sum = md5.Sum([]byte(strings.ToLower(value)))
  199. }
  200. indexkey := []byte(PrefixAttrHash + attr + string(sum[:16]))
  201. // Retrieve index entry
  202. obj, err := im.htree.Get(indexkey)
  203. if err != nil {
  204. return nil, &GraphError{ErrIndexError, err.Error()}
  205. }
  206. if obj == nil {
  207. return nil, nil
  208. }
  209. entry = obj.(*indexEntry)
  210. ret := make([]string, 0, len(entry.WordPos))
  211. for key := range entry.WordPos {
  212. ret = append(ret, key)
  213. }
  214. sort.StringSlice(ret).Sort()
  215. return ret, nil
  216. }
  217. /*
  218. Count returns the number of found nodes for a given word in a given attribute.
  219. */
  220. func (im *IndexManager) Count(attr, word string) (int, error) {
  221. var s string
  222. if CaseSensitiveWordIndex {
  223. s = word
  224. } else {
  225. s = strings.ToLower(word)
  226. }
  227. entry, err := im.htree.Get([]byte(PrefixAttrWord + attr + s))
  228. if err != nil {
  229. return 0, &GraphError{ErrIndexError, err.Error()}
  230. } else if entry == nil {
  231. return 0, nil
  232. }
  233. return len(entry.(*indexEntry).WordPos), nil
  234. }
  235. /*
  236. updateIndex updates the index for a specific object. Depending on the
  237. new and old arguments being set a given object is either indexed/added
  238. (only new is set), deindexted/removed (only old is set) or reindexted/updated
  239. (new and old are set).
  240. */
  241. func (im *IndexManager) updateIndex(key string, newObj map[string]string,
  242. oldObj map[string]string) error {
  243. attrMap := make(map[string][]byte)
  244. if newObj != nil && oldObj == nil {
  245. // Insert case
  246. for attr := range newObj {
  247. attrMap[attr] = nil
  248. }
  249. } else if newObj == nil && oldObj != nil {
  250. // Remove case
  251. for attr := range oldObj {
  252. attrMap[attr] = nil
  253. }
  254. } else {
  255. // Update case
  256. for attr := range newObj {
  257. attrMap[attr] = nil
  258. }
  259. for attr := range oldObj {
  260. attrMap[attr] = nil
  261. }
  262. }
  263. emptyws := newWordSet(1)
  264. for attr := range attrMap {
  265. var newwords, toadd, oldwords, toremove *wordSet
  266. newval, newok := newObj[attr]
  267. oldval, oldok := oldObj[attr]
  268. // Calculate which words to add or remove
  269. newwords = emptyws
  270. oldwords = emptyws
  271. if newok {
  272. newwords = extractWords(newval)
  273. }
  274. // At this point we have only words to add
  275. toadd = newwords
  276. toremove = emptyws
  277. if oldok {
  278. oldwords = extractWords(oldval)
  279. if !oldwords.Empty() && !newwords.Empty() {
  280. // Here a diff is necessary
  281. toadd = copyWordSet(newwords)
  282. toadd.RemoveAll(oldwords)
  283. toremove = oldwords
  284. toremove.RemoveAll(newwords)
  285. } else {
  286. // Either no new words or no old words
  287. toremove = oldwords
  288. }
  289. }
  290. // Add and remove index entries
  291. for w, p := range toremove.set {
  292. if err := im.removeIndexEntry(key, attr, w, p); err != nil {
  293. return &GraphError{ErrIndexError, err.Error()}
  294. }
  295. }
  296. for w, p := range toadd.set {
  297. if err := im.addIndexEntry(key, attr, w, p); err != nil {
  298. return &GraphError{ErrIndexError, err.Error()}
  299. }
  300. }
  301. // Update hash lookup
  302. if newok && oldok {
  303. // Update hash entry
  304. if err := im.removeIndexHashEntry(key, attr, oldval); err != nil {
  305. return &GraphError{ErrIndexError, err.Error()}
  306. } else if err := im.addIndexHashEntry(key, attr, newval); err != nil {
  307. return &GraphError{ErrIndexError, err.Error()}
  308. }
  309. } else if newok && !oldok {
  310. // Insert hash entry
  311. if err := im.addIndexHashEntry(key, attr, newval); err != nil {
  312. return &GraphError{ErrIndexError, err.Error()}
  313. }
  314. } else if oldok {
  315. // Delete old hash entry
  316. if err := im.removeIndexHashEntry(key, attr, oldval); err != nil {
  317. return &GraphError{ErrIndexError, err.Error()}
  318. }
  319. }
  320. }
  321. return nil
  322. }
  323. /*
  324. addIndexHashEntry add a hash entry from the index. A hash entry stores a whole
  325. value as MD5 sum.
  326. */
  327. func (im *IndexManager) addIndexHashEntry(key string, attr string, value string) error {
  328. var entry *indexEntry
  329. var sum [16]byte
  330. if CaseSensitiveWordIndex {
  331. sum = md5.Sum([]byte(value))
  332. } else {
  333. sum = md5.Sum([]byte(strings.ToLower(value)))
  334. }
  335. indexkey := []byte(PrefixAttrHash + attr + string(sum[:16]))
  336. // Retrieve index entry
  337. obj, err := im.htree.Get(indexkey)
  338. if err != nil {
  339. return err
  340. }
  341. if obj == nil {
  342. entry = &indexEntry{make(map[string]string)}
  343. } else {
  344. entry = obj.(*indexEntry)
  345. }
  346. entry.WordPos[key] = ""
  347. _, err = im.htree.Put(indexkey, entry)
  348. return err
  349. }
  350. /*
  351. removeIndexHashEntry removes a hash entry from the index. A hash entry stores a whole
  352. value as MD5 sum.
  353. */
  354. func (im *IndexManager) removeIndexHashEntry(key string, attr string, value string) error {
  355. var entry *indexEntry
  356. var sum [16]byte
  357. if CaseSensitiveWordIndex {
  358. sum = md5.Sum([]byte(value))
  359. } else {
  360. sum = md5.Sum([]byte(strings.ToLower(value)))
  361. }
  362. indexkey := []byte(PrefixAttrHash + attr + string(sum[:16]))
  363. // Retrieve index entry
  364. obj, err := im.htree.Get(indexkey)
  365. if err != nil {
  366. return err
  367. }
  368. if obj == nil {
  369. return nil
  370. }
  371. entry = obj.(*indexEntry)
  372. delete(entry.WordPos, key)
  373. if len(entry.WordPos) == 0 {
  374. im.htree.Remove(indexkey)
  375. } else {
  376. im.htree.Put(indexkey, entry)
  377. }
  378. return err
  379. }
  380. /*
  381. removeIndexEntry removes an entry from the index.
  382. */
  383. func (im *IndexManager) removeIndexEntry(key string, attr string, word string, pos []uint64) error {
  384. var entry *indexEntry
  385. indexkey := []byte(PrefixAttrWord + attr + word)
  386. // Retrieve index entry
  387. obj, err := im.htree.Get(indexkey)
  388. if err != nil {
  389. return err
  390. }
  391. if obj == nil {
  392. return nil
  393. }
  394. entry = obj.(*indexEntry)
  395. // Remove given pos from existing pos information
  396. if keyentry, ok := entry.WordPos[key]; ok {
  397. keyentrylist := bitutil.UnpackList(keyentry)
  398. res := make([]uint64, 0, len(keyentrylist))
  399. remLookup := make(map[uint64]bool)
  400. for _, item := range pos {
  401. remLookup[item] = true
  402. }
  403. for _, item := range keyentrylist {
  404. if _, ok := remLookup[item]; !ok {
  405. res = append(res, item)
  406. }
  407. }
  408. if len(res) == 0 {
  409. delete(entry.WordPos, key)
  410. } else {
  411. entry.WordPos[key] = bitutil.PackList(res, res[len(res)-1])
  412. }
  413. }
  414. if len(entry.WordPos) == 0 {
  415. _, err = im.htree.Remove(indexkey)
  416. } else {
  417. _, err = im.htree.Put(indexkey, entry)
  418. }
  419. return err
  420. }
  421. /*
  422. addIndexEntry adds an entry to the index.
  423. */
  424. func (im *IndexManager) addIndexEntry(key string, attr string, word string, pos []uint64) error {
  425. var entry *indexEntry
  426. indexkey := []byte(PrefixAttrWord + attr + word)
  427. // Retrieve or create index entry
  428. obj, err := im.htree.Get(indexkey)
  429. if err != nil {
  430. return err
  431. }
  432. if obj == nil {
  433. entry = &indexEntry{make(map[string]string)}
  434. } else {
  435. entry = obj.(*indexEntry)
  436. }
  437. // Create position string
  438. if len(pos) == 0 {
  439. panic("Trying to add index entry without position information")
  440. }
  441. // Mix in given pos with existing pos information
  442. if keyentry, ok := entry.WordPos[key]; ok {
  443. pos = append(bitutil.UnpackList(keyentry), pos...)
  444. sortutil.UInt64s(pos)
  445. pos = removeDuplicates(pos)
  446. }
  447. // Rely on the fact that position arrays are ordered in ascending order
  448. maxpos := pos[len(pos)-1]
  449. // Fill the entry and store it
  450. entry.WordPos[key] = bitutil.PackList(pos, maxpos)
  451. _, err = im.htree.Put(indexkey, entry)
  452. return err
  453. }
  454. /*
  455. Remove all duplicates from a given sorted list.
  456. */
  457. func removeDuplicates(list []uint64) []uint64 {
  458. if len(list) == 0 {
  459. return list
  460. }
  461. res := make([]uint64, 1, len(list))
  462. res[0] = list[0]
  463. last := list[0]
  464. for _, item := range list[1:] {
  465. if item != last {
  466. res = append(res, item)
  467. last = item
  468. }
  469. }
  470. return res
  471. }
  472. /*
  473. String returns a string representation of this index manager.
  474. */
  475. func (im *IndexManager) String() string {
  476. var buf bytes.Buffer
  477. buf.WriteString(fmt.Sprintf("IndexManager: %v\n", im.htree.Location()))
  478. it := hash.NewHTreeIterator(im.htree)
  479. for it.HasNext() {
  480. key, value := it.Next()
  481. posmap := make(map[string][]uint64)
  482. for k, v := range value.(*indexEntry).WordPos {
  483. posmap[k] = bitutil.UnpackList(v)
  484. }
  485. buf.WriteString(fmt.Sprintf(" %v%q %v\n", key[0], string(key[1:]), posmap))
  486. }
  487. return buf.String()
  488. }
  489. /*
  490. extractWords extracts all words from a given string and return a wordSet which contains
  491. all words and their positions.
  492. */
  493. func extractWords(s string) *wordSet {
  494. var text string
  495. if CaseSensitiveWordIndex {
  496. text = s
  497. } else {
  498. text = strings.ToLower(s)
  499. }
  500. initArrCap := int(math.Ceil(float64(len(text)) * 0.01))
  501. if initArrCap < 4 {
  502. initArrCap = 4
  503. }
  504. ws := newWordSet(initArrCap)
  505. var pos uint64
  506. wstart := -1
  507. for i, rune := range text {
  508. if !stringutil.IsAlphaNumeric(string(rune)) && (unicode.IsSpace(rune) || unicode.IsControl(rune) || unicode.IsPunct(rune)) {
  509. if wstart >= 0 {
  510. ws.Add(text[wstart:i], pos+1)
  511. pos++
  512. wstart = -1
  513. }
  514. } else if wstart == -1 {
  515. wstart = i
  516. }
  517. }
  518. if wstart >= 0 {
  519. ws.Add(text[wstart:], pos+1)
  520. }
  521. return ws
  522. }
  523. /*
  524. Internal data structure for sets of words and their positions.
  525. */
  526. type wordSet struct {
  527. set map[string][]uint64 // Map which holds the data
  528. initArrCap int // Initial capacity for the position array
  529. }
  530. /*
  531. newWordSet creates a new word set.
  532. */
  533. func newWordSet(initArrCap int) *wordSet {
  534. return &wordSet{make(map[string][]uint64), initArrCap}
  535. }
  536. /*
  537. copyWordSet creates a new word set from a present one.
  538. */
  539. func copyWordSet(ws *wordSet) *wordSet {
  540. ret := &wordSet{make(map[string][]uint64), ws.initArrCap}
  541. ret.AddAll(ws)
  542. return ret
  543. }
  544. /*
  545. Add adds a word to the word set. Returns true if the word was added and false
  546. if an existing entry was updated.
  547. */
  548. func (ws *wordSet) Add(s string, pos uint64) bool {
  549. v, ok := ws.set[s]
  550. if !ok {
  551. ws.set[s] = make([]uint64, 1, ws.initArrCap)
  552. ws.set[s][0] = pos
  553. } else {
  554. // Make sure the largest entry is always last
  555. l := len(ws.set[s])
  556. if ws.set[s][l-1] < pos {
  557. ws.set[s] = append(v, pos)
  558. } else {
  559. // Make sure there is no double entry
  560. for _, ex := range v {
  561. if ex == pos {
  562. return !ok
  563. }
  564. }
  565. ws.set[s] = append(v, pos)
  566. sortutil.UInt64s(ws.set[s])
  567. }
  568. }
  569. return !ok
  570. }
  571. /*
  572. AddAll adds all words from another word set to this word set.
  573. */
  574. func (ws *wordSet) AddAll(ws2 *wordSet) {
  575. for s, val := range ws2.set {
  576. for _, v := range val {
  577. ws.Add(s, v)
  578. }
  579. }
  580. }
  581. /*
  582. Empty checks if this word set is empty.
  583. */
  584. func (ws *wordSet) Empty() bool {
  585. return len(ws.set) == 0
  586. }
  587. /*
  588. Has checks if this word set has a certain word.
  589. */
  590. func (ws *wordSet) Has(s string) bool {
  591. _, ok := ws.set[s]
  592. return ok
  593. }
  594. /*
  595. Pos returns the positions of a certain word.
  596. */
  597. func (ws *wordSet) Pos(s string) []uint64 {
  598. if pos, ok := ws.set[s]; ok {
  599. return pos
  600. }
  601. return nil
  602. }
  603. /*
  604. Remove removes a word from the word set.
  605. */
  606. func (ws *wordSet) Remove(s string, pos uint64) {
  607. if posArr, ok := ws.set[s]; ok {
  608. // Look for the position
  609. for i, p := range posArr {
  610. if p == pos {
  611. posArr := append(posArr[:i], posArr[i+1:]...)
  612. ws.set[s] = posArr
  613. break
  614. }
  615. }
  616. // Remove the word if no more positions are left
  617. if len(ws.set[s]) == 0 {
  618. delete(ws.set, s)
  619. }
  620. }
  621. }
  622. /*
  623. RemoveAll removes all words from another word set from this word set.
  624. */
  625. func (ws *wordSet) RemoveAll(ws2 *wordSet) {
  626. for s, posArr2 := range ws2.set {
  627. if posArr, ok := ws.set[s]; ok {
  628. j := 0
  629. for i := 0; i < len(posArr2); i++ {
  630. for ; j < len(posArr); j++ {
  631. if posArr[j] == posArr2[i] {
  632. // If a matching entry was found remove it
  633. posArr = append(posArr[:j], posArr[j+1:]...)
  634. ws.set[s] = posArr
  635. break
  636. } else if posArr[j] > posArr2[i] {
  637. // Skip over if a position is not in the current posArr
  638. break
  639. }
  640. }
  641. }
  642. }
  643. // Remove the word if no more positions are left
  644. if len(ws.set[s]) == 0 {
  645. delete(ws.set, s)
  646. }
  647. }
  648. }
  649. /*
  650. String returns a string representation of this word set.
  651. */
  652. func (ws *wordSet) String() string {
  653. var buf bytes.Buffer
  654. c := make([]string, 0, len(ws.set))
  655. for s := range ws.set {
  656. c = append(c, s)
  657. }
  658. sort.StringSlice(c).Sort()
  659. buf.WriteString("WordSet:\n")
  660. for _, k := range c {
  661. buf.WriteString(fmt.Sprintf(" %v %v\n", k, ws.set[k]))
  662. }
  663. return buf.String()
  664. }