，Fruit Store。
List Structure
In this project, you are asked to implement a sorted linked list structure to help a fruit store update its inventory. To simplify this task, we make the following assumptions:
- The store sells fruits by unit (e.g., an apple, a bunch of grapes, etc.) not by weight.
- Every type of fruit, regardless of its quantity on stock, is displayed in exactly one storage bin.
- Storage bins are numbered consecutively starting at 1, and as many bins as needed are available.
- The names of fruits from the input or passed as arguments to method calls will always be from the list given in Appendix A. (These names are in lower case English letters.)
A doubly-sorted list (DSL) consists of two doubly-linked lists (DLLs), which share the same set of nodes, and are sorted respectively by two different data fields. In the DSL, exactly one node N is created for every type of fruit currently on stock. Shown in the top row of Fig. 1, such a node has three data fields: fruit, quantity, and bin, which respectively store the name of the fruit (as a String object), its quantity in units, and the number of its storage bin. At the bottom of the figure displays two nodes with actual data values. They record 50 apples stored in bin 5, and 100 bunches of grapes in bin 8.
In addition to the three data fields, a node N also has two pairs of links: nextN and previousN, and nextB and previousB. The first pair locates the two nodes created for the fruits whose names immediately precede and succeed, in the alphabetical order, the name N.fruit of the fruit represented by N. All the nextN and previousN links thus form a doubly-linked list (DLL) which orders the nodes by fruit name. The list, referred to as the N-list, is accessed via a dummy node headN. Fig. 2 shows an N-list for four different types of fruits. Note that the last node (“pear”) has its nextN link reference the dummy node headN.
At the node N, the other two links nextB and previousB respectively reference the nodes for the fruits stored in the previous and next non-empty bins in the numerical order. For instance, suppose N references the “apple” node in Fig. 2. As the node shows, all apples are displayed in bin 5 at the fruit store. The last non-empty bin is bin 3, which stores pears, so the link N.previousB references the “pear” node. Meanwhile, the next non-empty bin is bin 8. Therefore, N.nextB references the “grape” node. All the nextB and previousB links induce a second DLL sorted by bin number. It is called the B-list accessed via a dummy node headB. Fig. 3 displays the B-list formed by the same four nodes from Fig. 2.
To distinguish between the N- and B-lists, all the nextN and previousN links will be colored green as in Fig. 2, while all the nextB and previousB links will be colored blue as in Fig. 3. The DSL is now displayed compactly in Fig. 4 by simply merging the two DLLs from Figs. 2 and 3.
Constructors
There are three constructors:
1
2
3
|
public DoublySortedList()
public DoublySortedList(String inventoryFile) throws FileNotFoundException
public DoublySortedList(int size, Node headN, Node headB)
|
The first one is a default constructor which initializes an empty DSL. Fruits will be added to the list later using addition methods introduced later. The second constructor builds a DSL over an inventory file, of which an example is given below:
pear 40 3 apple 50 5 banana 20 9 grape 100 8
An input inventory file is assumed to always meet the following format requirements such that there is no need to check for correctness of formatting:
- Fruits are listed on consecutive lines.
- Each line displays the name of a different fruit, its quantity, and the number of its storage bin, with at least one blank or tab in between.
As in the earlier example, the fruits on an inventory list may not be in the alphabetical order. In the first stage of construction, you are asked to scan the list and create a node over every scanned line. The node’s two pairs of links (nextN, previousN) and (nextB, previousB) are initialized to represent the order of the scan. The links headN and headB both reference the first created node. The scan creates two DLLs, neither of which is sorted at the moment.
In the second stage, an insertion sort is carried out on each DLL by the following method:
1
|
public void insertionSort(boolean sortNList, Comparatorlt;Nodegt; comp)
|
Two comparator classes, NameComparator and BinComparator, are provided for the insertion sorts by name and by bin number to construct the N- and the B-lists, respectively. Please note that sorting here is performed on the nodes. You cannot first put the fruit names or their bins in an array and then sort the array instead.
The third constructor has been implemented. It will be used for splitting a DSL into two (to be described in Section 6) and by the TA for testing.
Stocking Fruits
The list is updated whenever new fruits are stocked. Every new fruit type leads to the creation of a node. For compactness of display, all fruits of this type should be placed into the first empty bin by number.
Insertion
Addition of a fruit in some specified quantity is carried out by the following method:
1
|
public void add(String fruit, int n) throws IllegalArgumentException
|
It starts out with a sequential search in the N-list for fruit. Two possible situations may arise:
- The search finds a node N housing fruit, simply increase the N.quantity field by n. This is illustrated in Fig. 5 below.
- If no node for fruit is found after the search, the fruit is new on the stock. In this case, a new node is created to store the fruit in the first available bin. To illustrate, suppose that add(“orange”, 70) is executed on the DSL in Fig. 4. A search of the B-list f⁰††㱥⼠㹨ਠ㱦㹬㱬㵩≮∠㹮൵੭㱢㸠൳੨⁷†㱩㸩മ਼ ‾ ‼ 㱯㸍ഊ਼⁰‾⁎⁸⁴††㱴†㵴≯∭㹬൩ੳ⁴††⁴†⁂㱬㸠㱢㵴≷≬㹰ㅥ㱲⼠㹯㱤†⽩㹮㱳⽥㸨ഩਠ†⁴⁂
㰩⼮㹨ਠ⁴†⁴㰠⁴㵥≳∠㸦൬ⁱ⁵※…㱤㸻㰠†㴠≢≥㹮㰠…㴻≧≵㹯㰻†㵯∻≱㹵㱳⼬㹬㰠㴠≭≥㹴㱮⽥㹡⁴㰠㵡≰≲㹩㱴⽥㹡㱤†㴭≬≮㸠⡆‶⥥㰠⽴㹩㱮⽫㸠㱢⽥㹯㱶†⽡㹲㱥⼠㹫†⁷⁴††㱯⽳㹳മਠ⁆†‷†㱩⽳㹡൹ੳ†⁴㰠⽄㹴ੲ㰠⽡㹯൮ਠ㱯⽦㹥㱷⼠㹯㰠㹷♨㭩㱳⼠㹯൷ਠ㱲㹦 ††䉰†䅭⁴†⁹⁵⁵††䙡㡥⸠䅯Ⱐ†ⰼ ⁵䙲㥡㱳⼽㹨൩੧㱨㍩㴠≪∾㸍㱢⽬㌾㸍ഊਠ㰠㸠 †‾†††Ᵽ††⁰‼㩩㱮⽥㸾റ਼㰯㹰㱡 㵮∠∼㸯൳ੰ㱡㸠യਾ‼ ⁰㱥㸠ഠਠ†††††††‼㰯㸾ਊ††††††††††††㰼†㴽∢∍㸊ഠਠ††††††††††‼⁰㱲㹳㱰㵬≩∼㹳ㅰ㱡⽮㹳㱳⽵㹮㱣•㵮∠≳㸽㈢㱫⽥㹤㰢⽩㹶㱡⽴㹳൰‾†‼⁰†㱳⽳㹫⁷•‾⁶‼ 㱳㵡≮≳㹳ഽਢ⁴⁴•‾㱴㹳㱰㵬≡≰㹡㱲‾㴠≮≥㸠㱰†㵮≥≡㹮㱮⼾㸯‾㰼†㴽∢≳㹰㱬⽡㹫㱹•㵡≴≡㹮㱰⽡㹡㱳㴢∾≳㹰⡡ⱳ㰽㵳≥≡㹮㱰⽡㹡⤽㰢⽰㹳•㰾㴬∠≥㹶㰠⽮㸼 䥳䅳䕰㰾⼼㸾㰍†⼠㸠㰠†㵤∾∠㸠㰠 㴠∠≤㹹㱡⽢㸊‼㰯㴾∍≳㹰㰾⼍㹅㱣⁴㵮≳≮㹯㱥⽮㸠㱮†㵡≮∠㹶⡩⁴䙩⥲㰠⽳㹰㱥㴠≮≮㹫㱯⽭㹥⁶䙩䙮䕸Ⱞ‼䤯䄳䕳㰾⽒㹣㱫⽩㹨㰳 ⼼㹰㰾⽒㹬ൡੲ⁹†⁴†⁴㰠⽩㹲ੳ⁴†⁷㱩⽴㹦൲ੵ⁴†㱯⽦㹩൰੬㱥⼠㸮ഠ㱨⽩㹭㱰⽬㹭੮㱴㹤☠㭨㱥⼠㹯൬੬㱯㹩‼⠊⤼⁰⁵‽†⁶⁴†⁴⸠††††⁴‾⸠†Ⱐ‼⁰‱⁰㰠⼯㸼യੰ㱲㸾††‼††† †ⱥ‾⁰•‾⁰†•‽⁷‾㱣⼼㹳൰㱮㸠⡤⤢‾⁰⁰⁴‾⁴‼‽‾‼⠽⤢⡥⁷㍳⸼㈯⥳䅮⥮⁰㉬⁁⥧⁵⁅㌼ⸯ㉳⁰ ⰾ‼†††††⸾†⁹⡬⥥‾ ⁰⁰⸠䥦⁴㩥㰠⽢㸠൬੩㱮㸠൷੨†㱥㹨⁴††⡳⤠ⱱ⁵⁴⁴⁷††‼‼†⡥⤠⸠㰠⼵㹧൲⁰††㰠㸰‼ⴲ••⁵′ ‾†䥦⁵††⁴ⱩⰠ⁴†⁴⁹䱬⁰‼⁒⁒ ⸼㱰⼾㹥൲㰠⽡㸠൴㱯㉲㵶≡䥬ⵤⵢⴠ䵮≹㸠䥢‼‾䴼㱡⽳㈽㸢൨੩㱧㹬⁶ †⸍ 䔠††⁴†ⰽ•⁴ †‼‾Ɒ‼ⴲ‼‾††⁴⸠†Ⱒ†††‽•⠾‼ⱥ⁹⤼ⸯ㱳⽰㹮ാਠ㰼㍰㵣≬䥡ⵤⴼ䴯∼㹳䥰⁴䵥㱳⽰㍮㸾഼ੳ㱰㹮⁓†㨯㱳⽰㹮ാ਼㰯㹰㱡 㵮∠≳㹰ൡ੮㰠㸽ഢ੫⁹⁷㱲㹢൬੩‼ ⁰‾㰠㹰ൡ੮†‽•⁹⁷㱯•㴼∯∼㹳൰†‽•⁴⁴㱬㹲㱥‼㴾∼∠㹣ㅬ㱡⽳㹡㱲⼢㸾㰨㵳∽≷㹯㉲㱤⼢㸼㰯⽮㸾㰠‼㴾∠≮㸠㍣㱬⽡㹫㱥⽲㹤㰢⼾㹯൷ੳ‼ ⁰‾†⁉㱧⽡㹲൧ੵ⁴⁅⁸⁰⁴㱮㴯≳∼㹢൲ਠ ‾‼ ⁰‾ ††㰠㸠㰠‼㴊∠∠㸠㰠‾㴠∼∊㸼㰯㵦≩≰㸾㱮⽢㸯⁰㰾‾㵯≶≴㹳㰠⽳㹨㱮⁴㵮∠∭㹬㱨⼠㹮㱡㵲∠∠㹂⠭⥥㰠⽮㹲㰠⽢㹉㱦⼠㹭㱡㵥∠≯㹵㱮㵲≥≴㹨㰬⼠㹯㱡㵥∠∠㹃䥨㰀⼀㸀㰀 㴀∀∀㸀⠀⤀㰀⼀㸀㰀⼀㸀㰀 ⼀㸀㰀 㴀∀∀㸀㰀 㴀∀∀㸀㰀⼀㸀 㰀 㴀∀∀㸀䤀䈀㰀⼀㸀㰀 㴀∀∀㸀⠀⤀㰀⼀㸀㰀⼀㸀㰀⼀㸀㰀 ⼀㸀㰀⼀㸀ഀ 㰀⼀㸀ഀ 㰀⼀㸀ഀ 㰀⼀㸀ഀ㰀⼀㸀ഀ㰀⼀㸀㰀⼀㸀ഀ㰀㸀☀㬀㰀⼀㸀ഀ㰀㸀 ⸀ ⸀ 䠀 䐀䰀 䘀⸀ 㐀⸀㰀⼀㸀ഀ㰀㸀 ⸀㰀⼀㸀ഀ㰀㸀ഀ 㰀㸀䔀 ⴀ⸀㰀⼀㸀ഀ 㰀㸀 㘀 ⸀㰀⼀㸀ഀ㰀⼀㸀ഀ㰀㸀 ⠀ 䄀 䄀⤀⸀ 㨀㰀⼀㸀ഀ㰀㸀ഀ 㰀㸀 ㌀ ⸀㰀⼀㸀ഀ㰀⼀㸀ഀ㰀㸀 䤀䈀⠀⤀ ⸀㰀⼀㸀ഀ㰀㌀ 㴀∀ⴀ䴀∀㸀 䴀㰀⼀㌀㸀ഀ㰀㸀 㨀㰀⼀㸀ഀ㰀㸀㰀 㴀∀ ∀㸀ഀ㰀㸀ഀ 㰀㸀ഀ 㰀㸀ഀ 㰀 㴀∀∀㸀ഀ 㰀㸀㰀 㴀∀∀㸀㰀⼀㸀㰀 ⼀㸀㰀 㴀∀∀㸀㈀㰀⼀㸀㰀 ⼀㸀㰀⼀㸀ഀ 㰀⼀㸀ഀ 㰀 㴀∀∀㸀ഀ 㰀㸀㰀 㴀∀∀㸀㰀 㴀∀∀㸀㰀 㴀∀∀㸀㰀⼀㸀 㰀 㴀∀∀㸀㰀⼀㸀 㰀 㴀∀∀㸀㰀⼀㸀㰀 㴀∀∀㸀⠀⤀㰀⼀㸀㰀⼀㸀㰀 ⼀㸀㰀 㴀∀∀㸀㰀 㴀∀∀㸀㰀⼀㸀 㰀 㴀∀∀㸀㰀⼀㸀 㰀 㴀∀∀㸀㰀⼀㸀㰀 㴀∀∀㸀⠀⤀㰀⼀㸀㰀⼀㸀㰀⼀㸀㰀 ⼀㸀㰀⼀㸀ഀ 㰀⼀㸀ഀ 㰀⼀㸀ഀ 㰀⼀㸀ഀ㰀⼀㸀ഀ㰀⼀㸀㰀⼀㸀ഀ㰀㸀☀㬀㰀⼀㸀ഀ㰀㸀 Ⰰ Ⰰ ⸀ Ⰰ 䈀ⴀ⸀ 䘀⸀ ㈀ ⸀㰀⼀㸀ഀ㰀㸀 ⠀⤀ ⴀ 䈀ⴀ 䈀 ⸀㰀⼀㸀