1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- A D A . C O N T A I N E R S . --
6 -- I N D E F I N I T E _ D O U B L Y _ L I N K E D _ L I S T S --
10 -- Copyright (C) 2004-2006, Free Software Foundation, Inc. --
12 -- This specification is derived from the Ada Reference Manual for use with --
13 -- GNAT. The copyright notice above, and the license provisions that follow --
14 -- apply solely to the contents of the part following the private keyword. --
16 -- GNAT is free software; you can redistribute it and/or modify it under --
17 -- terms of the GNU General Public License as published by the Free Soft- --
18 -- ware Foundation; either version 2, or (at your option) any later ver- --
19 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
20 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
21 -- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License --
22 -- for more details. You should have received a copy of the GNU General --
23 -- Public License distributed with GNAT; see file COPYING. If not, write --
24 -- to the Free Software Foundation, 51 Franklin Street, Fifth Floor, --
25 -- Boston, MA 02110-1301, USA. --
27 -- As a special exception, if other files instantiate generics from this --
28 -- unit, or you link this unit with other files to produce an executable, --
29 -- this unit does not by itself cause the resulting executable to be --
30 -- covered by the GNU General Public License. This exception does not --
31 -- however invalidate any other reasons why the executable file might be --
32 -- covered by the GNU Public License. --
34 -- This unit was originally developed by Matthew J Heaney. --
35 ------------------------------------------------------------------------------
37 with System; use type System.Address;
38 with Ada.Unchecked_Deallocation;
40 package body Ada.Containers.Indefinite_Doubly_Linked_Lists is
43 new Ada.Unchecked_Deallocation (Element_Type, Element_Access);
45 -----------------------
46 -- Local Subprograms --
47 -----------------------
49 procedure Free (X : in out Node_Access);
51 procedure Insert_Internal
52 (Container : in out List;
54 New_Node : Node_Access);
56 function Vet (Position : Cursor) return Boolean;
62 function "=" (Left, Right : List) return Boolean is
67 if Left'Address = Right'Address then
71 if Left.Length /= Right.Length then
77 for J in 1 .. Left.Length loop
78 if L.Element.all /= R.Element.all then
93 procedure Adjust (Container : in out List) is
94 Src : Node_Access := Container.First;
99 pragma Assert (Container.Last = null);
100 pragma Assert (Container.Length = 0);
101 pragma Assert (Container.Busy = 0);
102 pragma Assert (Container.Lock = 0);
106 pragma Assert (Container.First.Prev = null);
107 pragma Assert (Container.Last.Next = null);
108 pragma Assert (Container.Length > 0);
110 Container.First := null;
111 Container.Last := null;
112 Container.Length := 0;
117 Element : Element_Access := new Element_Type'(Src.Element.all);
119 Dst := new Node_Type'(Element, null, null);
126 Container.First := Dst;
127 Container.Last := Dst;
128 Container.Length := 1;
131 while Src /= null loop
133 Element : Element_Access := new Element_Type'(Src.Element.all);
135 Dst := new Node_Type'(Element, null, Prev => Container.Last);
142 Container.Last.Next := Dst;
143 Container.Last := Dst;
144 Container.Length := Container.Length + 1;
155 (Container : in out List;
156 New_Item : Element_Type;
157 Count : Count_Type := 1)
160 Insert (Container, No_Element, New_Item, Count);
167 procedure Clear (Container : in out List) is
171 if Container.Length = 0 then
172 pragma Assert (Container.First = null);
173 pragma Assert (Container.Last = null);
174 pragma Assert (Container.Busy = 0);
175 pragma Assert (Container.Lock = 0);
179 pragma Assert (Container.First.Prev = null);
180 pragma Assert (Container.Last.Next = null);
182 if Container.Busy > 0 then
186 while Container.Length > 1 loop
187 X := Container.First;
188 pragma Assert (X.Next.Prev = Container.First);
190 Container.First := X.Next;
191 Container.First.Prev := null;
193 Container.Length := Container.Length - 1;
198 X := Container.First;
199 pragma Assert (X = Container.Last);
201 Container.First := null;
202 Container.Last := null;
203 Container.Length := 0;
214 Item : Element_Type) return Boolean
217 return Find (Container, Item) /= No_Element;
225 (Container : in out List;
226 Position : in out Cursor;
227 Count : Count_Type := 1)
232 if Position.Node = null then
233 raise Constraint_Error;
236 if Position.Node.Element = null then
240 if Position.Container /= Container'Unrestricted_Access then
244 pragma Assert (Vet (Position), "bad cursor in Delete");
246 if Position.Node = Container.First then
247 Delete_First (Container, Count);
248 Position := No_Element; -- Post-York behavior
253 Position := No_Element; -- Post-York behavior
257 if Container.Busy > 0 then
261 for Index in 1 .. Count loop
263 Container.Length := Container.Length - 1;
265 if X = Container.Last then
266 Position := No_Element;
268 Container.Last := X.Prev;
269 Container.Last.Next := null;
275 Position.Node := X.Next;
277 X.Next.Prev := X.Prev;
278 X.Prev.Next := X.Next;
283 Position := No_Element; -- Post-York behavior
290 procedure Delete_First
291 (Container : in out List;
292 Count : Count_Type := 1)
297 if Count >= Container.Length then
306 if Container.Busy > 0 then
310 for I in 1 .. Count loop
311 X := Container.First;
312 pragma Assert (X.Next.Prev = Container.First);
314 Container.First := X.Next;
315 Container.First.Prev := null;
317 Container.Length := Container.Length - 1;
327 procedure Delete_Last
328 (Container : in out List;
329 Count : Count_Type := 1)
334 if Count >= Container.Length then
343 if Container.Busy > 0 then
347 for I in 1 .. Count loop
349 pragma Assert (X.Prev.Next = Container.Last);
351 Container.Last := X.Prev;
352 Container.Last.Next := null;
354 Container.Length := Container.Length - 1;
364 function Element (Position : Cursor) return Element_Type is
366 if Position.Node = null then
367 raise Constraint_Error;
370 if Position.Node.Element = null then
374 pragma Assert (Vet (Position), "bad cursor in Element");
376 return Position.Node.Element.all;
386 Position : Cursor := No_Element) return Cursor
388 Node : Node_Access := Position.Node;
392 Node := Container.First;
395 if Node.Element = null then
399 if Position.Container /= Container'Unrestricted_Access then
403 pragma Assert (Vet (Position), "bad cursor in Find");
406 while Node /= null loop
407 if Node.Element.all = Item then
408 return Cursor'(Container'Unchecked_Access, Node);
421 function First (Container : List) return Cursor is
423 if Container.First = null then
427 return Cursor'(Container'Unchecked_Access, Container.First);
434 function First_Element (Container : List) return Element_Type is
436 if Container.First = null then
437 raise Constraint_Error;
440 return Container.First.Element.all;
447 procedure Free (X : in out Node_Access) is
448 procedure Deallocate is
449 new Ada.Unchecked_Deallocation (Node_Type, Node_Access);
467 ---------------------
468 -- Generic_Sorting --
469 ---------------------
471 package body Generic_Sorting is
477 function Is_Sorted (Container : List) return Boolean is
478 Node : Node_Access := Container.First;
481 for I in 2 .. Container.Length loop
482 if Node.Next.Element.all < Node.Element.all then
497 (Target : in out List;
498 Source : in out List)
504 if Target'Address = Source'Address then
509 or else Source.Busy > 0
514 LI := First (Target);
515 RI := First (Source);
516 while RI.Node /= null loop
517 pragma Assert (RI.Node.Next = null
518 or else not (RI.Node.Next.Element.all <
519 RI.Node.Element.all));
521 if LI.Node = null then
522 Splice (Target, No_Element, Source);
526 pragma Assert (LI.Node.Next = null
527 or else not (LI.Node.Next.Element.all <
528 LI.Node.Element.all));
530 if RI.Node.Element.all < LI.Node.Element.all then
534 RI.Node := RI.Node.Next;
535 Splice (Target, LI, Source, RJ);
539 LI.Node := LI.Node.Next;
548 procedure Sort (Container : in out List) is
549 procedure Partition (Pivot : Node_Access; Back : Node_Access);
551 procedure Sort (Front, Back : Node_Access);
557 procedure Partition (Pivot : Node_Access; Back : Node_Access) is
558 Node : Node_Access := Pivot.Next;
561 while Node /= Back loop
562 if Node.Element.all < Pivot.Element.all then
564 Prev : constant Node_Access := Node.Prev;
565 Next : constant Node_Access := Node.Next;
570 Container.Last := Prev;
576 Node.Prev := Pivot.Prev;
580 if Node.Prev = null then
581 Container.First := Node;
583 Node.Prev.Next := Node;
599 procedure Sort (Front, Back : Node_Access) is
604 Pivot := Container.First;
609 if Pivot /= Back then
610 Partition (Pivot, Back);
616 -- Start of processing for Sort
619 if Container.Length <= 1 then
623 pragma Assert (Container.First.Prev = null);
624 pragma Assert (Container.Last.Next = null);
626 if Container.Busy > 0 then
630 Sort (Front => null, Back => null);
632 pragma Assert (Container.First.Prev = null);
633 pragma Assert (Container.Last.Next = null);
642 function Has_Element (Position : Cursor) return Boolean is
644 pragma Assert (Vet (Position), "bad cursor in Has_Element");
645 return Position.Node /= null;
653 (Container : in out List;
655 New_Item : Element_Type;
656 Position : out Cursor;
657 Count : Count_Type := 1)
659 New_Node : Node_Access;
662 if Before.Container /= null then
663 if Before.Container /= Container'Unrestricted_Access then
667 if Before.Node = null
668 or else Before.Node.Element = null
673 pragma Assert (Vet (Before), "bad cursor in Insert");
681 if Container.Length > Count_Type'Last - Count then
682 raise Constraint_Error;
685 if Container.Busy > 0 then
690 Element : Element_Access := new Element_Type'(New_Item);
692 New_Node := new Node_Type'(Element, null, null);
699 Insert_Internal (Container, Before.Node, New_Node);
700 Position := Cursor'(Container'Unchecked_Access, New_Node);
702 for J in Count_Type'(2) .. Count loop
705 Element : Element_Access := new Element_Type'(New_Item);
707 New_Node := new Node_Type'(Element, null, null);
714 Insert_Internal (Container, Before.Node, New_Node);
719 (Container : in out List;
721 New_Item : Element_Type;
722 Count : Count_Type := 1)
726 Insert (Container, Before, New_Item, Position, Count);
729 ---------------------
730 -- Insert_Internal --
731 ---------------------
733 procedure Insert_Internal
734 (Container : in out List;
735 Before : Node_Access;
736 New_Node : Node_Access)
739 if Container.Length = 0 then
740 pragma Assert (Before = null);
741 pragma Assert (Container.First = null);
742 pragma Assert (Container.Last = null);
744 Container.First := New_Node;
745 Container.Last := New_Node;
747 elsif Before = null then
748 pragma Assert (Container.Last.Next = null);
750 Container.Last.Next := New_Node;
751 New_Node.Prev := Container.Last;
753 Container.Last := New_Node;
755 elsif Before = Container.First then
756 pragma Assert (Container.First.Prev = null);
758 Container.First.Prev := New_Node;
759 New_Node.Next := Container.First;
761 Container.First := New_Node;
764 pragma Assert (Container.First.Prev = null);
765 pragma Assert (Container.Last.Next = null);
767 New_Node.Next := Before;
768 New_Node.Prev := Before.Prev;
770 Before.Prev.Next := New_Node;
771 Before.Prev := New_Node;
774 Container.Length := Container.Length + 1;
781 function Is_Empty (Container : List) return Boolean is
783 return Container.Length = 0;
792 Process : not null access procedure (Position : Cursor))
794 C : List renames Container'Unrestricted_Access.all;
795 B : Natural renames C.Busy;
797 Node : Node_Access := Container.First;
803 while Node /= null loop
804 Process (Cursor'(Container'Unchecked_Access, Node));
820 function Last (Container : List) return Cursor is
822 if Container.Last = null then
826 return Cursor'(Container'Unchecked_Access, Container.Last);
833 function Last_Element (Container : List) return Element_Type is
835 if Container.Last = null then
836 raise Constraint_Error;
839 return Container.Last.Element.all;
846 function Length (Container : List) return Count_Type is
848 return Container.Length;
855 procedure Move (Target : in out List; Source : in out List) is
857 if Target'Address = Source'Address then
861 if Source.Busy > 0 then
867 Target.First := Source.First;
868 Source.First := null;
870 Target.Last := Source.Last;
873 Target.Length := Source.Length;
881 procedure Next (Position : in out Cursor) is
883 pragma Assert (Vet (Position), "bad cursor in procedure Next");
885 if Position.Node = null then
889 Position.Node := Position.Node.Next;
891 if Position.Node = null then
892 Position.Container := null;
896 function Next (Position : Cursor) return Cursor is
898 pragma Assert (Vet (Position), "bad cursor in function Next");
900 if Position.Node = null then
905 Next_Node : constant Node_Access := Position.Node.Next;
907 if Next_Node = null then
911 return Cursor'(Position.Container, Next_Node);
920 (Container : in out List;
921 New_Item : Element_Type;
922 Count : Count_Type := 1)
925 Insert (Container, First (Container), New_Item, Count);
932 procedure Previous (Position : in out Cursor) is
934 pragma Assert (Vet (Position), "bad cursor in procedure Previous");
936 if Position.Node = null then
940 Position.Node := Position.Node.Prev;
942 if Position.Node = null then
943 Position.Container := null;
947 function Previous (Position : Cursor) return Cursor is
949 pragma Assert (Vet (Position), "bad cursor in function Previous");
951 if Position.Node = null then
956 Prev_Node : constant Node_Access := Position.Node.Prev;
958 if Prev_Node = null then
962 return Cursor'(Position.Container, Prev_Node);
970 procedure Query_Element
972 Process : not null access procedure (Element : Element_Type))
975 if Position.Node = null then
976 raise Constraint_Error;
979 if Position.Node.Element = null then
983 pragma Assert (Vet (Position), "bad cursor in Query_Element");
986 C : List renames Position.Container.all'Unrestricted_Access.all;
987 B : Natural renames C.Busy;
988 L : Natural renames C.Lock;
995 Process (Position.Node.Element.all);
1013 (Stream : access Root_Stream_Type'Class;
1016 N : Count_Type'Base;
1022 Count_Type'Base'Read (Stream, N);
1029 Element : Element_Access :=
1030 new Element_Type'(Element_Type'Input (Stream));
1032 Dst := new Node_Type'(Element, null, null);
1043 while Item.Length < N loop
1045 Element : Element_Access :=
1046 new Element_Type'(Element_Type'Input (Stream));
1048 Dst := new Node_Type'(Element, Next => null, Prev => Item.Last);
1055 Item.Last.Next := Dst;
1057 Item.Length := Item.Length + 1;
1062 (Stream : access Root_Stream_Type'Class;
1066 raise Program_Error;
1069 ---------------------
1070 -- Replace_Element --
1071 ---------------------
1073 procedure Replace_Element
1074 (Container : in out List;
1076 New_Item : Element_Type)
1079 if Position.Container = null then
1080 raise Constraint_Error;
1083 if Position.Container /= Container'Unchecked_Access then
1084 raise Program_Error;
1087 if Position.Container.Lock > 0 then
1088 raise Program_Error;
1091 if Position.Node.Element = null then
1092 raise Program_Error;
1095 pragma Assert (Vet (Position), "bad cursor in Replace_Element");
1098 X : Element_Access := Position.Node.Element;
1101 Position.Node.Element := new Element_Type'(New_Item);
1104 end Replace_Element;
1106 ----------------------
1107 -- Reverse_Elements --
1108 ----------------------
1110 procedure Reverse_Elements (Container : in out List) is
1111 I : Node_Access := Container.First;
1112 J : Node_Access := Container.Last;
1114 procedure Swap (L, R : Node_Access);
1120 procedure Swap (L, R : Node_Access) is
1121 LN : constant Node_Access := L.Next;
1122 LP : constant Node_Access := L.Prev;
1124 RN : constant Node_Access := R.Next;
1125 RP : constant Node_Access := R.Prev;
1140 pragma Assert (RP = L);
1154 -- Start of processing for Reverse_Elements
1157 if Container.Length <= 1 then
1161 pragma Assert (Container.First.Prev = null);
1162 pragma Assert (Container.Last.Next = null);
1164 if Container.Busy > 0 then
1165 raise Program_Error;
1168 Container.First := J;
1169 Container.Last := I;
1171 Swap (L => I, R => J);
1179 Swap (L => J, R => I);
1188 pragma Assert (Container.First.Prev = null);
1189 pragma Assert (Container.Last.Next = null);
1190 end Reverse_Elements;
1196 function Reverse_Find
1198 Item : Element_Type;
1199 Position : Cursor := No_Element) return Cursor
1201 Node : Node_Access := Position.Node;
1205 Node := Container.Last;
1208 if Node.Element = null then
1209 raise Program_Error;
1212 if Position.Container /= Container'Unrestricted_Access then
1213 raise Program_Error;
1216 pragma Assert (Vet (Position), "bad cursor in Reverse_Find");
1219 while Node /= null loop
1220 if Node.Element.all = Item then
1221 return Cursor'(Container'Unchecked_Access, Node);
1230 ---------------------
1231 -- Reverse_Iterate --
1232 ---------------------
1234 procedure Reverse_Iterate
1236 Process : not null access procedure (Position : Cursor))
1238 C : List renames Container'Unrestricted_Access.all;
1239 B : Natural renames C.Busy;
1241 Node : Node_Access := Container.Last;
1247 while Node /= null loop
1248 Process (Cursor'(Container'Unchecked_Access, Node));
1258 end Reverse_Iterate;
1265 (Target : in out List;
1267 Source : in out List)
1270 if Before.Container /= null then
1271 if Before.Container /= Target'Unrestricted_Access then
1272 raise Program_Error;
1275 if Before.Node = null
1276 or else Before.Node.Element = null
1278 raise Program_Error;
1281 pragma Assert (Vet (Before), "bad cursor in Splice");
1284 if Target'Address = Source'Address
1285 or else Source.Length = 0
1290 pragma Assert (Source.First.Prev = null);
1291 pragma Assert (Source.Last.Next = null);
1293 if Target.Length > Count_Type'Last - Source.Length then
1294 raise Constraint_Error;
1298 or else Source.Busy > 0
1300 raise Program_Error;
1303 if Target.Length = 0 then
1304 pragma Assert (Before = No_Element);
1305 pragma Assert (Target.First = null);
1306 pragma Assert (Target.Last = null);
1308 Target.First := Source.First;
1309 Target.Last := Source.Last;
1311 elsif Before.Node = null then
1312 pragma Assert (Target.Last.Next = null);
1314 Target.Last.Next := Source.First;
1315 Source.First.Prev := Target.Last;
1317 Target.Last := Source.Last;
1319 elsif Before.Node = Target.First then
1320 pragma Assert (Target.First.Prev = null);
1322 Source.Last.Next := Target.First;
1323 Target.First.Prev := Source.Last;
1325 Target.First := Source.First;
1328 pragma Assert (Target.Length >= 2);
1329 Before.Node.Prev.Next := Source.First;
1330 Source.First.Prev := Before.Node.Prev;
1332 Before.Node.Prev := Source.Last;
1333 Source.Last.Next := Before.Node;
1336 Source.First := null;
1337 Source.Last := null;
1339 Target.Length := Target.Length + Source.Length;
1344 (Container : in out List;
1346 Position : in out Cursor)
1349 if Before.Container /= null then
1350 if Before.Container /= Container'Unchecked_Access then
1351 raise Program_Error;
1354 if Before.Node = null
1355 or else Before.Node.Element = null
1357 raise Program_Error;
1360 pragma Assert (Vet (Before), "bad Before cursor in Splice");
1363 if Position.Node = null then
1364 raise Constraint_Error;
1367 if Position.Node.Element = null then
1368 raise Program_Error;
1371 if Position.Container /= Container'Unrestricted_Access then
1372 raise Program_Error;
1375 pragma Assert (Vet (Position), "bad Position cursor in Splice");
1377 if Position.Node = Before.Node
1378 or else Position.Node.Next = Before.Node
1383 pragma Assert (Container.Length >= 2);
1385 if Container.Busy > 0 then
1386 raise Program_Error;
1389 if Before.Node = null then
1390 pragma Assert (Position.Node /= Container.Last);
1392 if Position.Node = Container.First then
1393 Container.First := Position.Node.Next;
1394 Container.First.Prev := null;
1396 Position.Node.Prev.Next := Position.Node.Next;
1397 Position.Node.Next.Prev := Position.Node.Prev;
1400 Container.Last.Next := Position.Node;
1401 Position.Node.Prev := Container.Last;
1403 Container.Last := Position.Node;
1404 Container.Last.Next := null;
1409 if Before.Node = Container.First then
1410 pragma Assert (Position.Node /= Container.First);
1412 if Position.Node = Container.Last then
1413 Container.Last := Position.Node.Prev;
1414 Container.Last.Next := null;
1416 Position.Node.Prev.Next := Position.Node.Next;
1417 Position.Node.Next.Prev := Position.Node.Prev;
1420 Container.First.Prev := Position.Node;
1421 Position.Node.Next := Container.First;
1423 Container.First := Position.Node;
1424 Container.First.Prev := null;
1429 if Position.Node = Container.First then
1430 Container.First := Position.Node.Next;
1431 Container.First.Prev := null;
1433 elsif Position.Node = Container.Last then
1434 Container.Last := Position.Node.Prev;
1435 Container.Last.Next := null;
1438 Position.Node.Prev.Next := Position.Node.Next;
1439 Position.Node.Next.Prev := Position.Node.Prev;
1442 Before.Node.Prev.Next := Position.Node;
1443 Position.Node.Prev := Before.Node.Prev;
1445 Before.Node.Prev := Position.Node;
1446 Position.Node.Next := Before.Node;
1448 pragma Assert (Container.First.Prev = null);
1449 pragma Assert (Container.Last.Next = null);
1453 (Target : in out List;
1455 Source : in out List;
1456 Position : in out Cursor)
1459 if Target'Address = Source'Address then
1460 Splice (Target, Before, Position);
1464 if Before.Container /= null then
1465 if Before.Container /= Target'Unrestricted_Access then
1466 raise Program_Error;
1469 if Before.Node = null
1470 or else Before.Node.Element = null
1472 raise Program_Error;
1475 pragma Assert (Vet (Before), "bad Before cursor in Splice");
1478 if Position.Node = null then
1479 raise Constraint_Error;
1482 if Position.Node.Element = null then
1483 raise Program_Error;
1486 if Position.Container /= Source'Unrestricted_Access then
1487 raise Program_Error;
1490 pragma Assert (Vet (Position), "bad Position cursor in Splice");
1492 if Target.Length = Count_Type'Last then
1493 raise Constraint_Error;
1497 or else Source.Busy > 0
1499 raise Program_Error;
1502 if Position.Node = Source.First then
1503 Source.First := Position.Node.Next;
1505 if Position.Node = Source.Last then
1506 pragma Assert (Source.First = null);
1507 pragma Assert (Source.Length = 1);
1508 Source.Last := null;
1511 Source.First.Prev := null;
1514 elsif Position.Node = Source.Last then
1515 pragma Assert (Source.Length >= 2);
1516 Source.Last := Position.Node.Prev;
1517 Source.Last.Next := null;
1520 pragma Assert (Source.Length >= 3);
1521 Position.Node.Prev.Next := Position.Node.Next;
1522 Position.Node.Next.Prev := Position.Node.Prev;
1525 if Target.Length = 0 then
1526 pragma Assert (Before = No_Element);
1527 pragma Assert (Target.First = null);
1528 pragma Assert (Target.Last = null);
1530 Target.First := Position.Node;
1531 Target.Last := Position.Node;
1533 Target.First.Prev := null;
1534 Target.Last.Next := null;
1536 elsif Before.Node = null then
1537 pragma Assert (Target.Last.Next = null);
1538 Target.Last.Next := Position.Node;
1539 Position.Node.Prev := Target.Last;
1541 Target.Last := Position.Node;
1542 Target.Last.Next := null;
1544 elsif Before.Node = Target.First then
1545 pragma Assert (Target.First.Prev = null);
1546 Target.First.Prev := Position.Node;
1547 Position.Node.Next := Target.First;
1549 Target.First := Position.Node;
1550 Target.First.Prev := null;
1553 pragma Assert (Target.Length >= 2);
1554 Before.Node.Prev.Next := Position.Node;
1555 Position.Node.Prev := Before.Node.Prev;
1557 Before.Node.Prev := Position.Node;
1558 Position.Node.Next := Before.Node;
1561 Target.Length := Target.Length + 1;
1562 Source.Length := Source.Length - 1;
1564 Position.Container := Target'Unchecked_Access;
1572 (Container : in out List;
1577 or else J.Node = null
1579 raise Constraint_Error;
1582 if I.Container /= Container'Unchecked_Access
1583 or else J.Container /= Container'Unchecked_Access
1585 raise Program_Error;
1588 if I.Node = J.Node then
1592 if Container.Lock > 0 then
1593 raise Program_Error;
1596 pragma Assert (Vet (I), "bad I cursor in Swap");
1597 pragma Assert (Vet (J), "bad J cursor in Swap");
1600 EI_Copy : constant Element_Access := I.Node.Element;
1603 I.Node.Element := J.Node.Element;
1604 J.Node.Element := EI_Copy;
1612 procedure Swap_Links
1613 (Container : in out List;
1618 or else J.Node = null
1620 raise Constraint_Error;
1623 if I.Container /= Container'Unrestricted_Access
1624 or else I.Container /= J.Container
1626 raise Program_Error;
1629 if I.Node = J.Node then
1633 if Container.Busy > 0 then
1634 raise Program_Error;
1637 pragma Assert (Vet (I), "bad I cursor in Swap_Links");
1638 pragma Assert (Vet (J), "bad J cursor in Swap_Links");
1641 I_Next : constant Cursor := Next (I);
1642 J_Copy : Cursor := J;
1646 Splice (Container, Before => I, Position => J_Copy);
1650 J_Next : constant Cursor := Next (J);
1651 I_Copy : Cursor := I;
1655 Splice (Container, Before => J, Position => I_Copy);
1658 pragma Assert (Container.Length >= 3);
1660 Splice (Container, Before => I_Next, Position => J_Copy);
1661 Splice (Container, Before => J_Next, Position => I_Copy);
1667 pragma Assert (Container.First.Prev = null);
1668 pragma Assert (Container.Last.Next = null);
1671 --------------------
1672 -- Update_Element --
1673 --------------------
1675 procedure Update_Element
1676 (Container : in out List;
1678 Process : not null access procedure (Element : in out Element_Type))
1681 if Position.Node = null then
1682 raise Constraint_Error;
1685 if Position.Node.Element = null then
1686 raise Program_Error;
1689 if Position.Container /= Container'Unchecked_Access then
1690 raise Program_Error;
1693 pragma Assert (Vet (Position), "bad cursor in Update_Element");
1696 B : Natural renames Container.Busy;
1697 L : Natural renames Container.Lock;
1704 Process (Position.Node.Element.all);
1721 function Vet (Position : Cursor) return Boolean is
1723 if Position.Node = null then
1724 return Position.Container = null;
1727 if Position.Container = null then
1731 if Position.Node.Next = Position.Node then
1735 if Position.Node.Prev = Position.Node then
1739 if Position.Node.Element = null then
1744 L : List renames Position.Container.all;
1746 if L.Length = 0 then
1750 if L.First = null then
1754 if L.Last = null then
1758 if L.First.Prev /= null then
1762 if L.Last.Next /= null then
1766 if Position.Node.Prev = null
1767 and then Position.Node /= L.First
1772 if Position.Node.Next = null
1773 and then Position.Node /= L.Last
1778 if L.Length = 1 then
1779 return L.First = L.Last;
1782 if L.First = L.Last then
1786 if L.First.Next = null then
1790 if L.Last.Prev = null then
1794 if L.First.Next.Prev /= L.First then
1798 if L.Last.Prev.Next /= L.Last then
1802 if L.Length = 2 then
1803 if L.First.Next /= L.Last then
1807 if L.Last.Prev /= L.First then
1814 if L.First.Next = L.Last then
1818 if L.Last.Prev = L.First then
1822 if Position.Node = L.First then
1826 if Position.Node = L.Last then
1830 if Position.Node.Next = null then
1834 if Position.Node.Prev = null then
1838 if Position.Node.Next.Prev /= Position.Node then
1842 if Position.Node.Prev.Next /= Position.Node then
1846 if L.Length = 3 then
1847 if L.First.Next /= Position.Node then
1851 if L.Last.Prev /= Position.Node then
1865 (Stream : access Root_Stream_Type'Class;
1868 Node : Node_Access := Item.First;
1871 Count_Type'Base'Write (Stream, Item.Length);
1873 while Node /= null loop
1874 Element_Type'Output (Stream, Node.Element.all); -- X.all
1880 (Stream : access Root_Stream_Type'Class;
1884 raise Program_Error;
1887 end Ada.Containers.Indefinite_Doubly_Linked_Lists;