/*
 * Copyright ©2026 Soham Pardeshi. All rights reserved.
 * Permission is hereby granted to students registered for University of
 * Washington CSE 333 for use solely during Summer Quarter 2026 for
 * purposes of the course. No other use, copying, distribution, or
 * modification is permitted without prior written consent. Copyrights
 * for third-party components of this work must be honored. Instructors
 * interested in reusing these course materials should contact the author.
 */

#include <stdio.h>     // for printf
#include <stdlib.h>    // for EXIT_SUCCESS
#include <inttypes.h>  // for uint8_t, PRIx8, etc.

// Size of data arrays
#define ARRAY_SIZE 11


// Copy len elements from source to dest, placing elements
// in dest in non-decreasing order.
void CopyAndSort(uint8_t source[], uint8_t dest[], int len);

// Given that arr[0..len-1] is sorted in non-decreasing order, add
// num to arr in the proper place so that arr[0..len] is sorted.
// precondition: len > 0.
void DoInsert(uint8_t num, uint8_t arr[], int len);

// Prints the parameter byte_len in decimal,
// the address held by the parameter data in hex,
// and byte_len bytes in hex starting at data.
void DumpBytes(void* data, int32_t byte_len);

// Note that we pass in sizeof(arr) / sizeof(uint8_t)
// since the sizeof(arr) is the length * sizeof(element)
int main(int argc, char* argv[]) {
  int32_t int_val = 1;
  float float_val = 1.0f;
  uint8_t arr_unsorted[] = {3, 2, 0, 8, 17, 6, 10, 7, 8, 1, 12};
  uint8_t arr_sorted[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

  DumpBytes(&int_val, sizeof(int_val));
  DumpBytes(&float_val, sizeof(float_val));
  DumpBytes(arr_unsorted, sizeof(arr_unsorted));
  CopyAndSort(arr_unsorted, arr_sorted, ARRAY_SIZE);
  DumpBytes(arr_sorted, sizeof(arr_sorted));

  return EXIT_SUCCESS;
}

void CopyAndSort(uint8_t source[], uint8_t dest[], int len) {
  // Note how this would only dump 8 bytes since sizeof(source)
  // is only 8 bytes, not the length of the array.
  DumpBytes(source, sizeof(source));

  // Deal with the degenerate case of a zero-length array
  // (nothing to do in that case)
  if (len == 0) {
    return;
  }

  // Insertion sort
  // Copy first element
  dest[0] = source[0];

  // Insert remaining entries in order in dest.
  for (int i = 1; i < len; i++) {
    DoInsert(source[i], dest, i);
  }
}

void DoInsert(uint8_t num, uint8_t arr[], int len) {
  // precondition: len > 0 && arr[0..len-1] sorted in non-decreasing order
  int i = len;
  // invariant: arr[0..i-1] not checked and arr[i+1..len] > num.
  while (i > 0 && arr[i - 1] > num) {
    arr[i] = arr[i - 1];
    i--;
  }
  // arr[0..i-1] <= num && arr[i+1..len] > num
  arr[i] = num;
}

void DumpBytes(void* data, int32_t byte_len) {
  uint8_t* ptr = (uint8_t*) data;
  printf("The %" PRId32 " bytes starting at 0x%" PRIxPTR " are: ",
         byte_len, (uintptr_t) data);

  for (int i = 0; i < byte_len; i++) {
    printf("%s%02" PRIx8, (i > 0 ? " " : ""), ptr[i]);
  }
  printf("\n");
}