blob: ee7b27f442b02655a202723b1b786072944c3e28 [file] [log] [blame]
sslobodrd046be82019-01-16 10:02:22 -05001package llrb
2
3type ItemIterator func(i Item) bool
4
5//func (t *Tree) Ascend(iterator ItemIterator) {
6// t.AscendGreaterOrEqual(Inf(-1), iterator)
7//}
8
9func (t *LLRB) AscendRange(greaterOrEqual, lessThan Item, iterator ItemIterator) {
10 t.ascendRange(t.root, greaterOrEqual, lessThan, iterator)
11}
12
13func (t *LLRB) ascendRange(h *Node, inf, sup Item, iterator ItemIterator) bool {
14 if h == nil {
15 return true
16 }
17 if !less(h.Item, sup) {
18 return t.ascendRange(h.Left, inf, sup, iterator)
19 }
20 if less(h.Item, inf) {
21 return t.ascendRange(h.Right, inf, sup, iterator)
22 }
23
24 if !t.ascendRange(h.Left, inf, sup, iterator) {
25 return false
26 }
27 if !iterator(h.Item) {
28 return false
29 }
30 return t.ascendRange(h.Right, inf, sup, iterator)
31}
32
33// AscendGreaterOrEqual will call iterator once for each element greater or equal to
34// pivot in ascending order. It will stop whenever the iterator returns false.
35func (t *LLRB) AscendGreaterOrEqual(pivot Item, iterator ItemIterator) {
36 t.ascendGreaterOrEqual(t.root, pivot, iterator)
37}
38
39func (t *LLRB) ascendGreaterOrEqual(h *Node, pivot Item, iterator ItemIterator) bool {
40 if h == nil {
41 return true
42 }
43 if !less(h.Item, pivot) {
44 if !t.ascendGreaterOrEqual(h.Left, pivot, iterator) {
45 return false
46 }
47 if !iterator(h.Item) {
48 return false
49 }
50 }
51 return t.ascendGreaterOrEqual(h.Right, pivot, iterator)
52}
53
54func (t *LLRB) AscendLessThan(pivot Item, iterator ItemIterator) {
55 t.ascendLessThan(t.root, pivot, iterator)
56}
57
58func (t *LLRB) ascendLessThan(h *Node, pivot Item, iterator ItemIterator) bool {
59 if h == nil {
60 return true
61 }
62 if !t.ascendLessThan(h.Left, pivot, iterator) {
63 return false
64 }
65 if !iterator(h.Item) {
66 return false
67 }
68 if less(h.Item, pivot) {
69 return t.ascendLessThan(h.Left, pivot, iterator)
70 }
71 return true
72}
73
74// DescendLessOrEqual will call iterator once for each element less than the
75// pivot in descending order. It will stop whenever the iterator returns false.
76func (t *LLRB) DescendLessOrEqual(pivot Item, iterator ItemIterator) {
77 t.descendLessOrEqual(t.root, pivot, iterator)
78}
79
80func (t *LLRB) descendLessOrEqual(h *Node, pivot Item, iterator ItemIterator) bool {
81 if h == nil {
82 return true
83 }
84 if less(h.Item, pivot) || !less(pivot, h.Item) {
85 if !t.descendLessOrEqual(h.Right, pivot, iterator) {
86 return false
87 }
88 if !iterator(h.Item) {
89 return false
90 }
91 }
92 return t.descendLessOrEqual(h.Left, pivot, iterator)
93}