layer_rs/
insert.rs

1use super::*;
2
3/// This requires that the target requirement does not already exist in the tree.
4pub trait Insert<NewReq, MinDepth, Queries, Next>
5where
6    MinDepth: IsNumber,
7    Self::MinDepth: IsNumber,
8{
9    /// Inserts a new requirement into the tree.
10    /// If you want to replace an existing requirement, `remove` it beforehand.
11    fn insert(self, new_req: NewReq) -> Next;
12    type MinDepth;
13    type Queries;
14}
15
16// insert: insert into leaf node
17impl<Req, NewReq> Insert<NewReq, Succ<Zero>, Left<Here>, Node<Req, Node<NewReq, (), ()>, ()>>
18    for Node<Req, (), ()>
19{
20    fn insert(self, new_req: NewReq) -> Node<Req, Node<NewReq, (), ()>, ()> {
21        Node {
22            requirement: self.requirement,
23            prev_left: Node {
24                requirement: new_req,
25                prev_left: (),
26                prev_right: (),
27            },
28            prev_right: (),
29        }
30    }
31
32    type MinDepth = Succ<Zero>;
33    type Queries = Left<Here>;
34}
35
36// insert: insert into left-null tree
37impl<Req, ReqR, NewReq>
38    Insert<
39        NewReq,
40        Succ<Succ<Zero>>,
41        Left<Right<Here>>,
42        Node<Req, Node<NewReq, (), ()>, Node<ReqR, (), ()>>,
43    > for Node<Req, (), Node<ReqR, (), ()>>
44{
45    fn insert(self, new_req: NewReq) -> Node<Req, Node<NewReq, (), ()>, Node<ReqR, (), ()>> {
46        Node {
47            requirement: self.requirement,
48            prev_left: Node {
49                requirement: new_req,
50                prev_left: (),
51                prev_right: (),
52            },
53            prev_right: self.prev_right,
54        }
55    }
56
57    type MinDepth = Succ<Succ<Zero>>;
58    type Queries = Left<Here>;
59}
60
61// insert: insert into right-null tree
62impl<Req, ReqL, NewReq>
63    Insert<
64        NewReq,
65        Succ<Succ<Zero>>,
66        Right<Left<Here>>,
67        Node<Req, Node<ReqL, (), ()>, Node<NewReq, (), ()>>,
68    > for Node<Req, Node<ReqL, (), ()>, ()>
69{
70    fn insert(self, new_req: NewReq) -> Node<Req, Node<ReqL, (), ()>, Node<NewReq, (), ()>> {
71        Node {
72            requirement: self.requirement,
73            prev_left: self.prev_left,
74            prev_right: Node {
75                requirement: new_req,
76                prev_left: (),
77                prev_right: (),
78            },
79        }
80    }
81
82    type MinDepth = Succ<Succ<Zero>>;
83    type Queries = Right<Here>;
84}
85
86// insert: recurse into left subtree twice
87impl<
88    Req,
89    ReqL,
90    SubtreeLL,
91    SubtreeLR,
92    ReqR,
93    SubtreeRL,
94    SubtreeRR,
95    NewReq,
96    NextSubtreeL,
97    PrevQueriesL,
98>
99    Insert<
100        NewReq,
101        <Node<Req, NextSubtreeL, Node<ReqR, SubtreeRL, SubtreeRR>> as MinDepth>::Output,
102        Left<PrevQueriesL>,
103        Node<Req, NextSubtreeL, Node<ReqR, SubtreeRL, SubtreeRR>>,
104    > for Node<Req, Node<ReqL, SubtreeLL, SubtreeLR>, Node<ReqR, SubtreeRL, SubtreeRR>>
105where
106    Node<ReqL, SubtreeLL, SubtreeLR>: MinDepth,
107    Node<ReqR, SubtreeRL, SubtreeRR>: MinDepth,
108    Node<Req, NextSubtreeL, Node<ReqR, SubtreeRL, SubtreeRR>>: MinDepth,
109    NextSubtreeL: MinDepth,
110    Node<ReqL, SubtreeLL, SubtreeLR>:
111        Insert<NewReq, <NextSubtreeL as MinDepth>::Output, PrevQueriesL, NextSubtreeL>,
112    (): LessThan<
113            <Node<ReqL, SubtreeLL, SubtreeLR> as MinDepth>::Output,
114            <Node<ReqR, SubtreeRL, SubtreeRR> as MinDepth>::Output,
115        >,
116{
117    fn insert(self, new_req: NewReq) -> Node<Req, NextSubtreeL, Node<ReqR, SubtreeRL, SubtreeRR>> {
118        Node {
119            requirement: self.requirement,
120            prev_left: self.prev_left.insert(new_req),
121            prev_right: self.prev_right,
122        }
123    }
124
125    type MinDepth =
126        Succ<<Node<Req, NextSubtreeL, Node<ReqR, SubtreeRL, SubtreeRR>> as MinDepth>::Output>;
127    type Queries = Left<PrevQueriesL>;
128}
129
130// insert: recurse into left subtree twice
131impl<
132    Req,
133    ReqL,
134    SubtreeLL,
135    SubtreeLR,
136    ReqR,
137    SubtreeRL,
138    SubtreeRR,
139    NewReq,
140    NextSubtreeR,
141    PrevQueriesR,
142>
143    Insert<
144        NewReq,
145        <Node<Req, Node<ReqL, SubtreeLL, SubtreeLR>, NextSubtreeR> as MinDepth>::Output,
146        Right<PrevQueriesR>,
147        Node<Req, Node<ReqL, SubtreeLL, SubtreeLR>, NextSubtreeR>,
148    > for Node<Req, Node<ReqL, SubtreeLL, SubtreeLR>, Node<ReqR, SubtreeRL, SubtreeRR>>
149where
150    Node<ReqL, SubtreeLL, SubtreeLR>: MinDepth,
151    Node<ReqR, SubtreeRL, SubtreeRR>: MinDepth,
152    Node<Req, Node<ReqL, SubtreeLL, SubtreeLR>, NextSubtreeR>: MinDepth,
153    NextSubtreeR: MinDepth,
154    Node<ReqR, SubtreeRL, SubtreeRR>:
155        Insert<NewReq, <NextSubtreeR as MinDepth>::Output, PrevQueriesR, NextSubtreeR>,
156    (): GreaterThanOrEqual<
157            <Node<ReqL, SubtreeLL, SubtreeLR> as MinDepth>::Output,
158            <Node<ReqR, SubtreeRL, SubtreeRR> as MinDepth>::Output,
159        >,
160{
161    fn insert(self, new_req: NewReq) -> Node<Req, Node<ReqL, SubtreeLL, SubtreeLR>, NextSubtreeR> {
162        Node {
163            requirement: self.requirement,
164            prev_left: self.prev_left,
165            prev_right: self.prev_right.insert(new_req),
166        }
167    }
168
169    type MinDepth =
170        Succ<<Node<Req, Node<ReqL, SubtreeLL, SubtreeLR>, NextSubtreeR> as MinDepth>::Output>;
171    type Queries = Right<PrevQueriesR>;
172}
layer_rs/insert.rs

layer_rs/
insert.rs
