DEV Community: Satyarth Agrahari

[Rust] Generic Segment Tree

Satyarth Agrahari — Sat, 23 Apr 2022 05:16:54 +0000

I wanted to write and keep a segment tree implementation for myself, that I could use more generally (all reasonable data types, and all reasonable operations). I finally decided to write one and add it to cp-lib.

The core struct for now is:

pub struct SegTree<T, F>
where
    T: Clone + Copy,
    F: Fn(T, T) -> T,
{
    n: i32,
    default: T,
    cell: Vec<T>,
    lazy: Vec<T>,
    op: F,
}

And usage:

let mut tree = SegTree::new(10, i32::MIN, std::cmp::max);
tree.insert(1, 10);
tree.insert(2, 20);
assert_eq!(tree.query(1, 10), 20);

tree.insert_range(3, 6, 10);
assert_eq!(tree.query(5, 10), 10);

Where op is the operation that the segment tree performs (min, max, gcd, or something custom), and default is the value the should be returned as query default and gets stored during initialization.

The major benefit is that it allows for me to write more complicated segtree rather easily,
eg:
for problem: https://codeforces.com/contest/1557/problem/D
my solution (https://codeforces.com/contest/1557/submission/154901530) uses

let mut seg_tree = SegTree::new(
    points.len(),
    (0, 0),
    |left: (usize, usize), right: (usize, usize)| if left.1 > right.1 { left } else { right },
);

Sharing the full implementation here in case someone needs it.

I will keep on modifying it as needed. In case anyone do decide to use it and find some bugs, or have a feature request, do let me know.

Releasing rss-update-0.1-beta.2

Satyarth Agrahari — Thu, 19 Aug 2021 01:51:48 +0000

I recently setup neovim editor as my sole IDE. It was fun setting up an IDE with only the things that you care about, and get excellent speedups for both autocomplete and type hints. If you are interested in my current neovim conf, you can check it out at github.

Since I had my IDE setup, I wanted to take it out to a test drive, so I started writing a CLI util for something that I wanted to have for few months now. A way to track updates on blogs that I follow with no upper cap on number on blogs. And I recently learned rust, so it was time that I built something using both.

Presenting rss-update cli, an util for tracking rss/atom feeds and get updates on them, when you want to.

To add new feeds: rss-update add --feed <FEED>
To fetch new posts in feed: rss-update
To show unread posts: rss-update unread
To mark posts as read: rss-feed read --post <URL>
To list tracking feeds: rss-feed tracking
To remove feed from tracking: rss-feed remove --feed <FEED>

In case you try it out and have some feed-back / request, feel free to open an issue or reach out to me.

Indirect Coupling Story

Satyarth Agrahari — Wed, 21 Jul 2021 09:46:53 +0000

At some point or the other, we all read about importance of decoupling components while writing code. The coupling doesn't just exists in low level code, but one can also observer it at architecture levels. With the exploding popularity of micro services, and the lack of knowledge around building them (or rather the lack of curiosity of actually reading about them), has lead to creeping the same coupling problems between improperly designed micro services.

But let's not go into complex issues, and look at something which is much more simple and obvious ones you notice it. Its about coupling that is created from using a certain version of library dependency across services, and poor API design that doesn't abstract its effect from leaking out.

We have around 30-40 different micro services that just our team owns. Recently we started doing some dependency upgrades for our serde libraries that is used to pass object states across different services, and realised that a supposedly simple upgrade is proving to be non trivial.

The issue arose from the fact that we have plethora of micro services which all share states between each other, and used a serde to achieve the same. The serde however releases changes which are backward incompatible even across minor version upgrades (doesn't follows semver) and so there exists the possibility of breaking api calls between services since the API leaks the serialised objects as API's request / response arguments.

The way the services communicated also makes upgrading dependency iteratively difficult as they follow somewhat mesh structure, and thus we are stuck in a situation where:

one has to upgrade it for all required services in one go. 2. pause the traffic.
verify that we have covered all services by testing over a traffic slice.
Activate the traffic flow. In case something goes wrong, find the missing upgrade, and start with step 1 in loop.

I hope that I could say these are legacy services, but sadly they are services that were recently developed.

The important thing here is the learning that we get from the incident, majorly making micro services truly decoupled, and to achieve that, I guess at least one important thing is designing APIs in a way that doesn't leak effects from their dependencies.

Oh and also choosing 3p libraries that follow semver in case they are available.

Starship, because it's too damn cool

Satyarth Agrahari — Sun, 09 May 2021 05:31:27 +0000

This is more of an appreciative post for starship, an amazingly cool and customizable prompt for any shell. And the reason why it is so amazing is because even by default it has too many cool features while being super fast.

Just to show how it looks by default for rust and python:

We can see that it identifies what kind of project it is while giving information about which branch we are on, and which version of toolchain we are using.

It is not just limited to what comes by default, and its extensibility and ease of use is what is amazing about it. I use it for my personal projects as well as in my office system to inject information into prompt (like getting to know which versionset I am using).

And special thanks to Chris Rose for introducing me to this.

Playing the generator game

Satyarth Agrahari — Fri, 26 Mar 2021 05:56:14 +0000

A while back I wrote a post on

How I misunderstood Lombok

Satyarth Agrahari ・ Nov 13 '20

#java #programming

So This time around, I didn't wanted to make the same mistake, which brings us back to this post.

Let's start with a simple exercise for people familiar with lombok and dependency injection. What do you think should be the generated code from the following block

@RequiredArgsConstructor(onConstructor = @__(@Inject))
public class Test {
    @NonNull @Named("testString") private final String testString;
}

I think most people would guess (who have seen generated code by lombok) that this would translate to

public class Test {
    @Generated
    @Inject
    Test(@NonNull @Named("testString") String testString) {
        if (testString == null) {
            throw new NullPointerException("testString is marked non-null but is null");
        } else {
            this.testString = testString;   
        }
    }
}

But if it would have been the case, then we wouldn't be here, would we...
So lets see what it actually generates

public class Test {
    @Generated
    @Inject
    Test(@NonNull String testString) {
        if (testString == null) {
            throw new NullPointerException("testString is marked non-null but is null");
        } else {
            this.testString = testString;   
        }
    }
}

But that's strange, I can clearly see that I have annotated my field with @Named, and so how would it even find the correct dependency to inject, if it will not have the name discovery during dependency injection.

Well as it turns out, lombok doesn't respects all annotations, since it gets too complicated to implement that behaviour. You can go through the github issues for details 1 2

So now that we know that this is the case, the question is how to resolve this.

in newer versions of lombok one could add lombok.copyableAnnotations += com.google.inject.name.Named in lombok.config file and lombok would try and copy them when it generates the constructor.
Go with our old fashioned constructor based injection and write

public class Test {
    @Inject
    Test(@NonNull @Named("testString") final String testString) {
        this.testString = testString;
    }
}

I prefer 2, because of couple of reasons

Putting a conf in lombok.config that determines what gets copied hides too much information and is frankly just an accident waiting to happen, when someone see this code sample and tries to copy it and it somehow works because there was no collision.
It only copies the annotation which have copyable implemented for them, so in case we come across something that is not copyable, we are back to implementing 2 anyways.
I like the 2nd one since its more expressive, and I like writing codes that are more expressive since eventually we are writing them for humans, and its better if we do not hide too many things and keep things simple so that the person reading code can focus more on business logic rather than spending time understanding why or why not their injection works.

How I misunderstood Lombok

Satyarth Agrahari — Fri, 13 Nov 2020 07:38:24 +0000

I was working on a project, and I wrote some code which I expected to work fine. The snippet was like

But to my surprise, I got a Medium Priority Warnings from findbugs: RCN_REDUNDANT_NULLCHECK_WOULD_HAVE_BEEN_A_NPE: Nullcheck of value previously dereferenced

Basically it started complaining that I have non null check on a name on line 19 after it is being de-referenced at line 22 (the numbers are correct, bear with me for a while), so if the value was null, I would get NPE before even reaching this point.

This error in itself was super confusing, atleast for me. From what I understood here, we are creating Concrete, and checking if both the input are non null. Before it is initialized, we are passing this value super where we have non null check on name, and it is set as value.

So, I went and looked at the decompiled .class file. It was expanded as:

public Concrete(
    @NonNull final String name,
    @NonNull final String address
) {
    super(name);
    if (name == null) {
        throw new NullPointerException("name");
    }
    this.address = address;
}

What was happening here was, the non null check was applied after calling the super class constructor, as opposed to before calling it, which is not what I would have expected. I thought that non null check will happen, before anything is executed in body, but I was definitely wrong.

Lombok is a super helpful tool, and it has made java much much (a couple of thousands much) less painful. But this incident reminded me again that no matter what, we should never just assume something while writing code.

This was a great learning for me.