1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- A D A . C O N T A I N E R S . D O U B L Y _ L I N K E D _ L I S T S --
9 -- Copyright (C) 2004-2011, Free Software Foundation, Inc. --
11 -- GNAT is free software; you can redistribute it and/or modify it under --
12 -- terms of the GNU General Public License as published by the Free Soft- --
13 -- ware Foundation; either version 3, or (at your option) any later ver- --
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
16 -- or FITNESS FOR A PARTICULAR PURPOSE. --
18 -- As a special exception under Section 7 of GPL version 3, you are granted --
19 -- additional permissions described in the GCC Runtime Library Exception, --
20 -- version 3.1, as published by the Free Software Foundation. --
22 -- You should have received a copy of the GNU General Public License and --
23 -- a copy of the GCC Runtime Library Exception along with this program; --
24 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
25 -- <http://www.gnu.org/licenses/>. --
27 -- This unit was originally developed by Matthew J Heaney. --
28 ------------------------------------------------------------------------------
30 with System; use type System.Address;
32 with Ada.Unchecked_Deallocation;
34 package body Ada.Containers.Doubly_Linked_Lists is
36 List_Iterator_Interfaces.Reversible_Iterator with record
37 Container : List_Access;
41 overriding function First (Object : Iterator) return Cursor;
42 overriding function Last (Object : Iterator) return Cursor;
44 overriding function Next
46 Position : Cursor) return Cursor;
48 overriding function Previous
50 Position : Cursor) return Cursor;
52 -----------------------
53 -- Local Subprograms --
54 -----------------------
56 procedure Free (X : in out Node_Access);
58 procedure Insert_Internal
59 (Container : in out List;
61 New_Node : Node_Access);
63 function Vet (Position : Cursor) return Boolean;
69 function "=" (Left, Right : List) return Boolean is
70 L : Node_Access := Left.First;
71 R : Node_Access := Right.First;
74 if Left'Address = Right'Address then
78 if Left.Length /= Right.Length then
82 for J in 1 .. Left.Length loop
83 if L.Element /= R.Element then
98 procedure Adjust (Container : in out List) is
99 Src : Node_Access := Container.First;
103 pragma Assert (Container.Last = null);
104 pragma Assert (Container.Length = 0);
105 pragma Assert (Container.Busy = 0);
106 pragma Assert (Container.Lock = 0);
110 pragma Assert (Container.First.Prev = null);
111 pragma Assert (Container.Last.Next = null);
112 pragma Assert (Container.Length > 0);
114 Container.First := null;
115 Container.Last := null;
116 Container.Length := 0;
120 Container.First := new Node_Type'(Src.Element, null, null);
121 Container.Last := Container.First;
122 Container.Length := 1;
125 while Src /= null loop
126 Container.Last.Next := new Node_Type'(Element => Src.Element,
127 Prev => Container.Last,
129 Container.Last := Container.Last.Next;
130 Container.Length := Container.Length + 1;
141 (Container : in out List;
142 New_Item : Element_Type;
143 Count : Count_Type := 1)
146 Insert (Container, No_Element, New_Item, Count);
153 procedure Clear (Container : in out List) is
157 if Container.Length = 0 then
158 pragma Assert (Container.First = null);
159 pragma Assert (Container.Last = null);
160 pragma Assert (Container.Busy = 0);
161 pragma Assert (Container.Lock = 0);
165 pragma Assert (Container.First.Prev = null);
166 pragma Assert (Container.Last.Next = null);
168 if Container.Busy > 0 then
169 raise Program_Error with
170 "attempt to tamper with cursors (list is busy)";
173 while Container.Length > 1 loop
174 X := Container.First;
175 pragma Assert (X.Next.Prev = Container.First);
177 Container.First := X.Next;
178 Container.First.Prev := null;
180 Container.Length := Container.Length - 1;
185 X := Container.First;
186 pragma Assert (X = Container.Last);
188 Container.First := null;
189 Container.Last := null;
190 Container.Length := 0;
192 pragma Warnings (Off);
194 pragma Warnings (On);
203 Item : Element_Type) return Boolean
206 return Find (Container, Item) /= No_Element;
214 (Container : in out List;
215 Position : in out Cursor;
216 Count : Count_Type := 1)
221 if Position.Node = null then
222 raise Constraint_Error with
223 "Position cursor has no element";
226 if Position.Container /= Container'Unrestricted_Access then
227 raise Program_Error with
228 "Position cursor designates wrong container";
231 pragma Assert (Vet (Position), "bad cursor in Delete");
233 if Position.Node = Container.First then
234 Delete_First (Container, Count);
235 Position := No_Element; -- Post-York behavior
240 Position := No_Element; -- Post-York behavior
244 if Container.Busy > 0 then
245 raise Program_Error with
246 "attempt to tamper with cursors (list is busy)";
249 for Index in 1 .. Count loop
251 Container.Length := Container.Length - 1;
253 if X = Container.Last then
254 Position := No_Element;
256 Container.Last := X.Prev;
257 Container.Last.Next := null;
263 Position.Node := X.Next;
265 X.Next.Prev := X.Prev;
266 X.Prev.Next := X.Next;
271 Position := No_Element; -- Post-York behavior
278 procedure Delete_First
279 (Container : in out List;
280 Count : Count_Type := 1)
285 if Count >= Container.Length then
294 if Container.Busy > 0 then
295 raise Program_Error with
296 "attempt to tamper with cursors (list is busy)";
299 for I in 1 .. Count loop
300 X := Container.First;
301 pragma Assert (X.Next.Prev = Container.First);
303 Container.First := X.Next;
304 Container.First.Prev := null;
306 Container.Length := Container.Length - 1;
316 procedure Delete_Last
317 (Container : in out List;
318 Count : Count_Type := 1)
323 if Count >= Container.Length then
332 if Container.Busy > 0 then
333 raise Program_Error with
334 "attempt to tamper with cursors (list is busy)";
337 for I in 1 .. Count loop
339 pragma Assert (X.Prev.Next = Container.Last);
341 Container.Last := X.Prev;
342 Container.Last.Next := null;
344 Container.Length := Container.Length - 1;
354 function Element (Position : Cursor) return Element_Type is
356 if Position.Node = null then
357 raise Constraint_Error with
358 "Position cursor has no element";
361 pragma Assert (Vet (Position), "bad cursor in Element");
363 return Position.Node.Element;
373 Position : Cursor := No_Element) return Cursor
375 Node : Node_Access := Position.Node;
379 Node := Container.First;
382 if Position.Container /= Container'Unrestricted_Access then
383 raise Program_Error with
384 "Position cursor designates wrong container";
387 pragma Assert (Vet (Position), "bad cursor in Find");
390 while Node /= null loop
391 if Node.Element = Item then
392 return Cursor'(Container'Unchecked_Access, Node);
405 function First (Container : List) return Cursor is
407 if Container.First = null then
411 return Cursor'(Container'Unchecked_Access, Container.First);
414 function First (Object : Iterator) return Cursor is
416 if Object.Container = null then
419 return (Object.Container, Object.Container.First);
427 function First_Element (Container : List) return Element_Type is
429 if Container.First = null then
430 raise Constraint_Error with "list is empty";
433 return Container.First.Element;
440 procedure Free (X : in out Node_Access) is
441 procedure Deallocate is
442 new Ada.Unchecked_Deallocation (Node_Type, Node_Access);
450 ---------------------
451 -- Generic_Sorting --
452 ---------------------
454 package body Generic_Sorting is
460 function Is_Sorted (Container : List) return Boolean is
461 Node : Node_Access := Container.First;
464 for I in 2 .. Container.Length loop
465 if Node.Next.Element < Node.Element then
480 (Target : in out List;
481 Source : in out List)
486 if Target'Address = Source'Address then
490 if Target.Busy > 0 then
491 raise Program_Error with
492 "attempt to tamper with cursors of Target (list is busy)";
495 if Source.Busy > 0 then
496 raise Program_Error with
497 "attempt to tamper with cursors of Source (list is busy)";
500 LI := First (Target);
501 RI := First (Source);
502 while RI.Node /= null loop
503 pragma Assert (RI.Node.Next = null
504 or else not (RI.Node.Next.Element <
507 if LI.Node = null then
508 Splice (Target, No_Element, Source);
512 pragma Assert (LI.Node.Next = null
513 or else not (LI.Node.Next.Element <
516 if RI.Node.Element < LI.Node.Element then
519 pragma Warnings (Off, RJ);
521 RI.Node := RI.Node.Next;
522 Splice (Target, LI, Source, RJ);
526 LI.Node := LI.Node.Next;
535 procedure Sort (Container : in out List) is
537 procedure Partition (Pivot : Node_Access; Back : Node_Access);
539 procedure Sort (Front, Back : Node_Access);
545 procedure Partition (Pivot : Node_Access; Back : Node_Access) is
546 Node : Node_Access := Pivot.Next;
549 while Node /= Back loop
550 if Node.Element < Pivot.Element then
552 Prev : constant Node_Access := Node.Prev;
553 Next : constant Node_Access := Node.Next;
559 Container.Last := Prev;
565 Node.Prev := Pivot.Prev;
569 if Node.Prev = null then
570 Container.First := Node;
572 Node.Prev.Next := Node;
588 procedure Sort (Front, Back : Node_Access) is
589 Pivot : constant Node_Access :=
590 (if Front = null then Container.First else Front.Next);
592 if Pivot /= Back then
593 Partition (Pivot, Back);
599 -- Start of processing for Sort
602 if Container.Length <= 1 then
606 pragma Assert (Container.First.Prev = null);
607 pragma Assert (Container.Last.Next = null);
609 if Container.Busy > 0 then
610 raise Program_Error with
611 "attempt to tamper with cursors (list is busy)";
614 Sort (Front => null, Back => null);
616 pragma Assert (Container.First.Prev = null);
617 pragma Assert (Container.Last.Next = null);
626 function Has_Element (Position : Cursor) return Boolean is
628 pragma Assert (Vet (Position), "bad cursor in Has_Element");
629 return Position.Node /= null;
637 (Container : in out List;
639 New_Item : Element_Type;
640 Position : out Cursor;
641 Count : Count_Type := 1)
643 New_Node : Node_Access;
646 if Before.Container /= null then
647 if Before.Container /= Container'Unrestricted_Access then
648 raise Program_Error with
649 "Before cursor designates wrong list";
652 pragma Assert (Vet (Before), "bad cursor in Insert");
660 if Container.Length > Count_Type'Last - Count then
661 raise Constraint_Error with "new length exceeds maximum";
664 if Container.Busy > 0 then
665 raise Program_Error with
666 "attempt to tamper with cursors (list is busy)";
669 New_Node := new Node_Type'(New_Item, null, null);
670 Insert_Internal (Container, Before.Node, New_Node);
672 Position := Cursor'(Container'Unchecked_Access, New_Node);
674 for J in Count_Type'(2) .. Count loop
675 New_Node := new Node_Type'(New_Item, null, null);
676 Insert_Internal (Container, Before.Node, New_Node);
681 (Container : in out List;
683 New_Item : Element_Type;
684 Count : Count_Type := 1)
687 pragma Unreferenced (Position);
689 Insert (Container, Before, New_Item, Position, Count);
693 (Container : in out List;
695 Position : out Cursor;
696 Count : Count_Type := 1)
698 New_Node : Node_Access;
701 if Before.Container /= null then
702 if Before.Container /= Container'Unrestricted_Access then
703 raise Program_Error with
704 "Before cursor designates wrong list";
707 pragma Assert (Vet (Before), "bad cursor in Insert");
715 if Container.Length > Count_Type'Last - Count then
716 raise Constraint_Error with "new length exceeds maximum";
719 if Container.Busy > 0 then
720 raise Program_Error with
721 "attempt to tamper with cursors (list is busy)";
724 New_Node := new Node_Type;
725 Insert_Internal (Container, Before.Node, New_Node);
727 Position := Cursor'(Container'Unchecked_Access, New_Node);
729 for J in Count_Type'(2) .. Count loop
730 New_Node := new Node_Type;
731 Insert_Internal (Container, Before.Node, New_Node);
735 ---------------------
736 -- Insert_Internal --
737 ---------------------
739 procedure Insert_Internal
740 (Container : in out List;
741 Before : Node_Access;
742 New_Node : Node_Access)
745 if Container.Length = 0 then
746 pragma Assert (Before = null);
747 pragma Assert (Container.First = null);
748 pragma Assert (Container.Last = null);
750 Container.First := New_Node;
751 Container.Last := New_Node;
753 elsif Before = null then
754 pragma Assert (Container.Last.Next = null);
756 Container.Last.Next := New_Node;
757 New_Node.Prev := Container.Last;
759 Container.Last := New_Node;
761 elsif Before = Container.First then
762 pragma Assert (Container.First.Prev = null);
764 Container.First.Prev := New_Node;
765 New_Node.Next := Container.First;
767 Container.First := New_Node;
770 pragma Assert (Container.First.Prev = null);
771 pragma Assert (Container.Last.Next = null);
773 New_Node.Next := Before;
774 New_Node.Prev := Before.Prev;
776 Before.Prev.Next := New_Node;
777 Before.Prev := New_Node;
780 Container.Length := Container.Length + 1;
787 function Is_Empty (Container : List) return Boolean is
789 return Container.Length = 0;
798 Process : not null access procedure (Position : Cursor))
800 C : List renames Container'Unrestricted_Access.all;
801 B : Natural renames C.Busy;
803 Node : Node_Access := Container.First;
809 while Node /= null loop
810 Process (Cursor'(Container'Unchecked_Access, Node));
822 function Iterate (Container : List)
823 return List_Iterator_Interfaces.Reversible_Iterator'class
826 if Container.Length = 0 then
827 return Iterator'(null, null);
829 return Iterator'(Container'Unchecked_Access, Container.First);
833 function Iterate (Container : List; Start : Cursor)
834 return List_Iterator_Interfaces.Reversible_Iterator'class
836 It : constant Iterator := (Container'Unchecked_Access, Start.Node);
845 function Last (Container : List) return Cursor is
847 if Container.Last = null then
851 return Cursor'(Container'Unchecked_Access, Container.Last);
854 function Last (Object : Iterator) return Cursor is
856 if Object.Container = null then
859 return (Object.Container, Object.Container.Last);
867 function Last_Element (Container : List) return Element_Type is
869 if Container.Last = null then
870 raise Constraint_Error with "list is empty";
873 return Container.Last.Element;
880 function Length (Container : List) return Count_Type is
882 return Container.Length;
890 (Target : in out List;
891 Source : in out List)
894 if Target'Address = Source'Address then
898 if Source.Busy > 0 then
899 raise Program_Error with
900 "attempt to tamper with cursors of Source (list is busy)";
905 Target.First := Source.First;
906 Source.First := null;
908 Target.Last := Source.Last;
911 Target.Length := Source.Length;
919 procedure Next (Position : in out Cursor) is
921 Position := Next (Position);
924 function Next (Position : Cursor) return Cursor is
926 if Position.Node = null then
930 pragma Assert (Vet (Position), "bad cursor in Next");
933 Next_Node : constant Node_Access := Position.Node.Next;
936 if Next_Node = null then
940 return Cursor'(Position.Container, Next_Node);
946 Position : Cursor) return Cursor
949 if Position.Node = Object.Container.Last then
952 return (Object.Container, Position.Node.Next);
961 (Container : in out List;
962 New_Item : Element_Type;
963 Count : Count_Type := 1)
966 Insert (Container, First (Container), New_Item, Count);
973 procedure Previous (Position : in out Cursor) is
975 Position := Previous (Position);
978 function Previous (Position : Cursor) return Cursor is
980 if Position.Node = null then
984 pragma Assert (Vet (Position), "bad cursor in Previous");
987 Prev_Node : constant Node_Access := Position.Node.Prev;
990 if Prev_Node = null then
994 return Cursor'(Position.Container, Prev_Node);
1000 Position : Cursor) return Cursor
1003 if Position.Node = Position.Container.First then
1006 return (Object.Container, Position.Node.Prev);
1014 procedure Query_Element
1016 Process : not null access procedure (Element : Element_Type))
1019 if Position.Node = null then
1020 raise Constraint_Error with
1021 "Position cursor has no element";
1024 pragma Assert (Vet (Position), "bad cursor in Query_Element");
1027 C : List renames Position.Container.all'Unrestricted_Access.all;
1028 B : Natural renames C.Busy;
1029 L : Natural renames C.Lock;
1036 Process (Position.Node.Element);
1054 (Stream : not null access Root_Stream_Type'Class;
1057 N : Count_Type'Base;
1062 Count_Type'Base'Read (Stream, N);
1071 Element_Type'Read (Stream, X.Element);
1082 Item.Length := Item.Length + 1;
1083 exit when Item.Length = N;
1088 Element_Type'Read (Stream, X.Element);
1095 X.Prev := Item.Last;
1096 Item.Last.Next := X;
1102 (Stream : not null access Root_Stream_Type'Class;
1106 raise Program_Error with "attempt to stream list cursor";
1110 (Stream : not null access Root_Stream_Type'Class;
1111 Item : out Reference_Type)
1114 raise Program_Error with "attempt to stream reference";
1118 (Stream : not null access Root_Stream_Type'Class;
1119 Item : out Constant_Reference_Type)
1122 raise Program_Error with "attempt to stream reference";
1129 function Constant_Reference (Container : List; Position : Cursor)
1130 return Constant_Reference_Type is
1132 pragma Unreferenced (Container);
1134 if Position.Container = null then
1135 raise Constraint_Error with "Position cursor has no element";
1138 return (Element => Position.Node.Element'Access);
1139 end Constant_Reference;
1141 function Reference (Container : List; Position : Cursor)
1142 return Reference_Type is
1144 pragma Unreferenced (Container);
1146 if Position.Container = null then
1147 raise Constraint_Error with "Position cursor has no element";
1150 return (Element => Position.Node.Element'Access);
1153 ---------------------
1154 -- Replace_Element --
1155 ---------------------
1157 procedure Replace_Element
1158 (Container : in out List;
1160 New_Item : Element_Type)
1163 if Position.Container = null then
1164 raise Constraint_Error with "Position cursor has no element";
1167 if Position.Container /= Container'Unchecked_Access then
1168 raise Program_Error with
1169 "Position cursor designates wrong container";
1172 if Container.Lock > 0 then
1173 raise Program_Error with
1174 "attempt to tamper with elements (list is locked)";
1177 pragma Assert (Vet (Position), "bad cursor in Replace_Element");
1179 Position.Node.Element := New_Item;
1180 end Replace_Element;
1182 ----------------------
1183 -- Reverse_Elements --
1184 ----------------------
1186 procedure Reverse_Elements (Container : in out List) is
1187 I : Node_Access := Container.First;
1188 J : Node_Access := Container.Last;
1190 procedure Swap (L, R : Node_Access);
1196 procedure Swap (L, R : Node_Access) is
1197 LN : constant Node_Access := L.Next;
1198 LP : constant Node_Access := L.Prev;
1200 RN : constant Node_Access := R.Next;
1201 RP : constant Node_Access := R.Prev;
1216 pragma Assert (RP = L);
1230 -- Start of processing for Reverse_Elements
1233 if Container.Length <= 1 then
1237 pragma Assert (Container.First.Prev = null);
1238 pragma Assert (Container.Last.Next = null);
1240 if Container.Busy > 0 then
1241 raise Program_Error with
1242 "attempt to tamper with cursors (list is busy)";
1245 Container.First := J;
1246 Container.Last := I;
1248 Swap (L => I, R => J);
1256 Swap (L => J, R => I);
1265 pragma Assert (Container.First.Prev = null);
1266 pragma Assert (Container.Last.Next = null);
1267 end Reverse_Elements;
1273 function Reverse_Find
1275 Item : Element_Type;
1276 Position : Cursor := No_Element) return Cursor
1278 Node : Node_Access := Position.Node;
1282 Node := Container.Last;
1285 if Position.Container /= Container'Unrestricted_Access then
1286 raise Program_Error with
1287 "Position cursor designates wrong container";
1290 pragma Assert (Vet (Position), "bad cursor in Reverse_Find");
1293 while Node /= null loop
1294 if Node.Element = Item then
1295 return Cursor'(Container'Unchecked_Access, Node);
1304 ---------------------
1305 -- Reverse_Iterate --
1306 ---------------------
1308 procedure Reverse_Iterate
1310 Process : not null access procedure (Position : Cursor))
1312 C : List renames Container'Unrestricted_Access.all;
1313 B : Natural renames C.Busy;
1315 Node : Node_Access := Container.Last;
1321 while Node /= null loop
1322 Process (Cursor'(Container'Unchecked_Access, Node));
1333 end Reverse_Iterate;
1340 (Target : in out List;
1342 Source : in out List)
1345 if Before.Container /= null then
1346 if Before.Container /= Target'Unrestricted_Access then
1347 raise Program_Error with
1348 "Before cursor designates wrong container";
1351 pragma Assert (Vet (Before), "bad cursor in Splice");
1354 if Target'Address = Source'Address
1355 or else Source.Length = 0
1360 pragma Assert (Source.First.Prev = null);
1361 pragma Assert (Source.Last.Next = null);
1363 if Target.Length > Count_Type'Last - Source.Length then
1364 raise Constraint_Error with "new length exceeds maximum";
1367 if Target.Busy > 0 then
1368 raise Program_Error with
1369 "attempt to tamper with cursors of Target (list is busy)";
1372 if Source.Busy > 0 then
1373 raise Program_Error with
1374 "attempt to tamper with cursors of Source (list is busy)";
1377 if Target.Length = 0 then
1378 pragma Assert (Target.First = null);
1379 pragma Assert (Target.Last = null);
1380 pragma Assert (Before = No_Element);
1382 Target.First := Source.First;
1383 Target.Last := Source.Last;
1385 elsif Before.Node = null then
1386 pragma Assert (Target.Last.Next = null);
1388 Target.Last.Next := Source.First;
1389 Source.First.Prev := Target.Last;
1391 Target.Last := Source.Last;
1393 elsif Before.Node = Target.First then
1394 pragma Assert (Target.First.Prev = null);
1396 Source.Last.Next := Target.First;
1397 Target.First.Prev := Source.Last;
1399 Target.First := Source.First;
1402 pragma Assert (Target.Length >= 2);
1404 Before.Node.Prev.Next := Source.First;
1405 Source.First.Prev := Before.Node.Prev;
1407 Before.Node.Prev := Source.Last;
1408 Source.Last.Next := Before.Node;
1411 Source.First := null;
1412 Source.Last := null;
1414 Target.Length := Target.Length + Source.Length;
1419 (Container : in out List;
1424 if Before.Container /= null then
1425 if Before.Container /= Container'Unchecked_Access then
1426 raise Program_Error with
1427 "Before cursor designates wrong container";
1430 pragma Assert (Vet (Before), "bad Before cursor in Splice");
1433 if Position.Node = null then
1434 raise Constraint_Error with "Position cursor has no element";
1437 if Position.Container /= Container'Unrestricted_Access then
1438 raise Program_Error with
1439 "Position cursor designates wrong container";
1442 pragma Assert (Vet (Position), "bad Position cursor in Splice");
1444 if Position.Node = Before.Node
1445 or else Position.Node.Next = Before.Node
1450 pragma Assert (Container.Length >= 2);
1452 if Container.Busy > 0 then
1453 raise Program_Error with
1454 "attempt to tamper with cursors (list is busy)";
1457 if Before.Node = null then
1458 pragma Assert (Position.Node /= Container.Last);
1460 if Position.Node = Container.First then
1461 Container.First := Position.Node.Next;
1462 Container.First.Prev := null;
1464 Position.Node.Prev.Next := Position.Node.Next;
1465 Position.Node.Next.Prev := Position.Node.Prev;
1468 Container.Last.Next := Position.Node;
1469 Position.Node.Prev := Container.Last;
1471 Container.Last := Position.Node;
1472 Container.Last.Next := null;
1477 if Before.Node = Container.First then
1478 pragma Assert (Position.Node /= Container.First);
1480 if Position.Node = Container.Last then
1481 Container.Last := Position.Node.Prev;
1482 Container.Last.Next := null;
1484 Position.Node.Prev.Next := Position.Node.Next;
1485 Position.Node.Next.Prev := Position.Node.Prev;
1488 Container.First.Prev := Position.Node;
1489 Position.Node.Next := Container.First;
1491 Container.First := Position.Node;
1492 Container.First.Prev := null;
1497 if Position.Node = Container.First then
1498 Container.First := Position.Node.Next;
1499 Container.First.Prev := null;
1501 elsif Position.Node = Container.Last then
1502 Container.Last := Position.Node.Prev;
1503 Container.Last.Next := null;
1506 Position.Node.Prev.Next := Position.Node.Next;
1507 Position.Node.Next.Prev := Position.Node.Prev;
1510 Before.Node.Prev.Next := Position.Node;
1511 Position.Node.Prev := Before.Node.Prev;
1513 Before.Node.Prev := Position.Node;
1514 Position.Node.Next := Before.Node;
1516 pragma Assert (Container.First.Prev = null);
1517 pragma Assert (Container.Last.Next = null);
1521 (Target : in out List;
1523 Source : in out List;
1524 Position : in out Cursor)
1527 if Target'Address = Source'Address then
1528 Splice (Target, Before, Position);
1532 if Before.Container /= null then
1533 if Before.Container /= Target'Unrestricted_Access then
1534 raise Program_Error with
1535 "Before cursor designates wrong container";
1538 pragma Assert (Vet (Before), "bad Before cursor in Splice");
1541 if Position.Node = null then
1542 raise Constraint_Error with "Position cursor has no element";
1545 if Position.Container /= Source'Unrestricted_Access then
1546 raise Program_Error with
1547 "Position cursor designates wrong container";
1550 pragma Assert (Vet (Position), "bad Position cursor in Splice");
1552 if Target.Length = Count_Type'Last then
1553 raise Constraint_Error with "Target is full";
1556 if Target.Busy > 0 then
1557 raise Program_Error with
1558 "attempt to tamper with cursors of Target (list is busy)";
1561 if Source.Busy > 0 then
1562 raise Program_Error with
1563 "attempt to tamper with cursors of Source (list is busy)";
1566 if Position.Node = Source.First then
1567 Source.First := Position.Node.Next;
1569 if Position.Node = Source.Last then
1570 pragma Assert (Source.First = null);
1571 pragma Assert (Source.Length = 1);
1572 Source.Last := null;
1575 Source.First.Prev := null;
1578 elsif Position.Node = Source.Last then
1579 pragma Assert (Source.Length >= 2);
1580 Source.Last := Position.Node.Prev;
1581 Source.Last.Next := null;
1584 pragma Assert (Source.Length >= 3);
1585 Position.Node.Prev.Next := Position.Node.Next;
1586 Position.Node.Next.Prev := Position.Node.Prev;
1589 if Target.Length = 0 then
1590 pragma Assert (Target.First = null);
1591 pragma Assert (Target.Last = null);
1592 pragma Assert (Before = No_Element);
1594 Target.First := Position.Node;
1595 Target.Last := Position.Node;
1597 Target.First.Prev := null;
1598 Target.Last.Next := null;
1600 elsif Before.Node = null then
1601 pragma Assert (Target.Last.Next = null);
1602 Target.Last.Next := Position.Node;
1603 Position.Node.Prev := Target.Last;
1605 Target.Last := Position.Node;
1606 Target.Last.Next := null;
1608 elsif Before.Node = Target.First then
1609 pragma Assert (Target.First.Prev = null);
1610 Target.First.Prev := Position.Node;
1611 Position.Node.Next := Target.First;
1613 Target.First := Position.Node;
1614 Target.First.Prev := null;
1617 pragma Assert (Target.Length >= 2);
1618 Before.Node.Prev.Next := Position.Node;
1619 Position.Node.Prev := Before.Node.Prev;
1621 Before.Node.Prev := Position.Node;
1622 Position.Node.Next := Before.Node;
1625 Target.Length := Target.Length + 1;
1626 Source.Length := Source.Length - 1;
1628 Position.Container := Target'Unchecked_Access;
1636 (Container : in out List;
1640 if I.Node = null then
1641 raise Constraint_Error with "I cursor has no element";
1644 if J.Node = null then
1645 raise Constraint_Error with "J cursor has no element";
1648 if I.Container /= Container'Unchecked_Access then
1649 raise Program_Error with "I cursor designates wrong container";
1652 if J.Container /= Container'Unchecked_Access then
1653 raise Program_Error with "J cursor designates wrong container";
1656 if I.Node = J.Node then
1660 if Container.Lock > 0 then
1661 raise Program_Error with
1662 "attempt to tamper with elements (list is locked)";
1665 pragma Assert (Vet (I), "bad I cursor in Swap");
1666 pragma Assert (Vet (J), "bad J cursor in Swap");
1669 EI : Element_Type renames I.Node.Element;
1670 EJ : Element_Type renames J.Node.Element;
1672 EI_Copy : constant Element_Type := EI;
1684 procedure Swap_Links
1685 (Container : in out List;
1689 if I.Node = null then
1690 raise Constraint_Error with "I cursor has no element";
1693 if J.Node = null then
1694 raise Constraint_Error with "J cursor has no element";
1697 if I.Container /= Container'Unrestricted_Access then
1698 raise Program_Error with "I cursor designates wrong container";
1701 if J.Container /= Container'Unrestricted_Access then
1702 raise Program_Error with "J cursor designates wrong container";
1705 if I.Node = J.Node then
1709 if Container.Busy > 0 then
1710 raise Program_Error with
1711 "attempt to tamper with cursors (list is busy)";
1714 pragma Assert (Vet (I), "bad I cursor in Swap_Links");
1715 pragma Assert (Vet (J), "bad J cursor in Swap_Links");
1718 I_Next : constant Cursor := Next (I);
1722 Splice (Container, Before => I, Position => J);
1726 J_Next : constant Cursor := Next (J);
1730 Splice (Container, Before => J, Position => I);
1733 pragma Assert (Container.Length >= 3);
1735 Splice (Container, Before => I_Next, Position => J);
1736 Splice (Container, Before => J_Next, Position => I);
1743 --------------------
1744 -- Update_Element --
1745 --------------------
1747 procedure Update_Element
1748 (Container : in out List;
1750 Process : not null access procedure (Element : in out Element_Type))
1753 if Position.Node = null then
1754 raise Constraint_Error with "Position cursor has no element";
1757 if Position.Container /= Container'Unchecked_Access then
1758 raise Program_Error with
1759 "Position cursor designates wrong container";
1762 pragma Assert (Vet (Position), "bad cursor in Update_Element");
1765 B : Natural renames Container.Busy;
1766 L : Natural renames Container.Lock;
1773 Process (Position.Node.Element);
1790 function Vet (Position : Cursor) return Boolean is
1792 if Position.Node = null then
1793 return Position.Container = null;
1796 if Position.Container = null then
1800 if Position.Node.Next = Position.Node then
1804 if Position.Node.Prev = Position.Node then
1809 L : List renames Position.Container.all;
1811 if L.Length = 0 then
1815 if L.First = null then
1819 if L.Last = null then
1823 if L.First.Prev /= null then
1827 if L.Last.Next /= null then
1831 if Position.Node.Prev = null
1832 and then Position.Node /= L.First
1837 -- If we get here, we know that this disjunction is true:
1838 -- Position.Node.Prev /= null or else Position.Node = L.First
1840 if Position.Node.Next = null
1841 and then Position.Node /= L.Last
1846 -- If we get here, we know that this disjunction is true:
1847 -- Position.Node.Next /= null or else Position.Node = L.Last
1849 if L.Length = 1 then
1850 return L.First = L.Last;
1853 if L.First = L.Last then
1857 if L.First.Next = null then
1861 if L.Last.Prev = null then
1865 if L.First.Next.Prev /= L.First then
1869 if L.Last.Prev.Next /= L.Last then
1873 if L.Length = 2 then
1874 if L.First.Next /= L.Last then
1878 if L.Last.Prev /= L.First then
1885 if L.First.Next = L.Last then
1889 if L.Last.Prev = L.First then
1893 -- Eliminate earlier disjunct
1895 if Position.Node = L.First then
1899 -- If we get here, we know (disjunctive syllogism) that this
1900 -- predicate is true: Position.Node.Prev /= null
1902 -- Eliminate earlier disjunct
1904 if Position.Node = L.Last then
1908 -- If we get here, we know (disjunctive syllogism) that this
1909 -- predicate is true: Position.Node.Next /= null
1911 if Position.Node.Next.Prev /= Position.Node then
1915 if Position.Node.Prev.Next /= Position.Node then
1919 if L.Length = 3 then
1920 if L.First.Next /= Position.Node then
1924 if L.Last.Prev /= Position.Node then
1938 (Stream : not null access Root_Stream_Type'Class;
1941 Node : Node_Access := Item.First;
1944 Count_Type'Base'Write (Stream, Item.Length);
1946 while Node /= null loop
1947 Element_Type'Write (Stream, Node.Element);
1953 (Stream : not null access Root_Stream_Type'Class;
1957 raise Program_Error with "attempt to stream list cursor";
1961 (Stream : not null access Root_Stream_Type'Class;
1962 Item : Reference_Type)
1965 raise Program_Error with "attempt to stream reference";
1969 (Stream : not null access Root_Stream_Type'Class;
1970 Item : Constant_Reference_Type)
1973 raise Program_Error with "attempt to stream reference";
1976 end Ada.Containers.Doubly_Linked_Lists;