Skip to content
This repository has been archived by the owner on Aug 16, 2019. It is now read-only.

Azzaare/CompressedStacks.jl

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

29 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

CompressedStacks

Build Status

The documentation is still in progress (so is the package).

CompressedStacks.jl is a Julia package that provides a framework for compressed stacks. The design of this package is based on the article of ... All data structures and algorithms are implemented in pure Julia, and thus they are portable.

Main Features

The compressed stack structure used in CompressedStacks.jl requires conditions to be used optimally. If implemented with a classical stack, the problem requirements should be as follows:

  • The input is read sequentially and only once (in practice we require the user to read input from a file)
  • The reading of the stack can be written as below
1 : Initialize stack and auxiliary data structure DS with O(1) elements from I
2 : for all subsequent input a ∈ I do
3 :    while pop-condition(a,DS,stack.top(1),. . . , stack.top(k)) do
4 :      stack.pop
5 :    end while
6 :    if push-condition(a,DS,stack.top(1),. . . , stack.top(k)) then
7 :      stack.push(a)
8 :    end if
9 : end for
10: Report(stack)
  • The user is required to give the following functions (even for classical stacks)

    • pop_condition as in line 3 [return Bool]
    • push_condition as in line 6 [return Bool]
    • pop_action! to do when an element is popped (line 4) [return void]
    • push_action! to when an element is pushed (line 7) [return void]
    • read_input (line 2) [return D, where D is the data_type of the stack]
  • For Compressed Stacks, the following parameters are also required

    • (expected) size of the input or depth of the compressed stack
    • maximum space usage or space order
    • buffer of the stack (number of elements of the top than can be accessed anytime)
    • optional data_structure
    • context and data types

About

No description, website, or topics provided.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages