libstdc++: split_join_fn_imps.hpp Source File (original) (raw)

41#ifdef PB_DS_CLASS_C_DEC

43PB_DS_CLASS_T_DEC

44inline void

45PB_DS_CLASS_C_DEC::

46join(PB_DS_CLASS_C_DEC& other)

47{

48 PB_DS_ASSERT_VALID((*this))

49 PB_DS_ASSERT_VALID(other)

50 if (base_type::join_prep(other) == false)

51 {

52 PB_DS_ASSERT_VALID((*this))

53 PB_DS_ASSERT_VALID(other)

54 return;

55 }

57 const node_pointer p_x = other.split_min();

58 join_imp(p_x, other.m_p_head->m_p_parent);

59 base_type::join_finish(other);

60 PB_DS_ASSERT_VALID((*this))

61 PB_DS_ASSERT_VALID(other)

62 }

64PB_DS_CLASS_T_DEC

65void

66PB_DS_CLASS_C_DEC::

67join_imp(node_pointer p_x, node_pointer p_r)

68{

69 _GLIBCXX_DEBUG_ASSERT(p_x != 0);

70 if (p_r != 0)

71 p_r->m_red = false;

73 const size_type h = black_height(base_type::m_p_head->m_p_parent);

74 const size_type other_h = black_height(p_r);

75 node_pointer p_x_l;

76 node_pointer p_x_r;

78 const bool right_join = h >= other_h;

79 if (right_join)

80 {

81 join_pos = find_join_pos_right(base_type::m_p_head->m_p_parent,

82 h, other_h);

83 p_x_l = join_pos.first;

84 p_x_r = p_r;

85 }

86 else

87 {

88 p_x_l = base_type::m_p_head->m_p_parent;

89 base_type::m_p_head->m_p_parent = p_r;

90 if (p_r != 0)

91 p_r->m_p_parent = base_type::m_p_head;

93 join_pos = find_join_pos_left(base_type::m_p_head->m_p_parent,

94 h, other_h);

95 p_x_r = join_pos.first;

96 }

98 node_pointer p_parent = join_pos.second;

99 if (p_parent == base_type::m_p_head)

100 {

101 base_type::m_p_head->m_p_parent = p_x;

102 p_x->m_p_parent = base_type::m_p_head;

103 }

104 else

105 {

106 p_x->m_p_parent = p_parent;

107 if (right_join)

108 p_x->m_p_parent->m_p_right = p_x;

109 else

110 p_x->m_p_parent->m_p_left = p_x;

111 }

112

113 p_x->m_p_left = p_x_l;

114 if (p_x_l != 0)

115 p_x_l->m_p_parent = p_x;

116

117 p_x->m_p_right = p_x_r;

118 if (p_x_r != 0)

119 p_x_r->m_p_parent = p_x;

120

121 p_x->m_red = true;

122

123 base_type::initialize_min_max();

124 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))

125 base_type::update_to_top(p_x, (node_update* )this);

126 insert_fixup(p_x);

127 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))

128}

129

130PB_DS_CLASS_T_DEC

131inline typename PB_DS_CLASS_C_DEC::node_pointer

132PB_DS_CLASS_C_DEC::

133split_min()

134{

135 node_pointer p_min = base_type::m_p_head->m_p_left;

136

137#ifdef _GLIBCXX_DEBUG

138 const node_pointer p_head = base_type::m_p_head;

139 _GLIBCXX_DEBUG_ASSERT(p_min != p_head);

140#endif

141

142 remove_node(p_min);

143 return p_min;

144}

145

146PB_DS_CLASS_T_DEC

148 typename PB_DS_CLASS_C_DEC::node_pointer,

149 typename PB_DS_CLASS_C_DEC::node_pointer>

150PB_DS_CLASS_C_DEC::

151find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r)

152{

153 _GLIBCXX_DEBUG_ASSERT(h_l >= h_r);

154

155 if (base_type::m_p_head->m_p_parent == 0)

156 return (std::make_pair((node_pointer)0, base_type::m_p_head));

157

158 node_pointer p_l_parent = base_type::m_p_head;

159 while (h_l > h_r)

160 {

161 if (p_l->m_red == false)

162 {

163 _GLIBCXX_DEBUG_ASSERT(h_l > 0);

164 --h_l;

165 }

166

167 p_l_parent = p_l;

168 p_l = p_l->m_p_right;

169 }

170

171 if (!is_effectively_black(p_l))

172 {

173 p_l_parent = p_l;

174 p_l = p_l->m_p_right;

175 }

176

177 _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_l));

178 _GLIBCXX_DEBUG_ASSERT(black_height(p_l) == h_r);

179 _GLIBCXX_DEBUG_ASSERT(p_l == 0 || p_l->m_p_parent == p_l_parent);

180 return std::make_pair(p_l, p_l_parent);

181}

182

183PB_DS_CLASS_T_DEC

185 typename PB_DS_CLASS_C_DEC::node_pointer,

186 typename PB_DS_CLASS_C_DEC::node_pointer>

187PB_DS_CLASS_C_DEC::

188find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r)

189{

190 _GLIBCXX_DEBUG_ASSERT(h_r > h_l);

191 if (base_type::m_p_head->m_p_parent == 0)

192 return (std::make_pair((node_pointer)0,

193 base_type::m_p_head));

194 node_pointer p_r_parent = base_type::m_p_head;

195 while (h_r > h_l)

196 {

197 if (p_r->m_red == false)

198 {

199 _GLIBCXX_DEBUG_ASSERT(h_r > 0);

200 --h_r;

201 }

202

203 p_r_parent = p_r;

204 p_r = p_r->m_p_left;

205 }

206

207 if (!is_effectively_black(p_r))

208 {

209 p_r_parent = p_r;

210 p_r = p_r->m_p_left;

211 }

212

213 _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_r));

214 _GLIBCXX_DEBUG_ASSERT(black_height(p_r) == h_l);

215 _GLIBCXX_DEBUG_ASSERT(p_r == 0 || p_r->m_p_parent == p_r_parent);

216 return std::make_pair(p_r, p_r_parent);

217}

218

219PB_DS_CLASS_T_DEC

220inline typename PB_DS_CLASS_C_DEC::size_type

221PB_DS_CLASS_C_DEC::

222black_height(node_pointer p_nd)

223{

224 size_type h = 1;

225 while (p_nd != 0)

226 {

227 if (p_nd->m_red == false)

228 ++h;

229 p_nd = p_nd->m_p_left;

230 }

231 return h;

232}

233

234PB_DS_CLASS_T_DEC

235void

236PB_DS_CLASS_C_DEC::

237split(key_const_reference r_key, PB_DS_CLASS_C_DEC& other)

238{

239 PB_DS_ASSERT_VALID((*this))

240 PB_DS_ASSERT_VALID(other)

241

242 if (base_type::split_prep(r_key, other) == false)

243 {

244 PB_DS_ASSERT_VALID((*this))

245 PB_DS_ASSERT_VALID(other)

246 return;

247 }

248

249 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))

250 PB_DS_STRUCT_ONLY_ASSERT_VALID(other)

251 node_pointer p_nd = this->upper_bound(r_key).m_p_nd;

252 do

253 {

254 node_pointer p_next_nd = p_nd->m_p_parent;

255 if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))

256 split_at_node(p_nd, other);

257

258 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))

259 PB_DS_STRUCT_ONLY_ASSERT_VALID(other)

260 p_nd = p_next_nd;

261 }

262 while (p_nd != base_type::m_p_head);

263

264 base_type::split_finish(other);

265 PB_DS_ASSERT_VALID((*this))

266}

267

268PB_DS_CLASS_T_DEC

269void

270PB_DS_CLASS_C_DEC::

271split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other)

272{

273 _GLIBCXX_DEBUG_ASSERT(p_nd != 0);

274

275 node_pointer p_l = p_nd->m_p_left;

276 node_pointer p_r = p_nd->m_p_right;

277 node_pointer p_parent = p_nd->m_p_parent;

278 if (p_parent == base_type::m_p_head)

279 {

280 base_type::m_p_head->m_p_parent = p_l;

281 if (p_l != 0)

282 {

283 p_l->m_p_parent = base_type::m_p_head;

284 p_l->m_red = false;

285 }

286 }

287 else

288 {

289 if (p_parent->m_p_left == p_nd)

290 p_parent->m_p_left = p_l;

291 else

292 p_parent->m_p_right = p_l;

293

294 if (p_l != 0)

295 p_l->m_p_parent = p_parent;

296

297 this->update_to_top(p_parent, (node_update* )this);

298

299 if (!p_nd->m_red)

300 remove_fixup(p_l, p_parent);

301 }

302

303 base_type::initialize_min_max();

304 other.join_imp(p_nd, p_r);

305 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))

306 PB_DS_STRUCT_ONLY_ASSERT_VALID(other)

307}

308

309#endif

Struct holding two objects of arbitrary type.

_T1 first

The first member.

_T2 second

The second member.