dynset_trees.C

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
# include <iostream>
# include <iomanip>
# include <chrono>
# include <vector>
# include <algorithm>
# include <tclap/CmdLine.h>
# include <tpl_dynSetTree.H>
 
using namespace std;
using namespace Aleph;
 
// =============================================================================
// Type aliases for different tree implementations
// =============================================================================
 
// Standard trees (no rank support)
using AvlSet     = DynSetTree<int, Avl_Tree>;
using RbSet      = DynSetTree<int, Rb_Tree>;
using SplaySet   = DynSetTree<int, Splay_Tree>;
using TreapSet   = DynSetTree<int, Treap>;
using RandSet    = DynSetTree<int, Rand_Tree>;
 
// Ranked versions (support select(i) and position(x) operations)
// These trees maintain subtree sizes for O(log n) positional access
using AvlRkSet     = DynSetTree<int, Avl_Tree_Rk>;
using TreapRkSet   = DynSetTree<int, Treap_Rk>;
 
// Note: Other ranked trees exist (Rb_Tree_Rk, Splay_Tree_Rk) but have
// interface differences that may cause issues with DynSetTree wrapper
 
// =============================================================================
// Timing utilities
// =============================================================================
 
struct TimingResult
{
  string name;
  double insert_ms;
  double search_ms;
  double remove_ms;
  size_t height;
  size_t internal_path_length;
};
 
template <typename Set>
TimingResult benchmark_set(const string& name, const vector<int>& data, 
                           bool verbose)
{
  TimingResult result;
  result.name = name;
  
  Set set;
  
  // Benchmark insertions
  auto start = chrono::high_resolution_clock::now();
  for (int x : data)
    set.insert(x);
  auto end = chrono::high_resolution_clock::now();
  result.insert_ms = chrono::duration<double, milli>(end - start).count();
  
  // Get tree statistics
  result.height = computeHeightRec(set.get_root_node());
  result.internal_path_length = internal_path_length(set.get_root_node());
  
  // Benchmark searches (search all elements)
  start = chrono::high_resolution_clock::now();
  for (int x : data)
    {
      auto* p = set.search(x);
      if (p == nullptr)
        cerr << "ERROR: element " << x << " not found!" << endl;
    }
  end = chrono::high_resolution_clock::now();
  result.search_ms = chrono::duration<double, milli>(end - start).count();
  
  // Benchmark removals
  start = chrono::high_resolution_clock::now();
  for (int x : data)
    set.remove(x);
  end = chrono::high_resolution_clock::now();
  result.remove_ms = chrono::duration<double, milli>(end - start).count();
  
  if (set.size() != 0)
    cerr << "ERROR: set not empty after removals!" << endl;
  
  if (verbose)
    {
      cout << "  " << name << ":" << endl;
      cout << "    Height: " << result.height << endl;
      cout << "    Internal path length: " << result.internal_path_length << endl;
      cout << "    Avg path length: " << fixed << setprecision(2)
           << (double)result.internal_path_length / data.size() << endl;
    }
  
  return result;
}
 
// =============================================================================
// Demonstration of basic operations
// =============================================================================
 
void demonstrate_basic_operations()
{
  cout << "=== Basic Operations Demo ===" << endl << endl;
  
  // Using AVL tree as backend (the default)
  DynSetTree<int> avl_set;
  
  // Insert elements
  cout << "Inserting elements: 5, 3, 7, 1, 4, 6, 9" << endl;
  for (int x : {5, 3, 7, 1, 4, 6, 9})
    avl_set.insert(x);
  
  cout << "Set size: " << avl_set.size() << endl;
  cout << "Elements (in order): ";
  avl_set.for_each([](int x) { cout << x << " "; });
  cout << endl;
  
  // Search
  cout << endl << "Searching for 4: " 
       << (avl_set.search(4) ? "found" : "not found") << endl;
  cout << "Searching for 8: " 
       << (avl_set.search(8) ? "found" : "not found") << endl;
  
  // Contains
  cout << endl << "Contains 7: " << (avl_set.contains(7) ? "yes" : "no") << endl;
  cout << "Contains 10: " << (avl_set.contains(10) ? "yes" : "no") << endl;
  
  // Min/Max
  cout << endl << "Minimum: " << avl_set.min() << endl;
  cout << "Maximum: " << avl_set.max() << endl;
  
  // Remove
  cout << endl << "Removing 3..." << endl;
  avl_set.remove(3);
  cout << "Elements after removal: ";
  avl_set.for_each([](int x) { cout << x << " "; });
  cout << endl;
  
  cout << endl;
}
 
// =============================================================================
// Demonstration of different tree types
// =============================================================================
 
void demonstrate_tree_types()
{
  cout << "=== Different Tree Types Demo ===" << endl << endl;
  
  // Create sets with different backends
  AvlSet   avl;
  RbSet    rb;
  SplaySet splay;
  TreapSet treap;
  
  vector<int> data = {50, 25, 75, 10, 30, 60, 90, 5, 15, 27, 35};
  
  cout << "Inserting same data into different tree types:" << endl;
  cout << "Data: ";
  for (int x : data) cout << x << " ";
  cout << endl << endl;
  
  for (int x : data)
    {
      avl.insert(x);
      rb.insert(x);
      splay.insert(x);
      treap.insert(x);
    }
  
  cout << "Tree heights (lower is better balanced):" << endl;
  cout << "  AVL:    " << computeHeightRec(avl.get_root_node()) << endl;
  cout << "  RB:     " << computeHeightRec(rb.get_root_node()) << endl;
  cout << "  Splay:  " << computeHeightRec(splay.get_root_node()) << endl;
  cout << "  Treap:  " << computeHeightRec(treap.get_root_node()) << endl;
  
  // Note: Splay tree changes structure on every access
  cout << endl << "After searching for 5, 10, 15 (watch Splay change):" << endl;
  splay.search(5);
  splay.search(10);
  splay.search(15);
  cout << "  Splay height after searches: " 
       << computeHeightRec(splay.get_root_node()) << endl;
  cout << "  (Splay moves accessed elements toward root)" << endl;
  
  cout << endl;
}
 
// =============================================================================
// Demonstration of ranked operations
// =============================================================================
 
void demonstrate_ranked_operations()
{
  cout << "=== Ranked Operations Demo ===" << endl << endl;
  
  cout << "Ranked trees maintain subtree sizes, enabling O(log n) operations:" << endl;
  cout << "  select(i)   - get i-th smallest element (0-indexed)" << endl;
  cout << "  position(x) - get rank/position of element x" << endl << endl;
  
  cout << "Available ranked tree types:" << endl;
  cout << "  - Avl_Tree_Rk : AVL with rank (strictly balanced, deterministic)" << endl;
  cout << "  - Treap_Rk    : Treap with rank (randomized balance)" << endl << endl;
  
  // Demonstrate with ranked tree types
  AvlRkSet   avl_rk;
  TreapRkSet treap_rk;
  
  vector<int> data = {100, 50, 150, 25, 75, 125, 175, 10, 200};
  
  for (int x : data)
    {
      avl_rk.insert(x);
      treap_rk.insert(x);
    }
  
  cout << "Set contents (sorted): ";
  avl_rk.for_each([](int x) { cout << x << " "; });
  cout << endl << endl;
  
  // Show select operation
  cout << "Positional access - select(i) returns i-th element:" << endl;
  cout << "  Index  AVL_Rk  Treap_Rk" << endl;
  cout << "  -----  ------  --------" << endl;
  for (size_t i = 0; i < avl_rk.size(); ++i)
    {
      cout << "    " << i << "     "
           << setw(4) << avl_rk.select(i) << "      "
           << setw(4) << treap_rk.select(i) << endl;
    }
  
  // Show position operation
  cout << endl << "Element ranks - position(x) returns index of x:" << endl;
  cout << "  Value  AVL_Rk  Treap_Rk" << endl;
  cout << "  -----  ------  --------" << endl;
  for (int x : {10, 50, 100, 150, 200})
    {
      cout << "   " << setw(3) << x << "      "
           << avl_rk.position(x) << "         "
           << treap_rk.position(x) << endl;
    }
  
  // Demonstrate practical use: find median
  cout << endl << "Practical use - Finding median in O(log n):" << endl;
  size_t mid = avl_rk.size() / 2;
  cout << "  Median (middle element): " << avl_rk.select(mid) << endl;
  
  // Find k-th percentile
  size_t p25 = avl_rk.size() / 4;
  size_t p75 = 3 * avl_rk.size() / 4;
  cout << "  25th percentile: " << avl_rk.select(p25) << endl;
  cout << "  75th percentile: " << avl_rk.select(p75) << endl;
  
  // Count elements less than a value
  cout << endl << "Count elements < 100: " << avl_rk.position(100) << endl;
  
  cout << endl;
}
 
// =============================================================================
// Demonstration of functional programming features
// =============================================================================
 
void demonstrate_functional_features()
{
  cout << "=== Functional Programming Features ===" << endl << endl;
  
  DynSetTree<int> set;
  for (int i = 1; i <= 10; ++i)
    set.insert(i);
  
  cout << "Original set: ";
  set.for_each([](int x) { cout << x << " "; });
  cout << endl << endl;
  
  // Filter: keep only even numbers
  auto evens = set.filter([](int x) { return x % 2 == 0; });
  cout << "Filter (even): ";
  evens.for_each([](int x) { cout << x << " "; });
  cout << endl;
  
  // Map: square each element (returns DynList)
  auto squares = set.template maps<int>([](int x) { return x * x; });
  cout << "Map (square): ";
  squares.for_each([](int x) { cout << x << " "; });
  cout << endl;
  
  // Fold: sum all elements
  int sum = set.template foldl<int>(0, [](int acc, int x) { return acc + x; });
  cout << "Fold (sum): " << sum << endl;
  
  // All/Exists predicates
  cout << endl << "Predicates:" << endl;
  cout << "  All positive? " << (set.all([](int x) { return x > 0; }) ? "yes" : "no") << endl;
  cout << "  Exists > 5? " << (set.exists([](int x) { return x > 5; }) ? "yes" : "no") << endl;
  cout << "  All <= 10? " << (set.all([](int x) { return x <= 10; }) ? "yes" : "no") << endl;
  
  cout << endl;
}
 
// =============================================================================
// Performance comparison
// =============================================================================
 
void run_performance_comparison(size_t n, unsigned int seed, bool verbose)
{
  cout << "=== Performance Comparison ===" << endl;
  cout << "Testing with " << n << " elements (seed: " << seed << ")" << endl << endl;
 
  if (n == 0)
    {
      cout << "Nothing to benchmark: n=0\n\n";
      return;
    }
  
  // Generate random data
  srand(seed);
  vector<int> data;
  data.reserve(n);
  for (size_t i = 0; i < n; ++i)
    data.push_back(rand());
  
  // Remove duplicates (sets don't allow them)
  sort(data.begin(), data.end());
  data.erase(unique(data.begin(), data.end()), data.end());
 
  if (data.empty())
    {
      cout << "Nothing to benchmark: all generated keys collapsed to an empty set\n\n";
      return;
    }
  
  // Shuffle for random insertion order
  for (size_t i = data.size(); i > 1; --i)
    swap(data[i - 1], data[rand() % i]);
  
  cout << "Actual unique elements: " << data.size() << endl << endl;
  
  // Run benchmarks - Standard trees
  vector<TimingResult> results;
  
  cout << "Standard trees (no rank support):" << endl;
  results.push_back(benchmark_set<AvlSet>("AVL Tree", data, verbose));
  results.push_back(benchmark_set<RbSet>("Red-Black Tree", data, verbose));
  results.push_back(benchmark_set<SplaySet>("Splay Tree", data, verbose));
  results.push_back(benchmark_set<TreapSet>("Treap", data, verbose));
  results.push_back(benchmark_set<RandSet>("Rand Tree", data, verbose));
  
  cout << endl << "Ranked trees (with select/position support):" << endl;
  results.push_back(benchmark_set<AvlRkSet>("AVL_Rk", data, verbose));
  results.push_back(benchmark_set<TreapRkSet>("Treap_Rk", data, verbose));
  
  // Print results table
  cout << endl;
  cout << left << setw(18) << "Tree Type"
       << right << setw(12) << "Insert(ms)"
       << setw(12) << "Search(ms)"
       << setw(12) << "Remove(ms)"
       << setw(10) << "Height"
       << setw(15) << "Avg Path" << endl;
  cout << string(79, '-') << endl;
  
  for (const auto& r : results)
    {
      cout << left << setw(18) << r.name
           << right << fixed << setprecision(2)
           << setw(12) << r.insert_ms
           << setw(12) << r.search_ms
           << setw(12) << r.remove_ms
           << setw(10) << r.height
           << setw(15) << setprecision(2) 
           << (double)r.internal_path_length / data.size() << endl;
    }
  
  cout << endl;
  cout << "Notes:" << endl;
  cout << "  - Height: tree height (log2(" << data.size() << ") ~= " 
       << fixed << setprecision(1) << log2(data.size()) << ")" << endl;
  cout << "  - Avg Path: average path length from root (ideal ~= log2(n))" << endl;
  cout << "  - Splay tree optimizes for access patterns, not balance" << endl;
  cout << "  - _Rk variants have slight overhead for maintaining subtree sizes" << endl;
  cout << "  - Use _Rk trees when you need select(i) or position(x) operations" << endl;
  cout << endl;
}
 
// =============================================================================
// Main
// =============================================================================
 
int main(int argc, char* argv[])
{
  try
    {
      TCLAP::CmdLine cmd(
        "Demonstration of DynSetTree with different BST implementations.\n"
        "Shows how Aleph-w allows swapping data structure implementations\n"
        "through template parameters.",
        ' ', "1.0");
 
      TCLAP::ValueArg<size_t> nArg("n", "count",
                                    "Number of elements for performance test",
                                    false, 100000, "size_t");
      cmd.add(nArg);
 
      TCLAP::ValueArg<unsigned int> seedArg("s", "seed",
                                             "Random seed (0 = use time)",
                                             false, 0, "unsigned int");
      cmd.add(seedArg);
 
      TCLAP::SwitchArg allArg("a", "all",
                               "Run all demonstrations (not just performance)",
                               false);
      cmd.add(allArg);
 
      TCLAP::SwitchArg verboseArg("v", "verbose",
                                   "Show detailed tree statistics",
                                   false);
      cmd.add(verboseArg);
 
      cmd.parse(argc, argv);
 
      size_t n = nArg.getValue();
      unsigned int seed = seedArg.getValue();
      bool runAll = allArg.getValue();
      bool verbose = verboseArg.getValue();
 
      if (seed == 0)
        seed = time(nullptr);
 
      cout << "DynSetTree - Multiple BST Implementations Demo" << endl;
      cout << "==============================================" << endl << endl;
 
      if (runAll)
        {
          demonstrate_basic_operations();
          demonstrate_tree_types();
          demonstrate_ranked_operations();
          demonstrate_functional_features();
        }
 
      run_performance_comparison(n, seed, verbose);
 
      cout << "Done." << endl;
    }
  catch (TCLAP::ArgException& e)
    {
      cerr << "Error: " << e.error() << " for arg " << e.argId() << endl;
      return 1;
    }
 
  return 0;
}