SortedList

The <#8132#>SortedList<#8132#> class is a straightforward adaptation of <#8133#>List<#8133#> in which elements are inserted in order and searches are peformed more efficiently. <#8134#>SortedList<#8134#> is currently the default set implementation (see Page~#sec:set#8124>). As stated above in Section~#sec:container#8125>, the copy construction and assignment operations work the same way with any combination of <#8135#>SimpleContainer<#8135#> objects. The interaction between <#8136#>List<#8136#> and <#8137#>SortedList<#8137#> in Figure~#fig:List4#8126> provides our first example of this. <#8127#>
Figure 2.6: <#8246#>List<#8246#> and <#8247#>SortedList<#8247#>
#figure8127#

<#8127#> Note that the invariant of lexicographically-ordered storage of elements in <#8248#>SortedList<#8248#> is never violated, despite the unordered source <#8249#>List<#8249#>. Like assignment and initialization, comparison of <#8250#>Containers<#8250#> is consistent despite <#8251#>Container<#8251#> type. Unlike assignment and initialization, though, comparison is consistent accross both <#8252#>SimpleContainer<#8252#> and <#8253#>Dictionary<#8253#> objects. For an example, consider the code given in Figure~#fig:List5#8244>. <#8245#>
Figure 2.7: Comparisons of <#8268#>Containers<#8268#>
#figure8245#

<#8245#> The preceding example is interesting because it illustrates comparisons between elements which happen to be <#8269#>List<#8269#> and <#8270#>SortedList<#8270#> objects. Remember that two objects of class <#8271#>Container<#8271#> or <#8272#>Collection<#8272#> are considered to be equivalent if they contain equivalent objects in equivalent order. Nested iteration is used above to consider all possible comparison between three given lists. In order for the iteration scheme to work, <#8273#>Container<#8273#> pointers must have access through the virtual function mechanism to the <#8266#>iterate()<#8266#> method of each class in the <#8274#>Container<#8274#> hierarchy. This means that <#8275#>SortedList<#8275#> must declare <#8276#>List<#8276#> as a 60 base class even though private inheritance would be more natural. Therefore, <#8277#>SortedList<#8277#> must redefine certain inherited member functions to maintain the invariant that elements are stored in lexicographic order. The <#8278#>List<#8278#> methods listed in Section~#sec:list#8267> are inherited by <#8279#>SortedList<#8279#>; only those redefined are listed below. <#8280#>1. Creation<#8280#>


<#8282#>
<#8284#>
Figure 2.7: Comparisons of <#8268#>Containers<#8268#>
SortedList<#8308#>;SPMlt;<#8308#>Item<#8310#>;SPMgt;<#8310#> l;
<#8284#>
<#8288#>
Construct a singly-linked sorted list <#8312#>l<#8312#>.

<#8288#>

<#8282#>

<#8293#>
<#8295#>
SortedList<#8314#>;SPMlt;<#8314#>Item<#8316#>;SPMgt;<#8316#> l2(l);
<#8295#>
<#8299#>
Construct a singly-linked list <#8318#>l2<#8318#> and initialize it with the elements of <#8320#>l<#8320#> such that the elements of the new list are in lexicographic order. If <#8322#>l<#8322#> is an instance of a container other than a <#8304#>SortedList<#8304#>, then a sorted insertion routine must be used to load the elements, leading to <#8324#>O(n2)<#8324#> time. If <#8326#>l<#8326#> is a <#8305#>SortedList<#8305#>, then elements are appended to the end of <#8328#>l2<#8328#>, yielding <#8330#>O(n)<#8330#> time.

<#8299#>

<#8293#>

<#8306#>2. Operations<#8306#>


<#8336#>
<#8338#>
List<#8472#>;SPMlt;<#8472#>Item<#8474#>;SPMgt;<#8474#>& operator=(Container<#8476#>;SPMlt;<#8476#>Item<#8478#>;SPMgt;<#8478#>& list)
<#8338#>
<#8343#>
If the current list is different from the passed list, then remove any elements in the current list and iterate through the elements of the passed list, inserting them in the lexicographic order. <#8480#>O(n2)<#8480#>

<#8343#>

<#8336#>

<#8348#>
<#8350#>
List<#8482#>;SPMlt;<#8482#>Item<#8484#>;SPMgt;<#8484#>& operator=(SortedList<#8486#>;SPMlt;<#8486#>Item<#8488#>;SPMgt;<#8488#>& list)
<#8350#>
<#8355#>
If the current list is different from the passed list, then remove any elements in the current list and iterate through the elements of the passed list, appending them in the same order onto the end of the current list. <#8490#>O(n)<#8490#>

<#8355#>

<#8348#>

<#8360#>
<#8362#>
Bool memberQ(Item& item)
<#8362#>
<#8367#>
Indicate whether item is in list or not. Do not proceed if <#8369#>item<#8369#> is less than the current item <#8492#>O(n)<#8492#>

<#8367#>

<#8360#>

<#8373#>
<#8375#>
Bool sortedQ() const
<#8375#>
<#8380#>
Return TRUE. <#8494#>O(1)<#8494#>.

<#8380#>

<#8373#>

<#8385#>
<#8387#>
ContainerNode* search(Item& item)
<#8387#>
<#8392#>
Search for item and return a pointer to the node which contains it. Do not proceed if <#8394#>item<#8394#> is less than the current item. <#8496#>O(n)<#8496#>

<#8392#>

<#8385#>

<#8398#>
<#8400#>
ContainerNode* prepend(Item item)
<#8400#>
<#8405#>
Insert the item at the beginning of list if no order violation would occur. Otherwise warn of an attempted order violation and return NULL. <#8498#>O(1)<#8498#>

<#8405#>

<#8398#>

<#8410#>
<#8412#>
ContainerNode* insert(Item item)
<#8412#>
<#8417#>
Insert the item in lexicographically sorted order. <#8500#>O(n)<#8500#>

<#8417#>

<#8410#>

<#8422#>
<#8424#>
ContainerNode* append(Item item)
<#8424#>
<#8429#>
Append the item to the back of list if no order violation would occur. <#8502#>O(n)<#8502#>

<#8429#>

<#8422#>

<#8434#>
<#8436#>
ContainerNode* insertBefore(Item item, ContainerNode *n)
<#8436#>
<#8441#>
Insert the item before node n if no order violation would occur. Otherwise warn the user and return. <#8504#>O(1)<#8504#>

<#8441#>

<#8434#>

<#8446#>
<#8448#>
ContainerNode* insertAfter(Item item, ContainerNode *n)
<#8448#>
<#8453#>
Insert the item after node n if no order violation would occur. Otherwise warn the user and return. <#8506#>O(1)<#8506#>

<#8453#>

<#8446#>