---
tags: algorithms
---
<style>.markdown-body { max-width: 1000px; }</style>

# Data structures

## Circular Queue

public class CircularQueue {

    int k;
    int head;
    int[] array;
    int count;
    
    public CircularQueue(int k) {
        this.k = k;
        array = new int[k];
        head = 0;
    }
    
    public bool EnQueue(int value) {
        if(IsFull())
            return false;
        
        array[(head + count)%k] = value;
        count++;
        return true;
    }
    
    public bool DeQueue() {
        if(IsEmpty())
            return false;
        head = Next(head);
        count--;
        return true;
    }
    
    public int Front() {
        if(IsEmpty())
            return -1;
        return array[head];
    }
    
    public int Rear() {
        if(IsEmpty())
            return -1;
        return array[(head + count - 1)%k];
    }
    
    public bool IsEmpty() {
        return count == 0;
    }
    
    public bool IsFull(){
        return count == k;    
    }
    
    private int Next(int idx){
        return (idx + 1) % k;
    }
    
}

## Suffix Array

int[] BuildSuffixArray(string s){
	int n = s.Length;
	Suffix[] suffixes = new Suffix[n];
	
	for(int i = 0; i < n; i++){
		suffixes[i] = new Suffix(i, s[i] - 'a'); //, (i + 1 < n) ? s[i+1] - 'a' : -1 );
	}

	for (int i = 0; i < n; i++)
	{
		suffixes[i].nextRank = (i + 1 < n ? suffixes[i + 1].rank : -1);
	}

	Array.Sort(suffixes);
	
	//suffixes.D();
	int[] indices = new int[n];
	
	for(int length = 4; length < 2 * n; length <<=1){
		
		//Rank compressing and comparing with previous suffix ranks
		int rank = 0, prevRank = suffixes[0].rank;
		suffixes[0].rank = 0;
		indices[suffixes[0].index] = 0;

		for (int i = 1; i < n; i++)
		{
			if (suffixes[i].rank == prevRank && suffixes[i].nextRank == suffixes[i - 1].nextRank)
			{
				prevRank = suffixes[i].rank;
				suffixes[i].rank = rank;
			}
			else
			{
				prevRank = suffixes[i].rank;
				suffixes[i].rank = ++rank;
			}
			
			indices[suffixes[i].index] = i;
		}
		
		for(int i = 0; i < n; i++){
			int nextRankIndex = suffixes[i].index + length / 2;
			suffixes[i].nextRank = nextRankIndex < n ? suffixes[indices[nextRankIndex]].rank : -1;
		}

		Array.Sort(suffixes);
	}
	return suffixes.Select(s => s.index).ToArray();
}

public class Suffix : IComparable<Suffix>
{
	public int index;
	public int rank;
	public int nextRank;

	public Suffix(int index, int rank, int nextRank)
	{
		this.index = index;
		this.rank = rank;
		this.nextRank = nextRank;
	}
	
	
	public Suffix(int index, int rank):this(index, rank, 0)
	{
	}
	
	public int CompareTo(Suffix other)
	{
		if(rank != other.rank){
			return rank.CompareTo(other.rank);
		} 
		
		return nextRank.CompareTo(other.nextRank);
	}

	public override string ToString()
	{
		return $"index: {index}, rank: {rank}, nextRank: {nextRank}";
	}
}

## Disjoined Set (Union Find)

public class UnionFind
{
	int[] _parents;
	int _roots;
	public UnionFind(int n)
	{
		_roots = n;
		_parents = new int[n];
		Array.Fill(_parents, -1);
	}

	public int Find(int i)
	{
		return  _parents[i] < 0 ? i : _parents[i] = Find(_parents[i]);
	}
	
	public int Union(int i, int j){
		i = Find(i);
		j = Find(j);
		
		if(i != j){
			_parents[i] += _parents[j];
			_parents[j] = i;
			_roots--;
		}

		//$"Joined {i} and {j}".D();
		//_parents.Print();
		return -_parents[i];
	}
	
	public int Roots => _roots;
}

## DeQueue

public class Deque
{
    int[] values;
    int left_ptr = 0;
    int right_ptr = 0;
    int n = 0;
    int count = 0;
    public int Count => count;
	

    public Deque(int n)
    {
        this.n = n;
        values = new int[n];
    }

    public int First() { return values[left_ptr]; }
    public int Last() { return values[right_ptr]; }

    public void RemoveFirst() { if(left_ptr<n && left_ptr<right_ptr) left_ptr++; count--; }
    public void RemoveLast() { if(right_ptr>0 && right_ptr>left_ptr) right_ptr--; count--; }

    public void AddLast(int v) 
    {
      
        if (count == 0)
            values[right_ptr] = v;
        else
            values[++right_ptr] = v;

        count++;
    }
}

---

## BitSet

public class BitSet{
	
	int [] bitSet;
	
	public int[] Set => bitSet;
	
	public BitSet(int size){
		bitSet = new int[(size >> 5) + 1]; //divide by 32
	}
	
	public bool Contains(int number){
		int word = (number >> 5); //divide by 32
		int offset = number & 0x1F; //modulo 32
		//$"Checking number [{number}] as word {word}, offset {offset}. Result: {(bitSet[word] & (1 << offset))}".Dump();
		
		return (bitSet[word] & (1 << offset)) != 0;
	}
	
	public void SetBit(int number){
		int word = number >> 5;
		int offset = number & 0x1F;
		
		//$"Setting number [{number}] as word {word}, offset {offset}".Dump();
		
		bitSet[word] |= (1 << offset);
	}
	
	public string ShowWord(int number, bool debug = false){
		int word = number >> 5;

		if(debug){
			int setNumber = 32 * word;
			for(int i = 0; i < 32; i++){
				if((bitSet[word] & (1 << i)) != 0){
					$"{setNumber} is set".Dump();
				}
				setNumber++;
			}
		};
		return $"[ {Convert.ToString(bitSet[word], 2).PadLeft(32, '0')} ]";
	}
}

## Fenwick Tree

public class FenwickTree{

	int[] binaryTree;
	
	public FenwickTree(int[] array){
		binaryTree = new int[array.Length+1];
		for(int i = 1; i < binaryTree.Length; i++){
			UpdateBinaryTree(binaryTree, i, array[i-1]);
		}
	}
	
	public void UpdateBinaryTree(int[] binaryTree, int index, int value){
		while(index < binaryTree.Length){
			binaryTree[index] += value;
			index += index & (-index);
		}
	}
	
	public int Query(int from, int to){
		return Query(to) - Query(from-1);
	}
	
	public int Query(int index){
		int sum = 0;
		index = index+1;
		while(index > 0){
			sum += binaryTree[index];
			index -= index & (-index);
		}
		
		return sum;
	}
	
	public int[] BinaryTree => binaryTree;
}

## Segment Tree

public class SegmentTree
{
	int n;
	List<int> data = new List<int>();
	public SegmentTree(int[] a){
		n = a.Length;
		for(int i = 0; i < n; i++){
			data.Add(0);
		}
		for(int i = 0; i < n; i++){
			data.Add(a[i]);
		}
		
		for(int p = n-1; p > 0; p--){
			data[p] = Math.Min(data[p*2], data[p*2+1]);
		}
	}
	
	public int Min(int left, int right){
		left = left + n;
		right = right + n;
		int min = Int32.MaxValue;
		
		while(left < right){
			if((left & 1) == 1){
				min = Math.Min(min, data[left]);
				left++;
			}
			if((right & 1) == 1){
				right--;
				min = Math.Min(min, data[right]);
			}
			left >>= 1;
			right >>= 1;
		}
		
		return min;
	}
	
	public List<int> Data => data;
}