1 // RB tree implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
32 * Copyright (c) 1996,1997
33 * Silicon Graphics Computer Systems, Inc.
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation. Silicon Graphics makes no
40 * representations about the suitability of this software for any
41 * purpose. It is provided "as is" without express or implied warranty.
45 * Hewlett-Packard Company
47 * Permission to use, copy, modify, distribute and sell this software
48 * and its documentation for any purpose is hereby granted without fee,
49 * provided that the above copyright notice appear in all copies and
50 * that both that copyright notice and this permission notice appear
51 * in supporting documentation. Hewlett-Packard Company makes no
52 * representations about the suitability of this software for any
53 * purpose. It is provided "as is" without express or implied warranty.
59 * This is an internal header file, included by other library headers.
60 * You should not attempt to use it directly.
63 #ifndef __GLIBCPP_INTERNAL_TREE_H
64 #define __GLIBCPP_INTERNAL_TREE_H
68 Red-black tree class, designed for use in implementing STL
69 associative containers (set, multiset, map, and multimap). The
70 insertion and deletion algorithms are based on those in Cormen,
71 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
74 (1) the header cell is maintained with links not only to the root
75 but also to the leftmost node of the tree, to enable constant time
76 begin(), and to the rightmost node of the tree, to enable linear time
77 performance when used with the generic set algorithms (set_union,
80 (2) when a node being deleted has two children its successor node is
81 relinked into its place, rather than copied, so that the only
82 iterators invalidated are those referring to the deleted node.
86 #include <bits/stl_algobase.h>
87 #include <bits/allocator.h>
88 #include <bits/stl_construct.h>
89 #include <bits/stl_function.h>
93 enum _Rb_tree_color
{ _S_red
= false, _S_black
= true };
95 struct _Rb_tree_node_base
97 typedef _Rb_tree_node_base
* _Base_ptr
;
99 _Rb_tree_color _M_color
;
105 _S_minimum(_Base_ptr __x
)
107 while (__x
->_M_left
!= 0) __x
= __x
->_M_left
;
112 _S_maximum(_Base_ptr __x
)
114 while (__x
->_M_right
!= 0) __x
= __x
->_M_right
;
119 template<typename _Val
>
120 struct _Rb_tree_node
: public _Rb_tree_node_base
122 typedef _Rb_tree_node
<_Val
>* _Link_type
;
126 struct _Rb_tree_base_iterator
128 typedef _Rb_tree_node_base::_Base_ptr _Base_ptr
;
129 typedef bidirectional_iterator_tag iterator_category
;
130 typedef ptrdiff_t difference_type
;
137 if (_M_node
->_M_right
!= 0)
139 _M_node
= _M_node
->_M_right
;
140 while (_M_node
->_M_left
!= 0)
141 _M_node
= _M_node
->_M_left
;
145 _Base_ptr __y
= _M_node
->_M_parent
;
146 while (_M_node
== __y
->_M_right
)
149 __y
= __y
->_M_parent
;
151 if (_M_node
->_M_right
!= __y
)
159 if (_M_node
->_M_color
== _S_red
160 && _M_node
->_M_parent
->_M_parent
== _M_node
)
161 _M_node
= _M_node
->_M_right
;
162 else if (_M_node
->_M_left
!= 0)
164 _Base_ptr __y
= _M_node
->_M_left
;
165 while (__y
->_M_right
!= 0)
171 _Base_ptr __y
= _M_node
->_M_parent
;
172 while (_M_node
== __y
->_M_left
)
175 __y
= __y
->_M_parent
;
182 template<typename _Val
, typename _Ref
, typename _Ptr
>
183 struct _Rb_tree_iterator
: public _Rb_tree_base_iterator
185 typedef _Val value_type
;
186 typedef _Ref reference
;
187 typedef _Ptr pointer
;
188 typedef _Rb_tree_iterator
<_Val
, _Val
&, _Val
*> iterator
;
189 typedef _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>
191 typedef _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
> _Self
;
192 typedef _Rb_tree_node
<_Val
>* _Link_type
;
194 _Rb_tree_iterator() {}
195 _Rb_tree_iterator(_Link_type __x
) { _M_node
= __x
; }
196 _Rb_tree_iterator(const iterator
& __it
) { _M_node
= __it
._M_node
; }
199 operator*() const { return _Link_type(_M_node
)->_M_value_field
; }
202 operator->() const { return &(operator*()); }
220 operator--() { _M_decrement(); return *this; }
231 template<typename _Val
, typename _Ref
, typename _Ptr
>
233 operator==(const _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
>& __x
,
234 const _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
>& __y
)
235 { return __x
._M_node
== __y
._M_node
; }
237 template<typename _Val
>
239 operator==(const _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>& __x
,
240 const _Rb_tree_iterator
<_Val
, _Val
&, _Val
*>& __y
)
241 { return __x
._M_node
== __y
._M_node
; }
243 template<typename _Val
>
245 operator==(const _Rb_tree_iterator
<_Val
, _Val
&, _Val
*>& __x
,
246 const _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>& __y
)
247 { return __x
._M_node
== __y
._M_node
; }
249 template<typename _Val
, typename _Ref
, typename _Ptr
>
251 operator!=(const _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
>& __x
,
252 const _Rb_tree_iterator
<_Val
, _Ref
, _Ptr
>& __y
)
253 { return __x
._M_node
!= __y
._M_node
; }
255 template<typename _Val
>
257 operator!=(const _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>& __x
,
258 const _Rb_tree_iterator
<_Val
, _Val
&, _Val
*>& __y
)
259 { return __x
._M_node
!= __y
._M_node
; }
261 template<typename _Val
>
263 operator!=(const _Rb_tree_iterator
<_Val
, _Val
&, _Val
*>& __x
,
264 const _Rb_tree_iterator
<_Val
, const _Val
&, const _Val
*>& __y
)
265 { return __x
._M_node
!= __y
._M_node
; }
268 _Rb_tree_rotate_left(_Rb_tree_node_base
* __x
, _Rb_tree_node_base
*& __root
)
270 _Rb_tree_node_base
* __y
= __x
->_M_right
;
271 __x
->_M_right
= __y
->_M_left
;
272 if (__y
->_M_left
!=0)
273 __y
->_M_left
->_M_parent
= __x
;
274 __y
->_M_parent
= __x
->_M_parent
;
278 else if (__x
== __x
->_M_parent
->_M_left
)
279 __x
->_M_parent
->_M_left
= __y
;
281 __x
->_M_parent
->_M_right
= __y
;
283 __x
->_M_parent
= __y
;
287 _Rb_tree_rotate_right(_Rb_tree_node_base
* __x
, _Rb_tree_node_base
*& __root
)
289 _Rb_tree_node_base
* __y
= __x
->_M_left
;
290 __x
->_M_left
= __y
->_M_right
;
291 if (__y
->_M_right
!= 0)
292 __y
->_M_right
->_M_parent
= __x
;
293 __y
->_M_parent
= __x
->_M_parent
;
297 else if (__x
== __x
->_M_parent
->_M_right
)
298 __x
->_M_parent
->_M_right
= __y
;
300 __x
->_M_parent
->_M_left
= __y
;
302 __x
->_M_parent
= __y
;
306 _Rb_tree_rebalance(_Rb_tree_node_base
* __x
, _Rb_tree_node_base
*& __root
)
308 __x
->_M_color
= _S_red
;
310 && __x
->_M_parent
->_M_color
== _S_red
)
312 if (__x
->_M_parent
== __x
->_M_parent
->_M_parent
->_M_left
)
314 _Rb_tree_node_base
* __y
= __x
->_M_parent
->_M_parent
->_M_right
;
315 if (__y
&& __y
->_M_color
== _S_red
)
317 __x
->_M_parent
->_M_color
= _S_black
;
318 __y
->_M_color
= _S_black
;
319 __x
->_M_parent
->_M_parent
->_M_color
= _S_red
;
320 __x
= __x
->_M_parent
->_M_parent
;
324 if (__x
== __x
->_M_parent
->_M_right
)
326 __x
= __x
->_M_parent
;
327 _Rb_tree_rotate_left(__x
, __root
);
329 __x
->_M_parent
->_M_color
= _S_black
;
330 __x
->_M_parent
->_M_parent
->_M_color
= _S_red
;
331 _Rb_tree_rotate_right(__x
->_M_parent
->_M_parent
, __root
);
336 _Rb_tree_node_base
* __y
= __x
->_M_parent
->_M_parent
->_M_left
;
337 if (__y
&& __y
->_M_color
== _S_red
)
339 __x
->_M_parent
->_M_color
= _S_black
;
340 __y
->_M_color
= _S_black
;
341 __x
->_M_parent
->_M_parent
->_M_color
= _S_red
;
342 __x
= __x
->_M_parent
->_M_parent
;
346 if (__x
== __x
->_M_parent
->_M_left
)
348 __x
= __x
->_M_parent
;
349 _Rb_tree_rotate_right(__x
, __root
);
351 __x
->_M_parent
->_M_color
= _S_black
;
352 __x
->_M_parent
->_M_parent
->_M_color
= _S_red
;
353 _Rb_tree_rotate_left(__x
->_M_parent
->_M_parent
, __root
);
357 __root
->_M_color
= _S_black
;
360 inline _Rb_tree_node_base
*
361 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base
* __z
,
362 _Rb_tree_node_base
*& __root
,
363 _Rb_tree_node_base
*& __leftmost
,
364 _Rb_tree_node_base
*& __rightmost
)
366 _Rb_tree_node_base
* __y
= __z
;
367 _Rb_tree_node_base
* __x
= 0;
368 _Rb_tree_node_base
* __x_parent
= 0;
369 if (__y
->_M_left
== 0) // __z has at most one non-null child. y == z.
370 __x
= __y
->_M_right
; // __x might be null.
372 if (__y
->_M_right
== 0) // __z has exactly one non-null child. y == z.
373 __x
= __y
->_M_left
; // __x is not null.
376 // __z has two non-null children. Set __y to
377 __y
= __y
->_M_right
; // __z's successor. __x might be null.
378 while (__y
->_M_left
!= 0)
384 // relink y in place of z. y is z's successor
385 __z
->_M_left
->_M_parent
= __y
;
386 __y
->_M_left
= __z
->_M_left
;
387 if (__y
!= __z
->_M_right
)
389 __x_parent
= __y
->_M_parent
;
390 if (__x
) __x
->_M_parent
= __y
->_M_parent
;
391 __y
->_M_parent
->_M_left
= __x
; // __y must be a child of _M_left
392 __y
->_M_right
= __z
->_M_right
;
393 __z
->_M_right
->_M_parent
= __y
;
399 else if (__z
->_M_parent
->_M_left
== __z
)
400 __z
->_M_parent
->_M_left
= __y
;
402 __z
->_M_parent
->_M_right
= __y
;
403 __y
->_M_parent
= __z
->_M_parent
;
404 std::swap(__y
->_M_color
, __z
->_M_color
);
406 // __y now points to node to be actually deleted
410 __x_parent
= __y
->_M_parent
;
412 __x
->_M_parent
= __y
->_M_parent
;
416 if (__z
->_M_parent
->_M_left
== __z
)
417 __z
->_M_parent
->_M_left
= __x
;
419 __z
->_M_parent
->_M_right
= __x
;
420 if (__leftmost
== __z
)
421 if (__z
->_M_right
== 0) // __z->_M_left must be null also
422 __leftmost
= __z
->_M_parent
;
423 // makes __leftmost == _M_header if __z == __root
425 __leftmost
= _Rb_tree_node_base::_S_minimum(__x
);
426 if (__rightmost
== __z
)
427 if (__z
->_M_left
== 0) // __z->_M_right must be null also
428 __rightmost
= __z
->_M_parent
;
429 // makes __rightmost == _M_header if __z == __root
430 else // __x == __z->_M_left
431 __rightmost
= _Rb_tree_node_base::_S_maximum(__x
);
433 if (__y
->_M_color
!= _S_red
)
435 while (__x
!= __root
&& (__x
== 0 || __x
->_M_color
== _S_black
))
436 if (__x
== __x_parent
->_M_left
)
438 _Rb_tree_node_base
* __w
= __x_parent
->_M_right
;
439 if (__w
->_M_color
== _S_red
)
441 __w
->_M_color
= _S_black
;
442 __x_parent
->_M_color
= _S_red
;
443 _Rb_tree_rotate_left(__x_parent
, __root
);
444 __w
= __x_parent
->_M_right
;
446 if ((__w
->_M_left
== 0 ||
447 __w
->_M_left
->_M_color
== _S_black
) &&
448 (__w
->_M_right
== 0 ||
449 __w
->_M_right
->_M_color
== _S_black
))
451 __w
->_M_color
= _S_red
;
453 __x_parent
= __x_parent
->_M_parent
;
457 if (__w
->_M_right
== 0
458 || __w
->_M_right
->_M_color
== _S_black
)
460 __w
->_M_left
->_M_color
= _S_black
;
461 __w
->_M_color
= _S_red
;
462 _Rb_tree_rotate_right(__w
, __root
);
463 __w
= __x_parent
->_M_right
;
465 __w
->_M_color
= __x_parent
->_M_color
;
466 __x_parent
->_M_color
= _S_black
;
468 __w
->_M_right
->_M_color
= _S_black
;
469 _Rb_tree_rotate_left(__x_parent
, __root
);
475 // same as above, with _M_right <-> _M_left.
476 _Rb_tree_node_base
* __w
= __x_parent
->_M_left
;
477 if (__w
->_M_color
== _S_red
)
479 __w
->_M_color
= _S_black
;
480 __x_parent
->_M_color
= _S_red
;
481 _Rb_tree_rotate_right(__x_parent
, __root
);
482 __w
= __x_parent
->_M_left
;
484 if ((__w
->_M_right
== 0 ||
485 __w
->_M_right
->_M_color
== _S_black
) &&
486 (__w
->_M_left
== 0 ||
487 __w
->_M_left
->_M_color
== _S_black
))
489 __w
->_M_color
= _S_red
;
491 __x_parent
= __x_parent
->_M_parent
;
495 if (__w
->_M_left
== 0 || __w
->_M_left
->_M_color
== _S_black
)
497 __w
->_M_right
->_M_color
= _S_black
;
498 __w
->_M_color
= _S_red
;
499 _Rb_tree_rotate_left(__w
, __root
);
500 __w
= __x_parent
->_M_left
;
502 __w
->_M_color
= __x_parent
->_M_color
;
503 __x_parent
->_M_color
= _S_black
;
505 __w
->_M_left
->_M_color
= _S_black
;
506 _Rb_tree_rotate_right(__x_parent
, __root
);
510 if (__x
) __x
->_M_color
= _S_black
;
515 // Base class to encapsulate the differences between old SGI-style
516 // allocators and standard-conforming allocators. In order to avoid
517 // having an empty base class, we arbitrarily move one of rb_tree's
518 // data members into the base class.
520 // _Base for general standard-conforming allocators.
521 template<typename _Tp
, typename _Alloc
, bool _S_instanceless
>
522 class _Rb_tree_alloc_base
525 typedef typename _Alloc_traits
<_Tp
, _Alloc
>::allocator_type allocator_type
;
528 get_allocator() const { return _M_node_allocator
; }
530 _Rb_tree_alloc_base(const allocator_type
& __a
)
531 : _M_node_allocator(__a
), _M_header(0) {}
534 typename _Alloc_traits
<_Rb_tree_node
<_Tp
>, _Alloc
>::allocator_type
537 _Rb_tree_node
<_Tp
>* _M_header
;
540 _M_get_node() { return _M_node_allocator
.allocate(1); }
543 _M_put_node(_Rb_tree_node
<_Tp
>* __p
)
544 { _M_node_allocator
.deallocate(__p
, 1); }
547 // Specialization for instanceless allocators.
548 template<typename _Tp
, typename _Alloc
>
549 class _Rb_tree_alloc_base
<_Tp
, _Alloc
, true>
552 typedef typename _Alloc_traits
<_Tp
, _Alloc
>::allocator_type allocator_type
;
553 allocator_type
get_allocator() const { return allocator_type(); }
555 _Rb_tree_alloc_base(const allocator_type
&) : _M_header(0) {}
558 _Rb_tree_node
<_Tp
>* _M_header
;
560 typedef typename _Alloc_traits
<_Rb_tree_node
<_Tp
>, _Alloc
>::_Alloc_type
564 _M_get_node() { return _Alloc_type::allocate(1); }
567 _M_put_node(_Rb_tree_node
<_Tp
>* __p
) { _Alloc_type::deallocate(__p
, 1); }
570 template<typename _Tp
, typename _Alloc
>
571 struct _Rb_tree_base
: public _Rb_tree_alloc_base
<_Tp
, _Alloc
,
572 _Alloc_traits
<_Tp
, _Alloc
>::_S_instanceless
>
574 typedef _Rb_tree_alloc_base
<_Tp
,
575 _Alloc
, _Alloc_traits
<_Tp
, _Alloc
>::_S_instanceless
> _Base
;
576 typedef typename
_Base::allocator_type allocator_type
;
578 _Rb_tree_base(const allocator_type
& __a
)
579 : _Base(__a
) { this->_M_header
= _M_get_node(); }
580 ~_Rb_tree_base() { _M_put_node(this->_M_header
); }
584 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
585 typename _Compare
, typename _Alloc
= allocator
<_Val
> >
586 class _Rb_tree
: protected _Rb_tree_base
<_Val
, _Alloc
>
588 typedef _Rb_tree_base
<_Val
, _Alloc
> _Base
;
591 typedef _Rb_tree_node_base
* _Base_ptr
;
592 typedef _Rb_tree_node
<_Val
> _Rb_tree_node
;
595 typedef _Key key_type
;
596 typedef _Val value_type
;
597 typedef value_type
* pointer
;
598 typedef const value_type
* const_pointer
;
599 typedef value_type
& reference
;
600 typedef const value_type
& const_reference
;
601 typedef _Rb_tree_node
* _Link_type
;
602 typedef size_t size_type
;
603 typedef ptrdiff_t difference_type
;
605 typedef typename
_Base::allocator_type allocator_type
;
606 allocator_type
get_allocator() const { return _Base::get_allocator(); }
609 using _Base::_M_get_node
;
610 using _Base::_M_put_node
;
611 using _Base::_M_header
;
614 _M_create_node(const value_type
& __x
)
616 _Link_type __tmp
= _M_get_node();
618 { _Construct(&__tmp
->_M_value_field
, __x
); }
622 __throw_exception_again
;
628 _M_clone_node(_Link_type __x
)
630 _Link_type __tmp
= _M_create_node(__x
->_M_value_field
);
631 __tmp
->_M_color
= __x
->_M_color
;
638 destroy_node(_Link_type __p
)
640 _Destroy(&__p
->_M_value_field
);
644 size_type _M_node_count
; // keeps track of size of tree
645 _Compare _M_key_compare
;
648 _M_root() const { return (_Link_type
&) this->_M_header
->_M_parent
; }
651 _M_leftmost() const { return (_Link_type
&) this->_M_header
->_M_left
; }
654 _M_rightmost() const { return (_Link_type
&) this->_M_header
->_M_right
; }
657 _S_left(_Link_type __x
) { return (_Link_type
&)(__x
->_M_left
); }
660 _S_right(_Link_type __x
) { return (_Link_type
&)(__x
->_M_right
); }
663 _S_parent(_Link_type __x
) { return (_Link_type
&)(__x
->_M_parent
); }
666 _S_value(_Link_type __x
) { return __x
->_M_value_field
; }
669 _S_key(_Link_type __x
) { return _KeyOfValue()(_S_value(__x
)); }
671 static _Rb_tree_color
&
672 _S_color(_Link_type __x
) { return __x
->_M_color
; }
675 _S_left(_Base_ptr __x
) { return (_Link_type
&)(__x
->_M_left
); }
678 _S_right(_Base_ptr __x
) { return (_Link_type
&)(__x
->_M_right
); }
681 _S_parent(_Base_ptr __x
) { return (_Link_type
&)(__x
->_M_parent
); }
684 _S_value(_Base_ptr __x
) { return ((_Link_type
)__x
)->_M_value_field
; }
687 _S_key(_Base_ptr __x
) { return _KeyOfValue()(_S_value(_Link_type(__x
)));}
689 static _Rb_tree_color
&
690 _S_color(_Base_ptr __x
) { return (_Link_type(__x
)->_M_color
); }
693 _S_minimum(_Link_type __x
)
694 { return (_Link_type
) _Rb_tree_node_base::_S_minimum(__x
); }
697 _S_maximum(_Link_type __x
)
698 { return (_Link_type
) _Rb_tree_node_base::_S_maximum(__x
); }
701 typedef _Rb_tree_iterator
<value_type
, reference
, pointer
> iterator
;
702 typedef _Rb_tree_iterator
<value_type
, const_reference
, const_pointer
>
705 typedef std::reverse_iterator
<const_iterator
> const_reverse_iterator
;
706 typedef std::reverse_iterator
<iterator
> reverse_iterator
;
710 _M_insert(_Base_ptr __x
, _Base_ptr __y
, const value_type
& __v
);
713 _M_copy(_Link_type __x
, _Link_type __p
);
716 _M_erase(_Link_type __x
);
719 // allocation/deallocation
721 : _Base(allocator_type()), _M_node_count(0), _M_key_compare()
722 { _M_empty_initialize(); }
724 _Rb_tree(const _Compare
& __comp
)
725 : _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp
)
726 { _M_empty_initialize(); }
728 _Rb_tree(const _Compare
& __comp
, const allocator_type
& __a
)
729 : _Base(__a
), _M_node_count(0), _M_key_compare(__comp
)
730 { _M_empty_initialize(); }
732 _Rb_tree(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
)
733 : _Base(__x
.get_allocator()), _M_node_count(0),
734 _M_key_compare(__x
._M_key_compare
)
736 if (__x
._M_root() == 0)
737 _M_empty_initialize();
740 _S_color(this->_M_header
) = _S_red
;
741 _M_root() = _M_copy(__x
._M_root(), this->_M_header
);
742 _M_leftmost() = _S_minimum(_M_root());
743 _M_rightmost() = _S_maximum(_M_root());
745 _M_node_count
= __x
._M_node_count
;
748 ~_Rb_tree() { clear(); }
750 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>&
751 operator=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
);
754 void _M_empty_initialize()
756 _S_color(this->_M_header
) = _S_red
; // used to distinguish header from
757 // __root, in iterator.operator++
759 _M_leftmost() = this->_M_header
;
760 _M_rightmost() = this->_M_header
;
766 key_comp() const { return _M_key_compare
; }
769 begin() { return _M_leftmost(); }
772 begin() const { return _M_leftmost(); }
775 end() { return this->_M_header
; }
778 end() const { return this->_M_header
; }
781 rbegin() { return reverse_iterator(end()); }
783 const_reverse_iterator
784 rbegin() const { return const_reverse_iterator(end()); }
787 rend() { return reverse_iterator(begin()); }
789 const_reverse_iterator
790 rend() const { return const_reverse_iterator(begin()); }
793 empty() const { return _M_node_count
== 0; }
796 size() const { return _M_node_count
; }
799 max_size() const { return size_type(-1); }
802 swap(_Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __t
)
804 std::swap(this->_M_header
, __t
._M_header
);
805 std::swap(_M_node_count
, __t
._M_node_count
);
806 std::swap(_M_key_compare
, __t
._M_key_compare
);
811 insert_unique(const value_type
& __x
);
814 insert_equal(const value_type
& __x
);
817 insert_unique(iterator __position
, const value_type
& __x
);
820 insert_equal(iterator __position
, const value_type
& __x
);
822 template<typename _InputIterator
>
824 insert_unique(_InputIterator __first
, _InputIterator __last
);
826 template<typename _InputIterator
>
828 insert_equal(_InputIterator __first
, _InputIterator __last
);
831 erase(iterator __position
);
834 erase(const key_type
& __x
);
837 erase(iterator __first
, iterator __last
);
840 erase(const key_type
* __first
, const key_type
* __last
);
845 if (_M_node_count
!= 0)
848 _M_leftmost() = this->_M_header
;
850 _M_rightmost() = this->_M_header
;
857 find(const key_type
& __x
);
860 find(const key_type
& __x
) const;
863 count(const key_type
& __x
) const;
866 lower_bound(const key_type
& __x
);
869 lower_bound(const key_type
& __x
) const;
872 upper_bound(const key_type
& __x
);
875 upper_bound(const key_type
& __x
) const;
877 pair
<iterator
,iterator
>
878 equal_range(const key_type
& __x
);
880 pair
<const_iterator
, const_iterator
>
881 equal_range(const key_type
& __x
) const;
888 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
889 typename _Compare
, typename _Alloc
>
891 operator==(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
892 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
894 return __x
.size() == __y
.size() &&
895 equal(__x
.begin(), __x
.end(), __y
.begin());
898 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
899 typename _Compare
, typename _Alloc
>
901 operator<(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
902 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
904 return lexicographical_compare(__x
.begin(), __x
.end(),
905 __y
.begin(), __y
.end());
908 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
909 typename _Compare
, typename _Alloc
>
911 operator!=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
912 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
913 { return !(__x
== __y
); }
915 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
916 typename _Compare
, typename _Alloc
>
918 operator>(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
919 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
920 { return __y
< __x
; }
922 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
923 typename _Compare
, typename _Alloc
>
925 operator<=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
926 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
927 { return !(__y
< __x
); }
929 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
930 typename _Compare
, typename _Alloc
>
932 operator>=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
933 const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
934 { return !(__x
< __y
); }
936 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
937 typename _Compare
, typename _Alloc
>
939 swap(_Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
,
940 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __y
)
943 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
944 typename _Compare
, typename _Alloc
>
945 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>&
946 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
947 operator=(const _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>& __x
)
951 // Note that _Key may be a constant type.
954 _M_key_compare
= __x
._M_key_compare
;
955 if (__x
._M_root() == 0)
958 _M_leftmost() = this->_M_header
;
959 _M_rightmost() = this->_M_header
;
963 _M_root() = _M_copy(__x
._M_root(), this->_M_header
);
964 _M_leftmost() = _S_minimum(_M_root());
965 _M_rightmost() = _S_maximum(_M_root());
966 _M_node_count
= __x
._M_node_count
;
972 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
973 typename _Compare
, typename _Alloc
>
974 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
975 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
976 _M_insert(_Base_ptr __x_
, _Base_ptr __y_
, const _Val
& __v
)
978 _Link_type __x
= (_Link_type
) __x_
;
979 _Link_type __y
= (_Link_type
) __y_
;
982 if (__y
== this->_M_header
|| __x
!= 0 ||
983 _M_key_compare(_KeyOfValue()(__v
), _S_key(__y
)))
985 __z
= _M_create_node(__v
);
986 _S_left(__y
) = __z
; // also makes _M_leftmost() = __z
987 // when __y == _M_header
988 if (__y
== this->_M_header
)
991 _M_rightmost() = __z
;
993 else if (__y
== _M_leftmost())
994 _M_leftmost() = __z
; // maintain _M_leftmost() pointing to min node
998 __z
= _M_create_node(__v
);
1000 // Maintain _M_rightmost() pointing to max node.
1001 if (__y
== _M_rightmost())
1002 _M_rightmost() = __z
;
1004 _S_parent(__z
) = __y
;
1007 _Rb_tree_rebalance(__z
, this->_M_header
->_M_parent
);
1009 return iterator(__z
);
1012 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1013 typename _Compare
, typename _Alloc
>
1014 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1015 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1016 insert_equal(const _Val
& __v
)
1018 _Link_type __y
= this->_M_header
;
1019 _Link_type __x
= _M_root();
1023 __x
= _M_key_compare(_KeyOfValue()(__v
), _S_key(__x
)) ?
1024 _S_left(__x
) : _S_right(__x
);
1026 return _M_insert(__x
, __y
, __v
);
1029 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1030 typename _Compare
, typename _Alloc
>
1031 pair
<typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
,
1033 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1034 insert_unique(const _Val
& __v
)
1036 _Link_type __y
= this->_M_header
;
1037 _Link_type __x
= _M_root();
1042 __comp
= _M_key_compare(_KeyOfValue()(__v
), _S_key(__x
));
1043 __x
= __comp
? _S_left(__x
) : _S_right(__x
);
1045 iterator __j
= iterator(__y
);
1048 return pair
<iterator
,bool>(_M_insert(__x
, __y
, __v
), true);
1051 if (_M_key_compare(_S_key(__j
._M_node
), _KeyOfValue()(__v
)))
1052 return pair
<iterator
,bool>(_M_insert(__x
, __y
, __v
), true);
1053 return pair
<iterator
,bool>(__j
, false);
1057 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1058 typename _Compare
, typename _Alloc
>
1059 typename _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::iterator
1060 _Rb_tree
<_Key
, _Val
, _KeyOfValue
, _Compare
, _Alloc
>::
1061 insert_unique(iterator __position
, const _Val
& __v
)
1063 if (__position
._M_node
== this->_M_header
->_M_left
)
1067 _M_key_compare(_KeyOfValue()(__v
), _S_key(__position
._M_node
)))
1068 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
1069 // first argument just needs to be non-null
1071 return insert_unique(__v
).first
;
1073 else if (__position
._M_node
== this->_M_header
)
1076 if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v
)))
1077 return _M_insert(0, _M_rightmost(), __v
);
1079 return insert_unique(__v
).first
;
1083 iterator __before
= __position
;
1085 if (_M_key_compare(_S_key(__before
._M_node
), _KeyOfValue()(__v
))
1086 && _M_key_compare(_KeyOfValue()(__v
),_S_key(__position
._M_node
)))
1088 if (_S_right(__before
._M_node
) == 0)
1089 return _M_insert(0, __before
._M_node
, __v
);
1091 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
1092 // first argument just needs to be non-null
1095 return insert_unique(__v
).first
;
1099 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1100 typename _Compare
, typename _Alloc
>
1101 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1102 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1103 insert_equal(iterator __position
, const _Val
& __v
)
1105 if (__position
._M_node
== this->_M_header
->_M_left
)
1109 !_M_key_compare(_S_key(__position
._M_node
), _KeyOfValue()(__v
)))
1110 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
1111 // first argument just needs to be non-null
1113 return insert_equal(__v
);
1115 else if (__position
._M_node
== this->_M_header
)
1118 if (!_M_key_compare(_KeyOfValue()(__v
), _S_key(_M_rightmost())))
1119 return _M_insert(0, _M_rightmost(), __v
);
1121 return insert_equal(__v
);
1125 iterator __before
= __position
;
1127 if (!_M_key_compare(_KeyOfValue()(__v
), _S_key(__before
._M_node
))
1128 && !_M_key_compare(_S_key(__position
._M_node
),
1129 _KeyOfValue()(__v
)))
1131 if (_S_right(__before
._M_node
) == 0)
1132 return _M_insert(0, __before
._M_node
, __v
);
1134 return _M_insert(__position
._M_node
, __position
._M_node
, __v
);
1135 // first argument just needs to be non-null
1138 return insert_equal(__v
);
1142 template<typename _Key
, typename _Val
, typename _KoV
,
1143 typename _Cmp
, typename _Alloc
>
1146 _Rb_tree
<_Key
,_Val
,_KoV
,_Cmp
,_Alloc
>::
1147 insert_equal(_II __first
, _II __last
)
1149 for ( ; __first
!= __last
; ++__first
)
1150 insert_equal(*__first
);
1153 template<typename _Key
, typename _Val
, typename _KoV
,
1154 typename _Cmp
, typename _Alloc
>
1157 _Rb_tree
<_Key
,_Val
,_KoV
,_Cmp
,_Alloc
>::
1158 insert_unique(_II __first
, _II __last
)
1160 for ( ; __first
!= __last
; ++__first
)
1161 insert_unique(*__first
);
1164 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1165 typename _Compare
, typename _Alloc
>
1167 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::erase(iterator __position
)
1170 (_Link_type
) _Rb_tree_rebalance_for_erase(__position
._M_node
,
1171 this->_M_header
->_M_parent
,
1172 this->_M_header
->_M_left
,
1173 this->_M_header
->_M_right
);
1178 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1179 typename _Compare
, typename _Alloc
>
1180 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::size_type
1181 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::erase(const _Key
& __x
)
1183 pair
<iterator
,iterator
> __p
= equal_range(__x
);
1184 size_type __n
= std::distance(__p
.first
, __p
.second
);
1185 erase(__p
.first
, __p
.second
);
1189 template<typename _Key
, typename _Val
, typename _KoV
,
1190 typename _Compare
, typename _Alloc
>
1191 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::_Link_type
1192 _Rb_tree
<_Key
,_Val
,_KoV
,_Compare
,_Alloc
>::
1193 _M_copy(_Link_type __x
, _Link_type __p
)
1195 // Structural copy. __x and __p must be non-null.
1196 _Link_type __top
= _M_clone_node(__x
);
1197 __top
->_M_parent
= __p
;
1202 __top
->_M_right
= _M_copy(_S_right(__x
), __top
);
1208 _Link_type __y
= _M_clone_node(__x
);
1210 __y
->_M_parent
= __p
;
1212 __y
->_M_right
= _M_copy(_S_right(__x
), __y
);
1220 __throw_exception_again
;
1225 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1226 typename _Compare
, typename _Alloc
>
1228 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::_M_erase(_Link_type __x
)
1230 // Erase without rebalancing.
1233 _M_erase(_S_right(__x
));
1234 _Link_type __y
= _S_left(__x
);
1240 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1241 typename _Compare
, typename _Alloc
>
1243 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1244 erase(iterator __first
, iterator __last
)
1246 if (__first
== begin() && __last
== end())
1249 while (__first
!= __last
) erase(__first
++);
1252 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1253 typename _Compare
, typename _Alloc
>
1255 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1256 erase(const _Key
* __first
, const _Key
* __last
)
1258 while (__first
!= __last
)
1262 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1263 typename _Compare
, typename _Alloc
>
1264 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1265 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::find(const _Key
& __k
)
1268 = this->_M_header
; // Last node which is not less than __k.
1269 _Link_type __x
= _M_root(); // Current node.
1272 if (!_M_key_compare(_S_key(__x
), __k
))
1273 __y
= __x
, __x
= _S_left(__x
);
1275 __x
= _S_right(__x
);
1277 iterator __j
= iterator(__y
);
1278 return (__j
== end() || _M_key_compare(__k
, _S_key(__j
._M_node
))) ?
1282 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1283 typename _Compare
, typename _Alloc
>
1284 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1285 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1286 find(const _Key
& __k
) const
1289 = this->_M_header
; // Last node which is not less than __k.
1290 _Link_type __x
= _M_root(); // Current node.
1294 if (!_M_key_compare(_S_key(__x
), __k
))
1295 __y
= __x
, __x
= _S_left(__x
);
1297 __x
= _S_right(__x
);
1299 const_iterator __j
= const_iterator(__y
);
1300 return (__j
== end() || _M_key_compare(__k
, _S_key(__j
._M_node
))) ?
1304 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1305 typename _Compare
, typename _Alloc
>
1306 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::size_type
1307 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1308 count(const _Key
& __k
) const
1310 pair
<const_iterator
, const_iterator
> __p
= equal_range(__k
);
1311 size_type __n
= std::distance(__p
.first
, __p
.second
);
1315 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1316 typename _Compare
, typename _Alloc
>
1317 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1318 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1319 lower_bound(const _Key
& __k
)
1322 = this->_M_header
; /* Last node which is not less than __k. */
1323 _Link_type __x
= _M_root(); /* Current node. */
1326 if (!_M_key_compare(_S_key(__x
), __k
))
1327 __y
= __x
, __x
= _S_left(__x
);
1329 __x
= _S_right(__x
);
1331 return iterator(__y
);
1334 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1335 typename _Compare
, typename _Alloc
>
1336 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1337 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1338 lower_bound(const _Key
& __k
) const
1341 = this->_M_header
; /* Last node which is not less than __k. */
1342 _Link_type __x
= _M_root(); /* Current node. */
1345 if (!_M_key_compare(_S_key(__x
), __k
))
1346 __y
= __x
, __x
= _S_left(__x
);
1348 __x
= _S_right(__x
);
1350 return const_iterator(__y
);
1353 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1354 typename _Compare
, typename _Alloc
>
1355 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
1356 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1357 upper_bound(const _Key
& __k
)
1360 = this->_M_header
; /* Last node which is greater than __k. */
1361 _Link_type __x
= _M_root(); /* Current node. */
1364 if (_M_key_compare(__k
, _S_key(__x
)))
1365 __y
= __x
, __x
= _S_left(__x
);
1367 __x
= _S_right(__x
);
1369 return iterator(__y
);
1372 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1373 typename _Compare
, typename _Alloc
>
1374 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::const_iterator
1375 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1376 upper_bound(const _Key
& __k
) const
1379 = this->_M_header
; /* Last node which is greater than __k. */
1380 _Link_type __x
= _M_root(); /* Current node. */
1383 if (_M_key_compare(__k
, _S_key(__x
)))
1384 __y
= __x
, __x
= _S_left(__x
);
1386 __x
= _S_right(__x
);
1388 return const_iterator(__y
);
1391 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1392 typename _Compare
, typename _Alloc
>
1394 pair
<typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
,
1395 typename _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::iterator
>
1396 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::
1397 equal_range(const _Key
& __k
)
1398 { return pair
<iterator
, iterator
>(lower_bound(__k
), upper_bound(__k
)); }
1400 template<typename _Key
, typename _Val
, typename _KoV
,
1401 typename _Compare
, typename _Alloc
>
1403 pair
<typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::const_iterator
,
1404 typename _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>::const_iterator
>
1405 _Rb_tree
<_Key
, _Val
, _KoV
, _Compare
, _Alloc
>
1406 ::equal_range(const _Key
& __k
) const
1408 return pair
<const_iterator
,const_iterator
>(lower_bound(__k
),
1413 __black_count(_Rb_tree_node_base
* __node
, _Rb_tree_node_base
* __root
)
1420 if (__node
->_M_color
== _S_black
)
1422 if (__node
== __root
)
1424 __node
= __node
->_M_parent
;
1430 template<typename _Key
, typename _Val
, typename _KeyOfValue
,
1431 typename _Compare
, typename _Alloc
>
1433 _Rb_tree
<_Key
,_Val
,_KeyOfValue
,_Compare
,_Alloc
>::__rb_verify() const
1435 if (_M_node_count
== 0 || begin() == end())
1436 return _M_node_count
== 0 && begin() == end() &&
1437 this->_M_header
->_M_left
== this->_M_header
1438 && this->_M_header
->_M_right
== this->_M_header
;
1440 int __len
= __black_count(_M_leftmost(), _M_root());
1441 for (const_iterator __it
= begin(); __it
!= end(); ++__it
)
1443 _Link_type __x
= (_Link_type
) __it
._M_node
;
1444 _Link_type __L
= _S_left(__x
);
1445 _Link_type __R
= _S_right(__x
);
1447 if (__x
->_M_color
== _S_red
)
1448 if ((__L
&& __L
->_M_color
== _S_red
)
1449 || (__R
&& __R
->_M_color
== _S_red
))
1452 if (__L
&& _M_key_compare(_S_key(__x
), _S_key(__L
)))
1454 if (__R
&& _M_key_compare(_S_key(__R
), _S_key(__x
)))
1457 if (!__L
&& !__R
&& __black_count(__x
, _M_root()) != __len
)
1461 if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1463 if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))