Category Archives: Tutorials

Here comes the sun lalala

Block diagrams in practice without formalin

The block diagram is a visual tool that helps to turn a complex algorithm into an understandable and structured sequence of actions. From programming to business process management, they serve as a universal language for visualization, analysis and optimization of the most complex systems.

Imagine a map where instead of roads is logic, and instead of cities – actions. This is a block diagram-an indispensable tool for navigation in the most confusing processes.

Example 1: Simplified game launching scheme
To understand the principle of work, let’s present a simple game launch scheme.

This scheme shows the perfect script when everything happens without failures. But in real life, everything is much more complicated.

Example 2: Expanded scheme for starting the game with data loading
Modern games often require Internet connection to download user data, saving or settings. Let’s add these steps to our scheme.

This scheme is already more realistic, but what will happen if something goes wrong?

How was it: a game that “broke” with the loss of the Internet

At the start of the project, developers could not take into account all possible scenarios. For example, they focused on the main logic of the game and did not think what would happen if the player has an Internet connection.

In such a situation, the block diagram of their code would look like this:

In this case, instead of issuing an error or closing correctly, the game froze at the stage of waiting for data that she did not receive due to the lack of a connection. This led to the “black screen” and freezing the application.

How it became: Correction on user complaints

After numerous users’ complaints about hovering, the developer team realized that we needed to correct the error. They made changes to the code by adding an error processing unit that allows the application to respond correctly to the lack of connection.

This is what the corrected block diagram looks like, where both scenarios are taken into account:

Thanks to this approach, the game now correctly informs the user about the problem, and in some cases it can even go to offline mode, allowing you to continue the game. This is a good example of why block diagrams are so important : they make the developer think not only about the ideal way of execution, but also about all possible failures, making the final product much more stable and reliable.

Uncertain behavior

Hanging and errors are just one examples of unpredictable behavior of the program. In programming, there is a concept of uncertain behavior (undefined behavior) – this is a situation where the standard of the language does not describe how the program should behave in a certain case.

This can lead to anything: from random “garbage” in the withdrawal to the failure of the program or even serious security vulnerability. Indefinite behavior often occurs when working with memory, for example, with lines in the language of C.

An example from the language C:

Imagine that the developer copied the line into the buffer, but forgot to add to the end the zero symbol (`\ 0`) , which marks the end of the line.

This is what the code looks like:

#include 

int main() {
char buffer[5];
char* my_string = "hello";

memcpy(buffer, my_string, 5);

printf("%s\n", buffer);
return 0;
}

Expected result: “Hello”
The real result is unpredictable.

Why is this happening? The `Printf` function with the specifier`%S` expects that the line ends with a zero symbol. If he is not, she will continue to read the memory outside the highlighted buffer.

Here is the block diagram of this process with two possible outcomes:

This is a clear example of why the block diagrams are so important: they make the developer think not only about the ideal way of execution, but also about all possible failures, including such low-level problems, making the final product much more stable and reliable.

Pixel Perfect: myth or reality in the era of declarativeness?

In the world of interfaces development, there is a common concept – “Pixel Perfect in the Lodge” . It implies the most accurate reproduction of the design machine to the smallest pixel. For a long time it was a gold standard, especially in the era of a classic web design. However, with the arrival of the declarative mile and the rapid growth of the variety of devices, the principle of “Pixel Perfect” is becoming more ephemeral. Let’s try to figure out why.

Imperial Wysiwyg vs. Declarative code: What is the difference?

Traditionally, many interfaces, especially desktop, were created using imperative approaches or Wysiwyg (What You See is What You Get) of editors. In such tools, the designer or developer directly manipulates with elements, placing them on canvas with an accuracy to the pixel. It is similar to working with a graphic editor – you see how your element looks, and you can definitely position it. In this case, the achievement of “Pixel Perfect” was a very real goal.

However, modern development is increasingly based on declarative miles . This means that you do not tell the computer to “put this button here”, but describe what you want to get. For example, instead of indicating the specific coordinates of the element, you describe its properties: “This button should be red, have 16px indentations from all sides and be in the center of the container.” Freimvorki like React, Vue, Swiftui or Jetpack Compose just use this principle.

Why “Pixel Perfect” does not work with a declarative mile for many devices

Imagine that you create an application that should look equally good on the iPhone 15 Pro Max, Samsung Galaxy Fold, iPad Pro and a 4K resolution. Each of these devices has different screen resolution, pixel density, parties and physical sizes.

When you use the declarative approach, the system itself decides how to display your described interface on a particular device, taking into account all its parameters. You set the rules and dependencies, not harsh coordinates.

* Adaptability and responsiveness: The main goal of the declarative miles is to create adaptive and responsive interfaces . This means that your interface should automatically adapt to the size and orientation of the screen without breaking and maintaining readability. If we sought to “Pixel Perfect” on each device, we would have to create countless options for the same interface, which will completely level the advantages of the declarative approach.
* Pixel density (DPI/PPI): The devices have different pixel density. The same element with the size of 100 “virtual” pixels on a device with high density will look much smaller than on a low -density device, if you do not take into account the scaling. Declarative frameworks are abstracted by physical pixels, working with logical units.
* Dynamic content: Content in modern applications is often dynamic – its volume and structure may vary. If we tattered hard to the pixels, any change in text or image would lead to the “collapse” of the layout.
* Various platforms: In addition to the variety of devices, there are different operating systems (iOS, Android, Web, Desktop). Each platform has its own design, standard controls and fonts. An attempt to make an absolutely identical, Pixel Perfect interface on all platforms would lead to an unnatural type and poor user experience.

The old approaches did not go away, but evolved

It is important to understand that the approach to interfaces is not a binary choice between “imperative” and “declarative”. Historically, for each platform there were its own tools and approaches to the creation of interfaces.

* Native interface files: for iOS it were XIB/Storyboards, for Android-XML marking files. These files are a Pixel-PERFECT WYSIWYG layout, which is then displayed in the radio as in the editor. This approach has not disappeared anywhere, it continues to develop, integrating with modern declarative frames. For example, Swiftui in Apple and Jetpack Compose in Android set off on the path of a purely declarative code, but at the same time retained the opportunity to use a classic layout.
* hybrid solutions: Often in real projects, a combination of approaches is used. For example, the basic structure of the application can be implemented declaratively, and for specific, requiring accurate positioning of elements, lower -level, imperative methods can be used or native components developed taking into account the specifics of the platform.

from monolith to adaptability: how the evolution of devices formed a declarative mile

The world of digital interfaces has undergone tremendous changes over the past decades. From stationary computers with fixed permits, we came to the era of exponential growth of the variety of user devices . Today, our applications should work equally well on:

* smartphones of all form factors and screen sizes.
* tablets with their unique orientation modes and a separated screen.
* laptops and desktops with various permits of monitors.
* TVs and media centers , controlled remotely. It is noteworthy that even for TVs, the remarks of which can be simple as Apple TV Remote with a minimum of buttons, or vice versa, overloaded with many functions, modern requirements for interfaces are such that the code should not require specific adaptation for these input features. The interface should work “as if by itself”, without an additional description of what “how” to interact with a specific remote control.
* smart watches and wearable devices with minimalistic screens.
* Virtual reality helmets (VR) , requiring a completely new approach to a spatial interface.
* Augmented reality devices (AR) , applying information on the real world.
* automobile information and entertainment systems .
* And even household appliances : from refrigerators with sensory screens and washing machines with interactive displays to smart ovens and systems of the Smart House.

Each of these devices has its own unique features: physical dimensions, parties ratio, pixel density, input methods (touch screen, mouse, controllers, gestures, vocal commands) and, importantly, the subtleties of the user environment . For example, a VR shlesh requires deep immersion, and a smartphone-fast and intuitive work on the go, while the refrigerator interface should be as simple and large for quick navigation.

Classic approach: The burden of supporting individual interfaces

In the era of the dominance of desktops and the first mobile devices, the usual business was the creation and support of of individual interface files or even a completely separate interface code for each platform .

* Development under iOS often required the use of Storyboards or XIB files in XCode, writing code on Objective-C or SWIFT.
* For Android the XML marking files and the code on Java or Kotlin were created.
* Web interfaces turned on HTML/CSS/JavaScript.
* For C ++ applications on various desktop platforms, their specific frameworks and tools were used:
* In Windows these were MFC (Microsoft Foundation Classes), Win32 API with manual drawing elements or using resource files for dialog windows and control elements.
* Cocoa (Objective-C/Swift) or the old Carbon API for direct control of the graphic interface were used in macos .
* In linux/unix-like systems , libraries like GTK+ or QT were often used, which provided their set of widgets and mechanisms for creating interfaces, often via XML-like marking files (for example, .ui files in Qt Designer) or direct software creation of elements.

This approach ensured maximum control over each platform, allowing you to take into account all its specific features and native elements. However, he had a huge drawback: duplication of efforts and tremendous costs for support . The slightest change in design or functionality required the introduction of a right to several, in fact, independent code bases. This turned into a real nightmare for developer teams, slowing down the output of new functions and increasing the likelihood of errors.

declarative miles: a single language for diversity

It was in response to this rapid complication that the declarative miles appeared as the dominant paradigm. Framws like react, vue, swiftui, jetpack compose and others are not just a new way of writing code, but a fundamental shift in thinking.

The main idea of the declarative approach : Instead of saying the system “how” to draw every element (imperative), we describe “what“ we want to see (declarative). We set the properties and condition of the interface, and the framework decides how to best display it on a particular device.

This became possible thanks to the following key advantages:

1. Abstraction from the details of the platform: declarative fraimvorki are specially designed to forget about low -level details of each platform. The developer describes the components and their relationships at a higher level of abstraction, using a single, transferred code.
2. Automatic adaptation and responsiveness: Freimvorki take responsibility for automatic scaling, changing the layout and adaptation of elements to different sizes of screens, pixel density and input methods. This is achieved through the use of flexible layout systems, such as Flexbox or Grid, and concepts similar to “logical pixels” or “DP”.
3. consistency of user experience: Despite the external differences, the declarative approach allows you to maintain a single logic of behavior and interaction throughout the family of devices. This simplifies the testing process and provides more predictable user experience.
4. Acceleration of development and cost reduction: with the same code capable of working on many platforms, significantly is reduced by the time and cost of development and support . Teams can focus on functionality and design, and not on repeated rewriting the same interface.
5. readiness for the future: the ability to abstract from the specifics of current devices makes the declarative code more more resistant to the emergence of new types of devices and form factors . Freimvorki can be updated to support new technologies, and your already written code will receive this support is relatively seamless.

Conclusion

The declarative mile is not just a fashion trend, but the necessary evolutionary step caused by the rapid development of user devices, including the sphere of the Internet of things (IoT) and smart household appliances. It allows developers and designers to create complex, adaptive and uniform interfaces, without drowning in endless specific implementations for each platform. The transition from imperative control over each pixel to the declarative description of the desired state is a recognition that in the world of the future interfaces should be flexible, transferred and intuitive regardless of which screen they are displayed.

Programmers, designers and users need to learn how to live in this new world. The extra details of the Pixel Perfect, designed to a particular device or resolution, lead to unnecessary time costs for development and support. Moreover, such harsh layouts may simply not work on devices with non-standard interfaces, such as limited input TVs, VR and AR shifts, as well as other devices of the future, which we still do not even know about today. Flexibility and adaptability – these are the keys to the creation of successful interfaces in the modern world.

Vibe-core tricks: why LLM still does not work with Solid, Dry and Clean

With the development of large language models (LLM), such as ChatGPT, more and more developers use them to generate code, design architecture and accelerate integration. However, with practical application, it becomes noticeable: the classical principles of architecture – Solid, Dry, Clean – get along poorly with the peculiarities of the LLM codgendation.

This does not mean that the principles are outdated – on the contrary, they work perfectly with manual development. But with LLM the approach has to be adapted.

Why llm cannot cope with architectural principles

encapsulation

Incapsulation requires understanding the boundaries between parts of the system, knowledge about the intentions of the developer, as well as follow strict access restrictions. LLM often simplifies the structure, make fields public for no reason or duplicate the implementation. This makes the code more vulnerable to errors and violates the architectural boundaries.

Abstracts and interfaces

Design patterns, such as an abstract factory or strategy, require a holistic view of the system and understanding its dynamics. Models can create an interface without a clear purpose without ensuring its implementation, or violate the connection between layers. The result is an excess or non -functional architecture.

Dry (Donolt Repeat Yourself)

LLM do not seek to minimize the repeating code – on the contrary, it is easier for them to duplicate blocks than to make general logic. Although they can offer refactoring on request, by default models tend to generate “self -sufficient” fragments, even if it leads to redundancy.

Clean Architecture

Clean implies a strict hierarchy, independence from frameworks, directed dependence and minimal connectedness between layers. The generation of such a structure requires a global understanding of the system – and LLM work at the level of probability of words, not architectural integrity. Therefore, the code is mixed, with violation of the directions of dependence and a simplified division into levels.

What works better when working with LLM

Wet instead of Dry
The WET (Write EVERYTHING TWICE) approach is more practical in working with LLM. Duplication of code does not require context from the model of retention, which means that the result is predictable and is easier to correctly correct. It also reduces the likelihood of non -obvious connections and bugs.

In addition, duplication helps to compensate for the short memory of the model: if a certain fragment of logic is found in several places, LLM is more likely to take it into account with further generation. This simplifies accompaniment and increases resistance to “forgetting”.

Simple structures instead of encapsulation

Avoiding complex encapsulation and relying on the direct transmission of data between the parts of the code, you can greatly simplify both generation and debugging. This is especially true with a quick iterative development or creation of MVP.

Simplified architecture

A simple, flat structure of the project with a minimum amount of dependencies and abstractions gives a more stable result during generation. The model adapts such a code easier and less often violates the expected connections between the components.

SDK integration – manually reliable

Most language models are trained on outdated versions of documentation. Therefore, when generating instructions for installing SDK, errors often appear: outdated commands, irrelevant parameters or links to inaccessible resources. Practice shows: it is best to use official documentation and manual tuning, leaving LLM an auxiliary role – for example, generating a template code or adaptation of configurations.

Why are the principles still work – but with manual development

It is important to understand that the difficulties from Solid, Dry and Clean concern the codhegeneration through LLM. When the developer writes the code manually, these principles continue to demonstrate their value: they reduce connectedness, simplify support, increase the readability and flexibility of the project.

This is due to the fact that human thinking is prone to generalization. We are looking for patterns, we bring repeating logic into individual entities, create patterns. Probably, this behavior has evolutionary roots: reducing the amount of information saves cognitive resources.

LLM act differently: they do not experience loads from the volume of data and do not strive for savings. On the contrary, it is easier for them to work with duplicate, fragmented information than to build and maintain complex abstractions. That is why it is easier for them to cope with the code without encapsulation, with repeating structures and minimal architectural severity.

Conclusion

Large language models are a useful tool in development, especially in the early stages or when creating an auxiliary code. But it is important to adapt the approach to them: to simplify the architecture, limit abstraction, avoid complex dependencies and not rely on them when configuring SDK.

The principles of Solid, Dry and Clean are still relevant-but they give the best effect in the hands of a person. When working with LLM, it is reasonable to use a simplified, practical style that allows you to get a reliable and understandable code that is easy to finalize manually. And where LLM forgets – duplication of code helps him to remember.

Porting Surreal Engine C++ to WebAssembly

In this post I will describe how I ported the Surreal Engine game engine to WebAssembly.

Surreal Engine is a game engine that implements most of the functionality of the Unreal Engine 1 engine, famous games on this engine are Unreal Tournament 99, Unreal, Deus Ex, Undying. It belongs to the classic engines that worked mainly in a single-threaded execution environment.

My initial idea was to take on a project that I couldn’t complete in any reasonable amount of time, thus showing my Twitch followers that there are projects that even I can’t do. On my very first stream, I suddenly realized that the task of porting Surreal Engine C++ to WebAssembly using Emscripten was doable.

Surreal Engine Emscripten Demo

A month later I can show my fork and assembly of the engine on WebAssembly:
https://demensdeum.com/demos/SurrealEngine/

The controls are the same as in the original, using the keyboard arrows. Next, I plan to adapt it to mobile controls (touch), add correct lighting and other graphic features of the Unreal Tournament 99 render.

Where to start?

The first thing I want to say is that any project can be ported from C++ to WebAssembly using Emscripten, the only question is how complete the functionality will be. Choose a project whose library ports are already available for Emscripten, in the case of Surreal Engine, you are very lucky, because the engine uses the SDL 2, OpenAL libraries – they are both ported to Emscripten. However, Vulkan is used as a graphics API, which is currently not available for HTML5, work is underway to implement WebGPU, but it is also in the draft stage, and it is also unknown how simple the further port from Vulkan to WebGPU will be, after its full standardization. Therefore, I had to write my own basic OpenGL-ES / WebGL renderer for Surreal Engine.

Building the project

The build system in Surreal Engine is CMake, which also simplifies porting, since Emscripten provides its own native builders – emcmake, emmake.
The Surreal Engine port was based on the code of my last game on WebGL/OpenGL ES and C++ called Death-Mask, because of this the development went much easier, all the necessary build flags were with me, code examples.

One of the most important points in CMakeLists.txt is the build flags for Emscripten, below is an example from the project file:


-s MAX_WEBGL_VERSION=2 \

-s EXCEPTION_DEBUG \

-fexceptions \

--preload-file UnrealTournament/ \

--preload-file SurrealEngine.pk3 \

--bind \

--use-preload-plugins \

-Wall \

-Wextra \

-Werror=return-type \

-s USE_SDL=2 \

-s ASSERTIONS=1 \

-w \

-g4 \

-s DISABLE_EXCEPTION_CATCHING=0 \

-O3 \

--no-heap-copy \

-s ALLOW_MEMORY_GROWTH=1 \

-s EXIT_RUNTIME=1")

The build script itself:


emmake make -j 16

cp SurrealEngine.data /srv/http/SurrealEngine/SurrealEngine.data

cp SurrealEngine.js /srv/http/SurrealEngine/SurrealEngine.js

cp SurrealEngine.wasm /srv/http/SurrealEngine/SurrealEngine.wasm

cp ../buildScripts/Emscripten/index.html /srv/http/SurrealEngine/index.html

cp ../buildScripts/Emscripten/background.png /srv/http/SurrealEngine/background.png

Next, we’ll prepare index.html, which includes the project file system preloader. For posting on the web, I used Unreal Tournament Demo version 338. As you can see from the CMake file, the unpacked game folder was added to the build directory and linked as a preload-file for Emscripten.

Major code changes

Then it was necessary to change the game loop, you can’t run an infinite loop, it leads to the browser freezing, instead you need to use emscripten_set_main_loop, I wrote about this feature in my 2017 note “Porting SDL C++ game to HTML5 (Emscripten)”
We change the code for the condition for exiting the while loop to if, then we output the main class of the game engine, which contains the game loop, to the global scope, and write a global function that will call the step of the game loop from the global object:


#include <emscripten.h>

Engine *EMSCRIPTEN_GLOBAL_GAME_ENGINE = nullptr;

void emscripten_game_loop_step() {

	EMSCRIPTEN_GLOBAL_GAME_ENGINE->Run();

}

#endif

After this, you need to make sure that there are no background threads in the application. If there are, then get ready to rewrite them for single-thread execution, or use the phtread library in Emscripten.
The background thread in Surreal Engine is used to play music, the main thread of the engine receives data about the current track, about the need to play music, or its absence, then the background thread via mutex receives a new state and starts playing new music, or pauses. The background thread is also used to buffer music during playback.
My attempts to build Surreal Engine under Emscripten with pthread were unsuccessful, because the SDL2 and OpenAL ports were built without pthread support, and I did not want to rebuild them for the sake of music. Therefore, I moved the background music thread functionality to single-thread execution using a loop. Having removed pthread calls from the C++ code, I moved buffering, music playback to the main thread, so that there were no delays, I increased the buffer by several seconds.

Next I will describe specific implementations of graphics and sound.

Vulkan is not supported!

Yes, Vulkan is not supported in HTML5, although all the advertising brochures point out cross-platform and wide support on platforms as the main advantage of Vulkan. For this reason, I had to write my own basic graphics renderer for a simplified type of OpenGL – ES, it is used on mobile devices, sometimes does not contain fashionable features of modern OpenGL, but it is very well transferred to WebGL, this is what Emscripten implements. Writing a basic tile renderer, bsp rendering, for the simplest display of GUI, and drawing models + maps, was possible in two weeks. This was probably the most difficult part of the project. There is still a lot of work ahead to implement the full functionality of the Surreal Engine rendering, so any help from readers in the form of code and pull requests is welcome.

OpenAL is supported!

It was a great stroke of luck that Surreal Engine uses OpenAL for audio output. After writing a simple hello world in OpenAL and building it in WebAssembly using Emscripten, it became clear to me how simple it all is, and I set out to port the audio.
After several hours of debugging, it became obvious that there are several bugs in the OpenAL implementation of Emscripten, for example, when initializing the reading of the number of mono channels, the method returned an infinite number, and after trying to initialize a vector of infinite size, C++ crashes with the exception vector::length_error.
This was circumvented by hardcoding the number of mono channels to 2048:


		alcGetIntegerv(alDevice, ALC_STEREO_SOURCES, 1, &stereoSources);



#if __EMSCRIPTEN__

		monoSources = 2048; // for some reason Emscripten's OpenAL gives infinite monoSources count, bug?

#endif

Is there a network?

Surreal Engine currently does not support network play, play with bots is supported, but someone is needed to write AI for these bots. Theoretically, it is possible to implement network play on WebAssembly/Emscripten using Websockets.

Conclusion

In conclusion, I would like to say that porting Surreal Engine turned out to be quite smooth due to the use of libraries for which there are Emscripten ports, as well as my previous experience implementing a game in C++ for WebAssembly on Emscripten. Below are links to sources of knowledge, repositories on the topic.
M-M-M-MONSTER KILL!

Also, if you want to help the project, preferably with WebGL/OpenGL ES render code, then write to me in Telegram:
https://t.me/demenscave

Links

https://demensdeum.com/demos/SurrealEngine/
https://github.com/demensdeum/SurrealEngine-Emscripten

https://github.com/dpjudas/SurrealEngine

Turn on USB keyboard backlight on macOS

Recently bought a very inexpensive Getorix GK-45X USB keyboard with RGB backlighting. After connecting it to a MacBook Pro with an M1 processor, it became clear that the RGB backlighting was not working. Even pressing the magic combination Fn + Scroll Lock did not turn on the backlighting, only the level of the MacBook screen backlighting changed.
There are several solutions to this problem, namely OpenRGB (does not work), HID LED Test (does not work). Only the kvmswitch utility worked:
https://github.com/stoutput/OSX-KVM

You need to download it from GitHub and allow it to run from the terminal in the Security panel of the System Settings.
As I understood from the description, after launching the utility sends a press of Fn + Scroll Lock, thus turning on/off the backlight on the keyboard.

Tree sort

Tree sort – sorting by binary search tree. Time complexity – O(n²). In such a tree, each node has numbers on the left less than the node, on the right greater than the node, when coming from the root and printing values ​​from left to right, we get a sorted list of numbers. Amazing, right?

Let’s consider the binary search tree diagram:

Derrick Coetzee (public domain)

Try manually reading the numbers starting from the second to last left node in the lower left corner, for each node on the left – a node on the right.

It will look like this:

  1. The second to last node on the bottom left is 3.
  2. It has a left branch – 1.
  3. We take this number (1)
  4. Next we take the vertex itself 3 (1, 3)
  5. On the right is branch 6, but it contains branches. Therefore, we read it in the same way.
  6. Left branch of node 6 is number 4 (1, 3, 4)
  7. The node itself is 6 (1, 3, 4, 6)
  8. Right 7 (1, 3, 4, 6, 7)
  9. We go up to the root node – 8 (1,3, 4,6, 7, 8)
  10. Print everything on the right by analogy
  11. We get the final list – 1, 3, 4, 6, 7, 8, 10, 13, 14

To implement the algorithm in code, two functions are required:

  1. Building a Binary Search Tree
  2. Print out the binary search tree in the correct order

A binary search tree is assembled in the same way as it is read, each node is assigned a number on the left or right, depending on whether it is smaller or larger.

Example in Lua:


function Node:new(value, lhs, rhs)
    output = {}
    setmetatable(output, self)
    self.__index = self  
    output.value = value
    output.lhs = lhs
    output.rhs = rhs
    output.counter = 1
    return output  
end

function Node:Increment()
    self.counter = self.counter + 1
end

function Node:Insert(value)
    if self.lhs ~= nil and self.lhs.value > value then
        self.lhs:Insert(value)
        return
    end

    if self.rhs ~= nil and self.rhs.value < value then
        self.rhs:Insert(value)
        return
    end

    if self.value == value then
        self:Increment()
        return
    elseif self.value > value then
        if self.lhs == nil then
            self.lhs = Node:new(value, nil, nil)
        else
            self.lhs:Insert(value)
        end
        return
    else
        if self.rhs == nil then
            self.rhs = Node:new(value, nil, nil)
        else
            self.rhs:Insert(value)
        end
        return
    end
end

function Node:InOrder(output)
    if self.lhs ~= nil then
       output = self.lhs:InOrder(output)
    end
    output = self:printSelf(output)
    if self.rhs ~= nil then
        output = self.rhs:InOrder(output)
    end
    return output
end

function Node:printSelf(output)
    for i=0,self.counter-1 do
        output = output .. tostring(self.value) .. " "
    end
    return output
end

function PrintArray(numbers)
    output = ""
    for i=0,#numbers do
        output = output .. tostring(numbers[i]) .. " "
    end    
    print(output)
end

function Treesort(numbers)
    rootNode = Node:new(numbers[0], nil, nil)
    for i=1,#numbers do
        rootNode:Insert(numbers[i])
    end
    print(rootNode:InOrder(""))
end


numbersCount = 10
maxNumber = 9

numbers = {}

for i=0,numbersCount-1 do
    numbers[i] = math.random(0, maxNumber)
end

PrintArray(numbers)
Treesort(numbers)

Важный нюанс что для чисел которые равны вершине придумано множество интересных механизмов подцепления к ноде, я же просто добавил счетчик к классу вершины, при распечатке числа возвращаются по счетчику.

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/treesort

Источники

TreeSort Algorithm Explained and Implemented with Examples in Java | Sorting Algorithms | Geekific – YouTube

Tree sort – YouTube

Convert Sorted Array to Binary Search Tree (LeetCode 108. Algorithm Explained) – YouTube

Sorting algorithms/Tree sort on a linked list – Rosetta Code

Tree Sort – GeeksforGeeks

Tree sort – Wikipedia

How to handle duplicates in Binary Search Tree? – GeeksforGeeks

Tree Sort | GeeksforGeeks – YouTube

Bucket Sort

Bucket Sort – sorting by buckets. The algorithm is similar to counting sort, with the difference that the numbers are collected in “buckets”-ranges, then the buckets are sorted using any other, sufficiently productive, sorting algorithm, and the final chord is the unfolding of the “buckets” one by one, resulting in a sorted list.

The algorithm’s time complexity is O(nk). The algorithm works in linear time for data that obeys a uniform distribution law. To put it simply, the elements must be in a certain range, without “spikes”, for example, numbers from 0.0 to 1.0. If among such numbers there are 4 or 999, then such a series is no longer considered “even” according to the yard laws.

Example of implementation in Julia:

    buckets = Vector{Vector{Int}}()
    
    for i in 0:bucketsCount - 1
        bucket = Vector{Int}()
        push!(buckets, bucket)
    end

    maxNumber = maximum(numbers)

    for i in 0:length(numbers) - 1
        bucketIndex = 1 + Int(floor(bucketsCount * numbers[1 + i] / (maxNumber + 1)))
        push!(buckets[bucketIndex], numbers[1 + i])
    end

    for i in 0:length(buckets) - 1
        bucketIndex = 1 + i
        buckets[bucketIndex] = sort(buckets[bucketIndex])
    end

    flat = [(buckets...)...]
    print(flat, "\n")

end

numbersCount = 10
maxNumber = 10
numbers = rand(1:maxNumber, numbersCount)
print(numbers,"\n")
bucketsCount = 10
bucketSort(numbers, bucketsCount)

На производительность алгоритма также влияет число ведер, для большего количества чисел лучше взять большее число ведер (Algorithms in a nutshell by George T. Heineman)

Ссылки

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/bucketSort

Источники

https://www.youtube.com/watch?v=VuXbEb5ywrU
https://www.youtube.com/watch?v=ELrhrrCjDOA
https://medium.com/karuna-sehgal/an-introduction-to-bucket-sort-62aa5325d124
https://www.geeksforgeeks.org/bucket-sort-2/
https://ru.wikipedia.org/wiki/%D0%91%D0%BB%D0%BE%D1%87%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
https://www.youtube.com/watch?v=LPrF9yEKTks
https://en.wikipedia.org/wiki/Bucket_sort
https://julialang.org/
https://www.oreilly.com/library/view/algorithms-in-a/9780596516246/ch04s08.html