Binary Search

Suppose we need to find out whether the email address “ ” belongs to the list of allowed email addresses for receiving letters.

We sort through the entire list from the first to the last element, checking whether the element is equal to the specified address – we implement the linear search algorithm. But will it be long or not?

To answer this question, use the “Temporary complexity of the algorithms”, “O” notation. In the worst case, the linear search operation time is equal to the nth number of array elements, we write this in the “O” notation – O (n). Next, you need to clarify that for any known algorithm, there are three performance indicators – execution time in the best, worst, and average cases. For example, the mail address “ ” is in the first index of the array, then it will be found in the first step of the algorithm, it follows that the execution time in at best, O (1); and if at the end of the list, then this is the worst case – O (n)

But what about the details of the software implementation, the performance of the hardware, should they affect big O? Now exhale and imagine that the calculation of time complexity is calculated for some abstract ideal machine, in which there is only this algorithm and nothing more.


Ok, it turns out that the linear search is rather slow, let’s try using the binary search. To begin with, it should be clarified that we will not work with binary data, this name was given to this method because of the features of its work. Initially, we sort the array into lexicographically , then the algorithm takes the range of the entire array, gets the middle element of the range, compares it lexicographically , and depending on the result comparison decides what range to take to search for more – the top half of the current or lower. That is, at each step of the search, a decision is made of two possible ones – binary logic. This step is repeated until either the word is found or not found (the intersection of the lower and upper indices of the range will occur).

The performance of this algorithm is the best case when an element is immediately found in the middle of the O (1) array, the worst case is O (log n)


When implementing binary search, I came across not only the interesting problem of the lack of standardization of lexicographic comparison in programming language libraries, but I even found that there is no single standard for implementing localeCompare inside JavaScript . The ECMAScript standard allows different implementations of this function, because of this, when sorting using localeCompare, absolutely different results can be observed on different JavaScript engines.

Therefore, for the algorithm to work correctly, you must sort and use only the same lexicographic comparison algorithm in your work, otherwise nothing will work. So, for example, if you try to sort an array in Scala, and search using nodejs without realizing your own sorting / sorting of one implementation, then you will not expect anything other than disappointment in humanity.


Source Code

Facade Pattern

Facade belongs to structural design patterns. It provides a single interface that provides interaction between client and complex systems. GoF has a good example of the Facade – a compiler of programming languages ​​that provides different clients with different goals, the ability to build code through a single interface of the compiler facade.


Abstract Factory Pattern

Abstract factory – provides an interface for creating the corresponding objects, without specifying specific classes.

I really like the alternative name for this pattern – Kit

It is very similar to the Factory Method, however, Abstract Factories should describe the relationship between the created objects, otherwise it is already just the antipattern God Object, creating unsystematically everything.

Imagine the development of an AR framework for glasses, we display on the screen arrows for indoor navigation, store icons, interesting places, windows and buttons with information about any place where the user is now located.

At the same time, we need the ability to customize the appearance and behavior of the controls of the AR environment. That’s it for this case, you need to use the Set pattern.

We’ll write the interface of Abstract Factory and Products – parent protocols, elements of the AR environment:

protocol ARFactory {
    func arrow() -> ARArrow
    func icon() -> ARIcon
    func button() -> ARButton
    func window() -> ARWindow

protocol ARArrow {
    var image: { get }
    func handleSelection()

protocol ARIcon {
    var image: { get }
    var title: String

protocol ARButton {
    var title: String
    func handleSelection()

protocol ARWindow {
    var title: String
    var draw(canvas: Canvas)

Now the kit developers will need to implement the Concrete Factory on the basis of the Abstract Factory interface, and all the elements will have to be implemented together, the rest of the application will be able to work with the factory without changing its code.


Factory Method Pattern

Pattern Factory Method refers to creational design patterns.
This pattern describes the creation of an interface for creating an object of a particular class. Sounds simple yeah?


Suppose we are developing a framework for working with AR glasses, when you tilt your head to the side, a menu of available applications should appear in front of the user’s eyes. Applications will be developed by third-party companies, clients of our framework. Naturally, we don’t know which applications, icons, names should appear, so we must provide an interface for implementing the icon and related information about the application. Call it Product:

protocol Product {
 var name: String { get }
 var image: Image { get }
 var executablePath: String { get }

Next, we need to provide an interface so that our customers implement the application array of their Specific Product – an array of application icons with names that we will already draw in the framework.

We’ll write this interface – the Creator interface, containing the Factory Method, which returns an array of Products.

protocol Creator {
 func factoryMethod() -> [Product]

In practice

The first customer of our AR framework was 7B, a leading provider of coffee maker software in Honduras. They want to sell augmented reality glasses with the ability to brew coffee, check the fullness of the water / beans, point the way to their nearest coffee maker in indoor map mode.

They undertake the development of software, we only need to provide documentation on the interfaces of Creator and Product, for the correct listing of applications and their further launch.

After the documentation is transferred, 7B using the Creator interface implements the Concrete Creator – a class that returns an array of icon applications. Icon applications themselves are the Concrete Product classes implementing the Product interface.

Concrete Product code example:

class CoffeeMachineLocator: implements Product {
 let name = “7B Coffee Machine Locator v.3000”
 let image = Image.atPath(“images/locator.tga”)
 let executablePath = “CoffeeMachineLocator.wasm”

class iPuchinno: implements Product {
 let name = “iPuchinno 1.0.3”
 let image = Image.atPath(“images/puchino.pvrtc”)
 let executablePath = “neutron/ipuchBugFixFinalNoFreezeFixAlpha4.js”

Concrete Creator class, returning array with two applications:

class 7BAppsCreator: implements Creator {
 func factoryMethod() -> [Product] {
  return [CoffeeMachineLocator(), iPuchinno()]

After that, 7B compiles the library of Concrete Products, Concrete Creator and combines it with our framework, starts selling AR glasses for its coffee makers, no source code modifications on our side is required.


Command Pattern

Pattern Command refers to behavioral design patterns.

This is the pattern with which I sit longer than the rest, it is so simple that it is very complicated. But personally, I find the charm of self-learning in that you have all the time in the world to explore a specific issue from all angles.

So, in GoF, applicability is described rather concisely and clearly:
Encapsulates the request as an object, allowing you to configure (parameterize) clients with different requests, use queues, log requests and perform cancellation operations.

Now we implement a simple version of the command from the description:

string fakeTrumpsRequest = “SELECT * from Users where name beginsWith DonaldTrump”

We encapsulated the request in a string class object, it can configure clients, add commands to the queue, log, cancel (using the “Snapshot” pattern)

It seems to me that this is quite enough to implement SQL queries and the like, but then the implementation details begin, various applications, the code base of the pattern, the roles of the clients vary greatly, auxiliary classes are added.

The Math Part

The command pattern begins with the Command protocol, which contains a single execute() method. Next comes the Concrete Command and Receiver, QC implements the operation on the Receiver, describes the relationship between the Receiver and the action. Nothing is clear? Me too, but drove on. Client creates an instance of the Specific Command, associates it with the Receiver. Invoker – an object that implements the process of launching Command.

Now let’s try to figure out an example, let’s say we want to update myOS on myPhone, for this we launch the application myOS_Update!, in it we press the Update Now! Button, after 10 seconds the system will inform you of a successful update.

The Client in the example above is the application myOS_Update!, Invoker is the “Update Now!” button, it launches the Specific Command of the system update using the execute(), which refers to the Receiver – the daemon for updating the operating system.

Case Study

Let’s say the application UI is myOS_Update! so good that they decided to sell it as a separate product to provide an update interface for other operating systems. In this case, we will implement an application with support for extension through libraries, in the libraries there will be implementations of Specific Commands, Receivers, we will leave static/unchanged Invoker, Client, protocol Command.

Thus, there is no need to provide support for mutable code, since our code will remain unchanged, problems can arise only when implemented on the client side, due to errors in the code of their Concrete Commands and Receivers. Also, in such an implementation, there is no need to transfer the source code of the main application, that is, we encapsulated commands and UI interactions using the Command pattern.


Crosscompile for macOS on Ubuntu OSXCross CMake

In this note, I will describe the assembly of cross-platform C ++ applications for macOS on an Ubuntu build machine using CMake and osxcross.
First, install the osxcross toolchain:
Installation takes place in 3 stages, loading dependencies:

cd tools

Download XCode.xip from the official Apple website, then download the SDK from Xcode:

./ /media/demensdeum/2CE62A79E62A4404/LinuxSupportStorage/xcode111.xip

I hope you read the Xcode license agreement in the last step? Next, building the toolchain with the desired prefix:

INSTALLPREFIX=/home/demensdeum/Apps/osxcross ./ 

Now you can use osxcross from the prefix directory of the last step. Add a new build macro for CMake, write everything you need:

SET(CMAKE_C_COMPILER_AR x86_64-apple-darwin19-ar)
SET(CMAKE_CXX_COMPILER_AR x86_64-apple-darwin19-ar)
SET(CMAKE_LINKER x86_64-apple-darwin19-ld)

I did not succeed in dynamic linking, so we export the libraries statically:

add_library(FlameSteelCore STATIC ${SOURCE_FILES})

Further, you may encounter the fact that you do not have the necessary libraries for osxcross, I encountered this when using SDL2. osxcross supports ready-made library packages – macports. For example, installing SDL2-mixer:

osxcross-macports -v install libsdl2_mixer

After that, you can start assembling libraries / applications as usual in the cmake-make link, do not forget to register a static link of libraries if necessary.

Manual assembly of libraries

At the moment, I have encountered the problem of incorrect archiving of libraries during static linking, I get an error when building the final application:

file was built for archive which is not the architecture being linked (x86_64)

Very similar to this ticket , I managed to implement workaround in as a result, the build completes correctly. Unzip the static library and build it again using the osxcross archiver:

ar x ../libFlameSteelCore.a
rm ../libFlameSteelCore.a
x86_64-apple-darwin19-ar rcs ../libFlameSteelCore.a *.o

Also, I personally consider one of the problems the lack of the ability to run macOS applications immediately on ubuntu (at least with a part of the functionality), of course there is a project darling , but support is poor for the time being.


Crosscompile for Windows on Ubuntu MinGW CMake

In this article, I will describe the process of building libraries and applications for Windows using the MinGW32 toolchain on Ubuntu.
Install wine, mingw:

sudo apt-get install wine mingw-w64

After that, you can already build C / C ++ applications for Windows:

# C
i686-w64-mingw32-gcc helloWorld.c -o helloWorld32.exe      # 32-bit
x86_64-w64-mingw32-gcc helloWorld.c -o helloWorld64.exe    # 64-bit
# C++
i686-w64-mingw32-g++ -o helloWorld32.exe     # 32-bit
x86_64-w64-mingw32-g++ -o helloWorld64.exe   # 64-bit

Collected exe can be checked with wine.

Next, consider the changes to the CMake assembly, the CMakeLists.txt file, add MinGW specific things to the assembly file:

if (MINGW32)
SET(CMAKE_C_COMPILER i686-w64-mingw32-gcc)
SET(CMAKE_CXX_COMPILER i686-w64-mingw32-g++)
SET(CMAKE_RC_COMPILER i686-w64-mingw32-windres)
set(CMAKE_RANLIB i686-w64-mingw32-ranlib)

elseif (MINGW32)
add_library(FlameSteelEngineGameToolkit.dll SHARED ${SOURCE_FILES})

// link with all dependencies
if (MINGW32)

set_target_properties(FlameSteelEngineGameToolkit.dll PROPERTIES
        PREFIX ""
        SUFFIX ""
        LINK_FLAGS "-Wl,--add-stdcall-alias"
        POSITION_INDEPENDENT_CODE 0 # this is to avoid MinGW warning; 
        # MinGW generates position-independent-code for DLL by default


cmake -DMINGW32=1 .

The output will be dll or exe, depending on your build. You can look at the working example in the repository of the new Cube-Art-Project and its libraries:


Simple Emscripten auto test with ChromeDriver

In this article, I will describe the implementation of running autotest for ChromeDriver of the Chrome browser, which runs the module autotest translated from C ++ using Emscripten, reads the console output and returns the result of the check.
First you need to install selenium, for python3-ubuntu this is done like this:

pip3 install selenium

Next, download ChromeDriver from the official site, put the chromedriver in / usr / local / bin for example, after which you can start implementing the autotest.
Below I will give the autotest code that launches the Chrome browser with the autotest page open on Emscripten, checks for the presence of the text “Window test succeded”:

import time
from selenium import webdriver
from selenium.webdriver.common.keys import Keys
from selenium.webdriver.common.desired_capabilities import DesiredCapabilities

capabilities = DesiredCapabilities.CHROME
capabilities['goog:loggingPrefs'] = { 'browser':'ALL' }
driver = webdriver.Chrome()


exitCode = 1

for entry in driver.get_log('browser'):
    if entry["source"] == "console-api":
        message = entry["message"]
        if "Window test succeded" in message:
            print("Test succeded")
            exitCode = 0


Save the test as and run python3