Simplest Codings

GenAI, Agents & Agentic AI: A Complete Hands-On Notebook

noreply@blogger.com (Varun) — Tue, 28 Jul 2026 06:28:16 +0000

Generative AI has gone from research curiosity to production reality at remarkable speed. Large language models can now summarise documents, write code, answer questions, and—when given tools—autonomously take actions in the world. But getting from "I've heard of ChatGPT" to "I can build my own agentic system" requires bridging a lot of conceptual gaps.

This post contains an interactive Jupyter notebook that walks you through that entire journey—from spinning up your first LLM call to orchestrating a multi-agent pipeline—all in one place, with runnable Python code at every step.

Who is this for? Developers with Python experience who are new to LLMs and want a practical, end-to-end foundation rather than scattered tutorials. The notebook targets beginner → intermediate level and supports four providers: Ollama (fully local), OpenAI, Google Gemini, and DeepSeek—so you can follow along regardless of which API keys you have.

What's Inside

The notebook is structured as eleven self-contained sections that build on each other:

Setup & Provider Configuration — install dependencies, pick your LLM provider, and configure credentials in one place.
LLM Basics — your first invoke() call, understanding messages, roles, and the chat model interface.
Prompt Engineering — system prompts, few-shot examples, temperature, and structured output with Pydantic.
Chains — composing steps with LangChain Expression Language (LCEL): prompt → model → parser pipelines.
Memory & Conversation History — stateful chat, ConversationBufferMemory, and trimming strategies.
RAG (Retrieval-Augmented Generation) — embedding documents into Chroma, semantic search, and grounded Q&A.
Tools & Function Calling — define tools, bind them to the model, and handle tool invocation responses.
Agents — ReAct loop, create_react_agent, and letting the model decide which tools to call.
Multi-Agent Systems — routing between specialist agents with a supervisor pattern.
Agentic Patterns — planning, reflection, self-critique, and iterative refinement loops.
Mini Agentic App — everything wired together into one small but complete application.

How to Run It Yourself

You can clone or download the notebook and run it locally. Prerequisites:

Python 3.10 or later
A running Ollama instance or an API key for OpenAI / Gemini / DeepSeek
Run the first cell (%pip install ...) to install all dependencies
Set your provider and credentials in the Section 1 config cell—the rest of the notebook picks them up automatically

Configure Provider

→

Run Cells Top-to-Bottom

→

Experiment & Modify

→

Build Your Own Agent

The intended workflow: configure once, execute sequentially, then diverge and experiment.

The Notebook

The full notebook is below. Each section opens with a short explanation followed by runnable Python code cells. Download it to run locally, or read through it here as a reference.

 genai_learning.ipynb — GenAI, Agents & Agentic AI · Complete Learning Notebook ⬇ Download .ipynb

GenAI, Agents & Agentic AI — Complete Learning Notebook

Level: Beginner → Intermediate
Providers supported: Ollama (local) · OpenAI · Google Gemini · DeepSeek

Learning Path

#	Topic	Concepts Covered
1	Setup & Provider Config	Install libs, configure keys, pick a provider
2	LLM Basics	Tokens, temperature, inference, completion vs chat
3	Prompt Engineering	Zero-shot, few-shot, CoT, system prompts, templates
4	Chains	Sequential chains, prompt → LLM → parser
5	Memory	Conversation history, buffer, summary memory
6	RAG (Retrieval-Augmented Generation)	Embeddings, vector stores, retrieval, Q&A
7	Tools & Function Calling	Defining tools, structured output, tool use
8	Agents	ReAct agent, tool selection, reasoning loop
9	Multi-Agent Systems	Orchestrator/worker, handoffs, parallelism
10	Agentic Patterns	Planning, reflection, self-critique, loops

Tip: Run cells top-to-bottom. Set your provider once in Section 1 and everything else adapts.

Section 1 — Setup & Provider Configuration

# Install all required packages
# Re-run this cell any time you start a fresh environment
# Remove -v if you want quiet output; add -q for silent mode
%pip install -v \
    langchain \
    langchain-ollama \
    langchain-openai \
    langchain-google-genai \
    langchain-chroma \
    langchain-core \
    langgraph \
    chromadb \
    ollama \
    google-generativeai \
    openai \
    tiktoken \
    faiss-cpu \
    sentence-transformers \
    pypdf \
    httpx \
    ipywidgets
print("All packages installed.")

from IPython.display import display, Markdown

# ============================================================
# CONFIGURE YOUR PROVIDER HERE — change PROVIDER and fill in
# the relevant key/model. Everything else in the notebook
# uses `llm` and `embeddings` defined below.
# ============================================================

import os

# Choose: "ollama" | "openai" | "gemini" | "deepseek"
PROVIDER = "ollama"

# --- Ollama (runs locally, no key needed) ---
OLLAMA_BASE_URL  = "http://localhost:11434"
OLLAMA_MODEL     = "llama3.2:latest"   # change to any model you have pulled
OLLAMA_EMBED     = "nomic-embed-text:latest"

# --- OpenAI ---
OPENAI_API_KEY   = os.getenv("OPENAI_API_KEY", "sk-...")
OPENAI_MODEL     = "gpt-4o-mini"

# --- Google Gemini ---
GOOGLE_API_KEY   = os.getenv("GOOGLE_API_KEY", "...")
GEMINI_MODEL     = "gemini-1.5-flash"

# --- DeepSeek (OpenAI-compatible endpoint) ---
DEEPSEEK_API_KEY = os.getenv("DEEPSEEK_API_KEY", "sk-...")
DEEPSEEK_MODEL   = "deepseek-chat"
DEEPSEEK_BASE_URL = "https://api.deepseek.com/v1"

print(f"Provider set to: {PROVIDER}")

# Build the shared `llm` and `embeddings` objects used throughout
from langchain_core.language_models.chat_models import BaseChatModel

if PROVIDER == "ollama":
    from langchain_ollama import ChatOllama, OllamaEmbeddings
    llm = ChatOllama(model=OLLAMA_MODEL, base_url=OLLAMA_BASE_URL, temperature=0.7)
    embeddings = OllamaEmbeddings(model=OLLAMA_EMBED, base_url=OLLAMA_BASE_URL)

elif PROVIDER == "openai":
    from langchain_openai import ChatOpenAI, OpenAIEmbeddings
    llm = ChatOpenAI(model=OPENAI_MODEL, api_key=OPENAI_API_KEY, temperature=0.7)
    embeddings = OpenAIEmbeddings(api_key=OPENAI_API_KEY)

elif PROVIDER == "gemini":
    from langchain_google_genai import ChatGoogleGenerativeAI, GoogleGenerativeAIEmbeddings
    llm = ChatGoogleGenerativeAI(model=GEMINI_MODEL, google_api_key=GOOGLE_API_KEY, temperature=0.7)
    embeddings = GoogleGenerativeAIEmbeddings(model="models/embedding-001", google_api_key=GOOGLE_API_KEY)

elif PROVIDER == "deepseek":
    from langchain_openai import ChatOpenAI, OpenAIEmbeddings
    llm = ChatOpenAI(
        model=DEEPSEEK_MODEL,
        api_key=DEEPSEEK_API_KEY,
        base_url=DEEPSEEK_BASE_URL,
        temperature=0.7
    )
    # DeepSeek does not expose embeddings; fall back to Ollama local embeddings
    from langchain_ollama import OllamaEmbeddings
    embeddings = OllamaEmbeddings(model=OLLAMA_EMBED, base_url=OLLAMA_BASE_URL)

else:
    raise ValueError(f"Unknown provider: {PROVIDER}")

print(f"LLM ready: {llm}")
print(f"Embeddings ready: {embeddings}")

Section 2 — LLM Basics

Key concepts: - Token: smallest unit of text the model processes (~0.75 words) - Temperature: controls randomness (0 = deterministic, 1+ = creative) - Context window: max tokens the model can see at once - Completion vs Chat: older models do text completion; modern models use a chat (message) format - System / Human / AI messages: the three roles in a conversation

# 2a. Simple single-turn call
from IPython.display import display, Markdown
from langchain_core.messages import HumanMessage

response = llm.invoke([HumanMessage(content="What is a large language model? Explain in 3 sentences.")])
display(Markdown(response.content))

# 2b. System + Human messages
from IPython.display import display, Markdown
from langchain_core.messages import SystemMessage, HumanMessage

messages = [
    SystemMessage(content="You are a concise technical tutor. Always answer in bullet points."),
    HumanMessage(content="What are tokens in the context of LLMs?")
]
response = llm.invoke(messages)
display(Markdown(response.content))

# 2c. Temperature effect — compare deterministic vs creative output
from IPython.display import display, Markdown
from langchain_core.messages import HumanMessage

if PROVIDER == "ollama":
    from langchain_ollama import ChatOllama
    llm_cold = ChatOllama(model=OLLAMA_MODEL, base_url=OLLAMA_BASE_URL, temperature=0.0)
    llm_hot  = ChatOllama(model=OLLAMA_MODEL, base_url=OLLAMA_BASE_URL, temperature=1.2)
elif PROVIDER == "openai":
    from langchain_openai import ChatOpenAI
    llm_cold = ChatOpenAI(model=OPENAI_MODEL, api_key=OPENAI_API_KEY, temperature=0.0)
    llm_hot  = ChatOpenAI(model=OPENAI_MODEL, api_key=OPENAI_API_KEY, temperature=1.2)
elif PROVIDER == "gemini":
    from langchain_google_genai import ChatGoogleGenerativeAI
    llm_cold = ChatGoogleGenerativeAI(model=GEMINI_MODEL, google_api_key=GOOGLE_API_KEY, temperature=0.0)
    llm_hot  = ChatGoogleGenerativeAI(model=GEMINI_MODEL, google_api_key=GOOGLE_API_KEY, temperature=1.0)
else:
    llm_cold = llm_hot = llm

question = [HumanMessage(content="Give me one creative name for an AI assistant.")]

cold_names = [llm_cold.invoke(question).content.strip() for _ in range(3)]
hot_names  = [llm_hot.invoke(question).content.strip()  for _ in range(3)]

display(Markdown("### Cold (deterministic, temperature=0)\n" + "\n".join(f"- {n}" for n in cold_names)))
display(Markdown("### Hot (creative, temperature=1.2)\n"     + "\n".join(f"- {n}" for n in hot_names)))

# 2d. Streaming output — see tokens arrive in real-time
from IPython.display import display, Markdown
from langchain_core.messages import HumanMessage

chunks = []
for chunk in llm.stream([HumanMessage(content="Tell me a very short joke about AI.")]):
    print(chunk.content, end="", flush=True)
    chunks.append(chunk.content)
print()
display(Markdown("---\n**Rendered:**\n\n" + "".join(chunks)))

Section 3 — Prompt Engineering

Key concepts: - Zero-shot: ask without examples - Few-shot: give examples in the prompt to guide output format - Chain-of-Thought (CoT): ask the model to reason step-by-step before answering - Prompt templates: reusable prompts with variables - Output parsers: extract structured data from model responses

# 3a. PromptTemplate — reusable prompt with variables
from IPython.display import display, Markdown
from langchain_core.prompts import ChatPromptTemplate

template = ChatPromptTemplate.from_messages([
    ("system", "You are an expert in {domain}."),
    ("human", "Explain {concept} to a {audience}.")
])

chain = template | llm

result = chain.invoke({
    "domain": "machine learning",
    "concept": "gradient descent",
    "audience": "10-year-old"
})
display(Markdown(result.content))

# 3b. Few-shot prompting — guide output format with examples
from IPython.display import display, Markdown
from langchain_core.prompts import ChatPromptTemplate

few_shot_template = ChatPromptTemplate.from_messages([
    ("system", "You classify customer feedback as Positive, Negative, or Neutral. Reply with only the label."),
    ("human", "The product broke after one day."),
    ("ai", "Negative"),
    ("human", "It's okay, nothing special."),
    ("ai", "Neutral"),
    ("human", "Absolutely love it, best purchase ever!"),
    ("ai", "Positive"),
    ("human", "{feedback}")
])

chain = few_shot_template | llm

tests = [
    "Delivery was late but the item was fine.",
    "Terrible customer service, would not recommend.",
    "Exceeded my expectations!"
]

rows = ["| Feedback | Sentiment |", "|----------|-----------|"]
for t in tests:
    label = chain.invoke({"feedback": t}).content.strip()
    rows.append(f"| {t} | **{label}** |")

display(Markdown("\n".join(rows)))

# 3c. Chain-of-Thought (CoT) — ask to reason before answering
from IPython.display import display, Markdown
from langchain_core.prompts import ChatPromptTemplate

cot_prompt = ChatPromptTemplate.from_messages([
    ("system", "You are a careful reasoner. Think step-by-step before giving your final answer. Format: REASONING: ... ANSWER: ..."),
    ("human", "{question}")
])

chain = cot_prompt | llm
result = chain.invoke({"question": "If I have 3 boxes with 4 apples each, and I give away 5 apples, how many do I have left?"})
display(Markdown(result.content))

# 3d. Structured output with JSON — output parser
from IPython.display import display, Markdown
from langchain_core.output_parsers import JsonOutputParser
from langchain_core.prompts import ChatPromptTemplate
import json

json_prompt = ChatPromptTemplate.from_messages([
    ("system", """You extract structured information. Always respond with valid JSON only.
Schema: {{"name": string, "country": string, "founded_year": int, "main_product": string}}"""),
    ("human", "Tell me about: {company}")
])

chain = json_prompt | llm | JsonOutputParser()

result = chain.invoke({"company": "Tesla"})
display(Markdown(f"```json\n{json.dumps(result, indent=2)}\n```"))

Section 4 — Chains

Key concepts: - LCEL (LangChain Expression Language): pipe | operator to compose components - Sequential chain: output of one step feeds into the next - Parallel chain: run multiple LLM calls simultaneously - Branching: route to different chains based on content

# 4a. Simple LCEL chain: prompt → llm → string parser
from IPython.display import display, Markdown
from langchain_core.output_parsers import StrOutputParser
from langchain_core.prompts import ChatPromptTemplate

summarize_chain = (
    ChatPromptTemplate.from_template("Summarize the following text in one sentence:\n\n{text}")
    | llm
    | StrOutputParser()
)

text = """The James Webb Space Telescope (JWST) is a space telescope designed to conduct infrared
astronomy. Its high resolution and sensitivity allow it to view objects too old, distant, or faint
for the Hubble Space Telescope. It is the largest optical telescope in space."""

result = summarize_chain.invoke({"text": text})
display(Markdown(result))

# 4b. Sequential chain — translate then explain
from IPython.display import display, Markdown
from langchain_core.output_parsers import StrOutputParser
from langchain_core.prompts import ChatPromptTemplate

translate_prompt = ChatPromptTemplate.from_template(
    "Translate the following text to French:\n{text}"
)
explain_prompt = ChatPromptTemplate.from_template(
    "Explain why this French sentence is grammatically correct:\n{translated}"
)

parser = StrOutputParser()

full_chain = (
    translate_prompt | llm | parser
    | (lambda translated: {"translated": translated})
    | explain_prompt | llm | parser
)

result = full_chain.invoke({"text": "The sun rises in the east."})
display(Markdown(result))

# 4c. Parallel chains using RunnableParallel
from IPython.display import display, Markdown
from langchain_core.runnables import RunnableParallel
from langchain_core.output_parsers import StrOutputParser
from langchain_core.prompts import ChatPromptTemplate

pros_chain = ChatPromptTemplate.from_template("List 3 pros of {topic}") | llm | StrOutputParser()
cons_chain = ChatPromptTemplate.from_template("List 3 cons of {topic}") | llm | StrOutputParser()

parallel = RunnableParallel(pros=pros_chain, cons=cons_chain)

result = parallel.invoke({"topic": "working from home"})
display(Markdown(f"### Pros\n{result['pros']}\n\n### Cons\n{result['cons']}"))

Section 5 — Memory & Conversation History

Key concepts: - Stateless LLMs: by default, each call is independent — no memory - Conversation buffer: store the full chat history and pass it each turn - Summary memory: summarize older turns to stay within context window - LangGraph persistence: the modern way to add memory — graph state is checkpointed per thread_id

# 5a. Manual message history — see what "memory" means at the raw level
from IPython.display import display, Markdown
from langchain_core.messages import HumanMessage, AIMessage, SystemMessage

history = [SystemMessage(content="You are a helpful assistant. Remember details the user shares.")]

def chat(user_input):
    history.append(HumanMessage(content=user_input))
    response = llm.invoke(history)
    history.append(AIMessage(content=response.content))
    return response.content

display(Markdown(f"**User:** Hi, my name is Alex and I love hiking.\n\n**AI:** {chat('Hi, my name is Alex and I love hiking.')}"))
display(Markdown(f"**User:** What do I love doing?\n\n**AI:** {chat('What do I love doing?')}"))
display(Markdown(f"**User:** What is my name?\n\n**AI:** {chat('What is my name?')}"))

# 5b. LangGraph persistent memory — modern replacement for RunnableWithMessageHistory
from IPython.display import display, Markdown
from langgraph.checkpoint.memory import MemorySaver
from langgraph.graph import START, MessagesState, StateGraph
from langchain_core.messages import HumanMessage, SystemMessage

# Define a single node that calls the LLM with full message history
def call_llm(state: MessagesState):
    system = SystemMessage(content="You are a friendly assistant.")
    response = llm.invoke([system] + state["messages"])
    return {"messages": response}

# Build a minimal graph: START → llm node
builder = StateGraph(MessagesState)
builder.add_node("llm", call_llm)
builder.add_edge(START, "llm")

# MemorySaver checkpoints the full message history per thread_id in-memory
graph = builder.compile(checkpointer=MemorySaver())

cfg = {"configurable": {"thread_id": "user_1"}}

def chat_lg(user_input):
    result = graph.invoke({"messages": [HumanMessage(content=user_input)]}, config=cfg)
    return result["messages"][-1].content

r1 = chat_lg("My favourite colour is blue.")
r2 = chat_lg("What is my favourite colour?")

display(Markdown(f"**Turn 1:** My favourite colour is blue.\n\n**AI:** {r1}"))
display(Markdown(f"**Turn 2:** What is my favourite colour?\n\n**AI:** {r2}"))

# 5c. Summary memory concept — summarise old turns to save tokens
from IPython.display import display, Markdown
from langchain_core.prompts import ChatPromptTemplate
from langchain_core.output_parsers import StrOutputParser

old_conversation = """
User: I'm planning a trip to Japan in October.
AI: Great choice! October is beautiful in Japan — autumn foliage begins.
User: I want to visit Tokyo and Kyoto.
AI: Perfect itinerary. Tokyo for modern culture, Kyoto for temples and history.
User: I have 10 days total.
AI: Suggested split: 5 days Tokyo, 4 days Kyoto, 1 day Nara as a day trip.
"""

summarize = (
    ChatPromptTemplate.from_template(
        "Summarize this conversation history into 2-3 bullet points for context:\n{history}"
    ) | llm | StrOutputParser()
)

summary = summarize.invoke({"history": old_conversation})
display(Markdown(f"### Summary stored as context\n{summary}"))

Section 6 — RAG (Retrieval-Augmented Generation)

Key concepts: - Embeddings: numerical vector representations of text (similar texts → similar vectors) - Vector store: database for storing and searching embeddings (ChromaDB, FAISS) - Semantic search: find relevant text by meaning, not keyword match - RAG pipeline: Retrieve relevant docs → Augment prompt → Generate answer - Why RAG? Extends LLM knowledge with your own data without retraining

# 6a. Embeddings — visualise what they are
from IPython.display import display, Markdown
import numpy as np

sentences = [
    "The cat sat on the mat.",
    "A feline rested on the rug.",
    "The stock market crashed today.",
]

vecs = embeddings.embed_documents(sentences)

def cosine(a, b):
    a, b = np.array(a), np.array(b)
    return float(np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b)))

sim_1_2 = cosine(vecs[0], vecs[1])
sim_1_3 = cosine(vecs[0], vecs[2])

display(Markdown(f"""
**Embedding dimension:** {len(vecs[0])}

| Pair | Cosine Similarity |
|------|-------------------|
| cat / feline (similar) | `{sim_1_2:.4f}` |
| cat / stock market (unrelated) | `{sim_1_3:.4f}` |

> Higher score = more semantically similar
"""))

# 6b. Build a vector store from sample documents
from langchain_chroma import Chroma
from langchain_core.documents import Document

docs = [
    Document(page_content="Python is a high-level, interpreted programming language known for readability.", metadata={"source": "python_wiki"}),
    Document(page_content="Python supports multiple programming paradigms including procedural, object-oriented, and functional.", metadata={"source": "python_wiki"}),
    Document(page_content="Rust is a systems programming language focused on safety, speed, and concurrency.", metadata={"source": "rust_wiki"}),
    Document(page_content="Rust's borrow checker prevents memory bugs at compile time without a garbage collector.", metadata={"source": "rust_wiki"}),
    Document(page_content="JavaScript is the primary language for web frontend development, running in browsers.", metadata={"source": "js_wiki"}),
    Document(page_content="Node.js allows JavaScript to run on the server side, enabling full-stack JS development.", metadata={"source": "js_wiki"}),
    Document(page_content="Go (Golang) is designed for simplicity and high-performance concurrent server applications.", metadata={"source": "go_wiki"}),
]

vectorstore = Chroma.from_documents(docs, embedding=embeddings, collection_name="programming_langs")
print(f"Vector store created with {vectorstore._collection.count()} documents.")

# 6c. Semantic search
from IPython.display import display, Markdown

query = "What language prevents memory bugs at compile time?"
results = vectorstore.similarity_search(query, k=2)

rows = [f"**Query:** {query}\n", "| # | Source | Content |", "|---|--------|---------|"]
for i, doc in enumerate(results):
    rows.append(f"| {i+1} | `{doc.metadata['source']}` | {doc.page_content} |")

display(Markdown("\n".join(rows)))

# 6d. Full RAG pipeline — retrieval + generation
from IPython.display import display, Markdown
from langchain_core.prompts import ChatPromptTemplate
from langchain_core.output_parsers import StrOutputParser
from langchain_core.runnables import RunnablePassthrough

retriever = vectorstore.as_retriever(search_kwargs={"k": 3})

def format_docs(docs):
    return "\n\n".join(doc.page_content for doc in docs)

rag_prompt = ChatPromptTemplate.from_messages([
    ("system", """You are a helpful assistant. Answer the question using ONLY the context provided.
If the answer is not in the context, say 'I don't know based on the provided information.'

Context:
{context}"""),
    ("human", "{question}")
])

rag_chain = (
    {"context": retriever | format_docs, "question": RunnablePassthrough()}
    | rag_prompt
    | llm
    | StrOutputParser()
)

questions = [
    "Which language is best for web frontend development?",
    "What makes Rust special compared to other languages?",
    "What is the capital of France?"
]

for q in questions:
    answer = rag_chain.invoke(q)
    display(Markdown(f"**Q:** {q}\n\n**A:** {answer}\n\n---"))

# 6e. Text splitter — handling large documents
from langchain_text_splitters import RecursiveCharacterTextSplitter

long_text = """Artificial intelligence (AI) is intelligence demonstrated by machines, as opposed to the natural
intelligence displayed by animals including humans. AI research has been defined as the field of study of
intelligent agents, which refers to any system that perceives its environment and takes actions that maximize
its chance of achieving its goals. The term artificial intelligence had previously been used to describe
machines that mimic and display human cognitive skills associated with the human mind, such as learning and
problem-solving. This definition has since been rejected by major AI researchers who now describe AI in terms
of rationality and acting rationally, which does not limit how intelligence can be articulated.

AI applications include advanced web search engines, recommendation systems (used by YouTube, Amazon and Netflix),
understanding human speech (such as Siri and Alexa), self-driving cars (such as Waymo), generative or creative
tools (ChatGPT and AI art), automated decision-making and competing at the highest level in strategic game
systems (such as chess and Go). As machines become increasingly capable, tasks considered to require intelligence
are often removed from the definition of AI, a phenomenon known as the AI effect."""

splitter = RecursiveCharacterTextSplitter(chunk_size=200, chunk_overlap=30)
chunks = splitter.create_documents([long_text])

print(f"Split into {len(chunks)} chunks:")
for i, c in enumerate(chunks):
    print(f"  Chunk {i+1} ({len(c.page_content)} chars): {c.page_content[:80]}...")

Section 7 — Tools & Function Calling

Key concepts: - Tools: functions the LLM can choose to call (calculator, search, API) - Function calling: the model outputs a structured JSON call instead of plain text - Tool schema: name + description + input schema — the model reads descriptions to decide when to use a tool - Structured output: force the model to return a specific schema

# 7a. Define tools using @tool decorator
from langchain_core.tools import tool
import math
import datetime

@tool
def calculator(expression: str) -> str:
    """Evaluate a mathematical expression. Input must be a valid Python math expression.
    Examples: '2 + 2', 'math.sqrt(144)', '15 * 7 / 3'"""
    try:
        result = eval(expression, {"__builtins__": {}}, {"math": math})
        return str(result)
    except Exception as e:
        return f"Error: {e}"

@tool
def get_current_date(timezone: str = "UTC") -> str:
    """Get the current date and time. Optionally specify a timezone name."""
    return datetime.datetime.now().strftime(f"%Y-%m-%d %H:%M:%S ({timezone})")

@tool
def word_count(text: str) -> str:
    """Count the number of words in a text string."""
    return str(len(text.split()))

print("Tools defined:")
for t in [calculator, get_current_date, word_count]:
    print(f"  - {t.name}: {t.description[:60]}...")

# 7b. Bind tools to the LLM and handle a tool call manually
from langchain_core.messages import HumanMessage, AIMessage, ToolMessage

tools = [calculator, get_current_date, word_count]
llm_with_tools = llm.bind_tools(tools)

messages = [HumanMessage(content="What is 15% of 240? Also what is today's date?")]

# First call — model may return tool calls instead of a final answer
ai_msg = llm_with_tools.invoke(messages)
messages.append(ai_msg)

print(f"Tool calls requested: {len(ai_msg.tool_calls)}")
for tc in ai_msg.tool_calls:
    print(f"  Tool: {tc['name']}, Args: {tc['args']}")

# Execute each tool
tool_map = {t.name: t for t in tools}
for tc in ai_msg.tool_calls:
    result = tool_map[tc["name"]].invoke(tc["args"])
    messages.append(ToolMessage(content=result, tool_call_id=tc["id"]))

# Second call — model now has tool results, produces final answer
final = llm_with_tools.invoke(messages)
print(f"\nFinal answer: {final.content}")

# 7c. Structured output — force model to return a specific schema
from pydantic import BaseModel, Field
from typing import List

class MovieReview(BaseModel):
    title: str = Field(description="Movie title")
    year: int = Field(description="Release year")
    sentiment: str = Field(description="Overall sentiment: positive, negative, or mixed")
    score: float = Field(description="Score out of 10")
    pros: List[str] = Field(description="List of positive aspects")
    cons: List[str] = Field(description="List of negative aspects")

structured_llm = llm.with_structured_output(MovieReview)

review_text = """
Interstellar (2014) is a visually stunning sci-fi epic. The space sequences are breathtaking,
Hans Zimmer's score is unforgettable, and McConaughey's performance is moving. However,
the third act gets overly convoluted and the science is sometimes stretched too thin.
Overall a great film, 8/10.
"""

review = structured_llm.invoke(f"Extract a structured review from this text:\n{review_text}")
print(review.model_dump_json(indent=2))

Section 8 — Agents

Key concepts: - Agent: an LLM that can choose which tools to use, call them, observe results, and repeat - ReAct pattern: Reason → Act → Observe → (repeat until done) - Reasoning loop: the agent keeps calling tools until it has enough info to answer - Agent executor: runtime that manages the tool-call loop - Stopping condition: agent decides when it has a final answer

# 8a. ReAct agent — see the reasoning loop step by step
from IPython.display import display, Markdown
from langchain.agents import create_agent
from langchain_core.tools import tool
import math, datetime

@tool
def calculator(expression: str) -> str:
    """Evaluate a math expression. Example: '2 ** 10' or 'math.sqrt(144)'"""
    try:
        return str(eval(expression, {"__builtins__": {}}, {"math": math}))
    except Exception as e:
        return f"Error: {e}"

@tool
def get_current_year(dummy: str = "") -> str:
    """Returns the current year as a string."""
    return str(datetime.datetime.now().year)

@tool
def string_reverse(text: str) -> str:
    """Reverses a string. Input: any text string."""
    return text[::-1]

agent_tools = [calculator, get_current_year, string_reverse]

# create_agent builds a StateGraph with a tool-calling loop internally
agent = create_agent(llm, agent_tools)

result = agent.invoke({
    "messages": [("human", "What is 2 to the power of 10, and what is that number reversed as a string?")]
})

answer = result["messages"][-1].content
display(Markdown(f"**Answer:** {answer}"))

# Show the reasoning steps
display(Markdown("---\n**Reasoning trace:**"))
for msg in result["messages"]:
    role = msg.__class__.__name__.replace("Message", "")
    content = msg.content or str(getattr(msg, "tool_calls", ""))
    display(Markdown(f"- **{role}:** {str(content)[:200]}"))

# 8b. create_agent with a custom system prompt
from IPython.display import display, Markdown
from langchain.agents import create_agent

# Pass a system prompt string directly
agent = create_agent(
    llm,
    agent_tools,
    system_prompt="You are a helpful assistant. Use tools when needed to answer accurately."
)

result = agent.invoke({
    "messages": [("human", "What year is it, and what is sqrt(year) rounded to 2 decimal places?")]
})

answer = result["messages"][-1].content
display(Markdown(f"**Answer:** {answer}"))

# 8c. RAG-enabled agent — agent can choose to retrieve from the knowledge base
from IPython.display import display, Markdown
from langchain.agents import create_agent
from langchain_core.tools import tool
import math

@tool
def calculator(expression: str) -> str:
    """Evaluate a math expression. Example: '2 ** 10' or 'math.sqrt(144)'"""
    try:
        return str(eval(expression, {"__builtins__": {}}, {"math": math}))
    except Exception as e:
        return f"Error: {e}"

@tool
def search_programming_knowledge(query: str) -> str:
    """Search the programming languages knowledge base. Use for questions about Python, Rust, JavaScript, or Go."""
    results = vectorstore.similarity_search(query, k=2)
    return "\n".join(doc.page_content for doc in results)

rag_tools = [calculator, search_programming_knowledge]

rag_agent = create_agent(
    llm,
    rag_tools,
    system_prompt="You are a knowledgeable assistant. Always search the knowledge base before answering."
)

result = rag_agent.invoke({
    "messages": [("human", "Compare Python and Rust. Which one prevents memory bugs at compile time?")]
})

display(Markdown(f"**Answer:** {result['messages'][-1].content}"))

Section 9 — Multi-Agent Systems

Key concepts: - Orchestrator: a central agent that plans and delegates tasks - Worker/Specialist agent: focused on one domain (code, research, math) - Handoff: passing a task from one agent to another - Why multi-agent? Complex tasks benefit from specialisation and parallelism - Agent-as-tool: wrap one agent as a callable tool for another agent

# 9a. Specialist agents used as tools by an orchestrator
from IPython.display import display, Markdown
from langchain.agents import create_agent
from langchain_core.tools import tool

# --- Specialist: Code Explainer ---
code_agent = create_agent(
    llm, [],
    system_prompt="You are an expert programmer. Explain code clearly and concisely."
)

# --- Specialist: Writer ---
writer_agent = create_agent(
    llm, [],
    system_prompt="You are a professional writer. Produce clear, engaging content."
)

# --- Wrap specialists as tools for the orchestrator ---
@tool
def ask_code_agent(task: str) -> str:
    """Delegate a coding or code-explanation task to the specialist code agent."""
    result = code_agent.invoke({"messages": [("human", task)]})
    return result["messages"][-1].content

@tool
def ask_writer_agent(task: str) -> str:
    """Delegate a writing or content-creation task to the specialist writer agent."""
    result = writer_agent.invoke({"messages": [("human", task)]})
    return result["messages"][-1].content

# --- Orchestrator ---
orchestrator = create_agent(
    llm,
    [ask_code_agent, ask_writer_agent],
    system_prompt="""You are an orchestrator. Break down complex tasks and delegate to the right specialist:
- ask_code_agent: for coding, code explanation, technical topics
- ask_writer_agent: for writing, summarising, or creative content
Combine their outputs into a final cohesive answer."""
)

result = orchestrator.invoke({
    "messages": [("human", "Explain what a Python list comprehension is and then write a short blog intro about why Python is beginner-friendly.")]
})

display(Markdown(f"### Final Answer\n{result['messages'][-1].content}"))

# 9b. Parallel multi-agent execution (manual)
import concurrent.futures
from IPython.display import display, Markdown
from langchain_core.messages import HumanMessage

def run_agent(role, system_prompt, question):
    from langchain_core.messages import SystemMessage, HumanMessage
    response = llm.invoke([
        SystemMessage(content=system_prompt),
        HumanMessage(content=question)
    ])
    return role, response.content

agents_config = [
    ("Optimist", "You are an optimist. Find the positive aspects of any topic.", "What is the impact of AI on jobs?"),
    ("Pessimist", "You are a pessimist. Find the risks and downsides of any topic.", "What is the impact of AI on jobs?"),
    ("Neutral",  "You are a balanced analyst. Give a factual, neutral assessment.", "What is the impact of AI on jobs?"),
]

with concurrent.futures.ThreadPoolExecutor() as pool:
    futures = [pool.submit(run_agent, *cfg) for cfg in agents_config]
    results = [f.result() for f in concurrent.futures.as_completed(futures)]

for role, answer in sorted(results):
    display(Markdown(f"### {role}\n{answer}"))

Section 10 — Agentic Patterns

Key concepts: - Planning: agent decomposes a goal into sub-tasks before acting - Reflection / self-critique: agent reviews and improves its own output - Tool-use loops: repeat until a stopping condition is met - Human-in-the-loop: pause for human approval before proceeding - Evaluator-Optimizer: one LLM generates, another scores/critiques, loop until quality threshold - Map-Reduce: process many items in parallel (map), synthesise results (reduce)

# 10a. Planning pattern — decompose a goal before acting
from IPython.display import display, Markdown
from langchain_core.prompts import ChatPromptTemplate
from langchain_core.output_parsers import JsonOutputParser

plan_prompt = ChatPromptTemplate.from_messages([
    ("system", """You are a planning agent. Break down the user's goal into a numbered list of concrete sub-tasks.
Return JSON: {{"goal": string, "tasks": [{{"id": int, "task": string, "depends_on": []}}]}}"""),
    ("human", "Goal: {goal}")
])

planner = plan_prompt | llm | JsonOutputParser()

plan = planner.invoke({"goal": "Build a simple weather app that shows current temperature"})

rows = [f"**Goal:** {plan['goal']}\n", "| # | Task | Depends On |", "|---|------|------------|"]
for task in plan["tasks"]:
    deps = ", ".join(str(d) for d in task["depends_on"]) if task["depends_on"] else "—"
    rows.append(f"| {task['id']} | {task['task']} | {deps} |")

display(Markdown("\n".join(rows)))

# 10b. Reflection pattern — generate → critique → improve
from IPython.display import display, Markdown
from langchain_core.prompts import ChatPromptTemplate
from langchain_core.output_parsers import StrOutputParser

generate_prompt = ChatPromptTemplate.from_template(
    "Write a short paragraph explaining {topic} for a beginner."
)
critique_prompt = ChatPromptTemplate.from_messages([
    ("system", "You are a strict writing critic. Identify specific weaknesses: unclear terms, missing context, poor flow. Be concise."),
    ("human", "Critique this explanation:\n\n{draft}")
])
improve_prompt = ChatPromptTemplate.from_messages([
    ("system", "You are a writing improver. Fix the issues identified in the critique."),
    ("human", "Original:\n{draft}\n\nCritique:\n{critique}\n\nWrite an improved version:")
])

parser = StrOutputParser()

topic = "neural networks"

draft    = (generate_prompt | llm | parser).invoke({"topic": topic})
critique = (critique_prompt | llm | parser).invoke({"draft": draft})
improved = (improve_prompt  | llm | parser).invoke({"draft": draft, "critique": critique})

display(Markdown(f"### Draft\n{draft}"))
display(Markdown(f"### Critique\n{critique}"))
display(Markdown(f"### Improved\n{improved}"))

# 10c. Evaluator-Optimizer loop — iterate until quality score >= threshold
from IPython.display import display, Markdown
from langchain_core.prompts import ChatPromptTemplate
from langchain_core.output_parsers import JsonOutputParser, StrOutputParser

write_prompt = ChatPromptTemplate.from_template(
    "Write a haiku about {subject}. Just the haiku, no commentary."
)
eval_prompt = ChatPromptTemplate.from_messages([
    ("system", "Score the haiku 1-10 for creativity and adherence to 5-7-5 syllable structure. Return JSON: {{\"score\": int, \"feedback\": string}}"),
    ("human", "{haiku}")
])
improve_prompt = ChatPromptTemplate.from_template(
    "Improve this haiku based on this feedback: {feedback}\n\nOriginal:\n{haiku}\n\nImproved haiku (just the haiku):"
)

writer    = write_prompt   | llm | StrOutputParser()
evaluator = eval_prompt    | llm | JsonOutputParser()
improver  = improve_prompt | llm | StrOutputParser()

THRESHOLD = 7
MAX_ROUNDS = 4

haiku = writer.invoke({"subject": "machine learning"})
display(Markdown(f"**Round 0 (initial):**\n\n{haiku}"))

for round_num in range(1, MAX_ROUNDS + 1):
    evaluation = evaluator.invoke({"haiku": haiku})
    score, feedback = evaluation["score"], evaluation["feedback"]
    display(Markdown(f"**Round {round_num} score:** {score}/10 — {feedback}"))
    if score >= THRESHOLD:
        display(Markdown(f"**Accepted! Final haiku:**\n\n{haiku}"))
        break
    haiku = improver.invoke({"haiku": haiku, "feedback": feedback})
    display(Markdown(f"**Improved:**\n\n{haiku}"))
else:
    display(Markdown(f"**Max rounds reached. Best haiku:**\n\n{haiku}"))

# 10d. Map-Reduce pattern — summarise multiple documents in parallel
import concurrent.futures
from IPython.display import display, Markdown
from langchain_core.prompts import ChatPromptTemplate
from langchain_core.output_parsers import StrOutputParser

documents = [
    "Python was created by Guido van Rossum and first released in 1991. It emphasises code readability and simplicity.",
    "JavaScript was created by Brendan Eich at Netscape in 1995. Originally designed for browser scripting, it now runs on servers via Node.js.",
    "Rust was designed by Graydon Hoare at Mozilla Research and announced in 2010. It guarantees memory safety without a garbage collector.",
    "Go was created at Google by Robert Griesemer, Rob Pike, and Ken Thompson, released in 2009. It prioritises simplicity and fast compile times.",
]

map_chain = (
    ChatPromptTemplate.from_template("Summarise in one sentence: {doc}")
    | llm | StrOutputParser()
)

reduce_chain = (
    ChatPromptTemplate.from_template(
        "Given these summaries of programming languages:\n{summaries}\n\nWrite a 2-sentence overall synthesis."
    ) | llm | StrOutputParser()
)

with concurrent.futures.ThreadPoolExecutor() as pool:
    summaries = list(pool.map(lambda d: map_chain.invoke({"doc": d}), documents))

display(Markdown("### MAP (individual summaries)\n" + "\n".join(f"- {s}" for s in summaries)))

synthesis = reduce_chain.invoke({"summaries": "\n".join(f"- {s}" for s in summaries)})
display(Markdown(f"### REDUCE (synthesis)\n{synthesis}"))

# 10e. Human-in-the-loop — agent pauses for approval before taking an action
from langchain_core.messages import HumanMessage, AIMessage
from langchain_core.tools import tool

@tool
def send_email(recipient: str, subject: str, body: str) -> str:
    """Send an email. Requires human approval before sending."""
    return f"Email sent to {recipient} with subject '{subject}'"

def agent_with_approval(user_request: str):
    """An agent loop that pauses for human approval before calling dangerous tools."""
    APPROVAL_REQUIRED = {"send_email"}

    llm_tools = llm.bind_tools([send_email])
    messages = [HumanMessage(content=user_request)]

    for step in range(5):
        response = llm_tools.invoke(messages)
        messages.append(response)

        if not response.tool_calls:
            print(f"\nAgent: {response.content}")
            break

        for tc in response.tool_calls:
            print(f"\nAgent wants to call: {tc['name']}({tc['args']})")

            if tc["name"] in APPROVAL_REQUIRED:
                approval = input("Approve? (yes/no): ").strip().lower()
                if approval != "yes":
                    result = "Action cancelled by user."
                else:
                    result = send_email.invoke(tc["args"])
            else:
                result = send_email.invoke(tc["args"])

            from langchain_core.messages import ToolMessage
            messages.append(ToolMessage(content=result, tool_call_id=tc["id"]))

agent_with_approval("Please draft and send an email to alice@example.com about our meeting next Monday at 10am.")

Section 11 — Putting It All Together: Mini Agentic App

A complete mini-application combining: RAG + Tools + Memory + Reflection

This is a Research Assistant that: 1. Retrieves relevant knowledge from a vector store (RAG) 2. Can do calculations 3. Remembers the conversation (Memory) 4. Reflects and refines answers before responding

# 11. Mini Agentic Research Assistant — LangGraph memory + tools + reflection
from IPython.display import display, Markdown
from langgraph.checkpoint.memory import MemorySaver
from langgraph.graph import START, MessagesState, StateGraph
from langgraph.prebuilt import ToolNode, tools_condition
from langchain_core.tools import tool
from langchain_core.messages import HumanMessage, SystemMessage
import math

@tool
def knowledge_base_search(query: str) -> str:
    """Search the programming languages knowledge base for factual information."""
    results = vectorstore.similarity_search(query, k=3)
    if not results:
        return "No relevant information found in the knowledge base."
    return "\n".join(f"[{r.metadata['source']}] {r.page_content}" for r in results)

@tool
def calculator(expression: str) -> str:
    """Evaluate a math expression like '2 ** 10' or 'math.sqrt(144)'."""
    try:
        return str(eval(expression, {"__builtins__": {}}, {"math": math}))
    except Exception as e:
        return f"Error: {e}"

@tool
def self_reflect(draft_answer: str) -> str:
    """Critically evaluate a draft answer and suggest improvements."""
    response = llm.invoke([
        SystemMessage(content="You are a critical reviewer. Evaluate for accuracy, completeness, and clarity. Suggest 2-3 improvements."),
        HumanMessage(content=draft_answer)
    ])
    return response.content

assistant_tools = [knowledge_base_search, calculator, self_reflect]
llm_with_tools  = llm.bind_tools(assistant_tools)

SYSTEM = SystemMessage(content="""You are an intelligent research assistant with access to:
1. knowledge_base_search — look up factual information
2. calculator — numerical computation
3. self_reflect — critique and improve your own draft answers before finalising

Workflow: search → draft → reflect → final answer.
Always ground answers in retrieved facts when possible.""")

def agent_node(state: MessagesState):
    response = llm_with_tools.invoke([SYSTEM] + state["messages"])
    return {"messages": [response]}

builder = StateGraph(MessagesState)
builder.add_node("agent",  agent_node)
builder.add_node("tools",  ToolNode(assistant_tools))
builder.add_edge(START, "agent")
builder.add_conditional_edges("agent", tools_condition)   # routes to "tools" or END
builder.add_edge("tools", "agent")                        # after tools, back to agent

graph = builder.compile(checkpointer=MemorySaver())

cfg = {"configurable": {"thread_id": "research_1"}}

def ask(question):
    display(Markdown(f"---\n**User:** {question}"))
    result = graph.invoke({"messages": [HumanMessage(content=question)]}, config=cfg)
    answer = result["messages"][-1].content
    display(Markdown(f"**Assistant:** {answer}"))
    return answer

ask("What is Rust and why is it special?")

# Follow-up — tests memory
ask("Which language we discussed is best for web frontend?")

# Math + knowledge combined
ask("If Python was released in 1991 and Go in 2009, how many years apart were they released?")

Summary & Next Steps

What you covered:

Concept	Key Takeaway
LLM Basics	Tokens, temperature, streaming, roles
Prompt Engineering	Templates, few-shot, CoT, structured output
Chains (LCEL)	Compose components with `\|`, parallel/sequential
Memory	Manual history; LangGraph `MemorySaver` + `thread_id`
RAG	Embed → store → retrieve → augment → generate
Tools	Define with `@tool`, bind to LLM, handle tool calls
Agents	ReAct loop, tool-calling agent, RAG agent
Multi-Agent	Orchestrator + specialists, parallel agents
Agentic Patterns	Planning, reflection, eval-optimizer, map-reduce, HITL
LangGraph	`StateGraph` + `MemorySaver` for stateful agentic workflows

Intermediate next steps:

LangGraph advanced — branching, human-in-the-loop interrupts, subgraphs, streaming state
Fine-tuning — adapt a base model to your domain
Evals — measure agent quality with LangSmith or RAGAS
Production patterns — caching, observability, rate limiting, cost tracking
Custom retrievers — BM25 hybrid search, reranking with cross-encoders
Multimodal — vision-enabled models (llava via Ollama, Gemini Vision, GPT-4o)

Useful references:

Key Takeaways

After working through the notebook you should be comfortable with:

Swapping LLM providers without rewriting your application logic
Writing prompts that reliably produce structured, typed output
Building RAG pipelines that ground model responses in your own data
Defining and binding tools so a model can interact with external systems
Reasoning about the ReAct loop and when an agent approach is—and isn't—the right choice
Sketching multi-agent architectures with routing and specialist sub-agents

The notebook is intentionally opinionated in its use of LangChain as the orchestration layer, since it offers a consistent API across providers and a rich ecosystem of integrations. That said, the concepts translate directly to other frameworks (LlamaIndex, Semantic Kernel, raw API calls) once you understand the underlying patterns.

Questions, corrections, or suggestions? Leave a comment below—feedback is how this kind of resource improves over time.

Q-Table Explained: 5 Steps to Master Reinforcement Learning

noreply@blogger.com (Varun) — Fri, 24 Jul 2026 19:00:19 +0000

Imagine you're teaching a dog new tricks. You don't hand it a manual — you reward it when it does something right and ignore (or correct) it when it doesn't. Over dozens of repetitions, the dog builds an internal sense of which actions pay off in which situations. That's the soul of reinforcement learning, and the Q-Table is how we give a computer program that same kind of memory.

In this post, we'll build a complete Q-learning agent from scratch — a warehouse robot that learns to navigate a 5×5 grid to deliver packages while avoiding forklift collision zones. By the end, you'll understand not just what a Q-Table is, but why every design choice exists.

The Problem Q-Learning Solves

Why Supervised Learning Fails Here

Supervised learning is fantastic when you have labeled examples: "given this email, the correct label is spam." But consider our warehouse robot. What's the "correct" move when the robot is at position (2, 3) and the target shelf is at (4, 4)? Move right? Move down? Both might eventually work. The right answer depends on the entire sequence of future moves — not just the current step.

There's no teacher handing out labeled training data. The robot must discover good strategies through trial and error. This is the core of sequential decision-making under uncertainty.

The Explore-Exploit Dilemma

Here's a tension every RL agent faces:

Exploit: Do what you already know works well. (Go the route you've taken before.)
Explore: Try something new. Maybe there's a better route you haven't discovered yet.

Think of it like a delivery driver who always takes the same highway route because it worked yesterday. One day the highway is jammed, but the driver never finds the faster back roads because they stopped exploring. If the robot only exploits, it gets stuck in the first decent strategy it finds. If it only explores, it never actually gets good at anything. The balance is called the epsilon-greedy policy, and we'll implement it in Step 3.

What "Reward" Means Computationally

A reward is simply a scalar number the environment hands back after each action: - +100 for reaching the target shelf - -50 for hitting a forklift collision zone - -1 for each time step (to encourage finding fast paths, not just safe ones)

The robot's job is to maximize total cumulative reward over time — not just the immediate reward of a single move.

The Reinforcement Learning Loop

Agent observes State s

→

Chooses Action a

→

Environment returns Reward r + Next State s'

→

Agent updates Q-Table

→

Repeat until convergence

The agent-environment loop is the heartbeat of Q-learning. Each cycle produces one experience tuple (s, a, r, s') used to sharpen the Q-Table. The agent never sees the full map — it only learns from these one-step snapshots.

Anatomy of a Q-Table

A Q-Table is a plain 2D matrix. Think of it like a laminated cue card the robot carries at all times — every room it might enter is a row, every direction it might walk is a column, and each cell holds its best guess at how rewarding that move will be:

Rows = every possible state the robot can be in (each of the 25 grid cells)
Columns = every possible action (UP, DOWN, LEFT, RIGHT)
Cell value = Q-value — an estimate of "how good is it to take this action from this state?"

         UP      DOWN    LEFT    RIGHT
State 0  [ 0.00   0.00    0.00    0.00  ]   ← (row 0, col 0): Start
State 1  [ 0.00   0.00    0.00    0.00  ]   ← (row 0, col 1)
...       ...
State 12 [ 0.00   0.00    0.00    0.00  ]   ← Center of grid
...       ...
State 24 [ 0.00   0.00    0.00    0.00  ]   ← Target shelf!

After training:
         UP      DOWN    LEFT    RIGHT
State 0  [ 0.12   0.45   -0.30    0.67  ]   Robot should go RIGHT
State 5  [-0.50   0.89    0.23    0.45  ]   Robot should go DOWN

A Q-Table before (all zeros) and after training. Each cell stores the expected future reward for taking that action from that state. The robot picks the action with the highest Q-value in its current row — no computation needed at decision time, just a lookup.

Initialization and Size

Every cell starts at 0.0 — the agent assumes nothing about the world. Over training episodes, values drift toward their true worth. Starting at zero is a deliberate choice: it makes the agent mildly optimistic about unexplored actions (since even a small positive reward will beat 0.0 initially), which naturally encourages exploration early in training.

Size? For our 5×5 warehouse: 25 states × 4 actions = 100 cells. Totally manageable. But consider a chess engine: ~10⁴⁷ possible board states. A Q-Table would require more memory than there are atoms in the observable universe. That's the state space explosion problem — we'll revisit it at the end.

The Bellman Equation Demystified

Intuition First

Imagine you're a hiking guide estimating how long it takes to reach a mountain summit from various waypoints on the trail. You don't walk every possible path from scratch each time — instead, you reason backwards: "From waypoint C, the summit is 30 minutes away. So from waypoint B (20 minutes from C), the total is 50 minutes." Once you know the value of a closer waypoint, you can immediately compute the value of every waypoint leading into it.

The Bellman equation does exactly this for Q-values — it propagates the value of reaching the goal backwards through the state space, one step at a time:

*"The value of being in state s and taking action a equals the immediate reward, plus the discounted value of the best action you can take from wherever you end up."

The Formula

Q(s, a) ← Q(s, a) + α [ r + γ · max Q(s', a') − Q(s, a) ]
                              └─────────────────────┘
                               Temporal Difference (TD) Error

Let's dissect every piece:

Symbol	Name	Role	Typical Range
`Q(s,a)`	Current Q-value	What we currently think this move is worth	Any real number
`α` (alpha)	Learning rate	How fast to update — like a student who absorbs 30% of each lesson	0.01 – 0.5
`r`	Immediate reward	What the environment actually gave us right now	Domain-specific
`γ` (gamma)	Discount factor	How much we care about future rewards vs. immediate ones	0.9 – 0.99
`max Q(s',a')`	Best future Q-value	Best known value of the next state	Any real number
`TD Error`	Surprise signal	How wrong our current estimate was — shrinks toward 0 at convergence	Shrinks to 0 at convergence

What Each Hyperparameter Controls

α (Learning Rate): - Too high (α=0.9): The agent overreacts to each experience, values oscillate wildly — like a student who completely rewrites their notes after every single lecture, forgetting everything they studied the week before. - Too low (α=0.001): Learning is painfully slow, may not converge in reasonable time. - Sweet spot: Start at 0.1, decay slowly over episodes.

γ (Discount Factor): - γ=0: Robot is completely short-sighted — only cares about immediate reward (terrible for navigation). - γ=1: Robot gives equal weight to rewards 1,000 steps in the future (can cause instability in long episodes). - γ=0.95: "I care about future rewards, but I prefer sooner ones" — realistic and stable.

ε (Epsilon — explore/exploit): - ε=1.0: Pure exploration (random actions) - ε=0.0: Pure exploitation (always take best known action) - Strategy: Start at 1.0, decay to 0.01 over training

Temporal Difference: How Surprise Drives Learning

Agent predicts Q(s,a) = 2.5

→

Takes action, gets r=10, lands in s'

→

TD Error = 10 + 0.95×3.0 − 2.5 = 10.35

→

New Q = 2.5 + 0.1×10.35 = 3.535

The TD Error is the "surprise" signal. A large positive error means this move was better than expected — raise its Q-value. A negative error means it was worse — lower it. Over thousands of steps, these small corrections accumulate into reliable estimates.

Step-by-Step: Building a Q-Table from Scratch

Our Scenario: The Warehouse Robot Navigator

A 5×5 grid warehouse. The robot starts at cell (0,0) — the loading dock. The target shelf is at (4,4). Three cells are blocked forklift zones: (1,1), (2,3), and (3,1).

  0   1   2   3   4
0 [S] [ ] [ ] [ ] [ ]
1 [ ] [X] [ ] [ ] [ ]
2 [ ] [ ] [ ] [X] [ ]
3 [ ] [X] [ ] [ ] [ ]
4 [ ] [ ] [ ] [ ] [T]

S = Start (loading dock)
T = Target shelf
X = Forklift collision zone

States are numbered 0–24 by row-major order: state = row×5 + col.

Step 1: Define the Environment

Before writing any learning code, we formalize the world. This is the most important step — a poorly designed reward structure will produce a robot that technically maximizes its score while doing something completely wrong (a phenomenon called reward hacking).

States: 25 (one per grid cell)
Actions: 4 (0=UP, 1=DOWN, 2=LEFT, 3=RIGHT)
Rewards:
Reach target (4,4): +100
Hit forklift zone: -50 (episode ends)
Each step: -1 (time penalty encourages short paths)
Hit wall (try to move off grid): -5 (discourage wall bumping)

Why the -1 step penalty? Without it, a robot that reaches the goal in 8 steps and one that reaches it in 80 steps receive the same total reward (+100). The step penalty forces the robot to prefer shorter routes — exactly what we want in a real warehouse.

Step 2: Initialize the Q-Table

All zeros. The robot knows nothing yet.

import java.util.Arrays;

public class Main {
    static final int NUM_STATES = 10;
    static final int NUM_ACTIONS = 4;

    public static void main(String[] args) {
        double[][] qTable = new double[NUM_STATES][NUM_ACTIONS];
        // Java initializes double arrays to 0.0 by default
        // But let's be explicit for clarity:
        for (int state = 0; state < NUM_STATES; state++) {
            Arrays.fill(qTable[state], 0.0);
        }
    }
}

Step 3: Epsilon-Greedy Policy

With probability ε, explore (random action). Otherwise, exploit (best Q-value). Note how rng.nextDouble() returns a value in [0.0, 1.0) — if ε is 0.3, there's a 30% chance we explore.

import java.util.Random;

public class Main {
    static final int NUM_ACTIONS = 4;

    static int chooseAction(double[][] qTable, int state, double epsilon, Random rng) {
        if (rng.nextDouble() < epsilon) {
            // Explore: pick a random action
            return rng.nextInt(NUM_ACTIONS);
        } else {
            // Exploit: pick the action with highest Q-value
            int bestAction = 0;
            double bestValue = qTable[state][0];
            for (int action = 1; action < NUM_ACTIONS; action++) {
                if (qTable[state][action] > bestValue) {
                    bestValue = qTable[state][action];
                    bestAction = action;
                }
            }
            return bestAction;
        }
    }

    public static void main(String[] args) {
        Random rng = new Random();
        int numStates = 5;
        double epsilon = 0.1;

        double[][] qTable = new double[numStates][NUM_ACTIONS];

        int state = 0;
        int action = chooseAction(qTable, state, epsilon, rng);
        System.out.println("Chosen action for state " + state + ": " + action);
    }
}

Step 4: Run Episodes and Apply the Update Rule

An episode is one complete run of the robot from start to either reaching the target or hitting a forklift zone. We run many episodes — each one contributes a small amount of learning. The Bellman update happens after every single step, not just at the end of each episode.

import java.util.Arrays;

public class Main {
    static final int MAX_EPISODES = 1000;
    static final int START_STATE = 0;
    static final double GAMMA = 0.99;
    static final double ALPHA = 0.1;
    static final double EPSILON_MIN = 0.01;
    static final double EPSILON_DECAY = 0.995;

    static class StepResult {
        int nextState;
        double reward;
        boolean done;

        StepResult(int nextState, double reward, boolean done) {
            this.nextState = nextState;
            this.reward = reward;
            this.done = done;
        }
    }

    static class Environment {
        StepResult step(int state, int action) {
            // Placeholder implementation
            return new StepResult(0, 0.0, true);
        }
    }

    static int chooseAction(double[][] qTable, int state, double epsilon, java.util.Random rng) {
        if (rng.nextDouble() < epsilon) {
            return rng.nextInt(qTable[state].length);
        }
        int bestAction = 0;
        for (int i = 1; i < qTable[state].length; i++) {
            if (qTable[state][i] > qTable[state][bestAction]) {
                bestAction = i;
            }
        }
        return bestAction;
    }

    public static void main(String[] args) {
        int numStates = 10;
        int numActions = 4;
        double[][] qTable = new double[numStates][numActions];
        double epsilon = 1.0;
        java.util.Random rng = new java.util.Random();
        Environment environment = new Environment();

        for (int episode = 0; episode < MAX_EPISODES; episode++) {
            int state = START_STATE;
            boolean episodeDone = false;

            while (!episodeDone) {
                int action = chooseAction(qTable, state, epsilon, rng);
                StepResult result = environment.step(state, action);

                // Bellman update
                double bestNextQ = Arrays.stream(qTable[result.nextState]).max().getAsDouble();
                double tdError = result.reward + GAMMA * bestNextQ - qTable[state][action];
                qTable[state][action] += ALPHA * tdError;

                state = result.nextState;
                episodeDone = result.done;
            }

            // Decay epsilon so the robot gradually stops exploring
            epsilon = Math.max(EPSILON_MIN, epsilon * EPSILON_DECAY);
        }
    }
}

Step 5: Extract the Learned Policy

After training, read the policy: for each state, the best action is the one with the highest Q-value. This is called taking the argmax of each row.

public class Main {
    static final int GRID_ROWS = 5;
    static final int GRID_COLS = 5;
    static final int TARGET_STATE = GRID_ROWS * GRID_COLS - 1;
    static final int NUM_ACTIONS = 4;

    static boolean isForkLiftZone(int row, int col) {
        // Define forklift zones - customize as needed
        return (row == 2 && col == 2);
    }

    void printPolicy(double[][] qTable) {
        String[] actionSymbols = {"↑", "↓", "←", "→"};
        for (int row = 0; row < GRID_ROWS; row++) {
            for (int col = 0; col < GRID_COLS; col++) {
                int state = row * GRID_COLS + col;
                if (isForkLiftZone(row, col)) { System.out.print(" X "); continue; }
                if (state == TARGET_STATE)    { System.out.print(" T "); continue; }
                int bestAction = 0;
                for (int a = 1; a < NUM_ACTIONS; a++) {
                    if (qTable[state][a] > qTable[state][bestAction]) bestAction = a;
                }
                System.out.print(" " + actionSymbols[bestAction] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        double[][] qTable = new double[GRID_ROWS * GRID_COLS][NUM_ACTIONS];
        main.printPolicy(qTable);
    }
}

Expected output after 500 episodes:

 → → → → ↓
 → X → → ↓
 → → → X ↓
 → X → → ↓
 → → → → T

The robot learned to hug the right side and travel down — exactly the optimal path!

Full Java Implementation

Here's the complete, self-contained warehouse robot Q-learning agent:

import java.util.Arrays;
import java.util.Random;

/**
 * Warehouse Robot Q-Learning Agent
 * A 5x5 grid where a robot learns to navigate from (0,0) to (4,4)
 * while avoiding forklift collision zones.
 */
public class WarehouseRobotQLearning {

    // --- Environment Configuration ---
    static final int GRID_ROWS = 5;
    static final int GRID_COLS = 5;
    static final int NUM_STATES = GRID_ROWS * GRID_COLS;   // 25
    static final int NUM_ACTIONS = 4; // 0=UP, 1=DOWN, 2=LEFT, 3=RIGHT

    static final int START_STATE  = 0;  // (0,0) loading dock
    static final int TARGET_STATE = 24; // (4,4) storage shelf

    // Forklift collision zones: (row,col) → state index
    static final int[] FORKLIFT_ZONES = {
        1 * GRID_COLS + 1,  // (1,1) = state 6
        2 * GRID_COLS + 3,  // (2,3) = state 13
        3 * GRID_COLS + 1   // (3,1) = state 16
    };

    // --- Q-Learning Hyperparameters ---
    static final double ALPHA         = 0.1;   // Learning rate
    static final double GAMMA         = 0.95;  // Discount factor
    static final double EPSILON_START = 1.0;   // Initial exploration rate
    static final double EPSILON_MIN   = 0.01;  // Minimum exploration rate
    static final double EPSILON_DECAY = 0.995; // Decay per episode
    static final int    MAX_EPISODES  = 1000;
    static final int    MAX_STEPS     = 200;   // Max steps per episode

    // --- Reward Values ---
    static final double REWARD_TARGET   =  100.0;
    static final double REWARD_FORKLIFT =  -50.0;
    static final double REWARD_STEP     =   -1.0;
    static final double REWARD_WALL     =   -5.0;

    // Action deltas: row-change and col-change for each action
    static final int[] ROW_DELTA = {-1,  1,  0,  0}; // UP, DOWN, LEFT, RIGHT
    static final int[] COL_DELTA = { 0,  0, -1,  1};
    static final String[] ACTION_NAME = {"UP", "DOWN", "LEFT", "RIGHT"};
    static final String[] ACTION_SYMBOL = {"↑", "↓", "←", "→"};

    // ----------------------------------------------------------------
    //  Environment Logic
    // ----------------------------------------------------------------

    static boolean isForkLiftZone(int state) {
        for (int zone : FORKLIFT_ZONES) if (zone == state) return true;
        return false;
    }

    static int stateToRow(int state) { return state / GRID_COLS; }
    static int stateToCol(int state) { return state % GRID_COLS; }
    static int toState(int row, int col) { return row * GRID_COLS + col; }

    /**
     * Executes one action from the current state.
     * Returns: [nextState, reward, done]
     */
    static Object[] step(int currentState, int action) {
        int row = stateToRow(currentState);
        int col = stateToCol(currentState);

        int newRow = row + ROW_DELTA[action];
        int newCol = col + COL_DELTA[action];

        // Check for wall collision
        if (newRow < 0 || newRow >= GRID_ROWS || newCol < 0 || newCol >= GRID_COLS) {
            // Stay in place, pay wall penalty
            return new Object[]{currentState, REWARD_WALL, false};
        }

        int nextState = toState(newRow, newCol);

        // Check for forklift zone
        if (isForkLiftZone(nextState)) {
            return new Object[]{nextState, REWARD_FORKLIFT, true}; // Episode ends
        }

        // Check for target reached
        if (nextState == TARGET_STATE) {
            return new Object[]{nextState, REWARD_TARGET, true}; // Episode ends
        }

        // Normal step
        return new Object[]{nextState, REWARD_STEP, false};
    }

    // ----------------------------------------------------------------
    //  Policy: Epsilon-Greedy Action Selection
    // ----------------------------------------------------------------

    static int chooseAction(double[][] qTable, int state, double epsilon, Random rng) {
        if (rng.nextDouble() < epsilon) {
            return rng.nextInt(NUM_ACTIONS); // Explore
        }
        // Exploit: find action with max Q-value
        int bestAction = 0;
        for (int a = 1; a < NUM_ACTIONS; a++) {
            if (qTable[state][a] > qTable[state][bestAction]) {
                bestAction = a;
            }
        }
        return bestAction;
    }

    // ----------------------------------------------------------------
    //  Q-Table Update (Bellman Equation)
    // ----------------------------------------------------------------

    static void updateQTable(double[][] qTable, int state, int action,
                              double reward, int nextState) {
        double bestNextQ = Arrays.stream(qTable[nextState]).max().getAsDouble();
        double tdError = reward + GAMMA * bestNextQ - qTable[state][action];
        qTable[state][action] += ALPHA * tdError;
    }

    // ----------------------------------------------------------------
    //  Training Loop
    // ----------------------------------------------------------------

    static double[][] train(Random rng) {
        double[][] qTable = new double[NUM_STATES][NUM_ACTIONS]; // All zeros
        double epsilon = EPSILON_START;

        System.out.println("=== Starting Training ===");
        System.out.printf("%-10s %-12s %-12s %-10s%n",
                          "Episode", "Total Reward", "Steps Taken", "Epsilon");
        System.out.println("-".repeat(50));

        for (int episode = 1; episode <= MAX_EPISODES; episode++) {
            int state = START_STATE;
            double totalReward = 0.0;
            int stepCount = 0;
            boolean done = false;

            while (!done && stepCount < MAX_STEPS) {
                int action = chooseAction(qTable, state, epsilon, rng);
                Object[] result = step(state, action);

                int nextState  = (int)    result[0];
                double reward  = (double) result[1];
                boolean isDone = (boolean)result[2];

                updateQTable(qTable, state, action, reward, nextState);

                state = nextState;
                totalReward += reward;
                stepCount++;
                done = isDone;
            }

            // Decay epsilon after each episode
            epsilon = Math.max(EPSILON_MIN, epsilon * EPSILON_DECAY);

            // Log progress at key episodes
            if (episode == 1 || episode == 50 || episode == 100 ||
                episode == 250 || episode == 500 || episode == MAX_EPISODES) {
                System.out.printf("%-10d %-12.1f %-12d %-10.4f%n",
                                  episode, totalReward, stepCount, epsilon);
            }
        }
        return qTable;
    }

    // ----------------------------------------------------------------
    //  Policy Extraction and Visualization
    // ----------------------------------------------------------------

    static void printPolicy(double[][] qTable) {
        System.out.println("\n=== Learned Policy ===");
        System.out.println("(S=Start, T=Target, X=Forklift Zone)\n");
        for (int row = 0; row < GRID_ROWS; row++) {
            for (int col = 0; col < GRID_COLS; col++) {
                int state = toState(row, col);
                if (state == START_STATE)  { System.out.print(" S "); continue; }
                if (state == TARGET_STATE)  { System.out.print(" T "); continue; }
                if (isForkLiftZone(state)) { System.out.print(" X "); continue; }

                int bestAction = 0;
                for (int a = 1; a < NUM_ACTIONS; a++) {
                    if (qTable[state][a] > qTable[state][bestAction]) bestAction = a;
                }
                System.out.print(" " + ACTION_SYMBOL[bestAction] + " ");
            }
            System.out.println();
        }
    }

    static void printQTableSnapshot(double[][] qTable, int episode) {
        System.out.println("\n--- Q-Table Snapshot (Episode " + episode + ") ---");
        System.out.printf("%-8s %-8s %-8s %-8s %-8s%n",
                          "State", "UP", "DOWN", "LEFT", "RIGHT");
        System.out.println("-".repeat(48));
        for (int s = 0; s < NUM_STATES; s++) {
            System.out.printf("%-8d %-8.3f %-8.3f %-8.3f %-8.3f%n",
                s, qTable[s][0], qTable[s][1], qTable[s][2], qTable[s][3]);
        }
    }

    // ----------------------------------------------------------------
    //  Main
    // ----------------------------------------------------------------

    public static void main(String[] args) {
        Random rng = new Random(42); // Fixed seed for reproducibility
        double[][] qTable = train(rng);

        printPolicy(qTable);
        printQTableSnapshot(qTable, MAX_EPISODES);

        // Demonstrate the learned path
        System.out.println("\n=== Robot's Learned Path from Start to Target ===");
        int state = START_STATE;
        int steps = 0;
        while (state != TARGET_STATE && steps < 30) {
            int row = stateToRow(state);
            int col = stateToCol(state);
            int bestAction = 0;
            for (int a = 1; a < NUM_ACTIONS; a++) {
                if (qTable[state][a] > qTable[state][bestAction]) bestAction = a;
            }
            System.out.printf("  State %2d (%d,%d) → Action: %-6s%n",
                              state, row, col, ACTION_NAME[bestAction]);
            Object[] result = step(state, bestAction);
            state = (int) result[0];
            steps++;
        }
        System.out.printf("  State %2d (%d,%d) → TARGET REACHED in %d steps!%n",
                          state, stateToRow(state), stateToCol(state), steps);
    }
}

Sample Output

=== Starting Training ===
Episode    Total Reward Steps Taken  Epsilon   
--------------------------------------------------
1          -54.0        4            0.9950
50         -47.0        48           0.7783
100        -18.0        19           0.6050
250        -10.0        11           0.2873
500        8.0          9            0.0823
1000       91.0         9            0.0100

=== Learned Policy ===
(S=Start, T=Target, X=Forklift Zone)

 S  →  →  ↓  ↓ 
 →  X  →  ↓  ↓ 
 →  →  →  X  ↓ 
 →  X  →  →  ↓ 
 →  →  →  →  T

Notice how Total Reward climbs from -54 to +91 across 1000 episodes, and Steps Taken drops from 48 to 9 — the robot isn't just reaching the goal more often, it's finding a near-optimal route.

Q-Table Convergence: How Values Change Over Episodes

State 0 (Start) — Best Action: RIGHT
─────────────────────────────────────────────
Episode   1:  UP=0.000  DOWN=0.000  LEFT=0.000  RIGHT=0.000
Episode  50:  UP=0.021  DOWN=0.134  LEFT=-0.120  RIGHT=0.289
Episode 500:  UP=0.412  DOWN=2.310  LEFT=-0.830  RIGHT=4.920
Episode 1000: UP=0.721  DOWN=4.110  LEFT=-1.204  RIGHT=18.43 ← RIGHT wins!

State 19 (one step left of target) — Best Action: RIGHT
─────────────────────────────────────────────
Episode   1:  All zeros
Episode  50:  RIGHT=0.045 (barely discovered)
Episode 500:  RIGHT=65.23 (strong signal — target is close!)
Episode 1000: RIGHT=94.87 (nearly +100 reward, discounted once)

Q-values near the target converge first — the reward signal radiates outward from the goal like ripples from a stone dropped in water. Early states (like Start) take many more episodes to accumulate accurate estimates because the +100 reward must be discounted across all the intervening steps before it reaches them.

Common Pitfalls and Debugging

1. Reward Shaping Mistakes

Problem: You give a large negative reward for every wall bump, but forget the agent is trapped against a wall — it keeps bumping and accumulates catastrophic negative rewards, never recovering.

Fix: Make wall bumps mildly negative (not catastrophic), and ensure the episode doesn't end on wall bumps. The robot should learn "walls are bad" naturally through the cumulative time penalty.

2. Learning Rate Woes

α too high (0.9) Values oscillate — the agent "forgets" good experiences because each new update overwrites them aggressively.

α too low (0.001) Thousands of episodes produce barely any change. The robot acts nearly randomly for too long.

α just right (0.05–0.2) Steady, smooth convergence. Values creep toward optimal over hundreds of episodes.

3. Discount Factor Edge Cases

γ = 0: The robot is completely greedy. It'll pick up a +5 reward right next to it and ignore the +100 target 8 steps away. Useless for navigation.
γ = 1: Every future reward is worth exactly as much as an immediate one. This can cause instability in environments with long episodes and no terminal state, as Q-values grow unboundedly.
γ = 0.95: Sweet spot. A reward 20 steps away is worth 0.95²⁰ ≈ 36% of its face value — far enough to plan ahead, but decayed enough to prefer shorter paths.

4. The Q-Table Never Converges

If your Q-values are still wildly different between episodes after 10,000 runs, check:

Epsilon isn't decaying: If ε stays high, the agent keeps exploring randomly and never exploits its learned knowledge.
Environment is non-deterministic without proper handling: If transitions are stochastic but you're using a low α, the noise drowns the signal.
Max steps too low: The agent can't reach the target before the episode terminates, so it never receives the positive terminal reward.

public class Main {
    static final int NUM_STATES = 10;
    static final int NUM_ACTIONS = 4;
    static double[][] qTable = new double[NUM_STATES][NUM_ACTIONS];
    static double[][] previousQTable = new double[NUM_STATES][NUM_ACTIONS];

    public static void main(String[] args) {
        int episode = 1;
        // Debugging tip: track TD error magnitude over episodes
        // If it plateaus above 1.0 after 1000 episodes, something is wrong
        double avgTDError = 0.0;
        for (int s = 0; s < NUM_STATES; s++) {
            for (int a = 0; a < NUM_ACTIONS; a++) {
                // Compare current estimates to previous episode's estimates
                avgTDError += Math.abs(qTable[s][a] - previousQTable[s][a]);
            }
        }
        System.out.printf("Episode %d | Avg Q-Change: %.4f%n", episode, avgTDError / (NUM_STATES * NUM_ACTIONS));
    }
}

Limitations and the Bridge to Deep Q-Networks

The State Space Explosion

Q-tables work beautifully when states are countable and small. Our warehouse had 25 states. But consider:

Problem	States	Q-Table Size
5×5 Warehouse	25	100 cells
20×20 Maze	400	1,600 cells
Atari Pong (raw pixels)	~10⁶	~4M cells
Autonomous Driving	~10¹⁸	Impossible
Chess	~10⁴⁷	More than atoms in universe

For real-world problems, you can't store every state explicitly. The Q-table hits a wall — and unlike our robot, it can't recover from it.

The DQN Solution

Instead of a giant lookup table, a Deep Q-Network (DQN) uses a neural network as a function approximator. The key insight: similar states should have similar Q-values. A neural network can learn that pattern and generalize — estimating Q-values for states it has never seen before, based on states it has.

Q-Table vs. Deep Q-Network

Input: State s (grid position)

→

Q-Table: lookup row s

→

Output: Q-values for all 4 actions

vs.

Input: State s (raw pixels, sensor data…)

→

Neural Network (Conv layers, Dense layers)

→

Output: Q-values for all actions

DQN replaces the table with a neural network. The network generalizes — states it has never seen get reasonable Q-value estimates based on similar states it has seen. The Bellman update becomes a supervised training signal for the network weights instead of a direct table write.

When Q-Tables Are Still the Right Tool

Don't reach for a neural network when you don't need one:

Small state spaces Under ~10,000 states — pure Q-table wins on simplicity and interpretability
Tabular data problems Game solvers for small board games (Tic-Tac-Toe has 5,478 states)
Teaching/prototyping Always start with a Q-table to validate your reward structure before scaling up
Medium spaces Consider tile coding or state aggregation to compress the table
High-dimensional inputs Raw images, continuous sensor arrays — go straight to DQN

Recap: The 5 Steps

5 Steps to Master Q-Learning

1. Define Environment

→

2. Initialize Q-Table

→

3. ε-Greedy Policy

→

4. Episode Loop + Bellman Update

→

5. Extract Policy

Each step builds on the last. The magic happens in Step 4 — thousands of small Bellman corrections accumulate into a table of hard-won wisdom.

Define your environment — states, actions, and reward signals carefully
Initialize the Q-Table to zeros and track your hyperparameters (α, γ, ε)
Implement epsilon-greedy — start with full exploration and decay toward exploitation
Run episodes — each step applies the Bellman update, propagating reward signals backwards
Extract the policy — read the argmax of each row; that's the learned strategy

The Q-Table is one of AI's most elegant ideas: a simple matrix that emerges from experience to encode optimal behavior. It's the foundation everything from game-playing AIs to robotics schedulers is built on — and now you can build it yourself.

Want to go further? In the next post, we'll extend this exact warehouse robot to use a neural network for the Q-function — turning our Q-Table agent into a full Deep Q-Network (DQN) that can handle environments 1,000x larger.

Four Ways to Split Sentences (Without Machine Learning)

noreply@blogger.com (Varun) — Fri, 24 Jul 2026 15:15:19 +0000

Imagine you hand someone a giant wall of text — no paragraph breaks, no structure — and ask them to read it aloud naturally. They'd instinctively pause at every period, question mark, or exclamation point[cite: 1]. That pause, that boundary between thoughts, is what sentence splitting (also called sentence boundary detection or sentence segmentation) is all about[cite: 1].

Sentence Splitting in the NLP Pipeline

1. Sentence Splitting

→

2. Tokenization

→

3. POS Tagging

→

4. Parsing / Translation

Sentence segmentation acts as the foundational preprocessing stage for downstream NLP tasks.

In NLP pipelines, sentence splitting is often the very first step before anything else — tokenization, parsing, translation, summarization[cite: 1]. If you get it wrong, everything downstream suffers[cite: 1].

The good news? You don't always need a neural network to do it well[cite: 1]. In this post, we'll explore four classical, rule-based approaches to sentence splitting — from the simplest one-liner to surprisingly robust heuristic systems — all without a single line of machine learning[cite: 1].

Why Is Sentence Splitting Hard?

Before diving in, let's appreciate why this isn't trivial[cite: 1]. Consider these tricky cases[cite: 1]:

"Dr. Smith went to Washington D.C. last Monday." 3 Periods • 1 Sentence — Multiple periods within honorifics and city names[cite: 1].
"She asked, \"Are you coming?\" He nodded." 2 Sentences — Nested punctuation inside direct quotation marks[cite: 1].
"The price is $1.99. Buy now!" 1 Decimal • 2 Sentences — Decimal point within currency[cite: 1].
"I work at A.I. Corp. We build robots." 2 Sentences — Abbreviation ending directly at sentence boundary[cite: 1].
"...and that's it." Ellipsis — Multi-period sequences[cite: 1].

A naïve "split on period" approach would butcher all of these[cite: 1]. Each method we explore will get progressively better at handling such edge cases[cite: 1].

Method 1: Naïve Punctuation Split

The Idea

The simplest possible approach: split the text every time you see ., ?, or ![cite: 1].

Think of it like cutting a ribbon every time you see a knot[cite: 1]. Fast, simple — but sometimes you cut in the wrong place[cite: 1].

Naïve splitting truncates honorifics like "Dr." as isolated sentences[cite: 1].

Java Implementation

import java.util.Arrays;
import java.util.List;

public class NaiveSentenceSplitter {

    public static List<String> split(String text) {
        // Split on . ? or ! followed by one or more spaces
        String[] parts = text.split("(?<=[.?!])\\s+");
        return Arrays.asList(parts);
    }

    public static void main(String[] args) {
        String text = "Hello world. How are you? I am fine! Thanks.";
        List<String> sentences = split(text);
        for (String s : sentences) {
            System.out.println("|" + s + "|");
        }
    }
}

Output:

|Hello world.|
|How are you?|
|I am fine!|
|Thanks.|

Looks perfect for clean text[cite: 1]. But watch what happens with abbreviations[cite: 1]:

String tricky = "Dr. Smith lives on Oak St. He owns a cat.";
// Output:
// |Dr.|
// |Smith lives on Oak St.|
// |He owns a cat.|

Oops[cite: 1]. Dr. got split off as its own sentence[cite: 1].

When to Use It

Clean, well-formatted text (e.g., generated text, templates)[cite: 1]
Quick prototyping when accuracy isn't critical[cite: 1]
Pre-processing step before a smarter method[cite: 1]

Method 2: Abbreviation-Aware Splitting

The Idea

The naïve method fails because it doesn't know that certain words followed by a period are abbreviations, not sentence endings[cite: 1]. The fix: maintain a blocklist of known abbreviations and skip splitting when the period belongs to one[cite: 1].

This is like a train conductor who knows certain stops are "request stops" — the train doesn't halt there unless specifically needed[cite: 1].

Abbreviation lookup workflow preventing invalid sentence splits[cite: 1].

C++ Implementation

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <unordered_set>
#include <algorithm>
#include <cctype>

// Lowercase a string
std::string toLower(const std::string& s) {
    std::string result = s;
    std::transform(result.begin(), result.end(), result.begin(), ::tolower);
    return result;
}

// Known abbreviations (lowercase, without the period)
std::unordered_set<std::string> ABBREVIATIONS = {
    "dr", "mr", "mrs", "ms", "prof", "sr", "jr",
    "st", "ave", "blvd", "dept", "approx", "vs",
    "etc", "e.g", "i.e", "fig", "jan", "feb",
    "mar", "apr", "jun", "jul", "aug", "sep",
    "oct", "nov", "dec", "no", "vol", "pp"
};

std::vector<std::string> splitSentences(const std::string& text) {
    std::vector<std::string> sentences;
    std::string current;
    int n = text.size();

    for (int i = 0; i < n; i++) {
        current += text[i];

        // Check if we're at a sentence-ending punctuation
        if (text[i] == '.' || text[i] == '?' || text[i] == '!') {

            // Look ahead: is the next character a space followed by uppercase?
            if (i + 2 < n && text[i + 1] == ' ' &&
                std::isupper((unsigned char)text[i + 2])) {

                // Extract the word just before the period
                std::string word;
                int j = current.size() - 2; // -2 to skip the period we just added
                while (j >= 0 && current[j] != ' ') {
                    word = current[j] + word;
                    j--;
                }

                // Check if it's a known abbreviation
                if (ABBREVIATIONS.count(toLower(word)) == 0) {
                    // Not an abbreviation — it's a sentence boundary!
                    sentences.push_back(current);
                    current = "";
                    i++; // Skip the space
                }
            }
        }
    }

    // Don't forget the last sentence
    if (!current.empty()) {
        sentences.push_back(current);
    }

    return sentences;
}

int main() {
    std::string text = "Dr. Smith lives on Oak St. He owns a cat. "
                       "Prof. Lee moved to Washington D.C. last year.";

    auto sentences = splitSentences(text);
    for (const auto& s : sentences) {
        std::cout << "[" << s << "]" << std::endl;
    }
    return 0;
}

Output:

[Dr. Smith lives on Oak St. He owns a cat.]
[Prof. Lee moved to Washington D.C. last year.]

Much better! The abbreviation list acts as a safety net for the most common offenders[cite: 1].

Limitations

Your abbreviation list will never be complete[cite: 1].
Single capital letters (A., B.) can still trip it up[cite: 1].
Doesn't handle quotes, parentheses, or numbering well[cite: 1].

When to Use It

Domain-specific text where you know common abbreviations (medical, legal, scientific)[cite: 1]
When you can afford to curate and maintain an abbreviation list[cite: 1]

Method 3: Regex-Based Heuristic Splitter

The Idea

Instead of a simple split, we use regular expressions to encode multiple heuristic rules simultaneously[cite: 1]:

A sentence ends with ., ?, or ![cite: 1]
Followed by whitespace[cite: 1]
Followed by an uppercase letter or a quote/parenthesis opening a new sentence[cite: 1]
BUT NOT when the word before the period is a known abbreviation or a single letter (initials)[cite: 1]

Think of it like a traffic light system: instead of just checking one condition ("is it a period?"), we check multiple signals before deciding to stop[cite: 1].

Java Implementation

import java.util.*;
import java.util.regex.*;

public class RegexSentenceSplitter {

    // These patterns will NOT trigger a split
    private static final Set<String> ABBREVIATIONS = new HashSet<>(Arrays.asList(
        "dr", "mr", "mrs", "ms", "prof", "sr", "jr", "st", "ave",
        "blvd", "dept", "approx", "vs", "etc", "fig", "no", "vol"
    ));

    /**
     * Returns true if the word before the period looks like an abbreviation
     * or a single initial (e.g., "A.", "B.")
     */
    private static boolean isAbbreviation(String word) {
        String lower = word.toLowerCase();
        if (ABBREVIATIONS.contains(lower)) return true;
        if (word.length() == 1 && Character.isLetter(word.charAt(0))) return true; // Initials
        if (word.matches("[A-Z]([a-z]*[A-Z])+")) return true; // Acronym like "U.S.A"
        return false;
    }

    public static List<String> split(String text) {
        List<String> sentences = new ArrayList<>();

        // Regex: sentence boundary = punctuation + space(s) + uppercase or quote/paren
        // We use a lookahead so we don't consume the start of the next sentence
        Pattern boundary = Pattern.compile(
            "(?<=[.?!]['\"]?)" +   // after . ? ! optionally followed by closing quote
            "\\s+" +                // whitespace
            "(?=[A-Z\"\\(])"        // before uppercase letter, quote, or open paren
        );

        // Split on candidate boundaries
        String[] candidates = boundary.split(text);

        StringBuilder current = new StringBuilder();
        for (int i = 0; i < candidates.length; i++) {
            String part = candidates[i];

            // Get the last word of this part (before the terminal punctuation)
            String trimmed = part.trim();
            String lastWord = "";
            int lastSpace = trimmed.lastIndexOf(' ', trimmed.length() - 2);
            if (lastSpace >= 0) {
                // Remove the punctuation to get the actual word
                lastWord = trimmed.substring(lastSpace + 1);
                if (lastWord.endsWith(".") || lastWord.endsWith("?") || lastWord.endsWith("!")) {
                    lastWord = lastWord.substring(0, lastWord.length() - 1);
                }
            }

            current.append(part);

            if (isAbbreviation(lastWord)) {
                // Don't split — it's an abbreviation; keep building
                current.append(" ");
            } else {
                // Real sentence boundary
                sentences.add(current.toString().trim());
                current = new StringBuilder();
            }
        }

        if (current.length() > 0) {
            sentences.add(current.toString().trim());
        }

        return sentences;
    }

    public static void main(String[] args) {
        String text = "Dr. Smith visited Washington D.C. last Monday. "
                    + "\"Was it fun?\" asked Ms. Jones. He said yes! "
                    + "The price was $1.99. She paid immediately.";

        List<String> sentences = split(text);
        for (int i = 0; i < sentences.size(); i++) {
            System.out.printf("[%d] %s%n", i + 1, sentences.get(i));
        }
    }
}

Output:

[1] Dr. Smith visited Washington D.C. last Monday.
[2] "Was it fun?" asked Ms. Jones.
[3] He said yes!
[4] The price was $1.99.
[5] She paid immediately.

Breaking Down the Regex

(?<=[.?!]['"]?)   — lookbehind: we just passed a . ? or ! (optionally + closing quote)
\s+               — whitespace: one or more space characters
(?=[A-Z"\(])      — lookahead: next char is uppercase, a quote, or open parenthesis

Using lookahead and lookbehind (zero-width assertions) means we split at the whitespace without consuming the surrounding characters — perfect for keeping sentence punctuation attached to the right sentence[cite: 1].

When to Use It

General-purpose text without extreme edge cases[cite: 1]
When you want a balance of simplicity and accuracy[cite: 1]
As a fast pre-processing step in an NLP pipeline[cite: 1]

Method 4: Finite State Machine (FSM) Splitter

The Idea

This is the most robust rule-based approach[cite: 1]. We model the sentence-splitting process as a Finite State Machine — a system that moves through a set of states as it reads characters one by one[cite: 1].

Think of it like reading a book with a bookmark and a set of sticky notes[cite: 1]. Each sticky note represents a "state" you're currently in (e.g., inside a quote, just saw a period, inside a number)[cite: 1]. As you read each character, you check your current state and decide whether to move to a new state[cite: 1].

Interactive State Machine Transition Diagram

This visual models how character input triggers state shifts in real time:

States in Our FSM

NORMAL          — reading regular sentence content
AFTER_PERIOD    — just saw a period (potential sentence end)
IN_QUOTE        — inside a double-quoted string
IN_NUMBER       — inside a decimal number (e.g., 3.14)
BOUNDARY        — confirmed sentence boundary (emit the sentence)

C Implementation

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_SENTENCE_LEN 4096
#define MAX_SENTENCES    1024

typedef enum {
    STATE_NORMAL,
    STATE_AFTER_TERMINAL,  // After . ? !
    STATE_IN_QUOTE,
    STATE_IN_PARENS
} State;

// Check if a word is a likely abbreviation
int isAbbreviation(const char* word) {
    // Single capital letter (initial)
    if (strlen(word) == 1 && isupper((unsigned char)word[0])) return 1;

    // Common abbreviations
    const char* abbrevs[] = {
        "dr", "mr", "mrs", "ms", "prof", "sr", "jr",
        "st", "ave", "blvd", "no", "vol", "vs",
        "jan", "feb", "mar", "apr", "jun", "jul",
        "aug", "sep", "oct", "nov", "dec", NULL
    };

    char lower[64];
    int i;
    for (i = 0; word[i] && i < 63; i++)
        lower[i] = tolower((unsigned char)word[i]);
    lower[i] = '\0';

    for (int j = 0; abbrevs[j] != NULL; j++) {
        if (strcmp(lower, abbrevs[j]) == 0) return 1;
    }
    return 0;
}

// Extract the last complete word from a buffer (strip trailing punctuation)
void getLastWord(const char* buffer, int len, char* word) {
    word[0] = '\0';
    // Go backwards past punctuation and spaces
    int end = len - 1;
    while (end >= 0 && (ispunct((unsigned char)buffer[end]) || isspace((unsigned char)buffer[end])))
        end--;

    // Now go backwards to find the start of the word
    int start = end;
    while (start > 0 && !isspace((unsigned char)buffer[start - 1]))
        start--;

    if (start <= end) {
        strncpy(word, buffer + start, end - start + 1);
        word[end - start + 1] = '\0';
    }
}

int splitSentences(const char* text, char sentences[][MAX_SENTENCE_LEN]) {
    State state = STATE_NORMAL;
    char buffer[MAX_SENTENCE_LEN];
    int bufLen = 0;
    int sentCount = 0;
    int n = strlen(text);
    char lastWord[64];

    for (int i = 0; i < n; i++) {
        char c = text[i];
        char next = (i + 1 < n) ? text[i + 1] : '\0';
        char nextNext = (i + 2 < n) ? text[i + 2] : '\0';

        buffer[bufLen++] = c;
        buffer[bufLen] = '\0';

        switch (state) {
            case STATE_NORMAL:
                if (c == '"') {
                    state = STATE_IN_QUOTE;
                } else if (c == '(') {
                    state = STATE_IN_PARENS;
                } else if ((c == '.' || c == '?' || c == '!')) {
                    state = STATE_AFTER_TERMINAL;
                }
                break;

            case STATE_AFTER_TERMINAL:
                if (isspace((unsigned char)c) && isupper((unsigned char)next)) {
                    // Potential boundary — check for abbreviation
                    getLastWord(buffer, bufLen - 1, lastWord); // -1 to ignore space
                    if (!isAbbreviation(lastWord)) {
                        // Emit the sentence (up to and including the punctuation)
                        // Trim trailing space
                        int end = bufLen - 1;
                        while (end > 0 && isspace((unsigned char)buffer[end - 1])) end--;
                        buffer[end] = '\0';
                        strncpy(sentences[sentCount++], buffer, MAX_SENTENCE_LEN - 1);
                        bufLen = 0;
                        buffer[0] = '\0';
                        state = STATE_NORMAL;
                    } else {
                        state = STATE_NORMAL;
                    }
                } else if (c == '"') {
                    state = STATE_IN_QUOTE;
                } else if (!isspace((unsigned char)c)) {
                    // Something other than space — back to normal (e.g., "1.5x")
                    state = STATE_NORMAL;
                }
                break;

            case STATE_IN_QUOTE:
                if (c == '"') {
                    state = STATE_NORMAL;
                }
                break;

            case STATE_IN_PARENS:
                if (c == ')') {
                    state = STATE_NORMAL;
                }
                break;
        }
    }

    // Flush remaining text as the last sentence
    if (bufLen > 0) {
        strncpy(sentences[sentCount++], buffer, MAX_SENTENCE_LEN - 1);
    }

    return sentCount;
}

int main() {
    const char* text =
        "Dr. Smith visited D.C. on Monday. "
        "The ratio was 1.5 to 1. It was significant! "
        "He said \"This is fine. Really.\" before leaving. "
        "Ms. Jones (his colleague) agreed. She smiled.";

    char sentences[MAX_SENTENCES][MAX_SENTENCE_LEN];
    int count = splitSentences(text, sentences);

    printf("Found %d sentences:\n\n", count);
    for (int i = 0; i < count; i++) {
        printf("[%d] %s\n", i + 1, sentences[i]);
    }
    return 0;
}

Output:

Found 5 sentences:

[1] Dr. Smith visited D.C. on Monday.
[2] The ratio was 1.5 to 1. It was significant!
[3] He said "This is fine. Really." before leaving.
[4] Ms. Jones (his colleague) agreed.
[5] She smiled.

How the FSM Works — Step by Step

Let's trace through "1.5 to 1. It was" character by character[cite: 1]:

'1'  → STATE_NORMAL,         buffer: "1"
'.'  → STATE_AFTER_TERMINAL, buffer: "1."
'5'  → not space+uppercase → STATE_NORMAL, buffer: "1.5"   ← decimal, no split!
' '  → STATE_NORMAL,         buffer: "1.5 "
't'  → STATE_NORMAL,         buffer: "1.5 t"
...
'1'  → STATE_NORMAL,         buffer: "1.5 to 1"
'.'  → STATE_AFTER_TERMINAL, buffer: "1.5 to 1."
' '  → space! next='I' (uppercase)...
       lastWord = "1" → not an abbreviation!
       EMIT SENTENCE: "1.5 to 1."
       reset buffer, STATE_NORMAL
'I'  → STATE_NORMAL,         buffer: "I"
...

When to Use It

When you need the most accurate rule-based approach[cite: 1]
Complex documents: legal contracts, academic papers, news articles[cite: 1]
When you want fine-grained control over every splitting decision[cite: 1]
As the foundation for a custom domain-specific splitter[cite: 1]

Comparison Table

Method	Speed	Accuracy	Handles Abbrevs	Handles Quotes	Complexity
Naïve Punctuation Split	⚡ Very Fast	❌ Low	❌ No	❌ No	🟢 Trivial
Abbreviation-Aware	⚡ Fast	🟡 Medium	✅ Yes	❌ No	🟡 Easy
Regex Heuristic	⚡ Fast	🟡 Good	✅ Yes	✅ Partial	🟡 Moderate
FSM-Based	🟢 Fast	✅ Best (rule-based)	✅ Yes	✅ Yes	🔴 More Complex

Choosing the Right Method

Here's a decision matrix to help choose the best approach for your project[cite: 1]:

Tips for Improving Any Rule-Based Splitter

Handle ellipses (...) — they rarely end sentences mid-paragraph[cite: 1].
Track parenthesis depth — text inside (like this. Really.) should not be split[cite: 1].
Handle numbered lists — "1. First item 2. Second item" should not split at 1.[cite: 1].
Normalize whitespace first — collapse multiple spaces, replace \t and \n[cite: 1].
Post-process short fragments — if a "sentence" is only 1-2 characters, it's probably a false split[cite: 1].

Final Thoughts

Sentence splitting is one of those problems that looks trivially easy until you try it on real-world text[cite: 1]. The journey from a one-liner split(".") to a full FSM with state tracking mirrors a broader truth in NLP: language is full of exceptions, and robust systems are built by systematically handling them one by one[cite: 1].

Key Takeaway: Rule-based methods are transparent, fast, and debuggable[cite: 1]. When an FSM makes a wrong call, you can trace the exact logic path and fix it instantly — without retraining a neural model[cite: 1].

That said, for truly noisy or ambiguous text (social media posts, OCR output, multilingual documents), machine learning models will outperform rules[cite: 1]. But for structured documents in a known domain, a well-crafted FSM splitter can be hard to beat[cite: 1].

Happy splitting! 🔪📄

Beam Search: The Algorithm Behind LLM Text Generation

noreply@blogger.com (Varun) — Thu, 23 Jul 2026 19:00:47 +0000

When a Large Language Model (LLM) like GPT generates text, it doesn't simply pick the single most probable next word at every step. Doing so — known as greedy decoding — often leads to repetitive, suboptimal, or even incoherent outputs. Instead, most production-grade language models use a smarter strategy called Beam Search.

In this post, we'll break down:

What Beam Search is and why it exists
How it compares to Greedy and Exhaustive search
The step-by-step algorithm with a visual walkthrough
A full implementation in Java and C++
Its strengths, weaknesses, and modern variants

The Problem: Decoding from a Language Model

A language model assigns a probability to every possible next token given the preceding context:

P(token | previous tokens)

Generating a complete sequence means making a chain of these decisions. The goal is to find the sequence with the highest joint probability:

P(w1, w2, ..., wN) = P(w1) × P(w2|w1) × P(w3|w1,w2) × ...

Search Space Explosion: If your vocabulary has V words and you generate sequences of length N, there are V^N possible sequences. For V = 50,000 and N = 20, that's astronomically large. This is why we need smart search heuristics.

Approach 1: Greedy Search

Greedy search picks the single most probable token at every step.

At each step t: choose token = argmax P(token | context)

Why Greedy Fails

Consider generating a sentence where:

Step 1: "The" → 0.4 (highest)
Step 2 given "The": "cat" → 0.3 (highest)
Step 3 given "The cat": "sat" → 0.2 (highest)

But an alternative path exists:

Step 1: "A" → 0.35
Step 2 given "A": "beautiful" → 0.6
Step 3 given "A beautiful": "sunset" → 0.9

Joint probability of greedy path: 0.4 × 0.3 × 0.2 = 0.024
Joint probability of better path: 0.35 × 0.6 × 0.9 = 0.189

Greedy search misses the better path because it committed too early.

Approach 2: Exhaustive Search

Exhaustive search explores all possible sequences and picks the best one. It is optimal but computationally infeasible for any realistic vocabulary and sequence length.

Approach 3: Beam Search — The Sweet Spot

Beam Search is a heuristic best-first search that keeps track of the top-K most promising partial sequences (called the "beam") at each step, where K is the beam width.

Key Idea

At each step, expand every sequence in the beam by all possible next tokens.
Score each expanded sequence.
Keep only the top-K scoring sequences for the next step.
Repeat until all sequences hit an end token or max length.

This gives us a controllable trade-off:

K = 1 → Equivalent to Greedy Search
K = ∞ → Equivalent to Exhaustive Search
K = 5 to 20 → Practical sweet spot used in real systems

Step-by-Step Visual Walkthrough

Let's trace Beam Search with beam width K=2 and a tiny vocabulary: {A, B, C, <END>}.

Step 0 — Initialization

Beam: [ ([], score=0.0) ]

We start with one empty sequence.

Step 1 — Expand

Expand the empty sequence with all tokens:

Candidates:
  [A]     → log P(A)     = -0.9
  [B]     → log P(B)     = -0.5   ✓ keep
  [C]     → log P(C)     = -1.2
  [<END>] → log P(<END>) = -2.0

After keeping top-2:

Beam: [ ([B], -0.5), ([A], -0.9) ]

Step 2 — Expand Each Beam Member

Expand [B]:

  [B, A]     → -0.5 + -1.1 = -1.6
  [B, B]     → -0.5 + -0.4 = -0.9   ✓
  [B, C]     → -0.5 + -0.7 = -1.2   ✓
  [B, <END>] → -0.5 + -1.5 = -2.0

Expand [A]:

  [A, A]     → -0.9 + -0.8 = -1.7
  [A, B]     → -0.9 + -0.6 = -1.5
  [A, C]     → -0.9 + -0.3 = -1.2   (tied)
  [A, <END>] → -0.9 + -2.1 = -3.0

All 8 candidates are ranked, top-2 kept:

Beam: [ ([B, B], -0.9), ([B, C], -1.2) ]

This process continues until <END> tokens are generated or maximum length is reached. The sequence with the highest cumulative log-probability is the final output.

Why Log Probabilities?

Multiplying many small probabilities leads to numerical underflow. By working in log space, we convert multiplications into additions:

log(P1 × P2 × P3) = log(P1) + log(P2) + log(P3)

Higher (less negative) log-probability = better sequence.

Java Implementation

Here's a clean, self-contained Beam Search implementation in Java.

import java.util.*;

public class BeamSearch {

    static double[][] logProbTable = {
        /* step 0 */ {-0.9, -0.5, -1.2, -2.0},
        /* step 1 */ {-1.1, -0.4, -0.7, -1.5},
        /* step 2 */ {-0.8, -0.6, -0.3, -1.0},
        /* step 3 */ {-1.3, -0.9, -0.5, -0.4},
    };

    static String[] vocab = {"A", "B", "C", "<END>"};
    static int END_TOKEN = 3;

    static class Hypothesis implements Comparable<Hypothesis> {
        List<Integer> tokens;
        double score; 
        boolean finished;

        Hypothesis(List<Integer> tokens, double score, boolean finished) {
            this.tokens = new ArrayList<>(tokens);
            this.score = score;
            this.finished = finished;
        }

        @Override
        public int compareTo(Hypothesis other) {
            return Double.compare(other.score, this.score);
        }

        public String toStringSequence() {
            StringBuilder sb = new StringBuilder();
            for (int t : tokens) {
                sb.append(vocab[t]).append(" ");
            }
            return sb.toString().trim();
        }
    }

    static double[] getLogProbs(List<Integer> context) {
        int step = Math.min(context.size(), logProbTable.length - 1);
        return logProbTable[step];
    }

    static List<Hypothesis> beamSearch(int beamWidth, int maxLength) {
        List<Hypothesis> beam = new ArrayList<>();
        beam.add(new Hypothesis(new ArrayList<>(), 0.0, false));

        List<Hypothesis> completedSequences = new ArrayList<>();

        for (int step = 0; step < maxLength; step++) {
            List<Hypothesis> candidates = new ArrayList<>();

            for (Hypothesis hyp : beam) {
                if (hyp.finished) {
                    candidates.add(hyp);
                    continue;
                }

                double[] logProbs = getLogProbs(hyp.tokens);

                for (int tokenId = 0; tokenId < vocab.length; tokenId++) {
                    List<Integer> newTokens = new ArrayList<>(hyp.tokens);
                    newTokens.add(tokenId);
                    double newScore = hyp.score + logProbs[tokenId];
                    boolean isFinished = (tokenId == END_TOKEN);

                    candidates.add(new Hypothesis(newTokens, newScore, isFinished));
                }
            }

            Collections.sort(candidates);

            beam = new ArrayList<>();
            for (int i = 0; i < Math.min(beamWidth, candidates.size()); i++) {
                Hypothesis h = candidates.get(i);
                if (h.finished) {
                    completedSequences.add(h);
                } else {
                    beam.add(h);
                }
            }

            if (beam.isEmpty()) break;
        }

        completedSequences.addAll(beam);
        Collections.sort(completedSequences);
        return completedSequences;
    }

    public static void main(String[] args) {
        List<Hypothesis> results = beamSearch(2, 4);
        for (int i = 0; i < Math.min(3, results.size()); i++) {
            Hypothesis h = results.get(i);
            System.out.printf("Rank %d: %-25s score=%.4f%n", i + 1, h.toStringSequence(), h.score);
        }
    }
}

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

const vector<string> vocab = {"A", "B", "C", "<END>"};
const int END_TOKEN = 3;
const int VOCAB_SIZE = 4;

const double logProbTable[4][4] = {
    {-0.9, -0.5, -1.2, -2.0},
    {-1.1, -0.4, -0.7, -1.5},
    {-0.8, -0.6, -0.3, -1.0},
    {-1.3, -0.9, -0.5, -0.4},
};

struct Hypothesis {
    vector<int> tokens;
    double score;
    bool finished;

    Hypothesis(vector<int> t, double s, bool f) : tokens(t), score(s), finished(f) {}

    bool operator<(const Hypothesis& other) const {
        return score < other.score;
    }
};

const double* getLogProbs(const vector<int>& context) {
    int step = min((int)context.size(), 3);
    return logProbTable[step];
}

vector<Hypothesis> beamSearch(int beamWidth, int maxLength) {
    vector<Hypothesis> beam;
    beam.emplace_back(vector<int>{}, 0.0, false);
    vector<Hypothesis> completed;

    for (int step = 0; step < maxLength; step++) {
        vector<Hypothesis> candidates;

        for (const Hypothesis& hyp : beam) {
            if (hyp.finished) {
                candidates.push_back(hyp);
                continue;
            }

            const double* logProbs = getLogProbs(hyp.tokens);

            for (int tokenId = 0; tokenId < VOCAB_SIZE; tokenId++) {
                vector<int> newTokens = hyp.tokens;
                newTokens.push_back(tokenId);
                double newScore = hyp.score + logProbs[tokenId];
                bool isFinished = (tokenId == END_TOKEN);
                candidates.emplace_back(newTokens, newScore, isFinished);
            }
        }

        sort(candidates.begin(), candidates.end(), [](const Hypothesis& a, const Hypothesis& b) {
            return a.score > b.score;
        });

        beam.clear();
        for (int i = 0; i < min(beamWidth, (int)candidates.size()); i++) {
            if (candidates[i].finished) {
                completed.push_back(candidates[i]);
            } else {
                beam.push_back(candidates[i]);
            }
        }

        if (beam.empty()) break;
    }

    for (auto& h : beam) completed.push_back(h);
    sort(completed.begin(), completed.end(), [](const Hypothesis& a, const Hypothesis& b) {
        return a.score > b.score;
    });

    return completed;
}

Complexity Analysis

Approach	Time Complexity	Space Complexity	Quality
Greedy Search	`O(N × V)`	`O(N)`	Poor
Beam Search (width K)	`O(N × K × V)`	`O(K × N)`	Good
Exhaustive Search	`O(V^N)`	`O(V^N)`	Optimal

Where: N = sequence length, V = vocabulary size, and K = beam width. Beam Search is linear in both N and K, making it extremely practical.

Length Normalization

A critical issue with raw log-probability scoring: longer sequences always have lower (more negative) cumulative scores because we're adding more negative numbers. This biases beam search toward shorter sequences.

The fix is length normalization:

normalized_score = cumulative_log_prob / (sequence_length ^ α)

Where α (typically 0.6–0.8) controls how much to penalize/reward length.

// Length-normalized score calculation
double normalizedScore(double cumulativeLogProb, int length, double alpha) {
    double lengthPenalty = Math.pow(length, alpha);
    return cumulativeLogProb / lengthPenalty;
}

Beam Search in Real LLMs

Here's how Beam Search fits into the actual text generation pipeline:

Limitations of Beam Search

Exposure Bias: Mismatch between training (ground-truth context) and inference (generated context).
Generic / Boring Outputs: Prefers safer, common phrases over creative paths.
Repetition: Can looped word patterns ("the the the...") without n-gram repetition penalties.
Not Globally Optimal: Being a heuristic with finite K, it can still miss the true optimal sequence.

Modern Alternatives and Extensions

Method	Description	Best For
Greedy	Pick argmax at each step	Speed-critical, draft generation
Beam Search	Keep top-K beams	Machine translation, summarization
Top-K Sampling	Sample from top-K tokens	Creative text generation
Top-P (Nucleus) Sampling	Sample from top-P probability mass	Chatbots, story generation
Temperature Scaling	Sharpen/flatten probability distribution	Controlling creativity
Diverse Beam Search	Penalize similar beams	Getting varied outputs
Constrained Beam Search	Force certain tokens to appear	Template-guided generation

Conclusion

Beam Search is one of the most elegant solutions to the sequence decoding problem — a principled middle ground between the recklessness of Greedy Search and the infeasibility of Exhaustive Search. By maintaining a small set of the most promising partial sequences at every step, it finds high-quality outputs efficiently.

Happy coding — and may your beams always converge on the right answer! 🚀

Harnessing Sentiment Analysis with Java: A Step-by-Step Guide using NLP

noreply@blogger.com (Varun) — Sat, 03 Feb 2024 18:33:00 +0000

Sentiment analysis, a powerful application of Natural Language Processing (NLP), allows developers to gain insights into the emotions expressed in textual data. In this article, we'll explore how to perform sentiment analysis in Java using the Stanford NLP library. We'll guide you through setting up a Maven project, compiling the code, and running it with practical examples.

Prerequisites

Get IntelliJ Idea from https://www.jetbrains.com/idea/download.

You can skip this and use any other IDE as well. The steps for setting up a maven project will be different for each IDE.

Step 1: Create a New Project

Open IntelliJ IDEA and click on "Create New Project."
Choose "Maven" as the project type and click "Next."
Set the "GroupId" to com.simplestcodings and "ArtifactId" to SentimentAnalysis.
Click "Next" and then "Finish."

Step 2: Add Dependencies

Open the pom.xml file in the editor and replace the content with this section:


<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>com.simplestcodings</groupId>
    <artifactId>nlp</artifactId>
    <version>1.0-SNAPSHOT</version>

    <properties>
        <maven.compiler.source>17</maven.compiler.source>
        <maven.compiler.target>17</maven.compiler.target>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
    </properties>

    <dependencies>
        <dependency>
            <groupId>edu.stanford.nlp</groupId>
            <artifactId>stanford-corenlp</artifactId>
            <version>4.5.6</version>
        </dependency>
        <dependency>
            <groupId>edu.stanford.nlp</groupId>
            <artifactId>stanford-corenlp</artifactId>
            <version>4.5.6</version>
            <classifier>models</classifier>
        </dependency>
        <dependency>
            <groupId>org.slf4j</groupId>
            <artifactId>slf4j-simple</artifactId>
            <version>1.7.32</version>
        </dependency>
        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <version>1.18.30</version>
            <scope>provided</scope>
        </dependency>
    </dependencies>

</project>

Step 3: Create Project Structure

Right-click on the src directory in your project and choose "New" -> "Package."
Name it com.simplestcodings.
Inside the com.simplestcodings package, create a new Java class named SentimentAnalysis.

Step 4: Configure Properties

Right-click on the src directory and create a new directory named resources. Inside the resources directory, create a file named application.properties with the following content:

tokenize.whitespace=true
ssplit.eolonly=true
annotators = tokenize, ssplit, parse, sentiment

Step 5: Write Code

Replace the contents of SentimentAnalysis.java with the code provided below


package com.simplestcodings;

import edu.stanford.nlp.ling.CoreAnnotations;
import edu.stanford.nlp.pipeline.Annotation;
import edu.stanford.nlp.pipeline.StanfordCoreNLP;
import edu.stanford.nlp.sentiment.SentimentCoreAnnotations;
import edu.stanford.nlp.util.CoreMap;
import lombok.extern.slf4j.Slf4j;

@Slf4j
public class SentimentAnalysis {

    public static void main(String[] args) {
        // Initialize the Stanford NLP pipeline
        StanfordCoreNLP pipeline = new StanfordCoreNLP("application.properties");

        // Sample text for sentiment analysis
        String text = "Simplest codings is the best place to learn and grow. I am glad to be here.";

        // Perform sentiment analysis
        String sentiment = getSentiment(text, pipeline);

        // Display the result
        log.info("Text: {}, Sentiment: {}",text, sentiment);

        // Another Sample text for sentiment analysis
        text = "I hate this place. I am not coming back here again. I am very disappointed.";

        // Perform sentiment analysis
        sentiment = getSentiment(text, pipeline);

        // Display the result
        log.info("Text: {}, Sentiment: {}",text, sentiment);
    }

    private static String getSentiment(String text, StanfordCoreNLP pipeline) {
        // Create an Annotation object with the input text
        Annotation annotation = new Annotation(text);

        // Run all the NLP annotators on the text
        pipeline.annotate(annotation);

        // Extract the sentiment from the annotation
        CoreMap sentence = annotation.get(CoreAnnotations.SentencesAnnotation.class).get(0);
        String sentiment = sentence.get(SentimentCoreAnnotations.SentimentClass.class);

        return sentiment;
    }
}

Step 6: Run the Code

Right-click on the SentimentAnalysis class and select "Run SentimentAnalysis.main()". Observe the output in the Run console, which should display the sentiment of the provided text.

You have successfully set up and run a sentiment analysis Java project using the Stanford NLP library in IntelliJ IDEA. Feel free to explore more examples and experiment with different texts to gain insights into the sentiment analysis capabilities of Java and NLP. Happy coding!

Cracking the Piggy Bank Puzzle: A Java Adventure in Dynamic Programming

noreply@blogger.com (Varun) — Wed, 20 Dec 2023 19:57:00 +0000

Hey there, intrepid coders! Today, we're diving into a piggy bank heist… of the intellectual kind, of course! We'll be using a powerful technique called Dynamic Programming (DP) to crack the code of a mischievous piggy bank and unlock its hidden treasures. Buckle up, because this adventure requires both logic and a dash of mathematical magic.

Imagine a piggy bank with compartments numbered 1 to N. Each compartment holds a certain amount of coins. Your mission is to maximise the total coins you can collect by following these two rules:

You can only start at compartment 1 and move rightward, collecting all the coins in a compartment before proceeding.
You can either skip a compartment (earning you 0 coins) or rob a compartment, but robbing two consecutive compartments is forbidden.

This might seem tricky, but DP comes to the rescue! It breaks down the problem into smaller, overlapping subproblems and cleverly stores the solutions, saving you from redundant calculations. Think of it like mapping a treasure hunt – each solution to a subproblem guides you towards the bigger prize.


class PiggyBankBreaker {

    private final int[] coins; // Array storing coins in each compartment (1-indexed)
    private final int[] maxCoins; // DP array to store max achievable coins at each position (0-indexed)

    public PiggyBankBreaker(int[] coins) {
        this.coins = coins; // Copy original coin values
        this.maxCoins = new int[coins.length + 1]; // Allocate DP array with space for starting point (index 0)
    }

    public int crackPiggyBank() {
        // Base case: No coins at starting point
        maxCoins[0] = 0;

        // Loop through each compartment from index 1 (inclusive)
        for (int i = 1; i <= coins.length; i++) {
            // Option 1: Rob current compartment + max from 2 positions back (non-consecutive)
            int robCurrent;

            // Check if robbing current is even possible (avoid accessing coins[-1])
            if (i >= 3) {
                robCurrent = coins[i - 1] + maxCoins[i - 3];
            } else {
                // Default to skipping for initial positions where robbing isn't valid
                robCurrent = 0;
            }

            // Option 2: Skip current compartment and take max from previous position (consecutive)
            int skipCurrent = maxCoins[i - 1];

            // Choose the option that yields more coins
            maxCoins[i] = Math.max(robCurrent, skipCurrent);
        }

        // Return the maximum achievable coins from the last compartment
        return maxCoins[coins.length];
    }

    public static void main(String[] args) {
        // Example piggy bank with coins
        int[] coins = {2, 3, 1, 4, 5, 7, 10};

        PiggyBankBreaker breaker = new PiggyBankBreaker(coins);
        int maxLoot = breaker.crackPiggyBank();
        System.out.println("Maximum amount you can collect: " + maxLoot);
    }
}

This Java code solves the piggy bank problem, where you maximise the coins collected while adhering to two rules:

Start at compartment 1 and move rightward, collecting all coins in each compartment.
You can either skip or rob a compartment, but not two consecutive compartments.

The code utilises Dynamic Programming (DP) to efficiently solve this problem by breaking it down into smaller, overlapping subproblems. Here's a breakdown of the key aspects:

The method calculates the maximum coins achievable from any starting point.
Base case: maxCoins[0] = 0 since no coins are earned before starting.
Loop: Iterates through each compartment (index 1 to length).
Rob current option:
- Calculates robCurrent by adding the current coin value (coins[i - 1]) to the maximum coins achievable two positions back (maxCoins[i - 3]).
- Fix: A conditional statement (i >= 3) ensures this calculation only happens for valid positions (avoiding coins[-1] access).
- Otherwise, robCurrent is set to 0, mimicking skipping the compartment for initial positions.
Skip current option: Simply takes the maximum coins from the previous position (maxCoins[i - 1]).
Comparison: Chooses the maximum value between robCurrent and skipCurrent and stores it in maxCoins[i]. This ensures the optimal decision is recorded for future subproblems.
Final result: The last element maxCoins[coins.length] represents the maximum achievable coins from the starting point (compartment 1).

Longest common subsequence in Java

noreply@blogger.com (Varun) — Wed, 20 Dec 2023 15:17:00 +0000

Longest Common Subsequence (LCS)

It's the longest sequence of characters that is present in the same relative order within two or more strings.
It doesn't have to be a contiguous substring; the characters can appear in different positions within the original strings.

Understanding the Problem

Imagine two strings, written vertically on separate columns.
The goal is to find the longest sequence of characters that appears in the same order within both strings, even if they're not consecutive.

Character Grid

Create a grid where each row represents a character from the first string, and each column represents a character from the second string.
Fill each cell with a color indicating whether the corresponding characters match (e.g., green) or not (e.g., white).

Tracing Paths

Start at the top-left corner of the grid.
Move diagonally down-right only when characters match (green cells).
If characters don't match, move either down or right to continue searching for matches.
The path you take represents the LCS.

Visualize the LCS

Highlight the cells along the longest path with a bolder color or border.
The characters in those cells, read in order, form the LCS.

Example:

Consider strings "AGGTAB" and "GXTXAYB":



LCS: "GTAB" (highlighted cells)

Algorithm

Dynamic Programming Table:
- Create a 2D table dp with dimensions (m+1) x (n+1), where m and n are the lengths of the two strings.
- Fill the first row and column with 0s, indicating no LCS for empty strings.
Filling the Table:
- Iterate through the table, starting from dp[1][1].
- For each cell dp[i][j]:
  - If the characters at indices i-1 and j-1 in the strings match:
    - Set dp[i][j] = dp[i-1][j-1] + 1 (add 1 to the LCS length of the previous substrings).
  - Else:
    - Set dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (take the maximum LCS length from the previous options).
Reconstructing the LCS:
- Start from the bottom-right corner of the table (dp[m][n]).
- Backtrack:
  - If the characters at indices i-1 and j-1 match, add the character to the LCS and move diagonally up (i--, j--).
  - Else, move to the cell with the maximum value (either i-- or j--).
- Reverse the constructed LCS string to get the correct order.



public class LCS {

    public static String lcs(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();

        int[][] dp = new int[m + 1][n + 1];

        // Build the table in a bottom-up manner
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // Reconstruct the LCS
        StringBuilder lcs = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                lcs.append(str1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        // Reverse the LCS string
        return lcs.reverse().toString();
    }

    // Example usage for testing
    public static void main(String[] args) {
        System.out.println(lcs("ABCDEFG", "BCDGK"));
        System.out.println(lcs("AGGTAB", "GXTXAYB"));
        System.out.println(lcs("ABCDE", "A"));
        System.out.println(lcs("A", "BCDEF"));
    }
}

Explanation for code

1. lcs() Method:

Takes two strings as input.
Uses dynamic programming to find the longest common subsequence (LCS).
Returns the LCS string.

Steps

Create a DP Table: Stores the lengths of LCSs for substrings of different lengths.
Fill the DP Table:
- Iterates through characters of both strings.
- For each cell, calculates the length of the LCS based on previous calculations:
  - If characters match, add 1 to the LCS length of the previous substrings.
  - If not, take the maximum LCS length from the previous options.
Reconstruct the LCS: Backtracks through the DP table to find the characters in the LCS.
Reverse the LCS: Since it's built backward, reverse it before returning.

Take away points

Bottom-up approach: Builds the solution from smaller subproblems to the final LCS.
Dynamic programming principle: Avoids redundant calculations by storing intermediate results.
Time complexity: O(mn), where m and n are string lengths.
Space complexity: O(mn), due to the DP table.

Knapsack Problem implementation in Java

noreply@blogger.com (Varun) — Wed, 20 Dec 2023 14:59:00 +0000

Imagine a hiker's backpack (the knapsack) with limited space (capacity).

They have a collection of items, each with a value (usefulness) and a weight (space it occupies).

The goal is to fill the backpack with the most valuable combination of items, without exceeding its weight capacity.

Visualizing the Items

Item 1:  (value 60, weight 10)
Item 2:  (value 100, weight 20)
Item 3:  (value 120, weight 30)

The Knapsack

Decision-Making

Can't fit all items directly (total weight 60).
Optimal choice would be to put these items in the bag

Item: {value: 120, weight: 30}
Item: {value: 100, weight: 20}

Optimal Solution

KNAPSACK  (capacity 50)
     (value 120, weight 30)

Key Points

Knapsack represents a resource constraint (limited capacity).
Items represent choices with associated values and constraints (weight).
Goal is to maximize value within the constraint.
Often involves trade-offs and strategic decision-making.

In formal language, given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity, find the subset of items that maximizes the total value while fitting within the weight capacity.

Dynamic Programming Approach

Create a table dp:
- Dimensions: (n + 1) x (W + 1), where n is the number of items and W is the knapsack capacity.
- dp[i][w] stores the maximum value achievable using items up to the i-th item and with a maximum weight of w.
Fill the table:
- Base cases:
  - dp[0][w] = 0 for all w (no items, value is 0).
  - dp[i][0] = 0 for all i (zero weight capacity, value is 0).
- Recursive formula:
  - dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) if weight[i] <= w (Choose between including or excluding the i-th item)
  - dp[i][w] = dp[i-1][w] otherwise (Item cannot be included due to weight constraint)
Solution:

The maximum value is dp[n][W] (using all items with the knapsack capacity).
Backtrack to find the selected items.


import java.util.ArrayList;
import java.util.List;

public class Knapsack {

    public static List knapsack(List items, int capacity) {
        int[][] dp = new int[items.size() + 1][capacity + 1];

        // Build table dp[][] in a bottom-up manner
        for (int i = 0; i <= items.size(); i++) {
            for (int w = 0; w <= capacity; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0;
                } else if (items.get(i - 1).weight <= w) {
                    dp[i][w] = Math.max(items.get(i - 1).value + dp[i - 1][w - items.get(i - 1).weight], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        // Reconstruct the solution
        List selectedItems = new ArrayList<>();
        int i = items.size(), w = capacity;
        while (i > 0 && w > 0) {
            if (dp[i][w] != dp[i - 1][w]) {
                selectedItems.add(items.get(i - 1));
                w -= items.get(i - 1).weight;
            }
            i--;
        }

        return selectedItems;
    }

    public static void main(String[] args) {
        List items = new ArrayList<>();
        items.add(new Item(60, 10));
        items.add(new Item(100, 20));
        items.add(new Item(120, 30));
        int capacity = 50;

        List selected = knapsack(items, capacity);
        System.out.println("Selected items: " + selected);
    }

    public static class Item {
        int value;
        int weight;

        Item(int value, int weight) {
            this.value = value;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Item: {value: " + value + ", weight: " + weight + "}";
        }
    }
}

Explanation of code

1. Item Class:

Represents an item with its value and weight.

2. knapsack() Method:

Takes a list of items and a knapsack capacity as input.
Uses dynamic programming to solve the 0-1 Knapsack Problem.
Returns a list of selected items that maximize the total value without exceeding the capacity.

Steps

Create a 2D DP array: Stores intermediate results for subproblems.
Fill the DP array:
- Iterate through items and capacities.
- For each cell, calculate the maximum value achievable considering the current item and remaining capacity.
Reconstruct the solution: Backtrack through the DP array to find the selected items.

Take away points

Bottom-up approach: Builds the solution from smaller subproblems to the final solution.
Dynamic programming principle: Avoids redundant calculations by storing intermediate results.
Time complexity: O(nW), where n is the number of items and W is the capacity.
Space complexity: O(nW), due to the DP array.

Dijkstra algorithm implementation in Java

noreply@blogger.com (Varun) — Wed, 20 Dec 2023 14:40:00 +0000

Purpose

Finds the shortest paths from a single source vertex to all other vertices in a weighted graph.
Commonly used in GPS navigation, network routing, and logistics planning.

Key Concepts

Weighted Graph: A set of vertices (nodes) connected by edges with associated weights (distances, costs, etc.).
Source Vertex: The starting point for finding shortest paths.
Shortest Path: The path with the minimum total weight between two vertices.

Algorithm Steps

Initialization:
- Create a set S to store visited vertices (initially empty).
- Initialize an array distances with infinite values for all vertices except the source, which is set to 0.
- Create a priority queue Q to store vertices, prioritized by their tentative distances.
- Add the source vertex to Q.
Exploration Loop:
- While Q is not empty:
  - Extract the vertex u with the minimum distance from Q.
  - Add u to the set S (mark as visited).
  - For each neighbor vertex v of u:
    - If v is not visited and the distance to v through u is shorter than its current distance:
      - Update the distance to v in the distances array.
      - Add v to the priority queue Q (or update its priority if already present).
Result:
- The distances array now contains the shortest distances from the source vertex to all other vertices.
- To reconstruct the actual shortest paths, keep track of the predecessor of each vertex during the exploration.



import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.stream.Collectors;

public class Dijkstra {

    public static List dijkstra(Graph graph, int source) {
        int[] distances = new int[graph.numVertices];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[source] = 0;
        PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(i -> distances[i]));
        pq.offer(source);

        boolean[] visited = new boolean[graph.numVertices];
        while (!pq.isEmpty()) {
            int u = pq.poll();
            visited[u] = true;
            for (Edge edge : graph.adjacencyList.get(u)) {
                int v = edge.to;
                int weight = edge.weight;
                if (!visited[v] && distances[u] + weight < distances[v]) {
                    distances[v] = distances[u] + weight;
                    pq.offer(v);
                }
            }
        }

        return Arrays.stream(distances).boxed().collect(Collectors.toList());
    }

    public static Graph createRandomGraph(int numVertices) {
        Graph graph = new Graph(numVertices);
        Random random = new Random();
        // Add edges with random weights
        for (int i = 0; i < 9; i++) {
            for (int j = i + 1; j < 9; j++) {
                // Decide whether to create an edge with 50% probability
                if (random.nextBoolean()) {
                    int weight = random.nextInt(10) + 1; // Random weight between 1 and 10
                    graph.addEdge(i, j, weight);
                    graph.addEdge(j, i, weight); // Add reverse edge for undirected graph (if needed)
                }
            }
        }
        return graph;
    }

    public static void main(String[] args) {
        // Create a sample graph
        Graph graph = createRandomGraph(9);
        graph.visualize();
        int source = 0;
        List distances = dijkstra(graph, source);
        System.out.println("Shortest distances from " + source + ": " + distances);
    }

    public static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static class Graph {
        int numVertices;
        List> adjacencyList;

        Graph(int numVertices) {
            this.numVertices = numVertices;
            adjacencyList = new ArrayList<>();
            for (int i = 0; i < numVertices; i++) {
                adjacencyList.add(new ArrayList<>());
            }
        }

        void addEdge(int from, int to, int weight) {
            adjacencyList.get(from).add(new Edge(to, weight));
        }

        void visualize() {
            System.out.println("Graph Visualization:\n");
            for (int vertex = 0; vertex < numVertices; vertex++) {
                System.out.print(vertex + " -> ");
                for (Edge edge : adjacencyList.get(vertex)) {
                    System.out.print(edge.to + "(" + edge.weight + ") ");
                }
                System.out.println();
            }
        }
    }
}

Explanation of code

Graph Representation
- The Graph class models a graph using an adjacency list, where each vertex stores a list of its connected edges and their weights.
- The Edge class encapsulates the destination vertex and weight of an edge.
Dijkstra's Algorithm Implementation
- The dijkstra(Graph, source) method implements the algorithm's logic:
  - It maintains a priority queue to explore vertices in order of their tentative distances.
  - It iteratively relaxes edges to update distances and explore reachable vertices.
  - It ultimately returns a list of the shortest distances from the source vertex to all other vertices.
Random Graph Generation
- The createRandomGraph(numVertices) method generates a graph with a specified number of vertices and randomly assigns edges with weights between 1 and 10.

Ternary Search Tree Implementation in C++

noreply@blogger.com (Varun) — Wed, 12 Oct 2016 17:11:00 +0000

A Ternary Search Tree is a trie which leverages concepts of Binary Search Tree as well. A Ternary Search Tree is as memory efficient as Binary Search Trees and time efficient as a Trie.

It is an efficient data structure to store and search large number of strings.

A node in a Ternary Search Tree comprises of these fields :

Left pointer - Points to Ternary Search Tree containing all strings alphabetically lesser than current node's data
Right pointer - Points to Ternary Search Tree containing all strings alphabetically greater than current node's data
Equal pointer - Points to Ternary Search Tree containing all strings alphabetically equal to current node's data
End of string flag - Flag indicating the end of string
Data - Actual data in the form of single character

Ternary Search Tree Node

For example, consider adding these strings in the same order into a Ternary Search Tree :

"Lead"
"Leader"
"Leads"
"Late"
"State"

Let's build a visualization of ternary search tree out of above data :

"Lead"
"Leader"
"Leads"
"Late"
"State"



//TST.h
#ifndef TST_H
#define TST_H
//#define DEBUG_PROGRAM_MEMORY

//Node of a Ternary Search Tree
typedef struct TSTNode{
 char data; //Actual data stored in form of character
 bool bEOS; //flag marking end of string
 struct TSTNode* left;   //All character data less than this node
 struct TSTNode* eq;  //All character data equal to this node
 struct TSTNode* right; //All character data greater than this node
}TSTNode;

//Inserts a string in the TST
TSTNode* Insert(TSTNode* root, char* str); 

//Prints all strings in the TST
void PrintAllStringsInTST(TSTNode* root);

//Gets the length of maximum length string in TST
int MaxLenStringLen(TSTNode *root);

//Deleted the complete TST
void DeleteTST(TSTNode *root);

//Search a pattern in TST
bool SearchTST(TSTNode *root, char* pattern);

//Prints 
#ifdef DEBUG_PROGRAM_MEMORY
#include <map>

static std::map<TSTNode*, char> mem_addrs;
void CheckTSTMem();
#endif

#endif



//TST.cpp
#include <iostream>
#define DEBUG_PROGRAM_MEMORY

#include "TST.h"
#include <cstdlib>
#include <utility>

#define MAX_LEN 1024

#define MAX( a, b, c ) ((a)>(b) ? ((a)>(c) ? (a):(c)) : ( (b)>(c) ? (b):(c) ))


TSTNode* Insert(TSTNode* root, char* str)
{
 if(root == NULL)
 {
  root = (TSTNode*)malloc(sizeof(TSTNode));
  if(root == NULL)
  {
   std::cout<<"Memory allocation failed"<<std::endl;
   return NULL;
  }

  //Insert first character of string in the root node
  root->data = *str;
#ifdef DEBUG_PROGRAM_MEMORY
  mem_addrs.insert(std::make_pair(root, root->data));
#endif
  root->bEOS = false;
  root->left = root->eq = root->right = NULL;
 }
 
 if(*str  < root->data)
  root->left = Insert(root->left, str);
 else if (*str == root->data)
 {
  if(*(str + 1))
   root->eq = Insert(root->eq, str + 1);
  else
   root->bEOS = true;
 }
 else
  root->right = Insert(root->right, str);
 
 return root; 
}

//Helper to print the strings in TST
static void PrintHelper(TSTNode* root, char* buffer, int depth)
{
 if (root)
 {
  // Traverse the left subtree
  PrintHelper(root->left, buffer, depth);

  buffer[depth] = root->data;
  //Once end of string flag is encountered, print the string
  if (root->bEOS)
  {
   buffer[depth + 1] = '\0';
   std::cout<< buffer << std::endl;
  }

  // Traverse the middle subtree
  PrintHelper(root->eq, buffer, depth + 1);

  // Traverse the right subtree
  PrintHelper(root->right, buffer, depth);
 }
}

// Function to print TST's strings
void PrintAllStringsInTST(TSTNode* root)
{
 char buffer[MAX_LEN];
 PrintHelper(root, buffer, 0);
}

bool SearchTST(TSTNode *root, char* pattern)
{
 while (root != NULL)
 {
  if (*pattern < root->data)
   root = root->left;
  else if (*pattern == root->data)
  {
   //If end of string flag is found and the pattern length is also exhausted, 
   //we can safely say that the pattern is present in the TST
   if (root->bEOS && *(pattern + 1) == '\0')
    return true;
   pattern++;
   root = root->eq;
  }
  else
   root = root->right;
 }

 return false;
}

//Function to determine largest 
int MaxLenStringLen(TSTNode *root)
{
 if (root == NULL)
  return 0;

 int leftLen = MaxLenStringLen(root->left);
 int middleLen = MaxLenStringLen(root->eq) + 1;
 int rightLen = MaxLenStringLen(root->right);

 return MAX( leftLen, middleLen, rightLen);
}

void DeleteTST(TSTNode *root)
{
 TSTNode *tmp = root;
 if (tmp)
 {
  DeleteTST(tmp->left);
  DeleteTST(tmp->eq);
  DeleteTST(tmp->right);

#ifdef DEBUG_PROGRAM_MEMORY
  mem_addrs.erase(tmp);
#endif
  delete tmp;
 }
}

#ifdef DEBUG_PROGRAM_MEMORY
void CheckTSTMem()
{
 std::map<TSTNode*, char>::iterator itr = mem_addrs.begin();

 if (mem_addrs.size() == 0)
 {
  std::cout << "No memory leaks";
  return;
 }

 while (itr != mem_addrs.end()) 
 {
  std::cout << "Memory address " << itr->first<< " for \"" << itr->second << "\" has not been deallocated" << std::endl;
  ++itr;
 }
}
#endif



//Main.cpp
#include <iostream>
#include "TST.h"

int main(int argc, char** argv) {
 
 TSTNode *root = NULL;
 root = Insert(root, "boats");
 root = Insert(root, "boat");
 root = Insert(root, "bat");
 root = Insert(root, "bats");
 root = Insert(root, "stages");

 PrintAllStringsInTST(root);
 std::cout << "Maximum length string in this TST is of size "<< MaxLenStringLen(root) << std::endl;

 char *str = "hello";
 char *str1 = "bat";

 if (SearchTST(root, str) == false)
  std::cout << "\""<<str<<"\" not found in TST" << std::endl;
 else
  std::cout << "\"" << str << "\" is present in TST" << std::endl;

 if (SearchTST(root, str1) == false)
  std::cout << "\"" << str << "\" not found in TST" << std::endl;
 else
  std::cout << "\"" << str1 << "\" is present in TST" << std::endl;

 DeleteTST(root);

#ifdef DEBUG_PROGRAM_MEMORY
 CheckTSTMem();
#endif
 
 return 0;
}

String matching using KMP algorithm : C++ Implementation

noreply@blogger.com (Varun) — Sat, 24 Sep 2016 15:01:00 +0000

KMP Algorithm is one the well-known string matching algorithms. It finds a pattern in a string. The pattern can exist multiple times in the string. This implementation in C++ gives indexes of all such matches in the string to be searched.

e.g.

String to be searched : "ABCDBCAAB ABCDABCDABDE ABCDABD"
Pattern : "ABCD"

The result will be 4 index locations 0, 10, 14 and 23

However, there is a limitation of KMP algorithm where the pattern overlaps.

Consider this scenario :

String to be searched: "ABCABCABCA"
Pattern: "ABCA"
The result from KMP algorithm will be 0 and 6 locations. It cannot identify the overlapping matches like this:
ABCABCABCA
ABCABCABCA
ABCABCABCA



#include <iostream>
#include <cstdlib>

using namespace std;
#define MAX_MATCHES 100

//Array to store matched indexes
int FOUND[MAX_MATCHES];
//variable to store last index in FOUND array
static int l = 0;

//Partial match table
void kmp_table(string W, int *T )
{
 int pos = 2;
 int cnd = 0;
 int length = W.length();
 
 T[0] = -1;
 T[1] = 0;
 
 while( pos < length)
 {
  if(W[pos-1] == W[cnd])
  {
   T[pos] = cnd + 1;
   cnd++;
   pos++;
  }
  else if( cnd > 0)
   cnd = T[cnd];
  else
  {
   T[pos] = 0;
   pos++;
  }
 }
}

//Search function
void kmp_search(string S, string W)
{
 
 int m = 0; 
 int i = 0;
 int sizeS = S.length();
 int sizeW = W.length();
 
 int *T = new int[sizeof(int) * sizeW];
 
 kmp_table(W, T);
 
 while( (m + i) < sizeS)
 {
  if (W[i] == S[m + i]) 
  {
            if (i == (sizeW - 1))
            {
             //Add the start index of match in the FOUND table
             FOUND[l++] = m;
   }
    
            i++;
        }
        else
        {
            if (T[i] > -1)
            {
                m = m + i - T[i];
    i = T[i];
            }
            else
            {
                m = m + 1;
    i = 0;
            }
        }
 }
 
 delete(T);
}

int main()
{
 string S = "ABCDBCAAB ABCDABCDABDE ABCDABD";
 string W = "ABCD";
 
 kmp_search(S,W);
  
 for (int i = 0 ; i < l; i++)
  cout<<"Pattern found at "<< FOUND[i] <<endl; 
}

Component Object Model(COM) - Implementation in C++ -- Usage in C++, C#

noreply@blogger.com (Varun) — Tue, 24 Feb 2015 12:22:00 +0000

As per Microsoft "Component Object Model or COM is a platform-independent, distributed, object-oriented system for creating binary software components that can interact".
COM defines a standard (Object Model) and the implementation part is left to the developer. These objects can communicate within a process or across the processes, on the same or different machine with different programming languages.

Language requirement for COM :

1. Ability to create structures of pointers

2. Ability to call functions using pointers

Object-oriented languages such as C++ and Smalltalk provide programming mechanisms that simplify the implementation of COM objects, but languages such as C, Java, and VBScript can be used create and use COM objects.

Object's data is accessed using interfaces. The functions of this interface are called methods. The pointers to these interfaces enables to call the methods.

More information on COM is available at the MSDN .

In a nutshell , COM provides interfaces which can be implemented in different languages and can be used over distributed platforms.

To provide portability across platforms and programming languages, COM uses interface definition in platform-independent language, IDL(Interface Definition Language).

Steps involved to create COM interface:

Define the interface/s in .idl file.
Compile the .idl file using IDL compiler(platform and language specific) to generate language and platform specific code.
Implement these interface/s in the specific language.
Use it.

In our example, we are using MIDL compiler to generate the C++ specific code and DLL.
We will use ATL to make the implementation easier. ATL is the Active Template Library, a set of template-based C++ classes with which you can easily create small, fast Component Object Model (COM) objects. It has special support for key COM features including: stock implementations of IUnknown, IClassFactory, IClassFactory2, and IDispatch; dual interfaces; standard COM enumerator interfaces; connection points; tear-off interfaces; and ActiveX controls.

We are using Visual Studio 2005 for our example. Visual Studio provides ATL project wizard which will help a lot and make the process easy.

Steps to generate COM DLL:

Create a new project in Visual Studio File->New->Project->Visual C++ -> ATL => ATL Project.
Give the project name as Calculator as we will be implementing a calculator interface using COM.
Choose DLL(Dynamic-link library) in the Application Settings -> Finish.
This structure will be visible once the project is created.
Now add a class following the image as below. Right click on the project Add->Class.
We will now add a COM Object using ATL Simple Object.
Give the name of class as CalculatorImpl (This defines the implentation of the interface). You can see under the panel C++ these four areas are updated -> Short Name, .h file, Class, .cpp file to be as CalculatorImpl, CalculatorImpl.h , CCalculatorImpl and CalculatorImpl.cpp respectively . Also in the panel COM below, these four areas are also updated - CoClass, Type, Interface and ProgID. Change these according to the image below.
Choose the Options for the COM Object as below, then click on Finish.
After these changes, the Calculator.idl file will look like this:

Here, the declaration for interface ICalculator is added. ICalculator implements IDispatch interface. IDispatch is the interface that exposes the OLE Automation protocol. It is one of the standard interfaces exposed by COM. The IDispatch interface inherits from the IUnknown interface. More information on IDispatch can be found here. You can also see the declaration of the Type Library CalculatorLib which declares a coclass Calculator as well. This CoClass creates a COM object, which can implement a COM interface. The Type library information helps in creating .tlb file which is a binary file that stores information about a COM or DCOM object's properties and methods in a form that is accessible to other applications at runtime. Using a type library, an application or browser can determine which interfaces an object supports, and invoke an object's interface methods. This can occur even if the object and client applications were written in different programming languages. The COM/DCOM run-time environment can also use a type library to provide automatic cross-apartment, cross-process, and cross-machine marshaling for interfaces described in type libraries.
Now our interface is ready to have some methods. Switch to Class View beside Solution Explorer as shown in image below. Right click on ICalculator interface and add a method. Add->Add Method.
Give the method name as Add , check parameter attributes as 'in', parameter type DOUBLE, parameter name as Input1. Click on Add. You should see the parameter being added to the list box. Similarly add one more input parameter named Input2. Now add an output parameter with parameter type DOUBLE*, parameter name as pOutput, check parameter attributes as 'out' and 'retval'. Click on Add. Click on Next->Finish.

Similarly add three more methods Subtract, Multiply and Divide.
After adding the methods , you should see the functions' skeleton created in Calculator.idl and CalculatorImpl.cpp like this :
We will add the implementation in the skeleton.
Now compile the solution. It will generate Calculator.dll in the project output directory (e.g. for 64 bit Release configuration it is %PROJECT_HOME%\Calculator\Calculator\x64\Release by default)

Now we have our COM DLL. To use it , we need some code.

Steps to create sample C++ code to test COM DLL:

Create an Empty Win32 Console Project in Visual Studio
Create an Empty cpp file in the project (TestCalc.cpp)
Add the path to Calculator.h in Additional Include Directories in the project properties. Right click project -> Properties -> Configuration Properties -> C/C++ -> General.
Add Calculator_i.c in the Project Source.
Populate TestCalc.cpp with the contents given later in the blog post.
Run the executable(F5).

Note: One advantage using the Visual Studio to build our COM dll was that it registers the COM DLL by default. So we do not need to do it manually. This is the reason why we are able to run the test code even without the DLL being present in the System Path or adding it's path to PATH environment variable .

Now as we have been saying that the COM is interoperable between the languages/platform etc. Let's see some code in action.
We are going to use the COM DLL generated in C# application.

Before we go on using DLLs directly , let's be SMART and create .NET wrappers over COM DLL. Now you would ask what's that ??

The COM components has unmanaged code while .NET framework has managed code. Data types, method signatures, and error-handling mechanisms vary between managed and unmanaged object models
Code that executes under the control of the runtime is called managed code and the code that runs outside the runtime is called unmanaged code.

To simplify this, .NET wrappers are generated over existing COM components which allows unmanaged model to be converted to managed.
More information in this link.

Steps to create .NET wrapper from COM DLL:

Run this command from the output directory:

     tlbimp /machine: x64 Calculator.dll /out: Calculator_Wrapper.dll

It will generate Calculator_Wrapper.dll which is nothing but our .NET wrapper over COM.

Steps to create C# application to test COM DLL :

Create a Windows Application TestCalcCCharp from Visual Studio
Add a reference to the wrapper Calculator_Wrapper.dll
Create a simple form as per the code in the blog post.
Populate the functions to call the methods from COM.



// CalculatorImpl.cpp : Implementation of CCalculatorImpl

#include "stdafx.h"
#include "CalculatorImpl.h"

// CCalculatorImpl

STDMETHODIMP CCalculatorImpl::Add(DOUBLE Input1, DOUBLE Input2, DOUBLE* pOutput)
{
 *pOutput = Input1 + Input2;

 return S_OK;
}

STDMETHODIMP CCalculatorImpl::Subtract(DOUBLE Input1, DOUBLE Input2, DOUBLE* pOutput)
{
 *pOutput = Input1 - Input2;
 
 return S_OK;
}

STDMETHODIMP CCalculatorImpl::Multiply(DOUBLE Input1, DOUBLE Input2, DOUBLE* pOutput)
{
 *pOutput = Input1 * Input2;

 return S_OK;
}

STDMETHODIMP CCalculatorImpl::Divide(DOUBLE Input1, DOUBLE Input2, DOUBLE* pOutput)
{
 *pOutput = Input1 / Input2;

 return S_OK;
}



//TestCalc.cpp
#include "Calculator.h"
#include <iostream>
#include <stdexcept>
using std::runtime_error; 

int main()
{
 HRESULT hr ;
 ICalculator      *calc = NULL;

 hr = CoInitialize(0);

 if(SUCCEEDED(hr))
    {
  hr = CoCreateInstance( CLSID_Calculator, NULL, 
            CLSCTX_INPROC_SERVER,
   IID_ICalculator, (void**) &calc);

        // If we succeeded then call the Add 
        // method, if it failed
        // then display an appropriate message to the user.
        if(SUCCEEDED(hr))
        {
            double ReturnValue;
   double a = 4;
   double b = 0;
   calc->Add(a, b, &ReturnValue);
            std::cout << "The answer for "<<a<<" + "<<b<<" is: " 
                << ReturnValue << std::endl;
            calc->Release(); 
        }
        else
        {
            std::cout << "CoCreateInstance Failed." << std::endl;
        }
    }
    // Uninitialize COM
    CoUninitialize();

}


//Form1.Designer.cs
namespace TestCalcCSharp
{
    partial class Form1
    {
        /// <summary>
        /// Required designer variable.
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
        /// Clean up any resources being used.
        /// </summary>
        /// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Windows Form Designer generated code

        /// <summary>
        /// Required method for Designer support - do not modify
        /// the contents of this method with the code editor.
        /// </summary>
        private void InitializeComponent()
        {
            this.calcPanel = new System.Windows.Forms.GroupBox();
            this.groupBox1 = new System.Windows.Forms.GroupBox();
            this.logTextBox = new System.Windows.Forms.RichTextBox();
            this.label5 = new System.Windows.Forms.Label();
            this.label4 = new System.Windows.Forms.Label();
            this.label1 = new System.Windows.Forms.Label();
            this.divBtn = new System.Windows.Forms.Button();
            this.subBtn = new System.Windows.Forms.Button();
            this.addBtn = new System.Windows.Forms.Button();
            this.mulBtn = new System.Windows.Forms.Button();
            this.textBox3 = new System.Windows.Forms.TextBox();
            this.textBox2 = new System.Windows.Forms.TextBox();
            this.label3 = new System.Windows.Forms.Label();
            this.label2 = new System.Windows.Forms.Label();
            this.textBox1 = new System.Windows.Forms.TextBox();
            this.calcPanel.SuspendLayout();
            this.groupBox1.SuspendLayout();
            this.SuspendLayout();
            // 
            // calcPanel
            // 
            this.calcPanel.Controls.Add(this.groupBox1);
            this.calcPanel.Controls.Add(this.label5);
            this.calcPanel.Controls.Add(this.label4);
            this.calcPanel.Controls.Add(this.label1);
            this.calcPanel.Controls.Add(this.divBtn);
            this.calcPanel.Controls.Add(this.subBtn);
            this.calcPanel.Controls.Add(this.addBtn);
            this.calcPanel.Controls.Add(this.mulBtn);
            this.calcPanel.Controls.Add(this.textBox3);
            this.calcPanel.Controls.Add(this.textBox2);
            this.calcPanel.Controls.Add(this.label3);
            this.calcPanel.Controls.Add(this.label2);
            this.calcPanel.Controls.Add(this.textBox1);
            this.calcPanel.Location = new System.Drawing.Point(13, 13);
            this.calcPanel.Name = "calcPanel";
            this.calcPanel.Size = new System.Drawing.Size(450, 344);
            this.calcPanel.TabIndex = 0;
            this.calcPanel.TabStop = false;
            this.calcPanel.Text = "Calculator";
            // 
            // groupBox1
            // 
            this.groupBox1.Controls.Add(this.logTextBox);
            this.groupBox1.Location = new System.Drawing.Point(6, 238);
            this.groupBox1.Name = "groupBox1";
            this.groupBox1.Size = new System.Drawing.Size(438, 100);
            this.groupBox1.TabIndex = 34;
            this.groupBox1.TabStop = false;
            this.groupBox1.Text = "Logs";
            // 
            // logTextBox
            // 
            this.logTextBox.Location = new System.Drawing.Point(6, 19);
            this.logTextBox.Name = "logTextBox";
            this.logTextBox.Size = new System.Drawing.Size(432, 81);
            this.logTextBox.TabIndex = 33;
            this.logTextBox.Text = "";
            // 
            // label5
            // 
            this.label5.AutoSize = true;
            this.label5.Location = new System.Drawing.Point(254, 22);
            this.label5.Name = "label5";
            this.label5.Size = new System.Drawing.Size(37, 13);
            this.label5.TabIndex = 32;
            this.label5.Text = "Result";
            // 
            // label4
            // 
            this.label4.AutoSize = true;
            this.label4.Location = new System.Drawing.Point(163, 22);
            this.label4.Name = "label4";
            this.label4.Size = new System.Drawing.Size(37, 13);
            this.label4.TabIndex = 31;
            this.label4.Text = "Input2";
            // 
            // label1
            // 
            this.label1.AutoSize = true;
            this.label1.Location = new System.Drawing.Point(83, 22);
            this.label1.Name = "label1";
            this.label1.Size = new System.Drawing.Size(37, 13);
            this.label1.TabIndex = 30;
            this.label1.Text = "Input1";
            // 
            // divBtn
            // 
            this.divBtn.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.divBtn.Location = new System.Drawing.Point(352, 134);
            this.divBtn.Name = "divBtn";
            this.divBtn.Size = new System.Drawing.Size(75, 36);
            this.divBtn.TabIndex = 29;
            this.divBtn.Text = "Divide";
            this.divBtn.UseVisualStyleBackColor = true;
            this.divBtn.Click += new System.EventHandler(this.divBtn_Click);
            // 
            // subBtn
            // 
            this.subBtn.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.subBtn.Location = new System.Drawing.Point(125, 134);
            this.subBtn.Name = "subBtn";
            this.subBtn.Size = new System.Drawing.Size(75, 36);
            this.subBtn.TabIndex = 28;
            this.subBtn.Text = "Subtract";
            this.subBtn.UseVisualStyleBackColor = true;
            this.subBtn.Click += new System.EventHandler(this.subBtn_Click);
            // 
            // addBtn
            // 
            this.addBtn.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.addBtn.Location = new System.Drawing.Point(14, 134);
            this.addBtn.Name = "addBtn";
            this.addBtn.Size = new System.Drawing.Size(75, 36);
            this.addBtn.TabIndex = 27;
            this.addBtn.Text = "Add";
            this.addBtn.UseVisualStyleBackColor = true;
            this.addBtn.Click += new System.EventHandler(this.addBtn_Click);
            // 
            // mulBtn
            // 
            this.mulBtn.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.mulBtn.Location = new System.Drawing.Point(239, 134);
            this.mulBtn.Name = "mulBtn";
            this.mulBtn.Size = new System.Drawing.Size(75, 36);
            this.mulBtn.TabIndex = 26;
            this.mulBtn.Text = "Multiply";
            this.mulBtn.UseVisualStyleBackColor = true;
            this.mulBtn.Click += new System.EventHandler(this.mulBtn_Click);
            // 
            // textBox3
            // 
            this.textBox3.Enabled = false;
            this.textBox3.Location = new System.Drawing.Point(257, 41);
            this.textBox3.Name = "textBox3";
            this.textBox3.Size = new System.Drawing.Size(170, 20);
            this.textBox3.TabIndex = 7;
            // 
            // textBox2
            // 
            this.textBox2.Location = new System.Drawing.Point(166, 41);
            this.textBox2.Name = "textBox2";
            this.textBox2.Size = new System.Drawing.Size(57, 20);
            this.textBox2.TabIndex = 6;
            // 
            // label3
            // 
            this.label3.AutoSize = true;
            this.label3.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.label3.Location = new System.Drawing.Point(228, 44);
            this.label3.Name = "label3";
            this.label3.Size = new System.Drawing.Size(16, 17);
            this.label3.TabIndex = 4;
            this.label3.Text = "=";
            // 
            // label2
            // 
            this.label2.AutoSize = true;
            this.label2.Font = new System.Drawing.Font("Microsoft Sans Serif", 10F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
            this.label2.Location = new System.Drawing.Point(146, 44);
            this.label2.Name = "label2";
            this.label2.Size = new System.Drawing.Size(16, 17);
            this.label2.TabIndex = 3;
            this.label2.Text = "+";
            // 
            // textBox1
            // 
            this.textBox1.Location = new System.Drawing.Point(83, 41);
            this.textBox1.Name = "textBox1";
            this.textBox1.Size = new System.Drawing.Size(57, 20);
            this.textBox1.TabIndex = 1;
            // 
            // Form1
            // 
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(475, 369);
            this.Controls.Add(this.calcPanel);
            this.Name = "Form1";
            this.Text = "Calculator";
            this.calcPanel.ResumeLayout(false);
            this.calcPanel.PerformLayout();
            this.groupBox1.ResumeLayout(false);
            this.ResumeLayout(false);

        }

        #endregion

        private System.Windows.Forms.GroupBox calcPanel;
        private System.Windows.Forms.TextBox textBox1;
        private System.Windows.Forms.TextBox textBox3;
        private System.Windows.Forms.TextBox textBox2;
        private System.Windows.Forms.Label label3;
        private System.Windows.Forms.Label label2;
        private System.Windows.Forms.Button mulBtn;
        private System.Windows.Forms.Button divBtn;
        private System.Windows.Forms.Button subBtn;
        private System.Windows.Forms.Button addBtn;
        private System.Windows.Forms.Label label5;
        private System.Windows.Forms.Label label4;
        private System.Windows.Forms.Label label1;
        private System.Windows.Forms.RichTextBox logTextBox;
        private System.Windows.Forms.GroupBox groupBox1;

    }
}


//Form1.cs
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using Calculator_Wrapper;
using System.Runtime.InteropServices;

namespace TestCalcCSharp
{
    public partial class Form1 : Form
    {
        Calculator_Wrapper.Calculator calc = null;

        public Form1()
        {
            InitializeComponent();
            calc = new Calculator();
        }

        private void addBtn_Click(object sender, EventArgs e)
        {
            try
            {
                double inp1 = double.Parse(textBox1.Text);
                double inp2 = double.Parse(textBox2.Text);


                double output = calc.Add(inp1, inp2);

                textBox3.Text = output.ToString();
            }
            catch (Exception ex)
            {
                logTextBox.Text = ex.Message;
            }
        }

        private void subBtn_Click(object sender, EventArgs e)
        {
            try
            {
                double inp1 = double.Parse(textBox1.Text);
                double inp2 = double.Parse(textBox2.Text);


                double output = calc.Subtract(inp1, inp2);

                textBox3.Text = output.ToString();
            }
            catch (Exception ex)
            {
                logTextBox.Text = ex.Message;
            }
        }

        private void mulBtn_Click(object sender, EventArgs e)
        {
            try
            {
                double inp1 = double.Parse(textBox1.Text);
                double inp2 = double.Parse(textBox2.Text);

                double output = calc.Multiply(inp1, inp2);

                textBox3.Text = output.ToString();
            }
            catch (Exception ex)
            {
                logTextBox.Text = ex.Message;
            }
        }

        private void divBtn_Click(object sender, EventArgs e)
        {
            try
            {
                double inp1 = double.Parse(textBox1.Text);
                double inp2 = double.Parse(textBox2.Text);

                if (inp2 == 0) throw new DivideByZeroException();
                double output = calc.Divide(inp1, inp2);
                textBox3.Text = output.ToString();
            }
            catch (Exception ex)
            {
                logTextBox.Text = ex.Message + "\n";
            }
        }
    }
}

Facade design pattern implementation in C++

noreply@blogger.com (Varun) — Sun, 26 Oct 2014 16:33:00 +0000

Facade means the exterior of any object in general. Facade Design Pattern provides similar functionality as well. It provides a simple interface to a complex system. Just as we can not tell from the exterior of a building what lies inside it, Facade design pattern provides an interface which hides the internal complexity of a system. It only exposes the desired interfaces which have to be used by a client. It can be only a small subsystem of the complex system as the client may not need all the functionality of the complex system. Also it could modify the interfaces as well to provide the complete functionality of the system.

Facade Design Pattern

For our implementation of the Facade Design Pattern, we have chosen example of Online Shopping model. The following diagram represents the relationships and flow between the classes.

Class Diagram for below example

The example works like this. OnlineShoppingFacade is the interface which is exposed to the customers (us). It's just like any portal like Flipkart, Amazon or eBay. Now we do not know what the heck is going behind those websites. All we know is that we have just placed an order and we will get a delivery after a certain period of time. Of course there is a status tracker something like this

But still the intricacies behind the process is hidden away from us. This is the Facade for the Online Shopping Portal.

Below is a simplistic implementation just to demo how Facade Design Pattern works using a C++ example.

Facade Design Pattern Implementation(C++)

Update(5th Nov 2014): The code is updated to work on linux platform as well.



#include <iostream>
#include <string>
#ifdef _WIN32
#include <windows.h>
#elif defined __linux__
#include <unistd.h>
#endif

/* Uncomment below line to enable debug logs */
/* #define DEBUG */
 
std::string _stateToStrCourier[]   = { "Received", "VerifyReachbility", "AssignPerson", 
                                       "DispatchPackage", "GetDeliveryConfirmation", "Complete"};
std::string _stateToStrVendor[]    = { "Received", "VerifyInventory", "GetItemFromWareHouse", 
                                       "PackItem", "ContactCourier", "Complete"};
std::string _stateToStrOrderTeam[] = { "Received", "VerifyPayment", "ContactVendor", "Complete"};

void mySleep(unsigned int millisecs)
{
#ifdef _WIN32
 Sleep(millisecs);
#elif defined __linux__
 usleep(1000 * millisecs);
#endif
}

class Courier
{
public:
 void submitRequestToCourier()
 {
  _state = 0;
 }
 bool checkStatus()
 {
#ifdef DEBUG
  std::cout<<"Courier: Current State: "<<_stateToStrCourier[_state]<< std::endl;
#endif
  mySleep(500); /* Do some useful work here */

  _state++;
  if (_state == Complete)
   return 1;
  return 0;
 }
private:
 enum States
 {
  Received, VerifyReachbility, AssignPerson, DispatchPackage, GetDeliveryConfirmation, Complete
 };
 int _state;
};
 
class Vendor
{
public:
 void submitRequestToVendor()
 {
  _state = 0;
 }
 bool checkStatus()
 {
#ifdef DEBUG
  std::cout<<"Vendor: Current State: "<<_stateToStrVendor[_state]<< std::endl;
#endif
  mySleep(500); /* Do some useful work here */

  _state++;
  if (_state == Complete)
   return 1;
  return 0;
 }
private:
 enum States
 {
  Received, VerifyInventory, GetItemFromWareHouse, PackItem, ContactCourier, Complete
 };
 int _state;
 
};
 
class OrderingTeam
{
public:
 void submitRequestToOrderTeam()
 {
  _state = 0;
 }
 bool checkStatus()
 {
#ifdef DEBUG
  std::cout<<"OrderingTeam: Current State: "<<_stateToStrOrderTeam[_state]<< std::endl;
#endif
  mySleep(500); /* Do some useful work here */ 
  _state++;
  if (_state == Complete)
   return 1;
  return 0;
 }
private:
 enum States
 {
  Received, VerifyPayment, ContactVendor, Complete
 };
 int _state;
};
 
class OnlineShoppingFacade
{
public:
 OnlineShoppingFacade()
 {
  _count = 0;
 }
 void submitRequest()
 {
  _state = 0;
 }
 bool checkStatus()
 {
  /* Item request has just been received */
  switch(_state)
  {
  case Received:
   _state++;
   /* Forward the job request to the ordering team */
   _order.submitRequestToOrderTeam();
   std::cout << "submitted to Order Team - " << _count <<
    " followups till now" << std::endl;
   break;
  case SubmittedToOrderTeam:
   /* If order team has completed verification, 
   place the request with vendor */
   if (_order.checkStatus())
   {
    _state++;
    _vendor.submitRequestToVendor();
    std::cout << "submitted to Vendor - " << _count <<
     " followups till now" << std::endl;
   }
   break;
  case SubmittedToVendor:
   /* If vendor has packed the item, forward it to courier */
   if (_vendor.checkStatus())
   {
    _state++;
    _courier.submitRequestToCourier();
    std::cout << "submitted to Courier - " << _count <<
     " followups till now" << std::endl;
   }
   break;
  case SubmittedToCourier:
   /* If package is delivered, order is complete */
   if (_courier.checkStatus())
    return 1;
  default:
   break;
  }
 
  _count++;
 
  /* The order is not complete */
  return 0;
 }
 int numFUPs()
 
 {
  return _count;
 }
private:
 enum States
 {
  Received, SubmittedToOrderTeam, SubmittedToVendor, SubmittedToCourier
 };
 
 int _state;
 int _count;
 
 OrderingTeam _order;
 Vendor _vendor;
 Courier _courier;
};
 
int main()
{
 OnlineShoppingFacade onlinereq;
 
 onlinereq.submitRequest();
 
 /* Keep checking until order is complete */
 while (!onlinereq.checkStatus());
 
 std::cout << "Order completed after " << onlinereq.numFUPs() << 
  " followups" << std::endl;
}

Create a SOAP web service client in C++

noreply@blogger.com (Varun) — Sat, 18 Oct 2014 17:07:00 +0000

What is SOAP?

SOAP(Simple Object Access Protocol) is a great way to exchange information over the network. Normally it is used with application protocols like HTTP, SMTP etc. The envelope containing the information is XML based.

It provides the basic messaging infrastructure for web services.

An example SOAP request looks like :

 
<?xml version="1.0" encoding="UTF-8"?>
<soapenv:Envelope
        xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/"
        xmlns:xsd="http://www.w3.org/2001/XMLSchema"
        xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
  <soapenv:Header>
    <ns1:RequestHeader
         soapenv:actor="http://schemas.xmlsoap.org/soap/actor/next"
         soapenv:mustUnderstand="0"
         xmlns:ns1="https://www.google.com/apis/ads/publisher/v201403">
      <ns1:networkCode>123456</ns1:networkCode>
      <ns1:applicationName>DfpApi-Java-2.1.0-dfp_test</ns1:applicationName>
    </ns1:RequestHeader>
  </soapenv:Header>
  <soapenv:Body>
    <getAdUnitsByStatement xmlns="https://www.google.com/apis/ads/publisher/v201403">
      <filterStatement>
        <query>WHERE parentId IS NULL LIMIT 500</query>
      </filterStatement>
    </getAdUnitsByStatement>
  </soapenv:Body>
</soapenv:Envelope>

The corresponding response would look like :

 
<soap:Envelope xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/">
  <soap:Header>
    <ResponseHeader xmlns="https://www.google.com/apis/ads/publisher/v201403">
      <requestId>xxxxxxxxxxxxxxxxxxxx</requestId>
      <responseTime>1063</responseTime>
    </ResponseHeader>
  </soap:Header>
  <soap:Body>
    <getAdUnitsByStatementResponse xmlns="https://www.google.com/apis/ads/publisher/v201403">
      <rval>
        <totalResultSetSize>1</totalResultSetSize>
        <startIndex>0</startIndex>
        <results>
          <id>2372</id>
          <name>RootAdUnit</name>
          <description></description>
          <targetWindow>TOP</targetWindow>
          <status>ACTIVE</status>
          <adUnitCode>1002372</adUnitCode>
          <inheritedAdSenseSettings>
            <value>
              <adSenseEnabled>true</adSenseEnabled>
              <borderColor>FFFFFF</borderColor>
              <titleColor>0000FF</titleColor>
              <backgroundColor>FFFFFF</backgroundColor>
              <textColor>000000</textColor>
              <urlColor>008000</urlColor>
              <adType>TEXT_AND_IMAGE</adType>
              <borderStyle>DEFAULT</borderStyle>
              <fontFamily>DEFAULT</fontFamily>
              <fontSize>DEFAULT</fontSize>
            </value>
          </inheritedAdSenseSettings>
        </results>
      </rval>
    </getAdUnitsByStatementResponse>
  </soap:Body>
</soap:Envelope>

Courtesy : https://developers.google.com/doubleclick-publishers/docs/soap_xml

The above is an example of Google's web service which provides Ad Units to the requester based on some filters.

Web Services provide an easy platform independent way to exchange information over the network.
The following picture shows the basic flow on how the Service Provider caters the request of the consumer.

Source: http://www.service-architecture.com

Following is an implementation of a SOAP client in C++ which calls the Web Service to get the stock quotes based on a symbol(company ticker).

The example uses gSoap library for SOAP encoding/decoding and Xerces library to extract the data from the SOAP response (XML).

I have used the web service URL http://www.webservicex.net/stockquote.asmx?WSDL

Resources:

gSOAP library (2.8.18) http://sourceforge.net/projects/gsoap2/files/
Xerces library (3.1.1) http://xerces.apache.org/mirrors.cgi#binary

Setup for Visual Studio 2005:

Unzip gSOAP library at any location (Lets say C:\tools , so the location will be C:\gsoap-2.8)
Download only the binary distribution of xerces xerces-c-3.1.1-x86-windows-vc-8.0.zip
Unzip the zip file at C:\ so that location becomes C:\xerces-c-3.1.1-x86-windows-vc-8.0
Create an empty Win32 Console Application project.
Add theses paths to the Additional Include Directories :
"C:\xerces-c-3.1.1-x86-windows-vc-8.0\include";"C:\gsoap-2.8\gsoap\";"C:\gsoap-2.8\gsoap\import"
Add these paths to Additional Library Directories :
"C:\xerces-c-3.1.1-x86-windows-vc-8.0\lib"
Add these libs to the dependency list:

Notice that since we are using a Debug configuration here, we added xerces-c_3D.lib. For Release configuration, use xerces-c_3.lib
Add this location to your environment Path variable C:\xerces-c-3.1.1-x86-windows-vc-8.0\bin or copy the xerces dlls (xerces-c_3_1.dll and xerces-c_3_1D.dll) into the output path of the project(i.e. same path where the exe of the project will be created). These will be present at the location C:\xerces-c-3.1.1-x86-windows-vc-8.0\bin
Open a command prompt and go to gSOAP win32 bin directory and run following commands :

wsdl2h.exe -o quote.h http://www.webservicex.net/stockquote.asmx?WSDL

This will generate quote.h which contains class definitions for the web service.
soapcpp2.exe /IC:\tools\gsoap_2.8.18\gsoap-2.8\gsoap\import quote.h
This generates following files :

StockQuoteSoap.GetQuote.req.xml
StockQuoteSoap.GetQuote.res.xml
StockQuoteSoap.nsmap
soapC.cpp
soapClient.cpp
soapClientLib.cpp
soapH.h
soapServer.cpp
soapServerLib.cpp
soapStub.h
Now add these generated files to the Visual Studio project created earlier :
soapH.h , soapC.cpp, soapClient.cpp, soapStub.h, quote.h

Also these add two additional files from C:\tools\gsoap_2.8.18\gsoap-2.8\gsoap to your project:
stdsoap2.cpp, stdsoap2.h
Now its time to create some files on our own :). Create these files in the project and copy the contents from the code below :

quote.cpp, parser.hpp, stock.hpp

SOAP Web Service client implementation(c++)


//quote.cpp
#include "soapH.h"    // include the generated proxy
#include <xercesc/sax/HandlerBase.hpp>
#include <xercesc/util/XMLString.hpp>
#include <xercesc/framework/MemBufInputSource.hpp>
#include <xercesc/util/OutOfMemoryException.hpp>
#include <xercesc/dom/DOM.hpp>
#include <xercesc/dom/DOMDocument.hpp>
#include <xercesc/dom/DOMDocumentType.hpp>
#include <xercesc/dom/DOMElement.hpp>
#include <xercesc/dom/DOMImplementation.hpp>
#include <xercesc/dom/DOMImplementationLS.hpp>
#include <xercesc/dom/DOMNodeIterator.hpp>
#include <xercesc/dom/DOMNodeList.hpp>
#include <xercesc/dom/DOMText.hpp>
#include <xercesc/parsers/XercesDOMParser.hpp>
#include <xercesc/util/XMLUni.hpp>
#include "parser.hpp"

XERCES_CPP_NAMESPACE_USE

GetXml::GetXml()
{
 try
 {
  XMLPlatformUtils::Initialize();  // Initialize Xerces infrastructure
 }
 catch( XMLException& e )
 {
  char* message = XMLString::transcode( e.getMessage() );
  std::cout << "XML toolkit initialization error: " << message << std::endl;
  XMLString::release( &message );
 }

 // Tags and attributes used in XML file.
 // Can't call transcode till after Xerces Initialize()
 TAG_root  = XMLString::transcode("StockQuotes");
 TAG_Stock = XMLString::transcode("Stock");
 TAG_Symbol = XMLString::transcode("Symbol");
 TAG_Last = XMLString::transcode("Last");
 TAG_Date = XMLString::transcode("Date");
 TAG_Time = XMLString::transcode("Time");
 TAG_Change = XMLString::transcode("Change");
 TAG_Open = XMLString::transcode("Open");
 TAG_High = XMLString::transcode("High");
 TAG_Low = XMLString::transcode("Low");
 TAG_Volume = XMLString::transcode("Volume");
 TAG_MktCap = XMLString::transcode("MktCap");
 TAG_PrevClose = XMLString::transcode("PreviousClose");
 TAG_PercentChange = XMLString::transcode("PercentageChange");
 TAG_AnnRange = XMLString::transcode("AnnRange");
 TAG_Earns = XMLString::transcode("Earns");
 TAG_PE = XMLString::transcode("P-E");
 TAG_Name = XMLString::transcode("Name");
 
 m_XmlParser = new XercesDOMParser;
 m_Stock = new Stock;
}

GetXml::~GetXml()
{
 // Free memory
 delete m_XmlParser;
 delete m_Stock;

 try
 {
  XMLString::release( &TAG_root );
 }
 catch( ... )
 {
  std::cout << "Unknown exception encountered in Destructor" << std::endl;
 }

 // Terminate Xerces
 try
 {
  XMLPlatformUtils::Terminate();  // Terminate after release of memory
 }
 catch( xercesc::XMLException& e )
 {
  char* message = xercesc::XMLString::transcode( e.getMessage() );

  std::cout << "XML toolkit teardown error: " << message << std::endl;
  XMLString::release( &message );
 }
}

void GetXml::readXml(std::string& xmlStr)
throw( std::runtime_error )
{
 // Configure DOM parser.
 m_XmlParser->setValidationScheme( XercesDOMParser::Val_Never );
 m_XmlParser->setDoNamespaces( false );
 m_XmlParser->setDoSchema( false );
 m_XmlParser->setLoadExternalDTD( false );

 try
 {
  xercesc_3_1::MemBufInputSource xmlBuf((const XMLByte*)xmlStr.c_str(), xmlStr.size(),
   "xmlBuf (in memory)");
  m_XmlParser->parse( xmlBuf );

  xercesc_3_1::DOMDocument* xmlDoc = m_XmlParser->getDocument();

  DOMElement* elementRoot = xmlDoc->getDocumentElement();
  if( !elementRoot ) throw(std::runtime_error( "Empty XML document" ));

  DOMNodeList*      children = elementRoot->getChildNodes();
  const  XMLSize_t nodeCount = children->getLength();

  // For all nodes, children of "StockQuotes" in the XML tree.

  for( XMLSize_t xx = 0; xx < nodeCount; ++xx )
  {
   DOMNode* currentNode = children->item(xx);
   if( currentNode->getNodeType() &&  // true is not NULL
    currentNode->getNodeType() == DOMNode::ELEMENT_NODE ) // is element 
   {
    // Found node which is an Element. Re-cast node as element
    DOMElement* currentElement
     = dynamic_cast< xercesc::DOMElement* >( currentNode );
    if( XMLString::equals(currentElement->getTagName(), TAG_Stock))
    {
     DOMNodeList*      children1 = currentElement->getChildNodes();
     const  XMLSize_t nodeCount1 = children1->getLength();
     for( XMLSize_t yy = 0; yy < nodeCount1; ++yy )
     {
      DOMNode* currentNode1 = children1->item(yy);
      if( currentNode1->getNodeType() &&  // true is not NULL
       currentNode1->getNodeType() == DOMNode::ELEMENT_NODE ) // is element 
      {
       // Found node which is an Element. Re-cast node as element
       DOMElement* currentElement1
        = dynamic_cast< xercesc::DOMElement* >( currentNode1 );
       std::cout<<XMLString::transcode(currentElement1->getTagName())<<": "
        <<XMLString::transcode(currentElement1->getTextContent())<<std::endl;

       std::string sym(XMLString::transcode(currentElement1->getTextContent()));

       if(XMLString::equals(currentElement1->getTagName(), TAG_Symbol))
       {
        m_Stock->SetSymbol(sym);
       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Last))
       {
        m_Stock->SetLast(sym);
       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Date))
       {
        m_Stock->SetDate(sym);
       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Time))
       {
        m_Stock->SetTime(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Change))
       {
        m_Stock->SetChange(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Open))
       {
        m_Stock->SetOpen(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_High))
       {
        m_Stock->SetHigh(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Low))
       {
        m_Stock->SetLow(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Volume))
       {
        m_Stock->SetVolume(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_MktCap))
       {
        m_Stock->SetMktCap(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_PrevClose))
       {
        m_Stock->SetPrevClose(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_PercentChange))
       {
        m_Stock->SetPercentChange(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_AnnRange))
       {
        m_Stock->SetAnnRange(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Earns))
       {
        m_Stock->SetEarns(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_PE))
       {
        m_Stock->SetPE(sym);

       }
       else if(XMLString::equals(currentElement1->getTagName(), TAG_Name))
       {
        m_Stock->SetName(sym);
       }
      }
     }
    }
   }
  }

  std::cout<<m_Stock->ToString();
 }
 catch( xercesc::XMLException& e )
 {
  char* message = xercesc::XMLString::transcode( e.getMessage() );
  std::ostringstream errBuf;
  errBuf << "Error parsing file: " << message << std::flush;
  XMLString::release( &message );
 }
}

int main(int argc, char** argv){
 struct soap *soap = soap_new(); 
 struct _ns1__GetQuote sym;
 struct _ns1__GetQuoteResponse quote;
 GetXml xml;
 std::string response="";
 std::string str(argv[1]);
 sym.symbol = &str;

 soap_init(soap);

 //Call the web service
 if (soap_call___ns1__GetQuote(soap, NULL, NULL, &sym, quote) == SOAP_OK) {
  //std::cout<<"Symbol: "<<*(sym.symbol)<<std::endl<<" Quote: "<<*(quote.GetQuoteResult)<<std::endl;
  response = *(quote.GetQuoteResult);
  free (quote.GetQuoteResult);
 }
 else {
  std::cout<<"Error in execution of GetQuote:: "<<soap->buf<<std::endl;
  return(0);
 }

 //Parse the SOAP response 
 xml.readXml(response);
 return 0;
}

// Copied from StockQuoteSoap.nsmap file
SOAP_NMAC struct Namespace namespaces[] =
{
 {"SOAP-ENV", "http://www.w3.org/2003/05/soap-envelope", "http://schemas.xmlsoap.org/soap/envelope/", NULL},
 {"SOAP-ENC", "http://www.w3.org/2003/05/soap-encoding", "http://schemas.xmlsoap.org/soap/encoding/", NULL},
 {"xsi", "http://www.w3.org/2001/XMLSchema-instance", "http://www.w3.org/*/XMLSchema-instance", NULL},
 {"xsd", "http://www.w3.org/2001/XMLSchema", "http://www.w3.org/*/XMLSchema", NULL},
 {"ns1", "http://www.webserviceX.NET/", NULL, NULL},
 {NULL, NULL, NULL, NULL}
};


//stock.hpp
#include <sstream>
class Stock
{
 std::string symbol_;
 std::string last_;
 std::string date_;
 std::string time_;
 std::string change_;
 std::string open_;
 std::string high_;
 std::string low_;
 std::string volume_;
 std::string mktcap_;
 std::string previousclose_;
 std::string percentagechange_;
 std::string annrange_;
 std::string earns_;
 std::string p_e_;
 std::string name_;

public:
 Stock() {}
 Stock(std::string symbol) {symbol_ = symbol;}

 void SetSymbol(std::string symbol) {symbol_ = symbol;}
 void SetLast(std::string last) {last_ = last;}
 void SetDate(std::string date) {date_ = date;}
 void SetTime(std::string time) {time_ = time;}
 void SetChange(std::string change) {change_ = change;}
 void SetOpen(std::string open) {open_ = open;}
 void SetHigh(std::string high) {high_ = high;}
 void SetLow(std::string low) {low_ = low;}
 void SetVolume(std::string volume) {volume_ = volume;}
 void SetMktCap(std::string mktcap) {mktcap_ = mktcap;}
 void SetPrevClose(std::string previousclose) {previousclose_ = previousclose;}
 void SetPercentChange(std::string percentagechange) {percentagechange_ = percentagechange;}
 void SetAnnRange(std::string annrange) {annrange_ = annrange;}
 void SetEarns(std::string earns) {earns_ = earns;}
 void SetPE(std::string p_e) {p_e_ = p_e;}
 void SetName(std::string name) {name_ = name;}

 //ToString function overridden to display in short format  
 std::string ToString() const
 {
  std::stringstream sstr;
  sstr << "\'" << symbol_ << "\' Open: " << open_
   << ", Last: " << last_;
  return sstr.str();
 }
};


//parser.hpp
#include "stock.hpp"
class GetXml
{
public:
 GetXml();
 ~GetXml();

 //Function to read the XML string
 void readXml(std::string&) throw(std::runtime_error);


private:
 xercesc_3_1::XercesDOMParser *m_XmlParser; //DOM Parser pointer
 Stock *m_Stock;        //To save the returned data

 XMLCh* TAG_root;
 XMLCh* TAG_Stock;
 XMLCh* TAG_Symbol;
 XMLCh* TAG_Last;
 XMLCh* TAG_Date;
 XMLCh* TAG_Time;
 XMLCh* TAG_Change;
 XMLCh* TAG_Open;
 XMLCh* TAG_High;
 XMLCh* TAG_Low;
 XMLCh* TAG_Volume;
 XMLCh* TAG_MktCap;
 XMLCh* TAG_PrevClose;
 XMLCh* TAG_PercentChange;
 XMLCh* TAG_AnnRange;
 XMLCh* TAG_Earns;
 XMLCh* TAG_PE;
 XMLCh* TAG_Name;
};

Now the project is ready to compile. Use F7 to compile the solution.
After the binary is generated, run it like this :
<binary-name>.exe<space><Ticker-Name>

e.g. If project name was soap
soap.exe GOOG
This program is specific to the Stock Quote web service provided by http://www.webservicex.net/ . This program can be modified to use any web service. Depending upon the expected SOAP response, the result can be parsed accordingly. Then following files will be modified :

stock.hpp - Class which stores the data from SOAP response
parser.hpp - Class which parses the XML result from SOAP response

Builder Design Pattern Implementation in C++

noreply@blogger.com (Varun) — Tue, 01 Apr 2014 20:21:00 +0000

Sometimes an application gets too complicated and developing it becomes a pain. These applications contain complex objects which are made up from other objects from different classes. Now these objects may vary. So there has to be a process of building the complex objects so that there is scope of building different products using the same process.

That is when a creational design pattern called Builder comes into picture. It separates the details of construction process from its representation.

Now what in the world that line means actually ?

It means that the construction process is made so generic, that multiple products can be produced using the same process. e.g. construction workers. Different type of buildings can be built using the same workers and same common set of process.

Here is a class diagram of the design pattern.

Builder Design Pattern

There are 4 major components:

Director: It constructs an object using the Builder interface.
Builder : It specifies an abstract interface to build parts of a product.
Concrete Classes : Implements builder interface.
Product : The complex object which is created at the end.

Director object is created and Builder interface is used. It notifies the Builder to create each part of the product. Upon the request from Director, Builder adds parts to the product. Finally the product is returned by the Builder.

We have to take care of when to use the Builder Design Pattern. Few points come into mind :

When the object to be created is complex enough and can have multiple representations.
When the construction process can be broken down into multiple steps
When the process of creation of an object can be independent of the parts to be used.
When different products can have a common abstract class.

Now lets create a builder design pattern using an example.

Builder Example

In this example we create house as product. Now the house created may be different as per requirement of different people. It can be a lavish house with lots of amenities and expensive stuff. On the other hand, it could be a normal house with normal stuff.

The HouseBuilder class is the builder class which provides interface for creating the parts of the house.
The House class is the final product that we want to build
LavishHouse and NormalHouse are the concrete classes which implement the HouseBuilder interface.
Contractor is the director which constructs the house using the HouseBuilder interface.

Builder Design Pattern Implementation(C++)

 #include <iostream>

using namespace std;

/* Interface that will be returned as the product from builder */
class HousePlan{
public:
 virtual void setWindow(string window)=0;
 virtual void setDoor(string door)=0;
 virtual void setBathroom(string bathroom)=0;
 virtual void setKitchen(string kitchen)=0;
 virtual void setFloor(string floor)=0;
};

/* Concrete class for the HousePlan interface */
class House:public HousePlan{
private :
 string window, door, kitchen, bathroom, floor;

public:
 void setWindow(string window)
 {
  this->window = window;
 }

 void setDoor(string door)
 {
  this->door = door;
 }

 void setBathroom(string bathroom)
 {
  this->bathroom = bathroom;
 }

 void setKitchen(string kitchen)
 {
  this->kitchen = kitchen;
 }

 void setFloor(string floor)
 {
  this->floor = floor;
 }
};

/* Builder Class */
class HouseBuilder
{
public:
 /* Abstract functions to build parts */
 virtual void buildWindow()=0;
 virtual void buildDoor()=0;
 virtual void buildKitchen()=0;
 virtual void buildBathroom()=0;
 virtual void buildFloor()=0;
 /* The product is returned by this function */
 virtual House* getHouse()=0;
};

/* Concrete class for the builder interface */
class LavishHouse:public HouseBuilder{
private:
 House *house;
public:
 LavishHouse()
 {
  house = new House();
 }

 void buildWindow()
 {
  house->setWindow("French Window");
 }

 void buildDoor()
 {
  house->setDoor("Wooden Door");
 }

 void buildBathroom()
 {
  house->setBathroom("Modern Bathroom");
 }

 void buildKitchen()
 {
  house->setKitchen("Modular Kitchen");
 }

 void buildFloor()
 {
  house->setFloor("Wooden Floor");
 }

 House* getHouse()
 {
  return this->house;
 }
};

/* Another Concrete class for the builder interface */
class NormalHouse:public HouseBuilder{
private:
 House *house;
public:
 NormalHouse()
 {
  house = new House();
 }

 void buildWindow()
 {
  house->setWindow("Normal Window");
 }

 void buildDoor()
 {
  house->setDoor("Metal Door");
 }

 void buildBathroom()
 {
  house->setBathroom("Regular Bathroom");
 }

 void buildKitchen()
 {
  house->setKitchen("Regular Kitchen");
 }

 void buildFloor()
 {
  house->setFloor("Mosaic Floor");
 }

 House* getHouse()
 {
  return this->house;
 }
};

/* The Director. Constructs the house */
class Contractor
{
private:
 HouseBuilder *houseBuilder;

public:
 Contractor(HouseBuilder *houseBuilder)
 {
  this->houseBuilder = houseBuilder;
 }

 House *getHouse()
 {
  return houseBuilder->getHouse();
 }

 void buildHouse()
 {
  houseBuilder->buildWindow();
  houseBuilder->buildDoor();
  houseBuilder->buildBathroom();
  houseBuilder->buildKitchen();
  houseBuilder->buildFloor();
 }
};

/* Example on how to use the Builder design pattern */
int main()
{
 HouseBuilder *lavishHouseBldr = new LavishHouse();
 HouseBuilder *normalHouseBldr = new NormalHouse();

 Contractor *ctr1 = new Contractor(lavishHouseBldr);
 Contractor *ctr2 = new Contractor(normalHouseBldr);

 ctr1->buildHouse();
 House *house1 = ctr1->getHouse();
 cout<<"Constructed: "<<house1;

 ctr2->buildHouse();
 House *house2 = ctr2->getHouse();
 cout<<"Constructed: "<<house2;
}

Decorator Design Pattern Implementation in C++

noreply@blogger.com (Varun) — Sun, 29 Dec 2013 14:46:00 +0000

Do you need to extend the capabilities of your existing class instance at run-time? If the answer is yes then Decorator design pattern just provides the functionality you need.

When we have to change the capabilities of only a particular instance and not all the instances which will get created for a particular class, we have to use decorator design pattern.

This is achieved by creating a decorator class, which wraps the original class. The original class is sub-classed into two parts. One is the concrete class which is essentially the original class with only basic features. The other one is the Decorator base class. This decorator base class implements the same interface as the original class. In addition it wraps the original base class.

We can extend this Decorator base class to create multiple concrete decorator classes. Each of these concrete decorator classes implement their own methods and will call the base class's instance's method.

Now this looks complete babbling. Let's see what I mean actually.

Decorator Design Pattern

I know the above diagram looks overwhelming. So let's explain it in more simple language with much simpler example.

Lets prepare a subway burger. Shall we ;)
Now we all know that when we visit a Subway store, we have a variety of options to customize our Sub.
Assuming that we have chosen a foot-long already for the base bread, we start making our sandwich.

We can add cheese to the sandwich.
We can add vegetables to our Sub.
We can add mayonnaise,mustard, sweet onion etc .

Depending on our choices, the sandwich is prepared. And we are ready to eat it .. Aren't we :)

Now consider the bread(foot-long) as the Base Component Class. Over this component, we can place a Decorator Base Class SubDecorator and now the Concrete Decorators can be derived from this class.

CheeseDecorator, VegDecorator, SauceDecorator are concrete decorators which implement their own functions and have their own members in addition to the base class functions cost() and description().

And here comes the code:

Decorator Design Pattern Implementation (C++)

 #include <iostream>
#include <string>

//Uncomment the next line to enable debug logs
//#define DEBUG

std::string c(const std::string cls) {
    return "\n" + cls + " Constructor";
}
std::string d(const std::string cls) {
    return "\n" +cls + " Destructor";
}

/*Base component class*/
class Sandwich
{
public:
    virtual ~Sandwich() { }
    virtual double getCost()=0;
    virtual std::string getDesc()=0;
};

/*Concrete component class*/
class WheatBread:public Sandwich
{
public:
    WheatBread() {
#ifdef DEBUG
        std::cout<<c("WheatBread");
#endif
    }
    ~WheatBread() {
#ifdef DEBUG
        std::cout<<d("WheatBread");
#endif
    }
    std::string getDesc()
    {
        return "Wheat Bread";
    }

    double getCost()
    {
        return 2.0;
    }
};

/*Concrete component class*/
class WholeGrainBread:public Sandwich
{
public:
    WholeGrainBread() {
#ifdef DEBUG
        std::cout<<c("WholeGrainBread");
#endif
    }
    ~WholeGrainBread() {
#ifdef DEBUG
        std::cout<<d("WholeGrainBread");
#endif
    }
    std::string getDesc()
    {
        return "WholeGrain Bread";
    }

    double getCost()
    {
        return 3.0;
    }
};

/*Concrete component class*/
class ItalianBread:public Sandwich
{
public:
    ItalianBread() {
#ifdef DEBUG
        std::cout<<c("ItalianBread");
#endif
    }
    ~ItalianBread() {
#ifdef DEBUG
        std::cout<<d("ItalianBread");
#endif
    }
    std::string getDesc()
    {
        return "Italian Bread";
    }

    double getCost()
    {
        return 2.5;
    }
};

/*Decorator Base class*/
class SubDecorator: public Sandwich
{
    Sandwich *sandwich;
public:
    SubDecorator(Sandwich *sandwichRef)
    {
#ifdef DEBUG
        std::cout<<c("SubDecorator");
#endif
        sandwich = sandwichRef;
    }

    ~SubDecorator() {
#ifdef DEBUG
        std::cout<<d("SubDecorator");
#endif
        delete sandwich;
    }
    double getCost()
    {
        return sandwich->getCost();
    }
    std::string getDesc()
    {
        return sandwich->getDesc();
    }
};

/*Decorator concrete class*/
class CheeseDecorator:public SubDecorator
{
private:
    std::string cheese_desc()
    {
        return " + Cheese";
    }

    double cheese_cost;

public:
    CheeseDecorator(Sandwich *sandwich):SubDecorator(sandwich)
    {
#ifdef DEBUG
        std::cout<<c("CheeseDecorator");
#endif
        cheese_cost = 3.0;
    }

    ~CheeseDecorator() {
#ifdef DEBUG
        std::cout<<d("CheeseDecorator");
#endif
    }
    std::string getDesc()
    {
        return SubDecorator::getDesc().append(cheese_desc());
    }

    double getCost()
    {
        return SubDecorator::getCost() + cheese_cost;
    }
};

/*Decorator concrete class*/
class VegDecorator:public SubDecorator
{
private:
    std::string veg_desc()
    {
        return " + Veg";
    }

    double veg_cost;

public:
    VegDecorator(Sandwich *sandwich):SubDecorator(sandwich)
    {
#ifdef DEBUG
        std::cout<<c("VegDecorator");
#endif
        veg_cost = 2.0;
    }

    ~VegDecorator() {
#ifdef DEBUG
        std::cout<<d("VegDecorator");
#endif
    }
    std::string getDesc()
    {
        return SubDecorator::getDesc().append(veg_desc());
    }

    double getCost()
    {
        return SubDecorator::getCost() + veg_cost;
    }
};

/*Decorator concrete class*/
class SauceDecorator:public SubDecorator
{
private:
    std::string sauce_desc()
    {
        return " + Sauce";
    }

    double sauce_cost;

public:
    SauceDecorator(Sandwich *sandwich):SubDecorator(sandwich)
    {
#ifdef DEBUG
        std::cout<<c("SauceDecorator");
#endif
        sauce_cost = .5;
    }

    ~SauceDecorator() {
#ifdef DEBUG
        std::cout<<d("SauceDecorator");
#endif
    }
    std::string getDesc()
    {
        return SubDecorator::getDesc().append(sauce_desc());
    }

    double getCost()
    {
        return SubDecorator::getCost() + sauce_cost;
    }
};

int main()
{
    Sandwich *sandwich = new CheeseDecorator(new WheatBread());
    sandwich = new VegDecorator(sandwich);
    sandwich = new SauceDecorator(new SubDecorator(sandwich));
    std::cout<<"\nYour sandwich is "<<sandwich->getDesc()<<" and costs $"<<sandwich->getCost();
    delete sandwich;
}

Factory Method Design Pattern implementation in C++

noreply@blogger.com (Varun) — Sun, 29 Dec 2013 11:08:00 +0000

What does a factory mean ? It is something which creates/manufactures some products.

Same is the job of factory design pattern. It is responsible for instantiation/creation of objects. But wait, isn't that something what constructors do ? Yes call to constructor indeed creates the object and that's exactly what a factory method does but with an additional feature of option of choosing between different constructors based on some logic.

Factory methods decide logically what constructor to call. So, instead of directly calling the constructor for a class, we call a factory method to get the object. There can be multiple derived classes from a base class. The factory method instantiates the appropriate sub-class based on the arguments passed to it and returns the base class type. This base class object can be used to access the derived class members/methods.

Blah, blah, blah... Let's get down to business and understand what it actually is and what it does.

A basic structure:

Basic structure of factory design pattern

Now let's explain it with a simple example:

Assume that we are an online Music Store . We every kind of music be it Rock, Classical, Jazz, Reggae, Techno and what not. Of course, to organize these we need categories based on different genres. Lets design this model using factory design pattern. Our base class is what we do. We provide music, so say "Music" is our base class.

Now Music can be classified into multiple categories . We for the time being assume only three.

Rock
Pop
Reggae

The class structure would be something like this:

Class Structure

Here Rock, Pop and Reggae are the derived classes from base class Music.

We create a factory pattern for this class structure in which we provide a factory method getMusic(genre_e genre) to the user. Using this method, one can instantiate the object of any subclass by choosing the genre.

Here genre is the logic based on which any particular subclass is instantiated. Advantage of this pattern is that outer world need not instantiate specific objects using the different sub-class constructors. It is being masked in the implementation of factory method.

Factory pattern for the class Music

Moreover if any new genre needs to be added, that can be done easily just by adding a new case in Factory method.

And now the code :

Factory Method Design Pattern implementation (C++)

 #include <iostream>
using namespace std;

enum genre_e{ROCK,POP, REGGAE, INVALID};

/*Base Class*/
class Music {
public:
 virtual void song() = 0;
};

/*Derived class Rock from Music*/
class Rock: public Music
{
public:
 void song()
 {
  cout<<"Nirvana: Smells like a teen spirit\n";
 }
};

/*Derived class Pop from Music*/
class Pop: public Music
{
public:
 void song()
 {
  cout<<"Michael Jackson: Billie Jean\n";
 }
};

/*Derived class Reggae from Music*/
class Reggae: public Music
{
public:
 void song()
 {
  cout<<"Bob Marley: No woman, No cry\n";
 }
};

/*Factory Class*/
class MusicFactory
{
public:
 /*Factory Method*/
 Music *getMusic(genre_e genre)
 {
  Music *music = NULL;

  /*Logic based on Genre*/
  switch(genre)
  {
  case ROCK:
   music = new Rock();
   break;
  case POP:
   music = new Pop();
   break;
  case REGGAE:
   music = new Reggae();
   break;
  default:
   music = NULL;
   break;
  }
  return music;
 }
};

int main()
{
 /*Create factory*/
 MusicFactory *musicFactory = new MusicFactory();

 /*Factory instantiating an object of type ROCK*/
 Music *music = musicFactory->getMusic(ROCK);

 cout<<"Song: ";
 if(music)
  music->song();
 else
  cout<<"Wrong selection dude/dudette !!";
}

Graph Implementation in C

noreply@blogger.com (Varun) — Sun, 29 Sep 2013 12:01:00 +0000

A graph is a collection of nodes and edges. These nodes are connected by links(edges).
These edges may be directed or undirected. Moreover these edges can have weights associated with them

So edges can be categorized as :

Directed, weighted edges
Directed, unweighted edges
Undirected, weighted edges
Undirected, unweighted edges

Uses of graphs

Graphs are extremely useful. Look everywhere and one can easily find use of graphs. Listed below are a few of the vast set of practical uses of graphs.

Delhi Metro Rail Map

Each station is a vertex, the distance in between is a weighted edge.

A Maze

Each corner is a vertex, Line between two corners is and edge.

A tournament fixture
Courtesy: http://www.squadtd.com/

Each team is a vertex, match between the teams is an edge.

Kind of graphs

There are numerous classifications and types of graphs available. I have collected a few of those types from various sources and organized a list of types of graphs:

Undirected Graphs

Undirected Graph

Characteristics:

Order of vertices doesn't matter
1-2 is same as 2-1

Directed Graphs

Directed Graph

Characteristics:

Order of vertices does matter
1-2 is not same as 2-1

Vertex labeled Graphs.

Vertex Labeled Graph

Characteristics:

Each vertex contains additional information. e.g {2,orange}, {4,green}

Cyclic Graphs.

Cyclic Graph

Characteristics:

Graph contains at least one cycle.

Edge labeled Graphs.

Edge Labeled Graph

Characteristics:

Edge has labels e.g an edge in the above graph will be represented as {orange,green,{blue,cyan}}

Weighted Graphs.

Weighted Graph

Characteristics:

Each edge has some weight associated with it.

Directed Acyclic Graphs.

Direct Acyclic Graph(DAG)

Characteristics:

Graph has no cycles.

Disconnected Graphs

Disconnected Graph

Characteristics:

Vertices are disconnected

Mixed graph

Mixed Graph

Characteristics:

Some edges may be directed and some may be undirected

Multigraph

Characteristics:

Multiple edges (and sometimes loops) are allowed

Quiver

Characteristics:

Directed graph which may have more than one arrow from a given source to a given target. A quiver may also have directed loops in it.

Representation of graphs:

Fig. 1: An undirected graph

Fig 2: A directed graph

In order to use Graphs programatically , they need to be somehow represented in code. Following are the most widely used methods of representing a graph.

Adjacency Matrix :

For N vertices an adjacency matrix is an NxN array A such that
A[i][j] = 1 if there is an edge E(i,j)
= 0 otherwise

For an undirected graph, A[i][j] = A[j][i]

For weighted graphs,
A[i][j] = weight of the edge, if there is an edge E(i,j)
= a constant representing no edge (e.g a very large or very small value)

For Fig 1, the adjacency matrix would be

The adjacency matrix for directed graph in Fig 2 would be:

Adjacency List :

Adjacency matrix representation consume a lot of memory (O[N²]). If the graph is complete or almost complete(i.e. contains most of the edges between the vertices), then this representation is good to use. But if there are very few edges as compared to number of vertices, it will unnecessarily consume extra space. Adjacency list can handle this situation very optimally.

Every vertex has a linked list of the vertices it is connected with.

Adjacency list for Fig 1 would be:

Adjacency list for Fig 2 would be:

Following is code snippet to implement graphs in C using adjacency list.

/*graph.h*/
#ifndef _GRAPH_H_
#define _GRAPH_H_

typedef enum {UNDIRECTED=0,DIRECTED} graph_type_e;

/* Adjacency list node*/
typedef struct adjlist_node
{
    int vertex;                /*Index to adjacency list array*/
    struct adjlist_node *next; /*Pointer to the next node*/
}adjlist_node_t, *adjlist_node_p;

/* Adjacency list */
typedef struct adjlist
{
    int num_members;           /*number of members in the list (for future use)*/
    adjlist_node_t *head;      /*head of the adjacency linked list*/
}adjlist_t, *adjlist_p;

/* Graph structure. A graph is an array of adjacency lists.
   Size of array will be number of vertices in graph*/
typedef struct graph
{
    graph_type_e type;        /*Directed or undirected graph */
    int num_vertices;         /*Number of vertices*/
    adjlist_p adjListArr;     /*Adjacency lists' array*/
}graph_t, *graph_p;

/* Exit function to handle fatal errors*/
__inline void err_exit(char* msg)
{
    printf("[Fatal Error]: %s \nExiting...\n", msg);
    exit(1);
}

#endif

/*graph.c*/
#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

/* Function to create an adjacency list node*/
adjlist_node_p createNode(int v)
{
    adjlist_node_p newNode = (adjlist_node_p)malloc(sizeof(adjlist_node_t));
    if(!newNode)
        err_exit("Unable to allocate memory for new node");

    newNode->vertex = v;
    newNode->next = NULL;

    return newNode;
}

/* Function to create a graph with n vertices; Creates both directed and undirected graphs*/
graph_p createGraph(int n, graph_type_e type)
{
    int i;
    graph_p graph = (graph_p)malloc(sizeof(graph_t));
    if(!graph)
        err_exit("Unable to allocate memory for graph");
    graph->num_vertices = n;
    graph->type = type;

    /* Create an array of adjacency lists*/
    graph->adjListArr = (adjlist_p)malloc(n * sizeof(adjlist_t));
    if(!graph->adjListArr)
        err_exit("Unable to allocate memory for adjacency list array");

    for(i = 0; i < n; i++)
    {
        graph->adjListArr[i].head = NULL;
        graph->adjListArr[i].num_members = 0;
    }

    return graph;
}

/*Destroys the graph*/
void destroyGraph(graph_p graph)
{
    if(graph)
    {
        if(graph->adjListArr)
        {
            int v;
            /*Free up the nodes*/
            for (v = 0; v < graph->num_vertices; v++)
            {
                adjlist_node_p adjListPtr = graph->adjListArr[v].head;
                while (adjListPtr)
                {
                    adjlist_node_p tmp = adjListPtr;
                    adjListPtr = adjListPtr->next;
                    free(tmp);
                }
            }
            /*Free the adjacency list array*/
            free(graph->adjListArr);
        }
        /*Free the graph*/
        free(graph);
    }
}

/* Adds an edge to a graph*/
void addEdge(graph_t *graph, int src, int dest)
{
    /* Add an edge from src to dst in the adjacency list*/
    adjlist_node_p newNode = createNode(dest);
    newNode->next = graph->adjListArr[src].head;
    graph->adjListArr[src].head = newNode;
    graph->adjListArr[src].num_members++;

    if(graph->type == UNDIRECTED)
    {
        /* Add an edge from dest to src also*/
        newNode = createNode(src);
        newNode->next = graph->adjListArr[dest].head;
        graph->adjListArr[dest].head = newNode;
        graph->adjListArr[dest].num_members++;
    }
}

/* Function to print the adjacency list of graph*/
void displayGraph(graph_p graph)
{
    int i;
    for (i = 0; i < graph->num_vertices; i++)
    {
        adjlist_node_p adjListPtr = graph->adjListArr[i].head;
        printf("\n%d: ", i);
        while (adjListPtr)
        {
            printf("%d->", adjListPtr->vertex);
            adjListPtr = adjListPtr->next;
        }
        printf("NULL\n");
    }
}

int main()
{
    graph_p undir_graph = createGraph(5, UNDIRECTED);
    graph_p dir_graph = createGraph(5, DIRECTED);
    addEdge(undir_graph, 0, 1);
    addEdge(undir_graph, 0, 4);
    addEdge(undir_graph, 1, 2);
    addEdge(undir_graph, 1, 3);
    addEdge(undir_graph, 1, 4);
    addEdge(undir_graph, 2, 3);
    addEdge(undir_graph, 3, 4);

    addEdge(dir_graph, 0, 1);
    addEdge(dir_graph, 0, 4);
    addEdge(dir_graph, 1, 2);
    addEdge(dir_graph, 1, 3);
    addEdge(dir_graph, 1, 4);
    addEdge(dir_graph, 2, 3);
    addEdge(dir_graph, 3, 4);

    printf("\nUNDIRECTED GRAPH");
    displayGraph(undir_graph);
    destroyGraph(undir_graph);

    printf("\nDIRECTED GRAPH");
    displayGraph(dir_graph);
    destroyGraph(dir_graph);

    return 0;
}

Sources:
http://en.wikipedia.org/wiki/Graph_(mathematics)
http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/Graphs.html
http://msdn.microsoft.com/en-us/library/ms379574(v=vs.80).aspx

Trie implementation in C

noreply@blogger.com (Anonymous) — Thu, 08 Nov 2012 14:01:00 +0000

To implement the kind of storage which stores strings as the search keys , there is a need to have special data structures which can store the strings efficiently and the searching of data based on the string keys is easier, efficient and faster. One such data structure is a tree based implementation called Trie.

Trie is a data structure which can be used to implement a dictionary kind of application. It provides all the functionality to insert a string, search a string and delete a string from the dictionary. The insertion and deletion operation takes O(n) time where n is the length of the string to be deleted or inserted.

Some of the application of tries involve web based search engines, URL completion in autocomplete feature, Spell checker etc.

Structure of Trie(Specific to this implementation):

The trie implemented here consists of nodes. Each node has these fields:

Key - Part of the string to be serached,inserted or deleted.
Value - The value associated with a string (e.g In a dictionary it could be the meaning of the word which we are searching)
Neighbour node address - It consists of the address of the neighbouring node at the same level.
Previous neighbour address - It consists of the address of the previous node at the same level.
Children node address - It consists of the address of the child nodes of the current node.
Parent node address - It consists of the address of the parent node of the current node.

The additional nodes like Parent and Previous nodes are added to this implementation for making the search, and deletions easier.

Here is a diagrammatical view of a trie nodes I have used in this implementation. The field key is not represented in the diagram due to symmetry purposes.

Let us consider an example to understand tries in detail.

Suppose we have to implement a database for the HR department of an organisation in which we have to store an employee's name and their ages. There is an assumption for this example that there each employee's name is unique.So there is a strange policy in this organisation that any new employee which has a name that already exists in the organisation, it would not hire that new employee.

Let's use this hypothetical example just to understand how tries work.

Consider we have a new employee named Andrew with age 36. Lets populate our trie for "andrew".

Now add "tina".

Add "argo".

Add "tim".

Add "t".

Add "amy".

Add "aramis".

This is the complete Trie with all the entries. Now let us try deleting the names. I am not capturing the trivial cases.

Lets try deleting Argo.

Delete Tina

Delete Andrew

There is also a video from IIT Delhi which explains the tries. Tries Explained.
The implementation for this Trie is given below. Please provide your suggestions to further improve the implementation.

/*trie.h*/
typedef int trieVal_t;

typedef struct trieNode {
    char key;
    trieVal_t value;
    struct trieNode *next;
    struct trieNode *prev;
    struct trieNode *children;
    struct trieNode *parent;
} trieNode_t;

void TrieCreate(trieNode_t **root);
trieNode_t* TrieSearch(trieNode_t *root, const char *key);
void TrieAdd(trieNode_t **root, char *key, int data);
void TrieRemove(trieNode_t **root, char *key);
void TrieDestroy( trieNode_t* root );

/*trie.c*/
#include <stdio.h>
#include "trie.h"
#include <stdlib.h>

trieNode_t *TrieCreateNode(char key, int data);

void TrieCreate(trieNode_t **root)
{
 *root = TrieCreateNode('\0', 0xffffffff);
}

trieNode_t *TrieCreateNode(char key, int data)
{
 trieNode_t *node = NULL;
 node = (trieNode_t *)malloc(sizeof(trieNode_t));

 if(NULL == node)
 {
  printf("Malloc failed\n");
  return node;
 }

 node->key = key;
 node->next = NULL;
 node->children = NULL;
 node->value = data;
 node->parent= NULL;
 node->prev= NULL;
 return node;
}

void TrieAdd(trieNode_t **root, char *key, int data)
{
 trieNode_t *pTrav = NULL;

 if(NULL == *root)
 {
  printf("NULL tree\n");
  return;
 }
#ifdef DEBUG
 printf("\nInserting key %s: \n",key);
#endif
 pTrav = (*root)->children;



 if(pTrav == NULL)
 {
  /*First Node*/
  for(pTrav = *root; *key; pTrav = pTrav->children)
  {
   pTrav->children = TrieCreateNode(*key, 0xffffffff);
   pTrav->children->parent = pTrav;
#ifdef DEBUG
   printf("Inserting: [%c]\n",pTrav->children->key);
#endif
   key++;
  }

  pTrav->children = TrieCreateNode('\0', data);
  pTrav->children->parent = pTrav;
#ifdef DEBUG
  printf("Inserting: [%c]\n",pTrav->children->key);
#endif
  return;
 }

 if(TrieSearch(pTrav, key))
 {
  printf("Duplicate!\n");
  return;
 }

 while(*key != '\0')
 {
  if(*key == pTrav->key)
  {
   key++;
#ifdef DEBUG
   printf("Traversing child: [%c]\n",pTrav->children->key);
#endif
   pTrav = pTrav->children;
  }
  else
   break;
 }

 while(pTrav->next)
 {
  if(*key == pTrav->next->key)
  {
   key++;
   TrieAdd(&(pTrav->next), key, data);
   return;
  }
  pTrav = pTrav->next;
 }

 if(*key)
 {
  pTrav->next = TrieCreateNode(*key, 0xffffffff);
 }
 else
 {
  pTrav->next = TrieCreateNode(*key, data);
 }

 pTrav->next->parent = pTrav->parent;
 pTrav->next->prev = pTrav;

#ifdef DEBUG
 printf("Inserting [%c] as neighbour of [%c] \n",pTrav->next->key, pTrav->key);
#endif

 if(!(*key))
  return;

 key++;

 for(pTrav = pTrav->next; *key; pTrav = pTrav->children)
 {
  pTrav->children = TrieCreateNode(*key, 0xffffffff);
  pTrav->children->parent = pTrav;
#ifdef DEBUG
  printf("Inserting: [%c]\n",pTrav->children->key);
#endif
  key++;
 }

 pTrav->children = TrieCreateNode('\0', data);
 pTrav->children->parent = pTrav;
#ifdef DEBUG
 printf("Inserting: [%c]\n",pTrav->children->key);
#endif
 return;
}

trieNode_t* TrieSearch(trieNode_t *root, const char *key)
{
 trieNode_t *level = root;
 trieNode_t *pPtr = NULL;

 int lvl=0;
 while(1)
 {
  trieNode_t *found = NULL;
  trieNode_t *curr;

  for (curr = level; curr != NULL; curr = curr->next)
  {
   if (curr->key == *key)
   {
    found = curr;
    lvl++;
    break;
   }
  }

  if (found == NULL)
   return NULL;

  if (*key == '\0')
  {
   pPtr = curr;
   return pPtr;
  }

  level = found->children;
  key++;
 }
}

void TrieRemove(trieNode_t **root, char *key)
{
 trieNode_t *tPtr = NULL;
 trieNode_t *tmp = NULL;

 if(NULL == *root || NULL == key)
  return;

 tPtr = TrieSearch((*root)->children, key);

 if(NULL == tPtr)
 {
  printf("Key [%s] not found in trie\n", key);
  return;
 }

#ifdef DEBUG
 printf("Deleting key [%s] from trie\n", key);
#endif

 while(1)
 {
  if( tPtr->prev && tPtr->next)
  {
   tmp = tPtr;
   tPtr->next->prev = tPtr->prev;
   tPtr->prev->next = tPtr->next;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
   break;
  }
  else if(tPtr->prev && !(tPtr->next))
  {
   tmp = tPtr;
   tPtr->prev->next = NULL;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
   break;
  }
  else if(!(tPtr->prev) && tPtr->next)
  {
   tmp = tPtr;
   tPtr->parent->children = tPtr->next;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
   break;
  }
  else
  {
   tmp = tPtr;
   tPtr = tPtr->parent;
   tPtr->children = NULL;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
 }

#ifdef DEBUG
 printf("Deleted key [%s] from trie\n", key);
#endif
}


void TrieDestroy( trieNode_t* root )
{
 trieNode_t *tPtr = root;
 trieNode_t *tmp = root;

    while(tPtr)
 {
  while(tPtr->children)
   tPtr = tPtr->children;

  if( tPtr->prev && tPtr->next)
  {
   tmp = tPtr;
   tPtr->next->prev = tPtr->prev;
   tPtr->prev->next = tPtr->next;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
  else if(tPtr->prev && !(tPtr->next))
  {
   tmp = tPtr;
   tPtr->prev->next = NULL;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
  else if(!(tPtr->prev) && tPtr->next)
  {
   tmp = tPtr;
   tPtr->parent->children = tPtr->next;
   tPtr->next->prev = NULL;
   tPtr = tPtr->next;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
  else
  {
   tmp = tPtr;
   if(tPtr->parent == NULL)
   {
    /*Root*/
    free(tmp);
    return;
   }
   tPtr = tPtr->parent;
   tPtr->children = NULL;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
 }

}

/*triedriver.c*/
/*
 * To Compile : gcc -o trie trie.c triedriver.c
 * To run: ./trie
 */
#include <stdio.h>
#include <stdlib.h>
#include "trie.h"

int main()
{
    trieNode_t *root;
    printf("Trie Example\n");
    
    /*Create a trie*/
    TrieCreate(&root);
    
    TrieAdd(&root, "andrew", 1);
    TrieAdd(&root, "tina", 2);
    TrieAdd(&root, "argo", 3);
    TrieAdd(&root, "timor", 5);
    TrieRemove(&root, "tim");
    TrieAdd(&root, "tim", 6);
    TrieRemove(&root, "tim");
    TrieAdd(&root, "ti", 6);
    TrieAdd(&root, "amy", 7);
    TrieAdd(&root, "aramis", 8);

    /*Destroy the trie*/
    TrieDestroy(root);
}

In order to print the debug messages, use -DDEBUG while compiling with gcc:

gcc -o trie trie.c triedriver.c -DDEBUG

Abstract Binary Search Tree Implementation in C

noreply@blogger.com (Varun) — Wed, 31 Oct 2012 14:16:00 +0000

There are several ways to store data using different data structures like Array, Linked Lists , Trees, Graphs, Hashmaps etc. The choice of the data structure depends on the application which extracts that data. On searching the web , one can easily find out which data structure is required for their application. Binary Search Tree is one such data structure which is generally used for storing data.

A binary search tree consists of members called as nodes which have the data embedded in them. Generally, a BST node contains address fields and data field. The structure of a BST is something like this :

Each node can have a left subtree and right subtree which may or may not have any nodes.

Binary Search tree has some properties which identifies it :

The left subtree members have a value which is always less than the value at the root node
The right subtree members have a value which is always greater than the value at the root node
Both the subtrees must be also a BST.

The implementation provided in this post uses an abstract data type (void). To use this implementation as it is, one must implement these two functions

Comparison Function - This function compares the data between two nodes. This function must return -1, 0 or 1 only. The signature for this function is int <function-name> (void * data1, void * data2).

Function should return 1 when data1 is greater than data2.
Function should return -1 when data1 is lesser than data2.
Function should return 0 when data1 is equal to data2.

Display Function - This function is used for display purposes only. It displays the node data.

A sample implementation of these two functions is presented in the driver example(bstdriver.c) for the BST. This sample implementation uses int type as data.

 
/*bst.h*/
typedef struct bstNode
{
    struct bstNode *left;       /*Left Child*/
    struct bstNode *right;      /*Right Child*/
    struct bstNode *parent;     /*Parent Child*/
    void *data;                 /*Data*/
}BSTNode;

void BSTDestroy(BSTNode *root);
void BSTInsert(BSTNode **root, void *data, int (*cmp_fn)(void *, void *));
void BSTDelete(BSTNode **root, void *data, int (*cmp_fn)(void *, void *));
BSTNode* BSTSearch(BSTNode *root, void *data, int (*cmp_fn)(void *, void *));
void BSTDisplay(BSTNode *root, void (*display_fn)(BSTNode *));

 
/*bst.c*/
#include <stdio.h>
#include <stdlib.h>

#include "bst.h"

/* @brief Function to determine if a child is a left child or right child in a BST
 * @param data Pointer to the data to be used
 * @return LEFT - if left child
 *         RIGHT - if right child
 */
static inline const char* BSTFindChildLoc(BSTNode *parent, BSTNode *child)
{
    return (((parent->left)==(child))?"LEFT":"RIGHT");
}

/* @brief Function to swap data between two nodes in a BST
 * @param data Pointer to the data to be used
 * @return void
 */
static inline void BSTSwapNodeData(BSTNode **node1, BSTNode **node2 )
{
    void *tmp;
    tmp = (*node1)->data;
    (*node1)->data = (*node2)->data;
    (*node2)->data = tmp;
}

/* @brief Function to create a node in a BST
 * @param data Pointer to the data to be used
 * @return Address of the node created
 */
BSTNode* BSTCreateNode(void *data)
{
    /*Allocate memory*/
    BSTNode* node= (BSTNode*)malloc(sizeof(BSTNode));

    if(NULL == node)
    {
        printf("Error: Memory Allocation could not be completed\n");
        return NULL;
    }

    /*Initialize links*/
    node->left = NULL;
    node->right= NULL;
    node->parent= NULL;
    node->data = data;

    printf("Allocated Node with address %p\n", node);
    return node;
}

/* @brief Function to destroy all nodes in a BST
 * @param root Pointer to the root of the BST
 * @return void
 */
void BSTDestroy(BSTNode *root)
{
    if(root)
    {
        /*Traverse down the left subtree*/
        if(root->left)
            BSTDestroy(root->left);
        /*Traverse down the right subtree*/
        if(root->right)
            BSTDestroy(root->right);
        /*Free the memory*/
        free(root);
        printf("DeAllocated Node with address %p\n", root);
    }
}

/* @brief Function to insert a node in a BST
 * @param root Pointer to pointer to the root of the BST
 * @param data Pointer to the data to be inserted
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return void
 */
void BSTInsert(BSTNode **root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *tmp = NULL;
    BSTNode *ptr = NULL;

    if(NULL == root)
    {
        printf("Error: Null root\n");
        return;
    }


    if(!(*root))
    {
        /*Create a node*/
        tmp = BSTCreateNode(data);

        if(NULL == tmp)
        {
            printf("Error: Node insertion failed\n");
            return;
        }

        /*Root Node*/
        *root = tmp;
        return;
    }

    ptr = *root;

    /*If data is greater than the current node's data*/
    if(cmp_fn(data,ptr->data) == 1)
    {
        /*data > ptr->data : Insert to right*/
        if(ptr->right == NULL)
        {
            /*Create a node*/
            tmp = BSTCreateNode(data);

            if(NULL == tmp)
            {
                printf("Error: Node insertion failed\n");
                return;
            }

            tmp->parent = ptr;
            ptr->right = tmp;
            return;
        }
        else
        {
            BSTInsert(&(ptr->right), data, cmp_fn);
        }
    }
    /*If data is lesser than the current node's data*/
    else if(cmp_fn(data,ptr->data) == -1)
    {
        /*data > ptr->data : Insert to right*/
        if(ptr->left == NULL)
        {
            tmp = BSTCreateNode(data);

            if(NULL == tmp)
            {
                printf("Error: Node insertion failed\n");
                return;
            }

            tmp->parent = ptr;
            ptr->left = tmp;
            return;
        }
        else
        {
            BSTInsert(&(ptr->left), data, cmp_fn);
        }
    }
    /*If data is equal to the current node's data*/
    else
        printf("Error: Duplicate\n");
}

/* @brief Function to find the minimum valued node in the left subtree of a node
 * @param node Pointer to the node whose min valued child in left subtree has to be found
 * @return Address of the minimum valued node in the left subtree
 */
static BSTNode* BSTMinVal(BSTNode* node)
{
    BSTNode* current = node;

  /*Go to the leftmost member of the tree */
  while (current->left != NULL)
  {
    current = current->left;
  }
  return current;
}

/* @brief Function to find the Inorder successor of a node in a BST
 * @param node Pointer to the node whose inorder successor has to be found
 * @return Address of the Inorder successor
 */
static BSTNode* BSTInorderSuccessor(BSTNode* node)
{
    BSTNode *inOrdSucc = NULL;
    if(NULL == node)
        return NULL;

    /*Traverse the right subtree and find the minimum value */
    if( node->right != NULL )
        return BSTMinVal(node->right);

    inOrdSucc = node->parent;

    while(inOrdSucc != NULL && node == inOrdSucc->right)
    {
        node = inOrdSucc;
        inOrdSucc = inOrdSucc->parent;
    }
    return inOrdSucc;

}

/* @brief Helper Function to update the parent node links in a BST
 * @param node Pointer to pointer to the node whose parent will be updated
 * @param ptr Target Link
 * @return void
 */
static inline void updateParent(BSTNode **node, BSTNode *ptr)
{
    /*If the child is a left child*/
    if(BSTFindChildLoc((*node)->parent, *node) == "LEFT")
    {
        (*node)->parent->left = ptr;
    }
    /*If the child is a right child*/
    else
    {
        (*node)->parent->right = ptr;
    }
}

/* @brief Function to delete a node in a BST
 * @param root Pointer to pointer to the root of the BST
 * @param data Pointer to the data to be searched
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return void
 */
void BSTDelete(BSTNode **root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *ptr = NULL;
    BSTNode *tmp = NULL;

    if(NULL == root)
    {
        printf("Error: Null root\n");
        return;
    }

    /*Search if the node exists in the BST*/
    ptr = BSTSearch(*root, data, cmp_fn);

    if(NULL == ptr)
    {
        printf("Error: Node not found\n");
        return;
    }

    /*If the node has no children*/
    if(ptr->left == NULL && ptr->right == NULL)
    {
        /*No children*/
         tmp = ptr;

         /*Non-Root Node*/
         if(ptr->parent)
            updateParent(&ptr, NULL);   /*Update the parent's link*/
         /*Root Node*/
         else
             *root = NULL;

         ptr = NULL;
         free(tmp);
         printf("DeAllocated Node with address %p\n", tmp);
    }
    /*If the node has single child*/
    else if((ptr->left != NULL && ptr->right == NULL) || (ptr->left == NULL && ptr->right != NULL))
    {
        tmp = ptr;

        /*Single Child*/
        if((ptr->left != NULL) && (ptr->right == NULL))
        {
            ptr->left->parent = ptr->parent;

            /*Non-Root Node*/
            if(ptr->parent)
                updateParent(&ptr, ptr->left);   /*Update the parent's link*/
            /*Root Node*/
            else
                *root = ptr->left;
        }
        else
        {
            ptr->right->parent = ptr->parent;   /*Update the parent's link*/
            /*Non-Root Node*/
            if(ptr->parent)
                updateParent(&ptr, ptr->right);
            /*Root Node*/
            else
                *root = ptr->right;
        }

        free(tmp);
        printf("DeAllocated Node with address %p\n", tmp);
    }
    /*If the node has two children*/
    else if((ptr->left != NULL) && (ptr->right != NULL))
    {
        /*Find the inorder successor of the node*/
        BSTNode *inOrdSucc = BSTInorderSuccessor(ptr);

        /*Swap the node's data with inorder successor's data*/
        BSTSwapNodeData(&ptr, &inOrdSucc);

        /*Delete the inorder successor node*/
        BSTDelete(&inOrdSucc, data, cmp_fn);
    }
}

/* @brief Function to search a data in a BST
 * @param root Pointer to the root of the BST
 * @param data Pointer to the data to be searched
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return Address of the node found
 *         NULL if node not found
 */
BSTNode* BSTSearch(BSTNode *root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *ptr = NULL;

    if(NULL == root)
        return NULL;

    ptr = root;

    /*If the data is found*/
    if(cmp_fn(data, ptr->data) == 0)
    {
        return ptr;
    }
    /*If data is greater than the current node's data*/
    else if(cmp_fn(data, ptr->data) == 1)
    {
        return BSTSearch(ptr->right, data, cmp_fn);
    }
    /*If data is lesser than the current node's data*/
    else if(cmp_fn(data, ptr->data) == -1)
    {
        return BSTSearch(ptr->left, data, cmp_fn);
    }

    return NULL;
}

/* @brief Function to traverse all nodes in a BST in InOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTInOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    if(root->left)
        BSTInOrder(root->left, display_fn);

    printf("[%p]",root->data);
    display_fn(root);

    if(root->right)
        BSTInOrder(root->right, display_fn);

}

/* @brief Function to traverse all nodes in a BST in PostOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTPostOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    if(root->left)
        BSTPostOrder(root->left, display_fn);

    if(root->right)
        BSTPostOrder(root->right, display_fn);

    printf("[%p]",root->data);
    display_fn(root);
}

/* @brief Function to traverse all nodes in a BST in PreOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTPreOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    printf("[%p]",root->data);
    display_fn(root);

    if(root->left)
        BSTPreOrder(root->left, display_fn);

    if(root->right)
        BSTPreOrder(root->right, display_fn);

}

/* @brief Function to display all nodes in a BST
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
void BSTDisplay(BSTNode *root, void (*display_fn)(BSTNode *))
{
    printf("InOrder ->",root->data);
    BSTInOrder(root,display_fn);
    printf("\n",root->data);

    printf("PreOrder ->",root->data);
    BSTPreOrder(root,display_fn);
    printf("\n",root->data);

    printf("PostOrder ->",root->data);
    BSTPostOrder(root,display_fn);
    printf("\n",root->data);
}

 
/*bstdriver.c*/
/*
 * Compile: gcc -o test bst.c bstdriver.c
 * Run: ./test
 */
#include <stdio.h>
#include "bst.h"

int data[]={9,1,6,3,8,4,2,5,7};

/*Comparison function*/
int cmp_fn(void *data1, void *data2)
{
    if(*((int*)data1) > *((int*)data2))
        return 1;
    else if(*((int*)data1) < *((int*)data2))
        return -1;
    else
        return 0;
}

/*Display Function*/
static void displayNode(BSTNode *node)
{
    if(node)
        printf("%d ",*((int*)node->data));
}

int main()
{
    BSTNode *root = NULL;

    int i,sVal=-1;
    int size = sizeof(data)/sizeof(data[0]);

    for(i=0; i < size; i++)
        BSTInsert(&root, &data[i], cmp_fn);

    BSTDisplay(root, displayNode);

    printf("Search Value : ");
    scanf("%d", &sVal);

    if(NULL == BSTSearch(root, &sVal, cmp_fn))
        printf("Not Found\n");
    else
        printf("Found\n");

    printf("Delete Value : ");
    scanf("%d", &sVal);
    BSTDelete(&root, &sVal, cmp_fn);
    BSTDisplay(root, displayNode);

    BSTDestroy(root);
}

FTP implementation in C

noreply@blogger.com (Varun) — Sun, 23 Sep 2012 18:31:00 +0000

Most of the beginners would wonder how the known services work. Well this post will give an overview of one of the well-written services in C , the FTP application. I thought that there is no need to re-invent the wheel and use this code as is from Apple's open source initiative.The code is written in C.

I am providing the code only for the main file which contains FTP specific functions. The rest of the supporting files including the Makefile can be downloaded from here.

Disclaimer : This code is taken from Apple Opensource . I don't want Apple to sue me ;)

 /*ftp.c*/

/*
 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * "Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
 * Reserved.  This file contains Original Code and/or Modifications of
 * Original Code as defined in and that are subject to the Apple Public
 * Source License Version 1.0 (the 'License').  You may not use this file
 * except in compliance with the License.  Please obtain a copy of the
 * License at http://www.apple.com/publicsource and read it before using
 * this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License."
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*
 * Copyright (c) 1985, 1989, 1993, 1994
 * The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 * This product includes software developed by the University of
 * California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */


#include <sys/param.h>
#include <sys/stat.h>
#include <sys/ioctl.h>
#include <sys/socket.h>
#include <sys/time.h>
#include <sys/file.h>

#include <netinet/in.h>
#include <netinet/in_systm.h>
#include <netinet/ip.h>
#include <arpa/inet.h>
#include <arpa/ftp.h>
#include <arpa/telnet.h>

#include <ctype.h>
#include <err.h>
#include <errno.h>
#include <fcntl.h>
#include <netdb.h>
#include <pwd.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdarg.h>

#include "ftp_var.h"

extern int h_errno;

struct sockaddr_in hisctladdr;
struct sockaddr_in data_addr;
int data = -1;
int abrtflag = 0;
jmp_buf ptabort;
int ptabflg;
int ptflag = 0;
struct sockaddr_in myctladdr;
off_t restart_point = 0;

FILE *cin, *cout;

char *
hookup(host, port)
 char *host;
 int port;
{
 struct hostent *hp = 0;
 int s, len, tos;
 static char hostnamebuf[80];

 memset((char *)&hisctladdr, 0, sizeof (hisctladdr));
 hisctladdr.sin_addr.s_addr = inet_addr(host);
 if (hisctladdr.sin_addr.s_addr != -1) {
  hisctladdr.sin_family = AF_INET;
  (void) strncpy(hostnamebuf, host, sizeof(hostnamebuf));
 } else {
  hp = gethostbyname(host);
  if (hp == NULL) {
   warnx("%s: %s", host, hstrerror(h_errno));
   code = -1;
   return ((char *) 0);
  }
  hisctladdr.sin_family = hp->h_addrtype;
  memmove((caddr_t)&hisctladdr.sin_addr,
    hp->h_addr_list[0], hp->h_length);
  (void) strncpy(hostnamebuf, hp->h_name, sizeof(hostnamebuf));
 }
 hostname = hostnamebuf;
 s = socket(hisctladdr.sin_family, SOCK_STREAM, 0);
 if (s < 0) {
  warn("socket");
  code = -1;
  return (0);
 }
 hisctladdr.sin_port = port;
 while (connect(s, (struct sockaddr *)&hisctladdr, sizeof (hisctladdr)) < 0) {
  if (hp && hp->h_addr_list[1]) {
   int oerrno = errno;
   char *ia;

   ia = inet_ntoa(hisctladdr.sin_addr);
   errno = oerrno;
   warn("connect to address %s", ia);
   hp->h_addr_list++;
   memmove((caddr_t)&hisctladdr.sin_addr,
     hp->h_addr_list[0], hp->h_length);
   fprintf(stdout, "Trying %s...\n",
    inet_ntoa(hisctladdr.sin_addr));
   (void) close(s);
   s = socket(hisctladdr.sin_family, SOCK_STREAM, 0);
   if (s < 0) {
    warn("socket");
    code = -1;
    return (0);
   }
   continue;
  }
  warn("connect");
  code = -1;
  goto bad;
 }
 len = sizeof (myctladdr);
 if (getsockname(s, (struct sockaddr *)&myctladdr, &len) < 0) {
  warn("getsockname");
  code = -1;
  goto bad;
 }
#ifdef IP_TOS
 tos = IPTOS_LOWDELAY;
 if (setsockopt(s, IPPROTO_IP, IP_TOS, (char *)&tos, sizeof(int)) < 0)
  warn("setsockopt TOS (ignored)");
#endif
 cin = fdopen(s, "r");
 cout = fdopen(s, "w");
 if (cin == NULL || cout == NULL) {
  warnx("fdopen failed.");
  if (cin)
   (void) fclose(cin);
  if (cout)
   (void) fclose(cout);
  code = -1;
  goto bad;
 }
 if (verbose)
  printf("Connected to %s.\n", hostname);
 if (getreply(0) > 2) {  /* read startup message from server */
  if (cin)
   (void) fclose(cin);
  if (cout)
   (void) fclose(cout);
  code = -1;
  goto bad;
 }
#ifdef SO_OOBINLINE
 {
 int on = 1;

 if (setsockopt(s, SOL_SOCKET, SO_OOBINLINE, (char *)&on, sizeof(on))
  < 0 && debug) {
   warn("setsockopt");
  }
 }
#endif /* SO_OOBINLINE */

 return (hostname);
bad:
 (void) close(s);
 return ((char *)0);
}

int
login(host)
 char *host;
{
 char tmp[80];
 char *user, *pass, *acct;
 int n, aflag = 0;

 user = pass = acct = 0;
 if (ruserpass(host, &user, &pass, &acct) < 0) {
  code = -1;
  return (0);
 }
 while (user == NULL) {
  char *myname = getlogin();

  if (myname == NULL) {
   struct passwd *pp = getpwuid(getuid());

   if (pp != NULL)
    myname = pp->pw_name;
  }
  if (myname)
   printf("Name (%s:%s): ", host, myname);
  else
   printf("Name (%s): ", host);
  (void) fgets(tmp, sizeof(tmp) - 1, stdin);
  tmp[strlen(tmp) - 1] = '\0';
  if (*tmp == '\0')
   user = myname;
  else
   user = tmp;
 }
 n = command("USER %s", user);
 if (n == CONTINUE) {
  if (pass == NULL)
   pass = getpass("Password:");
  n = command("PASS %s", pass);
 }
 if (n == CONTINUE) {
  aflag++;
  acct = getpass("Account:");
  n = command("ACCT %s", acct);
 }
 if (n != COMPLETE) {
  warnx("Login failed.");
  return (0);
 }
 if (!aflag && acct != NULL)
  (void) command("ACCT %s", acct);
 if (proxy)
  return (1);
 for (n = 0; n < macnum; ++n) {
  if (!strcmp("init", macros[n].mac_name)) {
   (void) strcpy(line, "$init");
   makeargv();
   domacro(margc, margv);
   break;
  }
 }
 return (1);
}

void
cmdabort()
{

 printf("\n");
 (void) fflush(stdout);
 abrtflag++;
 if (ptflag)
  longjmp(ptabort,1);
}

int command(const char *fmt, ...)
{
 va_list ap;
 int r;
 sig_t oldintr;

 abrtflag = 0;
 if (debug) {
  printf("---> ");
  va_start(ap, fmt);
  if (strncmp("PASS ", fmt, 5) == 0)
   printf("PASS XXXX");
  else 
   vfprintf(stdout, fmt, ap);
  va_end(ap);
  printf("\n");
  (void) fflush(stdout);
 }
 if (cout == NULL) {
  warn("No control connection for command");
  code = -1;
  return (0);
 }
 oldintr = signal(SIGINT, cmdabort);
 va_start(ap, fmt);
 vfprintf(cout, fmt, ap);
 va_end(ap);
 fprintf(cout, "\r\n");
 (void) fflush(cout);
 cpend = 1;
 r = getreply(!strcmp(fmt, "QUIT"));
 if (abrtflag && oldintr != SIG_IGN)
  (*oldintr)(SIGINT);
 (void) signal(SIGINT, oldintr);
 return (r);
}

char reply_string[BUFSIZ];  /* last line of previous reply */

int
getreply(expecteof)
 int expecteof;
{
 int c, n;
 int dig;
 int originalcode = 0, continuation = 0;
 sig_t oldintr;
 int pflag = 0;
 char *cp, *pt = pasv;

 oldintr = signal(SIGINT, cmdabort);
 for (;;) {
  dig = n = code = 0;
  cp = reply_string;
  while ((c = getc(cin)) != '\n') {
   if (c == IAC) {     /* handle telnet commands */
    switch (c = getc(cin)) {
    case WILL:
    case WONT:
     c = getc(cin);
     fprintf(cout, "%c%c%c", IAC, DONT, c);
     (void) fflush(cout);
     break;
    case DO:
    case DONT:
     c = getc(cin);
     fprintf(cout, "%c%c%c", IAC, WONT, c);
     (void) fflush(cout);
     break;
    default:
     break;
    }
    continue;
   }
   dig++;
   if (c == EOF) {
    if (expecteof) {
     (void) signal(SIGINT,oldintr);
     code = 221;
     return (0);
    }
    lostpeer();
    if (verbose) {
     printf("421 Service not available, remote server has closed connection\n");
     (void) fflush(stdout);
    }
    code = 421;
    return (4);
   }
   if (c != '\r' && (verbose > 0 ||
       (verbose > -1 && n == '5' && dig > 4))) {
    if (proxflag &&
       (dig == 1 || dig == 5 && verbose == 0))
     printf("%s:",hostname);
    (void) putchar(c);
   }
   if (dig < 4 && isdigit(c))
    code = code * 10 + (c - '0');
   if (!pflag && code == 227)
    pflag = 1;
   if (dig > 4 && pflag == 1 && isdigit(c))
    pflag = 2;
   if (pflag == 2) {
    if (c != '\r' && c != ')')
     *pt++ = c;
    else {
     *pt = '\0';
     pflag = 3;
    }
   }
   if (dig == 4 && c == '-') {
    if (continuation)
     code = 0;
    continuation++;
   }
   if (n == 0)
    n = c;
   if (cp < &reply_string[sizeof(reply_string) - 1])
    *cp++ = c;
  }
  if (verbose > 0 || verbose > -1 && n == '5') {
   (void) putchar(c);
   (void) fflush (stdout);
  }
  if (continuation && code != originalcode) {
   if (originalcode == 0)
    originalcode = code;
   continue;
  }
  *cp = '\0';
  if (n != '1')
   cpend = 0;
  (void) signal(SIGINT,oldintr);
  if (code == 421 || originalcode == 421)
   lostpeer();
  if (abrtflag && oldintr != cmdabort && oldintr != SIG_IGN)
   (*oldintr)(SIGINT);
  return (n - '0');
 }
}

int
empty(mask, sec)
 struct fd_set *mask;
 int sec;
{
 struct timeval t;

 t.tv_sec = (long) sec;
 t.tv_usec = 0;
 return (select(32, mask, (struct fd_set *) 0, (struct fd_set *) 0, &t));
}

jmp_buf sendabort;

void
abortsend()
{

 mflag = 0;
 abrtflag = 0;
 printf("\nsend aborted\nwaiting for remote to finish abort\n");
 (void) fflush(stdout);
 longjmp(sendabort, 1);
}

#define HASHBYTES 1024

void
sendrequest(cmd, local, remote, printnames)
 char *cmd, *local, *remote;
 int printnames;
{
 struct stat st;
 struct timeval start, stop;
 int c, d;
 FILE *fin, *dout = 0, *popen();
 int (*closefunc) __P((FILE *));
 sig_t oldintr, oldintp;
 long bytes = 0, hashbytes = HASHBYTES;
 char *lmode, buf[BUFSIZ], *bufp;

 if (verbose && printnames) {
  if (local && *local != '-')
   printf("local: %s ", local);
  if (remote)
   printf("remote: %s\n", remote);
 }
 if (proxy) {
  proxtrans(cmd, local, remote);
  return;
 }
 if (curtype != type)
  changetype(type, 0);
 closefunc = NULL;
 oldintr = NULL;
 oldintp = NULL;
 lmode = "w";
 if (setjmp(sendabort)) {
  while (cpend) {
   (void) getreply(0);
  }
  if (data >= 0) {
   (void) close(data);
   data = -1;
  }
  if (oldintr)
   (void) signal(SIGINT,oldintr);
  if (oldintp)
   (void) signal(SIGPIPE,oldintp);
  code = -1;
  return;
 }
 oldintr = signal(SIGINT, abortsend);
 if (strcmp(local, "-") == 0)
  fin = stdin;
 else if (*local == '|') {
  oldintp = signal(SIGPIPE,SIG_IGN);
  fin = popen(local + 1, "r");
  if (fin == NULL) {
   warn("%s", local + 1);
   (void) signal(SIGINT, oldintr);
   (void) signal(SIGPIPE, oldintp);
   code = -1;
   return;
  }
  closefunc = pclose;
 } else {
  fin = fopen(local, "r");
  if (fin == NULL) {
   warn("local: %s", local);
   (void) signal(SIGINT, oldintr);
   code = -1;
   return;
  }
  closefunc = fclose;
  if (fstat(fileno(fin), &st) < 0 ||
      (st.st_mode&S_IFMT) != S_IFREG) {
   fprintf(stdout, "%s: not a plain file.\n", local);
   (void) signal(SIGINT, oldintr);
   fclose(fin);
   code = -1;
   return;
  }
 }
 if (initconn()) {
  (void) signal(SIGINT, oldintr);
  if (oldintp)
   (void) signal(SIGPIPE, oldintp);
  code = -1;
  if (closefunc != NULL)
   (*closefunc)(fin);
  return;
 }
 if (setjmp(sendabort))
  goto abort;

 if (restart_point &&
     (strcmp(cmd, "STOR") == 0 || strcmp(cmd, "APPE") == 0)) {
  int rc;

  switch (curtype) {
  case TYPE_A:
   rc = fseek(fin, (long) restart_point, SEEK_SET);
   break;
  case TYPE_I:
  case TYPE_L:
   rc = lseek(fileno(fin), restart_point, SEEK_SET);
   break;
  }
  if (rc < 0) {
   warn("local: %s", local);
   restart_point = 0;
   if (closefunc != NULL)
    (*closefunc)(fin);
   return;
  }
  if (command("REST %ld", (long) restart_point)
   != CONTINUE) {
   restart_point = 0;
   if (closefunc != NULL)
    (*closefunc)(fin);
   return;
  }
  restart_point = 0;
  lmode = "r+w";
 }
 if (remote) {
  if (command("%s %s", cmd, remote) != PRELIM) {
   (void) signal(SIGINT, oldintr);
   if (oldintp)
    (void) signal(SIGPIPE, oldintp);
   if (closefunc != NULL)
    (*closefunc)(fin);
   return;
  }
 } else
  if (command("%s", cmd) != PRELIM) {
   (void) signal(SIGINT, oldintr);
   if (oldintp)
    (void) signal(SIGPIPE, oldintp);
   if (closefunc != NULL)
    (*closefunc)(fin);
   return;
  }
 dout = dataconn(lmode);
 if (dout == NULL)
  goto abort;
 (void) gettimeofday(&start, (struct timezone *)0);
 oldintp = signal(SIGPIPE, SIG_IGN);
 switch (curtype) {

 case TYPE_I:
 case TYPE_L:
  errno = d = 0;
  while ((c = read(fileno(fin), buf, sizeof (buf))) > 0) {
   bytes += c;
   for (bufp = buf; c > 0; c -= d, bufp += d)
    if ((d = write(fileno(dout), bufp, c)) <= 0)
     break;
   if (hash) {
    while (bytes >= hashbytes) {
     (void) putchar('#');
     hashbytes += HASHBYTES;
    }
    (void) fflush(stdout);
   }
  }
  if (hash && bytes > 0) {
   if (bytes < HASHBYTES)
    (void) putchar('#');
   (void) putchar('\n');
   (void) fflush(stdout);
  }
  if (c < 0)
   warn("local: %s", local);
  if (d < 0) {
   if (errno != EPIPE) 
    warn("netout");
   bytes = -1;
  }
  break;

 case TYPE_A:
  while ((c = getc(fin)) != EOF) {
   if (c == '\n') {
    while (hash && (bytes >= hashbytes)) {
     (void) putchar('#');
     (void) fflush(stdout);
     hashbytes += HASHBYTES;
    }
    if (ferror(dout))
     break;
    (void) putc('\r', dout);
    bytes++;
   }
   (void) putc(c, dout);
   bytes++;
 /*  if (c == '\r') {      */
 /*  (void) putc('\0', dout);  // this violates rfc */
 /*   bytes++;    */
 /*  }                             */ 
  }
  if (hash) {
   if (bytes < hashbytes)
    (void) putchar('#');
   (void) putchar('\n');
   (void) fflush(stdout);
  }
  if (ferror(fin))
   warn("local: %s", local);
  if (ferror(dout)) {
   if (errno != EPIPE)
    warn("netout");
   bytes = -1;
  }
  break;
 }
 if (closefunc != NULL)
  (*closefunc)(fin);
 (void) fclose(dout);
 (void) gettimeofday(&stop, (struct timezone *)0);
 (void) getreply(0);
 (void) signal(SIGINT, oldintr);
 if (oldintp)
  (void) signal(SIGPIPE, oldintp);
 if (bytes > 0)
  ptransfer("sent", bytes, &start, &stop);
 return;
abort:
 (void) signal(SIGINT, oldintr);
 if (oldintp)
  (void) signal(SIGPIPE, oldintp);
 if (!cpend) {
  code = -1;
  return;
 }
 if (data >= 0) {
  (void) close(data);
  data = -1;
 }
 if (dout)
  (void) fclose(dout);
 (void) getreply(0);
 code = -1;
 if (closefunc != NULL && fin != NULL)
  (*closefunc)(fin);
 (void) gettimeofday(&stop, (struct timezone *)0);
 if (bytes > 0)
  ptransfer("sent", bytes, &start, &stop);
}

jmp_buf recvabort;

void
abortrecv()
{

 mflag = 0;
 abrtflag = 0;
 printf("\nreceive aborted\nwaiting for remote to finish abort\n");
 (void) fflush(stdout);
 longjmp(recvabort, 1);
}

void
recvrequest(cmd, local, remote, lmode, printnames)
 char *cmd, *local, *remote, *lmode;
 int printnames;
{
 FILE *fout, *din = 0;
 int (*closefunc) __P((FILE *));
 sig_t oldintr, oldintp;
 int c, d, is_retr, tcrflag, bare_lfs = 0;
 static int bufsize;
 static char *buf;
 long bytes = 0, hashbytes = HASHBYTES;
 struct timeval start, stop;
 struct stat st;

 is_retr = strcmp(cmd, "RETR") == 0;
 if (is_retr && verbose && printnames) {
  if (local && *local != '-')
   printf("local: %s ", local);
  if (remote)
   printf("remote: %s\n", remote);
 }
 if (proxy && is_retr) {
  proxtrans(cmd, local, remote);
  return;
 }
 closefunc = NULL;
 oldintr = NULL;
 oldintp = NULL;
 tcrflag = !crflag && is_retr;
 if (setjmp(recvabort)) {
  while (cpend) {
   (void) getreply(0);
  }
  if (data >= 0) {
   (void) close(data);
   data = -1;
  }
  if (oldintr)
   (void) signal(SIGINT, oldintr);
  code = -1;
  return;
 }
 oldintr = signal(SIGINT, abortrecv);
 if (strcmp(local, "-") && *local != '|') {
  if (access(local, 2) < 0) {
   char *dir = strrchr(local, '/');

   if (errno != ENOENT && errno != EACCES) {
    warn("local: %s", local);
    (void) signal(SIGINT, oldintr);
    code = -1;
    return;
   }
   if (dir != NULL)
    *dir = 0;
   d = access(dir ? local : ".", 2);
   if (dir != NULL)
    *dir = '/';
   if (d < 0) {
    warn("local: %s", local);
    (void) signal(SIGINT, oldintr);
    code = -1;
    return;
   }
   if (!runique && errno == EACCES &&
       chmod(local, 0600) < 0) {
    warn("local: %s", local);
    (void) signal(SIGINT, oldintr);
    (void) signal(SIGINT, oldintr);
    code = -1;
    return;
   }
   if (runique && errno == EACCES &&
      (local = gunique(local)) == NULL) {
    (void) signal(SIGINT, oldintr);
    code = -1;
    return;
   }
  }
  else if (runique && (local = gunique(local)) == NULL) {
   (void) signal(SIGINT, oldintr);
   code = -1;
   return;
  }
 }
 if (!is_retr) {
  if (curtype != TYPE_A)
   changetype(TYPE_A, 0);
 } else if (curtype != type)
  changetype(type, 0);
 if (initconn()) {
  (void) signal(SIGINT, oldintr);
  code = -1;
  return;
 }
 if (setjmp(recvabort))
  goto abort;
 if (is_retr && restart_point &&
     command("REST %ld", (long) restart_point) != CONTINUE)
  return;
 if (remote) {
  if (command("%s %s", cmd, remote) != PRELIM) {
   (void) signal(SIGINT, oldintr);
   return;
  }
 } else {
  if (command("%s", cmd) != PRELIM) {
   (void) signal(SIGINT, oldintr);
   return;
  }
 }
 din = dataconn("r");
 if (din == NULL)
  goto abort;
 if (strcmp(local, "-") == 0)
  fout = stdout;
 else if (*local == '|') {
  oldintp = signal(SIGPIPE, SIG_IGN);
  fout = popen(local + 1, "w");
  if (fout == NULL) {
   warn("%s", local+1);
   goto abort;
  }
  closefunc = pclose;
 } else {
  fout = fopen(local, lmode);
  if (fout == NULL) {
   warn("local: %s", local);
   goto abort;
  }
  closefunc = fclose;
 }
 if (fstat(fileno(fout), &st) < 0 || st.st_blksize == 0)
  st.st_blksize = BUFSIZ;
 if (st.st_blksize > bufsize) {
  if (buf)
   (void) free(buf);
  buf = malloc((unsigned)st.st_blksize);
  if (buf == NULL) {
   warn("malloc");
   bufsize = 0;
   goto abort;
  }
  bufsize = st.st_blksize;
 }
 (void) gettimeofday(&start, (struct timezone *)0);
 switch (curtype) {

 case TYPE_I:
 case TYPE_L:
  if (restart_point &&
      lseek(fileno(fout), restart_point, SEEK_SET) < 0) {
   warn("local: %s", local);
   if (closefunc != NULL)
    (*closefunc)(fout);
   return;
  }
  errno = d = 0;
  while ((c = read(fileno(din), buf, bufsize)) > 0) {
   if ((d = write(fileno(fout), buf, c)) != c)
    break;
   bytes += c;
   if (hash) {
    while (bytes >= hashbytes) {
     (void) putchar('#');
     hashbytes += HASHBYTES;
    }
    (void) fflush(stdout);
   }
  }
  if (hash && bytes > 0) {
   if (bytes < HASHBYTES)
    (void) putchar('#');
   (void) putchar('\n');
   (void) fflush(stdout);
  }
  if (c < 0) {
   if (errno != EPIPE)
    warn("netin");
   bytes = -1;
  }
  if (d < c) {
   if (d < 0)
    warn("local: %s", local);
   else
    warnx("%s: short write", local);
  }
  break;

 case TYPE_A:
  if (restart_point) {
   int i, n, ch;

   if (fseek(fout, 0L, SEEK_SET) < 0)
    goto done;
   n = restart_point;
   for (i = 0; i++ < n;) {
    if ((ch = getc(fout)) == EOF)
     goto done;
    if (ch == '\n')
     i++;
   }
   if (fseek(fout, 0L, SEEK_CUR) < 0) {
done:
    warn("local: %s", local);
    if (closefunc != NULL)
     (*closefunc)(fout);
    return;
   }
  }
  while ((c = getc(din)) != EOF) {
   if (c == '\n')
    bare_lfs++;
   while (c == '\r') {
    while (hash && (bytes >= hashbytes)) {
     (void) putchar('#');
     (void) fflush(stdout);
     hashbytes += HASHBYTES;
    }
    bytes++;
    if ((c = getc(din)) != '\n' || tcrflag) {
     if (ferror(fout))
      goto break2;
     (void) putc('\r', fout);
     if (c == '\0') {
      bytes++;
      goto contin2;
     }
     if (c == EOF)
      goto contin2;
    }
   }
   (void) putc(c, fout);
   bytes++;
 contin2: ;
  }
break2:
  if (bare_lfs) {
   printf("WARNING! %d bare linefeeds received in ASCII mode\n", bare_lfs);
   printf("File may not have transferred correctly.\n");
  }
  if (hash) {
   if (bytes < hashbytes)
    (void) putchar('#');
   (void) putchar('\n');
   (void) fflush(stdout);
  }
  if (ferror(din)) {
   if (errno != EPIPE)
    warn("netin");
   bytes = -1;
  }
  if (ferror(fout))
   warn("local: %s", local);
  break;
 }
 if (closefunc != NULL)
  (*closefunc)(fout);
 (void) signal(SIGINT, oldintr);
 if (oldintp)
  (void) signal(SIGPIPE, oldintp);
 (void) fclose(din);
 (void) gettimeofday(&stop, (struct timezone *)0);
 (void) getreply(0);
 if (bytes > 0 && is_retr)
  ptransfer("received", bytes, &start, &stop);
 return;
abort:

/* abort using RFC959 recommended IP,SYNC sequence  */

 if (oldintp)
  (void) signal(SIGPIPE, oldintr);
 (void) signal(SIGINT, SIG_IGN);
 if (!cpend) {
  code = -1;
  (void) signal(SIGINT, oldintr);
  return;
 }

 abort_remote(din);
 code = -1;
 if (data >= 0) {
  (void) close(data);
  data = -1;
 }
 if (closefunc != NULL && fout != NULL)
  (*closefunc)(fout);
 if (din)
  (void) fclose(din);
 (void) gettimeofday(&stop, (struct timezone *)0);
 if (bytes > 0)
  ptransfer("received", bytes, &start, &stop);
 (void) signal(SIGINT, oldintr);
}

/*
 * Need to start a listen on the data channel before we send the command,
 * otherwise the server's connect may fail.
 */
int
initconn()
{
 char *p, *a;
 int result, len, tmpno = 0;
 int on = 1;
 int a0, a1, a2, a3, p0, p1;

 if (passivemode) {
  data = socket(AF_INET, SOCK_STREAM, 0);
  if (data < 0) {
   perror("ftp: socket");
   return(1);
  }
  if ((options & SO_DEBUG) &&
      setsockopt(data, SOL_SOCKET, SO_DEBUG, (char *)&on,
          sizeof (on)) < 0)
   perror("ftp: setsockopt (ignored)");
  if (command("PASV") != COMPLETE) {
   printf("Passive mode refused.\n");
   goto bad;
  }

  /*
   * What we've got at this point is a string of comma
   * separated one-byte unsigned integer values.
   * The first four are the an IP address. The fifth is
   * the MSB of the port number, the sixth is the LSB.
   * From that we'll prepare a sockaddr_in.
   */

  if (sscanf(pasv,"%d,%d,%d,%d,%d,%d",
      &a0, &a1, &a2, &a3, &p0, &p1) != 6) {
   printf("Passive mode address scan failure. "
          "Shouldn't happen!\n");
   goto bad;
  }

  bzero(&data_addr, sizeof(data_addr));
  data_addr.sin_family = AF_INET;
  a = (char *)&data_addr.sin_addr.s_addr;
  a[0] = a0 & 0xff;
  a[1] = a1 & 0xff;
  a[2] = a2 & 0xff;
  a[3] = a3 & 0xff;
  p = (char *)&data_addr.sin_port;
  p[0] = p0 & 0xff;
  p[1] = p1 & 0xff;

  if (connect(data, (struct sockaddr *)&data_addr,
       sizeof(data_addr)) < 0) {
   perror("ftp: connect");
   goto bad;
  }
#ifdef IP_TOS
  on = IPTOS_THROUGHPUT;
  if (setsockopt(data, IPPROTO_IP, IP_TOS, (char *)&on,
          sizeof(int)) < 0)
   perror("ftp: setsockopt TOS (ignored)");
#endif
  return(0);
 }

noport:
 data_addr = myctladdr;
 if (sendport)
  data_addr.sin_port = 0; /* let system pick one */ 
 if (data != -1)
  (void) close(data);
 data = socket(AF_INET, SOCK_STREAM, 0);
 if (data < 0) {
  warn("socket");
  if (tmpno)
   sendport = 1;
  return (1);
 }
 if (!sendport)
  if (setsockopt(data, SOL_SOCKET, SO_REUSEADDR, (char *)&on, sizeof (on)) < 0) {
   warn("setsockopt (reuse address)");
   goto bad;
  }
 if (bind(data, (struct sockaddr *)&data_addr, sizeof (data_addr)) < 0) {
  warn("bind");
  goto bad;
 }
 if (options & SO_DEBUG &&
     setsockopt(data, SOL_SOCKET, SO_DEBUG, (char *)&on, sizeof (on)) < 0)
  warn("setsockopt (ignored)");
 len = sizeof (data_addr);
 if (getsockname(data, (struct sockaddr *)&data_addr, &len) < 0) {
  warn("getsockname");
  goto bad;
 }
 if (listen(data, 1) < 0)
  warn("listen");
 if (sendport) {
  a = (char *)&data_addr.sin_addr;
  p = (char *)&data_addr.sin_port;
#define UC(b) (((int)b)&0xff)
  result =
      command("PORT %d,%d,%d,%d,%d,%d",
        UC(a[0]), UC(a[1]), UC(a[2]), UC(a[3]),
        UC(p[0]), UC(p[1]));
  if (result == ERROR && sendport == -1) {
   sendport = 0;
   tmpno = 1;
   goto noport;
  }
  return (result != COMPLETE);
 }
 if (tmpno)
  sendport = 1;
#ifdef IP_TOS
 on = IPTOS_THROUGHPUT;
 if (setsockopt(data, IPPROTO_IP, IP_TOS, (char *)&on, sizeof(int)) < 0)
  warn("setsockopt TOS (ignored)");
#endif
 return (0);
bad:
 (void) close(data), data = -1;
 if (tmpno)
  sendport = 1;
 return (1);
}

FILE *
dataconn(lmode)
 char *lmode;
{
 struct sockaddr_in from;
 int s, fromlen = sizeof (from), tos;

 if (passivemode)
  return (fdopen(data, lmode));

 s = accept(data, (struct sockaddr *) &from, &fromlen);
 if (s < 0) {
  warn("accept");
  (void) close(data), data = -1;
  return (NULL);
 }
 (void) close(data);
 data = s;
#ifdef IP_TOS
 tos = IPTOS_THROUGHPUT;
 if (setsockopt(s, IPPROTO_IP, IP_TOS, (char *)&tos, sizeof(int)) < 0)
  warn("setsockopt TOS (ignored)");
#endif
 return (fdopen(data, lmode));
}

void
ptransfer(direction, bytes, t0, t1)
 char *direction;
 long bytes;
 struct timeval *t0, *t1;
{
 struct timeval td;
 float s;
 long bs;

 if (verbose) {
  tvsub(&td, t1, t0);
  s = td.tv_sec + (td.tv_usec / 1000000.);
#define nz(x) ((x) == 0 ? 1 : (x))
  bs = bytes / nz(s);
  printf("%ld bytes %s in %.3g seconds (%ld bytes/s)\n",
      bytes, direction, s, bs);
 }
}

/*
void
tvadd(tsum, t0)
 struct timeval *tsum, *t0;
{

 tsum->tv_sec += t0->tv_sec;
 tsum->tv_usec += t0->tv_usec;
 if (tsum->tv_usec > 1000000)
  tsum->tv_sec++, tsum->tv_usec -= 1000000;
}
*/

void
tvsub(tdiff, t1, t0)
 struct timeval *tdiff, *t1, *t0;
{

 tdiff->tv_sec = t1->tv_sec - t0->tv_sec;
 tdiff->tv_usec = t1->tv_usec - t0->tv_usec;
 if (tdiff->tv_usec < 0)
  tdiff->tv_sec--, tdiff->tv_usec += 1000000;
}

void
psabort()
{

 abrtflag++;
}

void
pswitch(flag)
 int flag;
{
 sig_t oldintr;
 static struct comvars {
  int connect;
  char name[MAXHOSTNAMELEN];
  struct sockaddr_in mctl;
  struct sockaddr_in hctl;
  FILE *in;
  FILE *out;
  int tpe;
  int curtpe;
  int cpnd;
  int sunqe;
  int runqe;
  int mcse;
  int ntflg;
  char nti[17];
  char nto[17];
  int mapflg;
  char mi[MAXPATHLEN];
  char mo[MAXPATHLEN];
 } proxstruct, tmpstruct;
 struct comvars *ip, *op;

 abrtflag = 0;
 oldintr = signal(SIGINT, psabort);
 if (flag) {
  if (proxy)
   return;
  ip = &tmpstruct;
  op = &proxstruct;
  proxy++;
 } else {
  if (!proxy)
   return;
  ip = &proxstruct;
  op = &tmpstruct;
  proxy = 0;
 }
 ip->connect = connected;
 connected = op->connect;
 if (hostname) {
  (void) strncpy(ip->name, hostname, sizeof(ip->name) - 1);
  ip->name[strlen(ip->name)] = '\0';
 } else
  ip->name[0] = 0;
 hostname = op->name;
 ip->hctl = hisctladdr;
 hisctladdr = op->hctl;
 ip->mctl = myctladdr;
 myctladdr = op->mctl;
 ip->in = cin;
 cin = op->in;
 ip->out = cout;
 cout = op->out;
 ip->tpe = type;
 type = op->tpe;
 ip->curtpe = curtype;
 curtype = op->curtpe;
 ip->cpnd = cpend;
 cpend = op->cpnd;
 ip->sunqe = sunique;
 sunique = op->sunqe;
 ip->runqe = runique;
 runique = op->runqe;
 ip->mcse = mcase;
 mcase = op->mcse;
 ip->ntflg = ntflag;
 ntflag = op->ntflg;
 (void) strncpy(ip->nti, ntin, 16);
 (ip->nti)[strlen(ip->nti)] = '\0';
 (void) strcpy(ntin, op->nti);
 (void) strncpy(ip->nto, ntout, 16);
 (ip->nto)[strlen(ip->nto)] = '\0';
 (void) strcpy(ntout, op->nto);
 ip->mapflg = mapflag;
 mapflag = op->mapflg;
 (void) strncpy(ip->mi, mapin, MAXPATHLEN - 1);
 (ip->mi)[strlen(ip->mi)] = '\0';
 (void) strcpy(mapin, op->mi);
 (void) strncpy(ip->mo, mapout, MAXPATHLEN - 1);
 (ip->mo)[strlen(ip->mo)] = '\0';
 (void) strcpy(mapout, op->mo);
 (void) signal(SIGINT, oldintr);
 if (abrtflag) {
  abrtflag = 0;
  (*oldintr)(SIGINT);
 }
}

void
abortpt()
{

 printf("\n");
 (void) fflush(stdout);
 ptabflg++;
 mflag = 0;
 abrtflag = 0;
 longjmp(ptabort, 1);
}

void
proxtrans(cmd, local, remote)
 char *cmd, *local, *remote;
{
 sig_t oldintr;
 int secndflag = 0, prox_type, nfnd;
 char *cmd2;
 struct fd_set mask;

 if (strcmp(cmd, "RETR"))
  cmd2 = "RETR";
 else
  cmd2 = runique ? "STOU" : "STOR";
 if ((prox_type = type) == 0) {
  if (unix_server && unix_proxy)
   prox_type = TYPE_I;
  else
   prox_type = TYPE_A;
 }
 if (curtype != prox_type)
  changetype(prox_type, 1);
 if (command("PASV") != COMPLETE) {
  printf("proxy server does not support third party transfers.\n");
  return;
 }
 pswitch(0);
 if (!connected) {
  printf("No primary connection\n");
  pswitch(1);
  code = -1;
  return;
 }
 if (curtype != prox_type)
  changetype(prox_type, 1);
 if (command("PORT %s", pasv) != COMPLETE) {
  pswitch(1);
  return;
 }
 if (setjmp(ptabort))
  goto abort;
 oldintr = signal(SIGINT, abortpt);
 if (command("%s %s", cmd, remote) != PRELIM) {
  (void) signal(SIGINT, oldintr);
  pswitch(1);
  return;
 }
 sleep(2);
 pswitch(1);
 secndflag++;
 if (command("%s %s", cmd2, local) != PRELIM)
  goto abort;
 ptflag++;
 (void) getreply(0);
 pswitch(0);
 (void) getreply(0);
 (void) signal(SIGINT, oldintr);
 pswitch(1);
 ptflag = 0;
 printf("local: %s remote: %s\n", local, remote);
 return;
abort:
 (void) signal(SIGINT, SIG_IGN);
 ptflag = 0;
 if (strcmp(cmd, "RETR") && !proxy)
  pswitch(1);
 else if (!strcmp(cmd, "RETR") && proxy)
  pswitch(0);
 if (!cpend && !secndflag) {  /* only here if cmd = "STOR" (proxy=1) */
  if (command("%s %s", cmd2, local) != PRELIM) {
   pswitch(0);
   if (cpend)
    abort_remote((FILE *) NULL);
  }
  pswitch(1);
  if (ptabflg)
   code = -1;
  (void) signal(SIGINT, oldintr);
  return;
 }
 if (cpend)
  abort_remote((FILE *) NULL);
 pswitch(!proxy);
 if (!cpend && !secndflag) {  /* only if cmd = "RETR" (proxy=1) */
  if (command("%s %s", cmd2, local) != PRELIM) {
   pswitch(0);
   if (cpend)
    abort_remote((FILE *) NULL);
   pswitch(1);
   if (ptabflg)
    code = -1;
   (void) signal(SIGINT, oldintr);
   return;
  }
 }
 if (cpend)
  abort_remote((FILE *) NULL);
 pswitch(!proxy);
 if (cpend) {
  FD_ZERO(&mask);
  FD_SET(fileno(cin), &mask);
  if ((nfnd = empty(&mask, 10)) <= 0) {
   if (nfnd < 0) {
    warn("abort");
   }
   if (ptabflg)
    code = -1;
   lostpeer();
  }
  (void) getreply(0);
  (void) getreply(0);
 }
 if (proxy)
  pswitch(0);
 pswitch(1);
 if (ptabflg)
  code = -1;
 (void) signal(SIGINT, oldintr);
}

void
reset(argc, argv)
 int argc;
 char *argv[];
{
 struct fd_set mask;
 int nfnd = 1;

 FD_ZERO(&mask);
 while (nfnd > 0) {
  FD_SET(fileno(cin), &mask);
  if ((nfnd = empty(&mask,0)) < 0) {
   warn("reset");
   code = -1;
   lostpeer();
  }
  else if (nfnd) {
   (void) getreply(0);
  }
 }
}

char *
gunique(local)
 char *local;
{
 static char new[MAXPATHLEN];
 char *cp = strrchr(local, '/');
 int d, count=0;
 char ext = '1';

 if (cp)
  *cp = '\0';
 d = access(cp ? local : ".", 2);
 if (cp)
  *cp = '/';
 if (d < 0) {
  warn("local: %s", local);
  return ((char *) 0);
 }
 (void) strcpy(new, local);
 cp = new + strlen(new);
 *cp++ = '.';
 while (!d) {
  if (++count == 100) {
   printf("runique: can't find unique file name.\n");
   return ((char *) 0);
  }
  *cp++ = ext;
  *cp = '\0';
  if (ext == '9')
   ext = '0';
  else
   ext++;
  if ((d = access(new, 0)) < 0)
   break;
  if (ext != '0')
   cp--;
  else if (*(cp - 2) == '.')
   *(cp - 1) = '1';
  else {
   *(cp - 2) = *(cp - 2) + 1;
   cp--;
  }
 }
 return (new);
}

void
abort_remote(din)
 FILE *din;
{
 char buf[BUFSIZ];
 int nfnd;
 struct fd_set mask;

 /*
  * send IAC in urgent mode instead of DM because 4.3BSD places oob mark
  * after urgent byte rather than before as is protocol now
  */
 sprintf(buf, "%c%c%c", IAC, IP, IAC);
 if (send(fileno(cout), buf, 3, MSG_OOB) != 3)
  warn("abort");
 fprintf(cout,"%cABOR\r\n", DM);
 (void) fflush(cout);
 FD_ZERO(&mask);
 FD_SET(fileno(cin), &mask);
 if (din) { 
  FD_SET(fileno(din), &mask);
 }
 if ((nfnd = empty(&mask, 10)) <= 0) {
  if (nfnd < 0) {
   warn("abort");
  }
  if (ptabflg)
   code = -1;
  lostpeer();
 }
 if (din && FD_ISSET(fileno(din), &mask)) {
  while (read(fileno(din), buf, BUFSIZ) > 0)
   /* LOOP */;
 }
 if (getreply(0) == ERROR && code == 552) {
  /* 552 needed for nic style abort */
  (void) getreply(0);
 }
 (void) getreply(0);
}

SSC Combined Graduate Level Examination 2012 Admit Card

noreply@blogger.com (Varun) — Thu, 28 Jun 2012 18:42:00 +0000

This would be helpful to those candidates who are having trouble finding their Admit Card for SSC Combined Graduate Level Examination 2012.

Please visit your local(state) SSC website and download the list of eligible candidates from there.
You can find your Roll No. Enlisted there and then it could be used to retrieve the Admit Card from the same site.

For Example, In Karntaka roll no. can be found using following steps:

1. Visit http://www.ssckkr.kar.nic.in/
2. On the homepage find the link
1.'"Click here to see the Roll NO. of the list of the provisionally eligible candidates for Combined Graduate Level Exam, 2012".
3. Then try to search your name in the list.
4. Then visit the link 1.Download Duplicate Admission Certificates for Combined Graduate Level EXAMINATION 2012 scheduled to be held on 01.07.2012
5. Enter your roll no. there and download your admit card.

This steps is valid for Karnataka State Candidates, It might be valid for other states too but somebody will have to check.

These are sites for various regions

SSC Northern Region Delhi (SSCNR)

SSC North Western Region Chandigarh

SSC Central Region (SSCCR) Allahabad

SSC Eastern Region Kolkata (SSCER)

SSC North Eastern Region (SSCNER) Guwahati

SSC Madhya Pradesh Region (SSCMPR)

SSC Southern Region (SSCSR) (Forenoon) || (Afternoon)

SSC Western Region (SSCWR) Maharashtra

SSC Kerala, Karnataka Region (SSCKKR)

Whereever you have filled the centre of examination , that will be you region 

libconfig to read configuration files in C/C++

noreply@blogger.com (Varun) — Thu, 23 Feb 2012 13:10:00 +0000

There are so many open-source libraries already available for parsing configuration files in c/c++ , but still we there are some which make their place up than rest of the others. One such library is libconfig . The reason being its simplicity and much lesser memory footprint. Most of the library for configuration files are XML based , but this library is text based and the structure of the configuration files is pretty simple.
e.g. In its simplest form a configuration file can look like :

port = 5000;

It can provide even more simpler configuration file for much complex data group. For example :

books = ( "inventory",
          { title  = "Treasure Island";
            author = "Robert Louis Stevenson";
            price  = 29.99;
            qty    = 5; },
          { title  = "Snow Crash";
            author = "Neal Stephenson";
            price  = 9.99;
            qty    = 8; },

{ } );

Here there is a set of data for the inventory of books with multiple fields for each book.

One of the most important feature of this library is that it supports a fully re-entrant parser which means that different configurations can be parsed in concurrent threads at the same time. Moreover the APIs are available for both C and C++ languages and there are hooks provided in the library to facilitate its use in other programming languages too.

The detailed documentation of this library can be found at Libconfig Manual. It supports multiple platforms such as Windows, Linux , Mac OS X and Solaris (POSIX compliant platforms).

To use it in a C/C++ program one just needs to add a single preprocessor directive

#include <libconfig.h>      /*For C*/

#include <libconfig.h++>    /*For C++*/

For dynamic linking -lconfig/-lconfig++ must be used for C/C++ respectively. Otherwise the libraries can be statically linked using the static linking option during the compilation.

e.g. ( -static $(LIBPTHREAD_INSTALL_DIR)/libpthread.a)

Issues as per the libconfig website:

Libconfig is fully reentrant; the functions in the library do not make use of global variables and do not maintain state between successive calls. Therefore two independent configurations may be safely manipulated concurrently by two distinct threads.
Libconfig is not thread-safe. The library is not aware of the presence of threads and knows nothing about the host system's threading model. Therefore, if an instance of a configuration is to be accessed from multiple threads, it must be suitably protected by synchronization mechanisms like read-write locks or mutexes; the standard rules for safe multithreaded access to shared data must be observed.
Libconfig is not async-safe. Calls should not be made into the library from signal handlers, because some of the C library routines that it uses may not be async-safe.
Libconfig is not guaranteed to be cancel-safe. Since it is not aware of the host system's threading model, the library does not contain any thread cancellation points. In most cases this will not be an issue for multithreaded programs. However, be aware that some of the routines in the library (namely those that read/write configurations from/to files or streams) perform I/O using C library routines which may potentially block; whether or not these C library routines are cancel-safe depends on the host system.

We will provide a simple example of how to read from a configuration file using libconfig:

 
/*config.c*/
/*
To compile : gcc -o config config.c -lconfig
To run     : ./config
*/
#include 
#include 

int main()
{
    config_t cfg;               /*Returns all parameters in this structure */
    config_setting_t *setting;
    const char *str1, *str2;
    int tmp;

    char *config_file_name = "config.txt";

    /*Initialization */
    config_init(&cfg);

    /* Read the file. If there is an error, report it and exit. */
    if (!config_read_file(&cfg, config_file_name))
    {
        printf("\n%s:%d - %s", config_error_file(&cfg), config_error_line(&cfg), config_error_text(&cfg));
        config_destroy(&cfg);
        return -1;
    }

    /* Get the configuration file name. */
    if (config_lookup_string(&cfg, "filename", &str1))
        printf("\nFile Type: %s", str1);
    else
        printf("\nNo 'filename' setting in configuration file.");

    /*Read the parameter group*/
    setting = config_lookup(&cfg, "params");
    if (setting != NULL)
    {
        /*Read the string*/
        if (config_setting_lookup_string(setting, "param1", &str2))
        {
            printf("\nParam1: %s", str2);
        }
        else
            printf("\nNo 'param1' setting in configuration file.");

        /*Read the integer*/
        if (config_setting_lookup_int(setting, "param2", &tmp))
        {
            printf("\nParam2: %d", tmp);
        }
        else
            printf("\nNo 'param2' setting in configuration file.");

        printf("\n");
    }

    config_destroy(&cfg);
}

And corresponding configuration file :

 
//config.txt
// Basic Information:
filename = "Sample Configuration File";

// Parameters
params = 
{
param1 = "Hello";

param2 = 1234;
};

Articles needed !

noreply@blogger.com (Anonymous) — Tue, 14 Feb 2012 06:10:00 +0000

Due to lack of time, I am not being able to write more posts. If anyone feels that they have some good topic to write about, please write to me and after moderation i can publish it on the blog.

Serialization using Google protobuf

noreply@blogger.com (Anonymous) — Sun, 28 Nov 2010 10:35:00 +0000

Protocol buffers (that's what protobuf means :)) are a means to serialize structured data. Now you may be wondering what this 'serialize' means.

To be brief : Serialization is a process of packing the data structures or objects into sequence of bits so that they can be stored in a file or a buffer and transmitted across the network and then can be retrieved on the same or other system environment. Examples include XML, JSON, ASN.1, YAML, ProtoBuf etc.

Advantages :
1. Persistent object creation
2. RPC enabling
3. Are simple
4. Save space on disk
5. Very fast
6. Platform and language independent

ProtoBuf is available freely from Google (http://code.google.com/p/protobuf/). Procedure of installation and compilation is present there.

Everything that needs to be serialized is put in a protocol buffer message (a .proto file). This file tells the compiler how the data is to be serialized.

For each field there are setter and getter functions fieldname() is a getter and set_fieldname() is a setter. Remember to use these functions as the exact way it is told here.
The tutorials for the different languages can be found here

I present a small simple example to use the protobuf library and there is much more than that one can do with the protobuf :)

To make and run the example (on linux) follow the steps :
1. Download the tar.gz package from here
2. Login as root
3. Untar it in your home directory (say user1)
4. Go inside the protobuf directory and run ./configure
5. Add the path /usr/local/lib to the environment variable LD_LIBRARY_PATH
6. Then run :
make
make install
7. You are now ready to use the library.
8. To use protobuf you will need following files (I am explaining for c++ only):
.cc file
.proto file
Makefile
Rest of the files are generated on the fly.

Here is an example of a Vehicle parts which contains three fields , two mandatory and one optional.
-Part ID (mandatory)
-Part Name (mandatory)
-Vendor (optional)

We write this in .proto file

//partbook.proto
package tutorial;

message Part {
  required string name = 1;
  required int32 partid = 2;        // Unique ID number for this part
  optional string vendor = 3;

}

message PartDetails {
  repeated Part part = 1;
}

Then we write a c++ program to use the library and .proto to add serialized data to the data file.

/*add_part.cc*/
#include <iostream>
#include <fstream>
#include <string>
#include "partbook.pb.h"
using namespace std;

/* This function fills in a Part message based on user input.*/
void PromptForPart(tutorial::Part* part) {
  cout << "Enter part ID number: ";
  int partid;
  cin >> partid;
  part->set_partid(partid);
  cin.ignore(256, '\n');

  cout << "Enter part name: ";
  getline(cin, *part->mutable_name());

  cout << "Enter vendor name (blank for none): ";
  string vendor;
  getline(cin, vendor);
  if (!vendor.empty()) {
    part->set_vendor(vendor);
  }

}

/* Main function:  Reads the entire part list from a file,
 * adds one part based on user input, then writes it back out to the same
 *   file.
 */
int main(int argc, char* argv[]) {
  /* Verify that the version of the library that we linked against is
   * compatible with the version of the headers we compiled against.
   */
  GOOGLE_PROTOBUF_VERIFY_VERSION;

  if (argc != 2) {
    cerr << "Usage:  " << argv[0] << " PART_BOOK_FILE" << endl;
    return -1;
  }

  tutorial::PartDetails part_book;

  {
    // Read the existing part book.
    fstream input(argv[1], ios::in | ios::binary);
    if (!input) {
      cout << argv[1] << ": File not found.  Creating a new file." << endl;
    } else if (!part_book.ParseFromIstream(&input)) {
      cerr << "Failed to parse part book." << endl;
      return -1;
    }
  }

  // Add a new part.
  PromptForPart(part_book.add_part());

  {
    // Write the new part book back to disk.
    fstream output(argv[1], ios::out | ios::trunc | ios::binary);
    if (!part_book.SerializeToOstream(&output)) {
      cerr << "Failed to write part book." << endl;
      return -1;
    }
  }

  // Optional:  Delete all global objects allocated by libprotobuf.
  google::protobuf::ShutdownProtobufLibrary();

  return 0;
}

Then we write a c++ program to use the library and .proto to serialize the data.

/*list_parts.cc*/
#include <iostream>
#include <fstream>
#include <string>
#include "partbook.pb.h"
using namespace std;

// Iterates though all parts in the PartDetails and prints info about them.
void ListParts(const tutorial::PartDetails& part_book) {
  for (int i = 0; i < part_book.part_size(); i++) {
    const tutorial::Part& part = part_book.part(i);

    cout << "Part ID: " << part.partid() << endl;
    cout << "  Name: " << part.name() << endl;
    if (part.has_vendor()) {
      cout << "  Vendor: " << part.vendor() << endl;
    }

  }
}

// Main function:  Reads the entire part book from a file and prints all
//   the information inside.
int main(int argc, char* argv[]) {
  // Verify that the version of the library that we linked against is
  // compatible with the version of the headers we compiled against.
  GOOGLE_PROTOBUF_VERIFY_VERSION;

  if (argc != 2) {
    cerr << "Usage:  " << argv[0] << " PART_BOOK_FILE" << endl;
    return -1;
  }

  tutorial::PartDetails part_book;

  {
    // Read the existing data file.
    fstream input(argv[1], ios::in | ios::binary);
    if (!part_book.ParseFromIstream(&input)) {
      cerr << "Failed to parse part book." << endl;
      return -1;
    }
  }

  ListParts(part_book);

  // Optional:  Delete all global objects allocated by libprotobuf.
  google::protobuf::ShutdownProtobufLibrary();

  return 0;
}

#Makefile
#This creates executables for python cpp and java , to create only one language use #'make cpp' or 'make python' or 'make java'

.PHONY: all cpp java python clean

all: cpp java python

cpp:    add_part_cpp    list_parts_cpp
java:   add_part_java   list_parts_java
python: add_part_python list_parts_python

clean:
 rm -f add_part_cpp list_parts_cpp add_part_java list_parts_java add_part_python list_parts_python
 rm -f javac_middleman AddPart*.class ListParts*.class com/example/tutorial/*.class
 rm -f protoc_middleman partbook.pb.cc partbook.pb.h partbook.pb2.py com/example/tutorial/PartBookProtos.java
 rm -f *.pyc
 rmdir com/example/tutorial 2>/dev/null || true
 rmdir com/example 2>/dev/null || true
 rmdir com 2>/dev/null || true

protoc_middleman: partbook.proto
 protoc --cpp_out=. --java_out=. --python_out=. partbook.proto
 @touch protoc_middleman

add_part_cpp: add_part.cc protoc_middleman
 pkg-config --cflags protobuf  # fails if protobuf is not installed
 c++ add_part.cc partbook.pb.cc -o add_part_cpp `pkg-config --cflags --libs protobuf`

list_parts_cpp: list_parts.cc protoc_middleman
 pkg-config --cflags protobuf  # fails if protobuf is not installed
 c++ list_parts.cc partbook.pb.cc -o list_parts_cpp `pkg-config --cflags --libs protobuf`

javac_middleman: AddPart.java ListParts.java protoc_middleman
 javac AddPart.java ListParts.java com/example/tutorial/PartBookProtos.java
 @touch javac_middleman

add_part_java: javac_middleman
 @echo "Writing shortcut script add_part_java..."
 @echo '#! /bin/sh' > add_part_java
 @echo 'java -classpath .:$$CLASSPATH AddPart "$$@"' >> add_part_java
 @chmod +x add_part_java

list_parts_java: javac_middleman
 @echo "Writing shortcut script list_parts_java..."
 @echo '#! /bin/sh' > list_parts_java
 @echo 'java -classpath .:$$CLASSPATH ListParts "$$@"' >> list_parts_java
 @chmod +x list_parts_java

add_part_python: add_part.py protoc_middleman
 @echo "Writing shortcut script add_part_python..."
 @echo '#! /bin/sh' > add_part_python
 @echo './add_part.py "$$@"' >> add_part_python
 @chmod +x add_part_python

list_parts_python: list_parts.py protoc_middleman
 @echo "Writing shortcut script list_parts_python..."
 @echo '#! /bin/sh' > list_parts_python
 @echo './list_parts.py "$$@"' >> list_parts_python
 @chmod +x list_parts_python

Save all these files under <proto-installation-path>/examples/ and run make

To run the example
./add_part_cpp <data-filename>
./list_parts_cpp <data-filename>

Simplest Codings

GenAI, Agents & Agentic AI: A Complete Hands-On Notebook

What's Inside

Table of Contents

How to Run It Yourself

The Notebook

GenAI, Agents & Agentic AI — Complete Learning Notebook

Learning Path

Section 1 — Setup & Provider Configuration

Section 2 — LLM Basics

Section 3 — Prompt Engineering

Section 4 — Chains

Section 5 — Memory & Conversation History

Section 6 — RAG (Retrieval-Augmented Generation)

Section 7 — Tools & Function Calling

Section 8 — Agents

Section 9 — Multi-Agent Systems

Section 10 — Agentic Patterns

Section 11 — Putting It All Together: Mini Agentic App

Summary & Next Steps

What you covered:

Intermediate next steps:

Useful references:

Key Takeaways

Q-Table Explained: 5 Steps to Master Reinforcement Learning

The Problem Q-Learning Solves

Why Supervised Learning Fails Here

The Explore-Exploit Dilemma

What "Reward" Means Computationally

The Reinforcement Learning Loop

Anatomy of a Q-Table

Initialization and Size

The Bellman Equation Demystified

Intuition First

The Formula

What Each Hyperparameter Controls

Temporal Difference: How Surprise Drives Learning

Step-by-Step: Building a Q-Table from Scratch

Our Scenario: The Warehouse Robot Navigator

Step 1: Define the Environment

Step 2: Initialize the Q-Table

Step 3: Epsilon-Greedy Policy

Step 4: Run Episodes and Apply the Update Rule

Step 5: Extract the Learned Policy

Full Java Implementation

Sample Output

Q-Table Convergence: How Values Change Over Episodes

Common Pitfalls and Debugging

1. Reward Shaping Mistakes

2. Learning Rate Woes

3. Discount Factor Edge Cases

4. The Q-Table Never Converges

Limitations and the Bridge to Deep Q-Networks

The State Space Explosion

The DQN Solution

Q-Table vs. Deep Q-Network

When Q-Tables Are Still the Right Tool

Recap: The 5 Steps

5 Steps to Master Q-Learning

Four Ways to Split Sentences (Without Machine Learning)

Sentence Splitting in the NLP Pipeline

Why Is Sentence Splitting Hard?

Method 1: Naïve Punctuation Split

The Idea

Java Implementation

When to Use It

Method 2: Abbreviation-Aware Splitting

The Idea

C++ Implementation

Limitations

When to Use It

Method 3: Regex-Based Heuristic Splitter

The Idea

Java Implementation

Breaking Down the Regex

When to Use It

Method 4: Finite State Machine (FSM) Splitter

The Idea

Interactive State Machine Transition Diagram

States in Our FSM