LZSSCompress::Private Class Reference

Collaboration diagram for LZSSCompress::Private:

Public Member Functions
void	DeleteNode (short int Node)
void	InitTree ()
void	InsertNode (short int Pos)

Static Public Attributes
static short int	m_dad [N+1]
static short int	m_lson [N+1]
static short int	m_match_length
static short int	m_match_position
static unsigned char	m_ring_buffer [N+F-1]
static short int	m_rson [N+257]

Detailed Description

Definition at line 61 of file lzsscomprs.cpp.

Member Function Documentation

void LZSSCompress::Private::DeleteNode

(

short int

Node

)

Definition at line 308 of file lzsscomprs.cpp.

{
    short int  q;

/*
    ASSERT(Node >= 0);
    ASSERT(Node < (N+1));
*/

    if (m_dad[Node] == NOT_USED) { // not in tree, nothing to do
        return;
    }

    if (m_rson[Node] == NOT_USED) {
        q = m_lson[Node];
    }
    else if (m_lson[Node] == NOT_USED) {
        q = m_rson[Node];
    }
    else {
        q = m_lson[Node];
        if (m_rson[q] != NOT_USED) {
            do {
                q = m_rson[q];
            } while (m_rson[q] != NOT_USED);

            m_rson[ m_dad[q] ] = m_lson[q];
            m_dad[ m_lson[q] ] = m_dad[q];
            m_lson[q] = m_lson[Node];
            m_dad[ m_lson[Node] ] = q;
        }

        m_rson[q] = m_rson[Node];
        m_dad[ m_rson[Node] ] = q;
    }

    m_dad[q] = m_dad[Node];

    if (m_rson[ m_dad[Node] ] == Node) {
        m_rson[ m_dad[Node] ] = q;
    }
    else {
        m_lson[ m_dad[Node] ] = q;
    }

    m_dad[Node] = NOT_USED;
}

void LZSSCompress::Private::InitTree

(

void

)

Definition at line 151 of file lzsscomprs.cpp.

                                       {
    int  i;

    // For i = 0 to N - 1, m_rson[i] and m_lson[i] will be the right
    // and left children of node i.  These nodes need not be
    // initialized.  However, for debugging purposes, it is nice to
    // have them initialized.  Since this is only used for compression
    // (not decompression), I don't mind spending the time to do it.
    //
    // For the same range of i, m_dad[i] is the parent of node i.
    // These are initialized to a known value that can represent
    // a "not used" state.
    
    for (i = 0; i < N; i++) {
        m_lson[i] = NOT_USED;
        m_rson[i] = NOT_USED;
        m_dad[i] = NOT_USED;
    }

    // For i = 0 to 255, m_rson[N + i + 1] is the root of the tree
    // for strings that begin with the character i.  This is why
    // the right child array is larger than the left child array.
    // These are also initialzied to a "not used" state.
    //
    // Note that there are 256 of these, one for each of the possible
    // 256 characters.

    for (i = N + 1; i <= (N + 256); i++) {
        m_rson[i] = NOT_USED;
    }
}

void LZSSCompress::Private::InsertNode

(

short int

Pos

)

Definition at line 210 of file lzsscomprs.cpp.

{
    short int i;
    short int p;
    int cmp;
    unsigned char * key;

/*
    ASSERT(Pos >= 0);
    ASSERT(Pos < N);
*/

    cmp = 1;
    key = &(m_ring_buffer[Pos]);

    // The last 256 entries in m_rson contain the root nodes for
    // strings that begin with a letter.  Get an index for the
    // first letter in this string.

    p = (short int) (N + 1 + key[0]);

    // Set the left and right tree nodes for this position to "not
    // used."

    m_lson[Pos] = NOT_USED;
    m_rson[Pos] = NOT_USED;

    // Haven't matched anything yet.

    m_match_length = 0;

    for ( ; ; ) {
        if (cmp >= 0) {
            if (m_rson[p] != NOT_USED) {
                p = m_rson[p];
            }
            else {
                m_rson[p] = Pos;
                m_dad[Pos] = p;
                return;
            }
        }
        else {
            if (m_lson[p] != NOT_USED) {
                p = m_lson[p];
            }
            else {
                m_lson[p] = Pos;
                m_dad[Pos] = p;
                return;
            }
        }

        // Should we go to the right or the left to look for the
        // next match?

        for (i = 1; i < F; i++) {
            cmp = key[i] - m_ring_buffer[p + i];
            if (cmp != 0)
                break;
        }

        if (i > m_match_length) {
            m_match_position = p;
            m_match_length = i;

            if (i >= F)
                break;
        }
    }

    m_dad[Pos] = m_dad[p];
    m_lson[Pos] = m_lson[p];
    m_rson[Pos] = m_rson[p];

    m_dad[ m_lson[p] ] = Pos;
    m_dad[ m_rson[p] ] = Pos;

    if (m_rson[ m_dad[p] ] == p) {
        m_rson[ m_dad[p] ] = Pos;
    }
    else {
        m_lson[ m_dad[p] ] = Pos;
    }

    // Remove "p"

    m_dad[p] = NOT_USED;
}

Member Data Documentation

short int LZSSCompress::Private::m_dad

static

Definition at line 68 of file lzsscomprs.cpp.

short int LZSSCompress::Private::m_lson

static

Definition at line 66 of file lzsscomprs.cpp.

short int LZSSCompress::Private::m_match_length

static

Definition at line 65 of file lzsscomprs.cpp.

short int LZSSCompress::Private::m_match_position

static

Definition at line 64 of file lzsscomprs.cpp.

unsigned char LZSSCompress::Private::m_ring_buffer

static

Definition at line 63 of file lzsscomprs.cpp.

short int LZSSCompress::Private::m_rson

static

Definition at line 67 of file lzsscomprs.cpp.

---

The documentation for this class was generated from the following file:

• src/modules/common/lzsscomprs.cpp