1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
//
// Copyright 2020-2022 Sean C Foley
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
package ipaddr
import "github.com/seancfoley/bintree/tree"
type Cached = tree.C
// CachingTrieIterator is an iterator of a tree that allows you to cache an object with the
// lower or upper sub-node of the currently visited node.
// The cached object can be retrieved later when iterating the sub-node.
// That allows you to provide iteration context from a parent to its sub-nodes when iterating,
// but can only be provided with iterators in which parent nodes are visited before their sub-nodes.
// The caching and retrieval is done in constant-time.
type CachingTrieIterator[T any] interface {
IteratorWithRemove[T]
// Note: We could theoretically try to make the cached type generic.
// But the problem with that is that the iterator methods that return them cannot be generic on their own, the whole type would need to specify the cache type.
// The other problem is that even if we could, some callers would not care about the caching behaviour and thus would not want to have to specify a cache type.
// GetCached returns an object previously cached with the current iterated node.
// After Next has returned a node,
// if an object was cached by a call to CacheWithLowerSubNode or CacheWithUpperSubNode
// was called when that node's parent was previously returned by Next,
// then this returns that cached object.
GetCached() Cached
// CacheWithLowerSubNode caches an object with the lower sub-node of the current iterated node.
// After Next has returned a node,
// calling this method caches the provided object with the lower sub-node so that it can
// be retrieved with GetCached when the lower sub-node is visited later.
//
// Returns false if it could not be cached, either because the node has since been removed with a call to Remove,
// because Next has not been called yet, or because there is no lower sub node for the node previously returned by Next.
//
// The caching and retrieval is done in constant time.
CacheWithLowerSubNode(Cached) bool
// CacheWithUpperSubNode caches an object with the upper sub-node of the current iterated node.
// After Next has returned a node,
// calling this method caches the provided object with the upper sub-node so that it can
// be retrieved with GetCached when the upper sub-node is visited later.
//
// Returns false if it could not be cached, either because the node has since been removed with a call to Remove,
// because Next has not been called yet, or because there is no upper sub node for the node previously returned by Next.
//
// The caching and retrieval is done in constant time.
CacheWithUpperSubNode(Cached) bool
}
// addressKeyIterator implements the address key iterator for tries
type addressKeyIterator[T TrieKeyConstraint[T]] struct {
tree.TrieKeyIterator[trieKey[T]]
}
func (iter addressKeyIterator[T]) Next() (t T) {
return iter.TrieKeyIterator.Next().address
}
func (iter addressKeyIterator[T]) Remove() (t T) {
return iter.TrieKeyIterator.Remove().address
}
//
type addrTrieNodeIteratorRem[T TrieKeyConstraint[T], V any] struct {
tree.TrieNodeIteratorRem[trieKey[T], V]
}
func (iter addrTrieNodeIteratorRem[T, V]) Next() *TrieNode[T] {
return toAddressTrieNode[T](iter.TrieNodeIteratorRem.Next())
}
func (iter addrTrieNodeIteratorRem[T, V]) Remove() *TrieNode[T] {
return toAddressTrieNode[T](iter.TrieNodeIteratorRem.Remove())
}
//
type addrTrieNodeIterator[T TrieKeyConstraint[T], V any] struct {
tree.TrieNodeIterator[trieKey[T], V]
}
func (iter addrTrieNodeIterator[T, V]) Next() *TrieNode[T] {
return toAddressTrieNode[T](iter.TrieNodeIterator.Next())
}
//
type cachingAddressTrieNodeIterator[T TrieKeyConstraint[T], V any] struct {
tree.CachingTrieNodeIterator[trieKey[T], V]
}
func (iter cachingAddressTrieNodeIterator[T, V]) Next() *TrieNode[T] {
return toAddressTrieNode[T](iter.CachingTrieNodeIterator.Next())
}
func (iter cachingAddressTrieNodeIterator[T, V]) Remove() *TrieNode[T] {
return toAddressTrieNode[T](iter.CachingTrieNodeIterator.Remove())
}
//////////////////////////////////////////////////////////////////
//////
type associativeAddressTrieNodeIteratorRem[T TrieKeyConstraint[T], V any] struct {
tree.TrieNodeIteratorRem[trieKey[T], V]
}
func (iter associativeAddressTrieNodeIteratorRem[T, V]) Next() *AssociativeTrieNode[T, V] {
return toAssociativeTrieNode[T, V](iter.TrieNodeIteratorRem.Next())
}
func (iter associativeAddressTrieNodeIteratorRem[T, V]) Remove() *AssociativeTrieNode[T, V] {
return toAssociativeTrieNode[T, V](iter.TrieNodeIteratorRem.Remove())
}
//
type associativeAddressTrieNodeIterator[T TrieKeyConstraint[T], V any] struct {
tree.TrieNodeIterator[trieKey[T], V]
}
func (iter associativeAddressTrieNodeIterator[T, V]) Next() *AssociativeTrieNode[T, V] {
return toAssociativeTrieNode[T, V](iter.TrieNodeIterator.Next())
}
//
type cachingAssociativeAddressTrieNodeIteratorX[T TrieKeyConstraint[T], V any] struct {
tree.CachingTrieNodeIterator[trieKey[T], V]
}
func (iter cachingAssociativeAddressTrieNodeIteratorX[T, V]) Next() *AssociativeTrieNode[T, V] {
return toAssociativeTrieNode[T, V](iter.CachingTrieNodeIterator.Next())
}
func (iter cachingAssociativeAddressTrieNodeIteratorX[T, V]) Remove() *AssociativeTrieNode[T, V] {
return toAssociativeTrieNode[T, V](iter.CachingTrieNodeIterator.Remove())
}
//
type emptyIterator[T any] struct{}
func (it emptyIterator[T]) HasNext() bool {
return false
}
func (it emptyIterator[T]) Next() (t T) {
return
}
func nilAddressIterator[T any]() Iterator[T] {
return emptyIterator[T]{}
}
|
