A complete console storefront — admin panel, customer panel, cart, checkout, delivery routing, recommendations, persistence — where every single container is implemented from scratch. No std::vector, no std::map, no std::sort, no std::priority_queue. If the program needs a dynamic array, it grows one. If it needs a priority queue, it sifts a heap.
The original semester submission used a plain BST, a linked queue and a linked list. This edition rebuilds it around 14 data structures and 13 algorithms, each one reachable from the menus and labelled with the structure it exercises, so the program is also a live demo of the syllabus.
The headline fix: the original's
findProductByName()walked every node in the tree — O(n) — and its plain BST degenerated into a linked list the moment an admin entered IDs in ascending order. Here, name lookup is an O(1) hash probe and the catalogue is an AVL tree that cannot degenerate.
g++ -O2 -Wall -o Online_Store_Advanced.exe Online_Store_Advanced.cpp./Online_Store_Advanced.exeNo dependencies, no build system, single translation unit. Default admin PIN is 1234.
flowchart TB
subgraph UI["🖥️ Terminal Interface Layer"]
MENU["Boxed ANSI menus<br/>validated input · colour tables"]
end
subgraph ROLES["🔐 Role Layer"]
ADMIN["👤 Admin Panel<br/>inventory · analytics · undo"]
CUST["🛒 Customer Panel<br/>browse · cart · checkout"]
end
subgraph CORE["📦 Inventory — triple indexed"]
AVL["AVL Tree<br/><i>by product id</i><br/>O(log n)"]
HASH["Hash Table<br/><i>by name</i><br/>O(1) avg"]
TRIE["Trie<br/><i>by prefix</i><br/>O(len)"]
end
subgraph SUPPORT["⚙️ Supporting Structures"]
CART["Doubly Linked List<br/><i>shopping cart</i>"]
HEAP["Binary Heap<br/><i>Top-K · low stock</i>"]
STACK["Linked Stack<br/><i>undo history</i>"]
QUEUE["Linked Queue<br/><i>restock alerts</i>"]
LRU["LRU Cache<br/><i>recently viewed</i>"]
end
subgraph GRAPHS["🌐 Graph Layer"]
NET["Weighted Graph<br/><i>Dijkstra routing</i>"]
RECO["Co-purchase Graph<br/><i>BFS depth 2</i>"]
DSU["Disjoint Set<br/><i>product bundles</i>"]
end
subgraph DISK["💾 Persistence"]
FILES["Preorder serialisation<br/>store_*.txt"]
end
MENU --> ADMIN & CUST
ADMIN --> CORE & STACK & QUEUE
CUST --> CORE & CART & LRU
CART --> NET
CART --> RECO
ADMIN --> HEAP
CUST --> RECO
CORE --> DSU
CORE --> FILES
NET --> FILES
classDef core fill:#8B5CF6,stroke:#6D28D9,color:#fff,stroke-width:2px
classDef sup fill:#22D3EE,stroke:#0891B2,color:#083344,stroke-width:2px
classDef gph fill:#F472B6,stroke:#BE185D,color:#fff,stroke-width:2px
classDef ui fill:#1F2937,stroke:#8B5CF6,color:#E5E7EB,stroke-width:2px
class AVL,HASH,TRIE core
class CART,HEAP,STACK,QUEUE,LRU sup
class NET,RECO,DSU gph
class MENU,ADMIN,CUST,FILES ui
| # | Structure | Used for | Key operation | Complexity |
|---|---|---|---|---|
| 01 | Dynamic Array | generic storage everywhere | push with doubling growth |
O(1) amortised |
| 02 | AVL Tree | product catalogue by id | insert / delete / search | O(log n) |
| 03 | Hash Table | product & user lookup by name | separate chaining, auto rehash | O(1) average |
| 04 | Trie | prefix autocomplete | 37-way node, DFS collect | O(len) |
| 05 | Binary Heap | Top-K, low stock, Dijkstra | comparator-driven min/max | O(log n) |
| 06 | Linked Stack | admin undo history | LIFO push / pop | O(1) |
| 07 | Linked Queue | restock alerts, BFS frontier | FIFO enqueue / dequeue | O(1) |
| 08 | Doubly Linked List | shopping cart | remove given a node | O(1) |
| 09 | Circular Linked List | round-robin delivery agents | assign & advance | O(1) |
| 10 | Weighted Graph | delivery network | adjacency list | O(V + E) space |
| 11 | Co-purchase Graph | "customers also bought" | BFS to depth 2 | O(V + E) |
| 12 | Disjoint Set (DSU) | product bundles | path compression + rank | O(α(n)) ≈ O(1) |
| 13 | LRU Cache | recently viewed products | hash map + doubly linked list | O(1) get / put |
| 14 | Order BST | per-user order history | range query by order number | O(log n + k) |
| Algorithm | Where it runs | Complexity |
|---|---|---|
| AVL rotations (LL · RR · LR · RL) | every catalogue insert / delete | O(1) per rotation |
| Merge sort on a linked list | sort by name · stock · units sold | O(n log n) |
| Quick sort (Lomuto partition) | sort by price · rating | O(n log n) avg |
| Binary search | id lookup, benchmarked against AVL | O(log n) |
| BST range query with subtree pruning | id ranges, order-number ranges | O(log n + k) |
| Top-K via bounded min-heap | best sellers, low-stock alerts | O(n log k) |
| KMP string matching | keyword search across names | O(n + m) |
| BFS / DFS | delivery network traversal | O(V + E) |
| Dijkstra with binary min-heap | cheapest delivery route | O(E log V) |
| 0/1 Knapsack (dynamic programming) | best basket within a budget | O(n × W) |
| Greedy coin change | cash payment breakdown | O(d) |
| Union-Find (compression + rank) | product bundles | O(α(n)) |
| Preorder serialisation | saving / restoring the AVL to disk | O(n) |
An admin naturally enters product IDs in ascending order. A plain BST turns that into a linked list and every search becomes O(n). The AVL rebalances on the way back up the recursion, and stays logarithmic.
flowchart LR
subgraph BAD["❌ Plain BST — 15 sorted inserts · height 15"]
direction TB
b1["101"] --> b2["136"] --> b3["145"] --> b4["155"] --> b5["190"] --> b6["⋮<br/>height grows linearly"]
end
subgraph GOOD["✅ AVL Tree — same 15 inserts · height 5"]
direction TB
a1["234"] --> a2["136"]
a1 --> a3["512"]
a2 --> a4["101"]
a2 --> a5["155"]
a3 --> a6["320"]
a3 --> a7["610"]
a5 --> a8["145"]
a5 --> a9["190"]
a6 --> a10["288"]
a6 --> a11["407"]
a7 --> a12["555"]
a7 --> a13["733"]
end
classDef bad fill:#7F1D1D,stroke:#EF4444,color:#FEE2E2,stroke-width:2px
classDef good fill:#8B5CF6,stroke:#6D28D9,color:#fff,stroke-width:2px
class b1,b2,b3,b4,b5,b6 bad
class a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13 good
The Structure Statistics screen prints this live from the running program:
AVL Tree (products keyed by id)
----------------------------------
Nodes : 15
Height : 5
Leaves : 7
Balanced : YES
Rotations so far : 3
A plain BST fed sorted ids would be height 15; AVL keeps it near 4.
Hash Table (name -> product)
-------------------------------
Entries : 15 Load factor : 0.47
Buckets : 32 Longest chain : 3
sequenceDiagram
autonumber
participant C as 🛒 Cart<br/>(doubly linked list)
participant G as 🌐 Delivery Graph
participant H as 🎟️ Coupon Hash Table
participant P as 💵 Greedy Change
participant R as 🔗 Reco Graph + DSU
participant D as 💾 Disk
C->>C: re-validate stock against live inventory
C->>G: destination city
G->>G: Dijkstra from warehouse (min-heap)
G-->>C: shortest route · km · delivery cost
C->>H: coupon code
H-->>C: O(1) probe → % off / free delivery
C->>P: cash tendered
P-->>C: greedy note breakdown
C->>R: bump every co-purchase pair
R-->>R: strengthen edges + union bundles
C->>D: append order, decrement stock
Note over C,D: sold-out items auto-enqueue<br/>onto the admin restock queue
D-->>C: ✅ order #1001 confirmed
Warehouse sits in Islamabad. The highlighted path is the actual route the program computed for a Karachi delivery: 1525 km, $533.75, ETA 4 days.
flowchart LR
ISB(("🏭 Islamabad"))
RWP(("Rawalpindi"))
PEW(("Peshawar"))
LHR(("Lahore"))
FSD(("Faisalabad"))
GUJ(("Gujranwala"))
MUL(("Multan"))
SKR(("Sukkur"))
QTA(("Quetta"))
HYD(("Hyderabad"))
KHI(("🎯 Karachi"))
ISB ---|15| RWP
ISB ---|180| PEW
ISB ---|380| LHR
ISB ===|320| FSD
RWP ---|170| PEW
RWP ---|250| GUJ
LHR ---|180| FSD
LHR ---|80| GUJ
LHR ---|340| MUL
FSD ===|250| MUL
MUL ===|470| SKR
MUL ---|610| QTA
SKR ---|440| QTA
SKR ===|320| HYD
HYD ===|165| KHI
QTA ---|690| KHI
classDef path fill:#8B5CF6,stroke:#22D3EE,color:#fff,stroke-width:4px
classDef node fill:#1F2937,stroke:#4B5563,color:#E5E7EB
class ISB,FSD,MUL,SKR,HYD,KHI path
class RWP,PEW,LHR,GUJ,QTA node
👤 Admin panel
| Feature | Structure exercised |
|---|---|
| Add product | AVL insert + hash put + trie insert, all three indexes in sync |
| Delete product | AVL delete with in-order successor, then rebalance |
| Update price / stock | snapshot pushed onto the undo stack |
| Undo last action | linked stack, LIFO — restores adds, deletes, price and stock changes |
| Restock queue | FIFO queue auto-filled the moment an item sells out |
| Analytics | Top-5 best sellers via bounded min-heap, lowest stock via min-heap |
| Structure statistics | live AVL height / balance / rotations, hash load factor & collisions, trie nodes |
| ASCII tree printer | sideways render of the real AVL with height and balance factors |
| Product bundles | Union-Find with path compression |
| Coupons | hash table keyed by code |
| Delivery agents | circular linked list, round-robin assignment |
| Delivery network | graph viewer with BFS, DFS and Dijkstra |
🛒 Customer panel
| Feature | Structure exercised |
|---|---|
| Browse catalogue | 8 orderings — quick sort, merge sort on a linked list, AVL in-order, iterative in-order with an explicit stack |
| Six search methods | AVL O(log n) · hash O(1) · trie prefix · KMP keyword · BST price range · binary search |
| Shopping cart | doubly linked list — forward and backward traversal, O(1) line removal |
| Recommendations | co-purchase graph, BFS depth 2, direct hits score 1.0 and two-hop hits 0.4 |
| Budget shopping | 0/1 knapsack DP — maximises total star rating within your budget |
| Checkout | Dijkstra routing + coupon hash + greedy change + loyalty points |
| Order history | BST keyed on order number — exact search and range queries |
| Recently viewed | LRU cache, hash map + doubly linked list |
🔍 Six ways to find one product — and why that matters
Every search method reports its own cost, so you can compare them side by side on the same catalogue:
[ OK ] Found in 3 comparison(s) (tree height 5) ← AVL tree
[ OK ] Found after 1 chain step(s) - hash lookup, ← hash table
not a tree walk.
[ OK ] Binary search found it in 4 comparison(s) ← sorted array
over 15 items.
This is the single best screen to demo: the same lookup, three structures, three different cost profiles.
💾 Persistence — preorder serialisation
The AVL is written out in preorder so that reloading rebuilds a similarly shaped tree instead of a degenerate one. Orders carry their line items on following rows, and the co-purchase graph is rebuilt from order history on load.
store_products.txt 234|laptop|2000|3|computing|5|2
store_orders.txt ORDER|1001|1786450044|hassan|Karachi|Ali Raza|DSA10|4180|418|533.75|4295.75|2
LINE|234|laptop|2|2000
store_coupons.txt DSA10|10|0
store_config.txt admin pin + next order number
⚠️ The admin PIN is stored in plain text. This is a classroom demo of data structures, not an authentication system.
Boxed ANSI menus, auto-detected colour with a plain-text fallback, aligned tables with colour-coded stock levels, and star ratings.
+==================================================================+
| ONLINE STORE MANAGEMENT SYSTEM |
| 15 products in stock | 1 orders placed |
+==================================================================+
+------------------------------------------------------------------+
| Main menu |
+------------------------------------------------------------------+
| [1] Administrator |
| [2] Customer |
| [3] DSA showcase - what this project implements |
| [0] Exit |
+------------------------------------------------------------------+
ID NAME PRICE STOCK CATEGORY RATING SOLD
---------------------------------------------------------------------------
234 laptop $2000.00 3 computing ***** 2
320 monitor $450.00 6 computing ***** 0
512 headphone $500.00 3 audio ****. 0
Real checkout output from a test run:
Route: Islamabad -> Faisalabad -> Multan -> Sukkur -> Hyderabad -> Karachi (1525 km)
[ OK ] Coupon applied: 10% off
Subtotal $4180.00
Coupon DSA10 -$418.00
Delivery $533.75
TOTAL $4295.75
Change (greedy algorithm)
19 x $5000 1 x $500 2 x $100 3 x $1
| Original submission | Advanced edition | |
|---|---|---|
| Data structures | 3 | 14 |
| Algorithms | 0 named | 13 |
| Catalogue tree | plain BST, degenerates to O(n) |
AVL, guaranteed O(log n) |
| Search by name | full tree walk, O(n) |
hash table, O(1) average |
| Prefix search | none | trie autocomplete |
| Sorting | none | merge sort + quick sort, 8 orderings |
| Delivery | none | Dijkstra shortest path |
| Recommendations | none | co-purchase graph, BFS |
| Persistence | none | preorder serialisation to disk |
| Bad menu input | infinite loop | rejected and re-prompted |
| Memory | products, orders and users leaked | freed on exit |
| Re-login as customer | leaked the previous User |
account reused |
| Stock accounting | decremented when ordering — abandoned carts ate inventory | decremented at checkout only |
| Lines of code | 421 | 3,200 |
DSA/
├── Online_Store_Management_system.cpp # original submission — untouched
├── Online_Store_Advanced.cpp # this project · 3,200 lines · single file
├── Online Store Management system.pptx # presentation
└── README.md
Generated at runtime in the working directory: store_products.txt, store_orders.txt, store_coupons.txt, store_config.txt.
- No STL containers —
std::stringand streams only; every container hand-written - C++98 / C++03 safe — no
auto,nullptr, lambdas or range-for - Single translation unit — no build system, no dependencies
- Compiles clean under
-Wall— zero warnings on MinGW g++ 6.3 - Every input validated — the program cannot be crashed or hung from the menus
- No memory leaks — every structure owns and frees its own nodes
