1package inflect
2
3import (
4	"fmt"
5	"regexp"
6	"strconv"
7	"strings"
8	"unicode"
9	"unicode/utf8"
10)
11
12// used by rulesets
13type Rule struct {
14	suffix      string
15	replacement string
16	exact       bool
17}
18
19// a Ruleset is the config of pluralization rules
20// you can extend the rules with the Add* methods
21type Ruleset struct {
22	uncountables   map[string]bool
23	plurals        []*Rule
24	singulars      []*Rule
25	humans         []*Rule
26	acronyms       []*Rule
27	acronymMatcher *regexp.Regexp
28}
29
30// create a blank ruleset. Unless you are going to
31// build your own rules from scratch you probably
32// won't need this and can just use the defaultRuleset
33// via the global inflect.* methods
34func NewRuleset() *Ruleset {
35	rs := new(Ruleset)
36	rs.uncountables = make(map[string]bool)
37	rs.plurals = make([]*Rule, 0)
38	rs.singulars = make([]*Rule, 0)
39	rs.humans = make([]*Rule, 0)
40	rs.acronyms = make([]*Rule, 0)
41	return rs
42}
43
44// create a new ruleset and load it with the default
45// set of common English pluralization rules
46func NewDefaultRuleset() *Ruleset {
47	rs := NewRuleset()
48	rs.AddPlural("s", "s")
49	rs.AddPlural("testis", "testes")
50	rs.AddPlural("axis", "axes")
51	rs.AddPlural("octopus", "octopi")
52	rs.AddPlural("virus", "viri")
53	rs.AddPlural("octopi", "octopi")
54	rs.AddPlural("viri", "viri")
55	rs.AddPlural("alias", "aliases")
56	rs.AddPlural("status", "statuses")
57	rs.AddPlural("bus", "buses")
58	rs.AddPlural("buffalo", "buffaloes")
59	rs.AddPlural("tomato", "tomatoes")
60	rs.AddPlural("tum", "ta")
61	rs.AddPlural("ium", "ia")
62	rs.AddPlural("ta", "ta")
63	rs.AddPlural("ia", "ia")
64	rs.AddPlural("sis", "ses")
65	rs.AddPlural("lf", "lves")
66	rs.AddPlural("rf", "rves")
67	rs.AddPlural("afe", "aves")
68	rs.AddPlural("bfe", "bves")
69	rs.AddPlural("cfe", "cves")
70	rs.AddPlural("dfe", "dves")
71	rs.AddPlural("efe", "eves")
72	rs.AddPlural("gfe", "gves")
73	rs.AddPlural("hfe", "hves")
74	rs.AddPlural("ife", "ives")
75	rs.AddPlural("jfe", "jves")
76	rs.AddPlural("kfe", "kves")
77	rs.AddPlural("lfe", "lves")
78	rs.AddPlural("mfe", "mves")
79	rs.AddPlural("nfe", "nves")
80	rs.AddPlural("ofe", "oves")
81	rs.AddPlural("pfe", "pves")
82	rs.AddPlural("qfe", "qves")
83	rs.AddPlural("rfe", "rves")
84	rs.AddPlural("sfe", "sves")
85	rs.AddPlural("tfe", "tves")
86	rs.AddPlural("ufe", "uves")
87	rs.AddPlural("vfe", "vves")
88	rs.AddPlural("wfe", "wves")
89	rs.AddPlural("xfe", "xves")
90	rs.AddPlural("yfe", "yves")
91	rs.AddPlural("zfe", "zves")
92	rs.AddPlural("hive", "hives")
93	rs.AddPlural("quy", "quies")
94	rs.AddPlural("by", "bies")
95	rs.AddPlural("cy", "cies")
96	rs.AddPlural("dy", "dies")
97	rs.AddPlural("fy", "fies")
98	rs.AddPlural("gy", "gies")
99	rs.AddPlural("hy", "hies")
100	rs.AddPlural("jy", "jies")
101	rs.AddPlural("ky", "kies")
102	rs.AddPlural("ly", "lies")
103	rs.AddPlural("my", "mies")
104	rs.AddPlural("ny", "nies")
105	rs.AddPlural("py", "pies")
106	rs.AddPlural("qy", "qies")
107	rs.AddPlural("ry", "ries")
108	rs.AddPlural("sy", "sies")
109	rs.AddPlural("ty", "ties")
110	rs.AddPlural("vy", "vies")
111	rs.AddPlural("wy", "wies")
112	rs.AddPlural("xy", "xies")
113	rs.AddPlural("zy", "zies")
114	rs.AddPlural("x", "xes")
115	rs.AddPlural("ch", "ches")
116	rs.AddPlural("ss", "sses")
117	rs.AddPlural("sh", "shes")
118	rs.AddPlural("matrix", "matrices")
119	rs.AddPlural("vertix", "vertices")
120	rs.AddPlural("indix", "indices")
121	rs.AddPlural("matrex", "matrices")
122	rs.AddPlural("vertex", "vertices")
123	rs.AddPlural("index", "indices")
124	rs.AddPlural("mouse", "mice")
125	rs.AddPlural("louse", "lice")
126	rs.AddPlural("mice", "mice")
127	rs.AddPlural("lice", "lice")
128	rs.AddPluralExact("ox", "oxen", true)
129	rs.AddPluralExact("oxen", "oxen", true)
130	rs.AddPluralExact("quiz", "quizzes", true)
131	rs.AddSingular("s", "")
132	rs.AddSingular("news", "news")
133	rs.AddSingular("ta", "tum")
134	rs.AddSingular("ia", "ium")
135	rs.AddSingular("analyses", "analysis")
136	rs.AddSingular("bases", "basis")
137	rs.AddSingular("diagnoses", "diagnosis")
138	rs.AddSingular("parentheses", "parenthesis")
139	rs.AddSingular("prognoses", "prognosis")
140	rs.AddSingular("synopses", "synopsis")
141	rs.AddSingular("theses", "thesis")
142	rs.AddSingular("analyses", "analysis")
143	rs.AddSingular("aves", "afe")
144	rs.AddSingular("bves", "bfe")
145	rs.AddSingular("cves", "cfe")
146	rs.AddSingular("dves", "dfe")
147	rs.AddSingular("eves", "efe")
148	rs.AddSingular("gves", "gfe")
149	rs.AddSingular("hves", "hfe")
150	rs.AddSingular("ives", "ife")
151	rs.AddSingular("jves", "jfe")
152	rs.AddSingular("kves", "kfe")
153	rs.AddSingular("lves", "lfe")
154	rs.AddSingular("mves", "mfe")
155	rs.AddSingular("nves", "nfe")
156	rs.AddSingular("oves", "ofe")
157	rs.AddSingular("pves", "pfe")
158	rs.AddSingular("qves", "qfe")
159	rs.AddSingular("rves", "rfe")
160	rs.AddSingular("sves", "sfe")
161	rs.AddSingular("tves", "tfe")
162	rs.AddSingular("uves", "ufe")
163	rs.AddSingular("vves", "vfe")
164	rs.AddSingular("wves", "wfe")
165	rs.AddSingular("xves", "xfe")
166	rs.AddSingular("yves", "yfe")
167	rs.AddSingular("zves", "zfe")
168	rs.AddSingular("hives", "hive")
169	rs.AddSingular("tives", "tive")
170	rs.AddSingular("lves", "lf")
171	rs.AddSingular("rves", "rf")
172	rs.AddSingular("quies", "quy")
173	rs.AddSingular("bies", "by")
174	rs.AddSingular("cies", "cy")
175	rs.AddSingular("dies", "dy")
176	rs.AddSingular("fies", "fy")
177	rs.AddSingular("gies", "gy")
178	rs.AddSingular("hies", "hy")
179	rs.AddSingular("jies", "jy")
180	rs.AddSingular("kies", "ky")
181	rs.AddSingular("lies", "ly")
182	rs.AddSingular("mies", "my")
183	rs.AddSingular("nies", "ny")
184	rs.AddSingular("pies", "py")
185	rs.AddSingular("qies", "qy")
186	rs.AddSingular("ries", "ry")
187	rs.AddSingular("sies", "sy")
188	rs.AddSingular("ties", "ty")
189	rs.AddSingular("vies", "vy")
190	rs.AddSingular("wies", "wy")
191	rs.AddSingular("xies", "xy")
192	rs.AddSingular("zies", "zy")
193	rs.AddSingular("series", "series")
194	rs.AddSingular("movies", "movie")
195	rs.AddSingular("xes", "x")
196	rs.AddSingular("ches", "ch")
197	rs.AddSingular("sses", "ss")
198	rs.AddSingular("shes", "sh")
199	rs.AddSingular("mice", "mouse")
200	rs.AddSingular("lice", "louse")
201	rs.AddSingular("buses", "bus")
202	rs.AddSingular("oes", "o")
203	rs.AddSingular("shoes", "shoe")
204	rs.AddSingular("crises", "crisis")
205	rs.AddSingular("axes", "axis")
206	rs.AddSingular("testes", "testis")
207	rs.AddSingular("octopi", "octopus")
208	rs.AddSingular("viri", "virus")
209	rs.AddSingular("statuses", "status")
210	rs.AddSingular("aliases", "alias")
211	rs.AddSingularExact("oxen", "ox", true)
212	rs.AddSingular("vertices", "vertex")
213	rs.AddSingular("indices", "index")
214	rs.AddSingular("matrices", "matrix")
215	rs.AddSingularExact("quizzes", "quiz", true)
216	rs.AddSingular("databases", "database")
217	rs.AddIrregular("person", "people")
218	rs.AddIrregular("man", "men")
219	rs.AddIrregular("child", "children")
220	rs.AddIrregular("sex", "sexes")
221	rs.AddIrregular("move", "moves")
222	rs.AddIrregular("zombie", "zombies")
223	rs.AddUncountable("equipment")
224	rs.AddUncountable("information")
225	rs.AddUncountable("rice")
226	rs.AddUncountable("money")
227	rs.AddUncountable("species")
228	rs.AddUncountable("series")
229	rs.AddUncountable("fish")
230	rs.AddUncountable("sheep")
231	rs.AddUncountable("jeans")
232	rs.AddUncountable("police")
233	return rs
234}
235
236func (rs *Ruleset) Uncountables() map[string]bool {
237	return rs.uncountables
238}
239
240// add a pluralization rule
241func (rs *Ruleset) AddPlural(suffix, replacement string) {
242	rs.AddPluralExact(suffix, replacement, false)
243}
244
245// add a pluralization rule with full string match
246func (rs *Ruleset) AddPluralExact(suffix, replacement string, exact bool) {
247	// remove uncountable
248	delete(rs.uncountables, suffix)
249	// create rule
250	r := new(Rule)
251	r.suffix = suffix
252	r.replacement = replacement
253	r.exact = exact
254	// prepend
255	rs.plurals = append([]*Rule{r}, rs.plurals...)
256}
257
258// add a singular rule
259func (rs *Ruleset) AddSingular(suffix, replacement string) {
260	rs.AddSingularExact(suffix, replacement, false)
261}
262
263// same as AddSingular but you can set `exact` to force
264// a full string match
265func (rs *Ruleset) AddSingularExact(suffix, replacement string, exact bool) {
266	// remove from uncountable
267	delete(rs.uncountables, suffix)
268	// create rule
269	r := new(Rule)
270	r.suffix = suffix
271	r.replacement = replacement
272	r.exact = exact
273	rs.singulars = append([]*Rule{r}, rs.singulars...)
274}
275
276// Human rules are applied by humanize to show more friendly
277// versions of words
278func (rs *Ruleset) AddHuman(suffix, replacement string) {
279	r := new(Rule)
280	r.suffix = suffix
281	r.replacement = replacement
282	rs.humans = append([]*Rule{r}, rs.humans...)
283}
284
285// Add any inconsistant pluralizing/sinularizing rules
286// to the set here.
287func (rs *Ruleset) AddIrregular(singular, plural string) {
288	delete(rs.uncountables, singular)
289	delete(rs.uncountables, plural)
290	rs.AddPlural(singular, plural)
291	rs.AddPlural(plural, plural)
292	rs.AddSingular(plural, singular)
293}
294
295// if you use acronym you may need to add them to the ruleset
296// to prevent Underscored words of things like "HTML" coming out
297// as "h_t_m_l"
298func (rs *Ruleset) AddAcronym(word string) {
299	r := new(Rule)
300	r.suffix = word
301	r.replacement = rs.Titleize(strings.ToLower(word))
302	rs.acronyms = append(rs.acronyms, r)
303}
304
305// add a word to this ruleset that has the same singular and plural form
306// for example: "rice"
307func (rs *Ruleset) AddUncountable(word string) {
308	rs.uncountables[strings.ToLower(word)] = true
309}
310
311func (rs *Ruleset) isUncountable(word string) bool {
312	// handle multiple words by using the last one
313	words := strings.Split(word, " ")
314	if _, exists := rs.uncountables[strings.ToLower(words[len(words)-1])]; exists {
315		return true
316	}
317	return false
318}
319
320// returns the plural form of a singular word
321func (rs *Ruleset) Pluralize(word string) string {
322	if len(word) == 0 {
323		return word
324	}
325	if rs.isUncountable(word) {
326		return word
327	}
328	for _, rule := range rs.plurals {
329		if rule.exact {
330			if word == rule.suffix {
331				return rule.replacement
332			}
333		} else {
334			if strings.HasSuffix(word, rule.suffix) {
335				return replaceLast(word, rule.suffix, rule.replacement)
336			}
337		}
338	}
339	return word + "s"
340}
341
342// returns the singular form of a plural word
343func (rs *Ruleset) Singularize(word string) string {
344	if len(word) == 0 {
345		return word
346	}
347	if rs.isUncountable(word) {
348		return word
349	}
350	for _, rule := range rs.singulars {
351		if rule.exact {
352			if word == rule.suffix {
353				return rule.replacement
354			}
355		} else {
356			if strings.HasSuffix(word, rule.suffix) {
357				return replaceLast(word, rule.suffix, rule.replacement)
358			}
359		}
360	}
361	return word
362}
363
364// uppercase first character
365func (rs *Ruleset) Capitalize(word string) string {
366	return strings.ToUpper(word[:1]) + word[1:]
367}
368
369// "dino_party" -> "DinoParty"
370func (rs *Ruleset) Camelize(word string) string {
371	words := splitAtCaseChangeWithTitlecase(word)
372	return strings.Join(words, "")
373}
374
375// same as Camelcase but with first letter downcased
376func (rs *Ruleset) CamelizeDownFirst(word string) string {
377	word = Camelize(word)
378	return strings.ToLower(word[:1]) + word[1:]
379}
380
381// Captitilize every word in sentance "hello there" -> "Hello There"
382func (rs *Ruleset) Titleize(word string) string {
383	words := splitAtCaseChangeWithTitlecase(word)
384	return strings.Join(words, " ")
385}
386
387func (rs *Ruleset) safeCaseAcronyms(word string) string {
388	// convert an acroymn like HTML into Html
389	for _, rule := range rs.acronyms {
390		word = strings.Replace(word, rule.suffix, rule.replacement, -1)
391	}
392	return word
393}
394
395func (rs *Ruleset) seperatedWords(word, sep string) string {
396	word = rs.safeCaseAcronyms(word)
397	words := splitAtCaseChange(word)
398	return strings.Join(words, sep)
399}
400
401// lowercase underscore version "BigBen" -> "big_ben"
402func (rs *Ruleset) Underscore(word string) string {
403	return rs.seperatedWords(word, "_")
404}
405
406// First letter of sentance captitilized
407// Uses custom friendly replacements via AddHuman()
408func (rs *Ruleset) Humanize(word string) string {
409	word = replaceLast(word, "_id", "") // strip foreign key kinds
410	// replace and strings in humans list
411	for _, rule := range rs.humans {
412		word = strings.Replace(word, rule.suffix, rule.replacement, -1)
413	}
414	sentance := rs.seperatedWords(word, " ")
415	return strings.ToUpper(sentance[:1]) + sentance[1:]
416}
417
418// an underscored foreign key name "Person" -> "person_id"
419func (rs *Ruleset) ForeignKey(word string) string {
420	return rs.Underscore(rs.Singularize(word)) + "_id"
421}
422
423// a foreign key (with an underscore) "Person" -> "personid"
424func (rs *Ruleset) ForeignKeyCondensed(word string) string {
425	return rs.Underscore(word) + "id"
426}
427
428// Rails style pluralized table names: "SuperPerson" -> "super_people"
429func (rs *Ruleset) Tableize(word string) string {
430	return rs.Pluralize(rs.Underscore(rs.Typeify(word)))
431}
432
433var notUrlSafe *regexp.Regexp = regexp.MustCompile(`[^\w\d\-_ ]`)
434
435// param safe dasherized names like "my-param"
436func (rs *Ruleset) Parameterize(word string) string {
437	return ParameterizeJoin(word, "-")
438}
439
440// param safe dasherized names with custom seperator
441func (rs *Ruleset) ParameterizeJoin(word, sep string) string {
442	word = strings.ToLower(word)
443	word = rs.Asciify(word)
444	word = notUrlSafe.ReplaceAllString(word, "")
445	word = strings.Replace(word, " ", sep, -1)
446	if len(sep) > 0 {
447		squash, err := regexp.Compile(sep + "+")
448		if err == nil {
449			word = squash.ReplaceAllString(word, sep)
450		}
451	}
452	word = strings.Trim(word, sep+" ")
453	return word
454}
455
456var lookalikes map[string]*regexp.Regexp = map[string]*regexp.Regexp{
457	"A":  regexp.MustCompile(`À|Á|Â|Ã|Ä|Å`),
458	"AE": regexp.MustCompile(`Æ`),
459	"C":  regexp.MustCompile(`Ç`),
460	"E":  regexp.MustCompile(`È|É|Ê|Ë`),
461	"G":  regexp.MustCompile(`Ğ`),
462	"I":  regexp.MustCompile(`Ì|Í|Î|Ï|İ`),
463	"N":  regexp.MustCompile(`Ñ`),
464	"O":  regexp.MustCompile(`Ò|Ó|Ô|Õ|Ö|Ø`),
465	"S":  regexp.MustCompile(`Ş`),
466	"U":  regexp.MustCompile(`Ù|Ú|Û|Ü`),
467	"Y":  regexp.MustCompile(`Ý`),
468	"ss": regexp.MustCompile(`ß`),
469	"a":  regexp.MustCompile(`à|á|â|ã|ä|å`),
470	"ae": regexp.MustCompile(`æ`),
471	"c":  regexp.MustCompile(`ç`),
472	"e":  regexp.MustCompile(`è|é|ê|ë`),
473	"g":  regexp.MustCompile(`ğ`),
474	"i":  regexp.MustCompile(`ì|í|î|ï|ı`),
475	"n":  regexp.MustCompile(`ñ`),
476	"o":  regexp.MustCompile(`ò|ó|ô|õ|ö|ø`),
477	"s":  regexp.MustCompile(`ş`),
478	"u":  regexp.MustCompile(`ù|ú|û|ü|ũ|ū|ŭ|ů|ű|ų`),
479	"y":  regexp.MustCompile(`ý|ÿ`),
480}
481
482// transforms latin characters like é -> e
483func (rs *Ruleset) Asciify(word string) string {
484	for repl, regex := range lookalikes {
485		word = regex.ReplaceAllString(word, repl)
486	}
487	return word
488}
489
490var tablePrefix *regexp.Regexp = regexp.MustCompile(`^[^.]*\.`)
491
492// "something_like_this" -> "SomethingLikeThis"
493func (rs *Ruleset) Typeify(word string) string {
494	word = tablePrefix.ReplaceAllString(word, "")
495	return rs.Camelize(rs.Singularize(word))
496}
497
498// "SomeText" -> "some-text"
499func (rs *Ruleset) Dasherize(word string) string {
500	return rs.seperatedWords(word, "-")
501}
502
503// "1031" -> "1031st"
504func (rs *Ruleset) Ordinalize(str string) string {
505	number, err := strconv.Atoi(str)
506	if err != nil {
507		return str
508	}
509	switch abs(number) % 100 {
510	case 11, 12, 13:
511		return fmt.Sprintf("%dth", number)
512	default:
513		switch abs(number) % 10 {
514		case 1:
515			return fmt.Sprintf("%dst", number)
516		case 2:
517			return fmt.Sprintf("%dnd", number)
518		case 3:
519			return fmt.Sprintf("%drd", number)
520		}
521	}
522	return fmt.Sprintf("%dth", number)
523}
524
525/////////////////////////////////////////
526// the default global ruleset
527//////////////////////////////////////////
528
529var defaultRuleset *Ruleset
530
531func init() {
532	defaultRuleset = NewDefaultRuleset()
533}
534
535func Uncountables() map[string]bool {
536	return defaultRuleset.Uncountables()
537}
538
539func AddPlural(suffix, replacement string) {
540	defaultRuleset.AddPlural(suffix, replacement)
541}
542
543func AddSingular(suffix, replacement string) {
544	defaultRuleset.AddSingular(suffix, replacement)
545}
546
547func AddHuman(suffix, replacement string) {
548	defaultRuleset.AddHuman(suffix, replacement)
549}
550
551func AddIrregular(singular, plural string) {
552	defaultRuleset.AddIrregular(singular, plural)
553}
554
555func AddAcronym(word string) {
556	defaultRuleset.AddAcronym(word)
557}
558
559func AddUncountable(word string) {
560	defaultRuleset.AddUncountable(word)
561}
562
563func Pluralize(word string) string {
564	return defaultRuleset.Pluralize(word)
565}
566
567func Singularize(word string) string {
568	return defaultRuleset.Singularize(word)
569}
570
571func Capitalize(word string) string {
572	return defaultRuleset.Capitalize(word)
573}
574
575func Camelize(word string) string {
576	return defaultRuleset.Camelize(word)
577}
578
579func CamelizeDownFirst(word string) string {
580	return defaultRuleset.CamelizeDownFirst(word)
581}
582
583func Titleize(word string) string {
584	return defaultRuleset.Titleize(word)
585}
586
587func Underscore(word string) string {
588	return defaultRuleset.Underscore(word)
589}
590
591func Humanize(word string) string {
592	return defaultRuleset.Humanize(word)
593}
594
595func ForeignKey(word string) string {
596	return defaultRuleset.ForeignKey(word)
597}
598
599func ForeignKeyCondensed(word string) string {
600	return defaultRuleset.ForeignKeyCondensed(word)
601}
602
603func Tableize(word string) string {
604	return defaultRuleset.Tableize(word)
605}
606
607func Parameterize(word string) string {
608	return defaultRuleset.Parameterize(word)
609}
610
611func ParameterizeJoin(word, sep string) string {
612	return defaultRuleset.ParameterizeJoin(word, sep)
613}
614
615func Typeify(word string) string {
616	return defaultRuleset.Typeify(word)
617}
618
619func Dasherize(word string) string {
620	return defaultRuleset.Dasherize(word)
621}
622
623func Ordinalize(word string) string {
624	return defaultRuleset.Ordinalize(word)
625}
626
627func Asciify(word string) string {
628	return defaultRuleset.Asciify(word)
629}
630
631// helper funcs
632
633func reverse(s string) string {
634	o := make([]rune, utf8.RuneCountInString(s))
635	i := len(o)
636	for _, c := range s {
637		i--
638		o[i] = c
639	}
640	return string(o)
641}
642
643func isSpacerChar(c rune) bool {
644	switch {
645	case c == rune("_"[0]):
646		return true
647	case c == rune(" "[0]):
648		return true
649	case c == rune(":"[0]):
650		return true
651	case c == rune("-"[0]):
652		return true
653	}
654	return false
655}
656
657func splitAtCaseChange(s string) []string {
658	words := make([]string, 0)
659	word := make([]rune, 0)
660	for _, c := range s {
661		spacer := isSpacerChar(c)
662		if len(word) > 0 {
663			if unicode.IsUpper(c) || spacer {
664				words = append(words, string(word))
665				word = make([]rune, 0)
666			}
667		}
668		if !spacer {
669			word = append(word, unicode.ToLower(c))
670		}
671	}
672	words = append(words, string(word))
673	return words
674}
675
676func splitAtCaseChangeWithTitlecase(s string) []string {
677	words := make([]string, 0)
678	word := make([]rune, 0)
679	for _, c := range s {
680		spacer := isSpacerChar(c)
681		if len(word) > 0 {
682			if unicode.IsUpper(c) || spacer {
683				words = append(words, string(word))
684				word = make([]rune, 0)
685			}
686		}
687		if !spacer {
688			if len(word) > 0 {
689				word = append(word, unicode.ToLower(c))
690			} else {
691				word = append(word, unicode.ToUpper(c))
692			}
693		}
694	}
695	words = append(words, string(word))
696	return words
697}
698
699func replaceLast(s, match, repl string) string {
700	// reverse strings
701	srev := reverse(s)
702	mrev := reverse(match)
703	rrev := reverse(repl)
704	// match first and reverse back
705	return reverse(strings.Replace(srev, mrev, rrev, 1))
706}
707
708func abs(x int) int {
709	if x < 0 {
710		return -x
711	}
712	return x
713}
714