deque.go

deque.go - Overview

This file implements a double-ended queue (deque) data structure with basic operations like push, pop, insert, and range retrieval, including two implementations: DequeBasic and Deque, along with encoding and decoding functions for deque entries.

Detailed Documentation

Interface DequeI

• Purpose: Defines the interface for deque operations.
• Methods:
  • GetLength() int64: Returns the length of the deque.
  • LPush(string): Pushes a string to the left end of the deque.
  • RPush(string): Pushes a string to the right end of the deque.
  • LPop() (string, error): Pops a string from the left end of the deque. Returns an error if the deque is empty.
  • RPop() (string, error): Pops a string from the right end of the deque. Returns an error if the deque is empty.
  • LInsert(string, string, string) (int64, error): Inserts a string before or after a specified pivot string. Returns the new length of the deque or an error.
  • LRange(start, stop int64) ([]string, error): Retrieves a range of strings from the deque.

Struct DequeBasic

• Purpose: Implements a basic deque using a byte slice.
• Fields:
  • Length int64: The number of elements in the deque.
  • buf []byte: The buffer storing the deque's data.
• Methods:
  • NewBasicDeque() *DequeBasic: Constructor for DequeBasic.
    • Returns: A pointer to a new DequeBasic instance.
  • GetLength() int64: Returns the length of the deque.
    • Returns: The length of the deque as an int64.
  • LPush(x string): Pushes x onto the left side of the deque.
    • Parameters:
      • x string: The string to push.
  • RPush(x string): Pushes x onto the right side of the deque.
    • Parameters:
      • x string: The string to push.
  • RPop() (string, error): Pops an element from the right side of the Deque.
    • Returns: The popped string and an error, if any.
  • LPop() (string, error): Pops an element from the left side of the Deque.
    • Returns: The popped string and an error, if any.
  • LInsert(pivot, element, beforeAfter string) (int64, error): Inserts element before/after pivot element.
    • Parameters:
      • pivot string: Pivot element.
      • element string: Element to be inserted.
      • beforeAfter string: "before" or "after".
    • Returns: Length of deque and an error, if any.
  • LRange(start, stop int64) ([]string, error): Iterates over the Deque and returns the element in order.
    • Parameters:
      • start int64: Start index.
      • stop int64: Stop index.
    • Returns: Slice of strings and an error, if any.
  • NewIterator() *DequeBasicIterator: Creates a new iterator for DequeBasic.
    • Returns: A pointer to a new DequeBasicIterator instance.

Struct DequeBasicIterator

• Purpose: Iterator for DequeBasic.
• Fields:
  • deque *DequeBasic: Pointer to the DequeBasic instance being iterated.
  • elementsTraversed int64: Number of elements traversed so far.
  • bufIndex int: Current index in the buffer.
• Methods:
  • HasNext() bool: Checks if there are more elements to iterate.
    • Returns: true if there are more elements, false otherwise.
  • Next() (string, error): Returns the next element and advances the iterator.
    • Returns: The next string and an error, if any.

Struct Deque

• Purpose: Implements a deque using a linked list of byte slices.
• Fields:
  • Length int64: The number of elements in the deque.
  • list *byteList: The linked list storing the deque's data.
  • leftIdx int: Index of the left end of the deque in the head node's buffer.
• Methods:
  • NewDeque() *Deque: Constructor for Deque.
    • Returns: A pointer to a new Deque instance.
  • GetLength() int64: Returns the length of the deque.
    • Returns: The length of the deque as an int64.
  • LPush(x string): Pushes x onto the left side of the deque.
    • Parameters:
      • x string: The string to push.
  • RPush(x string): Pushes x onto the right side of the deque.
    • Parameters:
      • x string: The string to push.
  • LPop() (string, error): Pops a string from the left end of the deque.
    • Returns: The popped string and an error, if any.
  • RPop() (string, error): Pops a string from the right end of the deque.
    • Returns: The popped string and an error, if any.
  • LInsert(pivot, element, beforeAfter string) (int64, error): Inserts element before/after pivot element.
    • Parameters:
      • pivot string: Pivot element.
      • element string: Element to be inserted.
      • beforeAfter string: "before" or "after".
    • Returns: Length of deque and an error, if any.
  • LRange(start, stop int64) ([]string, error): Iterates over the Deque and returns the element in order.
    • Parameters:
      • start int64: Start index.
      • stop int64: Stop index.
    • Returns: Slice of strings and an error, if any.
  • NewIterator() *DequeIterator: Creates a new iterator for Deque.
    • Returns: A pointer to a new DequeIterator instance.
  • Serialize(buf *bytes.Buffer) error: Serializes the Deque to a bytes.Buffer.
    • Parameters:
      • buf *bytes.Buffer: Buffer to write to.
    • Returns: An error, if any.
  • DeserializeDeque(buf *bytes.Reader) (*Deque, error): Deserializes the Deque from a bytes.Reader.
    • Parameters:
      • buf *bytes.Reader: Buffer to read from.
    • Returns: A new Deque and an error, if any.

Struct DequeIterator

• Purpose: Iterator for Deque.
• Fields:
  • deque *Deque: Pointer to the Deque instance being iterated.
  • CurrentNode *byteListNode: Current node in the linked list.
  • ElementsTraversed int64: Number of elements traversed so far.
  • BufIndex int: Current index in the node's buffer.
• Methods:
  • HasNext() bool: Checks if there are more elements to iterate.
    • Returns: true if there are more elements, false otherwise.
  • Next() (string, error): Returns the next element and advances the iterator.
    • Returns: The next string and an error, if any.

Constants

• Purpose: Defines constants used in the deque implementation.
• Constants:
  • minDequeNodeSize = 256: Minimum size for a deque node.
  • Before = "before": String constant for inserting before.
  • After = "after": String constant for inserting after.

Functions

• EncodeDeqEntry(x string) []byte: Encodes a string into a byte slice for deque storage. Chooses between integer and string encoding based on content.
  • Parameters:
    • x string: The string to encode.
  • Returns: The encoded byte slice.
• EncodeDeqStr(x string) []byte: Encodes a string into a byte slice for deque storage.
  • Parameters:
    • x string: The string to encode.
  • Returns: The encoded byte slice.
• EncodeDeqInt(v int64) []byte: Encodes an int64 into a byte slice for deque storage.
  • Parameters:
    • v int64: The integer to encode.
  • Returns: The encoded byte slice.
• EncodeDeqEntryInPlace(x string, buf []byte): Encodes a string into a byte slice in place. Chooses between integer and string encoding based on content.
  • Parameters:
    • x string: The string to encode.
    • buf []byte: The buffer to encode into.
• EncodeDeqStrInPlace(x string, buf []byte): Encodes a string into a byte slice in place.
  • Parameters:
    • x string: The string to encode.
    • buf []byte: The buffer to encode into.
• EncodeDeqIntInPlace(v int64, buf []byte): Encodes an int64 into a byte slice in place.
  • Parameters:
    • v int64: The integer to encode.
    • buf []byte: The buffer to encode into.
• GetEncodeDeqEntrySize(x string) uint64: Returns the size of the encoded string. Chooses between integer and string encoding based on content.
  • Parameters:
    • x string: The string to check.
  • Returns: The size of the encoded string.
• GetEncodeDeqStrSize(x string) uint64: Returns the size of the encoded string.
  • Parameters:
    • x string: The string to check.
  • Returns: The size of the encoded string.
• GetEncodeDeqIntSize(v int64) uint64: Returns the size of the encoded int64.
  • Parameters:
    • v int64: The integer to check.
  • Returns: The size of the encoded int64.
• DecodeDeqEntry(xb []byte) (x string, entryLen int): Decodes a byte slice into a string.
  • Parameters:
    • xb []byte: The byte slice to decode.
  • Returns: The decoded string and the length of the entry.
• sanitizeStartIndex(q DequeI, start int64) int64: Validates and adjusts the start index.
  • Parameters:
    • q DequeI: The deque interface.
    • start int64: The start index.
  • Returns: The sanitized start index.
• sanitizeStopIndex(q DequeI, stop int64) int64: Validates and adjusts the stop index.
  • Parameters:
    • q DequeI: The deque interface.
    • stop int64: The stop index.
  • Returns: The sanitized stop index.
• serializeByteList(buf *bytes.Buffer, list *byteList) error: Serializes byteList.
  • Parameters:
    • buf *bytes.Buffer: Buffer to write to.
    • list *byteList: ByteList to serialize.
  • Returns: An error, if any.
• deserializeByteList(buf *bytes.Reader) (*byteList, error): Deserializes byteList.
  • Parameters:
    • buf *bytes.Reader: Buffer to read from.
  • Returns: A new byteList and an error, if any.

Getting Started Relevance